AtCoder Beginner Contest 081

題目連結：https://abc081.contest.atcoder.jp/

總結：四道題較為簡單，比賽時切完三題rank41，然後D題讀錯題，一直挂機到結束，rank60，+200分。

A題：簽到題，直接讀入字元串判斷每個字元的1的個數輸出即可。

AC代碼：

1 #include<iostream>
 2 using namespace std;
 3 char s[4];
 4 int main()
 5 {
 6     cin>>s;
 7     int sum=0;
 8     for(int i=0;i<=2;i++)
 9     {
10         if(s[i]=='1')sum++;
11     }
12     cout<<sum<<endl;
13     return 0;
14 }      

B題：直接暴力即可，用另一個數組b[n]存每個數能/2的次數，排序輸出b[1]即可。

AC代碼：

1 #include<iostream>
 2 #include<algorithm>
 3 using namespace std;
 4 int n;
 5 const int maxn = 205;
 6 int a[maxn];
 7 int b[maxn];
 8 int main()
 9 {
10     cin>>n;
11     for(int i=1;i<=n;i++)
12     {
13         cin>>a[i];
14         if(a[i]&1)b[i]=0;
15         else
16         {
17             int k = 0;
18             while(a[i]%2==0)
19             {
20                 a[i]/=2;
21                 k++;
22             }
23             b[i]=k;
24         }
25     }
26     sort(b+1,b+1+n);
27     cout<<b[1]<<endl;
28     return 0;
29 }      

C題題意：給定一個數組a[n]和k，求最少删去多少個數使得數組a中隻有k個相同的數。

題解：因為a[i]<200000，是以記錄每個數出現的次數，統計一個有多少個不同的數出現。排序之後從出現的第一個數的次數加到第n-k個數出現的次數就是最少删去的數量。

AC代碼：

1 #include<iostream>
 2 #include<cstdio>
 3 #include<map>
 4 #include<algorithm>
 5 using namespace std;
 6 const int maxn = 200005;
 7 int a[maxn];
 8 int n,k,x;
 9 map<int,int> Q;
10 int main()
11 {
12     cin>>n>>k;
13     int now = 0;
14     for(int i=1;i<=n;i++)
15     {
16         a[i]=0;
17     }
18      for(int i=1;i<=n;i++)
19     {
20         cin>>x;
21         a[x]++;
22         if(!Q.count(x))
23         {
24             Q[x]=1;
25             now++;
26         }
27     }
28     sort(a+1,a+1+n);
29     int sum = 0;
30     for(int i=n-now+1;i<=n-k;i++)
31     {
32         sum+=a[i];
33     }
34     cout<<sum<<endl;
35 }      

D題題意：給定一組數，可以進行使ax=ax+ay的操作。求一個方法使得2N次操作内将數組變為不下降序列。（比賽時讀錯題，以為求最小操作次數。）

題解：如果都是正數，那麼每個數加前一個數必定符合要求，即a1,a1+a2,a2+a3,a3+a4...，負數同理，隻不過是反向加回來。如果有正負數，判斷一下最大數和最小數的絕對值誰大，給每個數加上絕對值最大的數即可轉換為符号相同的數組，求法同上。

AC代碼：

1 #include<iostream>
 2 #include<algorithm>
 3 #include<cstring>
 4 #include<cmath>
 5 #include<map>
 6 using namespace std;
 7 const int maxn = 55;
 8 int x[maxn];
 9 int n;
10 map<int,int> Q;
11 int main()
12 {
13     cin>>n;
14     int sum = 0;
15     int max1 = -1e6-5;
16     int min1 = 1e6+5;
17     int now = 0;
18     for(int i=1;i<=n;i++)
19     {
20         cin>>x[i];
21         Q[x[i]]=i;
22         max1 = max(max1,x[i]);
23         min1 = min(min1,x[i]);
24     }
25     if(abs(min1)>abs(max1))now = 1;
26     if(min1<=0&&max1>=0)
27     {
28         cout<<2*n-1<<endl;
29         for(int i=1;i<=n;i++)
30         {
31             if(now)cout<<Q[min1]<<" "<<i<<endl;
32             else cout<<Q[max1]<<" "<<i<<endl;
33         }
34     }
35     else cout<<n-1<<endl;
36     if(now)
37     {
38         for(int i=n;i>1;i--)
39         {
40             cout<<i<<" "<<i-1<<endl;
41         }
42     }
43     else
44     {
45         for(int i=2;i<=n;i++)
46         {
47             cout<<i-1<<" "<<i<<endl;
48         }
49     }
50     return 0;
51 }