首页 > 其他分享 >AtCoder Beginner Contest 267 解题报告

AtCoder Beginner Contest 267 解题报告

时间：2022-09-04 17:23:41浏览次数：100  
标签：AtCoder typedef Beginner Contest int ios long include define

A - Saturday

题意 ：输入字符串 代表 周一至周五的某一天，输出这一天离周六还有多少天
分析 ：映射一下，直接输入输出

ac代码：

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <queue>
#include <map>
#include <vector>
#include <stack>
#include <set>
#include <sstream>
#include <fstream> 
#include <cmath>
#include <iomanip>
#include <bitset>
#include <unordered_map>
#include <unordered_set>
#include <random>
//#pragma GCC optimize(3)
#define x first
#define y second
#define ios ios::sync_with_stdio(false),cin.tie(0);
#define endl '\n'
#define pb push_back
#define all(x) x.begin(),x.end()
#define all1(x) x.begin()+1,x.end()

using namespace std;
 
typedef unsigned long long uLL;
typedef long long LL;
typedef pair<int,int> PII;
 
const int N = 2000010,M = 10010,INF = 0x3f3f3f3f,mod = 1e9 + 7;
const double INFF = 0x7f7f7f7f7f7f7f7f,pi = acos(-1.0),eps = 1e-6;


int n,m,k,t;

int main()
{
	ios;
	map<string,int> mp;
	mp["Monday"] = 5;
	mp["Tuesday"] = 4;
	mp["Wednesday"] = 3;
	mp["Thursday"] = 2;
	mp["Friday"] = 1;
	string s;
	cin >> s;
	cout << mp[s] << endl;
	return 0;
}

B - Split?

题意 ：有7列保龄球瓶，现在告诉你哪几个瓶倒了，问是否有以下情况发生：
1.编号为1的瓶倒了
2.有两列至少有一个瓶站着，且这两列中间有一列全倒了
分析 ：模拟 + 暴力判断

image

ac代码

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <queue>
#include <map>
#include <vector>
#include <stack>
#include <set>
#include <sstream>
#include <fstream> 
#include <cmath>
#include <iomanip>
#include <bitset>
#include <unordered_map>
#include <unordered_set>
#include <random>
//#pragma GCC optimize(3)
#define x first
#define y second
#define ios ios::sync_with_stdio(false),cin.tie(0);
#define endl '\n'
#define pb push_back
#define all(x) x.begin(),x.end()
#define all1(x) x.begin()+1,x.end()

using namespace std;
 
typedef unsigned long long uLL;
typedef long long LL;
typedef pair<int,int> PII;
 
const int N = 2000010,M = 10010,INF = 0x3f3f3f3f,mod = 1e9 + 7;
const double INFF = 0x7f7f7f7f7f7f7f7f,pi = acos(-1.0),eps = 1e-6;


int n,m,k,t;

int main()
{
	ios;
	int id[] = {0,4,3,5,2,4,6,1,3,5,7};
	string s;
	cin >> s;
	s = ' ' + s;
	if(s[1] == '1') cout << "No" << endl;
	else
	{
		int a[] = {0,1,1,2,2,2,1,1};
		for(int i = 1;i <= 10;i ++)
		{
			if(s[i] == '0')
			{
				a[id[i]] --;
			}
		}

		bool success = false;
		for(int i = 1;i <= 7;i ++)
			for(int j = i + 1;j <= 7;j ++)
			if(a[i] && a[j])
			{
				int tp = 0;
				for(int k = i + 1;k < j;k ++) if(!a[k]) tp ++;
				if(tp) success = true;
			}
		if(success) cout << "Yes" << endl;
		else cout << "No" << endl;

	}
	return 0;
}

C - Index × A(Continuous ver.)

题意 ： 给定一个数组a,求a的一个长度为m的连续子序列b,使 \(\sum_1^m i * b_i\) 最大
分析 ：前缀和 + 暴力枚举,求出\(i * a_i\) 和 \(a_i\) 的前缀和s 和 a，当b以i为开头时，所求答案为\(s_{i + m - 1} - s_{i - 1} - (i - 1) * a_{i - 1}\)
ac代码

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <queue>
#include <map>
#include <vector>
#include <stack>
#include <set>
#include <sstream>
#include <fstream> 
#include <cmath>
#include <iomanip>
#include <bitset>
#include <unordered_map>
#include <unordered_set>
#include <random>
//#pragma GCC optimize(3)
#define x first
#define y second
#define ios ios::sync_with_stdio(false),cin.tie(0);
#define endl '\n'
#define pb push_back
#define all(x) x.begin(),x.end()
#define all1(x) x.begin()+1,x.end()

