A - A Unique Letter

题目大意

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

如果没有，输出-1。

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

输入格式

$S$

输出格式

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

样例

分析

我们设输入的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 
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;
}
1
2
3
4
5
6
7
8
9
10
11
12

---

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$

输入格式

$NXYZ$
$A_1{A}_2\dots A_N$
$B_1{B}_2\dots B_N$

输出格式

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

样例

略，请自行前往AtCoder查看。

分析

本题主要有两种思路：

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

详见代码1、代码2。

代码

代码1

• vector+sort实现

  #include 
  #include 
  #include 
  #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;
  }
  1
  2
  3
  4
  5
  6
  7
  8
  9
  10
  11
  12
  13
  14
  15
  16
  17
  18
  19
  20
  21
  22
  23
  24
  25
  26
  27
  28
  29
  30
  31
  32
  33
  34
  35
  36
  37
  38
  39
  40
  41
  42
  43
  44
  45
  46
  47
  48
  49

• priority_queue实现

  #include 
  #include 
  #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;
  }
  1
  2
  3
  4
  5
  6
  7
  8
  9
  10
  11
  12
  13
  14
  15
  16
  17
  18
  19
  20
  21
  22
  23
  24
  25
  26
  27
  28
  29
  30
  31
  32
  33
  34
  35
  36
  37
  38
  39

代码2

#include 
#include 
#include 
#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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57

---

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$

输入格式

$NXY$

输出格式

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

样例

注意小心$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 
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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

---

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)$的一种排列。

输入格式

$NK$
$P_1{P}_2\dots P_N$

输出格式

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

样例

略，就是懒

分析

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

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

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

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

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

至此，此题完。注意对$K=1$的特判。

代码

#include 
#include 
#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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43

---

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$

输入格式

$NM$
$A_1{B}_1$
$A_2{B}_2$
$⋮$
$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^{2}M)$，明显超时，不可取。

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

代码

---

F - Find 4-cycle

题目大意

输入格式

输出格式

样例

分析

代码