题目链接
@[toc]

A - やめて嘘はあなたらしくないよ

The $h$ -index of an author is the largest $h$ where he has at least $h$ papers with citations not less than $h$ .
Bobo has published many papers.
Given $a_{0}, a_{1}, a_{2}, \dots, a_{n}$ which means Bobo has published $a_{i}$ papers with citations exactly $i$ , find the $h$ -index of Bobo.
Input
The input consists of several test cases and is terminated by end-of-file.
The first line of each test case contains an integer $n$ .
The second line contains $(n + 1)$ integers $a_{0}, a_{1}, \dots, a_{n}$ .
Output
For each test case, print an integer which denotes the result.
Constraint
$1 \leq n \leq 2 \cdot 10^{5}$
$0 \leq a_{i} \leq 10^{9}$
The sum of $n$ does not exceed $250, 000$ .
Sample Input1
1 2
2
1 2 3
3
0 0 0 0
Sample Output1
2
0

cpp

#include<iostream>
#include<set>
#include<vector>

int a[1000005];
using namespace std;
int main() {
	int n;
	while (~scanf("%d", &n)) {
		for (int i = 0; i <= n; ++i)scanf("%d", &a[i]);
		int ans = 0;//表示论文数
		//从后往前贪心
		for (int i = n; i >= 0; --i) {
			ans += a[i];
			//如果不满足题目条件
			if (i <= ans) {
				printf("%d\n", i);
				break;
			}
		}
	}
	return 0;
}

B - 目を見てこれからのことを話そう

The $h$ -index of an author is the largest $h$ where he has at least hh papers with citations not less than $h$ .
Bobo has no papers and he is going to publish some subsequently.
If he works on a paper for xx hours, the paper will get $(a \cdot x)$ citations, where $a$ is a known constant.
It’s clear that $x$ should be a positive integer.
There is also a trick — one can cite his own papers published earlier.
Given Bobo has $n$ working hours, find the maximum $h$ -index of him.
Input
The input consists of several test cases and is terminated by end-of-file.
Each test case contains two integers $n$ and $a$ .
Output
For each test case, print an integer which denotes the maximum $h$ -index.
Constraint
$1 \leq n \leq 10^{9}$
$0 \leq a \leq n$
The number of test cases does not exceed $10^{4}$ .
Sample Input
3 0
3 1
1000000000 1000000000
Sample Output
1
2
1000000000
Hint
For the first sample, Bobo can work $3$ papers for $1$ hour each.
With the trick mentioned, he will get papers with citations $2, 1, 0$ . Thus, his $h$ -index is $1$ .
For the second sample, Bobo can work $2$ papers for $1$ and $2$ hours respectively. He will get papers with citations $1 + 1, 2 + 0$ . Thus, his $h$ -index is $2$ 。

最优解是每个论文都花1小时。仔细想一想就出来了。

cpp

#include<iostream>
using namespace std;
int main() {
	int n, a;
	while (~scanf("%d%d", &n, &a)) {
		printf("%d\n", (n + a) >> 1);
	}
	return 0;
}

F - my wish かなえたいのに

Bobo has $n$ tuples $(a_{1}, b_{1}, c_{1}), (a_{2}, b_{2}, c_{2}) \dots, (a_{n}, b_{n}, c_{n})$ .
He would like to find the lexicographically smallest permutation $p_{1}, p_{2}, \dots, p_{n}$
of $1, 2, \dots, n$ .
such that for $i \in {2, 3, \dots, n}$
it holds that

$\frac{a_{p_{i - 1}} + b_{p_{i - 1}}}{a_{p_{i - 1}} + b_{p_{i - 1}} + c_{p_{i - 1}}} \leq \frac{a_{p_{i}} + b_{p_{i}}}{a_{p_{i}} + b_{p_{i}} + c_{p_{i}}}$
Input
The input consists of several test cases and is terminated by end-of-file. The first line of each test case contains an integer $n$ .
The $i_{t h}$ of the following nn lines contains 3 integers $a_{i}, b_{i}$ and $c_{i}$ .
Output
For each test case, print nn integers $p_{1}, p_{2}, \dots, p_{n}$ seperated by spaces. DO NOT print trailing spaces.
Constraint
$1 \leq n \leq 10^{3}$
$1 \leq a_{i}, b_{i}, c_{i} \leq 2 \times 10^{9}$
The sum of nn does not exceed 10^4
Sample Input
2
1 1 1
1 1 2
2
1 1 2
1 1 1
3
1 3 1
2 2 1
3 1 1
Sample Output
2 1
1 2
1 2 3

除法化乘法避免精度损失，在优化一下乘法（卡long long上限）。

cpp

