cf div3 762 题解

cf div3 762 题解

题解若有错误，欢迎指正，q私法我或直接评论皆可
能力有限，暂时只有A到F，后期有所突破会更新g题h题

1.A.Square String?
题目链接：https://codeforces.com/contest/1619/problem/A
大致题意：
如果一个字符串在一行中被写了两次，那么这个字符串就叫做square，
判断一个字符串是不是square
思路：
很明显，判断前半部分与后半部分是否相同即可
特别的，如果字符串长度为奇数，必然不是

#include 
using namespace std;

void solve()
{
    string s;
    cin>>s;
    int num=0;
    int l=s.size();
     if(l%2==1) cout<<"no"<>t;
    while(t--)
    {
        solve();
    }
   // system("pause");
    return 0;
}

2.Squares and Cubes
题目链接：https://codeforces.com/contest/1619/problem/B
大致题意：
给定一个数n；让你找到从1到n的所有的平方数与立方数的个数；
思路1：
分别计算出平方数与立方数的个数，num1,num2，显然其中有一部分数同时是平方数和立方数，比如64，是8的平方或者4的立方；
那么我们要做的便是找出同时是平方数与立方数的个数num3;
最后的答案便是num1+num2-num3;
既是平方数又是立方数的数，就是6次方数
m^3，如果m是平方数，那么
m^3就是6次方数，所以对1到num2的三次方数中，又是平方数的个数为对num2开方，就是6次方数的个数

#include 
using namespace std;
void solve()
{
    int n;
    cin>>n;
    int num1=sqrt(n);
    int num2=0;
    for(int i=1;i<=n/i;i++)
    {
        if(pow(i,3)<=n&&pow(i+1,3)>n) num2=i;
    }
    int num3=sqrt(num2);
    cout<>t;
    while(t--)
    {
        solve();
    }
    system("pause");
    return 0;
}

思路二：给定的n的范围1e9，直接暴力
在set中每个元素的值都唯一，也就是插入n个1，里面只会有一个1；

#include 
 
using namespace std;
 
#define forn(i, n) for (int i = 0; i < int(n); i++)
 