using namespace std;
 
typedef unsigned long long uLL;
typedef long long LL;
typedef pair<int,int> PII;
 
const int N = 2000010,M = 10010,INF = 0x3f3f3f3f,mod = 1e9 + 7;
const double INFF = 0x7f7f7f7f7f7f7f7f,pi = acos(-1.0),eps = 1e-6;


int n,m,k,t;

int main()
{
	ios;
	cin >> n >> m;
	vector<LL> a(n + 1),b(n + 1);
	for(int i = 1;i <= n;i ++) cin >> a[i],b[i] = b[i - 1] + 1LL * a[i] * i,a[i] += a[i - 1];

	LL ans = - 1e18;
	for(int i = m;i <= n;i ++)
	{
		ans = max(ans,b[i] - b[i - m] - (a[i] - a[i - m]) * (i - m));
	}
	cout << ans << endl;
	return 0;
}

D - Index × A(Not Continuous ver.)

题意 ： 与C题意相同 但 求的b是a的子序列
分析 ： 考虑dp,从\(a_i\) 选与不选考虑(01背包)
\(f(i,j) 表示 ： 前i个物品中选了j个所能得到的最大值\)
\(不选 ： f(i,j) = f(i - 1,j)\)
\(选 ： f(i,j) = f(i - 1,j - 1) + j * a_i\)
坑点 ：因为\(a_i\)可能为负，f数组的赋初值1e18不够小
ac代码

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <queue>
#include <map>
#include <vector>
#include <stack>
#include <set>
#include <sstream>
#include <fstream> 
#include <cmath>
#include <iomanip>
#include <bitset>
#include <unordered_map>
#include <unordered_set>
#include <random>
//#pragma GCC optimize(3)
#define x first
#define y second
#define ios ios::sync_with_stdio(false),cin.tie(0);
#define endl '\n'
#define pb push_back
#define all(x) x.begin(),x.end()
#define all1(x) x.begin()+1,x.end()
 
using namespace std;
 
typedef unsigned long long uLL;
typedef long long LL;
typedef pair<int,int> PII;
 
const int N = 2000010,M = 10010,INF = 0x3f3f3f3f,mod = 1e9 + 7;
const double INFF = 0x7f7f7f7f7f7f7f7f,pi = acos(-1.0),eps = 1e-6;
 
 
int n,m,k,t;
LL f[2010][2010];
int main()
{
	ios;
	cin >> n >> m;
	vector<int> a(n + 1);
	for(int i = 1;i <= n;i ++) cin >> a[i];
	memset(f,-0x3f,sizeof f);
	for(int i = 0;i <= n;i ++) f[i][0] = 0;
 	for(int i = 1;i <= n;i ++)
	{
		for(int j = 1;j <= min(i,m);j ++)
		{
			f[i][j] = f[i - 1][j];
			f[i][j] = max(f[i][j],f[i - 1][j - 1] + 1LL * j * a[i]);
		}
	}
	cout << f[n][m] << endl;
	return 0;
}

E - Erasing Vertices 2

题意 ：给定一个无向图带有n个点m条边，每个点都有权值。每次要删除一条边，一次删除的代价是从这个点直接相邻的点的权值和，使n次删除操作后的最大值最小，求其最小值。
分析 ： 最大值最小问题，经典二分思路，二分答案，check函数模拟删点看能否删完所有点
ac代码

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <queue>
#include <map>
#include <vector>
#include <stack>
#include <set>
#include <sstream>
#include <fstream> 
#include <cmath>
#include <iomanip>
#include <bitset>
#include <unordered_map>
#include <unordered_set>
#include <random>
//#pragma GCC optimize(3,"Ofast","inline")
#define x first
#define y second
#define ios ios::sync_with_stdio(false),cin.tie(0);
#define endl '\n'
#define pb push_back
#define all(x) x.begin(),x.end()
#define all1(x) x.begin()+1,x.end()
 
using namespace std;
 
typedef unsigned long long uLL;
typedef long long LL;
typedef pair<int,int> PII;
 
const int N = 200010,M = 10010,INF = 0x3f3f3f3f,mod = 1e9 + 7;
const double DNF = 0x7f7f7f7f7f7f7f7f,pi = acos(-1.0),eps = 1e-6;
const long long LNF = 0x3f3f3f3f3f3f3f3f;
 
int n,m,k,t;
LL a[N];
int h[N],e[N << 1],ne[N << 1],idx;

void add(int a,int b)
{
	e[idx] = b,ne[idx] = h[a],h[a] = idx ++;
}

