最近CF超级慢，不知道怎么解决。
本场$unrated$了，于是C题放飞自我xjb写。
A. Specific Tastes of Andre
如果一个序列的和能够被它的长度整除，我们称这个序列是不错的。如果一个序列的所有的非空子序列都是不错的，我们就称这个序列是完美的。现在有 t组询问，每组询问给定一个整数 n，请构造出一个由不小于100的正整数组成的长度为 n 的完美的序列。
思路
很明显输出n个1即为合法解
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
|
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int>pii;
#define ff first
#define ss second
#define debug(x) std:: cerr << #x << " = " << x << std::endl;
const int maxn=2e5+10,inf=0x3f3f3f3f,mod=1000000007;
signed main(signed argc, char const *argv[])
{
std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
int t,n;
cin>>t;
while(t--)
{
cin>>n;
for(int i=1;i<=n;i++)
cout<<1<<' ';
cout<<endl;
}
return 0;
}
|
B. Valerii Against Everyone
给定$t$组询问，每组询问给定一个数组$b$，然后构造出一个数组$a$，其中 $\forall i\in[1,n],a_i=2^{b_i}$，试求出能否找出四个数 $l_1,r_1,l_2,r_2$，满足：
- $1\leqslant l_1\leqslant r_1 <l_2\leqslant r_2\leqslant n$。
- $\sum\limits_{i=l_1}^{r_1}a_i=\sum\limits_{i=l_2}^{r_2}a_i$
思路
因为$l$可以和$r$相等，所以可以看是否存在相同的两个数。
代码
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
|
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int>pii;
#define ff first
#define ss second
#define debug(x) std:: cerr << #x << " = " << x << std::endl;
const int maxn=2e5+10,inf=0x3f3f3f3f,mod=1000000007;
ll a[maxn],b[maxn];
signed main(signed argc, char const *argv[])
{
std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
int t,n;
cin>>t;
while(t--)
{
cin>>n;
bool ok=0;
map<ll,bool>mp;
for(int i=1;i<=n;i++)
{
cin>>a[i];
if(mp[a[i]])
ok=1;
mp[a[i]]=1;
}
cout<<(ok?"YES":"NO")<<endl;
}
return 0;
}
|
C. Engineer Artem
给出一个$n\times m$的矩阵 a（$1\le n,m\le 100$），其中 $1\le a_{i,j}\le 10^9$。
定义一个矩阵是合法的当且仅当没有任何两个相邻的元素是相等的（上下左右为相邻）。
你可以将矩阵中若干个元素加一，使其合法，输出最终矩阵。
形式化地，对于每个 $(i,j)$，$b_{i,j}=a_{i,j}$或者 $b_{i,j}=a_{i,j}+1$，输出合法的$b$矩阵。
思路
方法1
奇偶交错构造黑白棋盘。
方法2
转化为2-SAT问题。
本题用到了异或逻辑与蕴含逻辑。
代码
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
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
|
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int>pii;
#define ff first
#define ss second
#define debug(x) std:: cerr << #x << " = " << x << std::endl;
const int maxn=20005,inf=0x3f3f3f3f,mod=1000000007;
int n,m,a[105][105],nx[]={0,1,0,-1},ny[]={1,0,-1,0};
int tim=0,Index=0,cnt=0;
int stk[maxn],dfn[maxn],low[maxn],belong[maxn];
int val[maxn],rec[maxn];
bool vis[maxn];
vector<int> G[maxn];
void tarjan(int x)
{
dfn[x]=low[x]=++tim;
stk[++Index]=x;
vis[x]=1;
for(int &v:G[x])
{
if(!dfn[v])
{
tarjan(v);
low[x]=min(low[x],low[v]);
}
else if(vis[v])
low[x]=min(low[x],dfn[v]);
}
if(low[x]==dfn[x])
{
cnt++;
do{
belong[stk[Index]]=cnt;
rec[cnt]+=val[stk[Index]];
vis[stk[Index]]=0;
Index--;
}while(stk[Index+1]!=x);
}
}
inline int id(int x,int y)
{
return (x-1)*m+y;
}
void ins(int i,int j,int x,int y)
{
int u=id(i,j),v=id(x,y);
if(a[i][j]==a[x][y])
{
G[n*m+u].push_back(v);
G[v].push_back(n*m+u);
G[n*m+v].push_back(u);
G[u].push_back(n*m+v);
}
else if(a[i][j]==a[x][y]+1)
{
G[u].push_back(v);
G[n*m+v].push_back(n*m+u);
}
else if(a[i][j]+1==a[x][y])
{
G[v].push_back(u);
G[n*m+u].push_back(n*m+v);
}
}
signed main(signed argc, char const *argv[])
{
std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
int t;
cin>>t;
while(t--)
{
tim=Index=cnt=0;
memset(dfn,0,sizeof(dfn));
cin>>n>>m;
for(int i=1;i<=2*n*m;i++)
G[i].clear();
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
{
cin>>a[i][j];
}
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
{
if(j<m)
ins(i,j,i,j+1);
if(i<n)
ins(i,j,i+1,j);
}
for(int i=1;i<=2*n*m;i++)
if(!dfn[i])
tarjan(i);
bool ok=1;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
int x=id(i,j);
if(belong[x]==belong[x+n*m])
ok=0;
else if(dfn[x]>dfn[x+n*m])
a[i][j]++;
}
}
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
cout<<a[i][j]<<(j==m?'\n':' ');
}
return 0;
}
|
D. Powerful Ksenia
给 $n$ 个正整数 $a_i$,$1 \le a_i\le10^9$.
每次操作是选三个不同的下标 $i,j,k$ ，让 $a_i,a_j,a_k$ 都变成 $a_i \oplus a_j\oplus a_k$ 也就是这三个数的异或和.
让你判断是否能在 $n$ 次操作内，使这 $n$ 个正整数的值变成相同的.
若能，第一行输出YES，第二行输出$m$表示操作数两，接下来$m$行每行三个整数，描述一次操作。
若不能，输出NO.
思路
两个相同的数异或等于0，一个数与0异或等于这个数。
于是n为奇数时可以从下标为$1,3,5,\dots,n-2$开始每三个数为一组进行异或，最后再让$a_n$与前面构造出来的相同的两个数组成一组进行异或。
n为偶数时，因为要求所有数都相同，所以整体异或和等于0。而所给操作并不会改变异或结果，所以检查一下整体异或和是否为0，若不为0，则无解。
否则可以对前$n-1$项进行如同奇数情况的操作，使得前$n-1$项相同，此时第$n$项必然也与前$n-1$项相同。
代码
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
|
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int>pii;
int a[maxn];
signed main(signed argc, char const *argv[])
{
std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
int n;
cin>>n;
for(int i=1;i<=n;i++)
cin>>a[i];
if(n&1)
{
cout<<"YES"<<endl;
cout<<n-1<<endl;
for(int i=1;i+2<=n;i+=2)
cout<<i<<' '<<i+1<<' '<<i+2<<endl;
for(int i=1;i+2<=n;i+=2)
cout<<n<<' '<<i<<' '<<i+1<<endl;
}
else{
int sum=0;
for(int i=1;i<=n;i++)
sum^=a[i];
if(sum)
cout<<"NO"<<endl;
else{
cout<<"YES"<<endl;
cout<<n-2<<endl;
for(int i=1;i+2<=n-1;i+=2)
cout<<i<<' '<<i+1<<' '<<i+2<<endl;
for(int i=1;i+2<=n-1;i+=2)
cout<<n-1<<' '<<i<<' '<<i+1<<endl;
}
}
return 0;
}
|