Codeforces Round #707 (Div. 2, based on Moscow Open Olympiad in Informatics)
A. Alexey and Train
题意
火车按顺序经过 个车站，给出计划到达、发车时间，以及每段路额外花的时间。每站至少停留计划停留时间的一半，向上取整，而且不能早于计划时间发车。求到达最后一站的时间。
思路
按车站顺序模拟。每段实际行车时间是 ，到了以后再加上最短停留时间，如果还没到 就等到 。
最后一站只问到达时间，不用再算停留。扫一遍就行。
代码
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <cctype>
#include <iostream>
using namespace std;
const int maxn = 1e6 + 17;
int T, n, a[maxn], b[maxn], tm[maxn];
int main() {
cin >> T;
while(T--) {
cin >> n;
for(int i = 1; i <= n; i++) cin >> a[i] >> b[i];
for(int i = 1; i <= n; i++) cin >> tm[i];
int t = 0;
for(int i = 1; i <= n; i++) {
t += a[i] - b[i - 1] + tm[i];
if(i == n) break;
t += (b[i] - a[i] + 1) / 2;
if(t < b[i]) t = b[i];
}
cout << t <<endl;
}
return 0;
}B. Napoleon Cake
题意
蛋糕一层层往上叠，第 层放好以后倒入 份奶油，浸湿最上面的 层。层数不够就全部浸湿，多余奶油丢掉。问最后每一层有没有被浸湿。
思路
第 次倒奶油，对应的就是区间 。我把这些区间按左端点排序，再把它们覆盖的位置标成 1。
cr 记录已经扫到的最右端，只标它右边还没处理过的部分。这样每层最多标一次，时间主要在排序，是 。
代码
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <cctype>
#include <vector>
#include <iostream>
using namespace std;
#define mp make_pair
typedef pair<int, int> pii;
vector<pii> v;
const int maxn = 1e6 + 17;
int T, n, a[maxn];
bool cmp(pii A, pii B) {
return A.first < B.first;
}
int main () {
cin >> T;
while(T--) {
cin >> n;
for(int i = 1; i <= n; i++) a[i] = 0;
int cl = 0, cr = 0;
for(int i = 1; i <= n; i++) {
int len;
cin >> len;
if(len) v.push_back(mp(max(1, i - len + 1), i));
}
sort(v.begin(), v.end(), cmp);
int m = v.size();
for(int i = 0; i < m; i++) {
int l = v[i].first, r = v[i].second;
if(r > cr) {
for(int i = max(cr + 1, l); i <= r; i++) a[i] = 1;
if(l > cr) {
cl = l;
}
cr = r;
}
}
for(int i = 1; i <= n; i++) cout << a[i] << " \n"[i == n];
v.clear();
}
return 0;
}C. Going Home
题意
给一个数组，找四个互不相同的下标 ，满足 。有解就输出这四个下标，否则输出 NO。
思路
枚举两个位置，按两数之和分桶。每个和先留一对下标，再碰到同样的和，就看看两对有没有共用位置；四个下标都不同就找到了。
每个和只记第一对也够。假如答案中的两对都和它相交，那它的两个端点必然分别落在答案的两对里，剩下两个端点也能凑出同一个和，而且和第一对不相交，枚举到时一样能找到。
值域只有 ，和可以直接当数组下标。找到答案就结束，不用把所有二元组都存下来。
代码
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <cctype>
#include <vector>
#include <iostream>
using namespace std;
const int maxn = 3e6 + 17;
const int mx = 2500000;
int n, c[maxn], a[maxn];
typedef pair<int, int> pii;
pii s[mx * 2 + 17];
int main() {
cin >> n;
for(int i = 1; i <= n; i++) cin >> a[i];
for(int i = 1; i <= n; i++) {
for(int j = i + 1; j <= n; j++) {
int sum = a[i] + a[j];
if(s[sum].first) {
int x = s[sum].first, y = s[sum].second;
if(x != i && x != j && y != i && y != j) {
cout << "YES" << endl;
cout << x << " " << y << " " << i << " " << j << endl;
return 0;
}
}
else s[sum] = make_pair(i, j);
}
}
cout << "NO" << endl;
return 0;
}