11.3 解题报告

T1

用时：\(1\) h
期望得分：\(100\) pts
实际得分：\(40\) pts
这题是一个比较简单的贪心，枚举根，bfs求出根到每个点的最小距离然后取 \(\min\) 即可，当然由于点数极小，也可以直接枚举拓扑序，适当剪枝可过。

考场挂分一是用了邻接矩阵存图，而是搜索有一个地方没有清空标记。

#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,w[15];
int mp[15][15];
vector<int> e[15],s[15];
int dp[15],sum[15];
int calc(int fa,int k,int dep){
	int ret=0;
	sum[k]=w[k];
	for(int i:s[k]){
		if(i==fa) continue;
		ret+=calc(k,i,dep+1);
		sum[k]+=sum[i];
	}
	return dp[k]=ret+w[k]*dep;
}
int ans=1e9,vis[15],jl[15],js,a[15];
void dfs(int stp,int dep){
	++js;
	if(js>1.2e5) return ;
	if(stp==n){
		ans=min(ans,calc(0,1,1));
		for(int i=2;i<=n;i++)
		return ;
	}
	for(int x=1;x<=n;x++){
		int i=a[x];
		if(vis[i]) continue;
		for(int j:e[i]){
			if(jl[j]==dep-1){
				s[j].push_back(i);
				s[i].push_back(j);
				jl[i]=dep;vis[i]=1;
				dfs(stp+1,dep);
				jl[i]=0;vis[i]=0;
				s[i].pop_back();
				s[j].pop_back();
			}
			else if(jl[j]==dep&&mp[i][j]){
				s[j].push_back(i);
				s[i].push_back(j);
				jl[i]=dep+1;vis[i]=1;
				dfs(stp+1,dep+1);
				jl[i]=0;vis[i]=0;
				s[i].pop_back();
				s[j].pop_back();
			}
		}
	}
	return ;
}
signed main(){
//	freopen("tree.in","r",stdin);
//	freopen("tree.out","w",stdout);
	n=read(),m=read();
	for(int i=1;i<=n;i++) w[i]=read();
	for(int i=1;i<=n;i++) a[i]=i;
	sort(a+1,a+1+n,[](int x,int y){
		return w[x]>w[y];
	});
	for(int i=1;i<=m;i++){
		int u=read()+1,v=read()+1;
		if(!mp[u][v]){
			e[u].push_back(v);
			e[v].push_back(u);
		}
		mp[u][v]=mp[v][u]=1;
	}
	if(m==n-1){
		for(int i=1;i<=n;i++)
			for(int j:e[i]) s[i].push_back(j);
		for(int i=1;i<=n;i++) ans=min(ans,calc(0,i,1));
	}
	else{
		for(int x=1;x<=n;x++){
			int i=a[x];
			jl[i]=1;vis[i]=1;
			js=0;
			dfs(1,2);
			jl[i]=0;vis[i]=0;
		}
	}
	if(ans==1e9) ans=-1;
	cout<<ans<<endl;
	return 0;
}

T2

用时：近 \(2\) h
期望得分：\(100\) pts
实际得分：\(0\) pts
考场由于不是很会处理 set 的边界问题，选择了基于数据随机的 vector 做法，但事实证明数据不是随机的，这个做法的细节也更多，所以动手写之前还是要好好考虑一下。

#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,a,b;
multiset<pair<int,int>> xx,yy;
signed main(){
	n=read(),m=read();
	for(int i=1;i<=n;i++){
		a=read(),b=read();
		xx.insert(make_pair(a,b));yy.insert(make_pair(b,a));
	}
	int op,l,r;
	while(m--){
		int ans=0;
		op=read(),l=read(),r=read();
		if(!op){
			for(auto i=xx.lower_bound(make_pair(l,-1));i!=xx.end() && i->first<=r;i=xx.erase(i))
			yy.erase(yy.lower_bound(make_pair(i->second,i->first))),ans++;
		}
		else{
			for(auto i=yy.lower_bound(make_pair(l,-1));i!=yy.end() && i->first<=r;i=yy.erase(i))
			xx.erase(xx.lower_bound(make_pair(i->second,i->first))),ans++;
		}
		cout<<ans<<'\n';
	}
}

