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或者神奇树剖,不会。

原文地址:http://www.cnblogs.com/wapmhac/p/16852832.html

1. 本站所有资源来源于用户上传和网络,如有侵权请邮件联系站长! 2. 分享目的仅供大家学习和交流,请务用于商业用途! 3. 如果你也有好源码或者教程,可以到用户中心发布,分享有积分奖励和额外收入! 4. 本站提供的源码、模板、插件等等其他资源,都不包含技术服务请大家谅解! 5. 如有链接无法下载、失效或广告,请联系管理员处理! 6. 本站资源售价只是赞助,收取费用仅维持本站的日常运营所需! 7. 如遇到加密压缩包,默认解压密码为"gltf",如遇到无法解压的请联系管理员! 8. 因为资源和程序源码均为可复制品,所以不支持任何理由的退款兑现,请斟酌后支付下载 声明:如果标题没有注明"已测试"或者"测试可用"等字样的资源源码均未经过站长测试.特别注意没有标注的源码不保证任何可用性