首页 > 其他分享 >AtCoder Beginner Contest 326 题解

AtCoder Beginner Contest 326 题解

时间：2023-10-28 22:55:36浏览次数：33  
标签：frac14 frac AtCoder int 题解 long 326 选到 define

首先，\(\text{Happy Birthday to me !}\)

A - 2UP3DOWN

常规ABCA...

//If, one day, I finally manage to make my dreams a reality...
//I wonder, will you still be there by my side?
#include<bits/stdc++.h>
#define IOS ios::sync_with_stdio(false)
#define TIE cin.tie(0),cout.tie(0)
#define int long long
#define y1 cyy
#define fi first
#define se second
#define cnt1(x) __builtin_popcount(x)
#define mk make_pair
#define pb push_back
#define pii pair<int,int>
#define ls(x) (x<<1)
#define rs(x) (x<<1|1)
#define lbt(x) (x&(-x))
using namespace std;
int n,m,a[200005],ans;
signed main(){
	IOS;TIE;
	cin>>n>>m;
	if(m>=n-3&&m<=n+2) cout<<"Yes"<<endl;
	else cout<<"No"<<endl; 
	return 0;
}

B - 326-like Numbers

范围很小，直接枚举。

//If, one day, I finally manage to make my dreams a reality...
//I wonder, will you still be there by my side?
#include<bits/stdc++.h>
#define IOS ios::sync_with_stdio(false)
#define TIE cin.tie(0),cout.tie(0)
#define int long long
#define y1 cyy
#define fi first
#define se second
#define cnt1(x) __builtin_popcount(x)
#define mk make_pair
#define pb push_back
#define pii pair<int,int>
#define ls(x) (x<<1)
#define rs(x) (x<<1|1)
#define lbt(x) (x&(-x))
using namespace std;
int n,m,a[200005],ans;
signed main(){
	IOS;TIE;
	cin>>n;
	for(int i=n;;i++){
		if(i/100*(i/10%10)==i%10){
			cout<<i<<endl;
			return 0;
		}
	}
	return 0;
}

C - Peak

开始把 \(M\) 范围看小了还写了个小丑做法。

排完序直接二分第一个 \(>a_i+m-1\) 的位置，算一下就好。

//If, one day, I finally manage to make my dreams a reality...
//I wonder, will you still be there by my side?
#include<bits/stdc++.h>
#define IOS ios::sync_with_stdio(false)
#define TIE cin.tie(0),cout.tie(0)
#define int long long
#define y1 cyy
#define fi first
#define se second
#define cnt1(x) __builtin_popcount(x)
#define mk make_pair
#define pb push_back
#define pii pair<int,int>
#define ls(x) (x<<1)
#define rs(x) (x<<1|1)
#define lbt(x) (x&(-x))
using namespace std;
int n,m,a[300005],ans;
signed main(){
	IOS;TIE;
	cin>>n>>m;
	for(int i=1;i<=n;i++) cin>>a[i];
	sort(a+1,a+n+1);
	for(int i=1;i<=n;i++){
		ans=max(ans,upper_bound(a+i,a+n+1,a[i]+m-1)-a-i);
	}
	cout<<ans<<endl;
	return 0;
}

D - ABC Puzzle

首先这个数据范围肯定是搜索。直接搜过不去，考虑怎么剪点枝。

如果搜的过程中某行或某列出现了重复的字母，不用搜下去了（懒得记次数）。然后就是给的第一行第一列信息，如果当前是这一行或这一列的第一个填的字母，直接填给定的就行。

写了个依托答辩，怪不得 \(\text{CSPS}\) 大 \(\%\) 你写不出来（

