官方数据没出，根据目前已知信息瞎写，有错误请帮忙指出
假期计划
要找 \(1 - a - b - c - d - 1\) 的形式，不想偏的话应该能想到预处理一部分然后拼接
预处理形式相同的部分 \(1 - a - b\) \(1 - d - c\)
把信息放在 \(b / c\) 上
考虑拼接 \(b, c\)， 此时唯一的问题是可能会经过重复点，所以需要对他们的前驱点进行讨论
注意到一方有两个点，那么另外一方只要有至少三个点一定能匹配上一组合法的
于是对每个点记录最大前驱，次大前驱，次次大前驱，拼接时候枚举使用哪个前驱即可
code
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
ll read(){
ll x = 0; char c = getchar();
while(!isdigit(c)){c = getchar();}
do{x = x * 10 + (c ^ 48); c = getchar();}while(isdigit(c));
return x;
}
const int maxn = 2505;
const ll inf = 0x3f3f3f3f3f3f3f3f;
int n, m, k;
ll val[maxn];
int dis[maxn][maxn];
int head[maxn], tot;
struct edge{int to, net;}e[20005];
void add(int u, int v){
e[++tot].net = head[u];
head[u] = tot;
e[tot].to = v;
}
queue<int>q;
void get_dis(int s){
q.push(s);
while(!q.empty()){
int x = q.front(); q.pop();
for(int i = head[x]; i; i = e[i].net){
int v = e[i].to;
if(dis[s][v] > dis[s][x] + 1){
dis[s][v] = dis[s][x] + 1;
q.push(v);
}
}
}
}
int mx[maxn], cmx[maxn], ccmx[maxn];
ll getval(int x, int px, int y, int py){
if(!x || !y || !px || !py)return -inf;
if(x == y || x == py || y == px || px == py)return -inf;
if(dis[1][px] > k || dis[1][py] > k || dis[px][x] > k || dis[x][y] > k || dis[y][py] > k)return -inf;
return val[x] + val[px] + val[y] + val[py];
}
ll get(int x, int y){
ll ans = getval(x, mx[x], y, mx[y]);
ans = max(ans, getval(x, mx[x], y, cmx[y]));
ans = max(ans, getval(x, mx[x], y, ccmx[y]));
ans = max(ans, getval(x, cmx[x], y, mx[y]));
ans = max(ans, getval(x, cmx[x], y, cmx[y]));
ans = max(ans, getval(x, cmx[x], y, ccmx[y]));
ans = max(ans, getval(x, ccmx[x], y, mx[y]));
ans = max(ans, getval(x, ccmx[x], y, cmx[y]));
ans = max(ans, getval(x, ccmx[x], y, ccmx[y]));
return ans;
}
int main(){
// freopen("holiday.in","r",stdin);
// freopen("holiday.out","w",stdout);
n = read(), m = read(), k = read();
for(int i = 2; i <= n; ++i)val[i] = read();
for(int i = 1; i <= m; ++i){
int x = read(), y = read();
add(x, y); add(y, x);
}
for(int i = 1; i <= n; ++i)
for(int j = 1; j <= n; ++j)
dis[i][j] = 0x3f3f3f3f;
for(int i = 1; i <= n; ++i){dis[i][i] = -1; get_dis(i);}
for(int i = 2; i <= n; ++i)if(dis[1][i] <= k){
for(int j = 2; j <= n; ++j)if(j != i && dis[i][j] <= k){
if(val[i] > val[mx[j]]){
ccmx[j] = cmx[j];
cmx[j] = mx[j];
mx[j] = i;
}else if(val[i] > val[cmx[j]]){
ccmx[j] = cmx[j];
cmx[j] = i;
}else if(val[i] > val[ccmx[j]])ccmx[j] = i;
}
}
ll ans = 0;
for(int i = 2; i <= n; ++i)
for(int j = i + 1; j <= n; ++j)
if(i != j && dis[i][j] <= k)
ans = max(ans, get(i, j));
printf("%lld\n",ans);
return 0;
}
策略游戏
这个策略其实比较容易处理，后手决定了对于确定的 \(a_i\)， 会对应令答案最小的 \(b_j\)， 先手决定了在若干个 \(a_i\) 中会选择最后最大的
通过分类讨论发现可能对答案产生贡献的无非四种情况，
最大值， 最小值，最小正值， 最小负值
\(0\) 可以看做正也可以看做负
于是线段树维护一下，按照策略取值即可
code
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
int read(){
int x = 0; char c = getchar(); bool f = 0;
while(!isdigit(c)){f = c == '-'; c = getchar();}
do{x = x * 10 + (c ^ 48); c = getchar();}while(isdigit(c));
return f ? -x : x;
}
const int maxn = 100005;
const int inf = 2147483647;
int n, m, q;
struct node{
int mx, mi, mz, mf;
friend node operator + (const node &x, const node &y){
node ans;
ans.mi = min(x.mi, y.mi);
ans.mx = max(x.mx, y.mx);
ans.mz = min(x.mz, y.mz);
ans.mf = max(x.mf, y.mf);
return ans;
}
};
struct seg{
int a[maxn];
node t[maxn << 2 | 1];
void built(int x, int l, int r){
if(l == r){
t[x].mi = t[x].mx = a[l];
t[x].mf = -inf; t[x].mz = inf;
if(a[l] <= 0)t[x].mf = a[l];
if(a[l] >= 0)t[x].mz = a[l];
return;
}
int mid = (l + r) >> 1;
built(x << 1, l, mid);
built(x << 1 | 1, mid + 1, r);
t[x] = t[x << 1] + t[x << 1 | 1];
}
node query(int x, int l, int r, int L, int R){
if(L <= l && r <= R)return t[x];
int mid = (l + r) >> 1;
if(R <= mid)return query(x << 1, l, mid, L, R);
if(L > mid)return query(x << 1 | 1, mid + 1, r, L, R);
return query(x << 1, l, mid, L, R) + query(x << 1 | 1, mid + 1, r, L, R);
}
}ta, tb;
ll cmi(const ll &x, const node &y){
ll ans = min(y.mi * x, y.mx * x);
if(y.mz != inf)ans = min(ans, y.mz * x);
if(y.mf != -inf)ans = min(ans, y.mf * x);
return ans;
}
int main(){
freopen("game.in","r",stdin);
freopen("game.out","w",stdout);
n = read(), m = read(), q = read();
for(int i = 1; i <= n; ++i)ta.a[i] = read();
for(int i = 1; i <= m; ++i)tb.a[i] = read();
ta.built(1, 1, n);
tb.built(1, 1, m);
for(int i = 1; i <= q; ++i){
int l1 = read(), r1 = read(), l2 = read(), r2 = read();
node qa = ta.query(1, 1, n, l1, r1);
node qb = tb.query(1, 1, m, l2, r2);
ll ans = max(cmi(qa.mi, qb), cmi(qa.mx, qb));
if(qa.mz != inf)ans = max(ans, cmi(qa.mz, qb));
if(qa.mf != -inf)ans = max(ans, cmi(qa.mf, qb));
printf("%lld\n",ans);
}
return 0;
}
星战
题面比较复杂，但是转化后题意很清晰
能够发现一旦满足所有点有且仅有一条出边，那么这是一个可以反击的时刻
因为一直走出边永远停不下来，那么必然有环
因为操作在被指向点进行，考虑在那里维护
考场做法是维护了两个 \(multiset\)， 分别为对应边的起点
修改时维护当前出度为 \(1\) 的点的数量
这样就有了 \(60pts\) （应该）
目前已知的正解比较奇妙
考虑上面的做法因为 \(2 , 4\) 操作的存在会被卡成 \(nqlog\)
如何快速维护是个问题，如果转化为对某个数值的操作，那么就好办了
于是给每个点一个随机权值，在每条边的入点处加上出点的权值，记录所有点出度为 \(1\) 时的数，然后就可以快速维护了
关于冲突的概率我并不会分析，只能说解法奇妙
code
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
int read(){
int x = 0; char c = getchar();
while(!isdigit(c)){c = getchar();}
do{x = x * 10 + (c ^ 48); c = getchar();}while(isdigit(c));
return x;
}
mt19937 rd((ull)(new char) * (ull)(new char));
ll sr(){return uniform_int_distribution<ll>(1, 1e12)(rd);}
const int maxn = 500005;
int n, m;
ll val[maxn], sum[maxn], now[maxn], fl, ans;
int main(){
// freopen("galaxy.in","r",stdin);
// freopen("galaxy.out","w",stdout);
n = read(), m = read();
for(int i = 1; i <= n; ++i)val[i] = sr();
for(int i = 1; i <= m; ++i){
int u = read(), v = read();
sum[v] += val[u];
}
for(int i = 1; i <= n; ++i){
now[i] = sum[i];
ans += now[i];
fl += val[i];
}
int q = read();
for(int i = 1; i <= q; ++i){
int op = read();
if(op == 1 || op == 3){
int u = read(), v = read();
if(op == 1)now[v] -= val[u], ans -= val[u];
else now[v] += val[u], ans += val[u];
}else{
int u = read();
if(op == 2)ans -= now[u], now[u] = 0;
else ans -= now[u], now[u] = sum[u], ans += sum[u];
}
if(ans == fl)printf("YES\n");
else printf("NO\n");
}
return 0;
}
数据传输
有点 \(DDP\) 的思想在里面，如果你学过 \(DDP\),并且没有想我一样脑抽的话大概能搞不少分
首先考验一般的 \(DP\)
code
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
int read(){
int x = 0; char c = getchar();
while(!isdigit(c)){c = getchar();}
do{x = x * 10 + (c ^ 48); c = getchar();}while(isdigit(c));
return x;
}
const int maxn = 200005;
const ll inf = 0x3f3f3f3f3f3f3f3f;
struct matrix{
ll a[3][3];
matrix(){memset(a, 0x3f, sizeof(a));}
friend matrix operator * (const matrix &x, const matrix &y){
matrix ans;
for(int i = 0; i < 3; ++i)
for(int k = 0; k < 3; ++k)
for(int j = 0; j < 3; ++j)
ans.a[i][j] = min(ans.a[i][j], x.a[i][k] + y.a[k][j]);
return ans;
}
}f[maxn];
int head[maxn], tot;
struct edge{int to, net;}e[maxn << 1 | 1];
void add(int u, int v){
e[++tot].net = head[u];
head[u] = tot;
e[tot].to = v;
}
int n, q, k;
int v0[maxn], v1[maxn];
int fa[maxn], dep[maxn], size[maxn], son[maxn], top[maxn];
void dfs1(int x){
size[x] = 1;
for(int i = head[x]; i; i = e[i].net){
int v = e[i].to;
if(v == fa[x])continue;
dep[v] = dep[x] + 1; fa[v] = x;
dfs1(v);
size[x] += size[v];
son[x] = size[son[x]] > size[v] ? son[x] : v;
}
}
int tim, dfn[maxn], id[maxn];
void dfs2(int x, int tp){
dfn[x] = ++tim; id[tim] = x; top[x] = tp;
if(son[x])dfs2(son[x], tp);
for(int i = head[x]; i; i = e[i].net){
int v = e[i].to;
if(v == fa[x] || v == son[x])continue;
dfs2(v, v);
}
}
int LCA(int u, int v){
while(top[u] != top[v]){
if(dep[top[u]] < dep[top[v]])swap(u, v);
u = fa[top[u]];
}
return dep[u] < dep[v] ? u : v;
}
struct seg{
matrix t1[maxn << 2 | 1], t2[maxn << 2 | 1];
void built(int x, int l, int r){
if(l == r){
t1[x] = t2[x] = f[id[l]];
return;
}
int mid = (l + r) >> 1;
built(x << 1, l, mid);
built(x << 1 | 1, mid + 1, r);
t1[x] = t1[x << 1] * t1[x << 1 | 1];
t2[x] = t2[x << 1 | 1] * t2[x << 1];
}
matrix query1(int x, int l, int r, int L, int R){
if(L <= l && r <= R)return t1[x];
int mid = (l + r) >> 1;
if(R <= mid)return query1(x << 1, l, mid, L, R);
if(L > mid)return query1(x << 1 | 1, mid + 1, r, L, R);
return query1(x << 1, l, mid, L, R) * query1(x << 1 | 1, mid + 1, r, L, R);
}
matrix query2(int x, int l, int r, int L, int R){
if(L <= l && r <= R)return t2[x];
int mid = (l + r) >> 1;
if(R <= mid)return query2(x << 1, l, mid, L, R);
if(L > mid)return query2(x << 1 | 1, mid + 1, r, L, R);
return query2(x << 1 | 1, mid + 1, r, L, R) * query2(x << 1, l, mid, L, R);
}
}t;
void solve(){
int u = read(), v = read();
matrix a, b;
int lca = LCA(u, v);
a.a[0][0] = v0[u]; u = fa[u];
while(dep[top[u]] >= dep[lca]){
a = a * t.query2(1, 1, n, dfn[top[u]], dfn[u]);
u = fa[top[u]];
}
if(dep[u] >= dep[lca])a = a * t.query2(1, 1, n, dfn[lca], dfn[u]);
for(int i = 0; i < 3; ++i)b.a[i][i] = 0;
while(dep[top[v]] > dep[lca]){
b = t.query1(1, 1, n, dfn[top[v]], dfn[v]) * b;
v = fa[top[v]];
}
if(dep[v] > dep[lca])b = t.query1(1, 1, n, dfn[lca] + 1, dfn[v]) * b;
a = a * b;
printf("%lld\n", a.a[0][0]);
}
int main(){
// freopen("transmit.in","r",stdin);
// freopen("transmit.out","w",stdout);
n = read(), q = read(), k = read();
for(int i = 1; i <= n; ++i)v0[i] = read();
for(int i = 1; i < n; ++i){
int u = read(), v = read();
add(u, v); add(v, u);
}
for(int i = 1; i <= n; ++i)v1[i] = 0x3f3f3f3f;
for(int i = 1; i <= n; ++i){
for(int j = head[i]; j; j = e[j].net){
int v = e[j].to;
v1[i] = min(v1[i], v0[v]);
}
if(k == 1){
f[i].a[0][0] = v0[i];
}else if(k == 2){
f[i].a[0][0] = f[i].a[1][0] = v0[i];
f[i].a[0][1] = 0;
}else if(k == 3){
f[i].a[0][0] = f[i].a[1][0] = f[i].a[2][0] = v0[i];
f[i].a[0][1] = f[i].a[1][2] = 0;
f[i].a[1][1] = v1[i];
}
}
dep[1] = 1;
dfs1(1); dfs2(1, 1); t.built(1, 1, n);
for(int i = 1; i <= q; ++i)solve();
return 0;
}