HNOI2017 Day2
2023-06-10
注：Day2T2换为BJOI2017Day2T1，以匹配学习进度
HNOI2017 Day1
2023-06-09
HNOI2018 Day1
2023-05-30
A 寻宝游戏
给定\(n\)个长为\(m\)的二进制串，可以在每两个二进制数之间和第一个数之前添加一个运算符（按位与/按位或），然后在这个算式最前面填上\(0\)。问使得这个算式的值刚好为给定的询问值的添加方法数。\(q\)组询问。答案对\(10^9+7\)取模。
\(n \le 1000, m \le 5000, q \le 1000\)。
key：Adhoc
将按位与看做\(1\)，按位或看做\(0\)，会发现：将操作序列和每个数第\(j\)位构成的序列从后往前比较，若操作序列字典序小，则该位结果为\(1\)，否则结果为\(0\)。证明是不难的。
那么只要将每一位构成的序列排序，如果询问串要求比一段前缀大，比一段后缀小就合法，输出分界点的两个数的差；否则无解。
用基数排序可以将时间复杂度做到\(O((n+q)m)\)。
点击查看代码
#include<bits/stdc++.h>
using namespace std;
const int N=1005,M=5005,mod=1e9+7;
int n,m,q,d=1,cnt[2],val[M],A[M],B[M];char s[M];
int main(){
scanf("%d%d%d",&n,&m,&q);
for(int i=1;i<=m;i++)A[i]=i;
for(int i=1;i<=n;i++,d=d*2%mod){
scanf("%s",s+1);
cnt[0]=0;cnt[1]=m;
for(int j=1;j<=m;j++){
if(s[j]=='0')cnt[0]++;
else val[j]=(val[j]+d)%mod;
}
for(int j=m;j>=1;j--)
B[cnt[s[A[j]]-'0']--]=A[j];
for(int j=1;j<=m;j++)A[j]=B[j];
}
for(int i=1;i<=m;i++)B[A[i]]=i;
A[m+1]=m+1;val[m+1]=d;
for(int i=1;i<=q;i++){
int L=0,R=m+1;
scanf("%s",s+1);
for(int j=1;j<=m;j++){
if(s[j]=='0')L=max(L,B[j]);
else R=min(R,B[j]);
}
if(L>R)printf("0\n");
else printf("%d\n",(val[A[R]]-val[A[L]]+mod)%mod);
}
return 0;
}
B 转盘
一个转盘上有摆成一圈的\(n\)个物品，依次编号为\(1\sim n\)，编号为的\(i\)物品会在\(T_i\)时刻出现（之后不消失）。在 \(0\) 时刻时，小G可以任选 \(n\) 个物品中的一个，每经过一个单位时间可以继续选择当前物品或选择下一个物品。在每一时刻，如果小 G 选择的物品已经出现了，那么小G将会标记它。问小G至少需要多少时间来标记所有物品。
然而还有\(m\)次修改，每次修改改变一个物品的出现时间。强制在线。
\(n,m\le 10^5\)。
建议BC两题换一下名字
key：线段树，单调栈
首先转化问题，记\(a_i=t_i-i (1 \le i \le 2n)，t_{i+n}=t_i\)，注意到小G最多转一圈，随便推推容易发现：以\(i\)为起点的答案是\(\max_{i\le j \lt i+n}{a_j}+n+i-1\)。然后可以把上界换成\(2n\)。
这个时候转化视角，考虑对于某个\(j\)的最小值。显然只用考虑\(a_j\)是后缀最大值的情形。设\(a_i\)是大于\(a_j\)的数中最靠右的一个，则\(a_j\)的答案是\(a_j+i+n\)。
所以可以考虑用线段树维护一个单调栈，从后向前考虑即可。
点击查看代码
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5,INF=1<<30;
int n,m,op,a[N<<1],ans;
struct node{int mx,res;}tr[N<<2];
int query(int p,int l,int r,int x){
if(l==r)return tr[p].mx>x?x+l:INF;
int mid=l+r>>1;
if(tr[p<<1|1].mx<=x)return query(p<<1,l,mid,x);
return min(tr[p].res,query(p<<1|1,mid+1,r,x));
}
void push_up(int p,int l,int r){
tr[p].mx=max(tr[p<<1].mx,tr[p<<1|1].mx);
tr[p].res=query(p<<1,l,l+r>>1,tr[p<<1|1].mx);
}
void build(int p,int l,int r){
if(l==r){tr[p].mx=a[l]-l;return;}
int mid=l+r>>1;
build(p<<1,l,mid);
build(p<<1|1,mid+1,r);
push_up(p,l,r);
}
void modify(int p,int l,int r,int x,int v){
if(l==r){tr[p].mx=v-l;return;}
int mid=l+r>>1;
if(x<=mid)modify(p<<1,l,mid,x,v);
else modify(p<<1|1,mid+1,r,x,v);
push_up(p,l,r);
}
int main(){
scanf("%d%d%d",&n,&m,&op);
for(int i=1;i<=n;i++)scanf("%d",a+i);
build(1,1,n);
printf("%d\n",ans=query(1,1,n,tr[1].mx-n)+n);
for(int i=1,x,y;i<=m;i++){
scanf("%d%d",&x,&y);
if(op)x^=ans,y^=ans;
modify(1,1,n,x,y);
printf("%d\n",ans=query(1,1,n,tr[1].mx-n)+n);
}
return 0;
}
C 毒瘤
\(n\)个点，\(m\)条边的连通简单无向图，求独立集个数。
\(n\le 10^5,m \le n+10\)。
key：DP，虚树/动态DP
首先随便取一棵生成树，然后标记所有非树边的端点。
对于树的情况，很容易用树形DP解决。同时有一个显然的暴力：枚举上述所有端点的颜色，做树形DP。
考虑对所有端点建出虚树，在虚树上DP。这样时间复杂度就是\(O(s4^s)\)，其中\(s=m-n+1\)，能过。
发现在虚树上的一条边转移时，不论该边两个端点状态如何，因为这两个点在原树上之间的形态相同，所以转移系数是相同的。那么暴力求出每个点到它虚树上的父亲的转移系数。这里可以直接暴力，最多把每个点遍历一次。
剩下就是二进制枚举。
这道题也可以用动态DP，可以算是一个模板题。
点击查看代码
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+50,mod=998244353;
int n,m,ans,a[N];
int head[N],ver[N<<1],nxt[N<<1],tot=1;
int hc[N],vc[N<<1],nc[N<<1],tc;
void add(int u,int v){ver[++tot]=v;nxt[tot]=head[u];head[u]=tot;}
void addc(int u,int v){vc[++tc]=v;nc[tc]=hc[u];hc[u]=tc;}
int fa[N][20],dep[N],dfn[N],Dfn,tr[N<<1],vis[N],x[N],d[N],k,st[N],top;
void dfs(int u){
dfn[u]=++Dfn;
for(int i=head[u],v;i;i=nxt[i])
if(!dfn[v=ver[i]]){
tr[i]=tr[i^1]=1;
fa[v][0]=u;dep[v]=dep[u]+1;
dfs(v);
}
}
void LCA_pre(){
for(int j=1;(1<<j)<=n;j++)
for(int i=1;i<=n;i++)
fa[i][j]=fa[fa[i][j-1]][j-1];
}
int LCA(int u,int v){
if(dep[u]<dep[v])swap(u,v);
int d=dep[u]-dep[v];
for(int i=17;i>=0;i--)
if(d&(1<<i))u=fa[u][i];
if(u==v)return u;
for(int i=17;i>=0;i--)
if(fa[u][i]!=fa[v][i])
u=fa[u][i],v=fa[v][i];
return fa[u][0];
}
bool cmp(int i,int j){return dfn[i]<dfn[j];}
void vtree(){
sort(x+1,x+k+1,cmp);st[top=1]=1;
for(int i=1;i<=k;i++)if(x[i]!=1){
int g=LCA(x[i],st[top]);
if(g!=st[top]){
while(dfn[g]<dfn[st[top-1]])
addc(st[top-1],st[top]),--top;
if(dfn[g]!=dfn[st[top-1]])
addc(g,st[top]),st[top]=g;
else addc(g,st[top]),--top;
}
st[++top]=x[i];
}
for(int i=1;i<top;i++)addc(st[i],st[i+1]);
}
int dp[N][2],trans[N][2][2],f[N][2];
void DP_pre(int u){
dp[u][0]=dp[u][1]=1;
for(int i=head[u],v;i;i=nxt[i])
if(tr[i]&&(v=ver[i])!=fa[u][0]){
DP_pre(v);
if(!vis[v]){
dp[u][0]=1ll*dp[u][0]*(dp[v][0]+dp[v][1])%mod;
dp[u][1]=1ll*dp[u][1]*dp[v][0]%mod;
}
else vis[u]=1;
}
}
void DP(int u){
f[u][0]=dp[u][0];f[u][1]=dp[u][1];
if(a[u]!=-1)f[u][1-a[u]]=0;
for(int i=hc[u],v;i;i=nc[i]){
DP(v=vc[i]);
int f0=(1ll*trans[v][0][0]*f[v][0]+1ll*trans[v][0][1]*f[v][1])%mod,
f1=(1ll*trans[v][1][0]*f[v][0]+1ll*trans[v][1][1]*f[v][1])%mod;
f[u][0]=1ll*f[u][0]*(f0+f1)%mod;
f[u][1]=1ll*f[u][1]*f0%mod;
}
}
int main(){
memset(a,-1,sizeof(a));
scanf("%d%d",&n,&m);
for(int i=1,u,v;i<=m;i++){
scanf("%d%d",&u,&v);
add(u,v);add(v,u);
}
dfs(1);LCA_pre();
for(int i=2;i<=tot;i+=2)if(!tr[i]){
++k;vis[d[k]=x[k]=ver[i]]=1;
++k;vis[d[k]=x[k]=ver[i^1]]=1;
}
DP_pre(1);
sort(x+1,x+k+1);
k=unique(x+1,x+k+1)-x-1;
vtree();
for(int u=1;u<=n;u++)
for(int i=hc[u];i;i=nc[i]){
int v=vc[i];
trans[v][0][0]=trans[v][1][1]=1;
for(int x=v;fa[x][0]!=u;x=fa[x][0]){
int t00=trans[v][0][0],t01=trans[v][0][1],
t10=trans[v][1][0],t11=trans[v][1][1],y=fa[x][0];
trans[v][0][0]=1ll*dp[y][0]*(t00+t10)%mod;
trans[v][0][1]=1ll*dp[y][0]*(t01+t11)%mod;
trans[v][1][0]=1ll*dp[y][1]*t00%mod;
trans[v][1][1]=1ll*dp[y][1]*t01%mod;
}
}
for(int i=0;i<(1<<k);i++){
for(int j=1;j<=k;j++)a[x[j]]=(i>>j-1)&1;
bool flag=1;
for(int j=1;j<=m-n+1;j++)
if(a[d[2*j-1]]&&a[d[2*j]])flag=0;
if(!flag)continue;
DP(1);ans=(ans+(f[1][0]+f[1][1])%mod)%mod;
}
printf("%d\n",ans);
return 0;
}
动态DP：
点击查看代码
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e5+50;const ll mod=998244353;
int n,m;ll f[N][2],ans;
int head[N],nxt[N<<1],ver[N<<1],tot=1,tr[N<<1];
void add(int u,int v){ver[++tot]=v;nxt[tot]=head[u];head[u]=tot;}
ll power(ll a,ll b){
ll c=1;
for(;b;b>>=1){
if(b&1)c=c*a%mod;
a=a*a%mod;
}
return c;
}
struct Matrix{
ll a[2][2];
Matrix (){a[0][0]=a[0][1]=a[1][0]=a[1][1]=0;}
Matrix operator *(const Matrix&b)const{
Matrix c;
c.a[0][0]=(a[0][0]*b.a[0][0]+a[0][1]*b.a[1][0])%mod;
c.a[1][0]=(a[1][0]*b.a[0][0]+a[1][1]*b.a[1][0])%mod;
c.a[0][1]=(a[0][0]*b.a[0][1]+a[0][1]*b.a[1][1])%mod;
c.a[1][1]=(a[1][0]*b.a[0][1]+a[1][1]*b.a[1][1])%mod;
return c;
}
}g[N];
int fa[N],top[N],siz[N],L[N],dfn,R[N],son[N],id[N];
void dfs(int u){
f[u][0]=f[u][1]=1;siz[u]=1;
for(int i=head[u],v;i;i=nxt[i])
if(!siz[v=ver[i]]){
tr[i]=tr[i^1]=1;
fa[v]=u;dfs(v);siz[u]+=siz[v];
if(siz[v]>siz[son[u]])son[u]=v;
f[u][0]=f[u][0]*(f[v][0]+f[v][1])%mod;
f[u][1]=f[u][1]*f[v][0]%mod;
}
}
void rdfs(int u,int tp){
g[u].a[0][0]=g[u].a[1][0]=1;
L[u]=++dfn;id[dfn]=u;top[u]=tp;R[tp]=dfn;
if(son[u])rdfs(son[u],tp);
for(int i=head[u],v;i;i=nxt[i])
if(tr[i]&&(v=ver[i])!=fa[u]&&v!=son[u]){
rdfs(v,v);
g[u].a[0][0]=g[u].a[0][0]*(f[v][0]+f[v][1])%mod;
g[u].a[1][0]=g[u].a[1][0]*f[v][0]%mod;
}
g[u].a[0][1]=g[u].a[0][0];
}
struct SegmentTree{
Matrix a[N<<2];
#define mid (l+r>>1)
void build(int p,int l,int r){
if(l==r){a[p]=g[id[l]];return;}
build(p<<1,l,mid);
build(p<<1|1,mid+1,r);
a[p]=a[p<<1]*a[p<<1|1];
}
void modify(int p,int l,int r,int x){
if(l==r){a[p]=g[id[l]];return;}
if(x<=mid)modify(p<<1,l,mid,x);
else modify(p<<1|1,mid+1,r,x);
a[p]=a[p<<1]*a[p<<1|1];
}
Matrix query(int p,int l,int r,int L,int R){
if(l>=L&&r<=R)return a[p];
if(R<=mid)return query(p<<1,l,mid,L,R);
if(L>mid)return query(p<<1|1,mid+1,r,L,R);
return query(p<<1,l,mid,L,R)*query(p<<1|1,mid+1,r,L,R);
}
#undef mid
}seg;
int a[N],x[50],k,st[N],Top;Matrix g0[N];
vector<int> rej[N];
void update(int u,int op){
st[++Top]=u,g0[Top]=g[u];
if(op==0)g[u].a[1][0]=0;
else g[u].a[0][0]=g[u].a[0][1]=0;
while(u){
Matrix lst=seg.query(1,1,n,L[top[u]],R[top[u]]);
seg.modify(1,1,n,L[u]);
Matrix now=seg.query(1,1,n,L[top[u]],R[top[u]]);
u=fa[top[u]];st[++Top]=u,g0[Top]=g[u];
g[u].a[0][0]=g[u].a[0][0]*(now.a[0][0]+now.a[1][0])%mod
*power(lst.a[0][0]+lst.a[1][0],mod-2)%mod;
g[u].a[1][0]=g[u].a[1][0]*now.a[0][0]%mod
*power(lst.a[0][0],mod-2)%mod;
g[u].a[0][1]=g[u].a[0][0];
}
}
void clear(int tim){
while(Top>tim){
g[st[Top]]=g0[Top];
seg.modify(1,1,n,L[st[Top]]);
--Top;
}
}
void Enum(int p){
if(p==k+1){
Matrix res=seg.query(1,1,n,1,R[1]);
ans=(ans+res.a[0][0]+res.a[1][0])%mod;
return;
}
int tim=Top;
update(x[p],a[x[p]]=0);Enum(p+1);clear(tim);a[x[p]]=-1;
update(x[p],a[x[p]]=1);bool flag=1;
for(auto t:rej[x[p]])if(a[t]==1){flag=0;break;}
if(flag)Enum(p+1);clear(tim);a[x[p]]=-1;
}
int main(){
memset(a,-1,sizeof(a));
scanf("%d%d",&n,&m);
for(int i=1,u,v;i<=m;i++){
scanf("%d%d",&u,&v);
add(u,v);add(v,u);
}
dfs(1);rdfs(1,1);seg.build(1,1,n);
for(int i=2;i<=tot;i+=2)if(!tr[i]){
x[++k]=ver[i];x[++k]=ver[i^1];
rej[ver[i]].push_back(ver[i^1]);
rej[ver[i^1]].push_back(ver[i]);
}
sort(x+1,x+k+1);k=unique(x+1,x+k+1)-x-1;
Enum(1);
printf("%lld\n",ans);
return 0;
}