//If, one day, I finally manage to make my dreams a reality...
//I wonder, will you still be there by my side?
#include<bits/stdc++.h>
#define IOS ios::sync_with_stdio(false)
#define TIE cin.tie(0),cout.tie(0)
#define int long long
#define y1 cyy
#define fi first
#define se second
#define cnt1(x) __builtin_popcount(x)
#define mk make_pair
#define pb push_back
#define pii pair<int,int>
#define ls(x) (x<<1)
#define rs(x) (x<<1|1)
#define lbt(x) (x&(-x))
using namespace std;
int n;
string s,t;
char c[35];
int id(int x,int y){
	return (x-1)*n+y;
}
bool check(){
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			if(c[id(i,j)]!='.'){
				if(c[id(i,j)]==s[i]) break;
				else return 0;
			}
		}
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			if(c[id(j,i)]!='.'){
				if(c[id(j,i)]==t[i]) break;
				else return 0;
			}
		}
	}
	
	for(int j=1;j<=n;j++){
		int fa=0,fb=0,fc=0;
		for(int i=1;i<=n;i++){
			fa+=(c[id(j,i)]=='A');
			fb+=(c[id(j,i)]=='B');
			fc+=(c[id(j,i)]=='C');
		}
		if(fa!=1||fb!=1||fc!=1) return 0;
	}
	for(int j=1;j<=n;j++){
		int fa=0,fb=0,fc=0;
		for(int i=1;i<=n;i++){
			fa+=(c[id(i,j)]=='A');
			fb+=(c[id(i,j)]=='B');
			fc+=(c[id(i,j)]=='C');
		}
		if(fa!=1||fb!=1||fc!=1) return 0;
	}
	return 1;
}
bool ok(){
	for(int j=1;j<=n;j++){
		int fa=0,fb=0,fc=0;
		for(int i=1;i<=n;i++){
			fa+=(c[id(j,i)]=='A');
			fb+=(c[id(j,i)]=='B');
			fc+=(c[id(j,i)]=='C');
		}
		if(fa>1||fb>1||fc>1) return 0;
	}
	for(int j=1;j<=n;j++){
		int fa=0,fb=0,fc=0;
		for(int i=1;i<=n;i++){
			fa+=(c[id(i,j)]=='A');
			fb+=(c[id(i,j)]=='B');
			fc+=(c[id(i,j)]=='C');
		}
		if(fa>1||fb>1||fc>1) return 0;
	}
	return 1;
}
void dfs(int x,int y){
	if(!ok()) return ;
	if(id(x,+y)==n*n+1){
		if(check()){
			cout<<"Yes"<<endl;
			for(int i=1;i<=n;i++){
				for(int j=1;j<=n;j++) cout<<c[id(i,j)];
				cout<<endl;
			}
			exit(0);
		}
		return ;
	}
	bool fl1=1,fl2=1;
	for(int i=1;i<y;i++) if(c[id(x,i)]!='.') fl1=0;
	for(int i=1;i<x;i++) if(c[id(i,y)]!='.') fl2=0;
	int yy=y+1,xx=x;
	if(yy>n) xx++,yy=1;
	dfs(xx,yy);
	if(fl1) c[id(x,y)]=s[x],dfs(xx,yy);
	else if(fl2) c[id(x,y)]=t[y],dfs(xx,yy);
	else{
		for(char i='A';i<='C';i++){
			c[id(x,y)]=i;
			dfs(xx,yy);
		}
	}
	c[id(x,y)]='.';
}
signed main(){
	IOS;TIE;
	cin>>n>>s>>t;
	s=" "+s,t=" "+t;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++) c[id(i,j)]='.';
	}
	dfs(1,1);
	cout<<"No"<<endl;
	return 0;
}

E - Revenge of "The Salary of AtCoder Inc."

比较简单的期望题。（然而一开始又看错了题/fn）

套路地，我们讨论每个数字对于最终答案的贡献。

以四个数 1 2 3 4 为例：

首先是他们第一次就被选到的概率，显然都为 \(\frac14\)。

1 2 3 4
第1次 \(\frac14\) \(\frac14\) \(\frac14\) \(\frac14\)

然后考虑第二次的贡献：

  • \(1\) 不可能被选到
  • \(2\) 产生贡献前提是上一次选到了 \(1\)，然后这次选到 \(2\)。故概率是 \(\frac14\times\frac14=\frac{1}{4^2}\)
  • \(3\) 产生贡献前提是上一次选到了 \(1\) 或 \(2\)，然后这次选到 \(3\)。故概率是 \((\frac14+\frac14)\times\frac14=\frac{2}{4^2}\)
  • \(4\) 产生贡献前提是上一次选到了 \(1\) 或 \(2\) 或 \(3\)，然后这次选到 \(4\)。故概率是 \((\frac14+\frac14+\frac14)\times\frac14=\frac{3}{4^2}\)
