2018-2019, ICPC, Asia Yokohama Regional Contest 2018
A - Digits Are Not Just Characters
签到。
题意：从给定的集合中选出最多的数构成等差数列。
题解：数字排序后，设(dp[i][j])表示等差数列最后一个数字为(a[i]),倒数第二个数字为(a[j])的最大个数。然后对于每一位枚举 (i)，(lower\_bound())找有无合法的 (j) 即可。复杂度(O(n^2log(n)))。
代码：
#include <bits/stdc++.h>
#define fopi freopen("in.txt", "r", stdin)
using namespace std;
const int maxn = 5000 + 5;
int dp[maxn][maxn];
int a[maxn];
int n;
int main() {
scanf("%d", &n);
for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
sort(a+1, a+1+n);
int ans = 0;
for (int i = 1; i <= n; i++)
for (int j = 1; j < i; j++) {
int idx = lower_bound(a+1, a+1+n, a[j]-(a[i]-a[j])) - a;
if (a[j] - a[idx] == a[i] - a[j])
dp[i][j] = max(dp[i][j], dp[j][idx]+1);
ans = max(ans, dp[i][j]);
}
printf("%d
", ans+2);
}
题意：一些人在车座里，求所有人下车的最小时间。
题解：考虑到门口距离相等的两个人会在某个地方相遇，所以其中一个人要多花费一个单位的时间。故可以求出每个人到门口的距离，排序后处理相等的，直到序列变为升序。
D - Shortest Common Non-Subsequence
题意：给出两个(01)串(s)和(t)，求最短的 (01) 序列，不是 (s) 和 (t) 的子序列。多组答案输出字典序最小的。
题解：序列自动机。预处理出(s)和(t)每个位置上后面第一个(1)和第一个(0)的位置。设当前在(s)和(t)的位置分别为((x,y))，则可以由((next_s[x][1], next_t[y][1]))和((next_s[x][0],next_t[y][0]))转移到，分别代表当前位放(1)和(0)。则答案就是从((0,0))到((len_s+1, len_t+1))的字典序最小的最短路。
代码：
#include <bits/stdc++.h>
#define fopi freopen("in.txt", "r", stdin)
#define fopo freopen("out.txt", "w", stdout)
using namespace std;
typedef long long LL;
const int maxn = 4000 + 5;
const int inf = 0x3f3f3f3f;
int dp[maxn][maxn], fa[maxn][maxn];
char s[maxn], t[maxn];
int nexta[maxn][2], nextb[maxn][2];
int l1, l2;
vector<int> ans;
int dfs(int x, int y) {
if (x == l1+1 && y == l2+1) return 0;
if (dp[x][y]) return dp[x][y];
int tmp1 = dfs(nexta[x][0], nextb[y][0]),
tmp2 = dfs(nexta[x][1], nextb[y][1]);
if (tmp1 <= tmp2) fa[x][y] = -1; else fa[x][y] = 1;
return dp[x][y] = min(tmp1, tmp2)+1;
}
void Print(int x, int y) {
if (x == l1+1 && y == l2+1) return;
int res = fa[x][y] > 0;
ans.push_back(res);
Print(nexta[x][res], nextb[y][res]);
}
int main() {
scanf("%s%s", s+1, t+1);
l1 = strlen(s+1), l2 = strlen(t+1);
nexta[l1+1][1] = nexta[l1+1][0] = l1+1;
nextb[l2+1][1] = nextb[l2+1][0] = l2+1;
for (int i = l1; i >= 0; i--) {
nexta[i][1] = nexta[i+1][1];
nexta[i][0] = nexta[i+1][0];
if (s[i+1] == '1') nexta[i][1] = i+1;
else nexta[i][0] = i+1;
}
for (int i = l2; i >= 0; i--) {
nextb[i][1] = nextb[i+1][1];
nextb[i][0] = nextb[i+1][0];
if (t[i+1] == '1') nextb[i][1] = i+1;
else nextb[i][0] = i+1;
}
dfs(0, 0);
Print(0, 0);
for (auto p : ans) printf("%d", p);
puts("");
}
题意：在一个图上任意添加一些边，使得图中存在欧拉回路。输出添加的边。
题解：
存在欧拉回路 (=) 所有点的度数为偶数。
把每条可用的边设为一个未知数（值为(0)或(1)）。把每个点关于可用的边按度数写出一个方程，使得所有点的度数都为偶数。解非齐次线性方程组计算，计算出用哪些边（未知数值为1）。
若此时图已联通，那么这就是答案。如果此时图的连通块个数(>=3)，可以加入一些边使它们成环。如果连通块的个数为(2)，且每个连通块内都存在两点没有直接相连，那么就把这四个点连成环。
若方程组无解或无法联通，则无解。
G - What Goes Up Must Come Down
题意：通过交换相邻两个数的形式，把一个序列变为非递减(+)非递增两部分。求操作次数。
题解：小的数肯定要去大的外层。所以考虑每一个数走到两边的逆序对，每次取逆序对小的一侧。求和即为答案。求逆序对可以用树状数组，来回求两次。
代码：
#include <bits/stdc++.h>
#define fopi freopen("in.txt", "r", stdin)
#define fopo freopen("out.txt", "w", stdout)
using namespace std;
typedef long long LL;
const int maxn = 1e5 + 10;
int n;
int a[maxn];
struct Trray {
int C[maxn], N = 100000;
void init() { memset(C, 0, sizeof(C)); }
int lowbit(int x) { return x & (-x); }
void update(int i, int k) {
while(i <= N) C[i] += k, i += lowbit(i);
}
int getsum(int i) {
int res = 0;
while(i > 0) res += C[i], i -= lowbit(i);
return res;
}
}Tr;
int pre[maxn];
int main() {
scanf("%d", &n);
for (int i = 1; i <= n; i++) {
scanf("%d", &a[i]);
Tr.update(a[i], 1);
pre[i] = i - Tr.getsum(a[i]);
}
Tr.init();
LL ans = 0;
for (int i = n; i >= 1; i--) {
Tr.update(a[i], 1);
ans += min(pre[i], n-i+1 - Tr.getsum(a[i]));
}
printf("%lld
", ans);
}
题意：你和对手都有(n)个数字。你可以任意改变自己的数字顺序，对于每个位置，若自己的数字大，则得一分。求保证得分最多的前提下，字典序最大的顺序方案。
题解：先贪心求出最大得分。然后从前往后枚举每个位置，二分当前位置，在不改变得分的前提下，可用的最大数字。注意当前位置要分为得分和不得分两种情况，分别二分（如果不分情况直接二分，例如敌方(1 2 3)/我方(1 2 3)，第一局用(1)是会改变最大得分的，此时会被判定为不可以，(mid)会变小）。
代码：
#include <bits/stdc++.h>
#define fopi freopen("in.txt", "r", stdin)
using namespace std;
const int maxn = 5000 + 5;
int a[maxn], b[maxn], p[maxn];
int ans[maxn];
multiset<int> S, tep;
int n, x, num, now, tot;
bool check(int st, int mid) {
int res = 0, id = 1;
for (int i = st; i <= n; i++) {
while(id == mid || (id <= tot && b[id] <= a[i])) id++;
if (id <= tot) res++, id++;
}
return res + (b[mid] > a[st-1]) + now == num;
}
int main() {
scanf("%d", &n);
for (int i = 1; i <= n; i++) {
scanf("%d", &a[i]);
p[i] = a[i];
}
for (int i = 1; i <= n; i++) {
scanf("%d", &x);
tep.insert(x);
S.insert(x);
}
for (int i = 1; i <= n; i++) {
multiset<int> :: iterator it = tep.upper_bound(a[i]);
if (it == tep.end()) continue;
if (*it > a[i]) num++, tep.erase(it);
}
for (int i = 1; i <= n; i++) {
tot = 0;
for (auto p : S) b[++tot] = p;
copy(p+1, p+1+n, a+1);
sort(a+i+1, a+1+n);
int idx = upper_bound(b+1, b+1+tot, a[i])-b;
int l = idx, r = tot, tmp = -1;
while(b[idx] > a[i] && l <= r) {
int mid = (l+r) / 2;
if (check(i+1, mid)) tmp = mid, l = mid+1;
else r = mid-1;
}
if (tmp == -1) {
int l = 1, r = idx-1;
while(l <= r) {
int mid = (l+r) / 2;
if (check(i+1, mid)) tmp = mid, l = mid+1;
else r = mid-1;
}
}
multiset<int> :: iterator it = S.lower_bound(b[tmp]);
S.erase(it);
if (b[tmp] > a[i]) now++;
ans[i] = b[tmp];
}
for (int i = 1; i <= n; i++)
printf("%d%c", ans[i], i == n ? '
' : ' ');
}