Preface
猜结论场，很久没打比赛了然后赛前和ztc吹牛说每次隔一段时间来打CF就会有强运加持
结果好家伙BCE全部秒出结论（而且我比赛时都证不来），而且写的A~E都是一发入魂
凭借这次的莫名超神发挥终于冲上purple了的说，可喜可贺
A. Exponential Equation
签到题
首先瞄一眼样例，一眼猜测奇数必然无解
证明的话显然，若\(x,y\)都是奇数，则\(x^y\cdot y\)和\(y^x\cdot x\)都是奇数，加起来就是偶数
若\(x,y\)中有一个为偶数，则\(x^y\cdot y\)和\(y^x\cdot x\)都是偶数，加起来还是偶数
因此奇数必然无解，否则偶数的情况我们令\(x=\frac{n}{2},y=1\)显然满足题意
#include<cstdio>
#define RI register int
#define CI const int&
using namespace std;
int t,n;
int main()
{
//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
for (scanf("%d",&t);t;--t)
{
if (scanf("%d",&n),n&1) { puts("-1"); continue; }
printf("%d 1\n",n/2,1);
}
return 0;
}
B. Number Factorization
猜结论题
首先观察下和式的性质，不难发现如果质因子\(a_i\)的次数是\(p_i\)，那么将其拆分成\(p_i\)个相同的因子答案不变
因此我们不妨假定答案构成时所有的\(p_i\)均为\(1\)，然后我稍微手玩了一下感觉把所有的不同的因子乘在一起就是最优的
仔细想一下其实就是基本不等式的推广，计算答案的话我们倒着从最大的因子算起即可
#include<cstdio>
#include<queue>
#define RI register int
#define CI const int&
using namespace std;
struct element
{
int val,num;
friend inline bool operator < (const element& A,const element& B)
{
return A.val>B.val;
}
}; int t,n,mul,cur; priority_queue <element> hp; long long ans;
int main()
{
//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
for (scanf("%d",&t);t;--t)
{
RI i; for (scanf("%d",&n),mul=1,ans=0,i=2;i*i<=n;++i)
if (n%i==0)
{
int ct=0; while (n%i==0) n/=i,++ct;
mul*=i; hp.push((element){ct,i});
}
if (n!=1) hp.push((element){1,n}),mul*=n; cur=0;
while (!hp.empty())
{
int ct=hp.top().val,tp=hp.top().num; hp.pop();
ct-=cur; ans+=1LL*mul*ct; mul/=tp; cur+=ct;
}
printf("%lld\n",ans);
}
return 0;
}
C. Remove the Bracket
猜结论题
昨天比赛的时候卡了会心态有点小崩没想太清楚，今天写博客的时候想了下还是挺好证明的
首先单独考虑拆分某个数\(a_i\)时的策略，由于那个\((x_i-s)(y_i-s)\ge 0\)的限制，我们有：
- 若\(a_i\le s\)，则\(x_i,y_i\in[0,a_i]\)
- 若\(a_i>s\)，令\(L=\min(s,a_i-s),R=\max(s,a_i-s)\)，则\(x_i,y_i\in[L,R]\)
如果我们单独考虑对\(a_i\)的分解时，我们把其他的无关项都看作常量，那么它对答案的影响只有\(y_{i-1}x_i+y_ix_{i+1}\)这一项
我们把\(y_i=a_i-x_i\)代入发现\(y_{i-1}x_i+(a_i-x_i)x_{i+1}\)就是个关于\(x_i\)的一次函数，那么它的最小值一定在值域的端点处取得
因此每个数的分解方法其实已经确定了，现在要考虑的就是一个顺序的问题
不难发现由于贡献的产生只和上一个数的取法有关，因此可以直接DP，设\(f_{i,0/1}\)表示第\(i\)个数的两种排列顺序时前面的最大贡献，转移的时候讨论下取法即可
#include<cstdio>
#include<iostream>
#define RI register int
#define CI const int&
using namespace std;
const int N=200005;
int t,n,s,a[N],c[N][2]; long long f[N][2];
int main()
{
//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
for (scanf("%d",&t);t;--t)
{
RI i,p,q; for (scanf("%d%d",&n,&s),i=1;i<=n;++i)
{
scanf("%d",&a[i]); f[i][0]=f[i][1]=1e18;
if (a[i]<=s) c[i][0]=0,c[i][1]=a[i]; else c[i][0]=s,c[i][1]=a[i]-s;
}
for (f[1][0]=f[1][1]=0,c[1][0]=c[1][1]=a[1],c[n][0]=c[n][1]=a[n],i=2;i<=n;++i)
for (p=0;p<2;++p) for (q=0;q<2;++q)
f[i][p]=min(f[i][p],f[i-1][q]+1LL*c[i][p]*c[i-1][q^1]);
printf("%lld\n",min(f[n][0],f[n][1]));
}
return 0;
}
D. Game on Axis
分类讨论题
可能是一段时间没做题了，想不同情况的时候感觉思路不是很清晰，写完代码样例过一个挂一个，还好最后磕磕绊绊地写掉了
首先一个最simple的情况就是要根据在原来的序列上\(1\)是否能走出去来分类讨论：
- 若\(1\)本身无法走出去，说明一定存在一段成环的路径，我们统计出成环路径上的点数\(c\)
- 显然修改除这\(c\)个点外的任意点的值都不会让\(1\)走出，因此不用考虑
- 对于这\(c\)个点，直接修改它们的值有\(n+1\)种直接一步跳出的方案
- 同时我们统计下有哪些点是原来可以走出去的，设点数为\(m\)
- 不难发现对于这\(c\)个点，修改值使得它走到这\(m\)个点的任意一个都是可行的
- 因此综上，答案为\(c\times(n+1+m)\)
- 若\(1\)本身可以走出去，我们不妨统计处走出路径上的点数\(c\)
- 显然修改除这\(c\)个点外的任意点的值都还是会让\(1\)走出，因此有\((n-c)\times (2n+1)\)的贡献
- 对于这\(c\)个点，利用类似于上面的结论，我们发现会有\(c\times(n+1+m)\)的贡献，但是要减去一部分
- 要减去的部分就是当我们重定向某个点\(x\)时，如果指向了某个点\(z\)，满足从\(z\)可以走到这个跳出路径上的某个点\(y\)时，这种方法就要被减去
- 计算方法也很简单，我们统计下能走出去的点中，能走到每个点的点个数即可，直接用拓扑排序搞一遍即可
理清思路的话其实代码还是很清晰和好写的说
#include<cstdio>
#include<iostream>
#include<vector>
#define RI register int
#define CI const int&
#define pb push_back
using namespace std;
const int N=200005;
int t,n,a[N],q[N],deg[N],f[N]; bool vis[N],out[N]; vector <int> v[N],rv[N];
int main()
{
//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
for (scanf("%d",&t);t;--t)
{
RI i,H=0,T=0; for (scanf("%d",&n),i=1;i<=n;++i)
v[i].clear(),rv[i].clear(),vis[i]=out[i]=deg[i]=0,f[i]=1;
for (i=1;i<=n;++i)
{
scanf("%d",&a[i]); int tp=i+a[i];
if (tp<1||tp>n) out[i]=1,q[++T]=i; else v[i].pb(tp),rv[tp].pb(i),++deg[tp];
}
while (H<T)
{
int now=q[++H]; for (int to:rv[now])
if (!out[to]) out[to]=1,q[++T]=to;
}
int m=T; for (H=T=0,i=1;i<=n;++i) if (!deg[i]) q[++T]=i;
while (H<T)
{
int now=q[++H]; for (int to:v[now])
if (f[to]+=f[now],!--deg[to]) q[++T]=to;
}
if (out[1])
{
int c=0,now=1; long long ret=0;
while (now>=1&&now<=n) ++c,ret+=f[now],now+=a[now];
printf("%lld\n",1LL*(n-c)*(2*n+1)+1LL*c*(n+m+1)-ret);
} else
{
int c=0,now=1; while (!vis[now]) vis[now]=1,++c,now+=a[now];
printf("%lld\n",1LL*c*(n+m+1));
}
}
return 0;
}
E. The Harmonization of XOR
猜结论题
当时本来想睡觉了，但是写完D还剩一个小时就想着看一眼E，结果稍微手玩了下感觉有个可能的结论
本来都没打算能过的，就是想交一发存个档来着，结果看到那个PT通过的界面我自己人都懵逼了的说
先直接上构造的结论：
- 首先检查\(k\)个\(x\)的异或和是否等于\(1\sim n\)的异或和，不同的话显然无解
- 然后先单独判断掉\(k=1\)的情形，否则考虑以下方案
- 如果存在\(x\in[1,n]\)，则令\(x\)为一个单独的集合
- 如果对于某个未使用的\(i\)，满足\(i\oplus x\in[1,n]\)且\(i\oplus x\)也未使用，则令\(i\)和\(i\oplus x\)为一个集合
- 根据以上方案构成\(k-1\)个集合后，把剩下的元素都扔到一个集合里，若无法构成\(k-1\)个则无解
当时想着这样应该能组成尽可能多的集合数，然后看了官方Tutorial才知道怎么证明：
- 假设有\(M\)个数在\(x\)的最高位取到\(1\)，那么由于每个集合都至少需要一个数在该位取\(1\)，所以最多只能分\(M\)个集合
- 因此我们采取以上的策略，对于每一个在该位取\(1\)的数\(i\)，此时\(x\oplus i<x\)且\(x\oplus i<i\)一定成立，因此就可以分出\(M\)个集合了
- 因此我们得到了\(M\)个可分的集合，同时由于我们可以将其中的任意三个集合合并，使得集合数为\(M-2,M-4,\cdots\)
- 由于前面有检查\(k\)个\(x\)的异或和是否等于\(1\sim n\)的异或和的步骤，因此目标集合的奇偶性一定相同，可以由这种方法构造出
#include<cstdio>
#include<iostream>
#define RI register int
#define CI const int&
using namespace std;
const int N=200005;
int t,n,k,x,p[N],q[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%d",&n,&k,&x),i=1;i<=n;++i) vis[i]=0;
int c=0,lst=1; if (k!=1&&x<=n) p[++c]=x,q[1]=-1,vis[x]=1;
while (c<k-1)
{
while (vis[lst]) ++lst; if (lst>n) break;
int tp=lst^x; if (tp<=n&&!vis[tp]) ++c,p[c]=lst,q[c]=tp,vis[lst]=vis[tp]=1; else ++lst;
}
if (c<k-1) { puts("NO"); continue; }
int ret=0,ct=0; for (i=1;i<=n;++i) if (!vis[i]) ret^=i,++ct;
if (ret!=x) { puts("NO"); continue; }
for (puts("YES"),i=1;i<k;++i) if (~q[i]) printf("2 %d %d\n",p[i],q[i]); else printf("1 %d\n",p[i]);
for (printf("%d ",ct),i=1;i<=n;++i) if (!vis[i]) printf("%d ",i); putchar('\n');
}
return 0;
}