2021ICPC上海站-补题
2021ICPC上海站-补题
前言：打铁的第二站，思维太过僵硬，专业知识还不够深。赛中过了DEG，然后I题dp没想出来，罚坐4小时…
比赛链接：https://ac.nowcoder.com/acm/contest/24872
E题（签到·贪心）
题意：
从n个数中选m个，使其两两之间差值≥k
思路：
贪心的想，先排序，从头开始取，保证现在取的数比上一次取的要大于等于k
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const ll inf=1e18;
ll n,m,k,ans;
ll a[200010];
int main(){
scanf("%lld%lld",&n,&m);
for(int i=1;i<=n;i++)scanf("%lld",&a[i]);
sort(a+1,a+n+1);
k=-inf;ans=0;
for(int i=1;i<=n;i++){
if(a[i]>=k+m){
ans++;
k=a[i];
}
}
printf("%lld\n",ans);
}
D题（签到·简单数学）
题意：
给了分数p/q，计算a,b，满足1≤a,b≤1e9，p/q==a/b+b/a。不存在输出0 0。
思路：
a/b+b/a=(a^2+b^2)/ab，先约分p,q，现在只需判断是否存在k，满足kp=(a^2+b^2)，kq=ab。并且满足计算出来的ab满足范围约束。
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const ll inf=1e18,lim=1e9;
ll gcd(ll x,ll y){if(y==0)return x;return gcd(y,x%y);}
ll sq(ll x){return x*x;}
ll n,m,k,p,t,ans,x,y,x1,x2,k1,k2;
ll a[200010];
int main(){
scanf("%lld",&t);
while(t--){
scanf("%lld%lld",&n,&m);
k=gcd(n,m);
n/=k;m/=k;
k=sq(n)-4*sq(m);
if(k>=0){
p=sqrt(k);
if(p*p==k){
x1=n-p;x2=n+p;
y=2*m;
k1=gcd(x1,y);
k2=gcd(x2,y);
x1/=k1,x2/=k2;
if(x1>0&&x1>=1&&x1<=lim&&y/k1>=1&&y/k1<=lim){
x=x1,y=y/k1;ans=1;
}
else if(x2>=1&&x2<=lim&&y/k2>=1&&y/k2<=lim){
x=x2,y=y/k2;ans=1;
}
else ans=0;
}
else ans=0;
}
else ans=0;
if(ans)printf("%lld %lld\n",x,y);
else printf("0 0\n");
}
}
G题（dfs/树形dp）
题意：
给定树，求将树分解成若干长度为2的路径的方案数。
思路：
考虑dfs，当前节点为x，有k个可用子节点。
- k为偶数，儿子--父亲(x)--儿子的路径可以构造k/2条，方案数为C(k,2)×C(k-2,2)×C(k-4,2)×…×C(2,2)，x对于其父节点来说视为可用的子节点
- k为奇数时，儿子--父亲(x)--儿子的路径可以构造k/2条，方案数为C(k,2)×C(k-2,2)×C(k-4,2)×…×C(3,2)，剩下的一条边将与边(x，x的父亲)组合，同时x对于其父节点来说视为不可用的子节点
（另外看到官方题解的做法是树形dp，思路大体一致）
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const ll inf=1e18,lim=1e9,N=1e5+10,mod=998244353;
ll gcd(ll x,ll y){if(y==0)return x;return gcd(y,x%y);}
ll fksm(ll a,ll b){ll r=1;for(a%=mod;b;b>>=1){if(b&1)r=r*a%mod;a=a*a%mod;}return r;}
ll sq(ll x){return x*x;}
ll n,m,k,p,t,ans,x,y,x1,x2,k1,k2;
ll a[N];
vector<ll>v[N];
ll fac[N],fra[N];
void init(){
fac[0]=1;
for(int i=1;i<=N;i++)fac[i]=fac[i-1]*i%mod;
fra[N]=fksm(fac[N],mod-2);
for(int i=N-1;i>=0;i--)fra[i]=fra[i+1]*(i+1)%mod;
}
ll C(ll n,ll k){if(!n||!k)return 1;if(n<k||k<0)return 0;return fac[n]*fra[k]%mod*fra[n-k]%mod;}
ll dfs(ll x,ll ac){
ll siz=v[x].size(),res=0;
for(int i=0;i<siz;i++){
if(v[x][i]!=ac)res+=dfs(v[x][i],x);
}
ll m=1,k=res/2,y=res;
while(res>2){
m=m*C(res,2)%mod;
res-=2;
}
m=m*fra[k]%mod;
ans=ans*m%mod;
if(y%2==0)return 1;
else return 0;
}
int main(){
init();
scanf("%lld",&n);
for(int i=1;i<n;i++){
scanf("%lld%lld",&x,&y);
v[x].push_back(y);
v[y].push_back(x);
}
ans=1;
dfs(1,0);
printf("%lld\n",ans);
}
I题（背包dp）
题意：
n张卡，每张卡有点数ti和价值vi，选择一些卡将其分成点数和相等的两堆，求两堆的价值和最大值。其中，给定k，可以使至多k张卡的点数×2。
思路：
考虑背包dp，dp(i,j,k)表示前i个，选了j个，左堆-右堆的点数差值为k（令左堆≥右堆）。dp(i,j,k)可以由五种状态取最大值转移过来。（比赛的时候一直在想四维dp，没想到可以左堆-右堆这种操作）
- dp(i-1,j,k)
- dp(i-1,j,k-ti)+vi
- dp(i-1,j,k+ti)+vi
- dp(i-1,j,k-2ti)+vi
- dp(i-1,j,k+2ti)+vi
#include<bits/stdc++.h>
#define ll long long
#define L(i,j,k) for(ll i=(j);i<=(k);i++)
#define R(i,j,k) for(ll i=(j);i>=(k);i--)
#define inf 0x3f3f3f3f3f3f3f3f
#define MS(i,j) memset(i,j,sizeof (i))
const ll N=2e4+10,mod=1e9+7;
using namespace std;
ll gcd(ll x,ll y){if(y==0) return x;return gcd(y,x%y);}
ll fksm(ll a,ll b){ll r=1;if(b<0)b+=mod-1;for(a%=mod;b;b>>=1){if(b&1)r=r*a%mod;a=a*a%mod;}return r;}//a 分母; b MOD-2
ll lowbit(ll x){return x&(-x);}
ll m,n,l,r,t,x,y,z,k,p,pp,mx,my,ansx,ansy,num,sum,pos,tot,root,block,key,cnt,minn,maxx,ans;
ll a[N],b[N],dp[110][110][3000];
bool vis,flag;
char zz;
struct qq{ll x,y;}q[N];
struct tree{ll l,r,tag,sum;}trs;
struct treap{ll l,r,fat,dep,n,w;}trp;
struct edge{ll to,nxt,w;}eg;
int main(){
scanf("%lld%lld",&n,&m);
ans=0;
L(i,1,n)scanf("%lld%lld",&a[i],&b[i]);
MS(dp,-inf);
dp[0][0][0]=0;
L(i,1,n)L(j,0,m)L(k,0,2600){
dp[i][j][k]=dp[i-1][j][k];
if(k-b[i]>=0)dp[i][j][k]=max(dp[i][j][k],dp[i-1][j][k-b[i]]+a[i]);
if(k+b[i]<=2600)dp[i][j][k]=max(dp[i][j][k],dp[i-1][j][k+b[i]]+a[i]);
if(k-2*b[i]>=0&&j-1>=0)dp[i][j][k]=max(dp[i][j][k],dp[i-1][j-1][k-2*b[i]]+a[i]);
if(k+2*b[i]<=2600&&j-1>=0)dp[i][j][k]=max(dp[i][j][k],dp[i-1][j-1][k+2*b[i]]+a[i]);
}
L(i,0,m)ans=max(ans,dp[n][i][0]);
printf("%lld\n",ans);
}
K题（构造）
题意：
n位01串，每一步，第i位的1可以分裂成两个1，分裂在第i-1与第i+1位上，同时第i位上的1消失。若与其他1相撞则消失。构造一个n位01串，使其在2n步以内产生循环。
思路：
构造找规律，可以发现，10->01->10；1001->0110->1001；10001->01010->10001；特判3位时，无法构造，其他的拿2、4、5位拼接即可。（比赛过程中开了这道题，但是题目意思理解错了）
#include<bits/stdc++.h>
#define ll long long
#define L(i,j,k) for(ll i=(j);i<=(k);i++)
#define R(i,j,k) for(ll i=(j);i>=(k);i--)
#define inf 0x3f3f3f3f3f3f3f3f
#define x first
#define y second
#define MS(i,j) memset(i,j,sizeof (i))
const ll N=2e4+10,mod=1e9+7;
using namespace std;
ll gcd(ll x,ll y){if(y==0) return x;return gcd(y,x%y);}
ll fksm(ll a,ll b){ll r=1;if(b<0)b+=mod-1;for(a%=mod;b;b>>=1){if(b&1)r=r*a%mod;a=a*a%mod;}return r;}//a 分母; b MOD-2
ll lowbit(ll x){return x&(-x);}
ll m,n,l,r,t,x,y,z,k,p,pp,mx,my,ansx,ansy,num,sum,pos,tot,root,block,key,cnt,minn,maxx,ans;
ll a[N],b[N],dp[110][110][3000];
bool vis,flag;
char zz;
struct qq{ll x,y;}q[N];
struct tree{ll l,r,tag,sum;}trs;
struct treap{ll l,r,fat,dep,n,w;}trp;
struct edge{ll to,nxt,w;}eg;
int main(){
scanf("%lld",&n);
x=0,y=0,z=0;
if(n==3){
printf("Unlucky\n");
}
else{
if(n%2)x=1,n-=5;
y=n/4;
z=(n%4!=0);
L(i,1,x)printf("10001");
L(i,1,y)printf("1001");
L(i,1,z)printf("10");
}
}
H题（Kruskal重构树）
题意：
给定一个图，n个点，m条边，第i节点有权值ai，连接u,v节点的无向路需要至少w的值才能通过。q个询问，初始位于x节点，自带k权值，每到一个节点可以获得对应的权值，从u到v经过路的时候权值不会减少但至少应有w。求能获得的最大权值。
思路：
按边权从小到大构建Kruskal重构树，化边权为点权。这样可以从x节点开始倍增的往上找，可以发现，只要能到达y节点，那么以y为根的子树上所有节点都可到达。
（Kruskal知道，最小生成树知道，但Kruskal重构树是个什么东东？不得不感慨，这一手化边权为点权实在是太妙了）
#include<bits/stdc++.h>
#define ll long long
#define L(i,j,k) for(ll i=(j);i<=(k);i++)
#define R(i,j,k) for(ll i=(j);i>=(k);i--)
#define inf 0x3f3f3f3f3f3f3f3f
#define x first
#define y second
#define MS(i,j) memset(i,j,sizeof (i))
const ll N=2e5+10,mod=1e9+7;
using namespace std;
ll gcd(ll x,ll y){if(y==0) return x;return gcd(y,x%y);}
ll fksm(ll a,ll b){ll r=1;if(b<0)b+=mod-1;for(a%=mod;b;b>>=1){if(b&1)r=r*a%mod;a=a*a%mod;}return r;}//a 分母; b MOD-2
ll lowbit(ll x){return x&(-x);}
ll m,n,l,r,t,x,y,z,k,p,pp,mx,my,ansx,ansy,num,pos,tot,root,block,key,cnt,minn,maxx,ans;
ll a[N],b[N],fat[25][N],lim[25][N],sum[N],pre[N];
bool vis,flag;
char zz;
struct qq{ll x,y,z;}q[N];
struct tree{ll l,r,tag,sum;}trs[N];
struct treap{ll l,r,fat,dep,n,w;}trp;
struct edge{ll to,nxt,w;}eg;
bool cmp(qq u,qq v){
return u.z<v.z;
}
bool cmpl(ll u,ll v){return u>v;}
struct cmps{bool operator()(qq u,qq v){
return (u.x>v.x);
}};//shun序
ll find(ll x){return x==pre[x]?x:pre[x]=find(pre[x]);}
void meg(ll x,ll y,ll z){
ll fx=find(x),fy=find(y);
if(fx!=fy){
cnt++;
pre[fx]=cnt;pre[fy]=cnt;
fat[0][fx]=cnt;fat[0][fy]=cnt;
lim[0][fx]=max(0ll,z-sum[fx]);
lim[0][fy]=max(0ll,z-sum[fy]);
sum[cnt]=sum[fx]+sum[fy];
}
}
int main(){
scanf("%lld%lld%lld",&n,&m,&t);
L(i,1,n)scanf("%lld",&a[i]);
cnt=n;
L(i,1,n){
pre[i]=i;pre[i+n]=i+n;
sum[i]=a[i];
}
L(i,1,m){
scanf("%lld%lld%lld",&x,&y,&z);
q[i]={x,y,z};
}
sort(q+1,q+m+1,cmp);
L(i,1,m)meg(q[i].x,q[i].y,q[i].z);
fat[0][cnt]=0;
L(i,1,21)//构建2^i代祖先关系
L(j,1,cnt){
fat[i][j]=fat[i-1][fat[i-1][j]];
lim[i][j]=max(lim[i-1][j],lim[i-1][fat[i-1][j]]);
}
while(t--){
scanf("%lld%lld",&x,&k);
R(i,20,0){
if(fat[i][x]&&lim[i][x]<=k)x=fat[i][x];
}
printf("%lld\n",sum[x]+k);
}
}
B题（容斥，NTT，启发式合并）
题意：
给定1到n的排列P，求1到n的排列Q，使Q中两个相邻的数a,b，满足b≠Pa。求构成Q的方案数。
思路：
考虑容斥。Q中两个相邻的数a,b，b≠Pa，相当于Q中不存在(i,Pi)，现在只需容斥的考虑Q中出现了几对(i,Pi)。可以发现，(i,Pi)对可以构成几个环。举个例子：
- P=[2,3,4,5,1]，可以列举出对(1,2),(2,3),(3,4),(4,5),(5,1)。构成了一个5元环，这样的对在Q中最多存在4对。
- P=[2,1,4,5,3]，可以列举出对(1,2),(2,1),(3,4),(4,5),(5,3)。构成了一个2元环和一个3元环，在Q中，第一个2元环的对最多只能出现1对，第二个3元环的对最多只能出现2对。
这时，好像发现了什么……
我们只需枚举每个环有几对出现在Q中。设P中有m个环。对于一个k元环，从其中选出1对的方案数为C(k,1)，选出2对的方案数为C(k,2)，……，选出k-1对的方案数为C(k,k-1)，特殊的、选出k对的方案数为0。那么，Q中出现的总对数就是这m个环出现的对数之和，由此我们可以想到多项式乘法。
考虑NTT，构造生成函数，其单个环的生成函数为：(x+1)^k-x^k。因此，多环只需对每个环的多项式相乘求解即可。启发式合并求解多个多项式乘积。
(补题的时候能推出个大概，但是不会NTT，所以只能从头开始学，顺便把FFT给看了………）
#include<bits/stdc++.h>
#define ll long long
#define L(i,j,k) for(ll i=(j);i<=(k);i++)
#define R(i,j,k) for(ll i=(j);i>=(k);i--)
#define inf 0x3f3f3f3f3f3f3f3f
#define x first
#define y second
#define MS(i,j) memset(i,j,sizeof (i))
const ll N=4e5+10,M=5,mod=998244353,mmod=mod-1;
const double pi=acos(-1);
using namespace std;
ll gcd(ll x,ll y){if(y==0) return x;return gcd(y,x%y);}
ll fksm(ll a,ll b){ll r=1;if(b<0)b+=mod-1;for(a%=mod;b;b>>=1){if(b&1)r=r*a%mod;a=a*a%mod;}return r;}//a 分母; b MOD-2
ll lowbit(ll x){return x&(-x);}
ll m,n,t,x,y,z,k,p,pp,nx,ny,ansx,ansy,lim,num,sum,pos,tot,root,block,key,cnt,minn,maxx,ans;
ll a[N],b[N],a1[N],a2[N],r[N];
bool vis[N]={0},flag;
char zz;
struct qq{ll x,y,z;}q;
struct tree{ll l,r,tag,sum;}trs;
struct treap{ll l,r,fat,dep,n,w;}trp;
struct edge{ll to,nxt,w;}eg;
struct matrix{ll n,m[M][M];};
struct complx{
double r,i;
complx(){}
complx(double r,double i):r(r),i(i){}
complx operator+(const complx& rhs)const{return complx (r+rhs.r,i+rhs.i);}
complx operator-(const complx& rhs)const{return complx (r-rhs.r,i-rhs.i);}
complx operator*(const complx& rhs)const{return complx (r*rhs.r-i*rhs.i,i*rhs.r+r*rhs.i);}
void operator+=(const complx& rhs){r+=rhs.r,i+=rhs.i;}
void operator*=(const complx& rhs){r=r*rhs.r-i*rhs.i,i=r*rhs.i+i*rhs.r;}
void operator/=(const double& x){r/=x,i/=x;}
complx conj(){return complx(r,-i);}
};
bool cmp(qq u,qq v){
return u.z<v.z;
}
bool cmpl(ll u,ll v){return u>v;}
struct cmps{bool operator()(qq u,qq v){
return (u.x>v.x);
}};//shun序
ll fac[N],fra[N],two=fksm(2,mod-2);
void init(){//n阶阶乘初始化
fac[0]=1;
L(i,1,N)fac[i]=fac[i-1]*i%mod;
fra[N]=fksm(fac[N],mod-2);
R(i,N-1,0)fra[i]=fra[i+1]*(i+1)%mod;
}
ll C(ll n,ll k){if(!n||!k)return 1;if(n<k||k<0)return 0;return fac[n]*fra[k]%mod*fra[n-k]%mod;}//组合数
void init_ntt(ll limit){lim=1,k=0;while(lim<limit)lim*=2,k++;L(i,0,lim-1)r[i]=(r[i>>1]>>1)|((i&1)<<(k-1));}
void ntt(ll *a,ll type){
ll G=3,Gi=fksm(G,mod-2);//mod=998244353,G=3;mod=1e9+7,G=5;
L(i,0,lim-1)
if(i<r[i])swap(a[i],a[r[i]]);
for(ll mid=1;mid<lim;mid<<=1){
ll Wn=fksm(type==1?G:Gi,(mod-1)/(mid<<1));
for(ll j=0;j<lim;j+=(mid<<1)){
ll w=1;
for(ll k=0;k<mid;k++,w=(w*Wn)%mod){
ll x=a[j+k],y=w*a[j+k+mid]%mod;
a[j+k]=(x+y)%mod,
a[j+k+mid]=(x-y+mod)%mod;
}
}
}
}
void nttle(ll *a,ll *b){
ntt(a,1);ntt(b,1);
L(i,0,lim-1)a[i]=(a[i]*b[i])%mod;
ntt(a,-1);
ll inv=fksm(lim,mod-2);
L(i,0,lim-1)a[i]=a[i]*inv%mod;
}
ll dfs(ll x){
if(vis[x])return 0;
vis[x]=1;
return dfs(a[x])+1;
}
vector<ll> solve(ll l,ll r){
if(l==r){
vector<ll>res;
L(i,0,b[l]-1)res.push_back(C(b[l],i));
return res;
}
ll mid=(l+r)/2,siz,siz1,siz2;
vector<ll>b1=solve(l,mid);
vector<ll>b2=solve(mid+1,r);
siz1=b1.size();siz2=b2.size();siz=siz1+siz2-1;
init_ntt(siz);L(i,0,lim)a1[i]=0,a2[i]=0;
L(i,0,siz1-1)a1[i]=b1[i];
L(i,0,siz2-1)a2[i]=b2[i];
nttle(a1,a2);
vector<ll>res;
L(i,0,siz-1)res.push_back(a1[i]);
return res;
}
int main(){
init();m=0;MS(vis,0);
scanf("%lld",&n);
L(i,1,n)scanf("%lld",&a[i]);
L(i,1,n){
if(!vis[i]){
vis[x]=1;
b[++m]=dfs(i);
}
}
vector<ll>vans=solve(1,m);
p=1;ans=0;
ll siz=vans.size();
L(i,0,n-1){
if(i>=siz)k=0;
else k=vans[i];
ans=(ans+p*fac[n-i]%mod*k)%mod;
ans=(ans+mod)%mod;
p*=-1;
}
printf("%lld\n",ans);
}
2022-10-24更，NTT板子优化封装
#include<bits/stdc++.h>
#define ll long long
#define L(i,j,k) for(ll i=(j);i<=(k);i++)
#define R(i,j,k) for(ll i=(j);i>=(k);i--)
#define inf 0x3f3f3f3f3f3f3f3f
#define x first
#define y second
#define vec vector
#define pb push_back
#define mkp make_pair
#define MS(i,j) memset(i,j,sizeof (i))
const ll N=4e5+10,M=5,mod=998244353,mmod=mod-1;
const double pi=acos(-1);
using namespace std;
ll gcd(ll x,ll y){if(y==0) return x;return gcd(y,x%y);}
ll fksm(ll a,ll b){ll r=1;if(b<0)b+=mod-1;for(a%=mod;b;b>>=1){if(b&1)r=r*a%mod;a=a*a%mod;}return r;}//a 分母; b MOD-2
ll lowbit(ll x){return x&(-x);}
ll m,n,t,x,y,z,k,p,pp,nx,ny,ansx,ansy,lim,num,sum,pos,tot,root,block,key,cnt,minn,maxx,ans;
ll a[N],b[N],a1[N],a2[N],R[N];
bool vis[N]={0},flag;
char zz;
struct qq{ll x,y,z;}q;
struct tree{ll l,r,tag,sum;}trs;
struct treap{ll l,r,fat,dep,n,w;}trp;
struct edge{ll to,nxt,w;}eg;
bool cmp(qq u,qq v){
return u.z<v.z;
}
bool cmpl(ll u,ll v){return u>v;}
struct cmps{bool operator()(qq u,qq v){
return (u.x>v.x);
}};//shun序
ll fac[N],fra[N],two=fksm(2,mod-2);
void init(){//n阶阶乘初始化
fac[0]=1;
L(i,1,N)fac[i]=fac[i-1]*i%mod;
fra[N]=fksm(fac[N],mod-2);
R(i,N-1,0)fra[i]=fra[i+1]*(i+1)%mod;
}
ll C(ll n,ll k){if(!n||!k)return 1;if(n<k||k<0)return 0;return fac[n]*fra[k]%mod*fra[n-k]%mod;}//组合数
void init_ntt(ll limit){lim=1;ll k=0;while(lim<limit)lim*=2,k++;L(i,0,lim-1)R[i]=(R[i>>1]>>1)|((i&1)<<(k-1));}
void ntt(vec<ll> &f,ll type){
const ll G=3,Gi=fksm(G,mod-2);//mod=998244353,G=3;mod=1e9+7,G=5;
L(i,0,lim-1)
if(i<R[i])swap(f[i],f[R[i]]);
for(ll mid=1;mid<lim;mid<<=1){
ll Wn=fksm(type==1?G:Gi,(mod-1)/(mid<<1));
for(ll j=0;j<lim;j+=(mid<<1)){
ll w=1;
for(ll k=0;k<mid;k++,w=(w*Wn)%mod){
ll x=f[j+k],y=w*f[j+k+mid]%mod;
f[j+k]=(x+y)%mod,
f[j+k+mid]=(x-y+mod)%mod;
}
}
}
if(type==-1){
ll inv=fksm(lim,mod-2);
L(i,0,lim-1)f[i]=f[i]*inv%mod;
}
}
vec<ll> operator * (vec<ll> f,vec<ll> g){
ll siz=f.size()+g.size()-1;
init_ntt(siz);
f.resize(lim),g.resize(lim);
ntt(f,1);ntt(g,1);
L(i,0,lim-1)f[i]=(f[i]*g[i])%mod;
ntt(f,-1);f.resize(siz);
return f;
}
ll dfs(ll x){
if(vis[x])return 0;
vis[x]=1;
return dfs(a[x])+1;
}
vector<ll> solve(ll l,ll r){
if(l==r){
vector<ll>res;
L(i,0,b[l]-1)res.push_back(C(b[l],i));
return res;
}
ll mid=(l+r)>>1;
return solve(l,mid)*solve(mid+1,r);
}
int main(){
init();m=0;MS(vis,0);
scanf("%lld",&n);
L(i,1,n)scanf("%lld",&a[i]);
L(i,1,n){
if(!vis[i]){
vis[x]=1;
b[++m]=dfs(i);
}
}
vector<ll>vans=solve(1,m);
p=1;ans=0;
ll siz=vans.size();
L(i,0,n-1){
if(i>=siz)k=0;
else k=vans[i];
ans=(ans+p*fac[n-i]%mod*k)%mod;
ans=(ans+mod)%mod;
p*=-1;
}
printf("%lld\n",ans);
}
J题（bitset优化）
题意：
给定长度为n的a,b两个01串，当在a中选取区间长度为k时(右端点为i，左端点若＜1则取1)，若区间内1的数量＞0的数量，则=1，否则=0，若该值==bi，则返回1，否则返回0。对于k，若每个区间的返回值都=1，则ck=1，否则ck=0。求01串c。
思路：
题目给的n的范围为1≤n≤50000，不大不小的一个值，考虑bitset优化O(n^2)。
令bitset bi[i]表示右端点为第i位时，每一个k值对应的01状态。考虑前缀和sum，若sum值之前出现过，那么此时的bi[i]可以由上次出现时的转移过来。
| i | 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|---|
| A | 1 | 1 | 0 | 1 | 0 |
| sum | 1 | 2 | 1 | 2 | 1 |
| K=1 | 1 | 1 | 0 | 1 | 0 |
| K=2 | 1 | 1 | 0 | 0 | 0 |
| K=3 | 1 | 1 | 1 | 1 | 0 |
| K=4 | 1 | 1 | 1 | 1 | 0 |
| K=5 | 1 | 1 | 1 | 1 | 1 |
观察图中标黑处，发现当两个sum值相等，bi[i]的值可以转移。设sum值上次相等时位置在j，则bi[i]的后(n-i+j)位，就等于bi[j]的前(n-i+j)位。
另外，可以发现，当ai=0时，bi[i]的前(i-j)位都等于0；当ai=1时，前(i-j-1)位都等于1，第(i-j)位等于0。
当sum值之前没有出现过时，很好推算，若ai=1，则bi[i]全等于1；若ai=0，则bi[i]全等于0。
由此构建bitset递推求解。最后，当b[i]=0时，只需将bi[i]全体取反即可。最后求与。
(bitset优化怎么看起来那么………妙，总之还是题练少了）
#include<bits/stdc++.h>
#define ll long long
#define L(i,j,k) for(ll i=(j);i<=(k);i++)
#define R(i,j,k) for(ll i=(j);i>=(k);i--)
#define inf 0x3f3f3f3f3f3f3f3f
#define x first
#define y second
#define MS(i,j) memset(i,j,sizeof (i))
const ll N=5e4+10,M=5,mod=998244353,mmod=mod-1;
const double pi=acos(-1);
using namespace std;
ll gcd(ll x,ll y){if(y==0) return x;return gcd(y,x%y);}
ll fksm(ll a,ll b){ll r=1;if(b<0)b+=mod-1;for(a%=mod;b;b>>=1){if(b&1)r=r*a%mod;a=a*a%mod;}return r;}//a 分母; b MOD-2
ll lowbit(ll x){return x&(-x);}
ll m,n,t,x,y,z,k,p,pp,nx,ny,ansx,ansy,lim,num,sum,pos,tot,root,block,key,cnt,minn,maxx,ans;
ll a[N],b[N],c[N*2],a2[N],r[N];
bool vis[N]={0},flag;
char zz;
struct qq{ll x,y,z;}q;
struct tree{ll l,r,tag,sum;}trs;
struct treap{ll l,r,fat,dep,n,w;}trp;
struct edge{ll to,nxt,w;}eg;
bool cmp(qq u,qq v){
return u.z<v.z;
}
bool cmpl(ll u,ll v){return u>v;}
struct cmps{bool operator()(qq u,qq v){
return (u.x>v.x);
}};//shun序
bitset<N>bi[N],bc,bans;
int main(){
scanf("%lld",&t);bc.set();
while(t--){
scanf("%lld",&n);
L(i,1,n)scanf("%1lld",&a[i]);
L(i,1,n)scanf("%1lld",&b[i]);
k=50000;bi[0].reset();
L(i,k-n-1,k+n+1)c[i]=-1;
c[k]=0;
L(i,1,n){
k+=(a[i])?1:-1;
if(c[k]>=0){
bi[i].reset();
if(a[i]){
bi[i]|=bc>>(N-(i-c[k]-1));
bi[i]|=bi[c[k]]<<(i-c[k]);
}
else{
bi[i].reset();
bi[i]|=bi[c[k]]<<(i-c[k]);
}
}
else{
if(a[i])bi[i].set();
else bi[i].reset();
}
c[k]=i;
}
bans.set();
L(i,1,n){
if(!b[i])bi[i].flip();
bans&=bi[i];
}
L(i,0,n-1){
if(bans[i])printf("1");
else printf("0");
}
printf("\n");
}
}
M题（结论题·二分图）
题意：
给定一块地，第一次将其随机平分成n份，每个人选取一块。第二次再随机平分成n份，每个人再选取一块。一个人选取的有效面积为两次选取的交集。每个人都希望自己的有效面积尽可能大。问所有情况中，最小的单个人的有效面积为多大。
思路：
考虑二分图匹配，第一次分配的为图为A，第二次分配的图为B。则Ai与B的边权和为1/n，同样Bi与A的边权和为1/n。那么我们考虑已经有t个A匹配了(t-1)个B，同时，A的每个边权都是1/nt，那么这t个A每个都还剩下1/nt的权值还未被匹配，将这1/nt平分给剩下的(n-t+1)个B点，则至少有一个B点的匹配边权为1/(nt×(n-t+1))。构造推理出来求解该最小值即可。可以算出此时t=(n+1)/2。
（想不到，怎么想都想不到吧……二分图可以理解，但这个构造……）
#include<bits/stdc++.h>
#define ll long long
#define L(i,j,k) for(ll i=(j);i<=(k);i++)
#define R(i,j,k) for(ll i=(j);i>=(k);i--)
#define inf 0x3f3f3f3f3f3f3f3f
#define x first
#define y second
#define MS(i,j) memset(i,j,sizeof (i))
const ll N=5e4+10,M=5,mod=998244353,mmod=mod-1;
const double pi=acos(-1);
using namespace std;
ll gcd(ll x,ll y){if(y==0) return x;return gcd(y,x%y);}
ll fksm(ll a,ll b){ll r=1;if(b<0)b+=mod-1;for(a%=mod;b;b>>=1){if(b&1)r=r*a%mod;a=a*a%mod;}return r;}//a ｷﾖﾄｸ; b MOD-2
ll lowbit(ll x){return x&(-x);}
ll m,n,t,x,y,z,k,p,pp,nx,ny,ansx,ansy,lim,num,sum,pos,tot,root,block,key,cnt,minn,maxx,ans;
bool vis,flag;
char zz;
struct qq{ll x,y,z;}q;
struct tree{ll l,r,tag,sum;}trs;
struct treap{ll l,r,fat,dep,n,w;}trp;
struct edge{ll to,nxt,w;}eg;
int main(){
scanf("%lld",&n);
ans=n;
ans*=(n+1)/2;
ans*=(n+2)/2;
double dans=(double)1/(double)ans;
printf("%.9lf",dans);
}
