今天题比较简单的一次。T1 数组爆了是我小丑。
为啥离线测的时候 T2 t 了啊。我题库上边跑 1300ms 也挺健康的吧。
居然 nealchen 老师的课件。
EmoCosine！这曲曲绘输血袋插耳机上）
图案
原题：CF526D。
发现 \(k+1\) 个 \(B\) 和 \(k\) 个 \(A\) 交错排列可以换个形式：\(k\) 个 \(X\) 跟着一个 \(X\) 的前缀。那么枚举 \(X\) 的长度，暴力判每个前缀是否是 \(k\) 个 \(X\)，然后哈希 + 二分跑一下后边前缀的长度就行了。当然得到了合法区间之后直接覆盖大概复杂度会爆炸，差分一下就行了。
注意二分的时候的右端点不要飞出去。
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
using namespace std;
const int mod=1000000007,prm=131;
int n,k,hs[1000010],p[1000010];
char s[1000010];
int ans[1000010];
int geths(int l,int r){
return (hs[r]-1ll*hs[l-1]*p[r-l+1]%mod+mod)%mod;
}
int main(){
scanf("%d%d%s",&n,&k,s+1);p[0]=1;
for(int i=1;i<=n;i++){
p[i]=1ll*p[i-1]*prm%mod;
hs[i]=(1ll*hs[i-1]*prm+s[i])%mod;
}
for(int i=1;i<=n/k;i++){
bool jud=true;
for(int j=1;j<=k;j++){
int l=i*(j-1)+1,r=i*j;
if(geths(1,i)!=geths(l,r)){
jud=false;break;
}
}
if(!jud)continue;
int l=0,r=min(i,n-i*k);
while(l<r){
int mid=(l+r+1)>>1;
if(geths(1,mid)==geths(i*k+1,i*k+mid))l=mid;
else r=mid-1;
}
ans[i*k]++;ans[i*k+r+1]--;
}
for(int i=1;i<=n;i++){
ans[i]+=ans[i-1];
putchar(ans[i]?'1':'0');
}
puts("");
return 0;
}
树点购买
半个原题：CF1120D。
题解说的贪心是啥啊。
首先发现假如子树有 \(a\) 个叶子，那么我们只要唯一确定 \(a-1\) 个叶子的值以及它们的和就可以得到剩下一个叶子的值。
于是设 \(dp_{x,0/1}\) 为 \(x\) 的子树确定的叶子个数为 \(a-1/a\) 的最小代价。转移：
- \(dp_{x,0}\)：子树选一个 \(dp_{v,0}\)，剩下的都是 \(dp_{v,1}\)。
- \(dp_{x,1}\)：从 \(dp_{x,0}+c_x\) 得到，或者子树都是 \(dp_{x,1}\)。
于是第一问就做完了。容易根据第一问得到第三问方案数。
然后考虑第二问怎么做。发现我们得到 \(dp\) 数组之后根据 \(dp\) 的过程倒着往回搜一遍就可以得到哪些 \(c_x\) 是可能被选的。
快速幂这个 \(\log\) 会导致离线评测 T 掉吗？不是很懂。反正无论如何都是模拟省选 D2 翻盘。啊我翻不了盘那没事了。
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
const int mod=998244353;
int n,k,c[1000010];
struct node{
int v,next;
}edge[2000010];
int t,head[1000010];
void add(int u,int v){
edge[++t].v=v;edge[t].next=head[u];head[u]=t;
}
int qpow(int a,int b){
int ans=1;
while(b){
if(b&1)ans=1ll*ans*a%mod;
a=1ll*a*a%mod;
b>>=1;
}
return ans;
}
long long dp[1000010][2];
int g[1000010][2];
bool v[1000010];
void dfs(int x,int f){
long long sum=0,mul=1;dp[x][0]=dp[x][1]=0x3f3f3f3f3f3f3f3f;
int cnt=0;
for(int i=head[x];i;i=edge[i].next){
if(edge[i].v!=f){
cnt++;
dfs(edge[i].v,x);
sum+=dp[edge[i].v][1];
mul=1ll*mul*g[edge[i].v][1]%mod;
}
}
if(!cnt)dp[x][1]=c[x],dp[x][0]=0,g[x][0]=g[x][1]=1;
else{
dp[x][1]=sum;g[x][1]=mul;
int ret=1;
for(int i=head[x];i;i=edge[i].next){
if(edge[i].v!=f){
if(dp[x][0]>sum-dp[edge[i].v][1]+dp[edge[i].v][0]){
dp[x][0]=sum-dp[edge[i].v][1]+dp[edge[i].v][0];
ret=1ll*mul*qpow(g[edge[i].v][1],mod-2)%mod*g[edge[i].v][0]%mod;
}
else if(dp[x][0]==sum-dp[edge[i].v][1]+dp[edge[i].v][0]){
ret=(ret+1ll*mul*qpow(g[edge[i].v][1],mod-2)%mod*g[edge[i].v][0])%mod;
}
}
}
g[x][0]=ret;
if(dp[x][1]>dp[x][0]+c[x]){
dp[x][1]=dp[x][0]+c[x];g[x][1]=g[x][0];
}
else if(dp[x][1]==dp[x][0]+c[x]){
g[x][1]=(g[x][1]+g[x][0])%mod;
}
}
}
bool vis[1000010][2];
void dfs2(int x,int f,int od){
if(vis[x][od])return;
vis[x][od]=true;
long long sum=0;
for(int i=head[x];i;i=edge[i].next){
if(edge[i].v!=f)sum+=dp[edge[i].v][1];
}
if(od){
if(dp[x][1]==sum){
for(int i=head[x];i;i=edge[i].next){
if(edge[i].v!=f)dfs2(edge[i].v,x,1);
}
}
if(dp[x][1]==dp[x][0]+c[x])v[x]=true,od=0;
}
if(!od){
vis[x][od]=true;
vector<int>son;
for(int i=head[x];i;i=edge[i].next){
if(edge[i].v==f)continue;
if(dp[x][0]==sum-dp[edge[i].v][1]+dp[edge[i].v][0])dfs2(edge[i].v,x,0),son.push_back(edge[i].v);
else dfs2(edge[i].v,x,1);
}
if(son.size()>1){
for(int v:son)dfs2(v,x,1);
}
}
}
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++)scanf("%d",&c[i]);
for(int i=1;i<n;i++){
int u,v;scanf("%d%d",&u,&v);
add(u,v);add(v,u);
}
scanf("%d",&k);
dfs(1,0);
printf("%lld\n",dp[1][1]);
if(k>=2){
dfs2(1,0,1);
for(int i=1;i<=n;i++)if(v[i])printf("%d ",i);puts("");
}
if(k>=3)printf("%d\n",g[1][1]);
return 0;
}
舰队游戏
原题 ARC016D。
看 A 老师博客看见过这题。当时没怎么注意，导致场上就只记得是个二分。推了半天结果没写完。
首先一个显然的 \(dp\) 是设 \(dp_{x,i}\) 为 \(x\) 点 \(i\) 血到终点的期望步数，则
\[dp_{x,i}=\min(dp_{1,H}+H-i,\frac 1d\sum_{v}dp_{v,i-d_v}+1)
\]
然而这个会在 \(dp_{1,H}\) 出环。既然这个只在 \(dp_{1,H}\) 出环，那直接给他钦定一个数，然后嗯转移，完事看看是不是相等。
设钦定为 \(x\) 的时候得到是 \(dp_{1,H}=f(x)\)，那么显然 \(f'(x)\le 1\)，那就可以二分 \(f(x)-x=0\) 的地方。
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <queue>
#include <vector>
using namespace std;
const double eps=1e-8;
int n,m,H,d[110];
double dp[110][110];
struct node{
int v,next;
}edge[10010];
int t,head[110];
void add(int u,int v){
edge[++t].v=v;edge[t].next=head[u];head[u]=t;
}
bool v[110];
void dfs(int x,double mid){
v[x]=true;
int deg=0;
for(int i=head[x];i;i=edge[i].next){
deg++;
if(!v[edge[i].v])dfs(edge[i].v,mid);
for(int j=1;j<=H;j++){
if(j<=d[edge[i].v])dp[x][j]=1e12;
else dp[x][j]+=dp[edge[i].v][j-d[edge[i].v]];
}
}
if(x==n){
for(int i=1;i<=H;i++)dp[x][i]=0;
}
else{
if(!deg){
for(int i=1;i<H;i++)dp[x][i]=mid-i+H;
if(x==1)dp[x][H]=1e12;
else dp[x][H]=mid;
}
else{
for(int i=1;i<=H;i++){
if(x==1&&i==H)dp[x][i]=1+dp[x][i]/deg;
else dp[x][i]=min(1+dp[x][i]/deg,mid-i+H);
}
}
}
}
double check(double mid){
memset(v,false,sizeof(v));
memset(dp,0,sizeof(dp));
dfs(1,mid);
if(!v[n])return 1e12;
return dp[1][H];
}
int main(){
scanf("%d%d%d",&n,&m,&H);
for(int i=1;i<=m;i++){
int u,v;scanf("%d%d",&u,&v);add(u,v);
}
for(int i=1;i<=n;i++)scanf("%d",&d[i]);
double l=0,r=1e6+1;
while(l+eps<r){
double mid=(l+r)/2;
if(check(mid)<=mid)r=mid;
else l=mid;
}
if(l>1e6)puts("-1");
else printf("%.6lf\n",l);
return 0;
}