向总的评测机有毒。。本来310的能给卡成210。。
1.题目一
求最长公共上升子序列
枚举a[i], b[o]
用f[o]表示以b[o]结尾能匹配的最大长度（要求此时b[o]=a[i]）
那么f[o]=max(f[k])+1, k<o, b[k]<b[o]
枚举b[o]的时候记一下最大值即可将转移复杂度降到O(1)
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 |
// <one.cpp> - 02/18/16 08:05:00 // This file is created by XuYike's black technology automatically. // Copyright (C) 2015 ChangJun High School, Inc. // I don't know what this program is. #include <iostream> #include <vector> #include <algorithm> #include <cstring> #include <cstdio> #include <cmath> using namespace std; typedef long long lol; int getint(){ int res=0,fh=1;char ch=getchar(); while((ch>'9'||ch<'0')&&ch!='-')ch=getchar(); if(ch=='-')fh=-1,ch=getchar(); while(ch>='0'&&ch<='9')res=res*10+ch-'0',ch=getchar(); return fh*res; } const int MAXN=5002; int a[MAXN],b[MAXN],f[MAXN]; int main(){ freopen("one.in","r",stdin); freopen("one.out","w",stdout); int n=getint(); for(int i=1;i<=n;i++)a[i]=getint(); for(int i=1;i<=n;i++)b[i]=getint(); for(int i=1;i<=n;i++){ int k=0;//保存b中<a[i]的f值最大的数 for(int o=1;o<=n;o++) if(a[i]==b[o])f[o]=max(f[o],f[k]+1); else if(b[o]<a[i]&&f[o]>f[k])k=o; } int ans=0; for(int i=1;i<=n;i++)ans=max(ans,f[i]); printf("%d",ans); return 0; } |
2.题目二
一个略麻烦的贪心
从下往上贪心，每个点记录c[i]【离它最远的没有消防站的点的距离】和f[i]【最近的消防站的距离】
那么当f[i]+c[i]<=d时说明这个点子树上都没问题了
否则如果c[i]==d在该点设置消防站
【听说可能会爆栈写了个手写栈 但善良的出题人并没有卡栈【却被向总的机子卡T掉30分
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 |
// <two.cpp> - 02/18/16 08:05:00 // This file is created by XuYike's black technology automatically. // Copyright (C) 2015 ChangJun High School, Inc. // I don't know what this program is. #include <iostream> #include <vector> #include <stack> #include <algorithm> #include <cstring> #include <cstdio> #include <cmath> using namespace std; typedef long long lol; int getint(){ int res=0,fh=1;char ch=getchar(); while((ch>'9'||ch<'0')&&ch!='-')ch=getchar(); if(ch=='-')fh=-1,ch=getchar(); while(ch>='0'&&ch<='9')res=res*10+ch-'0',ch=getchar(); return fh*res; } const int MAXN=500002; vector <int> b[MAXN]; int d,ans,n; int dep[MAXN],f[MAXN],c[MAXN]; bool vis[MAXN]; stack <int> s; vector <int> v; void dfs(int x){ s.push(x); while(!s.empty()){ int now=s.top();s.pop(); v.push_back(now); vis[now]=1;c[now]=1; for(int i=0;i<b[now].size();i++){ int next=b[now][i]; if(vis[next])continue; dep[next]=dep[now]+1; s.push(next); } } for(int a=n-1;a>=0;a--){ int now=v[a]; for(int i=0;i<b[now].size();i++){ int next=b[now][i]; if(dep[next]<dep[now])continue; if(f[next]&&(!f[now]||f[next]+1<f[now]))f[now]=f[next]+1; if(c[next])c[now]=max(c[now],c[next]+1); } if(f[now]&&f[now]+c[now]-2<=d)c[now]=0; if(c[now]-1==d){f[now]=1;c[now]=0;ans++;} } if(c[1])ans++; } int main(){ freopen("two.in","r",stdin); freopen("two.out","w",stdout); n=getint();d=getint(); for(int i=0;i<n-1;i++){ int x=getint(),y=getint(); b[x].push_back(y); b[y].push_back(x); } dfs(1); printf("%d",ans); return 0; } |
3.题目三
树分治？。。
好吧%王队给我们讲了一下
还算简单吧 就是不断找重心删重心
【然后就是最后一个点要开无限栈/写BFS
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 |
// <three.cpp> - 02/18/16 08:05:01 // This file is created by XuYike's black technology automatically. // Copyright (C) 2015 ChangJun High School, Inc. // I don't know what this program is. #include <iostream> #include <vector> #include <algorithm> #include <cstring> #include <cstdio> #include <cmath> using namespace std; typedef long long lol; int getint(){ int res=0,fh=1;char ch=getchar(); while((ch>'9'||ch<'0')&&ch!='-')ch=getchar(); if(ch=='-')fh=-1,ch=getchar(); while(ch>='0'&&ch<='9')res=res*10+ch-'0',ch=getchar(); return fh*res; } const int MAXN=100002; const int INF=1000000000; vector <int> b[MAXN]; int size[MAXN],k[MAXN],dep[MAXN]; bool kill[MAXN]; int n,d,root,S,ans; void gr(int x,int fa){ k[x]=0;size[x]=1; for(int i=0;i<b[x].size();i++){ int next=b[x][i]; if(next==fa||kill[next])continue; gr(next,x); size[x]+=size[next]; k[x]=max(k[x],size[next]); } k[x]=max(k[x],S-size[x]); if(k[x]<k[root])root=x; } int cnt[MAXN]; void dfs(int x,int fa){ cnt[dep[x]]++; for(int i=0;i<b[x].size();i++){ int next=b[x][i]; if(next==fa||kill[next])continue; dep[next]=dep[x]+1; dfs(next,x); } } int calc(int x,int k){ int tot=0; for(int i=0;i<=d;i++)cnt[i]=0; dep[x]=k;dfs(x,0); for(int i=0;i<<1<d;i++)tot+=cnt[i]*cnt[d-i]; if(!(d&1))tot+=(cnt[d>>1]*(cnt[d>>1]-1))>>1; return tot; } void get(int x){ ans+=calc(x,0); kill[x]=1; for(int i=0;i<b[x].size();i++){ int next=b[x][i]; if(kill[next])continue; ans-=calc(next,1); S=size[next]; if(S<d)continue; gr(next,root=0); get(root); } } int main(){ freopen("three.in","r",stdin); freopen("three.out","w",stdout); n=getint();d=getint(); for(int i=0;i<n-1;i++){ int x=getint(),y=getint(); b[x].push_back(y); b[y].push_back(x); } S=n;k[0]=INF; gr(1,root=0); get(root); printf("%d",ans); return 0; } |
4.题目四
裸的求树的直径
【听说DFS会爆栈于是写了个BFS 但善良的出题人并没有卡栈【却被向总的机子卡T掉70分
【DFS版】
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 |
// <four.cpp> - 02/18/16 08:05:01 // This file is created by XuYike's black technology automatically. // Copyright (C) 2015 ChangJun High School, Inc. // I don't know what this program is. #include <iostream> #include <vector> #include <queue> #include <algorithm> #include <cstring> #include <cstdio> #include <cmath> using namespace std; typedef long long lol; int getint(){ int res=0,fh=1;char ch=getchar(); while((ch>'9'||ch<'0')&&ch!='-')ch=getchar(); if(ch=='-')fh=-1,ch=getchar(); while(ch>='0'&&ch<='9')res=res*10+ch-'0',ch=getchar(); return fh*res; } const int MAXN=1000002; vector <int> b[MAXN]; int dep[MAXN]; bool vis[MAXN]; int D=1; void dfs(int x,bool f){ vis[x]=f; if(dep[x]>dep[D])D=x; for(int i=0;i<b[x].size();i++){ int next=b[x][i]; if(vis[next]==f)continue; dep[next]=dep[x]+1; dfs(next,f); } } int main(){ freopen("four.in","r",stdin); freopen("four.out","w",stdout); int n=getint(); for(int i=0;i<n-1;i++){ int x=getint(),y=getint(); b[x].push_back(y); b[y].push_back(x); } dfs(1,1);dep[D]=0; dfs(D,0); printf("%d",dep[D]); return 0; } |
【BFS版】
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 |
// <four.cpp> - 02/18/16 08:05:01 // This file is created by XuYike's black technology automatically. // Copyright (C) 2015 ChangJun High School, Inc. // I don't know what this program is. #include <iostream> #include <vector> #include <queue> #include <algorithm> #include <cstring> #include <cstdio> #include <cmath> using namespace std; typedef long long lol; int getint(){ int res=0,fh=1;char ch=getchar(); while((ch>'9'||ch<'0')&&ch!='-')ch=getchar(); if(ch=='-')fh=-1,ch=getchar(); while(ch>='0'&&ch<='9')res=res*10+ch-'0',ch=getchar(); return fh*res; } const int MAXN=1000002; vector <int> b[MAXN]; int dep[MAXN]; bool vis[MAXN]; int D=1; queue <int> q; void bfs(int x,bool f){ dep[x]=0;vis[x]=f;q.push(x); while(!q.empty()){ int now=q.front();q.pop(); if(dep[now]>dep[D])D=now; for(int i=0;i<b[now].size();i++){ int next=b[now][i]; if(vis[next]==f)continue; dep[next]=dep[now]+1; vis[next]=f;q.push(next); } } } int main(){ freopen("four.in","r",stdin); freopen("four.out","w",stdout); int n=getint(); for(int i=0;i<n-1;i++){ int x=getint(),y=getint(); b[x].push_back(y); b[y].push_back(x); } bfs(1,1); bfs(D,0); printf("%d",dep[D]); return 0; } |
农炸了
%