首页 > 其他分享 >[ABC266] AtCoder Beginner Contest 266

[ABC266] AtCoder Beginner Contest 266

时间:2023-02-02 20:45:29浏览次数:84  
标签:AtCoder typedef int LL long ABC266 sec 266 include

比赛链接:Tasks - AtCoder Beginner Contest 266

先贴代码,题解有空再补。

Tasks


Task Name Time Limit Memory Limit
A Middle Letter 2 sec 1024 MB Submit
B Modulo Number 2 sec 1024 MB Submit
C Convex Quadrilateral 2 sec 1024 MB Submit
D Snuke Panic (1D) 2 sec 1024 MB Submit
E Throwing the Die 2 sec 1024 MB Submit
F Well-defined Path Queries on a Namori 3 sec 1024 MB Submit
G Yet Another RGB Sequence 2 sec 1024 MB Submit
Ex Snuke Panic (2D) 5 sec 1024 MB Submit

Solutions

A

#include<set>
#include<map>
#include<queue>
#include<stack>
#include<cmath>
#include<ctime>
#include<bitset>
#include<vector>
#include<cstdio>
#include<complex>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>

using namespace std;
typedef long long LL;
typedef long double LD;
typedef unsigned long long ULL;

int main()
{
//	freopen("1.in","r",stdin);
	string str;
	cin>>str;
	printf("%c\n",str[str.length()/2]);
	return 0;
}

B

#include<set>
#include<map>
#include<queue>
#include<stack>
#include<cmath>
#include<ctime>
#include<bitset>
#include<vector>
#include<cstdio>
#include<complex>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>

using namespace std;
typedef long long LL;
typedef long double LD;
typedef unsigned long long ULL;

int main()
{
//	freopen("1.in","r",stdin);
	LL x;
	cin>>x;
	const LL MOD=998244353;
	printf("%lld\n",(x%MOD+MOD)%MOD);
	return 0;
}

C

#include<set>
#include<map>
#include<queue>
#include<stack>
#include<cmath>
#include<ctime>
#include<bitset>
#include<vector>
#include<cstdio>
#include<complex>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>

using namespace std;
typedef long long LL;
typedef long double LD;
typedef pair<int,int> PII;
typedef unsigned long long ULL;

const int N=1000;

PII a[N];

int S(int x,int y,int z)
{
	int x_1=a[y].first-a[x].first;
	int y_1=a[y].second-a[x].second;
	int x_2=a[z].first-a[x].first;
	int y_2=a[z].second-a[x].second;
	return abs(x_1*y_2-x_2*y_1);
}

int main()
{
	for(int i=1;i<=4;i++) {
		cin>>a[i].first>>a[i].second;
		a[i+4]=a[i];
		a[i+8]=a[i];
	}
	int ans=S(1,2,3)+S(1,3,4);
	for(int i=2;i<=9;i++) {
		int siz=S(i-1,i,i+1)+S(i-1,i+1,i+2);
		if(siz!=ans) return puts("No")&0;
	}
	puts("Yes");
	return 0;
}

D

#include<set>
#include<map>
#include<queue>
#include<stack>
#include<cmath>
#include<ctime>
#include<bitset>
#include<vector>
#include<cstdio>
#include<complex>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>

using namespace std;
typedef long long LL;
typedef long double LD;
typedef unsigned long long ULL;

const int N=1e5+5;

int n,m;
LL f[N][5],a[N][5];

int main()
{
//	freopen("1.in","r",stdin);
	scanf("%d",&n);
	for(int i=1,t,x,z;i<=n;i++) {
		scanf("%d%d%d",&t,&x,&z);
		a[t][x]+=z;
		m=max(m,t);
	}
	memset(f,-0x3f,sizeof f);
	f[0][0]=0;
	for(int i=1;i<=m;i++) 
		for(int j=0;j<=4;j++) {
			f[i][j]=f[i-1][j]+a[i][j];
			if(j-1>=0) f[i][j]=max(f[i][j],f[i-1][j-1]+a[i][j]);
			if(j+1<=4) f[i][j]=max(f[i][j],f[i-1][j+1]+a[i][j]);
		}
	
	LL ans=0;
	for(int i=0;i<=4;i++) ans=max(ans,f[m][i]);
	printf("%lld\n",ans);
	return 0;
}

