首页 > 其他分享 >AtCoder Beginner Contest 260 A~F 题解

AtCoder Beginner Contest 260 A~F 题解

时间：2024-09-08 23:14:46浏览次数：14  
标签：AtCoder le 输出 int 题解 d% 260 maxn include

A - A Unique Letter

题目大意

给定一个长度为\(3\)的字符串\(S\)。
输出\(S\)中出现正好一次的字母（任意，如abc中，三个字母都可为答案）。

如果没有，输出-1。

数据保证\(S\)的长为\(3\)，且由小写英文字母组成。

输入格式

\(S\)

输出格式

输出任意符合条件的答案。

样例

\(S\) 输出
pop o
abc a/b/c
xxx -1

分析

我们设输入的3个字母分别为a、b、c。
首先，如果\(a=b=c\)，那么输出\(-1\)。
其次，我们依次尝试找到两个相同的字母：

  • xxy形式（\(a=b\)）：输出\(c\)
  • xyx形式（\(a=c\)）：输出\(b\)
  • yxx形式（\(b=c\)）：输出\(a\)
  • xyz形式（\(a\ne b\ne c\)）：输出任意一个

代码

这里，我把最后两种情况合并了（一个else搞定，都输出\(a\)）：

#include <cstdio>
using namespace std;

int main()
{
	char a = getchar(), b = getchar(), c = getchar();
	if(a == b && b == c) puts("-1");
	else if(a == c) putchar(b);
	else if(a == b) putchar(c);
	else putchar(a);
	return 0;
}

B - Better Students Are Needed!

题目大意

\(N\)个员工参加了一场选聘考试。
第\(i\)个员工数学考了\(A_i\)分，英语\(B_i\)分。

公司按如下的方式选聘员工：

  1. 数学分数在前\(X\)的被直接录取；
  2. 剩下的人中，英语分数在前\(Y\)的被录取；
  3. 最后，总分在前\(Z\)的被录取，剩下的人被淘汰。

注意：分数相同的员工按编号排序。

输出被录取的所有员工的编号，按升序排列。

\(1\le N\le 1000\)
\(0\le X,Y,Z\le N\)
\(1\le X+Y+Z\le N\)
\(0\le A_i,B_i\le 100\)

输入格式

\(N~X~Y~Z\)
\(A_1~A_2~\dots~A_N\)
\(B_1~B_2~\dots~B_N\)

输出格式

输出被录取的所有员工的编号，按升序排列，每行一个。

样例

略，请自行前往AtCoder查看

分析

本题主要有两种思路：

  1. 用pair<int, int>代表一个员工，再使用vector+sort或priority_queue执行三次分别排序数学、英语、总分；
  2. 用struct { int math, english, id; }表示员工，存储一次，排序三次（使用不同的排序依据）

详见代码1、代码2。

代码

代码1

  • vector+sort实现
    #include <cstdio>
#include <vector>
#include <algorithm>
#define maxn 1005
using namespace std;

int a[maxn], b[maxn];
bool used[maxn];

int main()
{
	int n, x, y, z;
	scanf("%d%d%d%d", &n, &x, &y, &z);
	for(int i=0; i<n; i++)
		scanf("%d", a + i);
	for(int i=0; i<n; i++)
		scanf("%d", b + i);
	
	// Math
	vector<pair<int, int>> sel_a;
	for(int i=0; i<n; i++)
		sel_a.emplace_back(-a[i], i);
	sort(sel_a.begin(), sel_a.end());
	for(int i=0; i<x; i++)
		used[sel_a[i].second] = true;
	
	// English
	vector<pair<int, int>> sel_b;
	for(int i=0; i<n; i++)
		if(!used[i])
			sel_b.emplace_back(-b[i], i);
	sort(sel_b.begin(), sel_b.end());
	for(int i=0; i<y; i++)
		used[sel_b[i].second] = true;
	
	// Total
	vector<pair<int, int>> sel_t;
	for(int i=0; i<n; i++)
		if(!used[i])
			sel_t.emplace_back(-(a[i] + b[i]), i);
	sort(sel_t.begin(), sel_t.end());
	for(int i=0; i<z; i++)
		used[sel_t[i].second] = true;
	
	for(int i=0; i<n; i++)
		if(used[i])
			printf("%d\n", i + 1);
	return 0;
}
  • priority_queue实现
    #include <cstdio>
