Manthan, Codefest 19 (open for everyone, rated, Div. 1 + Div. 2)

没打rating

f[0]=a, f[1]=b, f[n]=f[n-1]^f[n-2]，求f[n]

可以发现，3个一周期

也就是a, b, a^b, a^b^b=a, a^a^b=b, ...

 1 #include<iostream>
 2 #include<sstream>
 3 #include<fstream>
 4 #include<algorithm>
 5 #include<cstring>
 6 #include<iomanip>
 7 #include<cstdlib>
 8 #include<cctype>
 9 #include<vector>
10 #include<string>
11 #include<cmath>
12 #include<ctime>
13 #include<stack>
14 #include<queue>
15 #include<map>
16 #include<set>
17 #define mem(a,b) memset(a,b,sizeof(a))
18 #define random(a,b) (rand()%(b-a+1)+a)
19 #define ll long long
20 #define ull unsigned long long
21 #define e 2.71828182
22 #define Pi acos(-1.0)
23 #define ls(rt) (rt<<1)
24 #define rs(rt) (rt<<1|1)
25 #define lowbit(x) (x&(-x))
26 using namespace std;
27 int read()
28 {
29     int s=1,x=0;
30     char ch=getchar();
31     while(!isdigit(ch)) {if(ch=='-') s=-1;ch=getchar();}
32     while(isdigit(ch)) {x=10*x+ch-'0';ch=getchar();}
33     return x*s;
34 }
35 
36 int main()
37 {
38     int test=read(),c;
39     while(test--)
40     {
41         int a=read(),b=read(),n=read();
42         c=a^b;
43         if(n%3==0) printf("%d
",a);
44         else if(n%3==1) printf("%d
",b);
45         else printf("%d
",c);    
46     } 
47 }

View Code

B、Uniqueness

给定n个数，求最短区间[l,r]使得去掉[l,r]区间内的数使得剩下的数两两互不相同。

由于数据范围不大(n<=2000)，时间又给了两秒，自然想到暴力

  1 #include<iostream>
  2 #include<sstream>
  3 #include<fstream>
  4 #include<algorithm>
  5 #include<cstring>
  6 #include<iomanip>
  7 #include<cstdlib>
  8 #include<cctype>
  9 #include<vector>
 10 #include<string>
 11 #include<cmath>
 12 #include<ctime>
 13 #include<stack>
 14 #include<queue>
 15 #include<map>
 16 #include<set>
 17 #define mem(a,b) memset(a,b,sizeof(a))
 18 #define random(a,b) (rand()%(b-a+1)+a)
 19 #define ll long long
 20 #define ull unsigned long long
 21 #define e 2.71828182
 22 #define Pi acos(-1.0)
 23 #define ls(rt) (rt<<1)
 24 #define rs(rt) (rt<<1|1)
 25 #define lowbit(x) (x&(-x))
 26 using namespace std;
 27 const int MAXN=2e3+5;
 28 int n,a[MAXN];
 29 map<int,int> tmp,pool;
 30 int read()
 31 {
 32     int s=1,x=0;
 33     char ch=getchar();
 34     while(!isdigit(ch)) {if(ch=='-') s=-1;ch=getchar();}
 35     while(isdigit(ch)) {x=10*x+ch-'0';ch=getchar();}
 36     return x*s;
 37 }
 38 void showtmp()
 39 {
 40     cout<<"tmp:
";
 41     for(auto &it:tmp)
 42     cout<<it.first<<':'<<it.second<<endl;
 43 }
 44 void showpool()
 45 {
 46     cout<<"pool:
";
 47     for(auto &it:pool)
 48     cout<<it.first<<':'<<it.second<<endl;
 49 }
 50 int main()
 51 {
 52     int n=read();
 53     for(int i=1;i<=n;++i) 
 54     {
 55         a[i]=read();
 56         if(tmp.count(a[i])) tmp[a[i]]++;
 57         else tmp[a[i]]=1;
 58     }
 59     
 60     int uni=tmp.size();
 61     if(uni==n) return 0*printf("%d",0);
 62     bool flag=false;
 63     int ans=-1,lt,lp;
 64     for(int i=n-uni;!flag;++i)//r
 65     {
 66         tmp.clear(),pool.clear(),lp=n-i,lt=i;
 67         for(int j=1;j<=i;++j) 
 68         {
 69             if(tmp.count(a[j])) tmp[a[j]]++;
 70             else tmp[a[j]]=1;
 71         }
 72         for(int j=i+1;j<=n;++j) 
 73         {
 74             if(pool.count(a[j])) pool[a[j]]++;
 75             else pool[a[j]]=1;
 76         }
 77         if(pool.size()==lp) 
 78         {
 79             flag=true;
 80             ans=i;
 81         }
 82         for(int j=i+1;j<=n&&!flag;++j)
 83         {
 84             if(pool.count(a[j-lt])) pool[a[j-lt]]++;
 85             else pool[a[j-lt]]=1;
 86             if(tmp.count(a[j])) tmp[a[j]]++;
 87             else tmp[a[j]]=1;
 88             if(pool[a[j]]==1) pool.erase(a[j]);
 89             else pool[a[j]]--;
 90             if(tmp[a[j-lt]]==1) tmp.erase(a[j-lt]);
 91             else tmp[a[j-lt]]--;
 92             /*cout<<"i: "<<i<<" j: "<<j<<" lt: "<<lt<<endl;
 93         showtmp();showpool();*/
 94             if(pool.size()==lp) 
 95             {
 96                 flag=true;
 97                 ans=i;break;
 98             }
 99             
100         }
101         
102     }
103     cout<<ans<<endl;
104 }

View Code

 1 #include<iostream>
 2 #include<sstream>
 3 #include<fstream>
 4 #include<algorithm>
 5 #include<cstring>
 6 #include<iomanip>
 7 #include<cstdlib>
 8 #include<cctype>
 9 #include<vector>
10 #include<string>
11 #include<cmath>
12 #include<ctime>
13 #include<stack>
14 #include<queue>
15 #include<map>
16 #include<set>
17 #define mem(a,b) memset(a,b,sizeof(a))
18 #define random(a,b) (rand()%(b-a+1)+a)
19 #define ll long long
20 #define ull unsigned long long
21 #define e 2.71828182
22 #define Pi acos(-1.0)
23 #define ls(rt) (rt<<1)
24 #define rs(rt) (rt<<1|1)
25 #define lowbit(x) (x&(-x))
26 using namespace std;
27 const int MAXN=2e3+5;
28 int n,a[MAXN];
29 map<int,int> tmp,pool;
30 int read()
31 {
32     int s=1,x=0;
33     char ch=getchar();
34     while(!isdigit(ch)) {if(ch=='-') s=-1;ch=getchar();}
35     while(isdigit(ch)) {x=10*x+ch-'0';ch=getchar();}
36     return x*s;
37 }
38 /*void showtmp()
39 {
40     cout<<"tmp:
";
41     for(auto &it:tmp)
42     cout<<it.first<<':'<<it.second<<endl;
43 }
44 void showpool()
45 {
46     cout<<"pool:
";
47     for(auto &it:pool)
48     cout<<it.first<<':'<<it.second<<endl;
49 }*/
50 int main()
51 {
52     int n=read();
53     for(int i=1;i<=n;++i) 
54     a[i]=read(),tmp[a[i]]++;
55     
56     int uni=tmp.size();
57     if(uni==n) return 0*printf("%d",0);
58     bool flag=false;
59     int ans=-1,lt,lp;//lt保存枚举[l,r]区间的长度，lp是剩下的长度 
60     //tmp保存枚举的数及相应的个数，pool保存剩下的数及相应的个数 
61     for(int i=n-uni;!flag;++i)//r
62     {
63         tmp.clear(),pool.clear(),lp=n-i,lt=i;
64         for(int j=1;j<=i;++j) 
65         tmp[a[j]]++;
66  
67         for(int j=i+1;j<=n;++j) 
68         pool[a[j]]++;
69         
70         if(pool.size()==lp) 
71         {
72             flag=true;
73             ans=i;
74         }
75         for(int j=i+1;j<=n&&!flag;++j)
76         {
77             pool[a[j-lt]]++;
78             tmp[a[j]]++;
79             if(pool[a[j]]==1) pool.erase(a[j]);
80             else pool[a[j]]--;
81             if(tmp[a[j-lt]]==1) tmp.erase(a[j-lt]);
82             else tmp[a[j-lt]]--;
83             if(pool.size()==lp) 
84             {
85                 flag=true;
86                 ans=i;
87             }    
88         }
89         
90     }
91     cout<<ans<<endl;
92 }

View Code

我这个暴力是枚举每次删去的区间，区间长度从小到大枚举，只要有满足条件的就会是最小区间长度。

题解的暴力是，删去区间后每次剩下前缀和后缀，枚举前缀和后缀都两两不同时中间区间的长度，取最小值。

还是学习下高效一点的写法吧：看看榜一的代码

求最长的不含重复数字的前缀后缀

 1 #include <bits/stdc++.h>
 2  
 3 using namespace std;
 4  
 5 int main() {
 6   ios::sync_with_stdio(false);
 7   cin.tie(0);
 8   int n;
 9   cin >> n;
10   vector<int> a(n);
11   for (int i = 0; i < n; i++) {
12     cin >> a[i];
13   }
14   vector<int> b = a;
15   sort(b.begin(), b.end());
16   b.resize(unique(b.begin(), b.end()) - b.begin());
17   if ((int) b.size() == n) {
18     cout << 0 << '
';
19     return 0;
20   }
21   for (int i = 0; i < n; i++) {
22     a[i] = (int) (lower_bound(b.begin(), b.end(), a[i]) - b.begin());
23   }
24   int ans = 0;
25   vector<int> mark(n, 0);
26   for (int i = 0; i < n; i++) {
27     int take = 0;
28     for (int j = 0; j < n; j++) {
29       if (mark[a[n - 1 - j]] > 0) {
30         break;
31       }
32       mark[a[n - 1 - j]] = 1;
33       ++take;
34     }
35     ans = max(ans, i + take);
36     for (int j = 0; j < take; j++) {
37       mark[a[n - 1 - j]] = 0;
38     }
39     if (mark[a[i]]) {
40       break;
41     }
42     mark[a[i]] = 1;
43   }
44   cout << n - ans << '
';
45   return 0;
46 }

View Code

 1 #include<iostream>
 2 #include<sstream>
 3 #include<fstream>
 4 #include<algorithm>
 5 #include<cstring>
 6 #include<iomanip>
 7 #include<cstdlib>
 8 #include<cctype>
 9 #include<vector>
10 #include<string>
11 #include<cmath>
12 #include<ctime>
13 #include<stack>
14 #include<queue>
15 #include<map>
16 #include<set>
17 #define mem(a,b) memset(a,b,sizeof(a))
18 #define random(a,b) (rand()%(b-a+1)+a)
19 #define ll long long
20 #define ull unsigned long long
21 #define e 2.71828182
22 #define Pi acos(-1.0)
23 #define ls(rt) (rt<<1)
24 #define rs(rt) (rt<<1|1)
25 #define lowbit(x) (x&(-x))
26 using namespace std;
27 const int MAXN=2e3+5;
28 int mark[MAXN],a[MAXN],b[MAXN]; 
29 int n,uni,take;
30 int read()
31 {
32     int s=1,x=0;
33     char ch=getchar();
34     while(!isdigit(ch)) {if(ch=='-') s=-1;ch=getchar();}
35     while(isdigit(ch)) {x=10*x+ch-'0';ch=getchar();}
36     return x*s;
37 }
38 int main()
39 {
40     n=read();
41     for(int i=1;i<=n;++i) a[i]=read(),b[i]=a[i];
42     sort(b+1,b+n+1);
43     uni=unique(b+1,b+n+1)-b-1;//去掉重复元素后的个数 
44     for(int i=1;i<=n;++i)//离散化后a[i]最大也就2000，方便使用mark数组 
45     a[i]=lower_bound(b+1,b+uni+1,a[i])-b;
46     int ans=-1;//最长不含重复数字的前缀后缀长度之和 
47     for(int i=0;i<=n;++i)//枚举不含重复数字的前缀 
48     {
49         if(mark[a[i]]) break;
50         mark[a[i]]=1;
51         take=n-i;//不含重复数字的后缀 
52         for(int j=n;j>=i+1;--j)
53         {
54             if(mark[a[j]]) 
55             {
56                 take=n-j;
57                 break;//有重复数字了 
58             }
59             mark[a[j]]++;        
60         }
61         ans=max(ans,i+take);
62         for(int j=1;j<=take;++j) mark[a[n-j+1]]=0;
63     } 
64     cout<<n-ans<<endl;
65 }

View Code

C、Magic Grid

给定一个是4的倍数的n，构造一个n行n列的矩阵，使得每行每列的异或值相等。

出现异或，可以多从二进制方面考虑，，构造每行每列的异或值为0

 1 #include<iostream>
 2 #include<sstream>
 3 #include<fstream>
 4 #include<algorithm>
 5 #include<cstring>
 6 #include<iomanip>
 7 #include<cstdlib>
 8 #include<cctype>
 9 #include<vector>
10 #include<string>
11 #include<cmath>
12 #include<ctime>
13 #include<stack>
14 #include<queue>
15 #include<map>
16 #include<set>
17 #define mem(a,b) memset(a,b,sizeof(a))
18 #define random(a,b) (rand()%(b-a+1)+a)
19 #define ll long long
20 #define ull unsigned long long
21 #define e 2.71828182
22 #define Pi acos(-1.0)
23 #define ls(rt) (rt<<1)
24 #define rs(rt) (rt<<1|1)
25 #define lowbit(x) (x&(-x))
26 using namespace std;
27 const int MAXN=1005;
28 int a[MAXN][MAXN];
29 int read()
30 {
31     int s=1,x=0;
32     char ch=getchar();
33     while(!isdigit(ch)) {if(ch=='-') s=-1;ch=getchar();}
34     while(isdigit(ch)) {x=10*x+ch-'0';ch=getchar();}
35     return x*s;
36 }
37 
38 int main()
39 {
40     ios::sync_with_stdio(false);
41     cout.tie(0);
42     int n=read(),cnt=0;
43     for(int i=1;i<=n;i+=4)
44     for(int j=1;j<=n;j+=4)
45     for(int x=i;x<=i+3;++x)
46     for(int y=j;y<=j+3;++y)
47     a[x][y]=cnt++;
48     
49     for(int i=1;i<=n;++i)
50     {
51         for(int j=1;j<=n;++j)
52         cout<<a[i][j]<<' ';
53         cout<<endl;
54     }
55 }

View Code

也可以根据题目样例构造

 1 #include<iostream>
 2 #include<sstream>
 3 #include<fstream>
 4 #include<algorithm>
 5 #include<cstring>
 6 #include<iomanip>
 7 #include<cstdlib>
 8 #include<cctype>
 9 #include<vector>
10 #include<string>
11 #include<cmath>
12 #include<ctime>
13 #include<stack>
14 #include<queue>
15 #include<map>
16 #include<set>
17 #define mem(a,b) memset(a,b,sizeof(a))
18 #define random(a,b) (rand()%(b-a+1)+a)
19 #define ll long long
20 #define ull unsigned long long
21 #define e 2.71828182
22 #define Pi acos(-1.0)
23 #define ls(rt) (rt<<1)
24 #define rs(rt) (rt<<1|1)
25 #define lowbit(x) (x&(-x))
26 using namespace std;
27 const int MAXN=1e3+5;
28 int read()
29 {
30     int s=1,x=0;
31     char ch=getchar();
32     while(!isdigit(ch)) {if(ch=='-') s=-1;ch=getchar();}
33     while(isdigit(ch)) {x=10*x+ch-'0';ch=getchar();}
34     return x*s;
35 }
36 int ans[5][5]=
37 {{0,0,0,0,0},
38 {0,8,9,1,13},
39 {0,3,12,7,5},
40 {0,0,2,4,11},
41 {0,6,10,15,14}};
42 int a[MAXN][MAXN];
43 int main()
44 {
45     int n=read(),cnt=0;
46     for(int i=1;i<=n;i+=4)
47     for(int j=1;j<=n;j+=4)
48     {
49         for(int x=1;x<=4;++x)
50         for(int y=1;y<=4;++y)
51         a[i+x-1][j+y-1]=ans[x][y]+cnt*16;
52         cnt++;
53     }
54                 
55     for(int i=1;i<=n;++i)
56     {
57         for(int j=1;j<=n;++j)
58         cout<<a[i][j]<<' ';
59         cout<<endl;
60     }        
61     
62 }

View Code

D、Restore Permutation

 1 #include<iostream>
 2 #include<sstream>
 3 #include<fstream>
 4 #include<algorithm>
 5 #include<cstring>
 6 #include<iomanip>
 7 #include<cstdlib>
 8 #include<cctype>
 9 #include<vector>
10 #include<string>
11 #include<cmath>
12 #include<ctime>
13 #include<stack>
14 #include<queue>
15 #include<map>
16 #include<set>
17 #define mem(a,b) memset(a,b,sizeof(a))
18 #define random(a,b) (rand()%(b-a+1)+a)
19 #define ll long long
20 #define ull unsigned long long
21 #define e 2.71828182
22 #define Pi acos(-1.0)
23 #define ls(rt) (rt<<1)
24 #define rs(rt) (rt<<1|1)
25 #define lowbit(x) (x&(-x))
26 using namespace std;
27 const int MAXN=2e5+5;
28 ll T[MAXN],n,a[MAXN],p[MAXN];
29 void update(int x,int k)
30 {
31     for(int i=x;i<=n;i+=lowbit(i))
32     T[i]+=k;
33 }
34 ll getsum(int x)
35 {
36     ll res=0;
37     for(int i=x;i>0;i-=lowbit(i))
38     res+=T[i];
39     return res;
40 } 
41 ll read()
42 {
43     ll s=1,x=0;
44     char ch=getchar();
45     while(!isdigit(ch)) {if(ch=='-') s=-1;ch=getchar();}
46     while(isdigit(ch)) {x=10*x+ch-'0';ch=getchar();}
47     return x*s;
48 }
49 int main()
50 {
51     n=read();
52     for(int i=1;i<=n;++i)
53     a[i]=read(),update(i,i);
54     for(int i=n;i>=1;--i)
55     {
56         int l=-1,r=n+1;
57         while(l+1!=r)
58         {
59             int mid=(l+r)>>1;
60             if(getsum(mid)<=a[i]) l=mid;
61             else r=mid;
62         }
63         p[i]=l+1;
64         update(p[i],-p[i]);
65     }
66     for(int i=1;i<=n;++i)
67     cout<<p[i]<<' ';
68 }

View Code