E

一道期望题,重点在于读懂题目什么意思。

#include<set>
#include<map>
#include<queue>
#include<stack>
#include<cmath>
#include<ctime>
#include<bitset>
#include<vector>
#include<cstdio>
#include<complex>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>

using namespace std;
typedef long long LL;
typedef long double LD;
typedef unsigned long long ULL;

const int N=1000+5;

double f[N]; // f[i][j] 表示策略下在前 i 轮拿到 j 的概率 
int n;

int main()
{
	scanf("%d",&n);
	f[1]=3.5;
	for(int i=2;i<=n;i++) {
		for(int j=1;j<=6;j++) {
			if(j<f[i-1]) f[i]+=f[i-1];
			else f[i]+=j;
		}
		f[i]/=6;
	}		 
	printf("%.10lf\n",f[n]);
	return 0;
}

F

拓扑排序

#include<set>
#include<map>
#include<queue>
#include<stack>
#include<cmath>
#include<ctime>
#include<bitset>
#include<vector>
#include<cstdio>
#include<complex>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>

using namespace std;
typedef long long LL;
typedef long double LD;
typedef unsigned long long ULL;

const int N=4e5+5;

int one[N],idx;
int ver[N],Next[N];
void AddEdge(int a,int b)
{
	Next[idx]=one[a]; ver[idx]=b; one[a]=idx++;
}

int n,m;

queue<int> q;
int deg[N];
bool vis[N];

void topsort()
{
	while(q.size()) q.pop();
	memset(vis,false,sizeof vis);
	
	for(int i=1;i<=n;i++) {
		if(deg[i]==1) {
			q.push(i);
			vis[i]=true;
		}
	}
	
	while(q.size()) {
		int x=q.front(); q.pop();
		for(int i=one[x],y;~i;i=Next[i]) {
			y=ver[i];
			if(vis[y]) continue;
			if((--deg[y])==1) q.push(y),vis[y]=true;
		}
	}
}

int col[N];
void color(int x,int fa,int c)
{
	col[x]=c;
	for(int i=one[x];~i;i=Next[i]) {
		int y=ver[i];
		if(y==fa || !vis[y]) continue;
		color(y,x,c);
	}
}

int main()
{
//	freopen("1.in","r",stdin);
	
	scanf("%d",&n);
	memset(one,-1,sizeof one); idx=0;
	for(int i=1,x,y;i<=n;i++) {
		scanf("%d%d",&x,&y);
		AddEdge(x,y); AddEdge(y,x);
		deg[x]++; deg[y]++;
	}
	topsort();
	
	for(int i=1;i<=n;i++) {
		if(vis[i]) continue;
		color(i,-1,i);
	}
	
	int x,y;
	scanf("%d",&m);
	while(m--) {
		scanf("%d%d",&x,&y);
		if(col[x]==col[y]) puts("Yes");
		else puts("No");
	}
	
	return 0;
}

G

计数问题

#include<set>
#include<map>
#include<queue>
#include<stack>
#include<cmath>
#include<ctime>
#include<bitset>
#include<vector>
#include<cstdio>
#include<complex>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>

using namespace std;
typedef long long LL;
typedef long double LD;
typedef unsigned long long ULL;

const LL P=998244353;
const int N=3e6+5;

LL fact[N];
LL power(LL x,LL k)
{
	LL res=1;
	while(k) {
		if(k&1) res=res*x%P;
		x=x*x%P; k>>=1;
	} 
	return res%P;
}
LL inv(LL x) { return power(x,P-2); } 