bool check(LL x)
{
	vector<LL> w(n + 1);
	for(int i = 1;i <= n;i ++)
		for(int j = h[i];~ j;j = ne[j]) 
			w[e[j]] += a[i];

	queue<int> q;
	for(int i = 1;i <= n;i ++) if(w[i] <= x) q.push(i);
	vector<bool> st(n + 1);
	while(q.size())
	{
		int u = q.front();
		q.pop();
		if(st[u]) continue;
		st[u] = true;

		for(int i = h[u];~ i;i = ne[i])
		{
			int j = e[i];
			if(st[j]) continue;
			w[j] -= a[u];
			if(w[j] <= x) q.push(j);
		}
	} 

	for(int i = 1;i <= n;i ++) if(!st[i]) return false;
	return true;
}

int main()
{
	ios;
	cin >> n >> m;
	for(int i = 1;i <= n;i ++) h[i] = -1;
	for(int i = 1;i <= n;i ++) cin >> a[i];

	while(m --)
	{
		int a,b;
		cin >> a >> b;
		add(a,b), add(b,a);
	}

	LL l = -1, r = 1e18;

	while(l < r)
	{
		LL mid = l + r >> 1;
		if(check(mid)) r = mid;
		else l = mid + 1;
	}

	cout << l << endl;
	return 0;
}

F - Exactly K Steps

题意 ： 给定一棵树，有若干个询问，每次给定一个节点u和参数k，请随意输出一个和u距离为k的节点，如果不存在，输出-1。
分析 ： 树有一个性质：任意一个点的最远点一定是直径的一个端点。所以我们求出树的直径的两个端点，找出离点u最远的点v,如果最远距离 < k ,则输出 -1 ，否则我们利用树上倍增，来在u与v的路径上找出答案点
ac代码

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <queue>
#include <map>
#include <vector>
#include <stack>
#include <set>
#include <sstream>
#include <fstream> 
#include <cmath>
#include <iomanip>
#include <bitset>
#include <unordered_map>
#include <unordered_set>
#include <random>
//#pragma GCC optimize(3,"Ofast","inline")
#define x first
#define y second
#define ios ios::sync_with_stdio(false),cin.tie(0);
#define endl '\n'
#define pb push_back
#define all(x) x.begin(),x.end()
#define all1(x) x.begin()+1,x.end()
 
using namespace std;
 
typedef unsigned long long uLL;
typedef long long LL;
typedef pair<int,int> PII;
 
const int N = 200010,M = 10010,INF = 0x3f3f3f3f,mod = 1e9 + 7;
const double DNF = 0x7f7f7f7f7f7f7f7f,pi = acos(-1.0),eps = 1e-6;
const long long LNF = 0x3f3f3f3f3f3f3f3f;
 
int n,m,k,t;
int l,r;
int h[N],e[N << 1],ne[N << 1],idx;
int fa[N][18],depth[N];
int dist[N];
void add(int a,int b)
{
	e[idx] = b,ne[idx] = h[a],h[a] = idx ++;
}

void bfs()
{
	queue<int> q;
	for(int i = 1;i <= n;i ++) depth[i] = INF;
	depth[0] = 0,depth[1] = 1;
	q.push(1);

	while(q.size())
	{
		int u = q.front();
		q.pop();

		for(int i = h[u];~ i;i = ne[i])
		{
			int j = e[i];
			if(depth[j] > depth[u] + 1)
			{
				depth[j] = depth[u] + 1;
				fa[j][0] = u;
				q.push(j);

				for(int k = 1;k <= 17;k ++)
					fa[j][k] = fa[fa[j][k - 1]][k - 1];
			}
		}
	}
}

int lca(int a,int b)
{
	if(depth[a] < depth[b]) swap(a,b);

	for(int k = 17;~ k;k --)
		if(depth[fa[a][k]] >= depth[b])
			a = fa[a][k];

	if(a == b) return a;

	for(int k = 17;~ k;k --)
		if(fa[a][k] != fa[b][k])
		{
			a = fa[a][k];
			b = fa[b][k];
		}

	return fa[a][0];
}

void dfs(int u,int fa)
{
	for(int i = h[u];~ i;i = ne[i])
	{
		int j = e[i];
		if(j == fa) continue;
		if(dist[j] > dist[u] + 1) 
		{
			dist[j] = dist[u] + 1;
			dfs(j,u);
		}
	}
}

void find()
{
	for(int i = 1;i <= n;i ++) dist[i] = INF;
	dist[1] = 0;
	dfs(1,0);
	for(int i = 2;i <= n;i ++) if(dist[i] > dist[l]) l = i;
	for(int i = 1;i <= n;i ++) dist[i] = INF;
	dist[l] = 0;
	dfs(l,0);
	for(int i = 1;i <= n;i ++) if(dist[i] > dist[r]) r = i;
}