int main() {
    int t;
    cin >> t;
    forn(tt, t) {
        int n;
        cin >> n;
        set a;
        for (int i = 1; i * i <= n; i++)
            a.insert(i * i);
        for (int i = 1; i * i * i <= n; i++)
            a.insert(i * i * i);
        cout << a.size() << endl;
    }

3.C. Wrong Addition
题目链接：https://codeforces.com/contest/1619/problem/C
题意：
有这样一种特殊的加法，a+b=c不进位，12+9=111
第一步，她把a的最后一位和b的最后一位相加，然后把它们的和写在答案里。
在接下来的每一步中，她都会对相同位置的每一对数字进行相同的 *** 作，并将结果写在答案的左边。
现在给你a和c，让你求b

思路：直接模拟，c的最后一位如果比a的最后1位大，直接减去即可
若是小，要向前借位，这个时候要注意，如果前面的那位数不为1，则b不存在
最后如果c有剩余全部加在b的后面，最后将字符串b翻转即可；

#include 
using namespace std;
void solve()
{
    string a,b,c;
    cin>>a>>c;
    int len1=a.size()-1;
    int len2=c.size()-1;
    int ok=1;
    for(int i=len1;i>=0;i--)
    {
        if(len2<0) 
        {
            ok=0;
            break;
        }
        int x=a[i]-'0',y=c[len2]-'0';
        if(y>=x) 
        {
            b+=y-x+'0';
            len2--;
        }
        else 
        {
            if(!len2||c[len2-1]!='1')
            {
                ok=0;
                break;
            }         
               b+=(10+y-x)+'0';
               len2-=2;
            
        }
    }
    while(len2>=0) b+=c[len2--];
    if(ok==0) cout<<"-1"<>t;
    while(t--)
    {
        solve();
    }
    system("pause");
    return 0;
}

，

4.New Year’s Problem
题目链接：https://codeforces.com/contest/1619/problem/D
大致题意：有m个商店和n个朋友，最多只能去n-1个商店
第j个朋友从礼物中获得aj个单位的快乐。α=min{a1,a2，…，an}。目标是买礼物，使α的值尽可能大；
思路：我们要使每一个ai都尽可能的大
①当某些人获得的最大快乐值在同一个商店时，最多去n-1个商店的限制相当于就没了，我们对每个人取得的最大快乐值取min就行
②当每个人获得的最大值都在不同的商店时，其中有一个商店肯定要选两个，那么我们要选择第二个值最大的商店买两个人的礼物，再与除去这两人的最大快乐取min

因此每个人的最大快乐与每个商店第二大的最大值值取min就是答案

#include 
using namespace std;
const int INF = 1000000000;
int main(){
  int t;
  cin >> t;
  for (int i = 0; i < t; i++){
    int m, n;
    cin >> m >> n;
    vector> p(m, vector(n));
    for (int j = 0; j < m; j++){
      for (int k = 0; k < n; k++){
        cin >> p[j][k];
      }
    }
    int ans = 0;
    for (int j = 0; j < m; j++){
      vector p2 = p[j];
      sort(p2.begin(), p2.end(), greater());
      ans = max(ans, p2[1]);
    }
    for (int j = 0; j < n; j++){
      int mx = 0;
      for (int k = 0; k < m; k++){
        mx = max(mx, p[k][j]);
      }
      ans = min(ans, mx);
    }
    cout << ans << endl;
  }
}

E. MEX and Increments
题目链接：https://codeforces.com/contest/1619/problem/E
大致题意：
给定一个长度为n的序列，对于从0到n的i，需要多少次 *** 作才可以使i为最小的自然数；
*** 作为，对于一个数+1；
思路：
先将这个序列从小到大排列：
对于从0到n的i值：
要使，最小自然数为i，我们首先需要将所有的i *** 作＋1一次；
我们再考虑有没有i-1，如果没有i-1，那么小于i-1的数是否有多余的，有多余的我们就可以对这个多余的数 *** 作多次得到i-1，没有多余的，则说明对于从i开始的所有数，不存在 *** 作使最小自然数为i，i+1，…n;

#include 
using namespace std;
const int N=200010;
int a[N];
int cnt[N];
long long ans[N];
void solve()
{
    memset(ans,-1,sizeof(ans));
    memset(a,0,sizeof(a));
    memset(cnt,0,sizeof(cnt));

    int n;cin>>n;
    for(int i=0;i>a[i];
        cnt[a[i]]++;
    }
    sort(a,a+n);
    stack  st;
    long long  sum=0;
    for(int i=0;i<=n;i++)
    {
        if(i>0&&cnt[i-1]==0)
        {
            if(st.empty())break;
            int j=st.top();
            st.pop();
            sum+=i-j-1;
        }
       // cout<0&&cnt[i-1]>1)
        {
            cnt[i-1]--;
            st.push(i-1);
        }
    }
    for(int i=0;i<=n;i++) cout<>t;
    while(t)
    {
        solve();
        t--;
    }
    //system("pause");
    return 0;
}

F. Let’s Play the Hat?
题目链接：https://codeforces.com/contest/1619/problem/F
大致题意：有m个桌子，n个人玩k局游戏，每个桌子坐n/m向上取整或者向下取整个数的人，使所有人坐上n/m向上取整人数桌子的次数相差不超过一次；
思路：将所有人看成一个循环即可，比如5 2 2；
大桌子坐3人，小桌子坐2人，
第一轮游戏 1，2，3 大桌子 4，5小桌子
看成一个循环，那么第二局初始状态为4 5 1 2 3
第二局游戏 4 5 1大桌子 2 3小桌子
（n-1/m）+1就是n/m向上取整的值

#include 
 
using namespace std;
 
#define forn(i, n) for (int i = 0; i < int(n); i++)
 
int main() {
    int t;
    cin >> t;
    forn(tt, t) {
        int n, m, k;
        cin >> n >> m >> k;
        vector p(n);
        forn(i, n)
            p[i] = i;
        if (tt > 0)
            cout << endl;
        forn(round, k) 
        {
            int index = 0;
            forn(table, m) {
                int size = n / m;
                if (table < n % m)
                    size++;
                cout << size;
                forn(j, size)
                    cout << " " << p[index++] + 1;
                cout << endl;                        
            }
            rotate(p.begin(), p.begin() + (n % m) * ((n + m - 1) / m), p.end());
        }
    }
}