当前位置：首页 > news >正文

Codeforces Round #215 (Div. 2) 解题报告

news 来源：原创 2024/5/21 0:58:36

昨天第一题竟然还错了。。。真是忧伤。现在改过来了

Problem A Sereja and Coat Rack

一共有n个房间第i个能赚ai的钱不够一个房间陪d钱，算最后的赚了多少。

贪心思想赚的少的先来。

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <string.h>
 4 #include <algorithm>
 5 #define INF 0x7fffffff
 6 
 7 using namespace std;
 8 bool cmp(int a, int b){return a>b;}
 9 int main()
10 {
11 //    freopen("in.txt", "r", stdin);
12 
13     int n, d, a[111], m;
14     while(scanf("%d%d", &n, &d)!=EOF){
15         for(int i=0; i<n; i++){
16             scanf("%d", &a[i]);
17         }
18         scanf("%d", &m);
19         int ans = 0;
20         sort(a, a+n);
21         for(int i=0; i<min(m,n); i++){
22             ans+=a[i];
23         }
24         ans-=d*(m>n?(m-n):0);
25         cout << ans << endl;
26     }
27     return 0;
28 }

View Code

Problem B Sereja and Suffixes
统计第i个后有多少个不同的数，开局初始化一下即可。然后每次查询。

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <string.h>
 4 #include <algorithm>
 5 #define INF 0x7fffffff
 6 
 7 using namespace std;
 8 int tag[100100], dp[100100], a[100100];
 9 
10 int main()
11 {
12 //    freopen("in.txt", "r", stdin);
13     int n, m;
14     while(scanf("%d%d", &n, &m)!=EOF){
15         memset(tag, 0, sizeof tag);
16         memset(dp, 0, sizeof dp);
17         for(int i=0; i<n; i++){
18             scanf("%d", &a[i]);
19         }
20         for(int i=n-1; i>=0; i--){
21             if(tag[a[i]]==0){
22                 tag[a[i]] = 1;
23                 dp[i] = dp[i+1]+1;
24             }else dp[i] = dp[i+1];
25         }
26         for(int i=0; i<m; i++){
27             int temp;
28             scanf("%d", &temp);
29             cout << dp[temp-1] << endl;
30         }
31     }
32     return 0;
33 }

View Code

Problem C Sereja and Algorithm

找规律题，想了半天。最终结论很简单只要满足abs(a-b)>=2 || abs(b-c)>=2 || abs(c-a)>=2返回YES否则。

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <string.h>
 4 #include <algorithm>
 5 #define INF 0x7fffffff
 6 
 7 using namespace std;
 8 
 9 int dp[100100][5];
10 char str[100100];
11 
12 bool Judge(int a, int b, int c){
13     if(a==0 || b==0 || c==0) return false;
14     if(abs(a-b)>=2 || abs(b-c)>=2 || abs(c-a)>=2)return false;
15     return true;
16 }
17 
18 int main()
19 {
20 //    freopen("in.txt", "r", stdin);
21     while(cin >> str+1)
22     {
23         int len = strlen(str+1);
24         for(int i=1; i<=len; i++){
25             dp[i][0] = dp[i-1][0];
26             dp[i][1] = dp[i-1][1];
27             dp[i][2] = dp[i-1][2];
28             dp[i][str[i]-'x'] ++;
29         }
30         int q, l, r;
31         scanf("%d", &q);
32         for(int i=0; i<q; i++){
33             scanf("%d%d", &l, &r);
34             int tx = dp[r][0]-dp[l-1][0], ty = dp[r][1]-dp[l-1][1], tz = dp[r][2]-dp[l-1][2];
35             if(r-l<2)printf("YES\n");
36             else if(Judge(tx,ty,tz))printf("YES\n");
37             else printf("NO\n");
38         }
39     }
40     return 0;
41 }