1 2 3 4
第1次 \(\frac14\) \(\frac14\) \(\frac14\) \(\frac14\)
第2次 \(0\) \(\frac{1}{4^2}\) \(\frac{2}{4^2}\) \(\frac{3}{4^2}\)

同理考虑第三次的贡献：

  • \(1\) 和 \(2\) 不可能被选到
  • \(3\) 产生贡献前提是上一次选到了 \(1\) 或 \(2\)，然后这次选到 \(3\)。故概率是 \((0+\frac{1}{4^2})\times\frac14=\frac{1}{4^3}\)
  • \(4\) 产生贡献前提是上一次选到了 \(1\) 或 \(2\) 或 \(3\)，然后这次选到 \(4\)。故概率是 \((0+\frac{1}{4^2}+\frac{2}{4^2})\times\frac14=\frac{3}{4^3}\)

第四次概率也同理。

所以我们得到最终表格：

1 2 3 4
第1次 \(\frac14\) \(\frac14\) \(\frac14\) \(\frac14\)
第2次 \(0\) \(\frac{1}{4^2}\) \(\frac{2}{4^2}\) \(\frac{3}{4^2}\)
第3次 \(0\) 0 \(\frac{1}{4^3}\) \(\frac{3}{4^3}\)
第4次 \(0\) 0 0 \(\frac{1}{4^4}\)

发现了什么？第 \(j\) 次贡献的分母是 \(n^j\)，而对于每个数 \(i\) 来说，其分子依次为杨辉三角的第 \(i\) 横排。所以最终所求答案即为：

\[\sum _ {i = 1} ^ n \sum _ {j = 1} ^ i \frac{C_{i-1}^{j-1}}{n^j}\times a_i \]

我们设第 \(i\) 个数的贡献为 \(f_i\)，然后根据杨辉三角的优秀性质，就可以得到递推式：

\[f_i=f_{i-1}+f_{i-1}\times\frac1n \]

然后问题就解决了。

//If, one day, I finally manage to make my dreams a reality...
//I wonder, will you still be there by my side?
#include<bits/stdc++.h>
#define IOS ios::sync_with_stdio(false)
#define TIE cin.tie(0),cout.tie(0)
#define int long long
#define y1 cyy
#define fi first
#define se second
#define cnt1(x) __builtin_popcount(x)
#define mk make_pair
#define pb push_back
#define pii pair<int,int>
#define ls(x) (x<<1)
#define rs(x) (x<<1|1)
#define lbt(x) (x&(-x))
#define mod 998244353
using namespace std;
int n,a[300005],p,ans,f[300005];
int ksm(int x,int b){
	int ans=1;
	while(b){
		if(b&1) ans=ans*x%mod;
		x=x*x%mod,b>>=1;
	}
	return ans;
}
signed main(){
	IOS;TIE;
	cin>>n;
	for(int i=1;i<=n;i++) cin>>a[i];
	int INV=ksm(n,mod-2),p=1ll;
	f[1]=INV;
	ans+=f[1]*a[1]%mod;
	for(int i=2;i<=n;i++){
		f[i]=f[i-1]+f[i-1]*INV%mod,f[i]%=mod;
		ans+=a[i]*f[i]%mod;
		ans%=mod;
	}
	cout<<ans<<endl;
	return 0;
}

F - Robot Rotation"

据说是折四半搜索，有点抽象。赛时感觉来不及写就来写题解了（

咕咕咕

G - Unlock Achievement

流！！赛时怎么没看！！！亏爆（然而赛后看了十几分钟才看懂）

建图：

首先把每个技能拆为 \(5\) 个点（\(1\sim5\) 级）。初始源点向每个技能的 \(1\) 级连 \(inf\)（本来就有）。然后源点向 \(2\sim5\) 级连 \(c_i\)，每个技能除 \(5\) 级外的相邻等级再连 \(inf\)，这样就可以做到流到每个技能对应等级的最大流为升到这一级的花费。