#include <queue>
#define maxn 1005
using namespace std;

int a[maxn], b[maxn], c[maxn];
bool used[maxn];

inline void selectOnce(int* scores, int n, int snum)
{
	priority_queue<pair<int, int>> sel;
	for(int i=0; i<n; i++)
		if(!used[i])
		{
			sel.emplace(-scores[i], i);
			if(sel.size() > snum) sel.pop();
		}
	while(!sel.empty())
		used[sel.top().second] = true, sel.pop();
}

int main()
{
	int n, x, y, z;
	scanf("%d%d%d%d", &n, &x, &y, &z);
	for(int i=0; i<n; i++)
		scanf("%d", a + i);
	for(int i=0; i<n; i++)
		scanf("%d", b + i);
	for(int i=0; i<n; i++)
		c[i] = a[i] + b[i];
	selectOnce(a, n, x);
	selectOnce(b, n, y);
	selectOnce(c, n, z);
	for(int i=0; i<n; i++)
		if(used[i])
			printf("%d\n", i + 1);
	return 0;
}

代码2

#include <cstdio>
#include <vector>
#include <algorithm>
#define maxn 1005
using namespace std;

struct Emp { // Employee
	int math, eng, id;
} emps[maxn];

inline bool cmp1(const Emp& e1, const Emp& e2) {
	return e1.math == e2.math?
			e1.id < e2.id:
			e1.math > e2.math;
}

inline bool cmp2(const Emp& e1, const Emp& e2) {
	return e1.eng == e2.eng?
			e1.id < e2.id:
			e1.eng > e2.eng;
}

inline bool cmp3(const Emp& e1, const Emp& e2) {
	int tot1 = e1.math + e1.eng, tot2 = e2.eng + e2.math;
	return tot1 == tot2?
			e1.id < e2.id:
			tot1 > tot2;
}

inline bool cmp4(const Emp& e1, const Emp& e2) {
	return e1.id < e2.id;
}

int main()
{
	// Input
	int n, x, y, z;
	scanf("%d%d%d%d", &n, &x, &y, &z);
	
	for(int i=0; i<n; i++)
		scanf("%d", &emps[i].math),
		emps[i].id = i;
	for(int i=0; i<n; i++)
		scanf("%d", &emps[i].eng);
	
	// Sort
	auto last = emps + n;
	sort(emps, last, cmp1);
	sort(emps + x, last, cmp2);
	sort(emps + x + y, last, cmp3);
	sort(emps, emps + x + y + z, cmp4); // 按编号升序排序
	
	// Output
	for(int i=0; i<x+y+z; i++)
		printf("%d\n", emps[i].id + 1);
	return 0;
}

C - Changing Jewels

题目大意

Takahashi有一个\(N\)级的红色宝石。
他可以重复下列操作任意次数：

  • 将一个\(N\)级的红色宝石转换为“一个\((N-1)\)级的红色宝石和\(X\)个\(N\)级的蓝色宝石”。
  • 将一个\(N\)级的蓝色宝石转换为“一个\((N-1)\)级的红色宝石和\(Y\)个\(N-1\)级的蓝色宝石”。

Takahashi最后最多能得到几个\(1\)级的蓝色宝石？

\(1\le N\le 10\)
\(1\le X,Y\le 5\)

输入格式

\(N~X~Y\)

输出格式

输出一个整数，即最终蓝色宝石的数量。

样例

\(N\) \(X\) \(Y\) 输出
\(2\) \(3\) \(4\) \(12\)
\(10\) \(5\) \(5\) \(3942349900\)

