codeforces好题
CF1528B Kavi on Pairing Duty
\(\large\color{#a9acf9}{^{\ast}1700}\)
这是一道很好的 \(\mathrm{dp}\) 题。
引理：设 \(1\) 与 \(x\) 配对，则对于每一个 \(p(x
设 \(f_i\) 表示 \(i\) 时的种数。
对 \(x\) 进行分类讨论。
当 \(n+1\le x\le2n\) 时，根据引理可得 \(1\) 与 \(x\) 配对，\(2\) 与 \(x+1\) 配对，\(3\) 与 \(x+2\) 配对，直至 \(2n-x+1\)与\(2n\) 配对。因为 \(n+1\le x\le2n\)，所以 \(1\le2n-x+1\le x\)，可以想象到连完之后中间会空下连续的一段，共 \(2x-2n-2\) 个点，个数为 \(f_{x-n-1}\)。所以当 \(n+1\le x\le2n\) 时，个数共有 \(\sum_{i=0}^{n-1}f_i\) 种。
当 \(2\le x\le n\) 时，易得 \(x-1\) 为 \(n\) 的约数且不等于 \(n\)，设 \(D(n)\) 表示 \(n\) 除自己外的约数个数，则当 \(2\le x\le n\) 时，个数共有 \(D(n)\) 种。
综上，\(f_n=\sum_{i=0}^{n-1}f_i+D(n)\)。
初始化 \(f_0=1\)。
时间复杂度：\(O(n\log n)\)。
code
#include
using namespace std;
long long mod=998244353;
long long n;
long long dp[1000005];
int main()
{
cin>>n;
for(int i=1;i<=n;i++)
{
for(int j=2;i*j<=n;j++) dp[i*j]++;
}
dp[0]=1;
long long sum=1;
for(int i=1;i<=n;i++)
{
dp[i]=(dp[i]+sum)%mod;
sum=(sum+dp[i])%mod;
}
cout< CF1027E Inverse Coloring
\(\large\color{#f8cd91}{^{\ast}2100}\)
这是一道很好的 \(\mathrm{dp}\) 题。
引理：当一个正方形的第一行与第一列确定之后，这个正方形的漂亮着色就已经确定了。
证明：易得。
因此问题就转变为了要求行与列的最大连续同色长度的乘积 \(
行与列相同，所以可以只算一边。
设 \(f_{i,j}\) 表示在前 \(i\) 个中，最大连续黑色长度 \(\le j\) 的个数。
不难得出转移方程：\(f_{i,j}=\sum_{k=i-j}^{i-1}f_{k,min(j,k)}\)。
初始化：\(f_{i,i}=1\)
再利用差分，设 \(sum_i\) 表示长度为 \(n\)，且最大连续黑色长度 \(=i\) 的个数。
则 \(ans=\sum_{i=1}^n\sum_{j=1}^nsum_i\times sum_j\ [i\times j
最后因为有黑白两色，不要忘了 \(ans\times 2\)。
时间复杂度：\(O(n^3)\)。
code
#include
#include
#include
#include
using namespace std;
int n,m;
const int mod=998244353;
long long f[505][505],sum[505],ans;
int main()
{
cin>>n>>m;
for(int i=1;i<=n;i++) f[i][i]=1;
for(int i=2;i<=n;i++)
{
for(int j=0;j<=i;j++)
{
for(int k=i-j;k<=i-1;k++) f[i][j]=(f[i][j]+f[k][min(j,k)])%mod;
}
}
for(int i=1;i<=n;i++) sum[i]=(f[n][i]-f[n][i-1]+mod)%mod;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
if(i*j CF1510D Digits
\(\large\color{#f8cd91}{^{\ast}2100}\)
这是一道很好的 \(\mathrm{dp}\) 题。
状态很容易想出，设 \(f_{i,j}\) 表示前 \(i\) 位乘积 \(\%10\) 后为 \(j\)，且乘积最大的值。
但是转移时会发现乘积太大，无法直接转移。
因此我们可以运用对数化乘为加，即 \(x\times y=2^{\log_2x}\times2^{\log_2y}=2^{\log_2x+\log_2y}\)。
所以我们只需记录乘积的 \(\log\) 值即可。
转移方程：\(f_{i,k}=max(f_{i-1,k},f_{i-1,j}+\log_2a_i)\)。
至于方案，我们在更新答案的同时用一个 \(pre\) 数组来记录，即 \(pre_{i,k}=j\)。
初始化 \(f_{0,i}=-\inf\)，\(f_{0,1}=0\)。
时间复杂度：\(O(10n)\)
code
#include
#include
#include
#include
using namespace std;
int n,k,cnt;
long long a[100005],pre[100005][15],ans[100005];
double f[100005][15];
int main()
{
cin>>n>>k;
for(int i=1;i<=n;i++) cin>>a[i];
memset(pre,-1,sizeof(pre));
for(int i=0;i<=9;i++) f[0][i]=-1e9;
f[0][1]=0;
for(int i=1;i<=n;i++)
{
for(int j=0;j<=9;j++) f[i][j]=f[i-1][j];
for(int j=0;j<=9;j++)
{
int k=j*a[i]%10;
if(a[i]==1||f[i][k]=1;i--)
{
if(pre[i][k]!=-1)
{
ans[++cnt]=a[i];
k=pre[i][k];
}
}
if(cnt==0) cout<<-1< CF1515E Phoenix and Computers
\(\large\color{#f8cd91}{^{\ast}2200}\)
这是一道很好的 \(\mathrm{dp}\) 题。
首先我们将电脑打开方式分为两种，一种为手动，一种为自动。
那么我们先来考虑 \(n\) 台电脑全部为手动的情况。
如果先打开 \(1\) 号，那么剩余 \(n-1\) 个数中 \([2,n]\) 的顺序一定是 \(2,3,\dots,n\)，共 \(1\) 种。
如果先打开 \(2\) 号，那么剩余 \(n-1\) 个数中 \([3,n]\) 的顺序一定是 \(3,4,\dots,n\)，所以这 \(n-2\) 个数可以在 \(n-1\) 个空中随便选 \(n-2\) 个位置，然后在把 \(1\) 填入剩余的空中，共有 \(\binom{n-1}{n-2}\) 种。
如果先打开 \(3\) 号，那么剩余 \(n-1\) 个数中 \([4,n]\) 的顺序一定是 \(4,5,\dots,n\)，所以这 \(n-3\) 个数可以在 \(n-1\) 个空中随便选 \(n-3\) 个位置，然后在把 \(2,1\) 按序填入剩余的空中，共有 \(\binom{n-1}{n-3}\) 种。
所以对于一般情况，如果先打开 \(k(1\le k\le n)\) 号，那么剩余 \(n-1\) 个数中 \([k+1,n]\) 的顺序一定是 \(k+1,k+2,\dots,n\)，所以这 \(n-k\) 个数可以在 \(n-1\) 个空中随便选 \(n-k\) 个位置，然后在把 \(k,k-1,\dots,1\) 按序填入剩余的空中，共有 \(\binom{n-1}{n-k}\) 种。
所以综上所述，\(n\) 台电脑全部为手动的情况共有 \(\sum_{i=1}^{n}\binom{n-1}{n-k}=2^{n-1}\)。
接下来我们考虑最后电脑开启的状态。
很明显最终电脑的状态是一段手动，一个自动，再来一段手动，如此交替。
设 \(f_{i,j}\) 表示前 \(i\) 台电脑，手动 \(j\) 台，第 \(i\) 台手动，且第 \(i+1\) 台为自动的方案数。
那么转移时就从一段手动转移到下一段手动，即 \(f_{i,j}\to f_{i+k+1,j+k}\)。
我们先来考虑这 \(k\) 台手动内部的顺序，我们已经证明，为 \(2^{k-1}\) 种。
再来考虑原来的 \(j\) 台手动和这 \(k\) 台的手动，可以随意穿插，共有 \(\binom{j+k}{k}\) 种。
以及原有的 \(f_{i,j}\) 种，我们可以得出转移方程 \(f_{i+k+1,j+k}=\sum_{k=1}^{n-i-1}f_{i,j}\times2^{k-1}\times\binom{j+k}{k}\)。
初始化 \(f_{i,i}=2^{i-1}\)。
答案为 \(\sum_{i=1}^nf_{n,i}\)。
时间复杂度：\(O(n^3)\)。
code
#include
using namespace std;
int n,mod;
long long C[405][405],pow2[405],f[405][405],ans;
int main()
{
cin>>n>>mod;
C[0][0]=1;
for(int i=1;i<=n;i++)
{
C[i][0]=1;
for(int j=1;j<=i;j++) C[i][j]=(C[i-1][j-1]+C[i-1][j])%mod;
}
pow2[0]=1;
for(int i=1;i<=n;i++) pow2[i]=pow2[i-1]*2%mod;
for(int i=1;i<=n;i++)
{
f[i][i]=pow2[i-1];
for(int j=1;j<=i;j++)
{
for(int k=1;k<=n-i-1;k++) f[i+k+1][j+k]=(f[i+k+1][j+k]+f[i][j]*pow2[k-1]%mod*C[j+k][k]%mod)%mod;
}
}
for(int i=1;i<=n;i++) ans=(ans+f[n][i])%mod;
cout< CF1427E Xum
\(\large\color{#ef7f7b}{^{\ast}2500}\)
这是一道很好的数学构造题。
首先容易发现一个偶数与它后面的那个奇数异或和为 \(1\)，那么只需要找到这样的两个数即可。
设其中的偶数为 \(m\)，奇数为 \(n\)，则只需 \(n-m=1\)，思考如何与 \(x\) 产生联系。
不妨设 \(n\) 为 \(x\) 的倍数，\(m\) 为 \(y\) 的倍数，即转为 \(ax-by=1\)，成为了扩展欧几里德的模版，由裴蜀定理得，对于一对 \(x,y\)，当且仅当 \((x,y)=1\) 时，必能找到一对正数解 \(a,b\)，并且 \(b\) 为偶数。
问题转化为找到一个数 \(y\)，使得 \((x,y)=1\)。
一个神奇的操作：设 \(2^e\le x<2^{e+1}\)，那么令 \(y=2^ex\oplus x=2^ex+x-2\times 2^e=(2^e+1)x-2^{e+1}\)，此时 \((x,y)=(x,(2^e+1)x-2^{e+1})=(x,2^{e+1})=1\)，满足要求，并且可以通过和与异或的方式实现。
code
#include
using namespace std;
#define int long long
int x,y;
int e,f,g;
int u,v;
int xt,yt;
int xf,yg;
int c[1000005][3],cnt;
int lowbit(int a)
{
return a&(-a);
}
void add(int a,int b,int opt)
{
c[++cnt][0]=a;
c[cnt][1]=b;
c[cnt][2]=opt;
}
void print(int a,int b,int opt)
{
if(opt==0) printf("%lld + %lld\n",a,b);
else printf("%lld ^ %lld\n",a,b);
return;
}
void exgcd(int a,int b)
{
if(b==0)
{
xt=1;
yt=0;
return;
}
exgcd(b,a%b);
int z=xt;
xt=yt;
yt=z-a/b*yt;
return;
}
void mul(int a,int b)
{
u=lowbit(a);
int sum=u*b;
a-=u;
for(;a;a-=lowbit(a))
{
u=lowbit(a);
add(sum,u*b,0);
sum+=u*b;
}
}
signed main()
{
scanf("%lld",&x);
e=log2(x),y=x;
for(int i=1;i<=e;i++) add(y,y,0),y<<=1;
xf=y;
add(x,y,1),y^=x;
yg=y;
exgcd(x,y);
yt=-yt;
while(xt<0||yt<0||yt%2==1) xt+=y,yt+=x;
while(xt>2*y&&yt>2*x) xt-=2*y,yt-=2*x;
f=log2(xt),g=log2(yt);
for(int i=e+1;i<=f;i++) add(xf,xf,0),xf<<=1;
for(int i=1;i<=g;i++) add(yg,yg,0),yg<<=1;
mul(xt,x),mul(yt,y);
add(xt*x,yt*y,1);
printf("%lld\n",cnt);
for(int i=1;i<=cnt;i++) print(c[i][0],c[i][1],c[i][2]);
return 0;
}
CF1270G Subset with Zero Sum
\(\large\color{#ec483f}{^{\ast}2700}\)
这是一道很好的图论构造题。
题目中的 \(i-n\le a_i\le i-1\) 经过调换改为 \(1\le i-a_i\le n\)，可以发现 \(\sum a_i=0\) 与 \(\sum i=\sum i-a_i\) 等价。此时便可以从 \(i\) 向 \(i-a_i\) 连一条边，由于是 \(n\) 个点，\(n\) 条边的图，因此至少有一个环。对这个环上的节点编号求和，便会得到之前的等式，因此就找见了一个满足的解。
此题的妙处在于通过确定 \(a_i\) 的范围想到连边，再想到是通过求和的方式转换为找环。
code
#include
using namespace std;
const int N=1e6+5;
int t;
int n,a[N],to[N],flag[N],d[N],u,cnt;
int main()
{
scanf("%d",&t);
while(t--)
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
to[i]=i-a[i];
flag[i]=0;
}
for(int i=1;i<=n;i++)
{
u=i,cnt=0;
while(u&&!flag[u])
{
flag[u]=1;
d[to[u]]=d[u]+1;
u=to[u];
}
if(u)
{
printf("%d\n%d ",d[u]-d[to[u]]+1,u);
break;
}
}
flag[u]=0;
u=to[u];
while(flag[u]) printf("%d ",u),u=to[u];
printf("\n");
}
return 0;
}