A. Ahahahahahahahaha
题意：
给定一个长度为 (n,nleq 10^3)并且 (n) 为偶数的 (01) 序列。
现在去掉最多 (frac{n}{2}) 个元素，使得剩下的序列奇数位置的和减去偶数位置的和为 (0)。
思路：
如果 (0) 的个数超过一半，那么留下所有 (0) 即可。
否则要考虑留下一些 (1)，并且这些 (1) 一定是成对出现的。考虑连续的三个数只有可能这几种情况：(001,010,011)，始终是能够选出一对出来，也就是每三个数会选两个出来，那么直接这样选直到满足条件即可。
题解的做法是根据大小关系直接构造全 (0) 或者全 (1)。
Code
// Author : heyuhhh
// Created Time : 2020/09/08 22:50:25
#include<bits/stdc++.h>
#define MP make_pair
#define fi first
#define se second
#define pb push_back
#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()
#define INF 0x3f3f3f3f
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
//head
const int N = 1e5 + 5;
void run() {
int n;
cin >> n;
vector<int> a(n);
for (int i = 0; i < n; i++)
cin >> a[i];
vector<int> b;
for (int i = 0; i < n; i++) {
int j = i + 1, k = i + 2;
if (j < n && a[i] == a[j]) {
++i;
b.emplace_back(a[i]);
b.emplace_back(a[i]);
} else if (j < n && k < n) {
i = k;
b.emplace_back(a[i]);
b.emplace_back(a[i]);
} else if (j == n) {
if (a[i] == 0)
b.emplace_back(a[i]);
} else if (k == n) {
b.emplace_back(0);
break;
}
}
cout << sz(b) << '
';
for (auto it : b)
cout << it << ' ';
cout << '
';
}
int main() {
#ifdef Local
freopen("input.in", "r", stdin);
#endif
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
cout << fixed << setprecision(20);
int T; cin >> T; while(T--)
run();
return 0;
}
B. B. Big Vova
贪心构造就行。时间复杂度 (O(n^2logn))。
Code
// Author : heyuhhh
// Created Time : 2020/09/08 22:39:15
#include<bits/stdc++.h>
#define MP make_pair
#define fi first
#define se second
#define pb push_back
#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()
#define INF 0x3f3f3f3f
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
//head
const int N = 1e5 + 5;
void run() {
int n;
cin >> n;
vector<int> a(n);
for (int i = 0; i < n; i++)
cin >> a[i];
sort(a.rbegin(), a.rend());
vector<int> b(n);
vector<bool> chk(n);
int g = 0;
for (int i = 0; i < n; i++) {
int now = -1, p;
for (int j = 0; j < n; j++) if (!chk[j]) {
if (__gcd(g, a[j]) > now) {
now = __gcd(g, a[j]);
p = j;
}
}
chk[p] = true;
b[i] = a[p];
g = __gcd(g, a[p]);
}
for (int i = 0; i < n; i++)
cout << b[i] << "
"[i == n - 1];
}
int main() {
#ifdef Local
freopen("input.in", "r", stdin);
#endif
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
cout << fixed << setprecision(20);
int T; cin >> T; while(T--)
run();
return 0;
}
C. Chocolate Bunny
题意：
交互题。
现在有一个排列 (p)，但是只知道长度。
然后最多 (2n) 次询问，每次询问 ((x,y))，会回答 (p_x\% p_y) 的值。
最后要还原排列。
思路：
询问 ((x,y),(y,x)) 即可得到较小的那个数，也就是每两次询问能确定一个数，那么通过 (2(n-1)) 次询问能够确定 (n-1) 个数，剩下一个数可以直接确定。
D. Discrete Centrifugal Jumps
题意：
现在有 (n) 根柱子，第 (i) 根的高度为 (h_i)。
现在能从 (i) 跳到 (j)，当且仅当：
- (j=i+1);
- (max(h_{i+1},cdots,h_{j-1})<min(h_i,h_j));
- (min(h_{i+1},cdots,h_{j-1})<max(h_i,h_j)).
问最少多少跳能从 (1) 到 (n)。
思路：
第一种情况不用考虑，主要来考虑第二、三种情况：
对于一个 (i)，能跳到的位置一定是一个递增的序列，并且最右边的位置是第一个高度大于等于 (h_i) 的位置，任意证明再往后就不合法了。除开最后一项，前面的一定要满足他们的高度要小于 (h_i)，即 (h_i) 是第一个高度大于他们的。
第三种情况就是一个递减序列，最右边是第一个小于等于 (h_i) 的位置，并且 (h_i) 是第一个小于他们的。
但只有小于会出问题，因为可能出现多个数相等的情况，这样只能从前面第一个小于等于/大于等于的地方转移过来。
通过单调栈预处理这些信息，然后直接 (dp) 即可，转移是常数级的，所以复杂度为 (O(n))。
Code
// Author : heyuhhh
// Created Time : 2020/09/09 00:21:00
#include<bits/stdc++.h>
#define MP make_pair
#define fi first
#define se second
#define pb push_back
#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()
#define INF 0x3f3f3f3f
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
//head
const int N = 1e5 + 5;
void run() {
int n;
cin >> n;
vector<int> a(n);
for (int i = 0; i < n; i++)
cin >> a[i];
vector<int> sta(n);
int top = -1;
vector<int> big(n);
for (int i = 0; i < n; i++) {
while (top >= 0 && a[sta[top]] <= a[i])
big[sta[top--]] = i;
sta[++top] = i;
}
while (top >= 0)
big[sta[top--]] = -1;
vector<int> small(n);
for (int i = 0; i < n; i++) {
while (top >= 0 && a[sta[top]] >= a[i])
small[sta[top--]] = i;
sta[++top] = i;
}
while (top >= 0)
small[sta[top--]] = -1;
vector<int> lbig(n);
for (int i = n - 1; i >= 0; i--) {
while (top >= 0 && a[sta[top]] <= a[i])
lbig[sta[top--]] = i;
sta[++top] = i;
}
while (top >= 0)
lbig[sta[top--]] = -1;
vector<int> lsmall(n);
for (int i = n - 1; i >= 0; i--) {
while (top >= 0 && a[sta[top]] >= a[i])
lsmall[sta[top--]] = i;
sta[++top] = i;
}
while (top >= 0)
lsmall[sta[top--]] = -1;
vector<vector<int>> G(n);
for (int i = 0; i < n; i++) {
if (lsmall[i] != -1)
G[i].push_back(lsmall[i]);
if (lbig[i] != -1)
G[i].push_back(lbig[i]);
if (small[i] != -1)
G[small[i]].push_back(i);
if (big[i] != -1)
G[big[i]].push_back(i);
}
vector<int> dp(n, INF);
dp[0] = 0;
for (int i = 1; i < n; i++) {
for (auto j : G[i]) {
dp[i] = min(dp[i], dp[j] + 1);
}
}
int res = dp[n - 1];
cout << res << '
';
}
int main() {
#ifdef Local
freopen("input.in", "r", stdin);
#endif
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
cout << fixed << setprecision(20);
run();
return 0;
}
题意：
给定一个 (n) 个点，(m) 条边的有向图，现在要给每个结点黑白染色，从一个点出发，只能走对应颜色的出边。
现在问怎么染色能使得 (1
ightarrow n) 的最短路尽可能长。
思路：
朴素想法即是从起点开始贪心染色，选择一个距离最短的出点，然后将当前点染为和该边颜色不同的颜色，这样就能避免走最短路。但是实际上代码中很复杂，因为可能会涉及回溯等问题。
实际上直接在反向图上面染色即可，从终点往前bfs进行染色。
假设当前点为 (v)，那么对于 ((u,v,t)) 这样的边，如果 (u) 点未染色就染为另一种颜色，否则距离加 (1) 并且入队。这样能保证最优性，因为假设存在另外一点 (v') 能够到 (u)，但是在后面出队，说明距离更大，那么染色过后最短路可以从 (u
ightarrow v) 这条路过来。
执行一遍上述算法即可得到最长的最短距离以及染色方案。
Code
// Author : heyuhhh
// Created Time : 2020/09/09 11:25:07
#include<bits/stdc++.h>
#define MP make_pair
#define fi first
#define se second
#define pb push_back
#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()
#define INF 0x3f3f3f3f
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
//head
const int N = 1e5 + 5;
void run() {
int n, m;
cin >> n >> m;
vector<vector<pii>> G(n);
for (int i = 0; i < m; i++) {
int u, v, t;
cin >> u >> v >> t;
--u, --v;
G[v].emplace_back(u, t);
}
vector<int> col(n, -1), dis(n, INF);
vector<bool> vis(n);
queue<int> q;
dis[n - 1] = col[n - 1] = 0;
q.push(n - 1);
while (!q.empty()) {
int v = q.front(); q.pop();
vis[v] = true;
for (auto& it : G[v]) {
int u = it.fi, t = it.se;
if (vis[u]) continue;
if (col[u] == -1) {
col[u] = 1 - t;
} else {
if (col[u] == t && dis[u] > dis[v] + 1) {
dis[u] = dis[v] + 1;
q.push(u);
}
}
}
}
int ans = dis[0];
if (ans == INF) ans = -1;
cout << ans << '
';
for (int i = 0; i < n; i++)
cout << max(0, col[i]);
cout << '
';
}
int main() {
#ifdef Local
freopen("input.in", "r", stdin);
#endif
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
cout << fixed << setprecision(20);
run();
return 0;
}