注意小心\(32\)位整数（int/int32）溢出。

分析

要获得\((N-1)\)级的蓝宝石，必须先尽可能多的获得\(N\)级的蓝宝石。
而要达到这个目的，就需要有尽可能多的\(N\)级红宝石。

以此类推，我们可以按顺序进行操作\(1\)，操作\(2\)……直到所有宝石全部为\(1\)级（也就是循环\((N-1)\)次）。维护两个变量\(\text{red}\)（初始为\(1\)）和\(\text{blue}\)（初始为\(0\)），分别表示当前的红、蓝宝石的数目。
每次循环，先将\(\text{blue}\)加上\(\text{red}\times X\)（操作\(1\)），再将\(\text{red}\)加上\(\text{blue}\)、\(\text{blue}\)乘上\(Y\)（操作\(2\)）。

时间复杂度\(\mathcal O(n)\)，如有读不懂的地方，可参考代码。

代码

注意使用long long。

#include <cstdio>
using namespace std;

int main()
{
	int n, x, y;
	scanf("%d%d%d", &n, &x, &y);
	long long red = 1LL, blue = 0LL;
	while(--n)
	{
		blue += red * x;
		red += blue, blue *= y;
	}
	printf("%lld\n", blue);
	return 0;
}

D - Draw Your Cards

题目大意

有\(N\)张牌，上面分别写着数字\(P_1,P_2,\dots,P_N\)。
按照这个顺序，我们进行\(N\)个操作，第\(i\)个操作的具体步骤如下：

  • 取出第\(i\)张牌，令\(X=P_i\)；
  • 找到存堆中顶牌\(~\ge X\)的最小一张，将这张牌置于其上；
  • 如果没有符合条件的牌，将\(X\)放入一新堆；
  • 当某堆牌数达到\(K\)时，把这堆的牌全部吃掉。

求每张牌被吃掉的时间（若没有被吃掉，输出-1，详见输出格式）。

\(1\le K\le N \le 2\times 10^5\)
\(P\)是\((1,2,\dots,N)\)的一种排列。

输入格式

\(N~K\)
\(P_1~P_2~\dots~P_N\)

输出格式

输出\(N\)行，第\(i\)行表示卡片\(i\)被吃掉的时间（如果没被吃掉，输出-1）。

样例

略，就是懒

分析

首先肯定不能用vector<stack<int>>这种数据结构，效率太低，容易写错，还不好用。可以用一个类似于并查集的数据结构，每次叠放操作都可看作“把下面的牌的父亲设置为上面的牌”。我们还需要记录并查集中每个连通分量的大小，方便模拟“吃掉”操作。

最终对于每个节点，输出其祖宗被吃掉的时间（咋听起来有点怪）。

目前的时间复杂度是\(\mathcal O(N^2)\)，因为每次操作都需要用\(\mathcal O(n)\)的时间，找到最小的符合条件的牌堆。
很容易想到，可以使用set优化。

set是自动排序的集合，常用的的操作有插入（insert）、删除（erase）、二分查找（lower_bound/upper_bound），一次操作的时间复杂度均为\(\mathcal O(\log n)\)。

这时，使用一个set<int>维护每个堆顶的卡牌编号，就可以把时间复杂度降到\(\mathcal O(n\log n)\)以内。

至此，此题完。注意对\(K=1\)的特判。

代码

#include <cstdio>
#include <set>
#define maxn 200005
using namespace std;

int fa[maxn], eat[maxn], sz[maxn];

int find(int x) {
	return fa[x] == x? x: fa[x] = find(fa[x]);
}

