Codeforces Good Bye 2020 A-D

A - Bovine Dilemma

解題思路：以為題上說了是一個三角形，并且有一個確定的點（0,1），所以這里只需要找兩個點便能構成一個三角形，而這兩個點都在x軸上，所以可以知道（0，1）到x軸為高，x軸上兩點只差為底，所以，我們只需要知道底有多少個不同的值即可，

把每個點和之前的點做差，用一個標記陣列b[x]查詢差值x是否出現過（沒出現過為0），如沒有出現過，b[x]++；反之，sum++，

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 int main()
 4 {
 5     int t,n,a[100],b[100],sum,x;
 6     scanf("%d",&t);
 7     while(t--)
 8     {
 9         memset(b,0,sizeof(b));
10         sum=0;
11         scanf("%d",&n);
12         for(int d=1;d<=n;d++)
13         {
14             scanf("%d",&a[d]);
15             for(int i=1;i<d;i++)
16             {
17                 x=a[d]-a[i];
18                 if(x<0)
19                     x=0-x;
20                 if(x!=0&&b[x]==0)
21                     sum++;
22                 b[x]++;
23             }
24         }
25         printf("%d\n",sum);
26     }
27     return 0;
28 }

B - Last minute enhancements

解題思路：本題就是找有多少個不同的數，且給的資料是遞增的，所以只要對輸入的數字x，查詢x是否出現過（在標記陣列b[ ]中），如果沒出現過（即b[x]=0），說明x是一個新數，sum++，在把x標記起來，b[x]++；如果出現過，就查詢x+1是否出現過，如果沒出現過，說明x+1是一個新數，sum++,在把x+1標記起來，b[x+1]++，

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 int b[200005];
 4 int main()
 5 {
 6     int t,n,x,sum;
 7     scanf("%d",&t);
 8     while(t--)
 9     {
10         memset(b,0,sizeof(b));
11         sum=0;
12         scanf("%d",&n);
13         for(int d=1;d<=n;d++)
14         {
15             scanf("%d",&x);
16             if(b[x]==0)
17             {
18                 b[x]++;
19                 sum++;
20             }
21             else
22             {
23                 b[x+1]++;
24                 if(b[x+1]==1)
25                     sum++;
26             }
27         }
28         printf("%d\n",sum);
29     }
30     return 0;
31 }

C - Canine poetry

解題思路：本題很簡單，只需要對每個字符查詢它是否與它前面的那個字符或者它前面的前面的那個字符相同即可，相同就把這個字符改為出字母外的任意一個字符即可，把每次相同加起來就是答案，

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 char a[100005];
 4 int main()
 5 {
 6     int n,sum;
 7     scanf("%d",&n);
 8     while(n--)
 9     {
10         sum=0;
11         scanf("%s",a);
12         for(int d=1;a[d]!='\0';d++)
13         {
14             if(a[d]==a[d-1])
15             {
16                 a[d]='!';
17                 sum++;
18             }
19             else if(a[d]==a[d-2]&&d>1)
20             {
21                 a[d]='!';
22                 sum++;
23             }
24         }
25         printf("%d\n",sum);
26     }
27     return 0;
28 }

D - 13th Labour of Heracles

解題思路：沒改變一條路徑，就會使一個端點多加一次（這個端點不能是為節點，即除這次的另一個端點外沒有其他節點與之連接），所以只需要把每次建立路徑的端點拿去查詢（b[x]是否大于0），如沒出現過（=0）就不管它；如出現過（>0）就把它保存起來（c[z]=a[x]，z++），在把c陣列按從大到小排序（題上要求了的），輸出n個數的和sum，在輸出每加一個c[d]后的sum，

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 int a[100005],b[100005],c[100005];
 4 long long sum;
 5 bool cmp(int x,int y)
 6 {
 7     return x>y;
 8 }
 9 int main()
10 {
11     int t,n,x,y,z;
12     scanf("%d",&t);
13     while(t--)
14     {
15         memset(b,0,sizeof(b));
16         memset(c,0,sizeof(c));
17         sum=0;
18         z=1;
19         scanf("%d",&n);
20         for(int d=1;d<=n;d++)
21         {
22             scanf("%d",&a[d]);
23             sum+=a[d];
24         }
25         for(int d=1;d<n;d++)
26         {
27             scanf("%d%d",&x,&y);
28             b[x]++;
29             b[y]++;
30             if(b[x]>1)
31             {
32                 c[z]=a[x];
33                 z++;
34             }
35             if(b[y]>1)
36             {
37                 c[z]=a[y];
38                 z++;
39             }
40         }
41         sort(c+1,c+z,cmp);
42         z--;
43         printf("%lld ",sum);
44         for(int d=1;d<=z;d++)
45         {
46             sum+=c[d];
47             printf("%lld ",sum);
48         }
49         printf("\n");
50     }
51     return 0;
52 }

標籤：C++

上一篇：求大神幫我的作業題，謝謝了

下一篇：7種排序演算法的C++實作以及比較