好久没打过cf了，今天重温一下，可能手比较生了，打得状态不太好。实时录屏
A. The Third Three Number Problem
题目描述：
/1.png)
题目分析
题意比较简单，给定一个数，构造三个数使得 a^b+b^c+c^a==n。首先不难想到，奇数一定无法构造，因为奇数异或偶数结果一定为奇数，奇数与奇数以及偶数与偶数异或结果一定为偶数，则我们有以下结论：
- 若三个数中没有奇数，则相互异或和一定为偶数。
- 若三个数中只有一个奇数，则异或的结果会产生2个奇数，一个偶数，最终和仍为偶数。
- 若三个数中有两个奇数，则异或的结果产生2个奇数，一个偶数，最终和也为偶数。
- 若三个数全是奇数，则异或的结果产生全为偶数，最终结果也是偶数。
不难发现我们最终结果必是偶数。
那么如果不是偶数那么直接输出-1，若是则我们令其中两个数为1，那么最终结果就是 n=1^1+1^x+1^x=2*(1^x)。我们非常容易能解出 x 的值。
标程
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
| #include<bits/stdc++.h>
#define maxn 200005
using namespace std;
int a[maxn],b[maxn];
char s[maxn];
void solve(){
int n;
scanf("%d",&n);
if(n%2==0){
printf("1 1 %d\n",(n/2)^1);
}
else{
printf("-1\n");
}
}
int main(){
#ifndef ONLINE_JUDGE
freopen("1.in","r",stdin);
#endif
int t=1;
cin>>t;
while(t--)solve();
return 0;
}
|
B. Bit Flipping
题目描述：
/2.png)
题目分析
这个题目就是说，构造一个给定长度的矩阵，矩阵的每个格子值为0或者1，要求对于每一个格子，都有两个相邻的与之颜色不一样的格子，并且只能有两个。
大部分同学可能找规律，但是我后面想到了一个递推的方式，从小的矩阵扩展。因为已有的矩阵必然满足以上条件，因此如果对矩阵进行扩展，那么扩展的一列必须和被扩展的那一列值一模一样，由于宽高都为偶数，因此我们再次扩充的一列必须与被扩展列完全相反。如此一来达到了我们所构造的目标，我们最终构造的图形为
/3.png)
初始化之后，根据长宽输出就可以了。
标程
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
| #include<bits/stdc++.h>
#define maxn 52
using namespace std;
int a[maxn][maxn];
int dx[]={1,0,0,-1},dy[]={0,1,-1,0};
queue<pair<int,int>>q;
int n,m;
void print(int n,int m){
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
printf("%d ",a[i][j]);
}
putchar(10);
}
}
void solve(){
int n,m;
scanf("%d %d",&n,&m);
print(n,m);
}
void init(){
a[1][1]=1;
a[1][2]=0;
a[2][1]=0;
a[2][2]=1;
for(int i=3;i<=50;i+=2){
for(int j=1;j<=2;j+=2){
a[i][j]=a[i-1][j];
a[i][j+1]=a[i-1][j+1];
a[i+1][j]=!a[i-1][j];
a[i+1][j+1]=!a[i-1][j+1];
}
}
for(int i=1;i<=50;i+=2){
for(int j=3;j<=50;j+=2){
a[i][j]=a[i][j-1];
a[i+1][j]=a[i+1][j-1];
a[i][j+1]=!a[i][j-1];
a[i+1][j+1]=!a[i+1][j-1];
}
}
}
int main(){
#ifndef ONLINE_JUDGE
freopen("1.in","r",stdin);
#endif
init();
int t=1;
cin>>t;
while(t--)solve();
return 0;
}
|
C. Line Empire
题目描述
/4.png)
题目分析
这个题目的意思是，求符合条件的排列数量，要求任意子区间内，满足未出现过的最小值相同，求排列数。先考虑一个问题，首先0的位置一定要相等，因为没有包括0，那么结果一定为0，包括了0，结果一定不为0。那么再考虑1，若区间同时包括0和1，那么结果一定不为1，因此1的位置也必须相同。那么再考虑2，同样，区间需要包括0，1，2时，结果才不为2及以下的值，但是这个时候就有两种情况，2在0和1之间或者2不在0和1之间。若在，那么我们可以在0~1的位置内任意放置2，因为我们若想同时包括0和1，则必须包括2，那么这个时候，2就可以在区间内任意位置，对方案数做出贡献。如果不在，那么2同样也只能固定位置。以此类推，我们设置一个区间，若数在区间外，则扩展区间，若在区间内，则区间内剩余的位置都可以放置。
标程
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
| #include<bits/stdc++.h>
#define maxn 500002
using namespace std;
int a[maxn];
const int mod=1e9+7;
int dx[]={1,0,0,-1},dy[]={0,1,-1,0};
queue<pair<int,int>>q;
int n,m;
void solve(){
int n,m;
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%d",&m);
a[m]=i;
}
int l=a[0],r=a[0];
int range=0;
long long ans=1;
for(int i=1;i<n;i++){
bool flag=1;
if(a[i]>r){
r=a[i];
flag=0;
}
if(a[i]<l){
l=a[i];
flag=0;
}
range=r-l;
if(flag){
ans*=(range-i+1);
ans%=mod;
}
}
printf("%lld\n",ans);
}
int main(){
#ifndef ONLINE_JUDGE
freopen("1.in","r",stdin);
#endif
int t=1;
cin>>t;
while(t--)solve();
return 0;
}
|
小结
啥也不说了，猛练吧。