LL C(LL n,LL m) 
{
	if(m>n || m<0) return 0;
	else return fact[n]*inv(fact[m])%P*inv(fact[n-m])%P;
}

LL R,G,B,k;
LL n;

int main()
{
//	freopen("1.in","r",stdin);
	fact[0]=1;
	for(int i=1;i<N;i++) 
		fact[i]=fact[i-1]*i%P;
	
	scanf("%lld%lld%lld%lld",&R,&G,&B,&k);
	n=R+G+B-k;
	LL ans=C(n-(G-k),k)*C(n-(G-k)-k,R-k)%P; // 排 RG,R,B 
	ans=ans*(C(B+k+G-k,G-k)%P)%P;
	printf("%lld\n",ans);
	return 0;
}

标签:AtCoder,typedef,int,LL,long,ABC266,sec,266,include
From: https://www.cnblogs.com/cjl-world/p/17087324.html

相关文章

  • Atcoder ABC282F Union of Two Sets
    https://atcoder.jp/contests/abc282/tasks/abc282_fST表板子???这怎么出的?发现要每一个区间都能拆分成至多两个区间,那很明显就能联想到ST表的查询。大概算一下发现......
  • Atcoder ABC282E Choose Two and Eat One
    https://atcoder.jp/contests/abc282/tasks/abc282_e发现选出两个球去掉一个球其实很像一颗树去掉叶子节点,贡献即为叶子节点与父亲的边权。那这题就很明显了,预处理好每......
  • Atcoder ABC282H Min + Sum
    https://atcoder.jp/contests/abc282/tasks/abc282_h挂了好久发现二分写挂了……对于\(\min\{a_i\}\)这一部分,不难想到找到当前\(\min\{a_i\}\)的位置计算其左右两......
  • AtCoder Beginner Contest 287
    FComponents考虑树形\(DP\)。有\(f_{i,j,0/1}\)为以\(i\)为根的子树,一共有\(j\)个连通块,选/不选的方案数。\[pre_{x,0/1}\leftarrowf_{u,x,0/1}\]\[f_......
  • AtCoder Beginner Contest 285
    C:abc285_brutmhyhiizp题目大意一串序列A,B,...,Z,AA,AB,...,ZZ,AAA,...给定一个字符串求在序列中的排名(保证存在)思路将每个A看作\(1\),B看作\(2\),....,Z......
  • (AtCoder Beginner Contest 287)(D 字符串前后缀合并匹配)(E Trie求最长公共前缀(LCP)
    D-MatchorNot(字符串前后缀合并匹配)题目大意:给定两个字符串S和T,对于每个x=0,1,2...|T|求S的子串(前x个字符和后|T|-x个字符在不改变顺序的情况下组成)是否与T相......
  • 【字典树】Atcoder Beginner Contest 287----E
    题目:E-Karuta(atcoder.jp)题解:这道题就是一个字典树求最长公共前缀的板子题。可以直接交板子。但我在翻题解的时候发现了另一种思路,就是将字符串按字典序排列后,每一个......
  • AtCoder Beginner Contest 287 解题报告
    AtCoderBeginnerContest287解题报告\(\text{ByDaiRuiChen007}\)ContestLinkA.Majority用map分别统计两种字符串出现的次数并与\(\left\lfloor\dfracn2\righ......
  • AtCoder Beginner Contest 287
    A-Majority(abc287a)题目大意给定\(n\)个人对某个提案的意见,问大多数意见是支持还是反对解题思路统计比较即可。神奇的代码#include<bits/stdc++.h>usingnam......
  • AtCoder Beginner Contest 287
    纯纯手速场C首先这张图必须是一棵树,必有\(M=N-1\)。接下来只需求出树的直径,判断其长度(边数)是否为\(N-1\)即可。https://atcoder.jp/contests/abc287/submissions/3......