您的位置: 首页  >  IT文章  >  Codeforces Round #402 (Div. 2)解题报告

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

分类: IT文章 • 2022-04-15 13:55:48

A.

 1 #include <iostream>
 2 #include<bits/stdc++.h>
 3 #include <stack>
 4 #include <queue>
 5 #include <map>
 6 #include <set>
 7 #include <cstdio>
 8 #include <cstring>
 9 #include <algorithm>
10 #include <math.h>
11 using namespace std;
12 typedef long long ll;
13 typedef unsigned long long ull;
14 int a[10],b[10],he[10];
15 int n;
16 int cnt;
17 int main()
18 {
19     scanf("%d",&n);
20     int i;
21     int tem;
22     for(i=1;i<=n;i++)
23     {
24         scanf("%d",&tem);
25         a[tem]++;
26         he[tem]++;
27     }
28     for(i=1;i<=n;i++)
29     {
30         scanf("%d",&tem);
31         b[tem]++;
32         he[tem]++;
33     }
34     for(i=1;i<=5;i++)
35     {
36         if(he[i]%2)
37         {
38             printf("-1
");return 0;
39         }
40         else
41         {
42             if(a[i]>he[i]/2)
43                 cnt+=a[i]-he[i]/2;
44         }
45 
46     }
47     printf("%d
",cnt);
48     return 0;
49 }
View Code

B.

 1 #include <iostream>
 2 #include<bits/stdc++.h>
 3 #include <stack>
 4 #include <queue>
 5 #include <map>
 6 #include <set>
 7 #include <cstdio>
 8 #include <cstring>
 9 #include <algorithm>
10 #include <math.h>
11 using namespace std;
12 typedef long long ll;
13 typedef unsigned long long ull;
14 char a[105];
15 int k;
16 int main()
17 {
18     scanf("%s %d",a,&k);
19     if(strlen(a)==1&&a[0]=='0')
20     {
21         printf("0
");
22         return 0;
23     }
24     else
25     {
26         int cnt=0;
27         int an=0;
28         int ge=0;
29         int j;
30         j=strlen(a)-1;
31         while(a[j]=='0')
32         {
33             cnt++;
34             j--;
35         }
36         if(cnt>=k)
37             printf("0
");
38         else
39         {
40             int i;
41             for(i=j;i>=0&&cnt<k;i--)
42             {
43                 if(a[i]=='0')
44                     cnt++;
45                 else
46                     ge++;
47             }
48             if(cnt==k)
49                 printf("%d
",ge);
50             else if(cnt>0)
51                 printf("%d
",strlen(a)-1);
52         }
53     }
54     return 0;
55 }
View Code

C.

 1 #include <iostream>
 2 #include<bits/stdc++.h>
 3 #include <stack>
 4 #include <queue>
 5 #include <map>
 6 #include <set>
 7 #include <cstdio>
 8 #include <cstring>
 9 #include <algorithm>
10 #include <math.h>
11 using namespace std;
12 typedef long long ll;
13 typedef unsigned long long ull;
14 const int MAX=2e5+5;
15 struct node
16 {
17     int sheng;
18     int id;
19 }a[MAX];
20 int x[MAX],y[MAX];
21 int n,k;
22 bool cmp(node p,node q)
23 {
24     if(p.sheng!=q.sheng)
25         return p.sheng>q.sheng;
26     else
27         return p.id<q.id;
28 }
29 int an;
30 int main()
31 {
32     scanf("%d %d",&n,&k);
33     int i;
34     for(i=0;i<n;i++)
35     {
36         scanf("%d",&x[i]);
37     }
38     for(i=0;i<n;i++)
39     {
40         scanf("%d",&y[i]);
41         a[i].sheng=y[i]-x[i];
42         a[i].id=i;
43     }
44     sort(a,a+n,cmp);
45     for(i=0;i<k||(a[i].sheng>=0&&i<n);i++)
46     {
47         an+=x[a[i].id];
48     }
49     for(int j=i;j<n;j++)
50     {
51         an+=y[a[j].id];
52     }
53     printf("%d
",an);
54     return 0;
55 }
View Code

D.

注意需要二分一下，不然会TLE

 1 #include <iostream>
 2 #include<bits/stdc++.h>
 3 #include <stack>
 4 #include <queue>
 5 #include <map>
 6 #include <set>
 7 #include <cstdio>
 8 #include <cstring>
 9 #include <algorithm>
10 #include <math.h>
11 using namespace std;
12 typedef long long ll;
13 typedef unsigned long long ull;
14 const int MAX=2e5+5;
15 char a[MAX],b[MAX];
16 bool val[MAX];
17 int num[MAX];
18 int len,le;//len是b长度，le是a长度
19 bool dfs(int x)//一直到编号x
20 {
21     for(int i=0;i<=le;i++)
22     {
23         val[i]=false;
24     }
25     for(int i=1;i<=x;i++)
26     {
27         val[num[i]-1]=true;
28     }
29     int lo=0;//匹配到了b的第lo个
30     for(int i=0;i<le&&lo<len;i++)
31     {
32         if(val[i])
33         {
34             if(a[i]==b[lo])
35                 lo++;
36         }
37     }
38     if(lo==len)
39         return true;
40     else return false;
41 }
42 int main()
43 {
44     scanf("%s %s",a,b);
45     len=strlen(b);
46     le=strlen(a);
47     int i;
48     for(i=le;i>0;i--)
49     {
50         scanf("%d",&num[i]);
51     }
52     int l=len,r=le,mid,an=-1;
53     while(l<=r)
54     {
55         mid=(l+r)/2;
56         if(dfs(mid))
57             {
58                 an=mid;
59                 r=mid-1;
60             }
61         else
62         {
63             l=mid+1;
64         }
65     }
66         if(an==-1)
67         printf("0
");
68         else
69             printf("%d
",le-an);
70     return 0;
71 }
View Code

相关推荐