首页 > 其他分享 >AtCoder Beginner Contest 266

AtCoder Beginner Contest 266

时间:2022-09-27 21:37:46浏览次数:70  
标签:AtCoder le Beginner 10 int ifin Snuke 266 mod

AtCoder 五十连练 第三练

AtCoder Beginner Contest 266

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;
}

标签:AtCoder,le,Beginner,10,int,ifin,Snuke,266,mod
From: https://www.cnblogs.com/EastPorridge/p/16736043.html

相关文章

  • AtCoder ABC 270 题解(D-F)
    AtCoderABC270题解(D-F)D-Stones(博弈DP)题目:​ 现在有一堆石子,一个序列a表示每次可以从石头里拿走多少个石子。当无法再拿出石头的时候,游戏结束。两边都以最佳策略......
  • AtCoder Beginner Contest 256
    AtCoder五十连练第二练AtCoderBeginnerContest256D-UnionofInterval给定\(N\)个左闭右开的区间,求这些区间的并集。数据范围:\(1\leN\le2\times10^5\)......
  • AtCoder Beginner Contest 270 G,Ex
    y1s1,G和Ex在推等比数列式子上是相似的。G前置知识:BSGS(其实就是根号讨论)首先我们展开这个递归式:\[X_{i}\equivA^{i}S+\sum_{j=0}^{i-1}A^jB\modP\]感觉第一项有......
  • Atcoder试题乱做 Part2
    感受下来,思维难度有参差,所以还是可以做的,虽然有的题和中国赛题差距有点大,但是无伤大雅?新的\(\text{Part}\)我要自己做出来更多题!\(\text{[AGC014D]Blackan......
  • Atcoder试题乱做 Part4
    时光怎不经一生浮浮沉沉已半生一壶浊酒欲随风一步一瞥似惊鸿情字要如何追问一指兰花为谁挽留\(\text{[ARC147D]SetsScores}\)\(\color{green}{\text{[EASY]}}\)......
  • Atcoder试题乱做 Part3
    最后一年了,一年不到,为了可爱的学长们,为了自己,要拼命了啊.\(\text{[AGC048D]PockyGame}\)\(\color{green}{\text{[EASY]}}\)怎么这都做不出来,废物啊.显然石......
  • AtCoder Beginner Contest 270
    AtCoder五十连练第一练AtCoderBeginnerContest270A-1-2-4Test考试有三道题,分别是\(1\)分、\(2\)分、\(4\)分。高桥、青木和Snuke参加了这次考试。高桥得......
  • AtCoder Beginner Contest 270
    A.1-2-4Test水题。B.Hammer分裂讨论。codeC.Simplepath一遍dfs就完了,怎么还有这种搜索题!codeD.Stones观察数据范围,\(O(NK)\)可过。\(dp_i\)表示\(i\)......
  • AtCoder Beginner Contest 270
    咕咕咕。D-Stones冲了发贪心,然后WA。然后想了个DP,就令\(dp_{n,0/1}\)表示石头总数为\(n\)时,先手/后手最多能拿多少个石头,然后跑个\(O(nk)\)的DP就完事了。......
  • AtCoder Beginner Contest 268(D-E)
    D-UniqueUsername 题意:给出n个字符串,以任意顺序排列,然后在每两个字符串中间加最少一个"_",然后给出m个字符串,问是否能得出一个字符串,不在这m个字符串中,并且长度在3-16......