CSP 取消了，只能 vp 一下。
T1
先枚举每个点，bfs 出中转次数不超过 \(k\) 次的点，并标记 \(f[i][j]=f[j][i]=1\)。
发现 \(1\) 与 \(A,B,C,D\) 构成的环可以拆成 \(1,A,B\) 与 \(1,D,C\)，这里想了好一会枚举 \(A,D\) 怎么做，结果发现自己弱智了。已经确定 \(1\)，在 \(n=2500\) 的背景下选择了枚举 \(B\) 和 \(C\) ，然后预处理 \(A,D\)。
考虑到可能会重复，例如通过 \(B\) 选出的 \(A\) 可能与 \(C,D\) 相同，所以我们最多只需要记录前三大即可。
预处理出对于 \(i\) 满足满足 \(f[i][j]=1,f[j][1]=1\) 的分数前三大的点 \(j\)，记为 \(\max_1[i],\max_2[i],\max_3[i]\)。
我们钦定 \(B<C\)，枚举 \(B,C\)，判断然后取最大值即可。
复杂度 \(O(n^2)\)，常数 \(\frac{9}{2}\)。
#include<bits/stdc++.h>
using namespace std;
#define int long long
inline int read(){
int x=0,f=1;
char c=getchar();
while(c<'0'||c>'9'){
if(c=='-')f=-1;
c=getchar();
}
while(c<='9'&&c>='0'){
x=(x<<1)+(x<<3)+(c^48);
c=getchar();
}
return x*f;
}
void print(int x){
if(x<0)putchar('-'),x=-x;
if(x>9)print(x/10);
putchar(x%10^48);
}
const int N=2505,M=1e4+5,K=105;
int n,m,k,a[N],head[N],cnt;
struct node{
int next,to;
}e[M<<1];
void add(int from,int to){
e[++cnt]=(node){head[from],to};
head[from]=cnt;
}
bool vis[N],f[N][N];
queue<int>q;
int dis[N];
void bfs(int x){
while(!q.empty())q.pop();
for(int i=1;i<=n;++i)vis[i]=0,dis[i]=1e18;
q.push(x),dis[x]=-1;
while(!q.empty()){
int u=q.front();
q.pop();
if(vis[u])continue;
vis[u]=1;
if(dis[u]>=k)break;
for(int i=head[u];i;i=e[i].next){
int v=e[i].to;
f[x][v]=f[v][x]=1;
dis[v]=min(dis[v],dis[u]+1);
if(!vis[v])q.push(v);
}
}
}
int maxn[4][N];
signed main(){
n=read(),m=read(),k=read();
for(int i=2;i<=n;++i)a[i]=read();
for(int i=1;i<=m;++i){
int u=read(),v=read();
add(u,v),add(v,u);
}
for(int i=1;i<=n;++i){
bfs(i);
}
for(int i=2;i<=n;++i){
for(int j=2;j<=n;++j){
if(i==j)continue;
if(f[i][j]&&f[j][1]){
if(a[j]>a[maxn[1][i]]){
maxn[3][i]=maxn[2][i];
maxn[2][i]=maxn[1][i];
maxn[1][i]=j;
}else if(a[j]>a[maxn[2][i]]){
maxn[3][i]=maxn[2][i];
maxn[2][i]=j;
}else if(a[j]>a[maxn[3][i]]){
maxn[3][i]=j;
}
}
}
}
int ans=0;
for(int i=2;i<=n;++i){
for(int j=i+1;j<=n;++j){
if(!f[i][j])continue;
for(int k1=1;k1<=3;++k1){
if(maxn[k1][i]==j)continue;
for(int k2=1;k2<=3;++k2){
if(maxn[k1][i]!=maxn[k2][j]&&maxn[k2][j]!=i&&f[maxn[k1][i]][1]&&f[maxn[k2][j]][1]){
ans=max(ans,a[i]+a[j]+a[maxn[k1][i]]+a[maxn[k2][j]]);
}
}
}
}
}
print(ans);
return 0;
}
T2
考虑最优策略是什么，可以从暴力中发掘：
枚举小 L 选的每一个值，小 Q 选择乘积最小的值，而小 L 从这些值里面选取最大的。
根据暴力理解完题目之后，不能把目光只停留在列举每一个数中，要考虑数的形成过程，即两区间内选数相乘。
也就是说：对于小 L 的每种情况，小 Q 都有相应的对策，这个对策在形式上是固定的，而小 L 根据每一种情况反馈出的值选择对于他来说最优的。
先考虑 \(A_i,B_i>0\) 的情况，对于小 L 选的每一个正数 \(A_i\)，小 Q 形式上固定的对策是选择区间内最小的 \(B_i\) 与之相乘保证最小，对此，小 L 将会选区间内最大的 \(A_i\) 使乘积最大。
再考虑正负零的情况，稍微列举归纳可发现，我们将数分为非负数和负数：
对于小 L 选这两种情况，小 Q 也有固定的策略：
- 小 L 选非负数，小 Q 有负数选负数，没有负数选最小的非负数，总结一下可以得到小 Q 的策略是：选最小的。
- 小 L 选负数，小 Q 有非负数选最大的非负数，没有非负数选最大的负数，总结一下可以得到小 Q 的策略是：选最大的。
所以我们只需要预处理 \(6\) 组值：
- \(A\) 序列非负数 \(\max_1,\min_1\)
- \(A\) 序列负数 \(\max_2,\min_2\)
- \(B\) 序列 \(\max_3,\min_3\)
用 ST 表实现即可，复杂度 \(O(n\log n)\)。
#include<bits/stdc++.h>
using namespace std;
#define int long long
inline int read(){
int x=0,f=1;
char c=getchar();
while(c<'0'||c>'9'){
if(c=='-')f=-1;
c=getchar();
}
while(c<='9'&&c>='0'){
x=(x<<1)+(x<<3)+(c^48);
c=getchar();
}
return x*f;
}
void print(int x){
if(x<0)putchar('-'),x=-x;
if(x>9)print(x/10);
putchar(x%10^48);
}
const int N=1e5+5;
int n,m,q,a[N],b[N],num[N],lgn,lgm;
int maxn1[N][21],minn1[N][21];
int maxn2[N][21],minn2[N][21];
int maxn3[N][21],minn3[N][21];
void init_maxn1(){
for(int i=1;i<=n;++i)maxn1[i][0]=a[i];
for(int j=1;j<=lgn;++j){
for(int i=1;i+(1<<j)-1<=n;++i){
maxn1[i][j]=max(maxn1[i][j-1],maxn1[i+(1ll<<(j-1))][j-1]);
}
}
}
void init_minn1(){
for(int i=1;i<=n;++i){
if(a[i]>=0)minn1[i][0]=a[i];
else minn1[i][0]=1e18;
}
for(int j=1;j<=lgn;++j){
for(int i=1;i+(1<<j)-1<=n;++i){
minn1[i][j]=min(minn1[i][j-1],minn1[i+(1ll<<(j-1))][j-1]);
}
}
}
void init_maxn2(){
for(int i=1;i<=n;++i){
if(a[i]<0)maxn2[i][0]=a[i];
else maxn2[i][0]=-1e18;
}
for(int j=1;j<=lgn;++j){
for(int i=1;i+(1<<j)-1<=n;++i){
maxn2[i][j]=max(maxn2[i][j-1],maxn2[i+(1ll<<(j-1))][j-1]);
}
}
}
void init_minn2(){
for(int i=1;i<=n;++i)minn2[i][0]=a[i];
for(int j=1;j<=lgn;++j){
for(int i=1;i+(1<<j)-1<=n;++i){
minn2[i][j]=min(minn2[i][j-1],minn2[i+(1ll<<(j-1))][j-1]);
}
}
}
void init_maxn3(){
for(int i=1;i<=m;++i)maxn3[i][0]=b[i];
for(int j=1;j<=lgm;++j){
for(int i=1;i+(1<<j)-1<=m;++i){
maxn3[i][j]=max(maxn3[i][j-1],maxn3[i+(1ll<<(j-1))][j-1]);
}
}
}
void init_minn3(){
for(int i=1;i<=m;++i)minn3[i][0]=b[i];
for(int j=1;j<=lgm;++j){
for(int i=1;i+(1<<j)-1<=m;++i){
minn3[i][j]=min(minn3[i][j-1],minn3[i+(1ll<<(j-1))][j-1]);
}
}
}
signed main(){
n=read(),m=read(),q=read();
lgn=(int)log2(n),lgm=(int)log2(m);
for(int i=1;i<=n;++i)a[i]=read();
for(int i=1;i<=m;++i)b[i]=read();
for(int i=1;i<=n;++i){
if(a[i]>=0)num[i]=num[i-1]+1;
else num[i]=num[i-1];
}
init_maxn1(),init_minn1();
init_maxn2(),init_minn2();
init_maxn3(),init_minn3();
int l1,r1,l2,r2,ans,lga,lgb,tmpa,tmpb;
while(q--){
l1=read(),r1=read(),l2=read(),r2=read();
ans=-1e18;
lga=(int)log2(r1-l1+1);
lgb=(int)log2(r2-l2+1);
if(num[r1]-num[l1-1]>0){
tmpb=min(minn3[l2][lgb],minn3[r2-(1<<lgb)+1][lgb]);
if(tmpb>=0){
tmpa=max(maxn1[l1][lga],maxn1[r1-(1<<lga)+1][lga]);
ans=max(ans,tmpa*tmpb);
}else{
tmpa=min(minn1[l1][lga],minn1[r1-(1<<lga)+1][lga]);
ans=max(ans,tmpa*tmpb);
}
}
if(num[r1]-num[l1-1]<r1-l1+1){
tmpb=max(maxn3[l2][lgb],maxn3[r2-(1<<lgb)+1][lgb]);
if(tmpb>=0){
tmpa=max(maxn2[l1][lga],maxn2[r1-(1<<lga)+1][lga]);
ans=max(ans,tmpa*tmpb);
}else{
tmpa=min(minn2[l1][lga],minn2[r1-(1<<lga)+1][lga]);
ans=max(ans,tmpa*tmpb);
}
}
print(ans),puts("");
}
return 0;
}
T3
题目比较难读，用了快半个小时才读懂题……
人话翻译：
\(n\) 个点，\(m\) 条边，要求支持：
- 删边 \((u,v)\)
- 删去所有以 \(u\) 为终点的点
- 加边 \((u,v)\)
- 加上所有以 \(u\) 为终点的点
在每一次操作之后判断：
- 是否每个点的出度为 \(1\)
- 是否每个点都能走到一个环
很显然第一个判断是包括了第二个的，所以我们只用判断：是否每个点的出度为 \(1\)。
赛时：\(O(mq)\) 模拟做法显然好做，然后没有 \(t=2\) 和 \(t=4\) 的情况只需要我们支持每次加删一条边和判断，用一个 multiset 维护出度判断首尾是否相同即可。对于有 \(t=2\) 的，我们用一个集合维护未被摧毁的边，由于每次加边只能加一条，复杂度是有保证的。这是 \(60\)，然后还写了一个用集合维护删边的，复杂度没有保证想骗点分，结果好像没骗到。码了整整两百行。
正解是 hash，看到判断每个点的出度全为 \(1\)，我们考虑给每个点随机赋一个权值 \(val_i\)，设出来一个与出度有关的 \(h(u)\)，用 \(\sum h(u)\) 来判断。
然后考虑如何应对上述操作。发现以 \(u\) 为终点很逆天，于是我们建反图把它干掉。
将图转化为反图，需要支持的操作变为：
- 删边 \((u,v)\)
- 删去所有以 \(u\) 为起点的点
- 加边 \((u,v)\)
- 加上所有以 \(u\) 为起点的点
此时我们需要判断：
- 每个点的入度为 \(1\)
对于删去所有和恢复所有边，需要我们记录所有点的初始出度和当前出度。
但是判断的是入度，应该怎么办呢？
考虑把当前点的贡献转移到起点，即对于边 \(u\to v\)，我们不记录 \(v\) 的入度，而记录 \(u\) 的出度，把 \(val_v\) 记录到 \(h(u)\) 上，这样既不会改变最终答案，又能解决出入度冲突问题。
所以我们设 \(h(u)\) 为以 \(u\) 为起点的边的终点权值和，这满足对于每个点入度都为 \(1\) 的图他们的 \(\sum h(u)\) 相同，即一个点的权值只会被统计一次。
为了保证正确率，可以多随机几个点的权值。
#include<bits/stdc++.h>
using namespace std;
#define int long long
inline int read(){
int x=0,f=1;
char c=getchar();
while(c<'0'||c>'9'){
if(c=='-')f=-1;
c=getchar();
}
while(c<='9'&&c>='0'){
x=(x<<1)+(x<<3)+(c^48);
c=getchar();
}
return x*f;
}
void print(int x){
if(x<0)putchar('-'),x=-x;
if(x>9)print(x/10);
putchar(x%10^48);
}
const int N=5e5+5;
const int MAX=1e9+7;
int n,m,q;
int d[N],nd[N],val[N][5],ans[5];
int nsum[N][5],nSum[5],sum[N][5];
signed main(){
n=read(),m=read();
srand(time(0));
for(int i=1;i<=n;++i){
for(int j=0;j<5;++j){
val[i][j]=rand()*rand()%MAX;
ans[j]+=val[i][j];
}
}
for(int i=1;i<=m;++i){
int u=read(),v=read();
d[v]++,nd[v]++;
for(int j=0;j<5;++j){
sum[v][j]+=val[u][j];
nsum[v][j]+=val[u][j];
nSum[j]+=val[u][j];
}
}
q=read();
int t,u,v;
while(q--){
t=read();
if(t==1){
u=read(),v=read();
nd[u]--;
for(int i=0;i<5;++i)nsum[v][i]-=val[u][i],nSum[i]-=val[u][i];
}else if(t==2){
u=read();
nd[u]=0;
for(int i=0;i<5;++i)nSum[i]-=nsum[u][i],nsum[u][i]=0;
}else if(t==3){
u=read(),v=read();
nd[u]++;
for(int i=0;i<5;++i)nsum[v][i]+=val[u][i],nSum[i]+=val[u][i];
}else{
u=read();
nd[u]=d[u];
for(int i=0;i<5;++i)nSum[i]+=(sum[u][i]-nsum[u][i]),nsum[u][i]=sum[u][i];
}
bool flag=1;
for(int i=0;i<5;++i)if(ans[i]!=nSum[i])flag=0;
if(flag)puts("YES");
else puts("NO");
}
return 0;
}
T4
开 T4 的时候时间已经不多了，然后就写挂了 \(8\) 分。
看完这题我直接就写了个把 \(s\) 到 \(t\) 之间的链扯下来 dp，然后就挂在了样例 \(2\)。
可以发现当 \(k=3\) 时是能跳出链外的。
于是我在写的 dfs 上加了对于 \(x\) 向外枚举 \(3\) 层转移，然后加上 \(k=1\) 就交了……
赛后发现挂分了，写了个拍可以发现存在这样一种情况：\(x\) 是 \(s\) 到 \(t\) 最优的中转点，而如果只从 \(s\) 开始 dfs 可能先到 \(t\) 再到 \(x\)。
对于这种情况，我们只需要跑 \(n\) 遍 dfs 就写了（
这样就有 \(44\) 分。
正解是倍增维护矩阵，鉴定为是我考场上写不出来的。
先扔这了，有时间再补。
原文地址：http://www.cnblogs.com/Daidly/p/16846087.html
