真就游寄
虽然没能正常参加 CSP，但是还是要做一下。
说实话这成绩七级勾本应该是稳了
T1 假期计划 （\(holiday\)）2s 512M
\(1\to A\to B\to C\to D\to 1\)
观察这个结构，发现两边是对称的。
预处理出对于所有 \(B\), \(1\to A \to B\) 的最大的 \(A\) 的值。
枚举一下 \(B,C\)，直接算贡献。
考虑到点冲突的问题，要记录次大值和次次大值。
int n, m, k;
struct node {
int t, n;
}e[100005];
int u, v;
int head[100005], head_size;
void ADD(int f, int t) {
e[++head_size]=(node){t, head[f]};
head[f]=head_size;
}
int dis[2505][2505];
ll val[2505], ans;
ll maxx[2505][3];
void Change(int i, int j) {
if(val[maxx[i][0]]<val[j]) {
maxx[i][2]=maxx[i][1];
maxx[i][1]=maxx[i][0];
maxx[i][0]=j;
}
else if(val[maxx[i][1]]<val[j]) {
maxx[i][2]=maxx[i][1];
maxx[i][1]=j;
}
else if(val[maxx[i][2]]<val[j]) {
maxx[i][2]=j;
}
}
void BFS(int S) {
dis[S][S]=0;
queue<int>q;
q.push(S);
while(!q.empty()) {
int x=q.front(); q.pop();
for(int i=head[x]; i; i=e[i].n) {
if(dis[S][e[i].t]>100000000) {
dis[S][e[i].t]=dis[S][x]+1;
q.push(e[i].t);
}
}
}
}
ll slove(int x, int y) {
ll re=-1;
ll sum=val[x]+val[y];
for(int i=0; i<=2; ++i) {
if(maxx[x][i]==0) continue ;
if(maxx[x][i]==y) continue ;
for(int j=0; j<=2; ++j) {
if(maxx[y][j]==0) continue ;
if(maxx[y][j]==x) continue ;
if(maxx[y][j]==maxx[x][i]) continue ;
re=max(re, sum+val[maxx[x][i]]+val[maxx[y][j]]);
}
}
return re;
}
int main(){
memset(dis, 0x3f, sizeof(dis));
n=read(); m=read(); k=read();
for(int i=2; i<=n; ++i) val[i]=read();
for(int i=1; i<=m; ++i) {
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(dis[1][j]<=k+1&&dis[j][i]<=k+1) Change(i, j);
}
}
for(int i=2; i<=n; ++i) {
if(!maxx[i][0]) continue ;
for(int j=2; j<=n; ++j) {
if(i==j) continue ;
if(dis[i][j]>k+1) continue ;
if(!maxx[j][0]) continue ;
ans=max(ans, slove(i, j));
}
}
cout<<ans;
}
T2 策略游戏 ( \(game\) ) 1s 512M
\(A\) 选一个数，\(B\) 选择使答案最小的那个。
对于所有 \(A\) 选数之后 \(B\) 选出的最小值取个最大值就行。
其实再多再多也就四种情况。
选正数里最大的或最小的，选负数里最大的或最小的。
那么两个序列，一共 \(4\times 4 = 16\) 种情况，枚举一下就行了。
特别的， \(0\) 作为交界点，即算正数，也算负数。
然后 \(8\) 个 ST 表伺候上就行了。
int n, m, q, a;
int sta[100005][20][4];
int stb[100005][20][4];
int lo[100005];
/*
0正数最大
1正数最小
2负数最大
3负数最小
*/
int main(){
n=read(); m=read(); q=read();
for(int i=1; i<=n; ++i) {
a=read();
sta[i][0][0]=sta[i][0][2]=-2e9;
sta[i][0][1]=sta[i][0][3]=2e9;
if(a>=0) sta[i][0][0]=sta[i][0][1]=a;
if(a<=0) sta[i][0][2]=sta[i][0][3]=a;
}
for(int i=1; i<=m; ++i) {
a=read();
stb[i][0][0]=stb[i][0][2]=-2e9;
stb[i][0][1]=stb[i][0][3]=2e9;
if(a>=0) stb[i][0][0]=stb[i][0][1]=a;
if(a<=0) stb[i][0][2]=stb[i][0][3]=a;
}
for(int i=2; i<=max(n, m); ++i) lo[i]=lo[i>>1]+1;
for(int cs=1; cs<=lo[n]; ++cs) {
for(int i=1; i+(1<<cs)-1<=n; ++i) {
sta[i][cs][0]=max(sta[i][cs-1][0], sta[i+(1<<cs-1)][cs-1][0]);
sta[i][cs][1]=min(sta[i][cs-1][1], sta[i+(1<<cs-1)][cs-1][1]);
sta[i][cs][2]=max(sta[i][cs-1][2], sta[i+(1<<cs-1)][cs-1][2]);
sta[i][cs][3]=min(sta[i][cs-1][3], sta[i+(1<<cs-1)][cs-1][3]);
}
}
for(int cs=1; cs<=lo[m]; ++cs) {
for(int i=1; i+(1<<cs)-1<=m; ++i) {
stb[i][cs][0]=max(stb[i][cs-1][0], stb[i+(1<<cs-1)][cs-1][0]);
stb[i][cs][1]=min(stb[i][cs-1][1], stb[i+(1<<cs-1)][cs-1][1]);
stb[i][cs][2]=max(stb[i][cs-1][2], stb[i+(1<<cs-1)][cs-1][2]);
stb[i][cs][3]=min(stb[i][cs-1][3], stb[i+(1<<cs-1)][cs-1][3]);
}
}
while(q--) {
int A[4], B[4];
int l, r, cs;
l=read(); r=read(); cs=lo[r-l+1];
A[0]=max(sta[l][cs][0], sta[r-(1<<cs)+1][cs][0]); A[1]=min(sta[l][cs][1], sta[r-(1<<cs)+1][cs][1]);
A[2]=max(sta[l][cs][2], sta[r-(1<<cs)+1][cs][2]); A[3]=min(sta[l][cs][3], sta[r-(1<<cs)+1][cs][3]);
l=read(); r=read(); cs=lo[r-l+1];
B[0]=max(stb[l][cs][0], stb[r-(1<<cs)+1][cs][0]); B[1]=min(stb[l][cs][1], stb[r-(1<<cs)+1][cs][1]);
B[2]=max(stb[l][cs][2], stb[r-(1<<cs)+1][cs][2]); B[3]=min(stb[l][cs][3], stb[r-(1<<cs)+1][cs][3]);
ll ans=-1e18, sum;
for(int i=0; i<4; ++i) {
if(abs(A[i])==2e9) continue ;
sum=1e18;
for(int j=0; j<4; ++j) {
if(abs(B[j])==2e9) continue ;
sum=min(sum, 1LL*A[i]*B[j]);
}
ans=max(ans, sum);
}
cout<<ans; putchar('\n');
}
}