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 }