Codeforces Round #399 (Div. 1 + Div. 2, combined) 解题报告

A.Oath of the Night's Watch

简单的排序

 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 using namespace std;
11 typedef long long ll;
12 typedef unsigned long long ull;
13 const int MAX=1e5+5;
14 int a[MAX];
15 int main()
16 {
17     int n;
18     int l,r;
19     scanf("%d",&n);
20     for(int i=0;i<n;i++)
21     {
22         scanf("%d",&a[i]);
23     }
24     sort(a,a+n);
25     if(a[0]==a[n-1])
26         printf("0
");
27     else
28     {
29         l=0;r=n-1;
30         while(a[l+1]==a[l])
31             l++;
32         while(a[r-1]==a[r])
33             r--;
34         printf("%d
",max(0,r-l-1));
35     }
36 }

View Code

B.Code For 1

分析n的二进制各位是0还是1。用数组a记录，设a的下标到x。对于操作后的第i个数，设i的因数2的幂次最大为z，i的值等于a[x-z]

 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 using namespace std;
11 typedef long long ll;
12 typedef unsigned long long ull;
13 ll n;
14 ll l,r;
15 int a[100];
16 int main()
17 {
18     cin>>n>>l>>r;
19     ll i;
20     ll cnt,j,an=0,wei;
21     for(i=0;n;i++)
22     {
23         a[i]=n%2;
24         n/=2;
25     }
26     wei=i-1;
27 //    printf("wei=%lld
",wei);
28     for(i=l;i<=r;i++)
29     {
30         cnt=0;
31         j=i;
32         while(j%2==0)
33         {
34             cnt++;
35             j/=2;
36         }
37 //        printf("%d
",cnt);
38         if(a[wei-cnt])
39             an++;
40     }
41     cout<<an<<"
";
42 
43 }

View Code

C.Jon Snow and his Favourite Number

经历若干次这样的操作后就会稳定下来。只需要模拟整个过程，每次循环的末尾判断是否稳定下来即可。

 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 using namespace std;
11 typedef long long ll;
12 typedef unsigned long long ull;
13 const int MAX=1e5+5;
14 int n,k,x;
15 int a[MAX];
16 int xiao[MAX],da[MAX];
17 int main()
18 {
19     cin>>n>>k>>x;
20     for(int i=0;i<n;i++)
21         cin>>a[i];
22     sort(a,a+n);
23 //    if(k%2==1)
24     for(int j=0;j<k;j++)
25     {
26         for(int i=0;i<n;i++)
27         if(i%2==0)
28             a[i]=a[i]^x;
29 //    }
30     sort(a,a+n);
31     xiao[j]=a[0];da[j]=da[n-1];
32     if(j>=2&&xiao[j]==xiao[j-1]&xiao[j]==xiao[j-2]&&da[j]==da[j-1]&&da[j]==da[j-2])
33         break;
34     }
35     printf("%d %d
",a[n-1],a[0]);
36 
37 }

View Code

E.E.Game of Stones

第一次见到Nim游戏的博弈题目。状态数为 n(n+1)/2 <=x 的最大x，之后就进行异或和即可。

 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 using namespace std;
11 typedef long long ll;
12 typedef unsigned long long ull;
13 const int MAX=1e5+5;
14 int n;
15 int a[66];
16 int main()
17 {
18     int i,j,st=0,an=0;
19     a[0]=0;
20     for(i=1;i<=10;i++)
21     {
22         for(j=1;j<=i+1;j++)
23         {
24             a[++st]=i;
25         }
26     }
27     scanf("%d",&n);
28     while(n--)
29     {
30         scanf("%d",&st);
31         an^=a[st];
32     }
33     if(an==0)
34         printf("YES
");
35     else
36         printf("NO
");
37 }