T3

用时：\(20\) min
期望得分：\(30\) pts
实际得分：\(0\) pts
这题放在了最后做，时间不够了，没仔细读题，题目的 lcs 和 lds 其实是可以重复在一起的，没有注意到这一点导致挂分。

正解是线段树合并维护 \(k\) 的子树内某个权值结尾的 lcs 和 lds 长度，枚举 \(k\) 的同时边更新答案边线段树合并即可。

#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=1e5+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,w[MAX],t[MAX],m;
struct node{int mx1,mx2,lc,rc;}a[MAX*100];
vector<int> s[MAX];
int rot[MAX],cnt;
int now_node(){return ++cnt;}
void push_up(int k){
	a[k].mx1=max(a[a[k].lc].mx1,a[a[k].rc].mx1);
	a[k].mx2=max(a[a[k].lc].mx2,a[a[k].rc].mx2);
	return ;
}
int merge(int u,int v,int l,int r){
	if(!u||!v) return u+v;
	if(l==r){
		a[u].mx1=max(a[u].mx1,a[v].mx1);
		a[u].mx2=max(a[u].mx2,a[v].mx2);
		return u;
	}
	int mid=(l+r)>>1;
	a[u].lc=merge(a[u].lc,a[v].lc,l,mid);
	a[u].rc=merge(a[u].rc,a[v].rc,mid+1,r);
	push_up(u);
	return u; 
}
int insert(int k,int x,int mx1,int mx2,int l,int r){
//	cout<<l<<" "<<r<<" "<<x<<endl; 
	if(!k) k=now_node();
	if(l==r){
		a[k].mx1=mx1;
		a[k].mx2=mx2;
		return k;
	}
	int mid=(l+r)>>1;
	if(x<=mid) a[k].lc=insert(a[k].lc,x,mx1,mx2,l,mid);
	else a[k].rc=insert(a[k].rc,x,mx1,mx2,mid+1,r);
	push_up(k);
	return k;
}
node ask(int L,int R,int l,int r,int k){
	if(!k||l>R||r<L) return (node){0,0};
	if(l>=L&&r<=R) return a[k];
	int mid=(l+r)>>1;
	node x=ask(L,R,l,mid,a[k].lc);
	node y=ask(L,R,mid+1,r,a[k].rc);
	return (node){max(x.mx1,y.mx1),max(x.mx2,y.mx2)};
}
int ans;
void dfs(int fa,int k){
	int mxs=0,mxj=0;
	for(int v:s[k]){
		if(v==fa) continue;
		dfs(k,v);
		int x=ask(1,w[k]-1,1,m,rot[v]).mx1;
		int y=ask(w[k]+1,m,1,m,rot[v]).mx2;
		ans=max(mxs+y+1,ans);
		ans=max(mxj+x+1,ans);
		mxs=max(mxs,x);
		mxj=max(mxj,y);
		rot[k]=merge(rot[k],rot[v],1,m);
	}
	rot[k]=insert(rot[k],w[k],mxs+1,mxj+1,1,m);
//	cout<<k<<" "<<x<<" "<<y<<" "<<cnt<<endl;
//	for(int i=1;i<=m;i++) cout<<ask(i,i,1,m,rot[k]).mx1
	return ;
}
signed main(){
//	freopen("1.in","r",stdin);
//	freopen("baoli.out","w",stdout);
	n=read();
	for(int i=1;i<=n;i++){
		t[i]=w[i]=read();
		int fa=read();
		if(fa) s[fa].push_back(i);
	}
	sort(t+1,t+1+n);
	m=unique(t+1,t+1+n)-t-1;
	for(int i=1;i<=n;i++) w[i]=lb(t+1,t+1+m,w[i])-t;
	dfs(0,1);
	cout<<ans;
	return 0;
}
/*
10
4 0
3 1
4 1
4 2
0 2
4 1
0 2
4 3
3 5
6 2
*/

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