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$）：
|
|
B - Better Students Are Needed!
题目大意
$N$个员工参加了一场选聘考试。
第$i$个员工数学考了$A_i$分，英语$B_i$分。
公司按如下的方式选聘员工：
- 数学分数在前$X$的被直接录取；
- 剩下的人中，英语分数在前$Y$的被录取；
- 最后，总分在前$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查看
分析
本题主要有两种思路：
- 用
pair<int, int>代表一个员工，再使用vector+sort或priority_queue执行三次分别排序数学、英语、总分； - 用
struct { int math, english, id; }表示员工，存储一次，排序三次（使用不同的排序依据）
详见代码1、代码2。
代码
代码1
vector+sort实现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#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实现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#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
|
|
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。
|
|
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$的特判。
代码
|
|
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)$，详见代码。
代码
|
|
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)$，对于随机数据的平均时间复杂度远远小于这个值。
代码
|
|