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
*/