#include<iostream>
#include<set>
#include<vector>
#include<algorithm>
using namespace std;
struct Node {
	long long a, b, c;
	int node;
};
Node Data[1001];
int main() {
	int n;
	while (~scanf("%d", &n)) {
		for (int i = 1; i <= n; ++i) {
			scanf("%lld%lld%lld", &Data[i].a, &Data[i].b, &Data[i].c);
			Data[i].node = i;
		}
		sort(Data + 1, Data + n + 1, [](Node&Left, Node&Right) {
			long long&&left = (Left.a + Left.b)*(Right.c),
				&&right = (Left.c)*(Right.a + Right.b);
			return (left == right ? Left.node < Right.node:left < right);
			});
		for (int i = 1; i < n; ++i) {
			printf("%lld ", Data[i].node);
		}
		printf("%lld", Data[n].node);
		putchar('\n');
	}
	return 0;
}

G - すべては God knows…

Bobo has a string S=s1s2…sn consists of letter a, b and c.
He can transform the string by inserting or deleting substrings aa, bb and abab.
Formally, A=u∘w∘v (`∘'' denotes string concatenation) can be transformed into A′=u∘v and vice versa where u, v are (possibly empty) strings and w∈{aa,bb,abab}. Given the target string $T=t_1t_2\cdots t_m$, determine if Bobo can transform the string S into T. Input The input consists of several test cases and is terminated by end-of-file. The first line of each test case contains a string $s_1s_2\cdots s_n$. The second line contains a string $t_1t_2\cdots t_m$. Output For each test case, printYesif Bobo can. PrintNootherwise. Constraint $1≤n,m≤10^4$ $s_1,s_2,\cdots ,s_n,t_1,t_2,\cdots ,t_m∈\{a,b,c\}$ The sum of n and m does not exceed 250,000. Sample Input ab ba ac ca a ab Sample Output Yes No No Hint For the first sample, Bobo can transform asab => aababb => babb => ba`.

根据提示，ab可以转为ba，ba同理。且可以增加删除aa或bb，那么，在没有c的字符串中，只要统计两个字符串中a和b个数是否同奇同偶即可。而对于c，可以看作c将字符串分割成了若干子串。

cpp

#include<iostream>
#include<string>
#define scanf scanf_s
int ans1[10001], ans2[10001];
using namespace std;string a, b;

int main() {
	while (cin >> a >> b) {
		int t = 0;
		int ct = 0;
		for (int i = 0; i < a.size(); ++i) {
			if (a[i] == 'c') {
				ans1[ct++] = t;
			}
			else {
				t ^= a[i];
			}
		}
		ans1[ct++] = t;
		int s = 0;
		int st = 0;
		for (int i = 0; i<b.size(); ++i) {
			if (b[i] == 'c') {
				ans2[st++] = s;
			}
			else {
				s ^= b[i];
			}
		}
		ans2[st++] = s;
		bool flag = false;
		if (st == ct) {
			for (int i = 0; i < st; ++i) {
				if (ans1[i] != ans2[i]) {
					puts("No");
					flag = true;
					break;
				}
			}
			if (!flag) {
				puts("Yes");
			}
		}
		else {
			puts("No");
		}
	}
	return 0;
}

K - 傷跡なぞる

Given $a, b, c, d$ find out the number of pairs of integers $(x, y)$ where $a \leq x \leq b, c \leq y \leq d$ and $x * y$ is a multiple of 2018.
Input
The input consists of several test cases and is terminated by end-of-file.
Each test case contains four integers $a, b, c, d$ .
Output
For each test case, print an integer which denotes the result.
Constraint
$1 \leq a \leq b \leq 10^{9}, 1 \leq c \leq d \leq 10^{9}$
The number of tests cases does not exceed $10^{4}$ .
Sample Input
1 2 1 2018
1 2018 1 2018
1 1000000000 1 1000000000
Sample Output
3
6051
1485883320325200

2018的公约数只有1*2018以及2*1009这两对，根据容斥定理很容易求出结果。

cpp

#include<iostream>
#include<set>
#include<vector>
using namespace std;
long long a, b, c, d;
int main() {
	while (~scanf("%lld%lld%lld%lld", &a, &b, &c, &d)) {
		long long left[4], right[4];

		auto fuck = [](long long Array[4],long long &left,long long &right)->void {
			Array[0] = right - left + 1;
			Array[1] = right / 2 - (left - 1) / 2;
			Array[2] = right / 1009 - (left - 1) / 1009;
			Array[3] = right / 2018 - (left - 1) / 2018;
			Array[2] -= Array[3];
			Array[1] -= Array[3];
			Array[0] -= Array[3] + Array[2] + Array[1];
		};

		fuck(left, a, b);
		fuck(right, c, d);

		const long long&&Ans =
			left[0] * right[3] +
			left[1] * (right[2] + right[3]) +
			left[2] * (right[1] + right[3]) +
			left[3] * (right[0] + right[1] + right[2] + right[3]);

		printf("%lld\n", Ans);
	}
	return 0;
}