比赛链接：2010-2011 ACM-ICPC, NEERC, Southern Subregional Contest
第一次打零食赛，被菊苣暴虐。 B:直接算就行
#include<bits/stdc++.h> using namespace std; typedef long long ll; int G[107][107]; int dir[4][2]={ {1,0},{-1,0},{0,1},{0,-1} }; int n,m; int ans; void update(int x,int y) { if(G[x][y]==0) return ; ans+=2; for(int i=0;i<4;i++) { int tx=x+dir[i][0]; int ty=y+dir[i][1]; if(tx>0&&tx<=n&&ty>0&&ty<=m) { if(G[x][y]>G[tx][ty]) ans+=G[x][y]-G[tx][ty]; } else ans+=G[x][y]; } } void ioinit(){freopen("input.txt","r",stdin);freopen("output.txt","w",stdout);} int main() { //freopen("in.txt","r",stdin); ioinit(); scanf("%d%d",&n,&m); char s[107]; for(int i=1;i<=n;i++) { scanf("%s",s+1); for(int j=1;j<=m;j++) G[i][j]=s[j]-'0'; } for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) update(i,j); printf("%d\n",ans); return 0; }C：状压dp。向行投掷炸弹共有 2n 种情况，枚举一下。对于每种情况 mask ， mask 标记了不投掷炸弹的行，则在行上要投掷炸弹的数量为 n−num[mask] （ num[i] 为 i 中 1 的数量）。对于标记的行，我们在列上投炸弹，投炸弹的状态记为 c[mask] 。设 r[i] 为第 i 行的炸弹分布情况，1 表示有炸弹， c[i] 的转移方程为：
c[i]=c[i−lowbit(i)]|r[log2(lowbit(i))] 对于每种情况， ans=min(ans,max(n−num[mask],num[c[i]])) #include<bits/stdc++.h> using namespace std; const int N=25; int r[N],c[1<<N],num[1<<N]; inline int lowbit(int x) {return x&-x; } inline int p(int x,int res=-1){while(x){x>>=1;++res;}return res;} void ioinit(){freopen("input.txt","r",stdin);freopen("output.txt","w",stdout);} int main() { ioinit(); int n,m; scanf("%d%d",&n,&m); for(int i=1;i<(1<<N);i++) num[i]=num[i-lowbit(i)]+1; getchar(); for(int i=0;i<n;i++) for(int j=0;j<m;j++) { r[i]<<=1; char ch=getchar(); if(ch=='*') ++r[i]; if(j+1==m) getchar(); } int ans=n; for(int i=1;i<(1<<n);i++) { c[i]=c[i-lowbit(i)]|r[p(lowbit(i))]; ans=min(ans,max(num[c[i]],n-num[i])); } printf("%d\n",ans); return 0; }D:博弈，先处理出最短路树，叶子结点一定是必败点，sg=0，然后最短路树同时是一个DAG，dfs的同时计算每个点的sg就行了。
#include<bits/stdc++.h> using namespace std; const int N=1007; vector<int> adj[N],e[N]; bool vis[N]; int d[N],sg[N]; void bfs() { queue<int> q; q.push(1); vis[1]=true; d[1]=0; while(!q.empty()) { int u=q.front();q.pop(); for(auto v:adj[u]) { if(!vis[v]) { vis[v]=true; q.push(v); d[v]=d[u]+1; } } } } void dfs(int u) { if(e[u].size()==0) { sg[u]=0; return ; } vis[u]=true; set<int> s; for(auto v:e[u]) { if(!vis[v]) dfs(v); s.insert(sg[v]); } int val=0; while(s.count(val)) val++; sg[u]=val; } void ioinit() { freopen("input.txt","r",stdin); freopen("output.txt","w",stdout); } int main() { ioinit(); int n,m,u,v; cin>>n>>m; for(int i=0;i<m;i++) { cin>>u>>v; adj[v].push_back(u); adj[u].push_back(v); } bfs(); for(int u=1;u<=n;u++) for(auto v:adj[u]) if(d[v]==d[u]+1) e[u].push_back(v); memset(vis,0,sizeof(vis)); dfs(1); if(sg[1]) cout << "Vladimir" << endl; else cout << "Nikolay" << endl; return 0; }E:状压dfs
#include<bits/stdc++.h> using namespace std; bool vis[207][207]; int d[207]; bool pos[207]; int n,k; struct Node { int v,d; Node(){} Node(int _v,int _d):v(_v),d(_d){} }; vector<Node> adj[207]; void dfs(int u, int c) { if(c==k) { pos[u]=true; return ; } vis[u][c]=true; for(auto e: adj[u]) { int v=e.v,d=e.d; if(vis[v][c+1]||::d[c+1]!=d) continue; dfs(v,c+1); } } void ioinit() { freopen("input.txt","r",stdin); freopen("output.txt","w",stdout); } int main() { ioinit(); scanf("%d",&n); for(int u=1;u<=n;u++) for(int v=1;v<=n;v++) { int t; scanf("%d",&t); if(t) adj[u].push_back(Node(v,t)); } scanf("%d",&k); for(int i=1;i<=k;i++) scanf("%d",&d[i]); for(auto e: adj[1]) { int v=e.v,d=e.d; if(::d[1]==d) dfs(v,1); } vector<int> ans; for(int i=1;i<=n;i++) if(pos[i]) ans.push_back(i); printf("%d\n",(int)ans.size()); for(int i=0;i<ans.size();i++) printf("%d%c",ans[i],i+1==ans.size()?'\n':' '); return 0; }F:模拟一下就行了。
#include<bits/stdc++.h> using namespace std; bool lt[107]; int o[107]; vector<int> ans; void ioinit() { freopen("input.txt","r",stdin); freopen("output.txt","w",stdout); } int main() { ioinit(); int n,f; cin>>n>>f; for(int i=0;i<n;i++) { int t; cin>>t; o[i]=t; lt[t]=true; } int to=o[0],cur=0; while(ans.size()<n) { while(f<to) { ++f; if(lt[f]) { lt[f]=false; ans.push_back(f); } } while(f>to) { --f; if(lt[f]) { lt[f]=false; ans.push_back(f); } } for(++cur;cur<n;cur++) if(lt[o[cur]]) break; to=o[cur]; } for(int i=0;i<ans.size();i++) printf("%d%c",ans[i],i+1==ans.size()?'\n':' '); return 0; }G:有两种做法： 第一种是直接暴力枚举每条边然后跑tarjan求出答案就行。复杂度应该是 O(m(n+m)) ，鉴于cf强大的评测机，还是1000ms过了。。。感觉现场赛不可能过的。
#include<bits/stdc++.h> using namespace std; const int N=1007; struct Edge { int id,u,v; Edge(){} Edge(int _u,int _v):u(_u),v(_v){} }; Edge e[20007]; vector<int> adj[N]; int dfn[N],low[N],st[N],ins[N],vis[N],index,top,c; vector<int> ans[N]; void tarjan(int u) { int v; low[u]=dfn[u]=++index; st[top++]=u; ins[u]=true; for(auto v:adj[u]) { if(!dfn[v]) { tarjan(v); if(low[u]>low[v]) low[u]=low[v]; } else if(ins[v]&&low[u]>dfn[v]) low[u]=dfn[v]; } if(low[u]==dfn[u]) { int res=0; do { v=st[--top]; ins[v]=false; res++; }while(v!=u); c=max(c,res); } } void ioinit() { freopen("input.txt","r",stdin); freopen("output.txt","w",stdout); } int main() { //freopen("in.txt","r",stdin); ioinit(); int n,m,u,v; scanf("%d%d",&n,&m); if(m==0) { printf("1\n0\n\n"); } for(int i=1;i<=m;i++) { scanf("%d%d",&u,&v); e[i]=Edge(u,v); adj[u].push_back(v); } for(int i=1;i<=m;i++) { u=e[i].u;v=e[i].v; adj[v].push_back(u); top=c=index=0; memset(dfn,0,sizeof(dfn)); memset(ins,0,sizeof(ins)); for(int i=1;i<=n;i++) if(!dfn[i]) tarjan(i); ans[c].push_back(i); adj[v].pop_back(); } for(int i=n;i>=1;i--) { if(ans[i].size()) { printf("%d\n%d\n",i,(int)ans[i].size()); for(int j=0;j<ans[i].size();j++) printf("%d%c",ans[i][j],j+1==ans[i].size()?'\n':' '); break; } } return 0; }还有一种做法是分类讨论： 若边在强连通分量内，则它变成有向边后不影响原图的连通性，所以答案为原图的答案。 若边不在强连通分量内，对于边 (u,v) 找出 u 所能到达的点和能到达 v 的点的交集的数量。这个数量就是答案。因为构成的新联通集中，所有点都满足这个条件。 这种做法复杂度为 O(n2+nm)
#include<bits/stdc++.h> using namespace std; const int N=1007; struct Edge { int id,u,v; Edge(){} Edge(int _u,int _v):u(_u),v(_v){} }; Edge e[20007]; vector<int> adj[N]; int dfn[N],low[N],st[N],ins[N],index,top,c,G[N][N],vis[N],idd,id[N],n,U; vector<int> ans[N]; void tarjan(int u) { dfn[u]=low[u]=++index; int v; st[top++]=u; ins[u]=true; for(auto v:adj[u]) { if(!dfn[v]) { tarjan(v); low[u]=min(low[u],low[v]); } else if(ins[v]) low[u]=min(low[u],dfn[v]); } if(low[u]==dfn[u]) { int res=0; ++idd; do { v=st[--top]; ins[v]=false; id[v]=idd; res++; }while(u!=v); c=max(res,c); } } void dfs(int U,int u) { vis[u]=true; for(auto v:adj[u]) { if(!vis[v]) { G[U][v]=true; dfs(U,v); } } } int get_c(int u,int v) { int res=2; for(int i=1;i<=n;i++) if(G[u][i]&&G[i][v]) ++res; return res; } void ioinit() { freopen("input.txt","r",stdin); freopen("output.txt","w",stdout); } int main() { ioinit(); int m,u,v; scanf("%d%d",&n,&m); if(m==0) { printf("1\n0\n\n"); } for(int i=1;i<=m;i++) { scanf("%d%d",&u,&v); e[i]=Edge(u,v); adj[u].push_back(v); } for(int i=1;i<=n;i++) { memset(vis,0,sizeof(vis)); dfs(i,i); } for(int i=1;i<=n;i++) if(!dfn[i]) tarjan(i); for(int i=1;i<=m;i++) { int u=e[i].u,v=e[i].v; if(id[u]==id[v]) ans[c].push_back(i); else ans[get_c(u,v)].push_back(i); } for(int i=n;i>=1;i--) { if(ans[i].size()) { printf("%d\n%d\n",i,(int)ans[i].size()); for(int j=0;j<ans[i].size();j++) printf("%d%c",ans[i][j],j+1==ans[i].size()?'\n':' '); break; } } return 0; }H：首先求出每个点对于 y 的LIS长度。可以通过对 (x,y) 排序， x 升序， y 降序来解决。 一个点是可能访问的点当且仅当它在一个 LIS 中。设 p[i] 记录了长度为 i 的LIS 的最后一个点的最大 y 值。从后往前扫，一个点j在 LIS 中当且仅当它能转移到一个 l 值恰好比它大1 且其纵坐标比它大的点，且这个点在 LIS 中，即 y[l[j]]<p[l[j]+1] （ l[i] 是 i 的LIS 长度）。如果 j 满足上述条件，则更新 p[l[j]]=max(p[l[j]],y[j]) 。 在 LIS 中， l[i] 是递增的，因此如果有某个 l[i] 仅出现了一次，那么 i <script type="math/tex" id="MathJax-Element-155">i</script> 一定被访问。
#include<bits/stdc++.h> using namespace std; const int INF=0x3f3f3f3f; const int N=1e5+7; struct Node { int x,y,id; bool operator < (const Node & r) const { return x<r.x||(x==r.x&&y>r.y); } }; Node pt[N]; int len[N],d[N],p[N],c[N]; vector<int> A,B; void ioinit(){freopen("input.txt","r",stdin);freopen("output.txt","w",stdout); } int main() { ioinit(); int n; scanf("%d",&n); for(int i=1;i<=n;i++) { scanf("%d%d",&pt[i].x,&pt[i].y); pt[i].id=i; } sort(pt+1,pt+n+1); memset(d,0x3f,sizeof(d)); d[0]=-1e9;d[1]=pt[1].y; len[1]=1; int h=1; for(int i=2;i<=n;i++) { int y=pt[i].y; len[i]=lower_bound(d,d+n,y)-d; d[len[i]]=min(d[len[i]],y); h=max(h,len[i]); } p[h+1]=1e9; for(int i=1;i<=h;i++) p[i]=-INF; for(int i=n;i>=1;i--) { if(pt[i].y<p[len[i]+1]) { A.push_back(pt[i].id); p[len[i]]=max(p[len[i]],pt[i].y); if(c[len[i]]) c[len[i]]=-1; else c[len[i]]=pt[i].id; } } for(int i=n;i>=1;i--) if(c[i]!=-1&&c[i]!=0) B.push_back(c[i]); sort(A.begin(),A.end()); sort(B.begin(),B.end()); printf("%d ",(int)A.size()); for(int i=0;i<A.size();i++) printf("%d%c",A[i],i+1==A.size()?'\n':' '); printf("%d ",(int)B.size()); for(int i=0;i<B.size();i++) printf("%d%c",B[i],i+1==B.size()?'\n':' '); return 0; }J：一定一个点是不移动的，我们遍历每个点假设其不移动，然后在其基础上枚举间距，两点之间的间距是凹函数，而凹函数的二阶导是递增的，所以凹函数+凹函数的二阶导也是递增的，因此凹函数+凹函数=凹函数。所以答案是个凹函数。然后可以三分枚举一下。
#include<bits/stdc++.h> using namespace std; const double INF=1e15; double p[407],ans=INF,d; int n,pt; double cal(int k,double d) { double res=0; for(int i=0;i<n;i++) res+=fabs(p[i]-(p[k]+(i-k)*d)); return res; } void check(int k) { double l=0,r=20000; for(int i=0;i<200;i++) { double m=(l+r)/2; double mm=(m+r)/2; double ms=cal(k,m); double mms=cal(k,mm); if(mms>ms) r=mm; else l=m; } double res=cal(k,r); if(res<ans) { ans=res; pt=k; d=r; } } void ioinit() { freopen("input.txt","r",stdin); freopen("output.txt","w",stdout); } int main() { ioinit(); scanf("%d",&n); for(int i=0;i<n;i++) scanf("%lf",&p[i]); for(int i=0;i<n;i++) check(i); printf("%.10f\n",ans); for(int i=0;i<n;i++) printf("%.10f%c",p[pt]+(i-pt)*d,i+1==n?'\n':' '); return 0; }