勉强混到 CQ 一等但是差 \(5\) 分 \(7\) 级勾（哭）。
A. 假期计划
我们先不考虑 \(4\) 个点，考虑 \(2\) 个点的情况。
我们发现可以枚举 \(a\) 点，再找到 \(a\) 能到达且 \(1\) 能到达的最大权值的点 \(b\)。
回到该题，运用刚才的思想，我们便可以通过枚举 \(b,c\) 点，按上述操作得到 \(a,d\) 点。即在处理 BFS 时提前处理好该点能到且 \(1\) 点能到的权值前 \(3\) 大的点。（为什么要取 \(3\) 个，为了防止枚举 \(b\) 时 \(a,c,d\) 重复）。
#include<bits/stdc++.h>
using namespace std;
const int N=2510;
vector<int> l[N];
void add(int u,int v){
l[u].push_back(v);
return ;
}
long long w[N];
vector<long long> sum[N];
bool go[N][N];
int dis[N];
int k,n;
void bfs(int s){
for(int i=1;i<=n;i++){
dis[i]=INT_MAX;
}
dis[s]=0;
queue<int> q;
q.push(s);
while(!q.empty()){
int u=q.front();
q.pop();
if(dis[u]>k){
continue;
}
if(u!=s){
go[s][u]=1;
if(u>1&&go[1][u]){
sum[s].push_back(u);
sort(sum[s].begin(),sum[s].end(),[](int x,int y){
return w[x]>w[y];
});
if(sum[s].size()==4){
sum[s].pop_back();
}//处理出最大的3个
}
}
for(auto v:l[u]){
if(dis[u]+1<dis[v]){
dis[v]=dis[u]+1;
q.push(v);
}
}
}
return ;
}
int main(){
int m;
scanf("%d%d%d",&n,&m,&k);
k++;
for(int i=2;i<=n;i++){
scanf("%lld",&w[i]);
}
for(int i=1;i<=m;i++){
int x,y;
scanf("%d%d",&x,&y);
add(x,y);
add(y,x);
}
for(int i=1;i<=n;i++){
bfs(i);
}
long long ans=0;
for(int b=2;b<=n;b++){
for(int c=2;c<=n;c++){//枚举b,c
if(go[b][c]){
for(auto a:sum[b]){
if(a==c){
continue;
}
for(auto d:sum[c]){
if(d==b||d==a){
continue;
}
ans=max(ans,w[a]+w[b]+w[c]+w[d]);
}
}
}
}
}
printf("%lld",ans);
return 0;
}
B. 策略游戏
可以发现，答案即为对于 \(i=l1\sim r1\) 行中 \(\min\{c_{i,j}\}(j=l2\sim r2)\) 最大的一行的最小值。
我们发现有多种情况：
- 若 \(a_i\ge0\)，则另一方会选 \(\min\{b_j\}\)。当然，若 \(\min\{b_j\}\ge0\)，会选 \(\max\{a_i\}\)；若 \(\min\{b_j\}<0\)，会选 \(\min\{a_i\}(a_i\ge0)\)。
- 若 \(a_i<0\)，则另一方会选 \(\max\{b_j\}\)。同理，若 \(\max\{b_j\}< 0\)，会选 \(\min\{a_i\}\)；若 \(\max\{b_j\}\ge0\)，则会选 \(\max\{a_i\}(a_i<0)\)。
ST 表维护上述提到的 6 种即可。
#include<bits/stdc++.h>
using namespace std;
const int M=100010,N=100010,T=17;
long long a[N],b[M];
long long amax[N][T],amin[N][T],bmax[M][T],bmin[M][T],afmax[M][T],azmin[M][T];
int lo2[N];
int main(){
int n,m,q;
scanf("%d%d%d",&n,&m,&q);
for(int i=2;i<=max(n,m);i++){
lo2[i]=lo2[i>>1]+1;
}
for(int i=1;i<=n;i++){
scanf("%lld",&a[i]);
}
for(int i=1;i<=m;i++){
scanf("%lld",&b[i]);
}
for(int i=1;i<=n;i++){
amax[i][0]=a[i];
amin[i][0]=a[i];
if(a[i]){
afmax[i][0]=(a[i]<0?a[i]:INT_MIN);
azmin[i][0]=(a[i]>=0?a[i]:INT_MAX);
}
else{
afmax[i][0]=azmin[i][0]=0;
}
}
for(int len=1;(1<<len)<=n;len++){
for(int j=(1<<len);j<=n;j++){
amax[j][len]=max(amax[j][len-1],amax[j-(1<<(len-1))][len-1]);
amin[j][len]=min(amin[j][len-1],amin[j-(1<<(len-1))][len-1]);
afmax[j][len]=max(afmax[j][len-1],afmax[j-(1<<(len-1))][len-1]);
azmin[j][len]=min(azmin[j][len-1],azmin[j-(1<<(len-1))][len-1]);
}
}
for(int i=1;i<=m;i++){
bmax[i][0]=b[i];
bmin[i][0]=b[i];
}
for(int len=1;(1<<len)<=m;len++){
for(int j=(1<<len);j<=m;j++){
bmax[j][len]=max(bmax[j][len-1],bmax[j-(1<<(len-1))][len-1]);
bmin[j][len]=min(bmin[j][len-1],bmin[j-(1<<(len-1))][len-1]);
}
}
while(q--){
int l1,r1,l2,r2;
scanf("%d%d%d%d",&l1,&r1,&l2,&r2);
int Alen=lo2[r1-l1+1],Blen=lo2[r2-l2+1];
long long Amax=max(amax[r1][Alen],amax[l1+(1<<Alen)-1][Alen]);
long long AFmax=max(afmax[r1][Alen],afmax[l1+(1<<Alen)-1][Alen]);
long long Bmax=max(bmax[r2][Blen],bmax[l2+(1<<Blen)-1][Blen]);
long long Amin=min(amin[r1][Alen],amin[l1+(1<<Alen)-1][Alen]);
long long AZmin=min(azmin[r1][Alen],azmin[l1+(1<<Alen)-1][Alen]);
long long Bmin=min(bmin[r2][Blen],bmin[l2+(1<<Blen)-1][Blen]);
long long ans=0;
if(l1==r1){
ans=min(Amax*Bmax,Amax*Bmin);
}
else if(l2==r2){
ans=max(Amin*Bmax,Amax*Bmax);
}
else{
if(Bmin>=0){
if(Amax<0){
ans=Amax*Bmax;
}
else{
ans=Amax*Bmin;
}
}
else if(Bmax<=0){
if(Amin<0){
ans=Amin*Bmax;
}
else{
ans=Amin*Bmin;
}
}
else{
ans=max(AZmin*Bmin,AFmax*Bmax);
}
}
printf("%lld\n",ans);
}
return 0;
}
C. 星战
“不可以，总司令。”
个人认为本次 S 最简单的题。
手模一下发现只要满足 2 性质，即每个点有且仅有一条出边即能“反攻”。
于是我们可以把 \(u\to v\) 的边转化为 \(v\to u\)（之后出现的 \(u\to v\) 默认以转换），给每个点定义一个哈希值 \(hsh_i\)。
我们令 \(all_v=\sum\limits_{u\to v} hsh_u\)，即一开始没有边被摧毁时点应有的哈希值。
令 \(now_v\) 为实时变换的该点的哈希值，初值即为 \(all_v\)。
若删除（增加）一条边，则为 \(now_v-(+)hsh_u\)。
若摧毁（修复）一条边，则为 \(now_v = 0(all_v)\)。
判断 \(\sum\limits_{i=1}^n now_i\) 是否等于 \(\sum\limits_{i=1}^n hsh_i\) 即可。可以用变量记录实时更新。
#include<bits/stdc++.h>
using namespace std;
const int N=500100;
const unsigned long long p=1000003;//要超过N的范围
unsigned long long sum,ac,all[N],now[N],s[N];//自然溢出
int main(){
int n,m;
scanf("%d%d",&n,&m);
s[1]=1;
ac=1;
for(int i=2;i<=n;i++){
s[i]=s[i-1]*p;
ac+=s[i];
}
while(m--){
int u,v;
scanf("%d%d",&u,&v);
sum+=s[u];
all[v]+=s[u];
now[v]+=s[u];
}
int q;
scanf("%d",&q);
while(q--){
int opt;
scanf("%d",&opt);
if(opt==1){
int u,v;
scanf("%d%d",&u,&v);
now[v]-=s[u];
sum-=s[u];
}
else if(opt==2){
int v;
scanf("%d",&v);
sum-=now[v];
now[v]=0;
}
else if(opt==3){
int u,v;
scanf("%d%d",&u,&v);
now[v]+=s[u];
sum+=s[u];
}
else{
int v;
scanf("%d",&v);
sum+=(all[v]-now[v]);
now[v]=all[v];
}
if(sum==ac){
printf("YES");
}
else{
printf("NO");
}
printf("\n");
}
return 0;
}
D. 数据传输
首先可以把询问的条件转化为中间连续不经过的点不超过 \(k\) 个。
则令 \((u,x)\) 双元组为在 \(u\) 点，已有 \(x\) 个连续点没经过。
但这样暴力跑时间复杂度为 \(O(qn\log_2n)\)，很不理想。
我们便考虑利用倍增求 LCA 一步步往上维护信息。
令 \(dp_{u,i,x,y}\) 为 \((u,x)\) 到 \((fa_u^{2^i},y)\) 的最短距离。
那我们便可以像倍增 LCA 一样预处理 \(dp_{u,0,x,y}\)，之后便利用 \(dp_{u,i-1,x,z},dp_{fa_u^{2^{i-1}},i-1,z,y}\) 转移即可。发现有 \(3\) 种情况：
- 走到 \(fa_u^1\)。
- \(u,fa_u^1\) 都不走。
- 走到与 \(u\) 有连边且权值最小的点再走到 \(fa_u^1\)。
答案便可以在向上求 LCA 时转移。但要注意若 \(x=y=0\) 时多算了一次 LCA 的权值。若 \(x+y>k\) 则说明还到不了 LCA，还需要找一个与 LCA 有连边的权值最小的点做转移。
#include <bits/stdc++.h>
using namespace std;
void Min (long long & u, long long v) {
u = min (u, v);
return ;
}
const int N = 200100;
vector <int> l [N];
long long v [N], near [N];
void add (int x, int y){
l [x] .push_back (y);
Min (near [x], v [y]);
return ;
}
const int M = 18, K = 3;
int depth [N], fa [N] [M];
long long dis [N] [M] [K] [K];
int s;
void Dfs (int u, int fat) {
depth [u] = depth [fat] + 1;
fa [u] [0] = fat;
auto t = dis [u] [0];
if (s == 1) {
t [0] [0] = v [fat];
}
else if (s == 2) {
t [0] [0] = t [1] [0] = v [fat];
t [0] [1] = 0;
}
else {
t [0] [0] = t [1] [0] = t [2] [0] = v [fat];
t [0] [1] = t [1] [2] = 0;
t [2] [2] = near [u];
}//初始化
for (int i = 1; i < M; i ++) {
fa [u] [i] = fa [fa [u] [i - 1]] [i - 1];
for (int j = 0; j < K; j ++) {
for (int k = 0; k < K; k ++) {
for (int h = 0; h < K; h ++) {
Min (dis [u] [i] [j] [h], dis [u] [i - 1] [j] [k] + dis [fa [u] [i - 1]] [i - 1] [k] [h]);
}
}
}//找中间值转移
}
for (auto to : l [u]) {
if (to == fat) {
continue;
}
Dfs (to, u);
}
return ;
}
int LCA (int x, int y) {
if (depth [x] < depth [y]) {
swap (x, y);
}
for (int i = M - 1; i >= 0; i --) {
if (depth [fa [x] [i]] >= depth [y]) {
x = fa [x] [i];
}
}
if (x == y) {
return x;
}
for (int i = M - 1; i >= 0; i --) {
if (fa [x] [i] != fa [y] [i]) {
x = fa [x] [i];
y = fa [y] [i];
}
}
return fa [x] [0];
}//模板
long long X [K], Y [K];
void Update (int u, int fat, long long *U) {
U [0] = U [1] = U [2] = v [u];
for (int i = M - 1; i >= 0; i --) {
if (depth [fa [u] [i]] >= depth [fat]) {
long long P [3] = {U [0], U [1], U [2]};
U [0] = U [1] = U [2] = 1e18;
for (int j = 0; j < K; j ++) {
for (int k = 0; k < K; k ++) {
Min (U [k], P [j] + dis [u] [i] [j] [k]);
}
}//找中间值转移
u = fa [u] [i];
}
}
return ;
}
long long Ans (int x, int y) {//为了方便调试拆开了求LCA和转移
int lca = LCA (x, y);
Update (x, lca, X);
Update (y, lca, Y);
long long ans = 1e18;
for (int i = 0; i < s; i ++) {
for (int j = 0; j < s; j ++) {
long long w = 0;
if (i + j == 0) {//多算了一次
w = - v [lca];
}
if (i + j > s) {//要再找一个
w = near [lca];
}
Min (ans, X [i] + Y [j] + w);
}
}
return ans;
}
signed main () {
ios :: sync_with_stdio (false);
cin .tie (nullptr);
cout .tie (nullptr);
int n, q;
cin >> n >> q >> s;
for (int i = 1; i <= n; i ++) {
cin >> v [i];
near [i] = v [i];
}
for (int i = 1; i < n; i ++) {
int x, y;
cin >> x >> y;
add (x, y);
add (y, x);
}
memset (dis, 1, sizeof (dis));//注意其余的要设为INF
Dfs (1, 0);
while (q --) {
int x, y;
cin >> x >> y;
cout << Ans (x, y) << '\n';
}
return 0;
}