考虑组合技怎么算答案。对应每个组合技开点（以下记为 \(x\)），该组合技中，每个技能对应等级的点分别向点 \(x\) 连 \(inf\)（\(1\) 级除外），这样就可以保证到点 \(x\) 的最大流为其最小花费。最后所有组合技点向汇点连的 \(a_i\) 后求得最大流为 \(tmp\)，最终答案就是 \((\sum a_i)-ans\)。

为什么这是对的？因为最大流即为最小割，而我们建的图的最小割，就相当于每个点选了一个等级，使之满足部分组合技，而剩下一些组合技不要了（相当于割掉组合技点像汇点连的 \(a_i\) ），并且做到花费最少。

要时刻记得等级写的是从 0 开始还是从 1 开始，警钟敲烂（

//If, one day, I finally manage to make my dreams a reality...
//I wonder, will you still be there by my side?
#include<bits/stdc++.h>
#define IOS ios::sync_with_stdio(false)
#define TIE cin.tie(0),cout.tie(0)
#define int long long
#define y1 cyy
#define fi first
#define se second
#define cnt1(x) __builtin_popcount(x)
#define mk make_pair
#define pb push_back
#define pii pair<int,int>
#define ls(x) (x<<1)
#define rs(x) (x<<1|1)
#define lbt(x) (x&(-x))
#define inf 1e15
using namespace std;
int n,m,c[105],a[105],ans,f[55][55];

struct MaxFlow{
	int tot=1,head[50005],cur[50005],dep[50005];
	struct node{
		int to,nxt,f;
	}e[50005];
	void add(int u,int v,int f){
		e[++tot]={v,head[u],f},head[u]=tot;
		e[++tot]={u,head[v],0},head[v]=tot;
	}
	queue<int> q;
	int bfs(int s,int t){
		while(q.size()) q.pop();q.push(s);
		memset(dep,0,sizeof(dep));dep[s]=1;
		while(q.size()){
			int x=q.front();q.pop();
			for(int i=head[x];i;i=e[i].nxt){
				node tmp=e[i];
				if(tmp.f&&!dep[tmp.to]){
					dep[tmp.to]=dep[x]+1;
					q.push(tmp.to);
				}
			}
		}
		return dep[t];
	}
	int dfs(int s,int t,int f){
		if(s==t||!f) return f;
		int ans=0;
		for(int i=cur[s];i;i=e[i].nxt){
			node &x=e[i];cur[s]=i;
			if(x.f&&dep[x.to]==dep[s]+1){
				int tmp=dfs(x.to,t,min(f,x.f));
				x.f-=tmp,e[i^1].f+=tmp;
				ans+=tmp,f-=tmp;
				if(f<=0) break;
			}
		}
		return ans;
	}
	int dinic(int s,int t){
		int ans=0;
		while(bfs(s,t)){
			memcpy(cur,head,sizeof(head));
			ans+=dfs(s,t,inf);
		}
		return ans;
	}
}mf;
signed main(){
	IOS;TIE;
	cin>>n>>m;
	int S=n*5+m+1,T=n*5+m+2;
	for(int i=1;i<=n;i++) cin>>c[i];
	for(int i=1;i<=m;i++) cin>>a[i],ans+=a[i];
	for(int i=1;i<=n;i++){
		for(int j=1;j<=4;j++){
			mf.add(S,(j-1)*n+i,c[i]);
			if(j<4) mf.add((j-1)*n+i,j*n+i,inf);
		}
	}
	for(int i=1;i<=m;i++){
		mf.add(n*5+i,T,a[i]);
		for(int j=1;j<=n;j++){
			cin>>f[i][j];
			if(f[i][j]>1) mf.add(n*(f[i][j]-2)+j,n*5+i,inf);
		}
	}
	cout<<ans-mf.dinic(S,T)<<endl;
	return 0;
}

标签：frac14,frac,AtCoder,int,题解,long,326,选到,define
From： https://www.cnblogs.com/binary1110011/p/17794737.html

