A. Koxia and Whiteboards
注意每一步替换操作都是强制的，而不是可选的。所以就用一个multiset维护所有的数，每次选一个最小的替换掉即可。
时间复杂度\(O(nlogn)\)。
点击查看代码
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;++i)
#define repn(i,n) for(int i=1;i<=n;++i)
#define LL long long
#define pii pair <int,int>
#define fi first
#define se second
#define mpr make_pair
#define pb push_back
void fileio()
{
#ifdef LGS
freopen("in.txt","r",stdin);
freopen("out.txt","w",stdout);
#endif
}
void termin()
{
#ifdef LGS
std::cout<<"\n\nEXECUTION TERMINATED";
#endif
exit(0);
}
using namespace std;
LL t,n,m,a[110],b[110];
int main()
{
fileio();
cin>>t;
rep(tn,t)
{
scanf("%lld%lld",&n,&m);
multiset <LL> st;
rep(i,n) scanf("%lld",&a[i]),st.insert(a[i]);
rep(i,m)
{
scanf("%lld",&b[i]);
//if(*st.begin()<b[i])
{
st.erase(st.begin());
st.insert(b[i]);
}
}
LL ans=0;
for(auto it:st) ans+=it;
printf("%lld\n",ans);
}
termin();
}
B. Koxia and Permutation
k=1的情况，输出任意排列都可以。k>1时，发现一个包含数n的长度为k的字段的权值至少为n+1，盲猜存在一种排法使得最大权值就是n+1。其实下面的排法就满足要求：\(n,1,n-1,2,n-2,3\cdots\)。比如n=7时，排列就是\(7,1,6,2,5,3,4\)。在这种排法下，如果一个子段的最大值\(x>\frac n2\)，由于它右边的数是\(n+1-x\)，左边的数是\(n-x\)，所以子段的权值绝对不会超过\(n+1\)。子段的最大值\(\le \frac n2\)时权值不可能达到\(n+1\)。所以这种构造是正确的。
时间复杂度\(O(n)\)。
点击查看代码
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;++i)
#define repn(i,n) for(int i=1;i<=n;++i)
#define LL long long
#define pii pair <int,int>
#define fi first
#define se second
#define mpr make_pair
#define pb push_back
void fileio()
{
#ifdef LGS
freopen("in.txt","r",stdin);
freopen("out.txt","w",stdout);
#endif
}
void termin()
{
#ifdef LGS
std::cout<<"\n\nEXECUTION TERMINATED";
#endif
exit(0);
}
using namespace std;
int t,n,k;
int main()
{
fileio();
cin>>t;
rep(tn,t)
{
cin>>n>>k;
int lb=1,ub=n;
while(lb<ub) printf("%d %d ",ub--,lb++);
if(lb==ub) cout<<lb;
cout<<endl;
}
termin();
}
C. Koxia and Number Theory
我们先\(O(n^2)\)地枚举数组中的每对数(a,b)，看看如果要求\(gcd(a+x,b+x)=1\)的话x需要满足什么条件。如果a=b显然无解。否则令a,b中较小的为c，较大的为c+d。则我们要求\(gcd(c+x,d)=1\)，也就是对于d的每个质因数，c+x都不能是这个质因数的倍数，也就是对于任意\(e|d,e是质数\)，满足\(x \neq -c (mod \ e)\)。枚举了所有\(O(n^2)\)对数之后我们会得到若干个限制，如果存在某个质数p，我们要求\(x\ mod \ p\neq 0,x\ mod\ p\neq 1\cdots x\ mod\ p\neq p-1\)，也就是所有p个限制都占满了，那肯定无解；否则根据中国剩余定理一定有解。
但是在上面枚举的过程中，\(d\)的数据范围是1e18，没法分解质因数。注意到一共只会产生\(\frac{n(n-1)}2\)个限制，所以在\(p>\frac{n(n-1)}2\)的情况下是不可能占满p个限制导致无解的，故只需考虑这个范围内的质数。
时间复杂度没仔细算，反正肯定是能过的。
点击查看代码
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;++i)
#define repn(i,n) for(int i=1;i<=n;++i)
#define LL long long
#define pii pair <int,int>
#define fi first
#define se second
#define mpr make_pair
#define pb push_back
void fileio()
{
#ifdef LGS
freopen("in.txt","r",stdin);
freopen("out.txt","w",stdout);
#endif
}
void termin()
{
#ifdef LGS
std::cout<<"\n\nEXECUTION TERMINATED";
#endif
exit(0);
}
using namespace std;
LL t,n,a[110],cnt[800][6000],lim;
vector <LL> pri;
bool isp(LL x)
{
for(LL i=2;i*i<=x;++i) if(x%i==0) return false;
return true;
}
void precalc()
{
for(LL i=2;i<=6000;++i)
if(isp(i)) pri.pb(i);
}
int main()
{
fileio();
precalc();
cin>>t;
repn(tn,t)
{
cin>>n;
rep(i,n) cin>>a[i];
LL tot=(n+1)*n/2+10;
lim=0;
rep(i,pri.size()) if(pri[i]<=tot) ++lim;
bool bad=false;
rep(i,n)
{
for(int j=i+1;j<n;++j)
{
LL bas=min(a[i],a[j]),sub=llabs(a[i]-a[j]);
if(sub==0){bad=true;break;}
rep(k,lim) if(sub%pri[k]==0)
{
LL x=(pri[k]-bas%pri[k])%pri[k];
cnt[k][x]=tn;
}
}
if(bad) break;
}
if(!bad)
{
rep(i,lim)
{
bool good=false;
rep(j,pri[i]) if(cnt[i][j]!=tn){good=true;break;}
if(!good){bad=true;break;}
}
}
puts(bad ? "NO":"YES");
}
termin();
}
D. Koxia and Game
按照游戏的过程正着分析看不出什么，我们倒着看看。方便起见把删数的那个人称为K，选数的那个人称为M。考虑这三个序列的最后一个数组成的multiset\(\{a_n,b_n,c_n\}\)，如果K删掉了某个元素使得剩下的两个元素不相等，那K是不可能赢的，因为M总能找出一个元素使得最后形成的序列不是排列。所以\(a_n,b_n,c_n\)三个数不能全不同，至少得有两个相同的，且K一定是留下两个相同的数。倒数第二个位置同理，顺着推下去其实前面的每个位置都同理。
所以现在问题变成了这样：有两个数列a和b，对于每个i你可以在\(a_i,b_i\)中选恰好一个数，要求最后选出的序列是排列，求方案数。对于\(a_i=b_i\)的位置，会额外有\(n\)的方案数(因为原问题中\(c_i\)在这里可以乱选)。如果有解的话，最后把这个额外的方案数乘上就行了，下面的思考过程忽略这个额外的方案数。
转化成图论问题：把每个数看成一个点，对于每个i，在\(a_i,b_i\)之间连一条无向边。这个图中可能有自环和重边。建完图之后发现图是由一些连通块组成的。如果一个连通块内的点数和边数不相等，显然无解。否则这个连通块就是一个基环树，我们需要为每个点选一条相邻的边与其匹配，使得每条边恰好被匹配一次，并求出方案数。如果基环是一个自环，那显然只有1种方案。否则有两种方案，因为基环有两种匹配的方向。所以每个连通块的方案数都是1或2，全部乘起来就行了。
时间复杂度\(O(nlogn)\)，因为要使用并查集维护图(其实直接搜也可以O(n))。
点击查看代码
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;++i)
#define repn(i,n) for(int i=1;i<=n;++i)
#define LL long long
#define pii pair <int,int>
#define fi first
#define se second
#define mpr make_pair
#define pb push_back
void fileio()
{
#ifdef LGS
freopen("in.txt","r",stdin);
freopen("out.txt","w",stdout);
#endif
}
void termin()
{
#ifdef LGS
std::cout<<"\n\nEXECUTION TERMINATED";
#endif
exit(0);
}
using namespace std;
const LL MOD=998244353;
LL t,n,a[100010],b[100010],cnt[100010],fa[100010],sc[100010],sz[100010];
LL Find(LL x){return fa[x]==x ? x:fa[x]=Find(fa[x]);}
int main()
{
fileio();
cin>>t;
rep(tn,t)
{
cin>>n;
rep(i,n) scanf("%lld",&a[i]);
rep(i,n) scanf("%lld",&b[i]);
repn(i,n) cnt[i]=sc[i]=0,fa[i]=i,sz[i]=1;
LL mul=1;
rep(i,n)
{
if(a[i]==b[i]) ++sc[a[i]],++cnt[a[i]],(mul*=n)%=MOD;
else
{
++cnt[a[i]];
if(Find(a[i])!=Find(b[i])) fa[Find(a[i])]=Find(b[i]);
}
}
repn(i,n) if(Find(i)!=i) cnt[Find(i)]+=cnt[i],sc[Find(i)]+=sc[i],++sz[Find(i)];
bool bad=false;
repn(i,n) if(Find(i)==i)
{
if(cnt[i]!=sz[i]){bad=true;break;}
if(sc[i]==0) (mul*=2)%=MOD;
}
if(bad) puts("0");
else printf("%lld\n",mul);
}
termin();
}
E. Koxia and Tree
我一开始想的是：对每个点求出进行完所有操作后这个位置包含蝴蝶的概率，然后用这个概率加权求出两两之间的距离和。不幸的是这么做是错的，因为每个点包含蝴蝶的概率并不独立，它们之间是有关联的，比如k=1时答案应该是0，这个方法算出的答案就不是0。
换一种思路。先把1定为树的根。对于每个子树，我们想求出从它的根到其父亲的那条边，在画出蝴蝶两两之间路径时期望被走了多少次。把所有边的这个值加起来就得到了蝴蝶两两之间距离和的期望，除以蝴蝶对数就得到答案了。对于点i，令\(sz_i=\)初始状态下(没开始操作的时候)i的子树内的蝴蝶数量。发现所有操作做完后i子树内的蝴蝶数量只有三种可能：\(sz_i-1,sz_i,sz_i+1\)，因为每条边最多运送一只蝴蝶，也最多只有一只蝴蝶能被运进或运出子树。如果能分别求出这三种情况发生的概率，也就能求出最终答案了。比如子树内蝴蝶数量为\(sz_i\)的概率是p，则对蝴蝶两两之间距离和的期望的贡献是\(sz_i\cdot(n-sz_i)\cdot p\)。这里我们计算期望时只有一个变量，不存在什么独立性的问题，所以正确性是有的。
对于一个点i，假设从它连向父亲的边的编号为j。如果我们知道在进行了j-1次操作后点i有蝴蝶的概率(p)与点i的父亲有蝴蝶的概率(q)，那就能求出上面说的三个概率了。这里p和q是独立的、没有关联的，因为前j-1次操作都是在这条边两侧的两个连通块内进行的，互不影响。所以这么做是有正确性的。
从前到后依次进行操作，并同时维护每个点有蝴蝶的概率，这点也是很容易做到的。假设当前边连接(x,y)，则令\(p_x=p_y=np,其中np=\frac{p_x+p_y}2\)即可，按照题目定义推一推就能得到。
时间复杂度\(O(n)\)。
点击查看代码
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;++i)
#define repn(i,n) for(int i=1;i<=n;++i)
#define LL long long
#define pii pair <int,int>
#define fi first
#define se second
#define mpr make_pair
#define pb push_back
void fileio()
{
#ifdef LGS
freopen("in.txt","r",stdin);
freopen("out.txt","w",stdout);
#endif
}
void termin()
{
#ifdef LGS
std::cout<<"\n\nEXECUTION TERMINATED";
#endif
exit(0);
}
using namespace std;
const LL MOD=998244353;
LL qpow(LL x,LL a)
{
LL res=x,ret=1;
while(a>0)
{
if(a&1) (ret*=res)%=MOD;
a>>=1;
(res*=res)%=MOD;
}
return ret;
}
LL n,k,a[300010],inv2=qpow(2,MOD-2),ans=0,dep[300010],sz[300010];
vector <LL> g[300010];
vector <pii> e;
LL dfs(LL pos,LL par)
{
sz[pos]=a[pos];
rep(i,g[pos].size()) if(g[pos][i]!=par)
{
dep[g[pos][i]]=dep[pos]+1;
sz[pos]+=dfs(g[pos][i],pos);
}
return sz[pos];
}
int main()
{
fileio();
cin>>n>>k;
LL x;rep(i,k){scanf("%lld",&x);a[x]=1;}
LL y;
rep(i,n-1)
{
scanf("%lld%lld",&x,&y);
e.pb(mpr(x,y));
g[x].pb(y);g[y].pb(x);
}
dfs(1,0);
rep(i,n-1)
{
x=e[i].fi;y=e[i].se;
if(dep[x]>dep[y]) swap(x,y);//x上y下
LL pls=a[x]*(1LL-a[y]+MOD)%MOD*inv2%MOD,sub=a[y]*(1LL-a[x]+MOD)%MOD*inv2%MOD,mid=(1LL-pls-sub+MOD+MOD)%MOD;
(ans+=sz[y]*(k-sz[y])%MOD*mid)%=MOD;
(ans+=(sz[y]+1)*(k-sz[y]-1)%MOD*pls)%=MOD;
(ans+=(sz[y]-1)*(k-sz[y]+1)%MOD*sub)%=MOD;
LL sum=(a[x]+a[y])%MOD;
(sum*=inv2)%=MOD;
a[x]=a[y]=sum;
}
LL tot=(k-1)*k/2%MOD;
(ans*=qpow(tot,MOD-2))%=MOD;
cout<<ans<<endl;
termin();
}