「LibreOJ NOIP Round #1」DNA 序列
注意到 \(k=10\)，\(|\Sigma|=4\)，故本质不同的子串个数只有 \(4^10\) 种，可以直接压位存下来。
时间复杂度 \(O(nk)\)。
Code
const int N=5e6+5;
char ch[N];
int n,K,bl[N];
int turn(char ch) {
if(ch=='A') return 0;
if(ch=='C') return 1;
if(ch=='G') return 2;
if(ch=='T') return 3;
assert(0);
}
int main() {
scanf("%s",ch+1);
scanf("%d",&K);
n=strlen(ch+1);
int ans=0;
FOR(i,1,n-K+1) {
int sum=0;
FOR(j,1,K) sum=4*sum+turn(ch[i+j-1]);
bl[sum]++,ans=max(ans,bl[sum]);
}
printf("%d\n",ans);
}
「LibreOJ NOIP Round #1」数列递推
注意到当 \(a_{i+1},a_{i}\) 同号时序列单增/单减，故考虑暴力递推直到序列单增单减，特殊记录前面的答案即可。
可以证明前面只有 \(\log a_i\) 项，故时间复杂度 \(O(T\log a_i)\)。
Code
const int M=3e5+5;
const __int128 inf=1e18;
int v[M];
map<int,int> app;
int main() {
int m;scanf("%d",&m);
FOR(i,1,m) scanf("%d",&v[i]),app[v[i]]=1;
int q;scanf("%d",&q);
while(q--) {
int a0,a1,k;
scanf("%d %d %d",&a0,&a1,&k);
if(a0==0&&a1==0) {
printf("%d %d\n",v[1],v[1]);
continue;
}
__int128 a=a0,b=a1,c,ma=-inf,mi=inf;
int o1=0,o2=0,i,op;
if(app[0]) ma=mi=a0;
if(app[1]) {
if(ma<a1) ma=a1,o1=1;
if(mi>a1) mi=a1,o2=1;
}
for(i=2;;i++) {
c=a+b*k;
if(c>inf||c<-inf) {
if(c>inf&&i<v[m]) o1=v[m];
else if(i<v[m]) o2=v[m];
break;
}
if(app[i]) {
if(ma<c) ma=c,o1=i;
if(mi>c) mi=c,o2=i;
}
a=b,b=c;
}
if(o1==0) o1=v[1];
if(o2==0) o2=v[1];
printf("%d %d\n",o1,o2);
}
}
「LibreOJ NOIP Round #1」旅游路线
考虑 DP，记 \(f_{u,i}\) 表示现在在 \(u\)，手里有 \(i\) 块钱，准备在 \(u\) 这个位置加油，可以得到的最大路程，有转移：
\[f_{u,i}=\max_v (f_{v,i-p_u}+w_{u,v,\min(C,c_u)}) \]其中 \(w_{u,v,i}\) 表示从 \(u\) 到 \(v\) 至多走 \(i\) 步得到的最大路程。
注意到对于任意一个 \(u\)，\(\min(C,c_u)\) 是固定的，考虑使用倍增来加速这个求的过程，记 \(g_{u,v,d}\) 表示 \(u\) 到 \(v\) 走至多 \(2^d\) 步的最大路程，有转移：
\[g_{u,v,d}=\max(g_{u,v,d-1},\max_x(g_{u,x,d}+g_{x,v,d})) \]那么 \(w\) 也可以转移出来：
\[w_{u,v,x}=\max_y(w_{u,y,x-2^k}+g_{y,v,k}) \]DP 即可，询问时二分一下就行。
总时间复杂度 \(O(n^3\log V+n^4+T\log V)\)。
Code
const int N=105,inf=1e9;
int n,m,C,Q;
int p[N],c[N],g[N][N][17],f[N][N*N],w[N][N],a[N],b[N];
int main() {
scanf("%d %d %d %d",&n,&m,&C,&Q);
FOR(i,1,n) {
scanf("%d %d",&p[i],&c[i]);
c[i]=min(c[i],C);
}
FOR(i,1,n) FOR(j,1,n) FOR(k,0,16) g[i][j][k]=-inf;
FOR(i,1,n) g[i][i][0]=0;
FOR(i,1,m) {
int x,y,v;
scanf("%d %d %d",&x,&y,&v);
chkmax(g[x][y][0],v);
}
FOR(k,1,16) FOR(i,1,n) FOR(j,1,n) {
chkmax(g[i][j][k],g[i][j][k-1]);
FOR(x,1,n) chkmax(g[i][j][k],g[i][x][k-1]+g[x][j][k-1]);
}
FOR(i,1,n) {
FOR(j,1,n) a[j]=-inf;
a[i]=0;
FOR(l,0,16) if(c[i]&(1<<l)) {
FOR(j,1,n) b[j]=a[j];
FOR(j,1,n) FOR(k,1,n) chkmax(b[k],a[j]+g[j][k][l]);
FOR(j,1,n) a[j]=b[j];
}
FOR(j,1,n) w[i][j]=a[j];
}
FOR(i,0,n*n) FOR(u,1,n) if(i>=p[u]) FOR(v,1,n) chkmax(f[u][i],f[v][i-p[u]]+w[u][v]);
while(Q--) {
int s,q,d;
scanf("%d %d %d",&s,&q,&d);
int x=lower_bound(f[s],f[s]+q+1,d)-f[s];
if(x>q) puts("-1");
else printf("%d\n",q-x);
}
}
「BalkanOI 2018」Election
将 C 看成 \(1\)，将 T 看成 \(-1\)，问题变为删去若干 T 后使前缀和 \(pre_i\ge 0\)，后缀和 \(suf_i\ge 0\)。
考虑先操作使得前缀和合法，此时的操作是，对于每一个第一次出现的前缀和为 \(-i\)，删去这个字母，操作次数为 \(-\min pre_i\)，此时的 \(suf_i\) 会变化，设变化后的是 \(suf'_i\)，则代价同样是 \(-\min suf'i\)。
尝试求出 \(suf'_{\min}\)，考虑某一个位置 \(p\)，其没被加到的情况是 \(-\min_{i<p}pre_q\)，故其后缀和为 \(suf_p+\min_{i<p}pre_i-pre_{\min}\)。
故答案为 \(-\min_{p<q}(pre_p+suf_q)\)，可以转化为总和减去中间一段，中间一段是最大子段和，线段树维护即可。
时间复杂度 \(O(n\log n)\)。
Code
const int N=5e5+5;
char ch[N];
int val[N];
struct node {int lma,rma,dat,sum;} tr[N*4];
node operator + (node a,node b) {
node ret;
ret.sum=a.sum+b.sum;
ret.lma=max(a.lma,a.sum+b.lma);
ret.rma=max(b.rma,b.sum+a.rma);
ret.dat=max({a.dat,b.dat,a.rma+b.lma});
return ret;
}
void build(int p,int l,int r) {
if(l==r) {
tr[p]={max(val[l],0),max(val[l],0),max(val[l],0),val[l]};
return;
}
int mid=(l+r)>>1;
build(p*2,l,mid),build(p*2+1,mid+1,r);
tr[p]=tr[p*2]+tr[p*2+1];
}
node query(int p,int l,int r,int x,int y) {
if(x<=l&&r<=y) return tr[p];
int mid=(l+r)>>1;
if(x>mid) return query(p*2+1,mid+1,r,x,y);
if(y<=mid) return query(p*2,l,mid,x,y);
return query(p*2,l,mid,x,y)+query(p*2+1,mid+1,r,x,y);
}
int main() {
int n=read();scanf("%s",ch+1);
FOR(i,1,n) {
if(ch[i]=='C') val[i]=1;
else val[i]=-1;
}
build(1,1,n);
int q=read();
while(q--) {
int l=read(),r=read();
node ret=query(1,1,n,l,r);
printf("%d\n",ret.dat-ret.sum);
}
}