int main()
{
	int n, k;
	scanf("%d%d", &n, &k);
	set<int> cards;
	for(int i=0; i<n; i++)
	{
		int x;
		scanf("%d", &x);
		x --;
		eat[x] = -1, fa[x] = x;
		if(k == 1)
		{
			eat[x] = i + 1;
			continue;
		}
		auto it = cards.upper_bound(x);
		if(it == cards.end())
			cards.insert(x), sz[x] = 1;
		else
		{
			fa[*it] = x;
			cards.erase(it);
			if((sz[x] = sz[*it] + 1) == k)
				eat[x] = i + 1;
			else cards.insert(x);
		}
	}
	for(int i=0; i<n; i++)
		printf("%d\n", eat[find(i)]);
	return 0;
}

E - At Least One

题目大意

给定整数\(M\)和\(N\)对整数：\((A_1,B_1),(A_2,B_2),\dots,(A_N,B_N)\)。
题目保证对于任意\(i\)，\(1\le A_i<B_i\le M\)。

符合如下条件的整数序列\(S\)被称作好的序列：

  • \(S\)是\((1,2,\dots,M)\)的连续子序列；
  • 对于每个\(i\)，\(S\)中包含\(A_i\)或\(B_i\)（或同时包含）。

令\(f(k)=(\)长为\(k\)的好序列的个数\()\)。求\(f(1),f(2),\dots,f(M)\)。

\(1\le N\le 2\times 10^5\)
\(2\le M\le 2\times 10^5\)
\(1\le A_i<B_i\le M\)

输入格式

\(N~M\)
\(A_1~B_1\)
\(A_2~B_2\)
\(\vdots\)
\(A_N~B_N\)

输出格式

输出一行，即\(f(1),f(2),\dots,f(M)\)，用空格分隔。

样例

略，请自行前往AtCoder查看

分析

首先，根据题意，\(S\)可被表示为一个区间\([l,r]\)，其中\(1\le l\le r\le M\)。
当对于每个\(i\)，\(l\le A_i\le r\)或\(l\le B_i\le r\)时，区间\([l,r]\)符合条件。
若按这样直接暴力枚举，时间复杂度为\(\mathcal O(N^2M)\)，明显超时，不可取。

仔细想想会发现，对于两个区间\([l,r]\)和\([a,b]\)，若\(a\le l\le r\le b\)，且\([l,r]\)符合条件，则\([a,b]\)也肯定符合条件。

此时，可以考虑使用滑动窗口优化，则时间复杂度降至\(\mathcal O(MN)\)。

继续优化。在窗口滑动的过程中，每次移动左/右端点时考虑一次移动对当前符合条件的\(i\)的数量的贡献，需要两个数组\(\mathrm{cnt}[N]\)（记录每个\(A_i\)和\(B_i\)符合条件的个数）和\(\mathrm{inv}[M+1][\dots]\)（预处理每个数值对应的所有元素下标）。

总时间复杂度为\(\mathcal O(N+M)\)，详见代码。

代码

#include <cstdio>
#include <vector>
#define maxn 200005
using namespace std;

vector<int> inv[maxn];
int cnt[maxn], ans[maxn];

int main()
{
	int n, m;
	scanf("%d%d", &n, &m);
	for(int i=0; i<n; i++)
	{
		int a, b;
		scanf("%d%d", &a, &b);
		inv[a].push_back(i);
		inv[b].push_back(i);
	}
	int left = n;
	for(int i=1, j=1; i<=m; i++)
	{
		for(; j <= m && left > 0; j++)
			for(int x: inv[j])
				if(++cnt[x] == 1)
					left --;
		if(left > 0) break;
		ans[j - i] ++, ans[m - i + 2] --;
		for(int x: inv[i])
			if(--cnt[x] == 0)
				left ++;
	}
	for(int i=1; i<=m; i++)
		printf("%d ", ans[i] += ans[i - 1]);
	return 0;
}

F - Find 4-cycle

给定一个二分图\(G\)，形如下：
二分图

图片来源：二分图_百度百科

其中顶点集\(U\)中的顶点数为\(S\)，\(V\)的顶点数为\(T\)，总边数为\(M\)（第\(i\)条边连接\(u_i\)和\(v_i\)）。
请找出此图中任意长为\(4\)的环。如果没有，输出-1。

