A. circle
分析
如果一个竞赛图存在大于等于三元环，则一定存在三元环
所以问题就变成了删去最少的点使的图中不存在三元环
考虑题目给出的特殊性质，删去 (k) 个点后剩余的图中将不存在环
也就是说剩下的 (n-k) 个点是一个 (DAG)，而且是一个满边 (DAG)
同样地，如果最终存在合法的解，那么这 (k) 个点形成的有向图也是一个满边 (DAG)
因为如果有环，我们肯定割不断这个环
先把这两部分按照拓扑序从小到大排好序
在满边 (DAG) 中，直接按照度数从小到大排就是一种拓扑序，而且这个拓扑序是唯一的
因为这些点的入度肯定是互不相同的
考虑删去一个点会使得剩下所有点的度数整体减一
所以某一时刻有且仅有一个点入度为零
设题目中给出的 (k) 个点为黑点，其它的点为白点
那么三元环只会有两种情况
(1)、两个黑点一个白点
(2)、两个白点一个黑点
第一种情况肯定要割掉白点
设这个白点为 (x)
出现这种情况只能是存在两个黑点 (u,v)
(u) 的拓扑序大于 (v) ，并且同时存在 (x) 到 (v) 的一条边和 (u) 到 (x) 的一条边
反之，不存在这种情况当且仅当 (x) 与所有黑点的连边按照黑点的拓扑序排序后
前半部分的边由黑点指向 (x)，后半部分的点由 (x) 指向黑点
第二种情况要在两个白点中选择一个割掉
这两个白点肯定不能是第一种情况，否则就没有选择了
所以它们排序之后的边一定有一个分界点，设这个分界点为 (val[i])
那么就考虑什么样的白点会产生冲突
当且仅当存在一对点 (i,j)，满足 (i) 的拓扑序小于 (j) 的拓扑序，并且 (val[i]>val[j])
可以理解为出现了逆序对就有冲突
所以只要对 (val) 数组求一个最长不下降子序列得到最多的能共存的白点
再拿白点的总数减去就行了
代码
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<cstring>
#include<queue>
#define rg register
inline int read(){
rg int x=0,fh=1;
rg char ch=getchar();
while(ch<'0' || ch>'9'){
if(ch=='-') fh=-1;
ch=getchar();
}
while(ch>='0' && ch<='9'){
x=(x<<1)+(x<<3)+(ch^48);
ch=getchar();
}
return x*fh;
}
const int maxn=2e3+5,maxm=1e6+5;
int mp[maxn][maxn],n,m,a[maxn],vis[maxn],id[maxn],du[maxn],f[maxn],val[maxn],cnt,sta[maxn],tp,mmax;
bool cmp(rg int aa,rg int bb){
if(vis[aa]==vis[bb]) return du[aa]<du[bb];
return vis[aa]<vis[bb];
}
int main(){
n=read(),m=read();
for(rg int i=1;i<=n;i++) for(rg int j=1;j<=n;j++) mp[i][j]=read();
for(rg int i=1;i<=m;i++) a[i]=read(),vis[a[i]]=1;
for(rg int i=1;i<=n;i++){
for(rg int j=1;j<=n;j++){
if(mp[i][j] && vis[i]==vis[j]) du[j]++;
}
}
for(rg int i=1;i<=n;i++) if(!vis[i]) id[++cnt]=i;
std::sort(a+1,a+1+m,cmp),std::sort(id+1,id+cnt+1,cmp);
for(rg int i=1;i<=cnt;i++){
if(du[id[i]]!=i-1){
printf("impossible
");
return 0;
}
}
for(rg int i=1;i<=m;i++){
if(du[a[i]]!=i-1){
printf("impossible
");
return 0;
}
}
for(rg int i=1;i<=cnt;i++){
val[i]=1;
for(rg int j=1;j<=m;j++){
if(mp[a[j]][id[i]]) val[i]=j+1;
else break;
}
for(rg int j=val[i];j<=m;j++){
if(!mp[id[i]][a[j]]){
val[i]=0;
break;
}
}
}
for(rg int i=1;i<=cnt;i++){
if(!val[i]) continue;
f[i]=1;
for(rg int j=1;j<i;j++){
if(!val[j]) continue;
if(val[i]>=val[j]) f[i]=std::max(f[i],f[j]+1);
}
mmax=std::max(mmax,f[i]);
}
if(cnt-mmax>=m) printf("impossible
");
else printf("%d
",cnt-mmax);
return 0;
}
B. 生成膜咒
分析
题目中的 (fail) 其实就是 (border)
一个 (border) 的贡献其实就是一个子串出现在了两个不同的位置
在后缀自动机中相当于一个 (endpos) 集合中不同的 (endpos) 之间的贡献
容易发现加入一个字符产生的新的贡献就是以当前节点为结尾的后缀
我们只需要看这些后缀在之前出现了多少次就行了
这用后缀自动机来做就很舒服了
for(;np;np=fa[np]){
nans=addmod(nans,mulmod(len[np]-len[fa[np]],siz[np]));
siz[np]++;
}
但是直接向上跳复杂度是假的，所以要用数据结构维护一下
比如说树剖或者 (lct)
因为是所有子串的贡献，而不是所有后缀的贡献
所以每次要把之前所有的贡献加上
代码
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<queue>
#include<cmath>
#include<ctime>
#define rg register
inline int read(){
rg int x=0,fh=1;
rg char ch=getchar();
while(ch<'0' || ch>'9'){
if(ch=='-') fh=-1;
ch=getchar();
}
while(ch>='0' && ch<='9'){
x=(x<<1)+(x<<3)+(ch^48);
ch=getchar();
}
return x*fh;
}
const int maxn=2e6+5,mod=1e9+7;
inline int addmod(rg int now1,rg int now2){
return now1+=now2,now1>=mod?now1-mod:now1;
}
inline int mulmod(rg long long now1,rg int now2){
return now1*=now2,now1>=mod?now1%mod:now1;
}
int n,ans;
char s[maxn];
struct SAM{
int ch[maxn][28],lst,cnt,fa[maxn],len[maxn],nans,wz[maxn];
void insert(rg int c){
rg int p=lst;
rg int np=lst=++cnt;
len[np]=len[p]+1;
for(;p && !ch[p][c];p=fa[p]) ch[p][c]=np;
if(!p) fa[np]=1;
else {
rg int q=ch[p][c];
if(len[q]==len[p]+1) fa[np]=q;
else {
rg int nq=++cnt;
len[nq]=len[p]+1;
memcpy(ch[nq],ch[q],sizeof(ch[q]));
fa[nq]=fa[q];
fa[q]=fa[np]=nq;
for(;p && ch[p][c]==q;p=fa[p]) ch[p][c]=nq;
}
}
}
void build(){
lst=cnt=1;
for(rg int i=1;i<=n;i++) wz[i]=cnt+1,insert(s[i]-'a');
}
struct asd{
int to,nxt;
}b[maxn<<1];
int h[maxn],tot=1;
void ad(rg int aa,rg int bb){
b[tot].to=bb;
b[tot].nxt=h[aa];
h[aa]=tot++;
}
int dfn[maxn],rk[maxn],dfnc,val[maxn],dep[maxn],son[maxn],siz[maxn],tp[maxn];
void dfs1(rg int now){
dep[now]=dep[fa[now]]+1;
siz[now]=1;
for(rg int i=h[now];i!=-1;i=b[i].nxt){
rg int u=b[i].to;
if(u==fa[now]) continue;
dfs1(u);
siz[now]+=siz[u];
if(son[now]==0 || siz[u]>siz[son[now]]) son[now]=u;
}
}
void dfs2(rg int now,rg int top){
dfn[now]=++dfnc;
tp[now]=top;
rk[dfnc]=now;
if(son[now]) dfs2(son[now],top);
for(rg int i=h[now];i!=-1;i=b[i].nxt){
rg int u=b[i].to;
if(u==son[now] || u==fa[now]) continue;
dfs2(u,u);
}
}
struct trr{
int l,r,sum,val,tag;
}tr[maxn<<2];
void push_up(rg int da){
tr[da].val=addmod(tr[da<<1].val,tr[da<<1|1].val);
tr[da].sum=addmod(tr[da<<1].sum,tr[da<<1|1].sum);
}
void push_down(rg int da){
if(!tr[da].tag) return;
tr[da<<1].sum=addmod(tr[da<<1].sum,mulmod(tr[da].tag,tr[da<<1].val));
tr[da<<1|1].sum=addmod(tr[da<<1|1].sum,mulmod(tr[da].tag,tr[da<<1|1].val));
tr[da<<1].tag=addmod(tr[da<<1].tag,tr[da].tag);
tr[da<<1|1].tag=addmod(tr[da<<1|1].tag,tr[da].tag);
tr[da].tag=0;
}
void buildtree(rg int da,rg int l,rg int r){
tr[da].l=l,tr[da].r=r;
if(l==r){
tr[da].val=val[rk[l]];
return;
}
rg int mids=(l+r)>>1;
buildtree(da<<1,l,mids),buildtree(da<<1|1,mids+1,r);
push_up(da);
}
void xg(rg int da,rg int l,rg int r){
if(tr[da].l>=l && tr[da].r<=r){
tr[da].tag++,tr[da].sum=addmod(tr[da].sum,tr[da].val);
return;
}
push_down(da);
rg int mids=(tr[da].l+tr[da].r)>>1;
if(l<=mids) xg(da<<1,l,r);
if(r>mids) xg(da<<1|1,l,r);
push_up(da);
}
int cx(rg int da,rg int l,rg int r){
if(tr[da].l>=l && tr[da].r<=r) return tr[da].sum;
push_down(da);
rg int mids=(tr[da].l+tr[da].r)>>1,tmp=0;
if(l<=mids) tmp=addmod(tmp,cx(da<<1,l,r));
if(r>mids) tmp=addmod(tmp,cx(da<<1|1,l,r));
return tmp;
}
void solve(){
memset(h,-1,sizeof(h));
for(rg int i=2;i<=cnt;i++) val[i]=len[i]-len[fa[i]],ad(i,fa[i]),ad(fa[i],i);
dfs1(1),dfs2(1,1);
buildtree(1,1,cnt);
for(rg int i=1;i<=n;i++){
rg int now=wz[i];
while(now){
nans=addmod(nans,cx(1,dfn[tp[now]],dfn[now]));
xg(1,dfn[tp[now]],dfn[now]);
now=fa[tp[now]];
}
ans=addmod(ans,nans);
printf("%d
",ans);
}
}
}sam;
int main(){
n=read();
scanf("%s",s+1);
sam.build();
sam.solve();
return 0;
}
C. simulate
分析
模拟
所谓的轮肯定是来束缚你的，操作顺序显然对答案没有影响
从前往后考虑，保证扫到的位置前面都是 (0/1)
对于当前位置进行操作，发现就是把前面最近的一个 (0) 拉近 (1) 的距离，并把当前数 (−1) 后面数 (+1)
特别的如果前面就是一个 (0) 那么就是当前位 (−2)，前面的 (0) 消失，后面 (+1)
用栈存 (0) 的位置，注意下标 (0)处有无穷无尽个 (0)
代码
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<cstring>
#include<vector>
#include<ctime>
#define rg register
inline int read(){
rg int x=0,fh=1;
rg char ch=getchar();
while(ch<'0' || ch>'9'){
if(ch=='-') fh=-1;
ch=getchar();
}
while(ch>='0' && ch<='9'){
x=(x<<1)+(x<<3)+(ch^48);
ch=getchar();
}
return x*fh;
}
const int maxn=2e7+5;
char s[maxn];
int n,sta[maxn],tp,a[maxn];
int main(){
scanf("%s",s+1);
n=strlen(s+1);
for(rg int i=1;i<=n;i++) a[i]=s[i]-'0';
for(rg int i=1;i<=n;i++){
while(a[i]>=2){
if(!tp) sta[++tp]=0;
rg int now=std::min(a[i]-1,i-1-sta[tp]);
if(sta[tp]==i-1) tp--,a[i]-=2,a[i+1]++;
else sta[tp]=sta[tp]+now,a[i]-=now,a[i+1]+=now;
}
if(!a[i]) sta[++tp]=i;
}
for(rg int i=1;i<=n;i++) a[i]=1;
for(rg int i=1;i<=tp;i++) a[sta[i]]=0;
for(rg int i=1;i<=n;i++) s[i]=a[i]+'0';
printf("%s
",s+1);
return 0;
}