2019 Multi-University Training Contest 2
Beauty Of Unimodal Sequence
这个题的最长长度好求，主要是考虑如何字典序最小以及字典序最大。
对于字典序最小，最直接的想法就是一个一个取，然后看剩下的能不能满足条件；而字典序最大的话，就是能不取就先不取。
考虑动态规划：\(dp[i][0/1]\)表示在\(i...n\)中，处于下降/上升状态的最长的满足条件的序列。转移的话\(dp[i][0]\)比较好转移，在后面找个\(max\{dp[j][0]\}\)即可；\(dp[i][1]\)就需要分情况了，因为可能从\(dp[j][0/1]\)转移过来，转移方程代码中写得应该比较清楚了。
求出这个过后，最长长度易得，假设为\(len\)。之后将所有的\(dp[len][1],dp[len-1][1],\cdots,dp[1][1]\)存入一个\(vector\)中，\(0\)也同样，这时\(vector\)存储的就是每种答案可能的位置。因为随着\(len\)的减小，最终的位置是不断增加的，那么就直接暴力来判断就行了。
具体见代码吧：
Code
#include <bits/stdc++.h>
#define INF 0x3f3f3f3f
using namespace std;
typedef long long ll;
const int N = 3e5 + 5;
struct Seg{
int mx[N << 2];
void build(int o, int l, int r) {
mx[o] = 0;
if(l == r) return ;
int mid = (l + r) >> 1;
build(o << 1, l, mid); build(o << 1|1, mid + 1, r);
}
void update(int o, int l, int r, int p, int v) {
if(l == r && l == p) {
mx[o] = v;
return;
}
int mid = (l + r) >> 1;
if(p <= mid) update(o << 1, l, mid, p, v);
else update(o << 1|1, mid + 1, r, p, v);
mx[o] = max(mx[o << 1], mx[o << 1|1]);
}
int query(int o, int l, int r, int L, int R) {
if(L <= l && r <= R) return mx[o];
int mid = (l + r) >> 1, ans = 0;
if(L <= mid) ans = max(ans, query(o << 1, l, mid, L, R));
if(R > mid) ans = max(ans, query(o << 1|1, mid + 1, r, L, R));
return ans;
}
}seg[2];
int n;
int a[N], b[N];
int dp[N][2];
vector <vector <vector<int> > > v;
int main() {
// ios::sync_with_stdio(false); cin.tie(0);
while(scanf("%d", &n) != EOF) {
for(int i = 1; i <= n; i++) scanf("%d", &a[i]), b[i] = a[i]; b[n + 1] = 0;
sort(b + 1, b + n + 2);
int D = unique(b + 1, b + n + 2) - b;
for(int i = 1; i <= n; i++) a[i] = lower_bound(b + 1, b + D, a[i]) - b;
seg[0].build(1, 1, D); seg[1].build(1, 1, D);
for(int i = 1; i <= n; i++) dp[i][0] = dp[i][1] = 0;
for(int i = n; i >= 1; i--) {
dp[i][0] = dp[i][1] = 1;
dp[i][1] = max(dp[i][1], seg[1].query(1, 1, D, 1, a[i] - 1) + 1);
dp[i][0] = max(dp[i][0], seg[1].query(1, 1, D, a[i] + 1, D) + 1);
dp[i][0] = max(dp[i][0], seg[0].query(1, 1, D, a[i] + 1, D) + 1);
dp[i][0] = max(dp[i][0], dp[i][1]);
seg[0].update(1, 1, D, a[i], dp[i][0]);
seg[1].update(1, 1, D, a[i], dp[i][1]);
}
int Max = 0;
for(int i = 1; i <= n; i++) for(int j = 0; j < 2; j++) Max = max(Max, dp[i][j]);
v.clear(); v.resize(n + 1);
for(int i = 1; i <= n; i++) v[i].resize(2);
for(int i = 1; i <= n; i++) {
v[dp[i][0]][0].push_back(i);
v[dp[i][1]][1].push_back(i);
}
vector <int> small, big;
int len = 0, sta = 0, now = 0;
while(len < Max) {
int pos = INF, nsta = 0;
if(sta == 0) {
for(auto it : v[Max - len][0]) {
if((now == 0 || a[it] > a[now]) && it < pos && it > now) {
pos = it; nsta = 0; break;
}
}
for(auto it : v[Max - len][1]) {
if((now == 0 || a[it] < a[now]) && it < pos && it > now) {
pos = it; nsta = 1; break;
}
}
} else {
for(auto it : v[Max - len][1]) {
if((now == 0 || a[it] < a[now]) && it < pos && it > now) {
pos = it; nsta = 1; break;
}
}
}
small.push_back(pos);
now = pos; sta = nsta;
len++;
}
len = 0, sta = 0, now = 0;
while(len < Max) {
int pos = 0, nsta = 0;
if(sta == 0) {
for(auto it : v[Max - len][0]) {
if((now == 0 || a[it] > a[now]) && it > pos && it > now) {
pos = it;
}
}
for(auto it : v[Max - len][1]) {
if((now == 0 || a[it] < a[now]) && it > pos && it > now) {
pos = it; nsta = 1;
}
}
} else {
for(auto it : v[Max - len][1]) {
if((now == 0 || a[it] < a[now]) && it > pos && it > now) {
pos = it; nsta = 1;
}
}
}
big.push_back(pos);
now = pos; sta = nsta;
len++;
}
for(int i = 0; i < Max; i++) printf("%d%c", small[i], " \n"[i == Max - 1]);
for(int i = 0; i < Max; i++) printf("%d%c", big[i], " \n"[i == Max - 1]);
}
return 0;
}
Everything Is Generated In Equal Probability
考场上直接找的规律，就不贴代码了，说说公式是如何推的吧。
假设\(f(n)\)为长度为\(n\)时的答案，然后就有：\(f(n)=\frac{1}{2}C_{n}^{2}+\frac{1}{2^n}\sum_{j=1}^{n}f(j)*C_{n}^{j}\)。
注意到右边求和时会枚举到\(j\)，就单独分出来，移到左边，会得到：\((1-\frac{1}{2^n})f(n)=\frac{1}{2}C_n^2+\frac{1}{2^n}\sum_{j=1}^{n - 1}f(j)*C_{n}^{j}\)。
之后将左边除过去就ok了，可以\(O(n^2)\)预处理出来。
Harmonious Army
比较套路的一个网络流，将收益最大转化为损失最小，然后考虑最小割，建图的话保证建出来的图的最小割只能是那几种情况，之后解方程求出每条边的收益就行了。
代码如下：
Code
#include <bits/stdc++.h>
#define INF 0x3f3f3f3f
using namespace std;
typedef long long ll;
const int N = 2e5 + 5;
template <class T>
struct Dinic{
struct Edge{
int v, next;
T flow;
Edge(){}
Edge(int v, int next, T flow) : v(v), next(next), flow(flow) {}
}e[N << 1];
int head[N], tot;
int dep[N];
void init() {
memset(head, -1, sizeof(head)); tot = 0;
}
void adde(int u, int v, T w, T rw = 0) {
e[tot] = Edge(v, head[u], w);
head[u] = tot++;
e[tot] = Edge(u, head[v], rw);
head[v] = tot++;
}
bool BFS(int _S, int _T) {
memset(dep, 0, sizeof(dep));
queue <int> q; q.push(_S); dep[_S] = 1;
while(!q.empty()) {
int u = q.front(); q.pop();
for(int i = head[u]; ~i; i = e[i].next) {
int v = e[i].v;
if(!dep[v] && e[i].flow > 0) {
dep[v] = dep[u] + 1;
q.push(v);
}
}
}
return dep[_T] != 0;
}
T dfs(int _S, int _T, T a) {
T flow = 0, f;
if(_S == _T || a == 0) return a;
for(int i = head[_S]; ~i; i = e[i].next) {
int v = e[i].v;
if(dep[v] != dep[_S] + 1) continue;
f = dfs(v, _T, min(a, e[i].flow));
if(f) {
e[i].flow -= f;
e[i ^ 1].flow += f;
flow += f;
a -= f;
if(a == 0) break;
}
}
if(!flow) dep[_S] = -1;
return flow;
}
T dinic(int _S, int _T) {
T max_flow = 0;
while(BFS(_S, _T)) max_flow += dfs(_S, _T, INF);
return max_flow;
}
};
Dinic <ll> G;
int n, m;
int main() {
ios::sync_with_stdio(false); cin.tie(0);
while(cin >> n >> m) {
G.init();
int S = 0, T = n + 1;
ll sum = 0;
for(int i = 1; i <= m; i++) {
int u, v, a, b, c;
cin >> u >> v >> a >> b >> c;
a *= 2, b *= 2, c *= 2;
G.adde(S, u, (b + c) / 2);
G.adde(S, v, (b + c) / 2);
G.adde(u, v, (a + c) / 2 - b);
G.adde(v, u, (a + c) / 2 - b);
G.adde(u, T, (a + b) / 2);
G.adde(v, T, (a + b) / 2);
sum += a + b + c;
}
cout << (ll)(sum - G.dinic(S, T)) / 2 << '\n';
}
return 0;
}
I Love Palindrome String
利用回文自动机求出本质不同的回文串，然后对于每个回文串马拉车判断其一半是否为回文串，最后将结果加起来即可。
代码中\(cnt\)数组的含义即为该回文串的出现次数，因为它可能为一些其它回文串的后缀，\(count\)函数累加的时候将其计算了出来。
Code
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 3e5 + 5;
struct Manacher{
char ch[N << 1];
int p[N << 1];
void work(char *s) {
int l = 0;
ch[l++] = '&'; ch[l++] = '#';
for(int i = 0; s[i]; i++) {
ch[l++] = s[i];
ch[l++] = '#';
}
ch[l] = '\0';
int mx = 0, id = 0;
for(int i = 0; i < l; i++) {
p[i] = i < mx ? min(p[2 * id - i], mx - i) : 1;
while(ch[i + p[i]] == ch[i - p[i]]) p[i]++;
if(i + p[i] > mx) mx = i + p[i], id = i;
}
}
bool check(int l, int r) {
int mid = (l * 2 + r * 2) >> 1;
return p[mid] - 1 >= r - l + 1;
}
}Man;
namespace PAM{
int ch[N][26], fail[N], len[N], st[N], cnt[N];
int sz, n, last;
int New(int l, int f) {
memset(ch[++sz], 0, sizeof(ch[sz]));
len[sz] = l, fail[sz] = f;
return sz;
}
void init() {
sz = -1;
New(0, 1); last = New(-1, 0);
st[n = 0] = -1;
memset(cnt, 0, sizeof(cnt));
}
int getf(int x) {
while(st[n - len[x] - 1] != st[n]) x = fail[x];
return x;
}
bool Insert(int c) { //int
st[++n] = c;
int x = getf(last);
bool F = 0;
if(!ch[x][c]) {
F = 1;
int f = getf(fail[x]);
ch[x][c] = New(len[x] + 2, ch[f][c]);
}
last = ch[x][c];
cnt[last]++;
return F;
}
void count() {
for(int i = sz; i >= 1; i--) cnt[fail[i]] += cnt[i];
}
};
char s[N];
int f[N], g[N], Len[N];
int main() {
while(scanf("%s", s + 1) != EOF) {
Man.work(s + 1);
int len = strlen(s + 1);
for(int i = 1; i <= len; i++) Len[i] = 0;
PAM::init();
for(int i = 1; i <= len; i++) {
if(PAM::Insert(s[i] - 'a')) {
g[i] = 1;
} else g[i] = 0;
f[i] = PAM::last;
}
PAM::count();
for(int i = 1; i <= len; i++) {
if(!g[i]) continue;
int length = PAM::len[f[i]];
int r = i;
int l = i - length + 1;
int mid = (l + r) >> 1;
if(Man.check(l, mid)) {
Len[length] += PAM::cnt[f[i]];
}
}
for(int i = 1; i <= len; i++) printf("%d%c", Len[i], " \n"[i == len]);
}
return 0;
}
Just Skip The Problem
比较水的一个题。
Code
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MOD = 1e6 + 3;
ll fac[MOD];
int main() {
ios::sync_with_stdio(false); cin.tie(0);
fac[0] = 1;
for(int i = 1; i < MOD; i++) fac[i] = fac[i - 1] * i % MOD;
int n;
while(cin >> n) {
if(n >= MOD) cout << 0 << '\n';
else cout << fac[n] << '\n';
}
return 0;
}
Keen On Everything But Triangle
一开始考虑的是莫队+set结果T飞了。。
其实这个题就直接考虑贪心就行了，每次取当前最大的三个出来判断能否构成三角形，不能就继续选次三大的...依次这样，可以借助斐波拉契亚数列证明最多只用选50多个数就能得到答案。
所以问题就变为了求区间前\(k\)大数了，这个直接上主席树就行了。
Code
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5 + 5;
int n, q;
int a[N], b[N], c[N], d[N];
int T;
int rt[N], ls[N * 20], rs[N * 20];
int sum[N * 20];
vector <ll> v;
void build(int &o, int l, int r) {
o = ++T;
sum[o] = 0;
if(l == r) return;
int mid = (l + r) >> 1;
build(ls[o], l, mid); build(rs[o], mid + 1, r);
}
void insert(int &o, int l, int r, int last, int v) {
o = ++T;
sum[o] = sum[last] + 1;
ls[o] = ls[last]; rs[o] = rs[last];
if(l == r) return ;
int mid = (l + r) >> 1;
if(v <= mid) insert(ls[o], l, mid, ls[last], v);
else insert(rs[o], mid + 1, r, rs[last], v);
}
int query(int o, int last, int l, int r, int k) {
if(l == r) return l;
int s = sum[rs[o]] - sum[rs[last]];
int mid = (l + r) >> 1;
if(s >= k) return query(rs[o], rs[last], mid + 1, r, k);
else return query(ls[o], ls[last], l, mid, k - s);
}
int main() {
ios::sync_with_stdio(false); cin.tie(0);
while(cin >> n >> q) {
T = 0;
for(int i = 1; i <= n; i++) cin >> a[i], b[i] = c[i] = d[i] = a[i];
sort(b + 1, b + n + 1);
int D = unique(b + 1, b + n + 1) - b - 1;
for(int i = 1; i <= n; i++) a[i] = lower_bound(b + 1, b + D + 1, a[i]) - b, d[a[i]] = c[i];
build(rt[0], 1, D);
for(int i = 1; i <= n; i++) insert(rt[i], 1, D, rt[i - 1], a[i]);
while(q--){
int l, r; cin >> l >> r;
v.clear();
for(int i = 1; i <= min(50, r - l + 1); i++) {
v.push_back(query(rt[r], rt[l - 1], 1, D, i));
}
int SZ = v.size(), f = 1;
for(int i = 0; i < SZ; i++) v[i] = d[v[i]];
for(int i = 0; i + 2 < SZ; i++) {
if(v[i] < v[i + 1] + v[i + 2]) {
cout << v[i] + v[i + 1] + v[i + 2] << '\n';
f = 0; break;
}
}
if(f) cout << -1 << '\n';
}
}
return 0;
}
Longest Subarray
一开始考虑的是分治，但似乎也可以搞，但我们没有搞出来= =
观察题目条件，因为要求最长的区间，可以考虑固定一个右端点，然后寻找合适的左端点来更新答案。之后就会发现左端点的不合法情况对于每个数来说都是一个区间（脑补一下即可）。那么对于不合法的区间可以打个标记，比如说都加上一个1，最后就求前面最远的一个0的位置，这个显然可以用线段树来解决。
问题的关键就是发现对于每一个数来说，不合法的情况是连续的区间。
代码如下：
Code
#include <bits/stdc++.h>
#define INF 0x3f3f3f3f
using namespace std;
typedef long long ll;
const int N = 1e5 + 5;
int n, c, k;
int a[N], lastl[N], lastr[N];
int sumv[N << 2], mn[N << 2], lz[N << 2];
void push_up(int o) {
sumv[o] = sumv[o << 1] + sumv[o << 1|1];
mn[o] = min(mn[o << 1], mn[o << 1|1]);
}
void push_down(int o, int l, int r) {
if(lz[o]) {
int mid = (l + r) >> 1;
lz[o << 1] += lz[o]; lz[o << 1|1] += lz[o];
sumv[o << 1] += (mid - l + 1) * lz[o];
sumv[o << 1|1] += (r - mid) * lz[o];
mn[o << 1] += lz[o];
mn[o << 1|1] += lz[o];
lz[o] = 0;
}
}
void build(int o, int l, int r) {
lz[o] = 0;
if(l == r) {
sumv[o] = 0; mn[o] = 0;
return;
}
int mid = (l + r) >> 1;
build(o << 1, l, mid); build(o << 1|1, mid + 1, r);
push_up(o);
}
void update(int o, int l, int r, int L, int R, int v) {
if(L > R || L == 0) return;
if(L <= l && r <= R) {
mn[o] += v; lz[o] += v;
sumv[o] += (r - l + 1) * v;
return;
}
push_down(o, l, r);
int mid = (l + r) >> 1;
if(L <= mid) update(o << 1, l, mid, L, R, v);
if(R > mid) update(o << 1|1, mid + 1, r, L, R, v);
push_up(o);
}
int query(int o, int l, int r, int L, int R) {
if(l == r) return l;
push_down(o, l, r);
int mid = (l + r) >> 1;
if(mn[o << 1] <= 0) return query(o << 1, l, mid, L, R);
if(R > mid && mn[o << 1|1] <= 0) return query(o << 1|1, mid + 1, r, L, R);
return INF;
}
vector <int> pos[N];
int main() {
ios::sync_with_stdio(false); cin.tie(0);
while(cin >> n >> c >> k) {
for(int i = 1; i <= c; i++) lastl[i] = lastr[i] = 0, pos[i].clear();
for(int i = 1; i <= n; i++) cin >> a[i];
build(1, 1, n);
int ans = 0;
for(int r = 1; r <= n; r++) {
pos[a[r]].push_back(r);
int sz = (int)pos[a[r]].size();
update(1, 1, n, lastl[a[r]] + 1, lastr[a[r]], -1);
if(sz >= k) {
lastl[a[r]] = pos[a[r]][sz - k], lastr[a[r]] = r;
} else {
lastr[a[r]] = r;
}
update(1, 1, n, lastl[a[r]] + 1, lastr[a[r]], 1);
int l = query(1, 1, n, 1, r);
ans = max(ans, r - l + 1);
}
cout << ans << '\n';
}
return 0;
}