\(2\le S\le 3\times 10^5\)
\(2\le T\le 3000\)
\(4\le M\le \min(S\times T,3\times 10^5)\)
\(1\le u_i\le S<v_i\le S+T\)

输入格式

\(S~T~M\)
\(u_1~V_1\)
\(u_2~V_2\)
\(\vdots\)
\(u_M~V_M\)

输出格式

如果有长为\(4\)的环，输出其中四个顶点的编号（顺序随意，用空格分隔）。
如果没有，输出-1。

样例

略，请自行前往AtCoder查看

分析

注意到样例中\(T\)只有\(3000\)，\(\mathcal O(T^2)=9\times 10^6\)可以接受。
然后因为是二分图，所以长为\(4\)的环肯定是在两个顶点集中各有两个点。

令\(f(x,y)\)为目前发现的与点\(x,y\)都相连的点，初始化为\(-1\)（表示未发现）。
输入使用邻接表存储，\(G[v]\)存储连到\(v\)的所有点，注意只需存顶点集\(U\)的\(G[v]\)即可。
再对于每个\(v\)，依次枚举\(G[v]\)中的两个点\((x,y)\)，如果\(f(x,y)=-1\)，则执行\(f(x,y):=v\)，如果不是\(-1\)，则输出{x} {y} {v} {f(x,y)}，结束程序。

时间复杂度约为\(\mathcal O(T^2)\)。

本题中的时间复杂度怎么算？
\(\to f(x,y)\)中不同\((x,y)\)的组合只有\(T(T-1)=T^2-T\approx T^2\)种。
\(\to~\) 根据鸽笼原理（又称抽屉原理），在最坏情况下，\(T^2\)种组合都记录过\(f\)之后，下一种组合无论是什么肯定都已经记录过\(f\)，因此最坏时间复杂度为\(\mathcal O(T^2)\)，对于随机数据的平均时间复杂度远远小于这个值。

代码

#include <cstdio>
#include <cstring>
#include <vector>
#define maxs 300005
#define maxt 3005
using namespace std;

vector<int> G[maxs];
int f[maxt][maxt];

int main()
{
	int s, t, m;
	scanf("%d%d%d", &s, &t, &m);
	while(m--)
	{
		int u, v;
		scanf("%d%d", &u, &v);
		G[--u].push_back(--v - s);
	}
	memset(f, -1, sizeof(f));
	for(int i=0; i<s; i++)
		for(int j=0; j+1<G[i].size(); j++)
			for(int k=j+1; k<G[i].size(); k++)
			{
				int u = G[i][j], v = G[i][k];
				if(u > v) u ^= v ^= u ^= v;
				if(f[u][v] != -1)
				{
					printf("%d %d %d %d\n", f[u][v] + 1, i + 1, u + s + 1, v + s + 1);
					return 0;
				}
				f[u][v] = i;
			}
	puts("-1");
	return 0;
}

标签：AtCoder,le,输出,int,题解,d%,260,maxn,include
From： https://www.cnblogs.com/stanleys/p/18403689/abc260

