【考试总结】2022-04-02
图案
先计算哪些前缀和被分成 \(K\) 个相同的字符串
设某个合法前缀是 \((A)^K\) 那么在 \(i+1\) 开始跟一段 \(A\) 的前缀都是合法的，长度可以使用 \(\rm Z-Function\) 来计算
区间覆盖 \(1\) 我写了树状数组，没细想有没有更快的做法
upd:好像可以使用简单的 差分法 将这题做到不带对数复杂度
Code Display
const int N=1e6+10;
char s[N];
int z[N],n,k;
ull hs[N],pw[N];
bool mark[N];
inline int get(int l,int r){return hs[r]-hs[l-1]*pw[r-l+1];}
struct Fenwick_Tree{
int c[N];
inline void insert(int x,int v){for(;x<=n;x+=x&(-x)) c[x]+=v;}
inline int query(int x){int res=0;for(;x;x-=x&(-x)) res+=c[x]; return res;}
}T;
signed main(){
freopen("pattern.in","r",stdin); freopen("pattern.out","w",stdout);
n=read(); k=read();
scanf("%s",s+1);
pw[0]=1;
rep(i,1,n) pw[i]=pw[i-1]*998244353,hs[i]=hs[i-1]*998244353+s[i];
for(int len=1;len<=n/k;++len){
bool legal=1;
for(int d=2;d<=k;++d){
if(get(1,len)!=get((d-1)*len+1,d*len)){
legal=0;
break;
}
}
mark[len*k]=legal;
}
z[1]=n;
for(int i=2,l=0,r=0;i<=n;++i){
if(i<=r) z[i]=min(z[i-l+1],r-i+1);
while(i+z[i]<=n&&s[z[i]+1]==s[i+z[i]]) ++z[i];
if(i+z[i]-1>r) l=i,r=i+z[i]-1;
}
for(int i=1;i<=n;++i) if(mark[i]){
int mxl=min(z[i+1],i/k);
T.insert(i,1);
T.insert(i+mxl+1,-1);
}
rep(i,1,n) putchar('0'+(bool)T.query(i));
putchar('\n');
return 0;
}
树点购买
前两问可以使用贪心来解决，也就是没棵子树里面剩余一个点不进行覆盖，找到根链上最小值来加到答案里面
第三问不能直接计数，考虑一类和贪心本质一样的 \(\rm DP\) 也就是设 \(f_{x},g_{x}\) 表示是/否全部覆盖的最小花费
转移分别为
\[\begin{aligned}g_x&\leftarrow \sum f_{son}-\max f_{son}-g_{son}\\f_{x}&\leftarrow \min\left\{\sum f_{son},g_{x}+a_x\right\}\end{aligned} \]方案数统计对着上面式子用简单的加法乘法即可
Code Display
const int N=1e6+10;
vector rely[N],G[N];
int n,typ,a[N];
bool cho[N];
int dp[N],node[N],rem[N];
inline void dfs(int x,int fat){
int sum=0,Mx=0;
if(x!=1&&G[x].size()==1){
node[x]=x;
rem[x]=a[x];
return ;
}
for(auto t:G[x]) if(t!=fat){
dfs(t,x);
dp[x]+=dp[t];
if(rem[x]!=rem[t]){
if(rem[x]a[x]) rem[x]=a[x],node[x]=x;
return ;
}
signed main(){
freopen("purtree.in","r",stdin); freopen("purtree.out","w",stdout);
n=read();
rep(i,1,n) a[i]=read();
for(int i=1;i=1){
dfs(1,0);
print(Mn=dp[1]+rem[1]);
putchar('\n');
}
if(typ>=2){
cho[node[1]]=1;
queue q;
rep(i,1,n) if(cho[i]) q.push(i);
while(q.size()){
int fr=q.front(); q.pop();
for(auto t:rely[fr]) if(!cho[t]){
cho[t]=1;
q.push(t);
}
}
rep(i,1,n) if(cho[i]) print(i);
putchar('\n');
}
if(typ>=3){
vector f(n+1),g(n+1);
vector mf(n+1),mg(n+1);
functionDFS=[&](const int x,const int fat){
if(x!=1&&G[x].size()==1){
f[x]=a[x];
mf[x]=mg[x]=1;
return ;
}
vector son;
int Mx=-1e18;
int Multf=1,sigf=0;
for(auto t:G[x]) if(t!=fat){
DFS(t,x);
if(Mx 舰队游戏
设 \(f_{i,j}\) 表示 \(i\) 点还有 \(j\) 的 \(\rm HP\) 想要走到终点的期望步数
转移分成走到后继节点和返回 \(1\) 号点补血两种：
\[f_{i,j}=\min\left\{\frac{1}{deg_i}f_{v,j-d_v},f_{1,H}+H-j\right\} \]此时所有的目光都落到了 \(f_{1,H}\) 上面，那么可以发现所有的 \(f_{i,j}\) 可以表达成 \(kf_{1,H}+b\) 的形式
尝试给 \(f_{1,H}\) 假定权值 \(x\) 并拓扑排序得到 \(f_{1,H}\) 和自己的表达关系，显然要满足 \(k=1,b=0\)
根据实际含义可以发现如果 \(f_{1,H}\) 小于实际值时会趋向于选择第二个决策，而大于实际值时趋向于第二个决策，所以二分答案找到最后一个满足斜率为 \(1\) 的地方即可
Code Display
const int N=110;
vector G[N];
int n,m,d[N],H;
pair dp[N][N];
inline double calc(double V){
for(int i=n-1;i>=1;--i){
int Mx=0;
for(auto t:G[i]) ckmax(Mx,d[t]);
rep(j,1,H){
dp[i][j]={0,0};
if(j<=Mx||!G[i].size()) dp[i][j]={V+1.0*H-j,1.0};
else{
for(auto t:G[i]){
dp[i][j].fir+=dp[t][j-d[t]].fir;
dp[i][j].sec+=dp[t][j-d[t]].sec;
}
dp[i][j].fir/=1.0*G[i].size();
dp[i][j].sec/=1.0*G[i].size();
dp[i][j].fir++;
if(dp[i][j].fir>V+H-j){
dp[i][j].sec=1;
dp[i][j].fir=V+H-j;
}
}
}
}
return dp[1][H].sec;
}
signed main(){
freopen("kancolle.in","r",stdin); freopen("kancolle.out","w",stdout);
n=read(); m=read(); H=read();
for(int i=1;i<=m;++i){
int u=read(),v=read();
G[u].emplace_back(v);
}
rep(i,1,n) d[i]=read();
double l=0,r=1e6,ans=r+1;
if(calc(ans)==1) puts("-1"),exit(0);
while(r-l>1e-9){
double mid=(l+r)/2;
if(calc(mid)<1) r=mid;
else l=mid,ans=mid;
}
printf("%.10lf\n",ans);
return 0;
}