A. The Fair Nut and Elevator
Solved.
签.
#include <bits/stdc++.h>
using namespace std; #define N 110
int n, a[N]; int main()
{
while (scanf("%d", &n) != EOF)
{
for (int i = ; i <= n; ++i) scanf("%d", a + i);
int res = 1e9;
for (int x = , tmp = ; x <= ; ++x, res = min(res, tmp), tmp = ) for (int i = ; i <= n; ++i) if (a[i])
{
tmp += a[i] * (abs(x - i) + abs(i - ) + abs(x - ) + abs(x - ) + abs(i - ) + abs(x - i));
}
printf("%d\n", res);
}
return ;
}
B. Kvass and the Fair Nut
Upsolved.
题意：
刚开始题意读错，过了pretest就没管了
有$n桶啤酒，要从中取出s升，求取出后剩余的量最少的那桶啤酒最大$
思路：
二分或者直接算都行
#include <bits/stdc++.h>
using namespace std; #define ll long long
#define N 1010
int n;
ll s, v[N]; bool check(ll x)
{
ll tot = ;
for (int i = ; i <= n; ++i)
{
if (v[i] < x) return false;
tot += v[i] - x;
}
return tot >= s;
} int main()
{
while (scanf("%d%lld", &n, &s) != EOF)
{
for (int i = ; i <= n; ++i) scanf("%lld", v + i);
ll l = , r = 1e9, res = -;
while (l <= r)
{
ll mid = (l + r) >> ;
if (check(mid))
{
res = mid;
l = mid + ;
}
else
r = mid - ;
}
printf("%lld\n", res);
}
return ;
}
C. The Fair Nut and String
Solved.
题意：
有一串字符串，求有多少个字符串，是abababab形式的。
思路：
字符不是‘a’ 也不是‘b’ 的话是没用的，然后如果两个'a'之间有多个'b'也没用
缩短字符串后
必然是aaabaaababab 这样的形式的
那么像统计DAG那样统计就没了
#include <bits/stdc++.h>
using namespace std; #define ll long long
#define N 100010
const ll MOD = (ll)1e9 + ;
char s[N], t[N]; int main()
{
while (scanf("%s", s + ) != EOF)
{
int n = ;
for (int i = , len = strlen(s + ); i <= len; ++i) if (s[i] == 'a' || s[i] == 'b')
{
if (s[i] == 'a') t[++n] = 'a';
else if (s[i] == 'b' && t[n] == 'a') t[++n] = 'b';
}
if (n == )
{
puts("");
continue;
}
ll res = , pre = , cnt = ;
for (int i = ; i <= n; ++i)
{
if (t[i] == 'b')
{
pre = (pre * (cnt + )) % MOD;
cnt = ;
}
else
{
++cnt;
res = (res + pre) % MOD;
}
}
printf("%lld\n", res);
}
return ;
}
D. The Fair Nut and the Best Path
Upsolved.
题意：
在一棵树上，每个点是加油站，最多加油$w_i，然后每条边是路，耗费油v_i$
$定义f(u, v)为u->v的简单路径上每个点都加满油，假设油箱容量无限，最后剩下的油量$
如果其中某条路上油耗尽了，那么这条路是不可行的
思路：
我们把点权视为正直，边权视为负值
然后就是求任意两点之间的最大权值和
不需要考虑不合法的路径，因为如果存在不合法的路劲，
那么肯定存在另一条合法的路径使得答案比它更优。
令$f[u] 表示到达u的子树中某点的最大权， 这是纵向路径$
再考虑横向路径即可
#include <bits/stdc++.h>
using namespace std; #define ll long long
#define N 300010
#define pii pair <int, int>
int n, w[N];
vector <pii> G[N];
ll res, f[N]; void DFS(int u, int fa)
{
f[u] = w[u];
ll Max[] = {, };
for (auto it : G[u])
{
int v = it.first;
if (v == fa) continue;
DFS(v, u);
ll cost = it.second;
f[u] = max(f[u], f[v] - cost + w[u]);
ll tmp = f[v] - cost;
if (tmp > Max[])
{
Max[] = Max[];
Max[] = tmp;
}
else if (tmp > Max[])
Max[] = tmp;
}
res = max(res, max(f[u], Max[] + Max[] + w[u]));
} int main()
{
while (scanf("%d", &n) != EOF)
{
for (int i = ; i <= n; ++i) scanf("%d", w + i);
for (int i = ; i <= n; ++i) G[i].clear();
for (int i = , u, v, w; i < n; ++i)
{
scanf("%d%d%d", &u, &v, &w);
G[u].emplace_back(v, w);
G[v].emplace_back(u, w);
}
res = ;
DFS(, );
printf("%lld\n", res);
}
return ;
}
E. The Fair Nut and Strings
Upsolved.
题意：
一共有$k个长度为n的字符串，他们的范围是[s, t] 之间，按字典序排序$
求这些字符串(构造k个满足字典序要求的字符串)最多有多少个前缀
思路：
相当于给出一棵二叉字典树，给出左右界，叶子节点不超过$k个$
求最多节点个数
能扩展就扩展，贪心一下即可
注意特判$k = 1$
#include <bits/stdc++.h>
using namespace std; #define ll long long
#define N 500010
int n, k;
char s[N], t[N]; int main()
{
while (scanf("%d%d", &n, &k) != EOF)
{
scanf("%s%s", s + , t + );
if (k == )
{
printf("%d\n", n);
continue;
}
int flag = ;
ll cur = , res = ; k -= ;
for (int i = ; i <= n; ++i)
{
if (flag == && s[i] != t[i])
flag = ;
else if (flag == )
{
ll extend = cur;
if (s[i] == 'a') ++extend;
if (t[i] == 'b') ++extend;
if (extend <= k)
{
k -= extend;
cur += extend;
}
else
{
cur += k;
k = ;
}
}
res += cur + + flag;
}
printf("%lld\n", res);
}
return ;
}
F. Max Mex
Upsolved.
题意：
一棵树上，两种操作
$交换两点的p[]值$
$询问MEX(v(l)), l表示某挑简单路径上权值的集合$
思路：
我们考虑将点按权值排序
我们考虑$1 -> i 和 i + 1 -> j$
$这两段的合并$
如果可以合并，那么答案的下限就是$j$
$树上的路径有三种类型$
$1、一个点$
$2、一条链$
$3、两条链$
那分情况讨论，一共只有6种情况
$但是这样太麻烦了$
$我们考虑这三种状态都可以用两条链的情况来表示$
$那么合并的时候，一条路径可以用两个点来表示$
$那么一条路径如果包含另外一条路径的两个端点$
$那么这条路径就包含另外一条路径$
$也就是说我们只需要分两次合并另外一条路径的两点即可$
$这样就只有一种情况$
#include <bits/stdc++.h>
using namespace std; #define N 200010
int n, q, p[N];
vector <int> G[N]; int in[N], out[N];
namespace ST
{
int rmq[N << ];
int mm[N << ];
int dp[N << ][];
int F[N << ], P[N];
int cnt, cnt2;
void init(int n)
{
mm[] = -;
for (int i = ; i <= n; ++i)
{
mm[i] = ((i & (i - )) == ) ? mm[i - ] + : mm[i - ];
dp[i][] = i;
}
for (int j = ; j <= mm[n]; ++j)
for (int i = ; i + ( << j) - <= n; ++i)
{
dp[i][j] = rmq[dp[i][j - ]] < rmq[dp[i + ( << (j - ))][j - ]] ?
dp[i][j - ] : dp[i + ( << (j - ))][j - ];
}
}
void DFS(int u, int pre, int dep)
{
F[++cnt] = u;
rmq[cnt] = dep;
P[u] = cnt;
in[u] = ++cnt2;
for (auto v : G[u]) if (v != pre)
{
DFS(v, u, dep + );
F[++cnt] = u;
rmq[cnt] = dep;
}
out[u] = cnt2;
}
void init(int root, int node_num)
{
cnt = ; cnt2 = ;
DFS(root, root, );
init( * node_num - );
}
int query(int a, int b)
{
a = P[a], b = P[b];
if (a > b) swap(a, b);
int k = mm[b - a + ];
return F[rmq[dp[a][k]] <= rmq[dp[b - ( << k) + ][k]] ?
dp[a][k] : dp[b - ( << k) + ][k]];
}
} namespace SEG
{
struct node
{
int u, v, p;
void init() { u = v = p = ; }
node () {}
node (int u, int v, int p) : u(u), v(v), p(p) {}
}a[N << ], res;
int ans;
void init() { memset(a, , sizeof a); }
bool anc(int x, int y)
{
return in[x] <= in[y] && out[x] >= out[y];
}
node check(node a, int y)
{
if (a.u == - || y == -) return node(-, -, -);
if (!y) return a;
if (!a.u) return node(y, y, y);
if (!anc(a.u, a.v)) swap(a.u, a.v);
if (anc(a.u, a.v))
{
if (anc(a.u, y))
{
int p = ST::query(y, a.v);
if (p == y)
return a;
else if (p == a.u)
return node(a.v, y, a.u);
else if (p == a.v)
return node(a.u, y, a.u);
else
return node(-, -, -);
}
else if (anc(y, a.u))
return node(y, a.v, y);
else
{
int p = ST::query(a.v, y);
return node(a.v, y, p);
}
}
else if (anc(a.p, y))
{
if (anc(a.u, y))
return node(y, a.v, a.p);
else if (anc(a.v, y))
return node(a.u, y, a.p);
else if (anc(y, a.u) || anc(y, a.v))
return a;
else
return node(-, -, -);
}
else
return node(-, -, -);
}
node merge(node a, node b)
{
a = check(a, b.u);
a = check(a, b.v);
return a;
}
void update(int id, int l, int r, int pos, int v)
{
if (l == r)
{
a[id] = node(v, v, v);
return;
}
int mid = (l + r) >> ;
if (pos <= mid) update(id << , l, mid, pos, v);
else update(id << | , mid + , r, pos, v);
a[id] = merge(a[id << ], a[id << | ]);
// printf("%d %d %d %d %d %d\n", l, r, a[id].t, a[id].u, a[id].v, a[id].p);
// printf("%d %d %d %d %d %d\n", l, mid, a[id << 1].t, a[id << 1].u, a[id << 1].v, a[id << 1].p);
// printf("%d %d %d %d %d %d\n", mid + 1, r, a[id << 1 | 1].t, a[id << 1 | 1].u, a[id << 1 | 1].v, a[id << 1 | 1].p);
// puts("*************************************");
}
bool query(int id, int l, int r)
{
node tmp = merge(res, a[id]);
// printf("bug %d %d %d %d %d\n", l, r, a[id].u, a[id].v, a[id].p);
// printf("bug %d %d %d %d %d\n", l, r, res.u, res.v, res.p);
// printf("bug %d %d %d %d %d\n", l, r, tmp.u, tmp.v, tmp.p);
// puts("**********************");
if (tmp.u != -)
{
res = tmp;
ans = r;
return ;
}
if (l == r) return ;
int mid = (l + r) >> ;
if (query(id << , l, mid))
query(id << | , mid + , r);
return ;
}
} int main()
{
while (scanf("%d", &n) != EOF)
{
for (int i = ; i <= n; ++i) G[i].clear();
for (int i = ; i <= n; ++i) scanf("%d", p + i), p[i] += ;
for (int v = , u; v <= n; ++v)
{
scanf("%d", &u);
G[u].push_back(v);
G[v].push_back(u);
}
ST::init(, n);
SEG::init();
for (int i = ; i <= n; ++i)
{
//printf("%d %d\n", p[i], i);
SEG::update(, , n, p[i], i);
}
scanf("%d", &q);
for (int i = , op, x, y; i <= q; ++i)
{
scanf("%d", &op);
if (op == )
{
scanf("%d%d", &x, &y);
swap(p[x], p[y]);
SEG::update(, , n, p[x], x);
SEG::update(, , n, p[y], y);
}
else
{
//for (int i = 1; i <= n; ++i) printf("%d%c", p[i], " \n"[i == n]);
SEG::res.init(); SEG::ans = ;
SEG::query(, , n);
printf("%d\n", SEG::ans);
}
}
}
return ;
}