碎碎念
班会8点开始，开到10点半直接被保安赶出来可还行
有点麻，冲到寝室10点40，状态全无，开打div1+2的比赛
第5题又是数学题，已经连续好几道数学题做不出来了，麻中麻
做出4题也上分了，嘿嘿嘿unrated了，麻中麻中麻
A - Mainak and Array
给你一个数组，你有一次机会滚动一个区间任意次
最大化a[n]-a[1]
solution
三种情况，第一种是前一个-后一个
第二种是最小在1或最大在n，最大-最小
第三种是最大-a[1]或a[n]-最小
#include<bits/stdc++.h>
#define inf 0x3f3f3f3f
using namespace std;
int T,n,a[2010];
int main()
{
scanf("%d",&T);
while(T--)
{
int minn=inf,maxx=0;
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
minn=min(a[i],minn);
maxx=max(a[i],maxx);
}
int flag=1,ans=0;
for(int i=1;i<n;i++)
{
if(a[i]==maxx&&a[i+1]==minn)
flag=0;
ans=max(ans,a[i]-a[i+1]);
}
if(a[1]==minn||a[n]==maxx)
flag=0;
if(flag)
ans=max(ans,max(maxx-a[1],a[n]-minn));
else ans=maxx-minn;
printf("%d\n",ans);
}
return 0;
}B - Mainak and Interesting Sequence
给你n和m，构造长度为n，和为m的数组，使得所有pi=0
pi的定义为数组中所有小于ai的数的xor和
solution
显然要求是除了最大数之外的每个数都要有偶数个
那么n为奇数时n-1个1，n为偶数时n-2个1就行了
#include<bits/stdc++.h>
using namespace std;
int T,n,m;
int main()
{
scanf("%d",&T);
while(T--)
{
scanf("%d%d",&n,&m);
if(n>m)puts("No");
else if(n%2)
{
puts("Yes");
for(int i=1;i<n;i++)
putchar('1'),putchar(' ');
printf("%d\n",m-n+1);
}
else
{
if(m%2)puts("No");
else
{
puts("Yes");
for(int i=3;i<=n;i++)
putchar('1'),putchar(' ');
printf("%d %d\n",(m-n+2)/2,(m-n+2)/2);
}
}
}
return 0;
}C - Jatayu's Balanced Bracket Sequence
给你一个匹配的括号序列，以该序列建立一张无向图
点i，j有边的条件是区间[i,j]是匹配的括号序列
求连通块数量
solution
显然归属于同一块的最外层的括号是一个连通块
所以使用递归解决，预处理出每个括号的对应括号在哪
#include<bits/stdc++.h>
using namespace std;
int T,n,a[200010];
char s[200010];
stack<int>q;
int solve(int sl,int sr)
{
if(sl>=sr)return 0;
if(sl+1==sr)return 1;
int ret=1,u=sl;
while(u<=sr)
{
ret+=solve(u+1,a[u]-1);
u=a[u]+1;
}
return ret;
}
int main()
{
scanf("%d",&T);
while(T--)
{
scanf("%d%s",&n,s);
for(int i=0;i<(n<<1);i++)
{
if(s[i]=='(')
q.push(i);
else
{
int u=q.top();
q.pop();
a[u]=i,a[i]=u;
}
}
printf("%d\n",solve(0,(n<<1)-1));
}
return 0;
}D - Edge Split
给你一张无向连通图，至多有n+2条边
现在需要给边染成两种颜色
最小化只启用一种颜色的边的连通块数量之和
solution
只要想办法构造每条边都不构成环就行了
因为m不超过n+2，所以最小生成树之后至多有一个三元环
如果有三元环，将环中的一条边加入最小生成树并重新做一遍最小生成树
#include<bits/stdc++.h>
using namespace std;
int T,n,m,x[200010],y[200010],f[200010];
char ans[200010];
int cnt,c[10];
int find(int x)
{
if(f[x]!=x)f[x]=find(f[x]);
return f[x];
}
void ins(int x)
{
for(int i=1;i<=cnt;i++)
if(c[i]==x)return;
c[++cnt]=x;
}
int main()
{
scanf("%d",&T);
while(T--)
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
f[i]=i;
for(int i=1;i<=m;i++)
{
scanf("%d%d",&x[i],&y[i]);
int fx=find(x[i]),fy=find(y[i]);
ans[i]=(fx==fy?'1':'0');
f[fy]=fx;
}
if(m==n+2)
{
cnt=0;memset(c,0,sizeof(c));
int ret;
for(int i=1;i<=m;i++)
if(ans[i]=='1')
ins(x[i]),ins(y[i]),ret=i;
while(cnt==3)
{
for(int i=1;i<=n;i++)
f[i]=i;
ans[ret]='0';
f[x[ret]]=y[ret];
for(int i=1;i<=m;i++)if(i!=ret)
{
int fx=find(x[i]),fy=find(y[i]);
ans[i]=(fx==fy?'1':'0');
f[fy]=fx;
}
cnt=0,memset(c,0,sizeof(c));
for(int i=1;i<=m;i++)
if(ans[i]=='1')
ins(x[i]),ins(y[i]),ret=i;
}
}
for(int i=1;i<=m;i++)
putchar(ans[i]);
putchar('\n');
}
return 0;
}E - Almost Perfect
完美排列满足abs(p[i]-a[i])<=1
其中p是排列数组，a[i]表示i在p中的位置
求出长度为n的完美排列的数量
solution
有个性质，如果将排列变为有向图，那么环的大小只能为1,2,4
大小为4的环一定是(i,i+1,j,j+1)，证明有点烦，不想证了QAQ
那么可以枚举大小为4的环的数量
使n为排列长度，m为大小为4的环的数量，方案数即为C(n-2m,2m)*(2m!)/m!
大致意思是我们先取出2m对(i,i+1)，再分别编号1~2m，令1与2，3与4，......，2m-1与2m配对，最后去重
然后我们只需要计算剩下n-4m个数分成大小为1或2的环的方案数即可
令f[i]表示i个数分成大小为1或2的环的方案数
更新时有i用与不用两种，不用直接继承f[i-1]
用的话先从前面选一个，有i-1种，剩下i-2个数的方案数即为f[i-2]
所以f[i]=f[i-1]+(i-1)*f[i-2]
#include<bits/stdc++.h>
#define N 300010
using namespace std;
const int MOD=998244353;
int pow(int a,int b){
int res=1;
while(b)
{
if(b&1)
res=1ll*res*a%MOD;
b/=2,a=1ll*a*a%MOD;
}
return res;
}
int T,n;
int inv[N],ji[N],ni[N];
int f[N];
int C(int x,int y){
return 1ll*ji[x]*ni[y]%MOD*ni[x-y]%MOD;
}
int main()
{
inv[1]=1;
for(int i=2;i<N;i++)
inv[i]=MOD-1ll*MOD/i*inv[MOD%i]%MOD;
ji[0]=1,ni[0]=1;
for(int i=1;i<N;i++)
ji[i]=1ll*ji[i-1]*i%MOD,
ni[i]=1ll*ni[i-1]*inv[i]%MOD;
f[0]=1,f[1]=1;
for(int i=2;i<N;i++)
f[i]=(f[i-1]+1ll*f[i-2]*(i-1)%MOD)%MOD;
scanf("%d",&T);
while(T--)
{
int ans=0;
scanf("%d",&n);
for(int i=0;4*i<=n;i++)
ans=(ans+1ll*C(n-2*i,2*i)*ji[2*i]%MOD*ni[i]%MOD*f[n-4*i]%MOD)%MOD;
printf("%d\n",ans);
}
return 0;
}
Comments NOTHING