相关文章

  • LINE Verda Programming Contest (AtCoder Beginner Contest 263) A~E 题解
    A-FullHouse题目大意来自一个掼蛋爱好者的翻译qwq给定一副扑克牌中五张牌的编号\(A,B,C,D,E\)，判断这五张是否为一组“三带二”。（不懂的自行百度数据范围：\(1\leA,B,C,D,E\le13\)，且\(A,B,C,D,E\)不会全部相同。输入格式\(A~B~C~D~E\)输出格式如果是“三带二”，输出Yes；否......
  • BZOJ 1396 识别子串 题解
    Statement给\(S\)，令\(x\)为\(S\)的第\(k\)个字符，称\(T=S[i..j]\)为关于\(x\)的识别子串，当且仅当：\(i\lek\lej\)（含\(x\)这一位）\(T\)在\(S\)中只出现一次求\(S\)关于每一位字符的最短识别子串长度，\(|S|\le10^5\).Solution1以下是我没看题解瞎胡的首先......
  • 动态规划01背包的一个例题——洛谷P2871 题解
    题面有N件物品和一个容量为M的背包。第I件物品的重量是W[i],价值是D[i].求解将哪些物品装入背包可使这些物品的重量总和不超过背包容量，且价值总和最大。样例数据输入46142631227输出23分析（如果亲爱的读者对动态规划略有了解的话应该能看出来这是个01背包的板子......
  • BZOJ 3796 Mushroom追妹纸 题解
    Statement给\(s_1,s_2,s_3\)，求最长的\(w\)的长度，满足\(w\)是\(s_1\)子串\(w\)是\(s_2\)子串\(s_3\)不是\(w\)子串Solution1以下是我没看题解瞎胡的首先一个弱智想法是，枚举\(s_1\)上\(w\)的左端点，二分右端点，判定时\(s_2\)用SAM，\(s_3\)用单串AC自动......
  • BZOJ 4502 串 题解
    妙妙数数题key：数数题通常是，对于特定形式的计数，就盯着这个模式观察，看出一些充要条件、计数形式的转化，然后想办法维护。优化的本质就是把难算的变成好算的，把不好一起统计的（只能一个个数的）以某种角度、用某些数据结构，一起统计（多个多个数）。我觉得难点通常在于“盯出一些充要条件”，......
  • 题解：AT_arc116_b [ARC116B] Products of Min-Max
    在题库里面乱翻，就翻到了。因为在这道题里面子序列不需要考虑元素顺序，所以原序列无论是什么顺序都不会影响答案。所以先把元素按照从大到小的顺序排列，然后考虑每个元素的贡献。在当前序列中，对于元素\(a_i\)，不妨设其为最小值，并去寻找它能作为哪些序列的最小值。容易发现它作为最......
  • 题解：AT_abc369_c [ABC369C] Count Arithmetic Subarrays
    很水的一道题，但是硬控我半个小时呜呜呜。它问等差数列的数量，我们发现只要找到所有的等差数列，那么答案一定包含在这些数列的连续子序列中。求所有等差数列显然可以线性，我们求出每个等差数列的长度\(n\)，那么连续子序列个数即为\(n(n+1)\over2\)。至于求的话我定义了两个指针，每......
  • AtCoder Beginner Contest 253 A~E 题解
    A-Median?题目大意给定正整数\(a,b,c\)，判断\(b\)是否为三个数中的中位数（即从小到大排序后是第二个，不是平均数）。\(1\lea,b,c\le100\)输入格式\(a~b~c\)输出格式如果\(b\)是三个数中的中位数，输出Yes；否则，输出No。样例\(a\)\(b\)\(c\)输出\(5\)\(3\)\(2\)Y......
  • AtCoder Beginner Contest 241 (Sponsored by Panasonic) D~F 题解
    D-SequenceQuery题目大意我们有一个空序列\(A\)。请依次处理\(Q\)个命令，每个命令有三种类型，每种类型的格式如下：1x：将\(x\)加入\(A\)（不去重）2xk：求在\(A\)的\(\lex\)的元素中，第\(k\)大的值。3xk：求在\(A\)的\(\gex\)的元素中，第\(k\)小的值。\(1\leQ\le2\times10^5......
  • AtCoder Beginner Contest 242 C~E 题解
    C-1111galpassword题目大意给定正整数\(N\)，求符合下列条件的整数\(X\)的个数，对\(998244353\)取模：\(X\)是\(N\)位的正整数\(X\)的每一位数都在\([1,9]\)之间（0不行）；\(X\)的相邻两位数之差的绝对值不超过\(1\)。\(2\leN\le10^6\)输入格式\(N\)输出格式输出答案。样......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99