Codeforces Round #423 (Div. 1, rated, based on VK Cup Finals)
CF827A String Reconstruction
洛谷传送门
CF827A
分析
考虑维护每个左端点通过一个区间覆盖到的最大右端点，然后直接双指针铺一下就可以了
代码
#include
#include
#include
using namespace std;
const int N=1000011;
char s[N]; int mx,m,len[N],r[N],L[N];
int iut(){
int ans=0; char c=getchar();
while (!isdigit(c)) c=getchar();
while (isdigit(c)) ans=ans*10+c-48,c=getchar();
return ans;
}
int main(){
m=iut();
for (int i=1;i<=m;++i){
scanf("%s",s+r[i-1]+1);
len[i]=strlen(s+r[i-1]+1);
r[i]=r[i-1]+len[i];
for (int j=iut();j;--j){
int x=iut();
if (mx CF827B High Load
洛谷传送门
CF827B
分析
类似于菊花图直接构造出长度相近的 \(k\) 条链，这样一定是最优的
代码
#include
using namespace std;
int n,m,ans;
int main(){
ios::sync_with_stdio(0);
cin>>n>>m,ans=(n-1+m-1)/m*2;
if ((n-1)%m==1) --ans;
cout< CF827C DNA Evolution
洛谷传送门
CF827C
分析
因为长度只有十，所以根据模数和余数直接开 \(\frac{10*(10-1)}{2}=45\) 棵线段树维护区间字母个数即可
理论上的空间为 \(O((n+m)\log n)\)
代码
#include
#include
#include
using namespace std;
const int N=100011; char s[N];
int w[N<<6][4],ls[N<<6],rs[N<<6],a[N],n,cnt,rt[11][11];
int iut(){
int ans=0; char c=getchar();
while (!isdigit(c)) c=getchar();
while (isdigit(c)) ans=(ans<<3)+(ans<<1)+(c^48),c=getchar();
return ans;
}
void print(int ans){
if (ans>9) print(ans/10);
putchar(ans%10+48);
}
int rk(char ch){
if (ch=='A') return 0;
else if (ch=='T') return 1;
else if (ch=='G') return 2;
else return 3;
}
void update(int &rt,int l,int r,int x,int y,int z){
if (!rt) rt=++cnt; w[rt][y]+=z;
if (l==r) return;
int mid=(l+r)>>1;
if (x<=mid) update(ls[rt],l,mid,x,y,z);
else update(rs[rt],mid+1,r,x,y,z);
}
int query(int rt,int l,int r,int x,int y,int z){
if (!rt) return 0;
if (l==x&&r==y) return w[rt][z];
int mid=(l+r)>>1;
if (y<=mid) return query(ls[rt],l,mid,x,y,z);
else if (x>mid) return query(rs[rt],mid+1,r,x,y,z);
else return query(ls[rt],l,mid,x,mid,z)+query(rs[rt],mid+1,r,mid+1,y,z);
}
int main(){
scanf("%s",s+1),n=strlen(s+1);
for (int i=1;i<=n;++i){
a[i]=rk(s[i]);
for (int j=1;j<=10;++j)
update(rt[j][i%j],1,n,i,a[i],1);
}
for (int T=iut();T;--T){
int opt=iut();
if (opt==1){
int x=iut(),y=rk(getchar());
for (int j=1;j<=10;++j){
update(rt[j][x%j],1,n,x,a[x],-1);
update(rt[j][x%j],1,n,x,y,1);
}
a[x]=y;
}else{
int l=iut(),r=iut(),len,ans=0;
scanf("%s",s+1),len=strlen(s+1);
if (len>r-l+1) len=r-l+1;
for (int j=1;j<=len;++j)
ans+=query(rt[len][(l+j-1)%len],1,n,l,r,rk(s[j]));
print(ans),putchar(10);
}
}
return 0;
}
CF827D Best Edge Weight
洛谷传送门
CF827D
分析
先建出一棵最小生成树，观察到非树边的最大边权就是树上路径最大边权减一，这个可以用倍增(ST表)来维护。
然后树边的最大边权就是所有经过它的非树边的最小边权减一，如果没有非树边就是-1，这个可以用逆ST表来维护。
代码
#include
#include
#include
#include
using namespace std;
const int N=200011; struct node{int y,rk,next;}e[N<<1]; struct rec{int x,y,w;}a[N];
int f[N][18],g[N][18],dp[N][18],F[N],dep[N],et=1,ans[N],rk[N],n,m,as[N],cho[N]; bool tree[N];
int iut(){
int ans=0; char c=getchar();
while (!isdigit(c)) c=getchar();
while (isdigit(c)) ans=ans*10+c-48,c=getchar();
return ans;
}
void print(int ans){
if (ans<0) ans=-ans,putchar('-');
if (ans>9) print(ans/10);
putchar(ans%10+48);
}
void Min(int &x,int y){x=xa[y].w?x:y;}
void dfs(int x,int fa){
for (int I=0;I<17&&f[x][I];++I)
f[x][I+1]=f[f[x][I]][I],
g[x][I+1]=Get(g[x][I],g[f[x][I]][I]);
for (int i=as[x];i;i=e[i].next)
if (e[i].y!=fa){
f[e[i].y][0]=x,g[e[i].y][0]=e[i].rk;
dep[e[i].y]=dep[x]+1,dfs(e[i].y,x);
}
}
int lca(int x,int y){
if (dep[x] CF827E Rusty String
洛谷传送门
CF827E
分析
往右移动 \(d\) 步重合那么它一定有一个长度为 \(n-1-d\) 的Border（通配符）
不如先用通配符的方法，那就是 \(S[i]\) 和 \(S[n-x+i]\) 匹配，
把后面这个字符串反转成 \(S'[n-1-(n-x+i)]\) 也就是 \(S'[x-1+i]\)
多项式乘法后的项被放在了 \(x-1\)，匹配函数就是 \((S[i]-S[j])^2S[i]S[j]\)
直接三次多项式乘法就可以了，这里写的是NTT
然后发现样例都过不了，是因为上面的是充分不必要条件，因为未知字符并不是通配符，
所以如果 \(kd\) 的 Border不对，那么 \(d\) 的Border也不对，再 \(O(n\log n)\) 判断一下就可以了
代码
#include
#include
#include
#include
#include
#define mem(f,n) memset(f,0,sizeof(int)*(n))
#define cpy(f,g,n) memcpy(f,g,sizeof(int)*(n))
using namespace std;
const int mod=998244353,i3=(mod+1)/3,i2=(mod+1)/2,N=500011;
typedef long long lll; typedef unsigned long long ull;
int n,Gmi[31],Imi[31],a[N],b[N],Ans[N],period[N],len,ff[N<<2],gg[N<<2],tt[N<<2];
int iut(){
int ans=0; char c=getchar();
while (!isdigit(c)) c=getchar();
while (isdigit(c)) ans=(ans<<3)+(ans<<1)+(c^48),c=getchar();
return ans;
}
void print(int ans){
if (ans>9) print(ans/10);
putchar(ans%10+48);
}
int ksm(int x,int y){
int ans=1;
for (;y;y>>=1,x=1ll*x*x%mod)
if (y&1) ans=1ll*ans*x%mod;
return ans;
}
namespace Theoretic{
int rev[N<<2],LAST; ull Wt[N<<2],F[N<<2];
void Pro(int n){
if (LAST==n) return; LAST=n,Wt[0]=1;
for (int i=0;i>1]>>1)|((i&1)?n>>1:0);
}
void NTT(int *f,int n,int op){
Pro(n);
for (int i=0;i CF827F Dirty Arkady's Kitchen
洛谷传送门
CF827F
分析
无向边的话，人可以一直在这条边上反复横跳，那么一个点理应要被拆成奇点和偶点。
设 \(dis[x][0/1]\) 表示从起点走到 \(x\) 的步数为偶数/奇数步时的最晚时间
然后将无向边拆成奇数特供和偶数特供，把它们丢进一个按照最早通过时间排序
如果当前的最晚时间不能满足的话，就先把它丢进一个延迟放入的数组里，等到有其它边启动时再将这条边启动。
这样小根堆里最多只会有 \(O(m)\) 条边，所以时间复杂度为 \(O(m\log m)\)
代码
#include
#include
#include
#include
using namespace std;
const int N=500011;
struct rec{
int x,y,l,r;
bool operator <(const rec &t)const{
return l>t.l;
}
};
vectore[N][2];
priority_queueq;
int n,m,dis[N][2];
int iut(){
int ans=0; char c=getchar();
while (!isdigit(c)) c=getchar();
while (isdigit(c)) ans=ans*10+c-48,c=getchar();
return ans;
}
int max(int a,int b){return a>b?a:b;}
int main(){
n=iut(),m=iut();
if (n==1) return !printf("0");
for (int i=1;i<=m;++i){
int x=iut(),y=iut(),l=iut(),r=iut()-1,opt=(r-l)&1;
if (l=t.l){
if (t.y==n) return !printf("%d",t.l+1);
if (dis[t.y][opt^1]<=t.r){
dis[t.y][opt^1]=t.r+1;
int len=e[t.y][opt^1].size();
for (int i=0;i