CYY's Blog
Codeforces Round
CYY
  2022-05-11 09:10:39   2022-05-11 09:10:39  

题目来源
https://codeforces.com/contest/1676

第一题

题意

给一个6位的数，如果后三位数的和等于前三位数的和则输出YES反之输出NO

思路

将数后三位累加前三位累减，最后判断是否为0

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#include <iostream>
using namespace std;
int main(){
    int n;
    cin>>n;
    int cnt = 0;
    for(int i = 0;i<n;i++){
        int b;
        int sum = 0;
        int cnt = 0;
        cin>>b;
        while(b){
            int temp = b%10;
            b/=10;
            if(cnt >= 3){
                sum-=temp;
            }else{
                sum+=temp;
            }
            cnt++;
        }
        if(sum == 0) cout<<"YES"<<endl;
        else cout<<"NO"<<endl;
    }
    return 0;
}

第二题

题意

有n个盒子，每个盒子有一定的糖果，让你吃每个盒子里的糖果使所有盒子中的糖果变成一样的，输出吃了多少个糖果

思路

找出糖果最少的盒子，让每个盒子的糖果数量与最小的糖果数相减并累加起来就是结果。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <iostream>
using namespace std;
int num[55];
int main(){
    int t;
    cin>>t;
    while(t--){
        int n;
        cin>>n;
        int minnum = 0x3f3f3f3f;
        for(int i = 0;i<n;i++){
            cin>>num[i];
            minnum = min(minnum,num[i]);
        }
        int sum = 0;
        for(int i = 0;i<n;i++){
            sum+=(num[i]-minnum);
        }
        cout<<sum<<endl;
    }
    return 0;
}

第三题

题意

给n个单词，每个单词的长度为m,找出两个单词使他们满足变成相同的单词所需要的操作次数最小，操作是指单词的每一个字符例如a通过一次操作可以变为b，b通过3次操作变成e。best->cost,也就是b->c,e->o,s->s,t->t的操作次数的和。

思路

由于数据量比较小，直接暴力模拟，判断每个单词和其他单词每一位所需要的操作次数，记录最小操作数最后输出即可

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
int nums[55][55];
string strs[55];
int main(){
    int t;
    cin>>t;
    while(t--){
        int n,m;
        int ans = 0x3f3f3f3f;
        cin>>n>>m;
        for(int i = 0;i<n;i++) cin>>strs[i];
        
        for(int i = 0;i<n;i++){
            for(int j = i+1;j<n;j++){
                int sum = 0;
                for(int k = 0;k<m;k++){
                    sum += max(strs[i][k],strs[j][k])-min(strs[i][k],strs[j][k]); 
                }
                ans = min(ans,sum);
            }
        }
       
        cout<<ans<<endl;
    }
    return 0;
}

第四题

题意

给一个n*m的矩阵，找到某一个位置的值加上斜对角的其他所有值以及反对角的其他所有值的总和最大

思路

对角线可以看做是y=x+b的一条直线，反对角线可以看做是y=-x+b的直线，可以看出每一个b都确定一条直线，确定对角线的b=y-x,反对角线的b=y+x，读数的时候维护对角线的和以及反对角线的和，由于y-x可能为负数，我们是用数组来存储的所以需要对整个对角线的b进行偏移，偏移量为n，最后遍历整个矩阵，计算每个位置对角线数和[y-x+n]+反对角数和[x+y]-该位置的值[x][y]，然后选出最大值。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include <iostream>
#include <cstring>
using namespace std;
const int N = 210;
int nums[N][N];
int dg[2*N],udg[2*N];
int dp[N][N];
int main(){
    int t;
    cin>>t;
    while(t--){
        int n,m;
        memset(dg,0,sizeof dg);
        memset(udg,0,sizeof udg);
        cin>>n>>m;
        for(int i = 0;i<n;i++){
            for(int j = 0;j<m;j++){
                cin>>nums[i][j];
                dg[j-i+n]+=nums[i][j];
                udg[i+j]+=nums[i][j];
            }
        }
        int ans = 0;
        for(int i = 0;i<n;i++){
            for(int j = 0;j<m;j++){
                dp[i][j] = dg[j-i+n]+udg[i+j]-nums[i][j];
                ans = max(ans,dp[i][j]);
            }
        }
        cout<<ans<<endl;
    }
}

第五题

题意

给n个糖果，每个糖果有一定的甜度值，吃糖果可以获得甜度值。然后是q次询问，对于每一次询问，给一个待满足甜度值x，判断目前的糖果是否能够满足该甜度值，如果不能输出-1，如果能输出最少需要吃多少颗糖果。

思路