void solve(int u,int v,int anc,int k)
{
	if(depth[u] - depth[anc] >= k)
	{
		for(int i = 17;~ i;i --) if(k >> i & 1) u = fa[u][i];
	}
	else
	{
		k = depth[u] + depth[v] - 2 * depth[anc] - k;
		u = v;
		for(int i = 17;~ i;i --) if(k >> i & 1) u = fa[u][i];

	}
	
	cout << u << endl;
}

int main()
{
	ios;
	
	cin >> n;
	for(int i = 1;i <= n;i ++) h[i] = -1;
	for(int i = 1;i < n;i ++)
	{
		int a, b;
		cin >> a >> b;
		add(a,b), add(b,a);
	}
	
	find();

	bfs();
	cin >> m;
	while(m --)
	{
		int u, k, v;
		cin >> u >> k;
		int ancl = lca(u,l),ancr = lca(u,r);
		//cout << ancl<< " " << ancr << endl;
		if(depth[u] + depth[l] - 2 * depth[ancl] > depth[u] + depth[r] - 2 * depth[ancr]) v = l;
		else v = r;
		int anc;
		if(v == l) anc = ancl;
		else anc = ancr;
		if(depth[u] + depth[v] - 2 * depth[anc] < k) cout << -1 << endl;
		else solve(u,v,anc,k);
	}

	return 0;
}

标签：AtCoder,typedef,Beginner,Contest,int,ios,long,include,define
From： https://www.cnblogs.com/notyour-young/p/16655470.html

相关文章

  • AtCoder Beginner Contest 267
    E-ErasingVertices2做法1观察可得：对于某个时刻，贪心删当前代价最小的点肯定是最优的。但是删一个点会减少相邻接的点的代价。然后就想到了堆，但是这个堆需要支持decre......
  • AtCoder Beginner Contest 267 E Erasing Vertices 2
    ErasingVertices2二分||贪心二分的做法就二分答案，然后检查一下能否删除，像拓扑一下跑一下就行#include<iostream>#include<cstdio>#include<algorithm>#includ......
  • AtCoder ABC 259 F Select Edges
    题意：​ 给出一棵树，边带权，对于点i，最多保留d[i]条边，可以被分成连通块，请问边权和最大是多少分析：​ 因为可以被分成连通块，我们就可以对点i划分两种状态。第一种是点i不与父......
  • AtCoder Beginner Contest 266 G,H
    G考虑先放G和B，此时共有\(C_{G+B}^{B}\)种方案。然后选出\(k\)个G，在前面放上\(R\)，共有\(C_{G}^{k}\)种方案。最后我们放剩下的\(R-K\)个R，考虑目前哪些区间内部可以放一段......
  • 2021 Xinjiang Provincial Collegiate Programming Contest
      G.cocktailwithsnake题意：给区间宽高：n，m，蛇形走位，问k步之后和原点的曼哈顿距离是多少分析intt=k/n就是走k步后当行数如果t是奇数，说明在往左走如果t是......
  • AtCoder Beginner Contest 266 一句话题解
    AandBsbt，不讲。C垃圾计算几何，问是不是一个凸包，搞份板子交就可以了。D简单dp，令\(f(i,j)\)表示第\(i\)个时间在第\(j\)个位置的最大价值，从上一个时间转移，可以......
  • AtCoder Beginner Contest 266
    比赛链接：https://atcoder.jp/contests/abc266C-ConvexQuadrilateral题意：平面图上有一个四边形，按照逆时针顺序给定四个点的坐标，判断四边形是不是凸的。思路：求两条......
  • AtCoder Beginner Contest 179
    https://atcoder.jp/contests/abc179我的AC代码https://atcoder.jp/contests/abc179/submissions/me?f.Task=&f.LanguageName=&f.Status=AC&f.User=HinanawiTenshi这......
  • AtCoder Beginner Contest 265(D-E)
    D-IrohaandHaiku(NewABCEdition)题意:找一个最少含有三个点的区间，将区间分成三块，三块的和分别为p,q,r，问是否存在这样的区间题解:先预处理一遍前缀和，和每一个前缀......
  • The 2021 Shanghai Collegiate Programming Contest D. Zztrans 的班级合照
    计数dp好题用组合数想了一下，需要容斥，情况太复杂用计数dp，\(dp[i][j]\)表示前\(i\)个人有\(j\)个在第一排，并且按照身高遍历i，这样满足了第一个偏序关系（“排成人数相同的两排......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99