Preface
2022的Last Round了，结果CD全卡住，反复横跳后最后才堪堪看出C的问题
D的话其实我刚开始是准备写并查集的，但后来nt了不知道为什么想到边双去了写Tarjan去了
唉只能说是实力不济了，不过索性没怎么掉分（-3pts不算掉）
A. Koxia and Whiteboards
SB题，按题意模拟即可
话说我家网真辣鸡，还不如学校的办电话卡送的宽带好用，开个题目都要1分多钟
#include<cstdio>
#include<queue>
#define RI register int
#define CI const int&
using namespace std;
int t,n,m,x; priority_queue < int,vector <int>,greater<int> > hp;
int main()
{
//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
for (scanf("%d",&t);t;--t)
{
RI i; for (scanf("%d%d",&n,&m),i=1;i<=n;++i) scanf("%d",&x),hp.push(x);
for (i=1;i<=m;++i) scanf("%d",&x),hp.pop(),hp.push(x);
long long ans=0; while (!hp.empty()) ans+=hp.top(),hp.pop();
printf("%lld\n",ans);
}
return 0;
}
B. Koxia and Permutation
瞎JB构造的构造题
不难发现答案的下界是\(n+1\)，考虑这样一种构造方案：
每次取出一段长度为\(k\)的段，第一段的两端分别放上\(n,1\)，第二段的两端分别放上\(n-1,2\)，依此类推
然后剩下的数随便填即可，手玩一下不难发现这样一定是正确的
#include<cstdio>
#define RI register int
#define CI const int&
using namespace std;
const int N=200005;
int t,n,k,a[N]; bool vis[N];
int main()
{
//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
for (scanf("%d",&t);t;--t)
{
RI i; for (scanf("%d%d",&n,&k),i=1;i<=n;++i) a[i]=vis[i]=0;
int tp=n; for (i=1;i+k-1<=n;i+=k) vis[a[i]=tp]=1,vis[a[i+k-1]=n+1-tp]=1,--tp;
for (tp=i=1;i<=n;++i) if (!a[i]) { while (vis[tp]) ++tp; vis[a[i]=tp]=1; }
for (i=1;i<=n;++i) printf("%d%c",a[i]," \n"[i==n]);
}
return 0;
}
C. Koxia and Number Theory
连续naive了好几次，我可以说是纯纯的大彩笔了
首先一个显然的结论，存在两个相同的数时一定时无解的
然后再多加思索，很容易想到当奇数和偶数都有两个及以上时一定不合法，因为此时不管\(x\)取什么值总有两个及以上的变化后的数是偶数
结果挂了之后一时想不出什么毛病，只好先去写D，结果一段时间后D也挂了看不出问题又滚回来写C
结果此时一眼看出来我们不仅要对\(2\)这个数进行验证，考虑对于某个质数\(p\)
我们考虑求出每个数对\(p\)取余的结果的个数，若余数为\(0,1,2,\cdots,p-1\)的个数都大于等于\(2\)，则这些数也是无解的
考虑抽屉原理，由于一共只有最多\(100\)个数，因此我们只要考虑小于\(50\)的所有质数即可
#include<cstdio>
#define RI register int
#define CI const int&
using namespace std;
const int N=105,prm[15]={2,3,5,7,11,13,17,19,23,29,31,37,41,43,47};
int t,n,c[50]; long long a[N];
int main()
{
//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
for (scanf("%d",&t);t;--t)
{
RI i,j; for (scanf("%d",&n),i=1;i<=n;++i) scanf("%lld",&a[i]);
bool flag=1; for (i=1;i<=n;++i) for (j=i+1;j<=n;++j)
if (a[i]==a[j]) flag=0; if (!flag) { puts("NO"); continue; }
for (i=0;i<15&&flag;++i)
{
int p=prm[i]; for (j=0;j<p;++j) c[j]=0;
for (j=1;j<=n;++j) ++c[a[j]%p];
bool sign=0; for (j=0;j<p&&!sign;++j) if (c[j]<2) sign=1;
if (!sign) flag=0;
}
puts(flag?"YES":"NO");
}
return 0;
}
D. Koxia and Game
我现在就好奇我当时为什么回去找桥，就是一个判环的并查集讨论问题的说
首先一个显然的结论，对于每一个\(i\)，我们必须使得在\(a_i,b_i,c_i\)中存在某个出现了两次及以上的数\(x\)，这样才能保证能在这一位上取到\(x\)
然后我们进行一些分析，假设我们已经确定一个位置\(i\)上的数取值为\(x\)了，那么其他所有的含有\(x\)这个数的位置的取值也确定了下来
因此我们可以把每对\(a_i\)和\(b_i\)进行连边，表示当其中一个确定时另一个就都确定了
然后考虑一些情况：
- 若\(a_i=b_i\)，显然\(c_i\)可以任意取值
- 若存在一个联通块构成一棵树，则无解（总会存在某对未确定的\(u,v\)在同个位置上）
- 若存在一个联通块，其中包括环（不含自环），则其对答案的贡献为\(\times2\)（很好理解，环上的点有两种选法，其它点会跟着这个环的选法确定）
- 若存在一个联通块，其中包括环，但这个环是自环，则其它部分的选法唯一，答案不变
- 若存在一个联通块中存在两个及以上的环，则无解
因此用并查集维护联通关系的同时在顺带维护下每个联通块的环的类型即可
#include<cstdio>
#include<iostream>
#define RI register int
#define CI const int&
using namespace std;
const int N=100005,mod=998244353;
int t,n,a[N],b[N],Fa[N],type[N]; bool sfcir[N];
//type=0 no circle; type=1 normal circle; type=2 self-loop with a link
inline int getfa(CI x)
{
return x!=Fa[x]?Fa[x]=getfa(Fa[x]):x;
}
int main()
{
//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
for (scanf("%d",&t);t;--t)
{
RI i; for (scanf("%d",&n),i=1;i<=n;++i) Fa[i]=i,type[i]=sfcir[i]=0;
for (i=1;i<=n;++i) scanf("%d",&a[i]); for (i=1;i<=n;++i) scanf("%d",&b[i]);
int ans=1; for (i=1;i<=n;++i) if (a[i]==b[i])
{
if (sfcir[a[i]]) ans=0; else sfcir[a[i]]=1,ans=1LL*ans*n%mod;
} else
{
int fa=getfa(a[i]),fb=getfa(b[i]);
if (fa!=fb)
{
if (type[fa]&&type[fb]) ans=0; else
{
if (!type[fa]) swap(fa,fb); Fa[fb]=fa;
}
} else
{
if (!type[fa]) type[fa]=1; else ans=0;
}
}
for (i=1;i<=n;++i) if (a[i]==b[i]) type[getfa(a[i])]=2;
for (i=1;i<=n;++i) if (!sfcir[i]&&getfa(i)==i)
{
if (!type[i]) ans=0; else if (type[i]==1) ans=2LL*ans%mod;
}
printf("%d\n",ans);
}
return 0;
}