A-D
A. Koxia and Whiteboards
题面
每次操作都把最小的换掉
AC代码： 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
using namespace std;
typedef long long ll;
priority_queue<int,vector<int>,greater<int>>q;
int main() {
ios::sync_with_stdio(false);cin.tie(nullptr);
int T;
cin>>T;
while(T--)
{
int n,m;
cin>>n>>m;
for(int i=1;i<=n;i++)
{
int x;
cin>>x;
q.push(x);
}
for(int i=1;i<=m;i++)
{
int x;
cin>>x;
q.pop();
q.push(x);
}
ll sum=0;
while(!q.empty())
{
sum+=q.top();
q.pop();
}
cout<<sum<<'\n';
}
return 0;
}
B. Koxia and Permutation
题面
考虑 n 这个数，如果 ci 从n这个数开始，那么最小是 n + 1
可以想到 n, 1, n − 1, 2, ... 这样下去是最小的， ci 始终不超过 n + 1
AC代码： 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
using namespace std;
typedef long long ll;
int main() {
ios::sync_with_stdio(false);cin.tie(nullptr);
int T;
cin>>T;
while(T--)
{
int n,k;
cin>>n>>k;
int x=1,j=0;
for(int i=1;i<=n;i++)
{
if(!x)
cout<<j<<' ';
else
cout<<n-++j+1<<' ';
x^=1;
}
cout<<'\n';
}
return 0;
}
C. Koxia and Number Theory
题面
首先是如果有两个相同的是不可能的，因为这两个相同的数比如 a = b , gcd(a+x,b+x) = a + x > 1
如果对于一个模数 m ，在模
m 的意义下 0, 1, ..., m − 1 中所有数都出现超过
1 次，那么加上的数 x 无论模 m 为几，都会有两个数同时被 m 整除。即若 ∀i ∈ [1,n], count[ai mod m] > = 2
，那么
同时模 m 下只需要计算模 m 的完全剩余系的出现次数，即只需计算 m 个数，所以当 m > n 时，就不需要考虑了，因为 n 个数必然填不满模 m 的完全剩余系
虽然这个条件的充分性还没有证明(不一定能找到对应的 x )，但是交了一发过了，那可以不用证了XD
(看了题解发现充分性是因为对所有的 m ，可以列出一个同余方程组，由中国剩余定理，解 x 一定存在)
所以只需要从 2 到 n 遍历 m ，检查是否会有模 m 下的完全剩余系内出现次数小于等于1的即可
AC代码： 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
using namespace std;
typedef long long ll;
const int N=105;
ll a[N];
int cnt[N];
int main() {
ios::sync_with_stdio(false);cin.tie(nullptr);
int T;
cin>>T;
while(T--)
{
int n;
cin>>n;
bool Flag=false;
for(int i=1;i<=n;i++)
{
cin>>a[i];
for(int j=1;j<i;j++)
{
if(a[i]==a[j])
{
Flag=true;
break;
}
}
}
if(Flag)
{
cout<<"NO"<<'\n';
continue;
}
for(int j=2;j<=n;j++)
{
memset(cnt,0,sizeof(cnt));
bool flag=false;
for(int i=1;i<=n;i++)
cnt[a[i]%j]++;
for(int i=0;i<j;i++)
{
if(cnt[i]<2)
{
flag=true;
break;
}
}
if(!flag)
{
Flag=true;
break;
}
}
if(Flag)
cout<<"NO"<<'\n';
else
cout<<"YES"<<'\n';
}
return 0;
}
D. Koxia and Game
题面
首先可以看出Mahiru不可能去选 ci ，因为 ci 是我们构造的，而我们构造的 ci 要让Koxia赢，而如果积极游戏的Mahiru选了我们给的 ci ，说明我们给的 ci 对Mahiru有帮助，所以我们肯定不能这么选 ci
所以Mahiru相当于只能从 ai, bi 中选一个
而构造合适的 ci 可以操纵Mahiru的选择，比如构造 ci = bi ，再拿走 ai ，那么相当于Mahiru只能选择 bi
现在只需要考虑所有的 ai, bi 能否构成一个排列，如果不能，那么无论怎么给 ci 都没用，如果有用，那么我们才能计数
这里尝试去写dfs，但是烂掉了，于是看了看题解..
发现题解的思路很巧妙
题解
AC代码： 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
using namespace std;
typedef long long ll;
const int N=1e5+5;
int a[N],b[N];
int fa[N];
int cnt_v[N],cnt_e[N],selfloop[N];
bool vis[N];
const int mod=998244353;
void init(int n)
{
for(int i=1;i<=n;i++)
fa[i]=i;
fill(cnt_v+1,cnt_v+1+n,1);
fill(cnt_e+1,cnt_e+1+n,0);
fill(selfloop+1,selfloop+1+n,0);
fill(vis+1,vis+1+n,false);
}
int find(int x)
{
return x==fa[x]?fa[x]:fa[x]=find(fa[x]);
}
void merge(int x,int y)
{
x=find(x);y=find(y);
if(x==y)
return;
cnt_v[y]+=cnt_v[x];
cnt_e[y]+=cnt_e[x];
selfloop[y]|=selfloop[x];
fa[x]=y;
}
int main() {
ios::sync_with_stdio(false);cin.tie(nullptr);
int T;
cin>>T;
while(T--)
{
int n;
cin>>n;
for(int i=1;i<=n;i++)
cin>>a[i];
for(int i=1;i<=n;i++)
cin>>b[i];
init(n);
for(int i=1;i<=n;i++)
{
merge(a[i],b[i]);
cnt_e[find(a[i])]++;
if(a[i]==b[i])
selfloop[find(a[i])]=1;
}
ll ans=1;
bool flag=false;
for(int i=1;i<=n;i++)
{
int x=find(i);
if(!vis[x])
{
vis[x]=true;
if(cnt_e[x]!=cnt_v[x])
{
flag=true;
break;
}
if(selfloop[x])
ans=(ans*n)%mod;
else
ans=(ans*2)%mod;
}
}
if(flag)
cout<<0<<'\n';
else
cout<<ans<<'\n';
}
return 0;
}