T1 签到题
模拟就好。
code
#include<bits/stdc++.h>
using namespace std;
int read() {
int x = 0, f = 1; char c = getchar();
while(c < '0' || c > '9') {if(c == '-') f = -1;c = getchar();}
while(c >= '0' && c <= '9') {x = x * 10 + c - '0';c = getchar();}
return x * f;
}
int n, now = 1, Ans;
priority_queue<int, vector<int>, greater<int> >q;
int main() {
n = read();
for (int i = 1; i <= n; i++) {
int x = read();
if(x == now) {
now = x + 1;
while(!q.empty() && (int)q.top() == now) {
now++;
q.pop();
}
continue;
}
else {
while(!q.empty() && (int)q.top() == now) {
now++;
q.pop();
}
if(now == x) Ans = max(Ans, (int)q.size());
else {
q.push(x);
Ans = max(Ans, (int)q.size());
}
}
}
cout<<Ans;
return 0;
}
T2 Z^2∼N
打表找规律，然后大力分类讨论
code
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int MAXN = 1e5 + 5;
int read() {
int x = 0, f = 1; char c = getchar();
while(c < '0' || c > '9') {if(c == '-') f = -1;c = getchar();}
while(c >= '0' && c <= '9') {x = x * 10 + c - '0';c = getchar();}
return x * f;
}
int n, m, a[MAXN];
struct node{int x, y;}b[MAXN];
signed main() {
n = read(), m = read();
for (int i = 1; i <= n; i++) {
int x = read(), y = read();
if(x == 0 && y == 0) a[i] = 0;
int ret = abs(x) + abs(y);
int cs = 1 + 2 * ret * (ret - 1);
if (x > 0 && y == 0) a[i] = cs;
if(x == 0 && y > 0) a[i] = cs + 2 * (ret - 1) + 1;
int fx = cs + 2 * (ret - 1) + 1;
if(x == 0 && y < 0) a[i] = cs + ret * 2 + (ret - 1) * 2 + 1;
if(x > 0 && y > 0) a[i] = cs + (y - 1) * 2 + 1;
if(x > 0 && y < 0) a[i] = cs + abs(y) * 2;
if(x < 0 && y >= 0) a[i] = fx + abs(x);
fx = fx + ret;
if(x < 0 && y < 0) a[i] = fx + abs(y);
}
for (int i = 1; i <= m; i++) {
int val = read();
if(val == 0) {b[i].x = 0, b[i].y = 0; continue;}
int y = sqrt((val - 1) / 2), ret;
ret = y;
for (int j = max(y - 1, 0ll); j <= y + 30; j++) {
if (1 + 2 * j * (j - 1) <= val && 1 + 2 * j * (j + 1) > val) {ret = j; break;}
}
int cs = 1 + 2 * ret * (ret - 1);
if(val == cs) b[i].x = ret, b[i].y = 0;
if(val >= cs + 1 && val <= cs + 2 * (ret - 1)) {
int cz = val - cs;
if(cz & 1) {
b[i].x = ret - (cz / 2 + 1);
b[i].y = cz / 2 + 1;
}
else {
b[i].x = ret - cz / 2;
b[i].y = (-1) * cz / 2;
}
}
if(val == cs + (ret - 1) * 2 + 1) b[i].x = 0, b[i].y = ret;
int fx = cs + (ret - 1) * 2 + 1;
if(val >= fx + 1 && val <= fx + ret) {
b[i].x = (-1) * (val - fx);
b[i].y = b[i].x + ret;
}
fx = fx + ret;
if(val >= fx + 1 && val <= fx + (ret - 1)) {
b[i].y = (val - fx) * (-1);
b[i].x = (-ret) - b[i].y;
}
if(val == fx + ret) {
b[i].x = 0, b[i].y = (-1) * ret;
}
}
for (int i = 1; i <= n; i++) cout<<a[i]<<"\n";
for (int i = 1; i <= m; i++) cout<<b[i].x<<" "<<b[i].y<<"\n";
return 0;
}
T3 P=NP
solution
稍微把那个取最大值的条件转化一下，其实就是一种颜色只能取一次最大值。
有一个朴素的状压 dp：对于每个点 \(i\) 和集合 \(S\)，\(dp[i][S]\) 代表到达 \(i\)，在 \(S\) 中的点取过颜色，得到的最大路径长度。转移就是对于每条边 \(u\to v\)，分别考虑要不要取 \(v\) 的权值。如果要取，那么必须之前没取过，也就是对于不包含 \(c_v\) 的集合 \(S\) 有 \(dp[v][S\cup\{c_v\}]\leftarrow dp[u][S]+a_v\)。如果不取就随意了，转移是 \(dp[v][S]\leftarrow dp[u][S]\)。这样复杂度是 \(m2^n\)。
然后你发现，如果一种颜色只出现了一次，显然没必要放到状压里，无脑取就行了
于是你只需要记出现至少两次的点，最多有 \(\frac n2\) 个。然后就做完了……时间复杂度 \(m2^{n/2}\)
code
#include<bits/stdc++.h>
using namespace std;
const int MAXN = 1e5 + 5;
int read() {
int x = 0, f = 1; char c = getchar();
while(c < '0' || c > '9') {if(c == '-') f = -1;c = getchar();}
while(c >= '0' && c <= '9') {x = x * 10 + c - '0';c = getchar();}
return x * f;
}
int n, m, cnt[40], f[37][(1 << 18)], id[40], tot, val[40], col[40];
vector<int>e[40];
int main() {
n = read();
for (int i = 1; i <= n; i++) {
col[i] = read(), val[i] = read();
cnt[col[i]]++;
if(cnt[col[i]] == 2) id[col[i]] = ++tot;
}
m = read();
for (int i = 1; i <= m; i++) {
int u = read(), v = read();
e[v].push_back(u);
}
memset(f, -0x3f, sizeof f);
if(cnt[col[1]] == 1) f[1][0] = val[1];
else {
f[1][(1 << (id[col[1]] - 1))] = val[1];
f[1][0] = 0;
}
for (int i = 2; i <= n; i++) {
for (int k = 0; k < e[i].size(); k++) {
int j = e[i][k];
for (int S = 0; S < 1 << tot; S++) {
if(cnt[col[i]] == 1) f[i][S] = max(f[i][S], f[j][S] + val[i]);
else {
f[i][S] = max(f[i][S], f[j][S]);
int M = S | (1 << id[col[i]] - 1);
if(!(S & (1 << id[col[i]] - 1))) f[i][M] = max(f[i][M], f[j][S] + val[i]);
}
}
}
}
for (int i = 1; i <= n; i++) {
int ans = *max_element(f[i], f[i] + (1 << tot));
if(ans < 0) ans = 0;
cout<<ans<<"\n";
}
system("pause");
return 0;
}
T4 后缀数组
solution
考虑 SA 中相邻的元素，也就是排名相邻的两个串。如果你知道 Height，相当于你就知道了 \(h_i\) 对字符的相等关系，和末尾一对字符的小于关系。对于相等关系，可以用并查集合并。
如果你不知道 Height，那也可以通过判断它后面的字符串的大小关系确定能不能相等。即，对于后缀 \(x,y\)，\(x\) 的字典序小于 \(y\)。如果 \(x+1\) 字典序小于 \(y+1\)，那么 \(x,y\) 位置的字符可以取等，否则必须 \(s_x<s_y\)。判断 \(x+1,y+1\) 的字典序可以通过求 SA 的逆数组得到。
然后把这些小于关系在并查集合并后的点上连边，那实际上就是找一个字典序最小拓扑序。可以按照 SA 的顺序贪心，每个合并后的点放能放的最小值，这样一定是字典序最小的（因为每个字符都是最小的）
code
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
#define X first
#define Y second
#define ALL(v) v.begin(), v.end()
#define pb push_back
#define SZ(a) ((int)a.size())
const int MAXn = 5005;
int sa[MAXn], hei[MAXn], rk[MAXn], val[MAXn];
int g[MAXn];
int f(int x) {
return g[x] = (g[x] == x ? x : f(g[x]));
}
void mg(int a, int b) {
a = f(a), b = f(b);
g[a] = b;
}
vector<int> v[MAXn];
void add(int x, int y) {
// x < y
v[y].pb(x);
}
int main() {
ios::sync_with_stdio(0), cin.tie(0);
int n;
cin >> n;
for (int i = 1; i <= n; i++)
cin >> sa[i], rk[sa[i]] = i;
for (int i = 1; i < n; i++)
cin >> hei[i];
for (int i = 1; i <= n + 1; i++)
g[i] = i;
rk[n + 1] = 0;
for (int i = 1; i < n; i++) {
if (hei[i] != -1) {
for (int j = 0; j < hei[i]; j++)
mg(sa[i] + j, sa[i + 1] + j);
}
}
for (int i = 1; i < n; i++) {
if (hei[i] != -1) {
add(f(sa[i] + hei[i]), f(sa[i + 1] + hei[i]));
}
if (rk[sa[i] + 1] > rk[sa[i + 1] + 1])
add(f(sa[i]), f(sa[i + 1]));
}
val[n + 1] = -1;
for (int i = 1; i <= n; i++)
val[i] = -2;
int cur = 0;
for (int i = 1; i <= n; i++) {
int t = f(sa[i]);
if (val[t] != -2) {
assert(val[t] == cur);
continue;
}
for (ll x : v[t]) {
assert(val[x] != -2);
cur = max(cur, val[x] + 1);
}
assert(cur < 26);
val[t] = cur;
}
for (int i = 1; i <= n; i++)
cout << (char)('a' + val[f(i)]);
cout << endl;
}