相关文章

  • 【杂题乱写】AtCoder-ARC114
    AtCoder-ARC114_ANotcoprime\(50\)内的质数只有\(15\)个，可能的答案也就只有\(2^{15}\)个，直接枚举。提交记录：Submission-AtCoderAtCoder-ARC114_BSpecialSubsets就是\(i\)与\(f_i\)连边，每个连通块都是基环树，一定能剥叶子变成环，所以答案就是连通块非空子集个数。......
  • P2514 [HAOI2010] 工厂选址 题解
    目录DescriptionSolutionCodeDescription有\(m\)座煤矿，每一座煤矿有\(a_i\)吨煤，第\(i\)座煤矿到第\(j\)号发电厂的运费为\(c_{i,j}\)每吨。有一座发电厂（标号为0），需要恰好\(b\)吨煤矿发电，初始运行费用为\(h\)。还有\(n\)座待运行的发电厂（标号为1~n），每座发电厂初......
  • ctf_show Web的Web8题解
    好久没写博客，上次写还是在上次（三年前）。如题，写一次CTF的题解 根据题目提示得知这应该是一个注入，什么注入还不知道，进入靶场。 仅有三个地方可点，都点进去看看。从URL处可以看到前端是传了一个参数id给后端（另外两个类似，就不贴图了）。那很明显了是SQL注入。 首先在参数后......
  • 【深度学习 | 概念】那些深度学习路上必经的 常见问题解决方案及最佳实践，确定不来看看
    ......
  • CSP-J 2023 题解
    CSP-J2023题解T1小苹果这个题直接遍历枚举必定TLE，这是CCF的出题风格，每题T1巨水无比，但是往往又需要一些思维。这道题我们可以发现每一轮操作都会拿走\(1+(n-1)/3\)个苹果，所以每次让\(n\)减去\(1+(n-1)/3\)就可以了。然后记录编号为\(n\)什么时候拿......
  • 「联合省选 2020 A」组合数问题 题解
    非常显然的，我们展开\(f(k)\)，于是有：\[\begin{align}&\sum\limits_{k=0}^{n}\sum\limits_{i=0}^{m}a_{i}k^{i}x^{k}\binom{n}{k}\\=&\sum\limits_{k=0}^{n}\sum\limits_{i=0}^{m}a_{i}{\sum\limits_{j=0}^{i}\begin{Bmatrix}i\\j\end{Bmatrix}\binom{......
  • CF777E题解
    分析看到这个题就想到了二维偏序。你们很自然地，以\(b\)为第一关键字降序排序，当有若干个片\(b\)相等时，我们发现由于\(a<b\)，所以排到最后的片一定能把这些\(b\)相等的片都统计上，而前面的片能否统计是依赖于\(b\)，所以考虑如何让后面的片更好统计，显然\(a\)越小越好统......
  • AtCoder Beginner Contest(abc) 310
    B-StrictlySuperior难度:⭐题目大意给定n个商品的价格,每个商品还有若干个属性,请问是否存在一个商品是另外一个商品的上位品;上位品的定义分两种,一是价格相同,但是商品A的属性不仅包括了商品B的属性,还比商品B多了至少一个属性;二是如果两商品的属性相同,但是......
  • NOIP2023模拟5联测26 题解
    NOIP2023模拟5联测26题解感觉我这场的官方题解写的是真的挺好的，所以我只能作少量补充。你可以直接去看官方题解，如果你想的话。T1x题解\(n=2\)没啥可说的。\(\color{white}{这档分你要是没拿到那你还是蛮强的。}\)\(n=3\)的时候，我们需要比较\((a_1^{a_2})^{a_3}\)与......
  • [TopCoder 13001] BigO 题解
    [TopCoder13001]BigO题解题目描述给定一张有向图，当\(L\)趋近于无穷大时，长度为\(L\)的路径条数有\(S\)条，此时若\(S=O(L^k)\)，输出\(k\)，否则如果没有多项式的大O表示法，输出\(-1\)。指数情况首先如果一张图中存在如下强连通分量，则\(S=O(2^L)\)。因为每次到1......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99