CF寒假补题集——1.23

B. Toy Blocks

题意：分配问题，n个盒子，把其中任意一个盒子拿出来把里面的积木分配给其他n-1个盒子，求使n-1个盒子里的积木数相同，最少还要额外补几块积木？

解题思路：求出 每个盒子平均分配后的可能的最大值， 1.当前所有盒子中所含积木的最大值2.平均值向上取整。

最后积木总数 - 取二者较大的一个*（n-1）== 额外要补贴的数的最小值；

AC:

#include 
#include 
using namespace std;
const int N =1e5+10;
int a[N];
int main()
{
   int t;
   cin>>t;
   while(t -- )
   {
       memset(a, 0, sizeof(a));
       long long n, sum = 0;
       cin>>n;
       for(int i =1; i<= n; i++)
       {
           cin>>a[i];
           sum += a[i];
       }
       long long  max_ = *max_element(a+1, a+n+1);
       long long other = sum /(n-1);
       if( sum %(n-1)) other ++;
       max_ = max(max_ , other);

       cout<<(max_)*(n-1) - sum< 
C. Plus and Multiply
 
题目大意：给一个数n，问是否是特殊集合中的数（特殊集合满足，有一个1，任意一个数都是由已有元素*a 或者 已有元素+b得来的）
 
解题思路：
 
1.特判掉几种
 
        1.n == 1, 必在集合中；
 
        2.a == 1时， 所有的数都是公差为b， 起点为1的等差数列；
 
                若满足（n-1）%b == 0， 必在数列中。
 
                若不满足，必不在。
 
        3.枚举可能的起点，c0 = 1, c0=a; c0 = a^2
 
                集合中任意一个数，1除外，都能分解为ci  + b*(ci-1) ==  n ; 或者 ci = n;这里的ci等于a的次方，因此 若 第一种情况 当 (n - ci) / b == (ci-1),则(n - ci) % b == 0， 若第二种情况 n-ci = 0, 则 (n - ci) % b == 0；，其余情况n都不在集合中；
 
AC代码：
 
#include 
#include 
using namespace std;
const int N =1e5+10;

int main()
{
   int t;
   cin>>t;
   while(t -- )
   {
      long long n, a, b;
        cin>>n>>a>>b;
        if(n == 1)
        {
            cout<<"Yes"< 
什么时候才能又快又对地A完前三道QAQ
 
PS：这两道都要注意有的数据类型，必须用long long 及以上，不然sum会错……;