\(\texttt{A. Almost Increasing Subsequence}\)
把 \(a_i>a_{i+1}\)的极长下降区间称为一个段，那么显然，一个长度为 \(len\) 的极长下降区间最多选 \(\min(2,len)\)个，并且可以达到这个数，因此记录每个位置属于哪个段，记录个前缀和就好了。
#include<bits/stdc++.h>
using namespace std;
const int N = 2e5+7;
int n,m,a[N],bel[N],st[N],ed[N];
int sum[N];
int main()
{
cin>>n>>m;
int o=0;
for(int i=1;i<=n;i++)scanf("%d",&a[i]);
for(int i=1;i<=n;i++)
{
int j=i;
while(j+1<=n&&a[j+1]<=a[j])j++;
++o;
st[o]=i;
ed[o]=j;
sum[o]=sum[o-1]+min(2,j-i+1);
for(int k=i;k<=j;k++)bel[k]=o;
i=j;
}
while(m--)
{
int l,r;
scanf("%d %d",&l,&r);
int res=0;
if(bel[l]==bel[r])res=min(2,r-l+1);
else
{
res=sum[bel[r]-1]-sum[bel[l]];
res+=min(2,ed[bel[l]]-l+1);
res+=min(2,r-st[bel[r]]+1);
}
printf("%d\n",res);
}
return 0;
}
\(\texttt{B. Fish Graph}\)
一个点集可以构成鱼，一个必要条件就是，形成一个环，且有一个点的度数 \(\geq 4\).
事实上这也是充分的。
对于度数\(\geq 4\)的点 \(u\)，假如它在环上相邻的点事 \(a,b\)，另外还有两条出边连向 \(x,y\)。
如果 \(x,y\) 不在环上，显然就是合法的。
否则，我们可以把环调整成 \(…… \to y\to u\to x\to ……\)，这时 \(a,b\) 就不在环上了，就合法了。
判断是不是在某个环里可以用边双，对于 \(u\)，可以建出 \(\text{BFS}\) 树，对于属于不同子树的横叉边，就构成了一个环，并且因为 \(\text{BFS}\)，所以环是最小的，直接输出就好了。
#include<bits/stdc++.h>
using namespace std;
const int N = 4e5+7;
struct edge
{
int y,next;
}e[2*N];
int link[N],t=1;
void add(int x,int y)
{
e[++t].y=y;
e[t].next=link[x];
link[x]=t;
}
int dfn[N],low[N],bel[N],num;
bool cut[N];
int n,m,deg[N],cnt=0,siz[N],fst[N],frt[N],vis[N];
void init()
{
for(int i=1;i<=t;i++)cut[i]=0;
t=1;cnt=0;
for(int i=1;i<=n;i++)dfn[i]=low[i]=bel[i]=link[i]=deg[i]=siz[i]=fst[i]=frt[i]=vis[i]=0;
num=0;
}
void tarjan(int x,int from)
{
dfn[x]=low[x]=++num;
for(int i=link[x];i;i=e[i].next)
{
int y=e[i].y;
if(!dfn[y])
{
tarjan(y,i);
if(low[y]>dfn[x])cut[i]=cut[i^1]=1;
low[x]=min(low[x],low[y]);
}
else if(i!=(from^1))low[x]=min(low[x],dfn[y]);
}
}
int E=0;
void mark(int x)
{
E++;
if(E>n)exit(0);
bel[x]=cnt;
siz[cnt]++;
for(int i=link[x];i;i=e[i].next)
{
int y=e[i].y;
if(cut[i])continue;
if(bel[y])continue;
mark(y);
}
}
queue<int> q;
void getans(int o)
{
while(!q.empty())q.pop();
q.push(o);
int G=0;
while(!q.empty())
{
int x=q.front();
q.pop();
for(int i=link[x];i;i=e[i].next)
{
int y=e[i].y;
if(y==o)continue;
if(!fst[y])
{
if(x==o)frt[y]=y;
else frt[y]=frt[x];
fst[y]=x;
q.push(y);
}
else if(x!=o&&frt[x]!=frt[y])
{
int p=x,s=3;
p=x;while(p!=o)s++,p=fst[p];
p=y;while(p!=o)s++,p=fst[p];
printf("%d\n",s);
p=x;while(p!=o)printf("%d %d\n",fst[p],p),vis[p]=1,p=fst[p];
p=y;while(p!=o)printf("%d %d\n",fst[p],p),vis[p]=1,p=fst[p];
printf("%d %d\n",x,y);
int c=0;
for(i=link[o];i;i=e[i].next)
{
int z=e[i].y;
if(vis[z])continue;
printf("%d %d\n",o,z);
c++;
if(c==2)return;
}
}
}
}
}
int S;
void solve()
{
E=0;
init();
scanf("%d %d",&n,&m);
for(int i=1;i<=m;i++)
{
int x,y;
scanf("%d %d",&x,&y);
deg[x]++;deg[y]++;
add(x,y);
add(y,x);
}
for(int i=1;i<=n;i++)
if(!dfn[i])tarjan(i,0);
for(int i=1;i<=n;i++)
if(!bel[i])
{
++cnt;
mark(i);
}
for(int i=1;i<=n;i++)
if(deg[i]>=4&&siz[bel[i]]>1)
{
printf("YES\n");
getans(i);
return;
}
printf("NO\n");
}
int main()
{
int T;
cin>>T;
S=T;
while(T--)
{
solve();
}
return 0;
}
\(\texttt{C. Similar Polynomials}\)
因为 \(B(x)=A(x+s)\)
所以,
\[\sum_{i=0}^db_ix^i=\sum_{i=0}^da_i(x+s)^i=\sum_{i=0}^da_i\sum_{j=0}^i\binom{i}{j}x_js_{i-j}=\sum_{i=0}^d\sum_{j=i}^d\binom{j}{i}a_js_{j-i}x^i \]对于 \(i=d-1\)，\(b_{d-1}=a_{d-1}s+da_d\)，这样就可以得到 \(s\) 啦。
\(b_{d-1},a_{d},a_{d-1}\)可以拉格朗日插值求。
#include<bits/stdc++.h>
using namespace std;
const int N = 3e6+7;
const int mod = 1e9+7;
const int inv2=(mod+1)/2;
int ifac[N],pw[N];
void init(int n)
{
ifac[1]=1;
for(int i=2;i<=n;i++)
ifac[i]=1ll*ifac[mod%i]*(mod-mod/i)%mod;
ifac[0]=1;
for(int i=1;i<=n;i++)ifac[i]=1ll*ifac[i-1]*ifac[i]%mod;
pw[0]=1;
for(int i=1;i<=n;i++)pw[i]=mod-pw[i-1];
}
int n,A[N],B[N];
int a[2],b[2];
void calc(int *S,int *arr)
{
for(int i=0;i<=n;i++)
{
int W=1ll*S[i]*pw[n-i]%mod*ifac[i]%mod*ifac[n-i]%mod;
int inv=mod-(1ll*n*(n+1)%mod*inv2-i+mod)%mod;
arr[0]=(arr[0]+W)%mod;
arr[1]=(arr[1]+1ll*W*inv%mod)%mod;
}
}
int Pow(int a,int b)
{
int res=1;
while(b)
{
if(b&1)res=1ll*res*a%mod;
a=1ll*a*a%mod;
b>>=1;
}
return res;
}
int main()
{
cin>>n;
init(n);
for(int i=0;i<=n;i++)scanf("%d",&A[i]);
for(int i=0;i<=n;i++)scanf("%d",&B[i]);
calc(A,a);calc(B,b);
int s=1ll*(b[1]-a[1]+mod)%mod*Pow(1ll*n*a[0]%mod,mod-2)%mod;
cout<<s;
return 0;
}
\(\texttt{D. Toy Machine}\)
找规律！
#include<bits/stdc++.h>
using namespace std;
int main()
{
int n,k;
scanf("%d %d",&n,&k);
int m=n/2;
if(k<=m)
{
for(int i=1;i<k;i++)printf("LDRU");
printf("L\n");
return 0;
}
k=n-k-1;
for(int i=1;i<k;i++)printf("RDLU");printf("R");
for(int i=1;i<=m;i++)printf("RDRU");printf("LU");
for(int i=1;i<m;i++)printf("LDRU");printf("L");
return 0;
}
\(\texttt{E. Half-sum}\)
完全不会。
首先，显然 \(|A-B|=max(A-B,B-A)\)，因此就是找出两个集合使得差最大，不放设我们要最大化 \(B-A\)
那么显然，\(B\)里面的数越大越好，因此把序列排序，一定一个前缀是 \(A\)，剩下的是 \(B\)。
对于一个有序的\(B\)，显然越大的数被合并次数越少越好，因此从小到大合并，A就反过来。
因此有一个 \(O(n^2)\) 的做法就是枚举分界点 \(i\)，分成 \([1,i-1],[i,n]\)，然后乘上 \(2^n\)，比大小。
设 \(b_{i}=a_{i}-a_{i-1}\)，可以得出答案从 \(i\to j\) 的变化量 \(D_{i\to j}=-\frac{b_i}{2^{i-1}}+\sum_{k=i+1}^{j-1}b_k(\frac{1}{2_{n-k+1}}-\frac{1}{2^{k-1}})+\frac{b_j}{2^{n-j+1}}\)，对于 \(j\leq \frac{n}{2}\)，中间部分显然小于0，因此若\(\frac{b_i}{2^{i-1}}\geq \frac{b_j}{2^{n-j+1}}\)，就会\(\leq 0\)，注意到 \(b_i\) 的影响最多30，因此我们检查一下前 \(30\) 个\(b_i\neq 0\) 的位置和后 30 个就好了。
// LUOGU_RID: 110350855
#include<bits/stdc++.h>
using namespace std;
const int N = 1e6+100;
const int mod = 1e9+7;
int Pow(int a,int b)
{
int res=1;
while(b)
{
if(b&1)res=1ll*res*a%mod;
a=1ll*a*a%mod;
b>>=1;
}
return res;
}
int a[N],now[N],ans[N];
int n;
void calc(int x)
{
for(int i=0;i<=n+51;i++)now[i]=0;
for(int i=1;i<=x;i++)
{
int C;
if(i==x)C=i-1;
else C=i;
for(int j=0;j<30;j++)
now[-C+n+j]-=((a[i]>>j)&1);
}
for(int i=x+1;i<=n;i++)
{
int C;
if(i==x+1)C=n-i;
else C=n-i+1;
for(int j=0;j<30;j++)
now[-C+n+j]+=((a[i]>>j)&1);
}
for(int i=0;i<=n+50;i++)
{
while(now[i]< 0)now[i+1]--,now[i]+=2;
while(now[i]>=2)now[i+1]++,now[i]-=2;
}
if(now[n+51]<0)return;
for(int i=n+50;i>=0;i--)
if(now[i]!=ans[i])
{
if(now[i]>ans[i])
{
for(int j=0;j<=n+50;j++)
ans[j]=now[j];
}
return;
}
}
void solve()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)scanf("%d",&a[i]);
for(int i=0;i<=n+50;i++)ans[i]=0;
sort(a+1,a+n+1);
for(int i=2,C=30;i<=n&&C;i++)if(a[i]!=a[i-1])calc(i-1),C--;
for(int i=n,C=30;i>=2&&C;i--)if(a[i]!=a[i-1])calc(i-1),C--;
int res=0;
for(int i=0;i<=n+50;i++)
if(ans[i])res=(res+Pow(2,i-n+mod-1))%mod;
printf("%d\n",res);
}
int main()
{
int T;
cin>>T;
while(T--)
{
solve();
}
return 0;
}
\(\texttt{F. Entangled Substrings}\)
第一个自己做出来的 \(3500\)，虽然比较水。
建出 \(\text{SAM}\)，考虑两个结点\(x,y\)什么时候会产生贡献。
那么，首先，他们的 \(endpos-fstpos\) 序列应该是相同的。
其次，从 \(y\) 的出现位置到 \(x\) 出现位置之间的所有位置都应该和 \(y\) 等价，也就是说。
\(fstpos_x\in [fstpos_y-len_y+1,fstpos_y-len_{fa_y}]\)
用字符串哈希维护 \(endpos-fstpos\)，对于每一个相同的结点计划，按照 \(fstpos\) 排序，然后对于每个 \(y\)，符合条件的都是一个区间，记录前缀和就好了。
// LUOGU_RID: 110085760
#include<bits/stdc++.h>
using namespace std;
const int N = 2e5+7;
int tr[N][26],len[N],fa[N],tot=1,last=1,fstpos[N];
typedef long long LL;
typedef unsigned long long ULL;
void copy(int x,int y)
{
fa[x]=fa[y];
len[x]=len[y];
fstpos[x]=fstpos[y];
for(int c=0;c<26;c++)
tr[x][c]=tr[y][c];
}
ULL P[N],H[N];
const ULL Base = 13331;
void Extend(int x,int c)
{
int p=last,np=last=++tot;
len[np]=len[p]+1;
fstpos[np]=x;
H[np]=1;
while(p&&!tr[p][c])
{
tr[p][c]=np;
p=fa[p];
}
if(!p)fa[np]=1;
else
{
int q=tr[p][c];
if(len[q]==len[p]+1)fa[np]=q;
else
{
int nq=++tot;
copy(nq,q);
len[nq]=len[p]+1;
fa[np]=fa[q]=nq;
while(p&&tr[p][c]==q)
{
tr[p][c]=nq;
p=fa[p];
}
}
}
}
char s[N];
int n;
struct edge
{
int y,next;
}e[2*N];
int link[N],t=0;
void add(int x,int y)
{
e[++t].y=y;
e[t].next=link[x];
link[x]=t;
}
void dfs(int x)
{
for(int i=link[x];i;i=e[i].next)
{
int y=e[i].y;
dfs(y);
if(x>1)H[x]=H[x]+H[y]*P[fstpos[y]-fstpos[x]];
}
}
int seq[N],m=0;
map<ULL,vector<int> > G;
bool cmp(int x,int y)
{
return fstpos[x]<fstpos[y];
}
LL sumL[N],sumF[N];
int get(int D)
{
int l=1,r=m,mid,pos=0;
while(l<=r)
{
mid=(l+r)>>1;
if(fstpos[seq[mid]]<=D)
{
pos=mid;
l=mid+1;
}
else r=mid-1;
}
return pos;
}
int main()
{
scanf("%s",s+1);
n=strlen(s+1);
P[0]=1;
for(int i=1;i<=n;i++)P[i]=P[i-1]*Base;
for(int i=1;i<=n;i++)Extend(i,s[i]-'a');
for(int i=2;i<=tot;i++)add(fa[i],i);
dfs(1);
LL ans=0;
for(int i=2;i<=tot;i++)G[H[i]].push_back(i);
for(auto U:G)
{
m=0;
for(auto u:U.second)seq[++m]=u;
sort(seq+1,seq+m+1,cmp);
for(int i=1;i<=m;i++)
{
int x=seq[i];
sumL[i]=sumL[i-1]+len[x]-len[fa[x]];
sumF[i]=sumF[i-1]+1ll*(len[x]-len[fa[x]])*fstpos[x];
}
for(int i=1;i<=m;i++)
{
int x=seq[i];
int l=len[fa[x]]+1,r=len[x];
int L=get(fstpos[x]-r-1),R=get(fstpos[x]-l);
ans+=1ll*(sumL[R]-sumL[L])*(fstpos[x]-len[fa[x]])-(sumF[R]-sumF[L]);
}
}
cout<<ans;
return 0;
}