Codeforces Round #531 (Div. 3)

A：瞎猜。

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 int main(){
 4     ios::sync_with_stdio(false);
 5     int n;
 6     cin>>n;
 7     if(n%4==0||n%4==3){
 8         cout<<0<<endl;
 9     } else{
10         cout<<1<<endl;
11     }
12 }

View Code

B：随便搞

#include <bits/stdc++.h>
using namespace std;
int n,k;
int a[6666],ans[6666];
set<int>s[6666];
void cloro(int id,int clo){
    while (s[a[id]].count(clo)){
        clo++;
        if(clo==k+1){
            clo=1;
        }
    }
    ans[id]=clo;
    s[a[id]].insert(clo);
}
int main() {
    ios::sync_with_stdio(false);
    cin>>n>>k;
    for(int i=1;i<=n;i++)
        cin>>a[i];
    int now = 1;
    bool flag = false;
    for(int i=1;i<=n;i++){
        if(s[a[i]].size()==k){
            cout<<"NO"<<endl;
            exit(0);
        }
        cloro(i,now);
        now++;
        if(now==k+1) {
            now = 1;
            flag = true;
        }
    }
    if(!flag&&now<k){
        cout<<"NO"<<endl;
        exit(0);
    }
    cout<<"YES"<<endl;
    for(int i=1;i<=n;i++)
        cout<<ans[i]<<' ';
}

View Code

C：傻逼题

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 int n,x,y,a[105];
 4 int dp[100005];
 5 set<int> s;
 6 int main() {
 7     ios::sync_with_stdio(false);
 8     cin>>n>>x>>y;
 9     for(int i=1;i<=n;i++)
10         cin>>a[i];
11     if(x>y){
12         cout<<n<<endl;
13     } else if(x<=y){
14         int num = 0;
15         for(int i=1;i<=n;i++){
16             if(a[i]<=x){
17                 num++;
18             }
19         }
20         int ans = 0;
21         while (num>0){
22             ans++;
23             num-=2;
24         }
25         cout<<ans<<endl;
26     }
27 }

View Code

D：贪心的六种变换随便搞

我写的应该是有问题的，但是ppt了就不想改了，估计会掉。

upd 1/10 15:20 hhhh果然掉了但是是我自己傻屌写错了，思路没有问题。代码已更新

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 string s;int n;
 4 int a[3];
 5 void slove(int c01,int c02,int c10,int c12,int c20,int c21){
 6     for(int i=n-1;i>=0;i--){
 7         if(s[i]=='0'){
 8             if(c02) {
 9                 s[i] = '2';
10                 c02--;
11             }
12             else if(c01) {
13                 s[i] = '1';
14                 c01--;
15             }
16 
17         } else if(s[i]=='1'){
18             if(c12){
19                 c12--;
20                 s[i]='2';
21             }
22         }
23     }
24     for(int i=0;i<n;i++){
25         if(s[i]=='2'){
26             if(c20){
27                 c20--;
28                 s[i]='0';
29             } else if(c21){
30                 c21--;
31                 s[i]='1';
32             }
33         } else if(s[i]=='1'){
34             if(c10){
35                 s[i]='0';
36                 c10--;
37             }
38         }
39     }
40 }
41 int main() {
42     ios::sync_with_stdio(false);
43     cin>>n>>s;
44     for(int i=0;i<n;i++){
45         a[s[i]-'0']++;
46     }
47     int c01=0,c02=0,c10=0,c12=0,c20=0,c21=0;
48     if(a[0]>n/3){
49         if(a[1]>n/3){
50             c02=a[0]-n/3;
51             c12=a[1]-n/3;
52         } else{
53             if(a[2]>n/3) {
54                 c21 = a[2] - n / 3;
55                 c01 = a[0]-n/3;
56             }
57             else {
58                 c02 = n / 3 - a[2];
59                 c01=n/3-a[1];
60             }
61         }
62     } else if(a[1]>n/3){
63         if(a[2]>n/3){
64             c10=a[1]-n/3;
65             c20=a[2]-n/3;
66         } else{
67             c10=n/3-a[0];
68             c12=n/3-a[2];
69         }
70     } else if(a[2]>n/3){
71         c20=n/3-a[0];
72         c21=n/3-a[1];
73     }
74     slove(c01,c02,c10,c12,c20,c21);
75     cout<<s<<endl;
76 }

