AtCoder 五十连练 第三练
D - Snuke Panic (1D)
高桥正试图抓住许多 Snuke。
有五个坑在坐标 \(0,1,2,3,4\) 号线，连接到 Snuke 的巢。现在，\(N\) 个 Snuke 会出现。第 \(i\) 只 Snuke 将在 \(T_i\) 出现在坐标 \(X_i\)，其大小为 \(A_i\)。高桥在时间为 \(0\) 时的坐标为 \(0\)，在直线上每个单位时间可以移动距离为 \(1\)。
当且仅当 Snuke 在 \(T_i\) 时刻出现时，高桥刚好在那个坑的坐标处，他才能抓住一个从坑中出现的 Snuke。所花费的时间 Snuke 可以忽略不计。
找出高桥能捕捉到的 Snuke 的最大大小之和。
数据范围：\(1 \le N \le 10^5\)。
设 \(dp[i][j]\) 表示时刻 \(i\)，高桥在第 \(j\) 号坑能抓到的最大大小。显然可以从第 \(i-1\) 的时刻的第 \(j-1\) 或 \(j+1\) 的坑转移过来，消除后效性，\(j\) 放在里层循环，每次加上在第 \(T_i\) 时刻出现在 \(X_i\) 的 Snuke 的大小 \(A_i\) 就可以了。
Code.
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e5+10;
int f[N][10],x[N],w[N],n,res;
signed main()
{
scanf("%lld",&n);
for(int i=1,t,pl,yl;i<=n;i++)
{
scanf("%lld%lld%lld",&t,&pl,&yl);
x[t]=pl; w[t]=yl;
}
for(int i=1;i<=4;i++) f[0][i]=-INT_MAX;
for(int i=1;i<=100000;i++)
{
for(int j=0;j<=4;j++)
{
f[i][j]=f[i-1][j];
if(j != 0) f[i][j]=max(f[i][j],f[i-1][j-1]);
if(j != 4) f[i][j]=max(f[i][j],f[i-1][j+1]);
}
f[i][x[i]]+=w[i];
}
for(int i=0;i<=4;i++) res=max(res,f[100000][i]);
printf("%lld",res);
return 0;
}
E - Throwing the Die
让我们玩一个用骰子的游戏。游戏最多包含 \(N\) 个回合，每个回合都如下所示。
投掷一个六面骰子，显示\(1,...,6\)，概率相等，让 \(X\) 是显示的数字(每次投掷都是独立的)。
如果现在是第 \(n\) 轮，你的分数是 \(X\)，游戏结束。否则，选择是继续还是结束游戏。如果你结束游戏，你的分数是 \(X\)，并且没有更多回合。
当你玩游戏时找出你的分数的期望值，使这个期望值最大化。
数据范围：\(1 \le N \le 100\)。
期望贪心题，显然，针对当前期望轮数第 \(i\) 轮，如果本次得分小于第 \(i-1\) 轮的期望得分，我们就没必要丢了，直接继承第 \(i-1\) 轮的期望，概率为六分之一，否则就加上本轮的点数乘六分之一就可以了。
Code.
#include<bits/stdc++.h>
using namespace std;
const int N=110;
double f[N]; int n;
int main()
{
f[1]=3.50000; scanf("%d",&n);
for(int i=2;i<=n;i++)
for(int j=1;j<=6;j++)
{
if(j < f[i-1]) f[i]+=1.0*(f[i-1])/6.0;
else f[i]+=1.0*j/6.0;
}
printf("%.8lf",f[n]);
return 0;
}
F - Well-defined Path Queries on a Namori
给定一个连通的简单无向图 \(G\)，有 \(N\) 个顶点，编号为 \(1\) 到 \(N\)，有 \(N\) 条边。第 \(i\) 条边双向连接顶点 \(u_i\) 和顶点 \(v_i\)。
\(Q\) 次询问，回答问题。确定从顶点 \(x_i\) 到顶点 \(y_i\) 是否存在唯一的简单路径(简单路径是没有顶点重复的路径)。
数据范围：\(3 \le N \le 2 \times 10^5\)。
基环树找环染色问题，把每个环上的点当作根节点都可以往底下形成一颗树，在同一颗树上的点显然只有一条简短路径，无向基环树找环，自己琢磨了一个拓扑排序，在环上的点之中做不到入度减为 \(1\)，所以可以直接拓扑时用一个 \(st\) 数组标记。
Code.
#include<bits/stdc++.h>
using namespace std;
const int N=2e5+10;
int h[N],ne[N<<1],e[N<<1],idx,n,Q,col[N],in[N],st[N],cnt,din[N]; queue<int> q;
void add(int u,int v) {ne[++idx]=h[u],e[idx]=v,h[u]=idx;}
void dfs(int u)
{
col[u]=cnt;
for(int i=h[u];~i;i=ne[i])
{
int j=e[i]; if(st[j] || col[j]) continue ;
dfs(j);
}
}
int main()
{
memset(h,-1,sizeof h); scanf("%d",&n);
for(int i=1,u,v;i<=n;i++) {scanf("%d%d",&u,&v); add(u,v); add(v,u); din[u]++; din[v]++;}
for(int i=1;i<=n;i++) st[i]=1;
for(int i=1;i<=n;i++)
if(din[i] == 1) q.push(i);
while(! q.empty())
{
int u=q.front(); q.pop(); st[u]=0;
for(int i=h[u];~i;i=ne[i])
{
int j=e[i]; if(! st[j]) continue ;
din[j]--; if(din[j] == 1) q.push(j);
}
}
for(int i=1;i<=n;i++) {if(! st[i]) continue ; ++cnt; dfs(i);}
scanf("%d",&Q);
while(Q -- )
{
int u,v; scanf("%d%d",&u,&v);
puts(col[u] == col[v] ? "Yes" : "No");
}
return 0;
}
G - Yet Another RGB Sequence
已知整数 \(R, G, B\) 和 \(K\)，有多少由 \(R,G\) 和 \(B\) 组成的字符串 \(S\) 满足下面的所有条件？答案对 \(998244353\) 取模。
\(R,G\) 和 \(B\) 在 \(S\) 中出现的次数分别为 \(R,G\) 和 \(B\)。\(RG\) 作为(连续的)子串出现在 \(S\) 中的次数是 \(K\)。
数据范围：\(1 \le R,G,B \le 10^6\)。
组合数题，太麻烦了，所以摆烂了。
Code.
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=2e6+10,M=2e6,mod=998244353;
int r,g,b,k,fin[N],ifin[N];
int ksm(int a,int b)
{
int res=1;
while(b)
{
if(b&1) res=(res*a)%mod;
a=(a*a)%mod; b>>=1;
}
return res;
}
int C(int n,int k)
{
if(k < 0 || k > n) return 0;
return fin[n]*ifin[k]%mod*ifin[n-k]%mod;
}
signed main()
{
cin>>r>>g>>b>>k; fin[0]=1;
for(int i=1;i<=M;i++) fin[i]=(fin[i-1]*i)%mod;
ifin[M]=ksm(fin[M],mod-2)%mod;
for(int i=M;i>=1;i--) ifin[i-1]=(ifin[i]*i)%mod;
cout<<C(b+g,b)*C(g,k)%mod*C(b+r,r-k)%mod;
return 0;
}