[ABC176F] Brave CHAIN
先转化一下问题为有\(2\)个数然后每一轮有固定三个数,每一轮在\(5\)个数中删去\(3\)个数
考虑朴素\(dp_{i,j,k}\)表示前\(i\)轮剩余\(j,k\)两个数的最大值,时间复杂度为\(O(10\times n^3)\)
考虑优化,设目前轮的固定的牌是\(A,B,C\),手里还有\(j,k\)
\(Case1:\)
如果\(j,k\)都被删去,则此时转移可以利用\(dp\)的最大值
假设留下\(A,B\),则先考虑\(j=k=C\)的情况要\(+1\),剩下的直接用最大值即可
\(Case2:\)
如果\(j,k\)被删去一个
假设固定\(j\),此时直接暴力\(O(n)\)转移
\(Case3:\)
如果\(j,k\)未被删去
此时\(dp\)的转移只与\(A,B,C\)是否相等有关,相当与直接打增量标记,注意前面的转移要剔除增量的影响
\(Tips:\)分析转移的形式可以优化掉许多无用转移
Show Code
#include<bits/stdc++.h>
using namespace std;
const int MAXN=2005;
int n;
int a[MAXN*3];
int dp[MAXN][MAXN];
int Mp[MAXN];
int fa[MAXN];
int fb[MAXN];
int fc[MAXN];
int main()
{
memset(dp,-0x3f,sizeof(dp));
memset(Mp,-0x3f,sizeof(Mp));
scanf("%d",&n);
for(int i=1;i<=3*n;i++)
{
scanf("%d",&a[i]);
}
dp[a[1]][a[2]]=0;
dp[a[2]][a[1]]=0;
Mp[a[1]]=0;
Mp[a[2]]=0;
int Add=0;
int Maxi=0;
for(int i=3;i<=3*n-2;i+=3)
{
int A=a[i];
int B=a[i+1];
int C=a[i+2];
int Nod=((A==B)&&(B==C));
Add+=Nod;
for(int x=1;x<=n;x++)
{
fa[x]=dp[A][x];
fb[x]=dp[B][x];
fc[x]=dp[C][x];
}
dp[A][B]=max(dp[A][B],(fc[C]+1)-Nod);
dp[A][B]=max(dp[A][B],Maxi-Nod);
dp[B][A]=dp[A][B];
dp[A][C]=max(dp[A][C],(fb[B]+1)-Nod);
dp[A][C]=max(dp[A][C],Maxi-Nod);
dp[C][A]=dp[A][C];
dp[B][C]=max(dp[B][C],(fa[A]+1)-Nod);
dp[B][C]=max(dp[B][C],Maxi-Nod);
dp[C][B]=dp[B][C];
for(int x=1;x<=n;x++)
{
if(B==C)
{
dp[A][x]=max(dp[A][x],fb[x]+1-Nod);
}
dp[A][x]=max(dp[A][x],Mp[x]-Nod);
dp[x][A]=dp[A][x];
}
for(int x=1;x<=n;x++)
{
if(A==C)
{
dp[B][x]=max(dp[B][x],fa[x]+1-Nod);
}
dp[B][x]=max(dp[B][x],Mp[x]-Nod);
dp[x][B]=dp[B][x];
}
for(int x=1;x<=n;x++)
{
if(B==A)
{
dp[C][x]=max(dp[C][x],fb[x]+1-Nod);
}
dp[C][x]=max(dp[C][x],Mp[x]-Nod);
dp[x][C]=dp[C][x];
}
Mp[A]=max(Mp[A],dp[A][B]);
Mp[B]=max(Mp[B],dp[A][B]);
Mp[A]=max(Mp[A],dp[A][C]);
Mp[C]=max(Mp[C],dp[A][C]);
Mp[C]=max(Mp[C],dp[C][B]);
Mp[B]=max(Mp[B],dp[C][B]);
for(int x=1;x<=n;x++)
{
Mp[A]=max(Mp[A],dp[A][x]);
Mp[x]=max(Mp[x],dp[A][x]);
}
for(int x=1;x<=n;x++)
{
Mp[B]=max(Mp[B],dp[B][x]);
Mp[x]=max(Mp[x],dp[B][x]);
}
for(int x=1;x<=n;x++)
{
Mp[C]=max(Mp[C],dp[C][x]);
Mp[x]=max(Mp[x],dp[C][x]);
}
for(int x=1;x<=n;x++)
{
Maxi=max(Maxi,Mp[x]);
}
}
int P=a[3*n];
int Res=0;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
Res=max(Res,dp[i][j]+Add);
}
}
Res=max(Res,dp[P][P]+Add+1);
printf("%d\n",Res);
}
[ABC213G] Connectivity 2
很明显可以枚举一个\(S\),\(i\in S,k\in S\),然后计算\(S\)的联通子图个数\(\times\)补集随便连的方案
我们就设\(F_S\)为\(S\)的联通子图个数,\(G_S\)为补集随便连的方案
很明显\(G\)就是\(S\)中的边数\(2^{Cnt}\)
最开始我想\(F\)的转移是从\(S\)向外连一条边转移,但\(S\)内部的边不好算方案
这时我们考虑容斥,用总方案\(G_S-\)不合法的方案
考虑不合法的方案是由一个联通的\(sub\)与不联通的\(S \oplus {sub}\)，注意我们要保证\(1\)是联通的
所以\(F_S=\sum\limits_{sub\subseteq S,1\in sub}F_{sub}\times G_{S-sub}\)
Show Code
#include<bits/stdc++.h>
using namespace std;
const int MOD=998244353;
int Pow(int a,int b,int p)
{
int res=1;
int base=a;
while(b)
{
if(b&1)
{
res=((long long)res*base)%p;
}
base=((long long)base*base)%p;
b>>=1;
}
return res;
}
int n,m;
int a[25][25];
int G[(1<<17)+5];
int F[(1<<17)+5];
int Ans[25];
int x,y;
void Print(int S)
{
vector<int>R;
R.clear();
while(S)
{
R.push_back(S&1);
S>>=1;
}
reverse(R.begin(),R.end());
for(int i=0;i<R.size();i++)
{
printf("%d",R[i]);
}
printf("\n");
}
int main()
{
scanf("%d %d",&n,&m);
for(int i=1;i<=m;i++)
{
scanf("%d %d",&x,&y);
a[x][y]=1;
}
for(int S=0;S<(1<<n);S++)
{
int Cnt=0;
for(int i=1;i<=n;i++)
{
for(int j=i+1;j<=n;j++)
{
if((S>>(i-1))&1)
{
if((S>>(j-1))&1)
{
Cnt+=a[i][j];
}
}
}
}
G[S]=Pow(2,Cnt,MOD);
}
F[0]=1;
for(int S=1;S<(1<<n);S++)
{
F[S]=G[S];
for(int sub=(S&(S-1));sub;sub=(S&(sub-1)))
{
if(sub&1)
{
}
else
{
continue;
}
F[S]=((long long)F[S]-((long long)F[sub]*G[S^sub])%MOD+MOD)%MOD;
}
}
int Sp=(1<<n)-1;
for(int S=0;S<(1<<n);S++)
{
if(S&1)
{
for(int i=2;i<=n;i++)
{
if((S>>(i-1))&1)
{
Ans[i]=((long long)Ans[i]+((long long)F[S]*G[Sp^S])%MOD)%MOD;
}
}
}
}
for(int i=2;i<=n;i++)
{
printf("%d\n",Ans[i]);
}
}
[CF1749F]Distance to the Path
原问题的修改肯定不好直接修改,而询问是单点修改肯定是在询问上有不同
我最开始是在询问的点找符合条件的链,貌似可以用树剖维护但会算重
然后换个思路,我们维护\(f_{x,d}\)表示\(x\)点为根,距离刚好为\(d\)的增量
很明显\(x\)的权值为\(\sum\limits_{v是x的祖先}f_{v,dist(v,x)}\)
现在考虑维护\(f\),对于\(x\rightarrow y\),对于其中的\(u\),如果直接给距离\(\le d\)节点\(+k\)
那对于\(fa_u\),给距离\(\le d\)节点\(+k\),对于与\(u\)距离\(<d\)的节点会算重
而\(u\)和\(fa_u\)唯一有用的贡献只有距离刚好为\(d\)的
所以如果我们直接对\(u\in x\rightarrow y\),\(f_{u，d}+=k\)
对于距离\(lca\ge d\)的点应该是不会算重的,但对于\(<d\)的以及\(lca\)外的点是无法加到的
考虑\(lca\)的父亲\(fa\),距离它\(\le d-1\)的点能加上,在\(lca\)子树内距离\(d-2\)
再考虑\(fa\)的父亲\(ffa\)，距离它\(\le d-2\)的点能加上,在\(lca\)子树内距离\(d-4\)
由此启发我们让\(fa\)管理\(d-2\)和\(d-3\),而\(ffa\)管理\(d-4,d-5\)(祖先一次管两层)
可以手玩一下,发现是不会算重的
最后树剖维护一下就好了
Show Code
#include<bits/stdc++.h>
#define ls 2*p
#define rs 2*p+1
using namespace std;
const int MAXN=3e5+5;
int n;
int q,d;
int x,y;
int op,k;
vector<int>g[MAXN];
int dfn[MAXN];
int cnt_dfn;
int Wson[MAXN];
int Siz[MAXN];
int Fa[MAXN];
int dep[MAXN];
int top[MAXN];
void dfs1(int x,int f)
{
Siz[x]=1;
for(int i=0;i<g[x].size();i++)
{
int v=g[x][i];
if(v==f)
{
continue;
}
dep[v]=dep[x]+1;
Fa[v]=x;
dfs1(v,x);
Siz[x]+=Siz[v];
if(Siz[v]>Siz[Wson[x]])
{
Wson[x]=v;
}
}
}
void dfs2(int x,int Top)
{
top[x]=Top;
dfn[x]=++cnt_dfn;
if(Wson[x])
{
dfs2(Wson[x],Top);
}
for(int i=0;i<g[x].size();i++)
{
int v=g[x][i];
if(v==Fa[x])
{
continue;
}
if(v==Wson[x])
{
continue;
}
dfs2(v,v);
}
}
struct Seg_node{
int l,r;
int lazy;
};
struct Seg{
Seg_node Tree[MAXN*4];
void push_down(int p)
{
if(Tree[p].lazy)
{
Tree[ls].lazy+=Tree[p].lazy;
Tree[rs].lazy+=Tree[p].lazy;
Tree[p].lazy=0;
}
}
void Build(int p,int l,int r)
{
Tree[p].l=l;
Tree[p].r=r;
if(l==r)
{
Tree[p].lazy=0;
return;
}
int mid=(l+r)>>1;
Build(ls,l,mid);
Build(rs,mid+1,r);
}
void Update(int p,int l,int r,int k)
{
if(Tree[p].l>=l&&Tree[p].r<=r)
{
Tree[p].lazy+=k;
return;
}
push_down(p);
int mid=(Tree[p].l+Tree[p].r)>>1;
if(l<=mid)
{
Update(ls,l,r,k);
}
if(r>mid)
{
Update(rs,l,r,k);
}
}
int Query(int p,int x)
{
if(Tree[p].l==Tree[p].r)
{
return Tree[p].lazy;
}
push_down(p);
int mid=(Tree[p].l+Tree[p].r)>>1;
if(x<=mid)
{
return Query(ls,x);
}
else
{
return Query(rs,x);
}
}
}tree[21];
int Query_lca(int x,int y)
{
while(top[x]!=top[y])
{
if(dep[top[x]]<dep[top[y]])
{
swap(x,y);
}
x=Fa[top[x]];
}
if(dep[x]<dep[y])
{
swap(x,y);
}
return y;
}
void Update_chain(int x,int y,int k,int d)
{
while(top[x]!=top[y])
{
if(dep[top[x]]<dep[top[y]])
{
swap(x,y);
}
tree[d].Update(1,dfn[top[x]],dfn[x],k);
x=Fa[top[x]];
}
if(dep[x]<dep[y])
{
swap(x,y);
}
tree[d].Update(1,dfn[y],dfn[x],k);
}
int main()
{
scanf("%d",&n);
for(int i=1;i<n;i++)
{
scanf("%d %d",&x,&y);
g[x].push_back(y);
g[y].push_back(x);
}
int cnt_node=n;
int last=1;
for(int i=0;i<=20;i++)
{
++cnt_node;
g[last].push_back(cnt_node);
g[cnt_node].push_back(last);
last=cnt_node;
}
scanf("%d",&q);
for(int i=0;i<=20;i++)
{
tree[i].Build(1,1,cnt_node);
}
dfs1(cnt_node,0);
dfs2(cnt_node,cnt_node);
while(q--)
{
scanf("%d",&op);
if(op==1)
{
scanf("%d",&x);
int Res=0;
int Now=0;
while(Now<=20)
{
Res+=tree[Now].Query(1,dfn[x]);
// printf("%d %d ?\n",x,tree[Now].Query(1,dfn[x]));
Now++;
x=Fa[x];
}
printf("%d\n",Res);
}
else
{
scanf("%d %d %d %d",&x,&y,&k,&d);
Update_chain(x,y,k,d);
int lca=Query_lca(x,y);
if(d)
{
tree[d-1].Update(1,dfn[lca],dfn[lca],k);
}
lca=Fa[lca];
while(d)
{
// printf("%d?\n",Now);
d--;
tree[d].Update(1,dfn[lca],dfn[lca],k);
if(d)
{
tree[d-1].Update(1,dfn[lca],dfn[lca],k);
}
lca=Fa[lca];
}
}
}
}
CF1770E Koxia and Tree加强版
只说大体思路
肯定是考虑每条边的贡献
首先转换\(k\)个点选\(m\)个点
选定其中一个连通块的中标记点大小\(S\),统计不合法的情况即可计算每条边经过的次数
然后解决每个点子树标记点大小为\(S\)的概率
注意到大小只会有\(1\)的变动,然后\(f_{x,t}\)为\(x\)点在\(t\)时有标记的概率,转移很简单
Show Code
#include<bits/stdc++.h>
using namespace std;
void read(int &x)
{
x=0;
int f=1;
char s=getchar();
while(s<'0'||s>'9')
{
if(s=='-')
{
f*=-1;
}
s=getchar();
}
while(s>='0'&&s<='9')
{
x=(x*10+(s-'0'));
s=getchar();
}
x*=f;
return;
}
const int MAXN=5e5+5;
const int MOD=998244353;
int fac[MAXN];
int inv_fac[MAXN];
int Pow(int a,int b,int p)
{
int res=1;
int base=a;
while(b)
{
if(b&1)
{
res=((long long)res*base)%p;
}
base=((long long)base*base)%p;
b>>=1;
}
return res;
}
int inv(int a,int p)
{
return Pow(a,p-2,p);
}
int C(int n,int m)
{
if(n<m||m<0)
{
return 0;
}
if(n==m||m==0)
{
return 1;
}
return ((((long long)fac[n]*inv_fac[m])%MOD)*inv_fac[n-m])%MOD;
}
int n,k,m;
int x,y;
pair<int,int>edge[MAXN];
int a[MAXN];
int f[MAXN];
int dep[MAXN];
vector<int>g[MAXN];
int Siz[MAXN];
int dp1[MAXN];
int dp2[MAXN];
int dp3[MAXN];
int P;
void dfs(int x,int f)
{
Siz[x]=a[x];
for(int i=0;i<g[x].size();i++)
{
int v=g[x][i];
if(v==f)
{
continue;
}
dep[v]=dep[x]+1;
dfs(v,x);
Siz[x]+=Siz[v];
}
}
int main()
{
fac[0]=1;
for(int i=1;i<=MAXN-5;i++)
{
fac[i]=((long long)fac[i-1]*i)%MOD;
}
inv_fac[MAXN-5]=inv(fac[MAXN-5],MOD);
for(int i=MAXN-5-1;i>=0;i--)
{
inv_fac[i]=((long long)inv_fac[i+1]*(i+1))%MOD;
}
scanf("%d %d",&n,&k);
m=2;
for(int i=1;i<=k;i++)
{
read(x);
f[x]=1;
a[x]=1;
}
for(int i=1;i<n;i++){
read(x);
read(y);
edge[i].first=x;
edge[i].second=y;
g[x].push_back(y);
g[y].push_back(x);
}
int inv2=(MOD-MOD/2);
dfs(1,0);
for(int i=1;i<n;i++)
{
P=i;
int u=edge[P].first;
int v=edge[P].second;
if(dep[u]<dep[v])
{
swap(u,v);
}
int Lu=f[u];
int Lv=f[v];
f[u]=(((long long)Lu+Lv)*inv2)%MOD;
f[v]=(((long long)Lu+Lv)*inv2)%MOD;
dp1[u]=((long long)Lu*((long long)(1-Lv+MOD)%MOD))%MOD;
dp1[u]=((long long)dp1[u]*inv2)%MOD;
dp2[u]=((long long)Lv*((long long)(1-Lu+MOD)%MOD))%MOD;
dp2[u]=((long long)dp2[u]*inv2)%MOD;
dp3[u]=((long long)1-dp1[u]-dp2[u]+MOD)%MOD;
}
int Res=0;
for(int i=1;i<n;i++)
{
int u=edge[i].first;
int v=edge[i].second;
if(dep[u]<dep[v])
{
swap(u,v);
}
if(Siz[u]>=1)
{
int S=Siz[u]-1;
int Np=((long long)C(S,m)+C(k-S,m))%MOD;
Np=((long long)Np*inv(C(k,m),MOD))%MOD;
Np=((long long)1-Np+MOD)%MOD;
Np=((long long)Np*dp1[u])%MOD;
Res=((long long)Res+Np)%MOD;
}
if(1)
{
int S=Siz[u]+1;
int Np=((long long)C(S,m)+C(k-S,m))%MOD;
Np=((long long)Np*inv(C(k,m),MOD))%MOD;
Np=((long long)1-Np+MOD)%MOD;
Np=((long long)Np*dp2[u])%MOD;
Res=((long long)Res+Np)%MOD;
}
if(1)
{
int S=Siz[u];
int Np=((long long)C(S,m)+C(k-S,m))%MOD;
Np=((long long)Np*inv(C(k,m),MOD))%MOD;
Np=((long long)1-Np+MOD)%MOD;
Np=((long long)Np*dp3[u])%MOD;
Res=((long long)Res+Np)%MOD;
}
}
// Res=((long long)Res*2)%MOD;
printf("%d\n",Res);
}
CSAcademy Round #35 Counting Quests
好像第一步转化就不会/kk,原问题等价于设\(S_i\)为覆盖到\(i\)的区间集合,\(S_i\)互不相同
具体证明好像不会/kk,手玩一下挺对的
然后有个性质若\(S_a=S_b,a<b,\)则不会存在选定的区间相交且不包含/包含于\([a,b]\)
证明考虑假设存在选定的区间\(p\)相交且不包含/包含于\([a,b]\),假设\(a\)不被\(p\)覆盖则\(S_a\)不存在\(p\)而\(S_b\)中存在\(p\),所以与\(S_a=S_b\)矛盾
这其实我们可以将最大的\([a,b]\)使得\(S_a=S_b\)划分为\(1\)段具体来说我们可以以\(i=1\)为起点找最后一个\(S_1=S_j\)的位置,将\([1,j]\)划分为一段,并以\(i=j+1\)为新的起点
假设当前的序列划分为若干段,其中一段区间\([a,b]\)满足\(S_a=S_b\),则\([a,b]\)内部连边并不会使得划分的段有变化
考虑\(S_a=S_b\),说明一定存在一个选定区间横跨\([a,b]\),而对于\(i\in(a,b)\),\(S_a \subseteq S_i\),这就保证了按上述方式划分,内部任意连边不会产生影响
这样做有什么意义呢？考虑合法方案其实就是段数为\(n\)的方案,而这样分段好转移
设\(dp_i\)为长度为\(i\)时的合法方案数,考虑用总方案减去不合法的方案
考虑不合法的就是段数小于\(i\)的方案,考虑枚举\(j<i\)
考虑将\(i\)个数划分为\(j\)段(不考虑段与段之间的连边)为\(f_{i,j}\),这个是可以直接求的
在考虑横贯段的连边,为了保持\(j\)个段,也就是说我们可以把每一段看成一个点连边使得\(S\)各不相同,这部分就是\(dp_j\)
Show Code
#include<bits/stdc++.h>
using namespace std;
int MOD;
int n;
int f[305][305];
int dp[305];
int Pow[100005];
int main()
{
scanf("%d %d",&n,&MOD);
Pow[0]=1;
for(int i=1;i<=100000;i++)
{
Pow[i]=((long long)Pow[i-1]*2)%MOD;
}
f[0][0]=1;
for(int i=0;i<=n;i++)
{
for(int j=0;j<=i;j++)
{
if(!f[i][j])
{
continue;
}
for(int k=1;k<=n;k++)
{
if(i+k>n)
{
continue;
}
f[i+k][j+1]=((long long)f[i+k][j+1]+((long long)Pow[(k-1)*(k-2)/2]*f[i][j])%MOD)%MOD;
}
}
}
dp[0]=1;
for(int i=1;i<=n;i++)
{
dp[i]=Pow[(i*(i+1))/2];
//printf("%d %d?\n",i,dp[i]);
for(int j=1;j<i;j++)
{
dp[i]=((long long)dp[i]-((long long)dp[j]*f[i][j])%MOD+MOD)%MOD;
}
}
printf("%d\n",dp[n]);
}
[ARC126E] Infinite Operations
首先我们肯定可以确定的是操作后序列全相同是贡献最大
然后因为和不变所以平均数作为最后的数,然后贡献就是原数减平均数?
这好像没有考虑操作的过程中额外产生的贡献,至少没法构造一种这样的解
然后我们考虑构造一个\(F(x)=\sum\limits_{i<j}|a_i-a_j|\)
我们考虑一次价值为\(x\)的操作对\(F(x)\)的影响,对于操作的\(i,j\)至少会减少\(2x\)
而如果不存在\(a_i<a_k<a_j\),则一定只会减少\(2x\)
而终止条件为\(F(x)=0\),如果我们要价值最大一定是每次都选择上面的\(i,j\)
最大价值为\(\dfrac{F(x)}{2}\),线段树维护一下即可
Show Code
#include<bits/stdc++.h>
#define ls Tree[p].lc
#define rs Tree[p].rc
using namespace std;
const int MAXN=3e6+5;
const int MOD=998244353;
int cnt_node;
struct Seg{
int date;
int lc,rc;
int num;
}Tree[MAXN*4];
int rt;
void Update(int &p,int l,int r,int x,int op)
{
if(!p)
{
p=++cnt_node;
}
Tree[p].date=((long long)Tree[p].date+op*x+MOD)%MOD;
Tree[p].num+=op;
if(l==r)
{
return;
}
int mid=(l+r)>>1;
if(x<=mid)
{
Update(ls,l,mid,x,op);
}
else
{
Update(rs,mid+1,r,x,op);
}
}
int Query(int p,int l,int r,int ql,int qr)
{
if(ql>qr)
{
return 0;
}
if(!p)
{
return 0;
}
if(l>=ql&&r<=qr)
{
return Tree[p].date;
}
int Res=0;
int mid=(l+r)>>1;
if(ql<=mid)
{
Res=((long long)Res+Query(ls,l,mid,ql,qr))%MOD;
}
if(qr>mid)
{
Res=((long long)Res+Query(rs,mid+1,r,ql,qr))%MOD;
}
return Res;
}
int query(int p,int l,int r,int ql,int qr)
{
if(ql>qr)
{
return 0;
}
if(!p)
{
return 0;
}
if(l>=ql&&r<=qr)
{
return Tree[p].num;
}
int Res=0;
int mid=(l+r)>>1;
if(ql<=mid)
{
Res=((long long)Res+query(ls,l,mid,ql,qr))%MOD;
}
if(qr>mid)
{
Res=((long long)Res+query(rs,mid+1,r,ql,qr))%MOD;
}
return Res;
}
int n,q;
int a[MAXN];
int x,y;
int inv2;
int main()
{
inv2=MOD-MOD/2;
scanf("%d %d",&n,&q);
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
Update(rt,1,1e9,a[i],1);
}
int F=0;
for(int i=1;i<=n;i++)
{
F=((long long)F+((long long)query(rt,1,1e9,1,a[i]-1)*a[i])%MOD)%MOD;
F=((long long)F-Query(rt,1,1e9,1,a[i]-1)+MOD)%MOD;
F=((long long)F-((long long)query(rt,1,1e9,a[i]+1,1e9)*a[i])%MOD+MOD)%MOD;
F=((long long)F+Query(rt,1,1e9,a[i]+1,1e9))%MOD;
}
F=((long long)F*inv2)%MOD;
while(q--)
{
scanf("%d %d",&x,&y);
F=((long long)F-((long long)query(rt,1,1e9,1,a[x]-1)*a[x])%MOD+MOD)%MOD;
F=((long long)F+Query(rt,1,1e9,1,a[x]-1)+MOD)%MOD;
F=((long long)F+((long long)query(rt,1,1e9,a[x]+1,1e9)*a[x])%MOD)%MOD;
F=((long long)F-Query(rt,1,1e9,a[x]+1,1e9)+MOD)%MOD;
Update(rt,1,1e9,a[x],-1);
a[x]=y;
Update(rt,1,1e9,a[x],1);
F=((long long)F+((long long)query(rt,1,1e9,1,a[x]-1)*a[x])%MOD)%MOD;
F=((long long)F-Query(rt,1,1e9,1,a[x]-1)+MOD)%MOD;
F=((long long)F-((long long)query(rt,1,1e9,a[x]+1,1e9)*a[x])%MOD+MOD)%MOD;
F=((long long)F+Query(rt,1,1e9,a[x]+1,1e9))%MOD;
printf("%d\n",(((long long)F*inv2)%MOD));
}
}
[ARC101F] Robots and Exits
又一次觉得自己是智障
很明显的转化,可以计算每个点左右走最近的出口,设距离为\(L_i,R_i\)
注意如果左或右没有出口直接忽略(可以直接确定是从哪个出口出去的)我就是因为这个被卡了
我最开始想的是给\(L_i\)排序,然后设\(dp_i\)为前\(i\)个数的方案
然后枚举一个\(j,R_j<R_i\)然后我们就假设\((i,j)\)从\(L\)走的,即\(dp_i=dp_j+1\)
不过很明显不对,没有考虑\(L\)的顺序,好像吧
然后换个思路我们考虑答案序列的构造
对于\(L_i\le L_j,R_i\ge R_j\),若\(i\)是从\(R\)走的,那\(j\)一定也是从\(R\)走
因此我们同样可以对\(L_i\)排序,考虑\(i\)如果选择,将会同样选择后面\(<R_i\)的\(j\)
这启示我们可以对第一次的选择\(Dp\)
设\(dp_i\)为前\(i\)个且第一次选择\(i\)的方案,这里要求选的\(i\)是单调递增的,即\(dp_i=\sum dp_j+1,R_j<R_I\)
这个式子和我错误的想法是一样的,大概能过?(/yiw)(反转了,好像举不出反例)
好像可以解释,我最开始想的反例是可能是不对的
Show Code
#include<bits/stdc++.h>
#define ls Tree[p].lc
#define rs Tree[p].rc
#define INF 2e9
using namespace std;
const int MAXN=2e5+5;
const int MOD=1e9+7;
int n,m;
int X[MAXN];
int Y[MAXN];
struct node{
int up,down;
bool operator<(const node x)const{
if(down==x.down)
{
return up>x.up;
}
return down<x.down;
}
}a[MAXN];
int dp[MAXN];
struct Seg{
int date;
int lc,rc;
}Tree[MAXN*20];
int rt;
int cnt_node;
void Update(int &p,int l,int r,int x,int k)
{
if(!p)
{
p=++cnt_node;
}
Tree[p].date=((long long)Tree[p].date+k)%MOD;
if(l==r)
{
return;
}
int mid=(l+r)>>1;
if(x<=mid)
{
Update(ls,l,mid,x,k);
}
else
{
Update(rs,mid+1,r,x,k);
}
}
int Query(int p,int l,int r,int ql,int qr)
{
if(ql>qr)
{
return 0;
}
if(!p)
{
return 0;
}
if(l>=ql&&r<=qr)
{
return Tree[p].date;
}
int Res=0;
int mid=(l+r)>>1;
if(ql<=mid)
{
Res=((long long)Res+Query(ls,l,mid,ql,qr))%MOD;
}
if(qr>mid)
{
Res=((long long)Res+Query(rs,mid+1,r,ql,qr))%MOD;
}
return Res;
}
int main()
{
scanf("%d %d",&n,&m);
printf("%d %d?\n",n,m);
for(int i=1;i<=n;i++)
{
scanf("%d",&X[i]);
}
for(int i=1;i<=m;i++)
{
scanf("%d",&Y[i]);
}
sort(X+1,X+1+n);
sort(Y+1,Y+1+m);
int Cnt=0;
for(int i=1;i<=n;i++)
{
int R=lower_bound(Y+1,Y+1+m,X[i])-Y;
int L=R-1;
if(R==m+1)
{
continue;
}
if(L==0)
{
continue;
}
a[++Cnt].up=Y[R]-X[i];
a[Cnt].down=X[i]-Y[L];
}
sort(a+1,a+1+Cnt);
dp[0]=1;
for(int i=1;i<=Cnt;i++)
{
if(a[i].up==a[i-1].up&&a[i].down==a[i-1].down)
{
continue;
}
// printf("%d?\n",i);
dp[i]=((long long)Query(rt,1,1e9,1,a[i].up-1)+1)%MOD;
Update(rt,1,1e9,a[i].up,dp[i]);
}
int Res=0;
// printf("%d??\n",Cnt);
for(int i=0;i<=Cnt;i++)
{
Res=((long long)Res+dp[i])%MOD;
}
printf("%d\n",Res);
}
[AGC049D] Convex Sequence
首先很明显转化成差分的形式后是下凸函数的形式(然后就不会了/kk)
然后肯定有个底,最下面是平台,我们考虑设平台最左端的点为\(i\)
考虑满足题意最小总和的序列,一定是平台为\(0\),左边依次加\(1\),右边全部为\(0\)
考虑在此基础上经过一些操作使得总和为\(m\)且依旧是个凸函数
回想之前一个很经典的题,构造一个总和为\(m\)的递增序列,具体做法就是用在末尾加\(1\)和整体加\(1\)构造
同样,在这道题中,我们可以设计三个操作
首先可以给序列整体加\(1\)
然后可以给\(i\)左边整体加一个等差数列\((k,k-1,k-2...1)\)
和给右边整体加一个等差数列\((1,2,....k)\)
可以证明这样的操作是可以覆盖所有满足条件的序列且合法的
然后注意到一次操作的贡献是\(n\)或\(\dfrac{k(k+1)}{2}\),说明\(k\)的取值只有\(\sqrt{m}\)个
对于固定的\(i\),做有\(\sqrt m\)个物品的完全背包即可
考虑从\((i-1)\rightarrow i\),不难想到左边的物品多了一个,右边少了一个,做一次完全背包删加物品即可
Show Code
#include<bits/stdc++.h>
using namespace std;
const int MAXN=1e5+5;
const int MOD=1e9+7;
int n,m;
int dp[MAXN];
int a[MAXN];
int f[MAXN];
int main()
{
scanf("%d %d",&n,&m);
a[0]=0;
for(int i=1;i<=n;i++)
{
a[i]=a[i-1]+i;
if(a[i]>m)
{
a[i]=m+1;
}
}
dp[0]=1;
for(int i=1;i<n;i++)
{
for(int j=a[i];j<=m;j++)
{
dp[j]=((long long)dp[j]+dp[j-a[i]])%MOD;
}
}
for(int i=n;i<=m;i++)
{
dp[i]=((long long)dp[i]+dp[i-n])%MOD;
}
int Res=dp[m];
int Rs=m;
for(int i=2;i<=n;i++)
{
Rs-=(i-1);
if(Rs<0)
{
break;
}
int Del=a[n-i+1];
for(int j=m;j>=Del;j--)
{
dp[j]=((long long)dp[j]-dp[j-Del]+MOD)%MOD;
}
int Add=a[i-1];
for(int j=Add;j<=m;j++)
{
dp[j]=((long long)dp[j]+dp[j-Add])%MOD;
}
Res=((long long)Res+dp[Rs])%MOD;
}
printf("%d\n",Res);
}
CF1481F AB Tree
我是zz
我们可以先把整棵树按层划分
然后很明显我们每一层尽量是把颜色涂满为好
如果能涂满就一定是最小答案,这一部分是背包,可以用\(bitset\)优化
然后如果不能涂满,那一定有一层是\(a,b\)都有
对于这一层,如果一个节点有不同会将其子树内的答案全\(+1\),所以我们尽量找叶子
所以我们会让一层的非叶子节点一样,叶子节点无所谓
假设\(x,y\)分别表示目前\(a,b\)数量中大的那个和小的,\(l\)表示当前层非叶子数
注意\(l\le\dfrac{x+y}{2}\le x\)(\(l\)下面还有儿子)
如果\(x,y\)都填不满当前层时候，我们先用\(x\)填非叶子在用\(y\)
很明显是合法的,且\(x\)会被用完,因此只会出现一次
因此答案最大值为深度\(+1\)
Show Code
#include<bits/stdc++.h>
using namespace std;
const int MAXN=1e5+5;
int n,m;
int x,y;
vector<int>g[MAXN];
int Dep[MAXN];
int Leaf[MAXN];
vector<int>V[MAXN];
void dfs(int x)
{
for(int i=0;i<g[x].size();i++)
{
int v=g[x][i];
Dep[v]=Dep[x]+1;
dfs(v);
}
}
bitset<MAXN>Dp,Las;
int C[MAXN];
int Rec[MAXN];
int Ans[MAXN];
int Vis[MAXN];
int Cntl[MAXN];
void print(int x)
{
if(x==m)
{
return;
}
int Po=Rec[x];
Vis[Po]=1;
print(x+C[Po]);
}
int main()
{
//freopen("date.in","r",stdin);
//freopen("date.out","w",stdout);
scanf("%d %d",&n,&m);
for(int i=2;i<=n;i++)
{
scanf("%d",&x);
g[x].push_back(i);
Leaf[x]=1;
}
Dep[1]=1;
dfs(1);
int D=0;
for(int i=1;i<=n;i++)
{
D=max(D,Dep[i]);
C[Dep[i]]++;
V[Dep[i]].push_back(i);
Leaf[i]=Leaf[i]^1;
if(!Leaf[i])
{
Cntl[Dep[i]]++;
}
}
Dp.reset();
Dp.set(m);
for(int i=1;i<=D;i++)
{
Las=(Dp|(Dp>>C[i]));
Dp=(Las^Dp);
for(int j=Dp._Find_first();j!=Dp.size();j=Dp._Find_next(j))
{
Rec[j]=i;
}
Dp=Las;
}
if(Dp[0]==1)
{
printf("%d\n",D);
print(0);
for(int i=1;i<=D;i++)
{
for(int j=0;j<V[i].size();j++)
{
Ans[V[i][j]]=Vis[i];
}
}
for(int i=1;i<=n;i++)
{
if(Ans[i])
{
printf("a");
}
else{
printf("b");
}
}
}
else
{
printf("%d\n",D+1);
int Key;
int Maxi=0;
for(int i=1;i<=D;i++)
{
if((C[i]-Cntl[i])>=Maxi)
{
Maxi=(C[i]-Cntl[i]);
Key=i;
}
}
for(int i=1;i<=D;i++)
{
if(i==Key)
{
continue;
}
if(m>=C[i])
{
m-=C[i];
for(int j=0;j<V[i].size();j++)
{
Ans[V[i][j]]=1;
}
}
}
if(m>=Cntl[Key])
{
for(int j=0;j<V[Key].size();j++)
{
if(!Leaf[V[Key][j]])
{
m--;
Ans[V[Key][j]]=1;
}
}
for(int j=0;j<V[Key].size();j++)
{
if(!m)
{
break;
}
if(Leaf[V[Key][j]])
{
m--;
Ans[V[Key][j]]=1;
}
}
}
else
{
for(int j=0;j<V[Key].size();j++)
{
if(!m)
{
break;
}
if(Leaf[V[Key][j]])
{
m--;
Ans[V[Key][j]]=1;
}
}
}
for(int i=1;i<=n;i++)
{
if(Ans[i])
{
printf("a");
}
else{
printf("b");
}
}
}
}
ABC295 Ex E or m
先考虑全是\(?\)的情况
不难想到会先一行一行地做,然后状压当前从最上面引下来连续\(1\)的状态
然后考虑转移,这明显是一个超集和,然后\(FWT\)?
其实这个也可以用高维前缀和,并且有个问题,就是可以从当前行的左边引出来\(1\)
这里我们先明确一下\(Dp\)的含义
当前到\(i,j,Dp_{S}\)表示前\(i\)行,我们做前缀和到了第\(j\)维时的方案
考虑那种特殊的,相当于只会多一种情况,也就是\(j\)这个位置凭空多出来,只需处理\(S\)中第\(j\)位为\(0\)的情况就行
然后我们考虑强制填\(1,0\)的情况
由于是超集和,填\(1\)相当于不动,填\(0\)则累加\(1,0\)
Show Code
#include<bits/stdc++.h>
using namespace std;
const int MOD=998244353;
int n,m;
char s[105][105];
int dp[(1<<18)+5];
int Tmp[(1<<18)+5];
int Wk[(1<<18)+5];
int main()
{
//freopen("date.in","r",stdin);
scanf("%d %d",&n,&m);
for(int i=1;i<=n;i++)
{
scanf("%s",s[i]+1);
}
dp[(1<<m)-1]=1;
for(int i=1;i<=n;i++)
{
for(int S=0;S<(1<<m);S++)
{
Tmp[S]=dp[S];
}
for(int j=1;j<=m;j++)
{
for(int S=0;S<(1<<m);S++)
{
Wk[S]=0;
}
if(s[i][j]!='1')
{
for(int S=0;S<(1<<m);S++)
{
if((S>>(j-1))&1)
{
Wk[(S^(1<<(j-1)))]=((long long)Wk[(S^(1<<(j-1)))]+dp[S])%MOD;
}
else
{
Wk[S]=((long long)Wk[S]+dp[S])%MOD;
}
}
}
if(s[i][j]!='0')
{
for(int S=0;S<(1<<m);S++)
{
if((S>>(j-1))&1)
{
Wk[S]=((long long)Wk[S]+dp[S])%MOD;
}
}
}
bool flag=1;
for(int k=1;k<=j;k++)
{
if(s[i][k]=='0')
{
flag=0;
break;
}
}
if(flag)
{
for(int S=0;S<(1<<m);S++)
{
if((S>>(j-1))&1)
{
continue;
}
Wk[S]=((long long)Wk[S]+Tmp[S])%MOD;
}
}
for(int S=0;S<(1<<m);S++)
{
dp[S]=Wk[S];
///printf("%d %d\n",S,dp[S]);
}
}
}
int Ans=0;
for(int i=0;i<(1<<m);i++)
{
Ans=((long long)Ans+dp[i])%MOD;
}
printf("%d",Ans);
}
[LNOI2022] 盒
先考虑固定\(B\)
直接考虑\(i\rightarrow i+1\)会经过多少次,对于\([1,i]\)这个整体,我们到外界的连边只有\(i\rightarrow i+1\),所以前缀的差值一定会经过他
因此其答案为\(\sum\limits_{i=1}^n|Suma_i-Sumb_i|w_i\)
根据这个我们可以搞一个\(O(nS)\)的\(dp\),\(dp_{i,S}\)表示前\(i\)个当前前缀和为\(S\)的答案
\(dp_{i,S}=|Suma_i-S|Sw_i+Sum_{i-1,S}\)
我们考虑枚举每个\(Sumb_i\)
即答案为\(\sum\limits_{i=1}^nw_i\sum\limits_{j=0}^S|Suma_i-j|Cnt(i,j)\)
其中\(Cnt(i,j)\)表示\(Sumb_i=j\)的方案
考虑有\(n\)个盒子,可以在里面放任意球
则原问题等价与在\([1,i]\)里放\(j\)球,在\([i+1,n]\)里方\(S-j\)球
则\(Cnt(i,j)=\binom{i+j-1}{j}\binom{n+S-i-j}{S-j}\)
即\(\sum\limits_{i=1}^nw_i\sum\limits_{j=0}^S|Suma_i-j|\binom{i+j-1}{j}\binom{n+S-i-j-1}{S-j}\)
拆绝对值
\(\sum\limits_{i=1}^nw_i\sum\limits_{j=0}^{Suma_i}(Suma_i-j)\binom{i+j-1}{i-1}\binom{n+S-i-j-1}{n-i-1}+\sum\limits_{j=Suma_i+1}^{S}(j-Suma_i)\binom{i+j-1}{i-1}\binom{n+S-i-j-1}{n-i-1}\)
观察一下式子,不妨再把括号拆开
即\(\sum\limits_{i=1}^nw_i[Suma_i(\sum\limits_{j=0}^{Suma_i}\binom{i+j-1}{i-1}\binom{n+S-i-j-1}{n-i-1}-\sum\limits_{j=Suma_i+1}^{S}\binom{i+j-1}{i-1}\binom{n+S-i-j-1}{n-i-1})\)
\(+\sum\limits_{j=Suma_i+1}^{S}j\binom{i+j-1}{i-1}\binom{n+S-i-j-1}{n-i-1}-\sum\limits_{j=0}^{Suma_i}j\binom{i+j-1}{i-1}\binom{n+S-i-j-1}{n-i-1}]\)
这里我们设\(f(n,S,i,k)=\sum\limits_{j=0}^{k}\binom{i+j-1}{i-1}\binom{n+S-i-j-1}{n-i-1}\),很明显上式可以容斥
注意到\(j\binom{i+j-1}{j}=i\binom{i+j-1}{i}\)
则\(\sum\limits_{j=0}^{k}j\binom{i+j-1}{j}\binom{n+S-i-j-1}{n-i-1}=i\sum\limits_{j=0}^{k}\binom{i+j-1}{j-1}\binom{n+S-i-j-1}{n-i-1}=i\sum\limits_{j=0}^{k-1}\binom{i+j}{j}\binom{n+S-i-j-2}{n-i-1}\)
\(=i\sum\limits_{j=0}^{k-1}\binom{(i+1)+j-1}{j}\binom{n+S-(i+1)-j-1}{n-(i+1)}=i\sum\limits_{j=0}^{k-1}\binom{(i+1)+j-1}{j}\binom{(n+1)+(S-1)-(i+1)-j-1}{(S-1)-j}=if(n+1,S-1,i+1,k-1)\)
因此我们只需计算\(f(n,S,i,S),f(n,S,i,Suma_i),f(n+1,S-1,i+1,S-1),f(n+1,S-1,i+1,Suma_i-1)\)即可
移动\(i\)的规律不好找,我们要对\(f\)做一些变形
我们认为\(f\)的求和相当于枚举前\(i\)个盒子球的个数,其中它的数量不超过\(k\)
换个思路,这里我们可以枚举第\(k+1\)的球放的位置\(j\),这时强制\(j\)放,\([1,j],[j,n]\)分别放\(k,S-k-1\)个球
即\(f(n,S,i,k)=\sum\limits_{j=i+1}^n\binom{j-1+k}{j-1}\binom{n-j+S-k-1}{n-j}\)
回到\(f\)的定义\(f(n,S,i,k)=\sum\limits_{j=0}^{k}\binom{i+j-1}{i-1}\binom{n+S-i-j-1}{n-i-1}\)
在实际过程中,\(Suma_i\)是递增的所以我们可以移利用上面的式子\(i,k\),移的次数也是线性的
Show Code
#include<bits/stdc++.h>
using namespace std;
const int MOD=998244353;
const int MAXN=4e6+5;
int Pow(int a,int b,int p)
{
int res=1;
int base=a;
while(b)
{
if(b&1)
{
res=((long long)res*base)%p;
}
base=((long long)base*base)%p;
b>>=1;
}
return res;
}
int inv(int a,int p)
{
return Pow(a,p-2,p);
}
int inv_fac[MAXN];
int fac[MAXN];
int C(int n,int m)
{
if(n<m||m<0)
{
return 0;
}
if(n==m||m==0)
{
return 1;
}
return ((((long long)fac[n]*inv_fac[m])%MOD)*inv_fac[n-m])%MOD;
}
struct Node{
int n,S,i,k;
int Ans;
void To(int I,int K)
{
while(i<I)
{
i++;
int Lp=((long long)C(i-1+k,i-1)*C(n-i+S-k-1,n-i))%MOD;
Ans=((long long)Ans-Lp+MOD)%MOD;
}
while(k<K)
{
k++;
int Lp=((long long)C(i+k-1,i-1)*C(n+S-i-k-1,n-i-1))%MOD;
Ans=((long long)Ans+Lp+MOD)%MOD;
}
return;
}
}A1,A2,A3,A4;
int T;
int n;
int a[MAXN];
int Suma[MAXN];
int w[MAXN];
int main()
{
fac[0]=1;
for(int i=1;i<=MAXN-5;i++)
{
fac[i]=((long long)fac[i-1]*i)%MOD;
}
inv_fac[MAXN-5]=inv(fac[MAXN-5],MOD);
for(int i=MAXN-5-1;i>=1;i--)
{
inv_fac[i]=((long long)inv_fac[i+1]*(i+1))%MOD;
}
scanf("%d",&T);
while(T--)
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
Suma[i]=Suma[i-1]+a[i];
}
for(int i=1;i<n;i++)
{
scanf("%d",&w[i]);
}
A1.n=n;
A1.S=Suma[n];
A1.i=0;
A1.k=-1;
A1.Ans=0;
A1.To(1,Suma[n]);
A2.n=n;
A2.S=Suma[n];
A2.i=0;
A2.k=-1;
A2.Ans=0;
A2.To(1,0);
A3.n=n+1;
A3.S=Suma[n]-1;
A3.i=0;
A3.k=-1;
A3.Ans=0;
A3.To(1,Suma[n]-1);
A4.n=n+1;
A4.S=Suma[n]-1;
A4.i=0;
A4.k=-1;
A4.Ans=0;
A4.To(1,-1);
int Ans=0;
for(int i=1;i<n;i++)
{
// printf("%d %d %d %d??\n",A1.Ans,A2.Ans,A3.Ans,A4.Ans);
A1.To(i,Suma[n]);
A2.To(i,Suma[i]);
A3.To(i+1,Suma[n]-1);
A4.To(i+1,Suma[i]-1);
int Po=0;
Po=((long long)2*A2.Ans)%MOD;
Po=((long long)Po-A1.Ans+MOD)%MOD;
Po=((long long)Po*Suma[i])%MOD;
int Qo=0;
Qo=((long long)2*A4.Ans)%MOD;
Qo=(MOD-Qo);
Qo=((long long)Qo+A3.Ans)%MOD;
Qo=((long long)Qo*i)%MOD;
Po=((long long)Po+Qo)%MOD;
Po=((long long)Po*w[i])%MOD;
Ans=((long long)Ans+Po)%MOD;
}
printf("%d\n",Ans);
}
}
CF1510J Japanese Game
首先这是个构造
首先考虑一下知道\(P\)求那些一定被染色
我们肯定是把其中的一个连通块左边的全部移到左边,右边额全部移到右边,之后看这个连通块左右移后一定经过的点
我最开始是考虑最左边的,假设是\([L_1,R_1]\)可以还原出他的\(Len\)为\(R_1\),然后他能自由移动的范围是\([1,R_1+Len]\),然后根据这个往后推就行了
不过你每个连同块的长度太长了,能只有操作的空间过小会更容易引冲突
所以我们会尽量固定每个连通块能自由活动的区间
观察样例,\(BRBRBR\)这样交错的能缩小活动的范围且不会贡献一定能染色
手玩一下会发现你每个连通块的活动范围不会大于自身程度加\(3\)
并且这个自由活动的范围是公用的(一直没注意到)
所以我们直接枚举额外的活动范围,把它放在末尾,然后再用\(BR\)填空即可
Show Code
#include<bits/stdc++.h>
using namespace std;
const int MAXN=5e6+5;
int n;
string s;
struct Site{
int l,r;
int Pl;
}a[MAXN];
string S;
int Cnt=0;
int Cp=0;
int Last=0;
int check(int mid)
{
Last=0;
for(int i=1;i<=Cnt;i++)
{
int Len=(a[i].l-a[i-1].r-2-mid);
if(i==Cnt)
{
Len+=2;
}
if(Len<0)
{
return 0;
}
if(Len>0)
{
if(mid==0||Len==1)
{
return 0;
}
if(Len&1)
{
if(mid<=1)
{
return 0;
}
int op=1;
for(int j=Last+1;j-Last<=(Len);j++)
{
if(op)
{
S[j]='B';
}
else
{
S[j]='R';
}
op^=1;
}
Last+=Len;
S[Last-1]='B';
S[Last]='R';
}
else
{
int op=1;
for(int j=Last+1;j-Last<=(Len);j++)
{
if(op)
{
S[j]='B';
}
else
{
S[j]='R';
}
op^=1;
}
Last+=Len;
}
}
if(i==Cnt)
{
continue;
}
for(int j=Last+1;j-Last<=(a[i].r-a[i].l+1+mid);j++)
{
S[j]='B';
}
Last=Last+(a[i].r-a[i].l+1+mid);
Last++;
S[Last]='R';
}
return 1;
}
int main()
{
//freopen("barca.in","r",stdin);
//freopen("barca.out","w",stdout);
cin>>s;
n=s.size();
int R=0;
for(int i=0;i<s.size();i++)
{
if(s[i]=='#')
{
if(R==0)
{
++Cnt;
a[Cnt].l=i+1;
R=1;
}
a[Cnt].r=i+1;
}
else
{
R=0;
}
}
int Len=3;
a[0].l=-1;
a[0].r=-1;
for(int i=2;i<=Cnt;i++)
{
Len=min(Len,a[i].l-a[i-1].r);
}
Len=min(Len,n-a[Cnt].r);
a[++Cnt].l=n;
a[Cnt].r=n;
for(int i=0;i<=Len;i++)
{
S.resize(n+1,'R');
if(check(i))
{
Cnt=0;
R=0;
for(int j=1;j<=n;j++)
{
if(S[j]=='B')
{
if(R==0)
{
++Cnt;
a[Cnt].l=j;
R=1;
}
a[Cnt].r=j;
}
else
{
R=0;
}
}
printf("%d\n",Cnt);
for(int j=1;j<=Cnt;j++)
{
printf("%d ",a[j].r-a[j].l+1);
}
return 0;
}
}
printf("-1\n");
}
CF794G Replace All
一个有意思的题
首先不难想到我们会将首尾的\(A,B\)先提前消掉,这样会剩首尾不同
但这就又出现了特殊情况,\(A=B\)的情况,我们可以算,很明显\(S,T\)任取,答案为\((\sum\limits_{i=1}^n(2^i))^2\)
剔除这种情况,假设\(|S|>|T|\)我们不难发现\(T\)是\(S\)的前缀和后缀
进一步的,\(S-T\)也会匹配到\(S\),或\(T\),不过\(|T|\),\(|S-T|\)一定是前缀的关系,具体要看谁大
模拟这个过程,发现其实他是类似于更相减损术,一直到减到呈倍数关系,这时小的那个很明显是循环节
我们设循环节为\(C\),则\(|C|=\gcd(|A|,|B|)\)
整理一下,如果\(A\not=B\),则\(S,T\)的选择和字符的位置无关
假设已经钦定\(?\)的选择
我们设\(a_d,a_f,b_d,b_f\)分别表示其数量
显然有\((a_d-a_f)|S|=(b_f-b_d)|T|\),不妨直接有\(a,b\)替换
\(|S|,|T|\)直接有\(|C|k_s,|C|k_s\)来替换,于是\(ak_s=bk_t\),\(\gcd(k_s,k_t)=1\)
注意一下,\(a,b\)要共号,或者\(a=0,b=0\)
再分讨一下
\(a,b=0\),很明显,\(k_s,k_b\)没限制,我们直接枚举\(a,b\)长度,然后有确定\(|C|\)的长度
即\(\sum\limits_{i=1}^n\sum\limits_{j=1}^n2^{\gcd(i,j)}\)
\(a,b\)不为\(0\),这里要\(a,b\)同时约一个\(\gcd(a,b)\)
注意\(a=k_t,b=k_s\),由此我们确定\(C\)就能同时推\(S,T\)
即\(\sum\limits_{i=1}^{\frac{n}{max(a,b)}}2^i\)
再把\(?\)考虑进去,首先我们知道这和顺序没有关系所以我们可以枚举个数设\(f(a,b)\)为上述的答案
设\(X\)为\(A\)串中\(?\)的数量,\(Y\)同理
即\(\sum\limits_{i=0}^X\sum\limits_{j=0}^Y(f(a+i-j,b-(X-i)+(Y-j)))\binom{X}{i}\binom{Y}{j}\)
注意到\(i-j\)是定值\(k\)
即\(\sum\limits_{k=-Y}^{X}f(a+k,b-X+Y-k)\sum\limits_{j=0}^{Y}\binom{X}{k+j}\binom{Y}{Y-j}\)
注意一下\(\sum\limits_{j=0}^Y\binom{X}{k+j}\binom{Y}{Y-j}\)
这个就相当于我们在\(X\)个中选\(k\)个再选\(j\)个,再在\(Y\)中选\(Y-j\)个
等价于\(\binom{X+Y}{Y+k}\)
然后最后还有把那个\(A=B\)的情况考虑进去,注意要把我们\(a,b=0\)的情况考虑进去
Show Code
#include<bits/stdc++.h>
using namespace std;
const int MOD=1e9+7;
const int MAXN=6e5+5;
int Abs(int x)
{
return x>0?x:-x;
}
int gcd(int a,int b)
{
if(b==0)
{
return a;
}
return gcd(b,a%b);
}
int prime[MAXN];
int cnt_prime;
int u[MAXN];
int vis[MAXN];
string A,B;
void Euler()
{
vis[1]=vis[0]=1;
u[1]=1;
for(int i=2;i<=MAXN-5;i++)
{
if(!vis[i])
{
prime[++cnt_prime]=i;
u[i]=-1;
}
for(int j=1;j<=cnt_prime&&prime[j]*i<=MAXN-5;j++)
{
vis[i*prime[j]]=1;
if(i%prime[j]==0)
{
u[i*prime[j]]=0;
break;
}
u[i*prime[j]]=u[i]*u[prime[j]];
}
}
}
int n;
int Pow(int a,int b,int p)
{
int res=1;
int base=a;
while(b)
{
if(b&1)
{
res=((long long)res*base)%p;
}
base=((long long)base*base)%p;
b>>=1;
}
return res;
}
int inv(int a,int p)
{
return Pow(a,p-2,p);
}
int fac[MAXN];
int inv_fac[MAXN];
int C(int n,int m)
{
if(n<m||m<0)
{
return 0;
}
if(n==m||m==0)
{
return 1;
}
int P=fac[n];
P=((long long)P*inv_fac[m])%MOD;
P=((long long)P*inv_fac[n-m])%MOD;
return P;
}
int P2[MAXN];
int P;
int f(int a,int b)
{
if((long long)a*b<0)
{
return 0;
}
if((long long)a*b==0)
{
if(a||b)
{
return 0;
}
return P;
}
int Lk=gcd(a,b);
a/=Lk;
b/=Lk;
a=Abs(a);
b=Abs(b);
int Res=0;
int Mp=(n/max(a,b));
return P2[Mp];}
int main()
{
//freopen("date.in","r",stdin);
//freopen("date.out","w",stdout);
fac[0]=1;
for(int i=1;i<=MAXN-5;i++)
{
fac[i]=((long long)fac[i-1]*i)%MOD;
}
inv_fac[MAXN-5]=inv(fac[MAXN-5],MOD);
for(int i=MAXN-5-1;i>=1;i--)
{
inv_fac[i]=((long long)inv_fac[i+1]*(i+1))%MOD;
}
for(int i=1;i<=MAXN-5;i++)
{
P2[i]=((long long)P2[i-1]+Pow(2,i,MOD))%MOD;
}
Euler();
cin>>A;
cin>>B;
scanf("%d",&n);
P=0;
for(int i=1;i<=n;i++)
{
int Rd=0;
for(int j=1;i*j<=n;j++)
{
int Po=u[j];
Po=((long long)Po*((n/i)/j))%MOD;
Po=((long long)Po*((n/i)/j))%MOD;
Rd=((long long)Rd+Po)%MOD;
}
Rd=((long long)Rd*Pow(2,i,MOD))%MOD;
//printf("%d????\n",Rd);
P=((long long)P+Rd)%MOD;
}
int a=0;
int b=0;
int X=0;
int Y=0;
for(int i=0;i<A.size();i++)
{
if(A[i]=='A')
{
a++;
}
else if(A[i]=='B')
{
b--;
}
else
{
X++;
}
}
for(int i=0;i<B.size();i++)
{
if(B[i]=='A')
{
a--;
}
else if(B[i]=='B')
{
b++;
}
else
{
Y++;
}
}
int Res=0;
for(int k=-Y;k<=X;k++)
{
Res=((long long)Res+((long long)f(a+k,b+k+Y-X)*C(X+Y,k+Y))%MOD)%MOD;
}
// printf("%d %d???\n",Res,P);
if(A.size()==B.size())
{
int Tot=0;
bool f=1;
for(int i=0;i<A.size();i++)
{
if(A[i]=='?'&&B[i]=='?')
{
Tot++;
}
else if(A[i]!='?'&&B[i]!='?')
{
if(A[i]!=B[i])
{
f=0;
break;
}
}
}
if(f)
{
int O=(((long long)P2[n]*P2[n])%MOD-P+MOD)%MOD;
O=((long long)O*Pow(2,Tot,MOD))%MOD;
Res=((long long)Res+O)%MOD;
}
}
printf("%d",Res);
}
[CEOI2020] 星际迷航
我们先考虑一棵树的结果
考虑维护以每个点为根是否必胜,这个是可以用换根\(Dp\)做
\(Dp=0\)为必败点,\(=1\)为必胜点
再考虑\(D=1\)怎么办
我们考虑\(i\)这个点连到必胜点,很明显\(i\)的胜负是不会变的,连必败点,如果是\(i\)自己是必败点他就会变必胜
而\(i\)的变化可能会引起根节点的变化,我们记录\(K_i\)为\(i\)为根子树内会引起变化点的数量,同样是换根
如果我们统计一下标号为\(1\)的树的必败点和必胜点数量\(f_0,f_1\)
那如果\(Dp_1=1\)答案即为\(f_0(n-K_1)+f_1n\),否则为\(f_0K_1\)
注意到跳到另一棵树后根会变,所以记录全部的\(K\)是有必要的
同样\(f_0,f_1\)为处理了后\(D\)棵树后的数量
不难想到从当前树连\(f_0\)为根本身就是败点接胜点和接败不变加胜接败变
\(f1\)同理,这个矩阵维护即可
Show Code
#include<bits/stdc++.h>
using namespace std;
const int MAXN=1e5+5;
const int MOD=1e9+7;
int n;
int x,y;
long long D;
vector<int>g[MAXN];
struct Martix{
int val[2][2];
int n,m;
void clear()
{
memset(val,0,sizeof(val));
}
void init()
{
clear();
for(int i=0;i<n;i++)
{
val[i][i]=1;
}
}
Martix operator*(const Martix x)const{
Martix Res;
Res.clear();
Res.n=n;
Res.m=x.m;
for(int k=0;k<m;k++)
{
for(int i=0;i<n;i++)
{
for(int j=0;j<x.m;j++)
{
Res.val[i][j]=((long long)Res.val[i][j]+((long long)val[i][k]*x.val[k][j])%MOD)%MOD;
}
}
}
return Res;
}
}A,B;
Martix Pw(Martix a,long long b)
{
Martix res;
res.n=a.n;
res.m=a.m;
res.init();
Martix Base=a;
while(b)
{
if(b&1)
{
res=(res*Base);
}
Base=(Base*Base);
b>>=1;
}
return res;
}
int Pow(int a,long long b,int p)
{
int res=1;
int base=a;
while(b)
{
if(b&1)
{
res=((long long)res*base)%p;
}
base=((long long)base*base)%p;
b>>=1;
}
return res;
}
int dp1[MAXN];
int dp2[MAXN];
int Fa[MAXN];
int King[MAXN];
int Queen[MAXN];
void dfs1(int x,int f)
{
Fa[x]=f;
for(int i=0;i<g[x].size();i++)
{
int v=g[x][i];
if(v==f)
{
continue;
}
dfs1(v,x);
}
int ct=0;
int Key;
for(int i=0;i<g[x].size();i++)
{
int v=g[x][i];
if(v==f)
{
continue;
}
if(!dp1[v])
{
ct++;
Key=v;
dp1[x]=1;
}
}
if(dp1[x])
{
for(int i=0;i<g[x].size();i++)
{
int v=g[x][i];
if(v==f)
{
continue;
}
if(ct==1&&Key==v)
{
King[x]+=(King[v]);
}
}
}
else
{
for(int i=0;i<g[x].size();i++)
{
int v=g[x][i];
if(v==f)
{
continue;
}
King[x]+=(King[v]);
}
}
if(!dp1[x])
{
King[x]++;
}
}
set<int>S;
void dfs2(int x,int f)
{
S.clear();
for(int i=0;i<g[x].size();i++)
{
int v=g[x][i];
if(v==f)
{
continue;
}
if(!dp1[v])
{
S.insert(v);
}
}
if(!dp2[x])
{
S.insert(x);
}
int Rp=0;
for(int i=0;i<g[x].size();i++)
{
int v=g[x][i];
if(v==f)
{
continue;
}
if(dp1[v])
{
Rp+=King[v];
}
}
if(dp2[x])
{
Rp+=Queen[x];
}
for(int i=0;i<g[x].size();i++)
{
int v=g[x][i];
if(v==f)
{
continue;
}
if(!dp1[v])
{
S.erase(v);
}
if((S.size()))
{
dp2[v]=1;
if(S.size()==1)
{
int P=(*(S.begin()));
if(P==x)
{
Queen[v]=Queen[x];
}
else
{
Queen[v]=King[P];
}
}
else
{
Queen[v]=0;
}
}
else
{
dp2[v]=0;
int Pop=Rp;
if(dp1[v])
{
Pop-=King[v];
}
Queen[v]=Pop;
}
if(!dp2[v])
{
Queen[v]++;
}
if(!dp1[v])
{
S.insert(v);
}
}
for(int i=0;i<g[x].size();i++)
{
int v=g[x][i];
if(v==f)
{
continue;
}
dfs2(v,x);
}
}
int Dp[MAXN];
int aL[MAXN];
int main()
{
//freopen("input22.txt","r",stdin);
//freopen("tree.out","w",stdout);
dp2[1]=1;
scanf("%d %lld",&n,&D);
for(int i=1;i<n;i++)
{
scanf("%d %d",&x,&y);
g[x].push_back(y);
g[y].push_back(x);
}
dfs1(1,0);
dfs2(1,0);
for(int i=1;i<=n;i++)
{
int ct=0;
int Key;
for(int j=0;j<g[i].size();j++)
{
int v=g[i][j];
if(v==Fa[i])
{
continue;
}
if(!dp1[v])
{
ct++;
Key=v;
Dp[i]=1;
}
}
if(!dp2[i])
{
Key=Fa[i];
ct++;
Dp[i]=1;
}
if(Dp[i]==1)
{
for(int j=0;j<g[i].size();j++)
{
int v=g[i][j];
if(v==Fa[i])
{
continue;
}
if(v==Key&&ct==1)
{
aL[i]=King[v];
}
}
if(Key==Fa[i]&&ct==1)
{
aL[i]=Queen[i];
}
}
else
{
for(int j=0;j<g[i].size();j++)
{
int v=g[i][j];
if(v==Fa[i])
{
continue;
}
aL[i]+=King[v];
}
aL[i]+=Queen[i];
}
if(!Dp[i])
{
aL[i]++;
}
}
for(int i=1;i<=n;i++)
{
dp2[i]=Dp[i];
Queen[i]=aL[i];
}
int f0=0;
int f1=0;
for(int i=1;i<=n;i++)
{
if(dp2[i])
{
f1++;
}
else
{
f0++;
}
}
//printf("%d %d??\n",f0,f1);
A.n=1;
A.m=2;
A.clear();
A.val[0][0]=f0;
A.val[0][1]=f1;
B.n=2;
B.m=2;
B.clear();
for(int i=1;i<=n;i++)
{
if(dp2[i]==1)
{
B.val[0][0]=((long long)B.val[0][0]+Queen[i])%MOD;
}
else
{
B.val[0][0]=((long long)B.val[0][0]+(n-Queen[i]))%MOD;
}
}
for(int i=1;i<=n;i++)
{
if(dp2[i]==0)
{
B.val[1][0]=((long long)B.val[1][0]+n)%MOD;
}
}
for(int i=1;i<=n;i++)
{
if(dp2[i]==0)
{
B.val[0][1]=((long long)B.val[0][1]+Queen[i])%MOD;
}
else
{
B.val[0][1]=((long long)B.val[0][1]+(n-Queen[i]))%MOD;
}
}
for(int i=1;i<=n;i++)
{
if(dp2[i]==1)
{
B.val[1][1]=((long long)B.val[1][1]+n)%MOD;
}
}
B=Pw(B,D-1);
A=A*B;
if(dp1[1])
{
int Po=(n-Queen[1]);
Po=((long long)Po*A.val[0][0])%MOD;
int Qo=(n);
Qo=((long long)Qo*A.val[0][1])%MOD;
Po=((long long)Po+Qo)%MOD;
printf("%d",Po);
}
else
{
int Po=(Queen[1]);
Po=((long long)Po*A.val[0][0])%MOD;
printf("%d\n",Po);
}
}
[THUWC2017]随机二分图
首先转化一下题意
这里的期望相当于是每个图出现的概率\(\times\)图上完美匹配的数量
当然我们可以将其转化为每个匹配出现的概率之和,这里其他不是匹配的边是无影响的
然后这个其实就是每条边出现概率的乘积
我们先考虑只有\(t=0\)的情况
不难想到我们设\(dp_{i,S}\)表示左部选了前\(i\)个点,右部选了\(S\)这个点集是所有完美匹配的概率乘积之和
很明显\(dp_{i+1,S|j}=\sum dp_{i,S}P_{i,j}\)
注意这里是不会算重的,因为已经钦定了顺序
考虑\(t>0\)的情况
对于\(t=1\),如果这两条边只有一条在匹配中,那我们可以直接把两条边独立地\(1/2\)的概率相连
如果都在匹配中,那原来的方法只会有\(1/4\)的贡献,但实际上是\(1/2\),我们要再加一条一次性连两条边的并有\(1/4\)的贡献
注意这里两条边的左部的点变化是不连续的,所以左部同样需要状压,这里就又涉及到转移顺序的问题,这里肯定不能随便连边,所以这里我们每次强制连\(S\)的最小位
解释一下为什么连两条边的操作是\(1/4\)且是直接加上去的,我们考虑\(S\)去除两条边的点,这里有两种途径,一是一条边一条边地走,还有就是直接连两条,这两个互不干扰
\(t=2\)的情况类似
Show Code
#include<bits/stdc++.h>
using namespace std;
const int MOD=1e9+7;
int Pow(int a,int b,int p)
{
int res=1;
int base=a;
while(b)
{
if(b&1)
{
res=((long long)res*base)%p;
}
base=((long long)base*base)%p;
b>>=1;
}
return res;
}
int inv(int a,int p)
{
return Pow(a,p-2,p);
}
int inv2,inv4;
int n,m,q;
int S[1005];
int P[1005];
map<int,int>dp;
int t,a,b,x,y;
int dfs(int x)
{
if(dp.find(x)!=dp.end())
{
return dp[x];
}
if(!x)
{
return 1;
}
int Key;
for(int i=0;i<n;i++)
{
if((x>>i)&1)
{
Key=i;
break;
}
}
int Res=0;
for(int i=1;i<=m;i++)
{
if(!(S[i]&(1<<Key)))
{
continue;
}
if((S[i]&x)!=S[i])
{
continue;
}
Res=((long long)Res+((long long)dfs(x^S[i])*P[i])%MOD)%MOD;
}
dp[x]=Res;
return Res;
}
int main()
{
//freopen("date.in","r",stdin);
inv2=inv(2,MOD);
inv4=inv(4,MOD);
scanf("%d %d",&n,&q);
m=0;
for(int i=1;i<=q;i++)
{
scanf("%d",&t);
if(t==0)
{
scanf("%d %d",&a,&b);
S[++m]=(1<<(a-1)|(1<<(n+b-1)));
P[m]=(inv2);
}
else
{
scanf("%d %d %d %d",&a,&b,&x,&y);
S[++m]=(1<<(a-1)|(1<<(n+b-1)));
P[m]=(inv2);
S[++m]=(1<<(x-1)|(1<<(n+y-1)));
P[m]=(inv2);
if((S[m]&S[m-1]))
{
continue;
}
++m;
S[m]=S[m-1]|S[m-2];
P[m]=inv4;
if(t==2)
{
P[m]=(MOD-P[m]);
}
}
}
int Res=dfs((1<<2*n)-1);
printf("%lld",((long long)Res*(1<<n)%MOD));
}
[HNOI2014]江南乐
首先明确\(SG\)函数的意义是将游戏等价于\(SG(x)\)个石子的\(Nim\)堆
考虑在这个游戏,很明显是可以将其拆分为每个石子的\(SG\)的异或和
对于一个\(x\)的石子堆,我们考虑分成\(M\)堆,其中大小有\(a=\lfloor\dfrac{x}{M}\rfloor,a+1\),个数分别为\(num=M-(x\bmod M),M-num\)
注意多个游戏的\(SG\)为其子游戏\(SG\)的异或和,则分成\(M\)堆对应的\(SG\)即为\([SG(a)*(num\&1)]\oplus [SG(a+1)*((M-num)\&1)]\)
最后再对每种分法取\(MEX\)即可,这样做是\(O(n^3)\)的
打个表发现答案不超过\(20\),这里我们可以考虑每个\(a\)对\(x\)的影响,即用\(aM\)倒退\(x\)的子结点是否有\(SG(a)\)
注意\(M>1\),这启示我们直接倍增
直接对于\(a\)调和级数枚举\(M\),考虑计算出其影响的区间及其长度,推导一下不难发现我们把位置分奇偶算贡献即可,最后离线处理一下即可,时间复杂度应该是\(O(nlog^2n)\)的
Show Code
#include<bits/stdc++.h>
using namespace std;
const int MAXN=1e5+5;
const int Lit=1e5;
int T;
int n,F;
int x;
int dp[MAXN];
vector<pair<int,int> >Rp[MAXN];
int Odd[25];
int Even[25];
int main()
{
// freopen("date.in","r",stdin);
// freopen("date.out","w",stdout);
scanf("%d %d",&T,&F);
dp[1]=0;
for(int Len=2;Len/2<=Lit;Len<<=1)
{
int L=1;
int R=min(Len,Lit);
int Pr=Len/2;
for(int i=L;i<=R;i++)
{
Rp[i].clear();
}
for(int i=1;i<=Pr;i++)
{
for(int j=2;i*j<=R;j++)
{
int l=i*j;
int r=(i+1)*j-1;
int len=(r-l+1);
if(len%2==0)
{
Rp[l+1].push_back(make_pair(dp[i]^dp[i+1],r));
}
else
{
Rp[l].push_back(make_pair(dp[i],r));
Rp[l+1].push_back(make_pair(dp[i+1],r));
}
}
}
for(int i=1;i<=20;i++)
{
Odd[i]=0;
Even[i]=0;
}
for(int i=1;i<=Lit;i++)
{
if(i&1)
{
for(int j=0;j<Rp[i].size();j++)
{
Odd[Rp[i][j].first]=max(Odd[Rp[i][j].first],Rp[i][j].second);
}
if(i>Pr)
{
for(int j=1;j<=20;j++)
{
if(Odd[j]>=i)
{
}
else
{
if(i>=F)
{
dp[i]=j;
if(i==1)
{
dp[i]=0;
}
}
else
{
dp[i]=0;
}
break;
}
}
}
}
else
{
for(int j=0;j<Rp[i].size();j++)
{
Even[Rp[i][j].first]=max(Even[Rp[i][j].first],Rp[i][j].second);
}
if(i>Pr)
{
for(int j=1;j<=20;j++)
{
if(Even[j]>=i)
{
}
else
{
if(i>=F)
{
dp[i]=j;
if(i==1)
{
dp[i]=0;
}
}
else
{
dp[i]=0;
}
break;
}
}
}
}
}
}
// for(int i=1;i<=10;i++)
// {
// printf("%d\n",dp[i]);
// }
while(T--)
{
scanf("%d",&n);
int Res=0;
while(n--)
{
scanf("%d",&x);
Res=Res^dp[x];
}
if(Res)
{
printf("1 ");
}
else
{
printf("0 ");
}
}
}
[HNOI2007]分裂游戏
一个很巧妙的题
首先每次操作是独立的,因为我们可以考虑对于\(i\)有\(1\)个豆子,操作\(i,j,k\)之后将其拆分成\(j,k\)两个游戏
假设\(i\)有一个豆子,胜负的决定在于\(i\)与\(n\)的位置,我们不妨倒序
很明显是\(SG\)函数,后续状态即使\(j,k\)的合并也就是\(SG(j)\oplus SG(k)\)
这里我们可以\(O(n^3)\)求出\(SG\)
对于提供方案,我们可以直接枚举,寻找\(i,j,k\),考虑操作后\(i,j,k\)的贡献情况都变了,于是直接异或即可
Show Code
#include<bits/stdc++.h>
using namespace std;
int T;
int n;
int dp[55];
int a[55];
int main()
{
freopen("date.in","r",stdin);
freopen("date.out","w",stdout);
dp[1]=0;
for(int i=2;i<=50;i++)
{
vector<int>Rp;
for(int j=1;j<i;j++)
{
for(int k=1;k<=j;k++)
{
Rp.push_back(dp[j]^dp[k]);
}
}
sort(Rp.begin(),Rp.end());
unique(Rp.begin(),Rp.end());
int Key=Rp.size();
for(int j=0;j<Rp.size();j++)
{
if(Rp[j]!=j)
{
Key=j;
break;
}
}
dp[i]=Key;
}
scanf("%d",&T);
while(T--)
{
scanf("%d",&n);
int Res=0;
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
int Rlf=n-i+1;
if(a[i]&1)
{
Res^=dp[Rlf];
}
}
if(Res)
{
int Tot=0;
for(int i=1;i<=n;i++)
{
for(int j=i+1;j<=n;j++)
{
for(int k=j;k<=n;k++)
{
int Lp=Res;
Lp^=dp[n-i+1];
Lp^=dp[n-j+1];
Lp^=dp[n-k+1];
if(Lp==0)
{
if(!Tot)
{
printf("%d %d %d\n",i-1,j-1,k-1);
}
Tot++;
}
}
}
}
printf("%d\n",Tot);
}
else
{
printf("-1 -1 -1\n");
printf("0\n");
}
}
}
[THUSCH2017] 巧克力
一个有意思的题
首先解决第一问,这个选择一些联通块使其包含\(k\)中不同的颜色看着就很像斯坦纳树,我们只需要枚举一些关键颜色即可
当然,枚举关键颜色什么的就已经超时了
这里我们可以考虑给每个颜色都赋一个\((0,k)\)的权,用这个跑斯坦纳树
合理跑出来的答案只会偏大,假设我们随机的权是的答案的方案正好不同,很明显,这样的正确率\(T=\dfrac{k!}{k^k}\)
这个正确率约为\(0.03\),如果我们多跑几次,错误的概率即为\((1-T)^t\)
实测\(t=150\)就可以了
考虑第二问,套路二分,在跑斯坦纳树的时候给大于\(Mid\)赋\(1\),小于的赋\(-1\),记录二元组的最小值即可
Show Code
#include<bits/stdc++.h>
using namespace std;
mt19937 mt_rand(time(0));
int n,m;
int K;
int C[240][240];
int clo[240];
int c[240];
int Hash(int x,int y)
{
return (x-1)*m+y;
}
int zfx[5]={0,0,1,-1};
int zfy[5]={1,-1,0,0};
int Val[240];
int a[240];
int A[240][240];
pair<int,int>dp[(1<<5)+5][240];
vector<int>g[240];
struct Node{
int u;
pair<int,int>Val;
bool operator < (const Node x)const{
return Val>x.Val;
}
};
pair<int,int>Plus(pair<int,int>x,pair<int,int>y)
{
return make_pair(x.first+y.first,x.second+y.second);
}
pair<int,int>Sub(pair<int,int>x,pair<int,int>y)
{
return make_pair(x.first-y.first,x.second-y.second);
}
priority_queue<Node>q;
bool vis[240];
void dijkstra(int S)
{
memset(vis,0,sizeof(vis));
while(q.size())
{
Node temp=q.top();
q.pop();
if(vis[temp.u])
{
continue;
}
vis[temp.u]=1;
for(int i=0;i<g[temp.u].size();i++)
{
int v=g[temp.u][i];
if(dp[S][v]>Plus(dp[S][temp.u],make_pair(1,Val[v])))
{
dp[S][v]=Plus(dp[S][temp.u],make_pair(1,Val[v]));
Node od;
od.u=v;
od.Val=dp[S][v];
q.push(od);
}
}
}
}
pair<int,int>Get()
{
int T=150;
pair<int,int>Res;
Res.first=0x3f3f3f3f;
Res.second=0x3f3f3f3f;
while(T--)
{
for(int i=1;i<=n*m;i++)
{
clo[i]=i;
}
shuffle(clo + 1, clo+ n * m, mt_rand);
for(int i=1;i<=n*m;i++)
{
clo[i]=(clo[i]%K);
}
for(int S=0;S<(1<<K);S++)
{
for(int i=1;i<=n*m;i++)
{
dp[S][i].first=0x3f3f3f3f;
dp[S][i].second=0x3f3f3f3f;
}
}
for(int i=1;i<=n*m;i++)
{
if(c[i]!=-1)
{
dp[(1<<clo[c[i]])][i].first=1;
dp[(1<<clo[c[i]])][i].second=Val[i];
}
}
for(int S=0;S<(1<<K);S++)
{
while(q.size())
{
q.pop();
}
for(int i=1;i<=n*m;i++)
{
for(int sub=(S&(S-1));sub;sub=(S)&(sub-1))
{
dp[S][i]=min(dp[S][i],Plus(dp[sub][i],Sub(dp[S^sub][i],make_pair(1,Val[i]))));
}
if(dp[S][i].first<0x3f3f3f3f)
{
Node lsp;
lsp.u=i;
lsp.Val=dp[S][i];
q.push(lsp);
}
}
dijkstra(S);
}
for(int i=1;i<=n*m;i++)
{
Res=min(Res,dp[(1<<K)-1][i]);
}
}
return Res;
}
bool check(int x)
{
for(int i=1;i<=n*m;i++)
{
if(a[i]>x)
{
Val[i]=1;
}
else
{
Val[i]=-1;
}
}
pair<int,int>P=Get();
return P.second<=0;
}
int main()
{
//freopen("date.in","r",stdin);
int T;
scanf("%d",&T);
while(T--)
{
scanf("%d %d %d",&n,&m,&K);
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
scanf("%d",&C[i][j]);
c[Hash(i,j)]=C[i][j];
}
}
vector<int>Pro;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
scanf("%d",&A[i][j]);
a[Hash(i,j)]=A[i][j];
Pro.push_back(A[i][j]);
}
}
sort(Pro.begin(),Pro.end());
unique(Pro.begin(),Pro.end());
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
g[Hash(i,j)].clear();
}
}
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
for(int k=0;k<4;k++)
{
int nx=i+zfx[k];
int ny=j+zfy[k];
if(nx>=1&&ny>=1&&nx<=n&&ny<=m)
{
if(c[Hash(nx,ny)]==-1)
{
continue;
}
g[Hash(i,j)].push_back(Hash(nx,ny));
}
}
}
}
pair<int,int>Pk=Get();
if(Pk.first==0x3f3f3f3f)
{
printf("-1 -1\n");
continue;
}
printf("%d ",Pk.first);
int l=0;
int r=Pro.size()-1;
int Key;
int Tot=0;
while(l<=r)
{
++Tot;
int mid=(l+r)>>1;
if(check(Pro[mid]))
{
r=mid-1;
Key=mid;
}
else
{
l=mid+1;
}
}
printf("%d\n",Pro[Key]);
}
}