T1
用时：\(1\) h
期望得分：\(70\) ~ \(80\)
实际得分：\(55\)
这题考场写了个常数比较小的 \(O(n^3)\) 的做法，期望得分 \(75\) 左右，但是由于 bfs 忘记打标记导致 MLE 和 TLE，挂掉 \(25\) 分。
正解是枚举 B 和 C，并 bfs 对 B C 分别预处理出权值前三大的点，并且满足这个点到 B 或 C 和 到 \(1\) 的距离都是 \(\le k\) 的，直接对于所有的不重点的四元组求一下权值和，然后取 \(\max\) 即可，复杂度 \(O(n^2)\)。
#include<bits/stdc++.h>
#define ll long long
//#define int unsigned long long
#define ull unsigned long long
#define lc(k) k<<1
#define rc(k) k<<1|1
#define lb lower_bound
#define orz cout<<"gzn ak ioi\n"
const int MAX=2510;
const int MOD=1e9+7;
using namespace std;
inline char readchar() {
static char buf[100000], *p1 = buf, *p2 = buf;
return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2) ? EOF : *p1++;
}
inline ull read() {
#define readchar getchar
ull res = 0, f = 0;
char ch = readchar();
for(; !isdigit(ch); ch = readchar()) if(ch == '-') f = 1;
for(; isdigit(ch);ch = readchar()) res = (res << 1) + (res << 3) + (ch ^ '0');
return f ? -res : res;
}
inline void write(ull x) {
if(x<0){putchar('-');x=-x;}
if(x>9) write(x/10);
putchar(x%10+'0');
}
int n,m,K,vis[MAX],tong[MAX][MAX];
vector<int> s[MAX],a[MAX];
queue<pair<int,int> > q;
void bfs(int u){
memset(vis,0,sizeof vis);
q.push(make_pair(u,-1));
while(!q.empty()){
auto f=q.front();q.pop();
if(vis[f.first]||f.second>K) continue;
vis[f.first]=1;
if(u!=f.first){
tong[u][f.first]=1;
// a[u].push_back(f.first);
}
for(int v:s[f.first])
q.push(make_pair(v,f.second+1));
}
return ;
}
//priority_queue<pair<int,int> > q2;
ull w[MAX];
signed main(){
n=read(),m=read(),K=read();
for(int i=2;i<=n;i++) w[i]=read();
for(int i=1;i<=m;i++){
int u=read(),v=read();
s[u].push_back(v);
s[v].push_back(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(tong[1][j]&&tong[i][j])
a[i].push_back(j);
for(int i=2;i<=n;i++)
sort(a[i].begin(),a[i].end(),[](int x,int y){
return w[x]>w[y];
});
ull ans=0;
for(int i=2;i<=n;i++)
for(int j=2;j<=n;j++){
if(!tong[i][j]) continue;
for(int k=0;k<min(3ll,(ll)a[i].size());k++)
for(int q=0;q<min(3ll,(ll)a[j].size());q++){
int x=a[i][k],y=a[j][q];
ans=max(ans,w[i]+w[j]+w[x]+w[y]);
}
}
cout<<ans;
return 0;
}
T2
用时：\(30\) min
期望得分：\(60\)
实际得分：\(60\)
由于前面写T4和T1占了太长时间，这题只码了一个 \(60\) 的暴力上去。
显然题目是要求你求出原矩阵的一个子矩阵中行最小值最大的那个最小值。
正解是考虑对于 A 的每种决策，根据正负，B只会做出选择最大值或最小值的决策，所以 A 只会有四种可能的决策：选正数最大，正数最下，负数最大，负数最小，\(0\) 可以随便归入一类。
那就直接开 \(6\) 个 ST 表，分别维护上面的 \(6\) 个最值，直接枚举八种情况求最 \(\max\) 即可。
复杂度 \(O(q(\log n+\log m)+n+m)\)。
#include<bits/stdc++.h>
#define ll long long
#define int long long
//#define ull unsigned long long
#define lc(k) k<<1
#define rc(k) k<<1|1
#define lb lower_bound
#define orz cout<<"gzn ak ioi\n"
const int MAX=1e6+10;
const int MOD=1e9+7;
using namespace std;
inline char readchar() {
static char buf[100000], *p1 = buf, *p2 = buf;
return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2) ? EOF : *p1++;
}
inline int read() {
#define readchar getchar
int res = 0, f = 0;
char ch = readchar();
for(; !isdigit(ch); ch = readchar()) if(ch == '-') f = 1;
for(; isdigit(ch);ch = readchar()) res = (res << 1) + (res << 3) + (ch ^ '0');
return f ? -res : res;
}
inline void write(int x) {
if(x<0){putchar('-');x=-x;}
if(x>9) write(x/10);
putchar(x%10+'0');
}
int n,m,q,a[MAX],b[MAX],st[8][MAX][20];
int lg[MAX];
/*
0 A 正大
1 A 正小
2 A 负大
3 A 负小
4 B 最大
5 B 最小
*/
void init(int i){
int len=(i<4)?n:m;
if(i&1){//min
for(int j=1;j<=20;j++)
for(int k=1;k+(1l<<j)-1<=len;k++)
st[i][k][j]=min(st[i][k][j-1],st[i][k+(1ll<<(j-1))][j-1]);
}
else{
for(int j=1;j<=20;j++)
for(int k=1;k+(1l<<j)-1<=len;k++)
st[i][k][j]=max(st[i][k][j-1],st[i][k+(1ll<<(j-1))][j-1]);
}
}
int ask(int i,int l,int r){
int x=lg[r-l+1];
if(i&1) return min(st[i][l][x],st[i][r-(1ll<<x)+1][x]);
else return max(st[i][l][x],st[i][r-(1ll<<x)+1][x]);
}
signed main(){
n=read(),m=read(),q=read();
lg[0]=-1;
for(int i=1;i<=max(n,m);i++) lg[i]=lg[i>>1]+1;
for(int i=1;i<=n;i++){
a[i]=read();
if(a[i]>=0){
st[0][i][0]=st[1][i][0]=st[3][i][0]=a[i];
st[2][i][0]=-1e18;
}
else{
st[0][i][0]=st[2][i][0]=st[3][i][0]=a[i];
st[1][i][0]=1e18;
}
}
for(int i=1;i<=m;i++){
b[i]=read();
st[4][i][0]=st[5][i][0]=b[i];
}
for(int i=0;i<=5;i++) init(i);
while(q--){
int ans=-1e18;
int l1=read(),r1=read(),l2=read(),r2=read();
ans=max(ans,min(ask(0,l1,r1)*ask(4,l2,r2),ask(0,l1,r1)*ask(5,l2,r2)));
if(ask(1,l1,r1)!=1e18) ans=max(ans,min(ask(1,l1,r1)*ask(4,l2,r2),ask(1,l1,r1)*ask(5,l2,r2)));
if(ask(2,l1,r1)!=-1e18) ans=max(ans,min(ask(2,l1,r1)*ask(4,l2,r2),ask(2,l1,r1)*ask(5,l2,r2)));
ans=max(ans,min(ask(3,l1,r1)*ask(4,l2,r2),ask(3,l1,r1)*ask(5,l2,r2)));
write(ans);
putchar('\n');
}
return 0;
}
T3
用时：\(30\) min
期望得分：\(40\)
实际得分：\(40\)
这题是最后写的，因为题面很长，这题主要难度在读题，一句话概括题意就是：
给定一个有向简单图，有若干删边加边操作，在每次操作后询问是否满足所有点的出度均为 \(1\)。
考虑哈希维护这个东西，维护一个出度为 \(1\) 的集合 \(A\)，把它哈希成所有点的编号平方和*对应出度，当 \(A\{1,2,3\dots n\}\) 时输出 YES。
复杂度 \(O(n)\)。
#include<bits/stdc++.h>
#define ll long long
#define int long long
//#define ull unsigned long long
#define lc(k) k<<1
#define rc(k) k<<1|1
#define lb lower_bound
#define orz cout<<"gzn ak ioi\n"
const int MAX=1e6+10;
const int MOD=1e9+7;
using namespace std;
inline char readchar() {
static char buf[100000], *p1 = buf, *p2 = buf;
return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2) ? EOF : *p1++;
}
inline int read() {
#define readchar getchar
int res = 0, f = 0;
char ch = readchar();
for(; !isdigit(ch); ch = readchar()) if(ch == '-') f = 1;
for(; isdigit(ch);ch = readchar()) res = (res << 1) + (res << 3) + (ch ^ '0');
return f ? -res : res;
}
inline void write(int x) {
if(x<0){putchar('-');x=-x;}
if(x>9) write(x/10);
putchar(x%10+'0');
}
int n,m,sum1,sum2,sum3[MAX],sum4[MAX];
signed main(){
n=read(),m=read();
// mt19937 Rand(time(0));
for(int i=1;i<=n;i++) sum1+=(i*i);
for(int i=1;i<=m;i++){
int u=read(),v=read();
sum2+=u*u;
sum3[v]+=u*u;
sum4[v]+=u*u;
}
// for(int i=1;i<=n;i++) cout<<sum3[i]<<" ";
int q=read();
while(q--){
int opt=read();
if(opt==1){
int u=read(),v=read();
sum2-=u*u;
sum3[v]-=u*u;
}
else if(opt==2){
int u=read();
sum2-=sum3[u];
sum3[u]=0;
}
else if(opt==3){
int u=read(),v=read();
sum2+=u*u;
sum3[v]+=u*u;
}
else{
int u=read();
sum2+=sum4[u]-sum3[u];
sum3[u]=sum4[u];
}
// cout<<sum1<<" "<<sum2<<endl;
// for(int i=1;i<=n;i++) cout<<sum3[i]<<" ";
// puts("");
if(sum1==sum2) puts("YES");
else puts("NO");
}
return 0;
}
T4
考场用时：\(2\) h
期望得分：\(44\)
实际得分：\(48\)
这题调了大约一个小时，据说正解是动态dp或者神奇树剖，不会。