贪心+二分
我们尽量吃甜度值大的糖果，如果吃了还未满足又吃第二大的糖果，这样的结果总是最优的。因此我们可以对所以糖果甜度值按照从大到小排序，然后求前缀合，前缀和数组s满足贪心的思路。接下来就是在s数组中从1-n依次查询,第一个大于或等于待满足甜度值的下标，该下标表示要吃多少颗糖果，也就是答案。但是这道题数据量可能会超时所以采用二分查找。
注:对于所有糖果一起吃都无法满足的询问直接输出-1，

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;

typedef long long LL;
const int N = 300005;
int n,m;
LL nums[N],s[N];

bool cmp(LL a,LL b){
    return a>b;
}

int find(int a){
    int l = 1,r = n;
    
    while(l<r){
        int mid = l+r>>1;
        if(s[mid] < a){
            l = mid+1;
        }else{
            r = mid;
        }
    }
    
    return l;
}
int main(){
    int t;
    cin>>t;
    while(t--){
        memset(nums,0,sizeof nums);
        memset(s,0,sizeof s);

        cin>>n>>m;
        for(int i = 1;i<=n;i++){
            cin>>nums[i];
        }
        sort(nums+1,nums+n+1,cmp);
      
        cout<<endl;
        for(int i = 1;i<=n;i++){
            s[i] = s[i-1]+nums[i];
        }
        
        cout<<endl;
        while(m--){
            int temp;
            cin>>temp;
            if(temp>s[n]) 
                cout<<-1<<endl;
            else
                cout<<find(temp)<<endl;
        }
    }
    return 0;
}

第六题

题意

给一个数组，包含n个数，给一个k，寻找一段连续的序列，使得序列中的每一个数都在数组中至少出现k次。序列的左右边界l,r满足l<=r，比如1-3的序列就包含了123三个数，1-1包含了1一个数

思路

map结构存储+双指针
map底层使用的红黑树，会默认按照key进行排序。我们key存储的是数组中出现的数，value存储该数出现的次数。然后对整个map进行遍历，用l,len用于记录当前访问的一个序列，用ans_l,ans_len存储全局最长的序列。(r-l = len-1所以可以得到r = len-1+r)。
初始化len为-1，r指针遍历map的每一个元素，如果r元素出现的次数满足题目要求，则进一步判断该元素是否可以直接加入上次的序列，可以则更新l和len的长度，反之则说明中间某些元素不满足，更新序列 r为当前元素,len为1。每次遍历后都更新全局最优序列，如果l当前序列en比全局最优的更优才进行更新。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
#include <iostream>
#include <map>
using namespace std;

int main(){
    int t;
    cin>>t;
    while(t--){
        map<int,int> m;
        int n,k;
        cin>>n>>k;
        int big = 0;
        for(int i = 0;i<n;i++){
            int id;
            cin>>id;
            if(!m.count(id)){
                m.insert({id,1});
            }else{
                m[id] = m[id]+1;
            }
        }
        int len = -1;
        int ans_len = -1;
        int ans_l = -1;
        int l,r; 
        for(auto iter = m.begin();iter != m.end();iter++){
            r = iter->first;
            if(iter->second >= k){
                if(len == -1){
                    l = r;
                    len = 1;
                }else if(len-1+l == iter->first-1){
                    len++;
                }else{
                    l = r;
                    len = 1;
                }
                if(len>ans_len){
                    ans_len = len;
                    ans_l = l;
                }
            }
        }
        if(ans_len == -1) cout<<-1<<endl;
        else 
            cout<<ans_l<<" "<<ans_len-1+ans_l<<endl;
    }
    return 0;
}
 Comments
Comment plugin failed to load
Loading comment plugin
  1. 第一题
    1. 题意
    2. 思路
    3. 代码
  2. 第二题
    1. 题意
    2. 思路
    3. 代码
  3. 第三题
    1. 题意
    2. 思路
    3. 代码
  4. 第四题
    1. 题意
    2. 思路
    3. 代码
  5. 第五题
    1. 题意
    2. 思路
    3. 代码
  6. 第六题
    1. 题意
    2. 思路
    3. 代码
© 2020 - 2024    CYY
Powered by Hexo & Theme Keep
  1. 第一题
    1. 题意
    2. 思路
    3. 代码
  2. 第二题
    1. 题意
    2. 思路
    3. 代码
  3. 第三题
    1. 题意
    2. 思路
    3. 代码
  4. 第四题
    1. 题意
    2. 思路
    3. 代码
  5. 第五题
    1. 题意
    2. 思路
    3. 代码
  6. 第六题
    1. 题意
    2. 思路
    3. 代码