View Code

E：每个数都可以确定一个区间，然后我们求不确定的区间的长度，答案就是 1<<(len-1)

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 typedef long long ll;
 4 const ll mod = 998244353;
 5 int n;int a[200005];
 6 ll qpow(ll a,ll x){
 7     ll res = 1;
 8     while (x){
 9         if(x&1)
10             res=(res*a)%mod;
11         a=(a*a)%mod;
12         x/=2;
13     }
14     return res;
15 }
16 map<int,int> m;
17 vector<int> v [200005];
18 int pre[200005];
19 int main() {
20     ios::sync_with_stdio(false);
21     cin>>n;
22     int id = 1;
23     for(int i=1;i<=n;i++) {
24         cin >> a[i];
25         if(m.count(a[i])){
26             v[m[a[i]]].push_back(i);
27         } else{
28             m[a[i]]=id;
29             v[id].push_back(i);
30             id++;
31         }
32     }
33     for(int i=1;i<id;i++){
34         pre[v[i][0]]++;
35         pre[v[i][v[i].size()-1]]--;
36     }
37     ll cnt = 0;
38     for(int i=1;i<=n;i++){
39         pre[i]+=pre[i-1];
40         if(pre[i]==0)
41             cnt++;
42     }
43     cout<<qpow(2,cnt-1)<<endl;
44 }

View Code

F:状压dp。数据范围很明显了。。先预处理出来任意两行相邻的时候对答案的贡献，以及任意两行做头尾(就是第一行和最后一行)的贡献，然后dp，dp的时候枚举第一行是啥。

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 int a[18][10005],n,m;
 4 int b[18][18],c[17][18],ans;
 5 int f[1<<16][16];
 6 int slove(int id){
 7     for(int i=0;i<(1<<n);i++)
 8         for(int j=0;j<n;j++)
 9             f[i][j]=0;
10     f[1<<id][id]=1e9;
11     for(int i=0;i<(1<<n);i++){
12         for(int j=0;j<n;j++){
13             if(i&(1<<j)){
14                 for(int k=0;k<n;k++){
15                     if(i&(1<<k))continue;
16                     f[i|(1<<k)][k]=max(f[i|(1<<k)][k],min(f[i][j],b[j][k]));
17                 }
18             }
19         }
20     }
21     int ans = 0;
22     for(int i=0;i<n;i++){
23         if(i==id)continue;
24         ans = max(ans,min(c[id][i],f[(1<<n)-1][i]));
25     }
26     return ans;
27 }
28 int main() {
29     ios::sync_with_stdio(false);
30     cin>>n>>m;
31     for(int i=0;i<n;i++){
32         for(int j=0;j<m;j++){
33             cin>>a[i][j];
34         }
35     }
36     if(n==1){
37         int ans = 1e9;
38         for(int i=0;i<m-1;i++)
39             ans = min(ans,abs(a[0][i]-a[0][i+1]));
40         cout<<ans<<endl;
41         return 0;
42     }
43     //预处理第i行与第j行相邻
44     for(int i=0;i<n;i++){
45         for(int j=0;j<n;j++){
46             b[i][j]=1e9;
47             for(int k=0;k<m;k++){
48                 b[i][j]=min(b[i][j],abs(a[i][k]-a[j][k]));
49             }
50         }
51     }
52     //i是第一行，j是最后一行
53     for(int i=0;i<n;i++){
54         for(int j=0;j<n;j++){
55             if(i==j) continue;
56             c[i][j]=1e9;
57             for(int k=0;k<m-1;k++)
58                 c[i][j]=min(c[i][j],abs(a[i][k+1]-a[j][k]));
59         }
60     }
61     int ans = 0;
62     for(int i=0;i<n;i++){
63         ans = max(ans,slove(i));
64     }
65     cout<<ans<<endl;
66 }

View Code