Wannafly挑战赛29-A/B

时间：2021-10-08 22:25:20

链接：https://ac.nowcoder.com/acm/contest/271/A
来源：牛客网

御坂美琴
时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 131072K，其他语言262144K
64bit IO Format: %lld

题目描述

misaka是呱太爷爷的小粉丝，呱太爷爷有一句话说的好："一尺之棰，日取其半，万世不竭"。

misaka现在有 n 个呱太玩偶放在一堆，每一次操作，misaka会选择当前个数 > 1 的一堆呱太玩偶。并将这一堆呱太玩偶分成 Wannafly挑战赛29-A/B和 Wannafly挑战赛29-A/B 两堆，x 是当前这一堆玩偶的个数。现在 misaka 想将玩偶分成 m 堆，其中第 i 堆呱太玩偶的个数是 ai ，你需要告诉 misaka 是否能通过若干次操作将玩偶分成指定的这 m 堆。如果可以输出 Wannafly挑战赛29-A/B ，否则输出 Wannafly挑战赛29-A/B 。

输入描述:

第一行两个数 n, m 。
接下来一行 m 个数 a

i

 。

输出描述:

输出共一个字符串

Wannafly挑战赛29-A/B

，表示 misaka 能否将玩偶分成指定的 m 堆。
　　　　简单模拟一下就好了，我的做法是先将输入的ai按降序排列，然后不断地由大到小分解石头，中间遇到等于ai的石头数就把这堆给它。
一开始以为queue就好了，WA很多次，后来发现要用priority_queue，比如25，25-> 25,13,12 -> 13,12,13,12  这样就不是严格递减了，
换成堆AC。
　　
 # include <iostream>

 # include <cstdio>

 # include <cstring>

 #include<queue>

 # include <algorithm>

 using namespace std;

 typedef long long LL;

 using namespace std;

 LL a[];

 priority_queue<LL>q;

 int main(){

     LL n,m;

     cin>>n>>m;

     LL s=;

     for(int i=;i<=m;++i)scanf("%lld",a+i),s+=a[i];

     if(s!=n){

         puts("ham");

         return ;

     }

     q.push(n);

     bool ok;

     sort(a+,a++m,greater<LL>());

     int i=;

     while(i<=m && !q.empty() ){

         LL p=q.top();

         q.pop();

         if(p>a[i]){

             q.push(p-p/);

             q.push(p/);

         }

         else if(p==a[i]){

             n-=a[i];

             i++;

             continue;

         }

         else{

             break;

         }

     }

     if(n== && i==m+) puts("misaka");

     else puts("ham");

     return ;

 }

链接：https://ac.nowcoder.com/acm/contest/271/B
来源：牛客网

白井黑子
时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 524288K，其他语言1048576K
64bit IO Format: %lld

题目描述

kuroko 作为常盘台唯一的空间系能力者，在每年例行的能力测试中可绝对不能让 misaka 失望哦，但是由于她的等级只是 level 4「大能力者」，在能力测试中会遇到不少困难。kuroko 是一个凡事都会尽力的好女孩，所以请你帮她算出她最多能完成多少测试吧

对于空间系能力者测试的内容是检验对物体进行空间移动的能力，测验时一共有 n 个物品放在一条直线上，每个物品都有一个坐标 ai ，kuroko 可以选择两个物品并使用能力交换它们的位置，但是如果两个物品的坐标不满足 kuroko 的计算公式的话，她就没有办法使用能力。

具体来说，对于坐标 ai ，其在 kuroko 的计算公式中是用参数 f(ai) 表示的。f(ai) 是 ai 各数位相乘的结果，由于 level 4「大能力者」在学园都市中也是很强大的存在，所以满足公式的条件不会太苛刻，对于两个物品 ai, aj ，如果 f(ai) x f(aj) 不能被某个自然数的 k 次幂表示 的话，那么 kuroko 就能对这两个物品使用能力。

现在 kuroko 想知道，有多少对物品她可以对其施展能力，知道了这个后她就知道自己能完成多少测验了。

这里认为任何自然数的 0 次幂都是1;

 
 
 
 
   一开始直接理解错题意，以为是k^x,想着直接暴力扫就好了，后来发现是x^k = =
　注意到把a数组转化为f之后，f里每个数的因子都只有2，3，5，7这四个，每个数都可以写作  A=2^v1 * 3^v3 * 5^v5 * 7^v7 的格式。
我们把每个数的<a1,a3,a5,a7>处理出来，要想A1*A1'是k次幂数显然要满足(vi+vi')%k==0,然后每次找他的补集统计一下不合法的数量就好了。
A<=1e18所以 a1,a3,a5,a7<=60，注意特判一下
k=0的情况。


段错误半天，后来发现找补集的时候可能对应的系数超出60，也就说明不存在这种方案，直接特判下就过了。




 #include<iostream>

 #include<cstdio>

 #include<cstring>

 #include<queue>

 #include<map>

 #include<algorithm>

 using namespace std;

 typedef long long LL;

 using namespace std;

 LL a[];

 int v[]={,,,};

 int g[][][][];

 int b[][];

 LL f(LL n){

     if(!n) return ;

     LL s=;

     while(n){

         s*=(n%);

         n/=;

     }

     return s;

 }

 int main(){

     LL s=,n,k,zero=;

     scanf("%lld%lld",&n,&k);

     for(int i=;i<=n;++i) scanf("%lld",a+i),a[i]=f(a[i]);

     if(k==){

         puts("");

         return ;

     }

     if(k==){

         for(int i=;i<=n;++i)if(a[i]==)s++;

         printf("%lld\n",n*(n-)/-s*(s-)/);

         return ;

     }

     for(int i=;i<=n;++i){

         if(a[i]==){zero++;continue;}

         LL tmp=a[i];

         for(int j=;j<;++j){

             while(tmp&&tmp%v[j]==){

                 b[i][j]++;

                 tmp/=v[j];

             }

             b[i][j]%=k;

             if(b[i][j]>){

                 while()puts("fuck");

             }

         }

         g[b[i][]][b[i][]][b[i][]][b[i][]]++;

     }

     LL ans=;

     for(int i=;i<=n;++i){

         if(a[i]==){

             ans+=n-i;

             zero--;

             continue;

         }

         int u[];

         g[b[i][]][b[i][]][b[i][]][b[i][]]--;

         for(int j=;j<;++j){

             if(b[i][j]==) u[j]=;

             else u[j]=(k-b[i][j])%k;

             if(u[j]>)u[j]=;

         }

         ans+=g[u[]][u[]][u[]][u[]]+zero;

     }

     ans=n*(n-)/-ans;

     printf("%lld\n",ans);

     return ;

 } 




 


 




相关文章