2016CCPC东北地区大学生程序设计竞赛题解

本文主要是介绍2016CCPC东北地区大学生程序设计竞赛题解，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

以下所有AC题解程序来自“仙客传奇”团队。

A. Minimum’s Revenge

AC的C++语言程序：

#include<iostream>
using namespace std;int main(){int t;long long a, b;cin >> t;for(int test = 1; test <= t; ++test){cin >> a >> b;cout << "Case #" << test << ":\n";if(a == b)cout << "1\n" << a << ' ' << b << endl;else if(a < b){cout << "2\n";cout << a << ' ' << b << endl;cout << b << ' ' << a << endl;}else{cout << "2\n";cout << b << ' ' << a << endl;cout << a << ' ' << b << endl;}}return 0;
}

B. Prediction

题解链接：
HDU5923——Prediction（数据结构，并查集）
hdu5923(并查集维护联通块)

C. Mr. Frog’s Problem

AC的C++语言程序：

#include<iostream>
using namespace std;int main(){int t;long long a, b;cin >> t;for(int test = 1; test <= t; ++test){cin >> a >> b;cout << "Case #" << test << ":\n";if(a == b)cout << "1\n" << a << ' ' << b << endl;else if(a < b){cout << "2\n";cout << a << ' ' << b << endl;cout << b << ' ' << a << endl;}else{cout << "2\n";cout << b << ' ' << a << endl;cout << a << ' ' << b << endl;}}return 0;
}

D. Coconuts

AC的C++语言程序：

#include<iostream>
#include<algorithm>
#include<queue>
#include<cstring>
using namespace std;
typedef long long ll;struct poll{long long x, y;bool operator < (poll const & a){return x < a.x;}
}bad[205];bool cmp(poll const& a, poll const& b){return a.y < b.y;
}
ll map[205][205], mark[205][205], allx[205], ally[205];
ll Move[4][2] = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
ll r, c;
long long ans[500];ll BFS(ll x,ll y){ll ret = 1;queue <poll> q;poll temp, tmp;temp.x = x; temp.y = y;mark[x][y] = 1;q.push(temp);while(!q.empty()){temp = q.front();q.pop();ll tempx, tempy;for(ll i = 0;i < 4; ++i){tempx = temp.x + Move[i][0];tempy = temp.y + Move[i][1];if(tempx < 1 || tempx > r || tempy < 1 || tempy > c) continue;if(map[tempx][tempy] == 0 && mark[tempx][tempy] == 0){mark[tempx][tempy] = 1;tmp.x = tempx;tmp.y = tempy;q.push(tmp);++ret;}}}return ret;
}int main(){ll t, n;ll x0, y0;long long count, temp;cin >> t;for(ll test = 1;test <= t;++test){count = 1, temp = 0;cin >> r >> c;cin >> n;for(ll i = 0; i < n; ++i)cin >> bad[i].x >> bad[i].y;bool sta1 = false,sta2 = false;sort(bad, bad + n);if(bad[0].x > 2)     temp += (bad[0].x - 2) * c;if(bad[0].x >= 2)    x0 = 1;if(r > bad[n - 1].x)   sta1 = true;if(r > bad[n - 1].x + 1)   temp += (r - bad[n - 1].x - 1) * c;for(ll i = 1;i < n;++i){if(bad[i].x - bad[i - 1].x > 2)	temp += (bad[i].x - bad[i - 1].x - 2) * c;allx[i] = bad[i].x - bad[i - 1].x;}if(bad[0].x > 2)    bad[0].x = 2;for(ll i = 1; i < n; ++i)if(allx[i] > 2)bad[i].x = bad[i - 1].x + 2;elsebad[i].x = bad[i - 1].x + allx[i];if(sta1){r = bad[n - 1].x + 1;x0 = r;}else r = bad[n - 1].x;sort(bad, bad + n, cmp);if(bad[0].y > 2) temp += (bad[0].y - 2) * r;if(bad[0].y >= 2) y0 = 1;if(c > bad[n - 1].y) sta2 = true;if(c >  bad[n - 1].y + 1) temp += (c - bad[n - 1].y - 1) * r;for(ll i = 1;i < n;++i){if(bad[i].y - bad[i - 1].y > 2)temp += (bad[i].y - bad[i - 1].y - 2) * r;ally[i] = bad[i].y - bad[i - 1].y;}if(bad[0].y > 2)    bad[0].y = 2;for(ll i = 1; i < n; ++i)if(ally[i] > 2)bad[i].y = bad[i - 1].y + 2;elsebad[i].y = bad[i - 1].y + ally[i];if(sta2){c = bad[n - 1].y + 1;y0 = c;}else c = bad[n - 1].y;memset(mark, 0, sizeof(mark));memset(map, 0, sizeof(map));for(ll i = 0; i < n; ++i)map[bad[i].x][bad[i].y] = 1;temp += BFS(x0, y0);ans[0] = temp;for(ll i = 1;i <= r;++i)for(ll j = 1;j <= c;++j)if(map[i][j] == 0 && mark[i][j] == 0){ans[count] = BFS(i, j);++count;}sort(ans, ans + count);cout << "Case #" << test << ":" << endl;cout << count << endl;for(ll i = 0; i < count - 1; ++i)cout << ans[i] << ' ';cout << ans[count - 1] << endl;}return 0;
}

AC的C++语言程序：

#include<bits/stdc++.h>using namespace std;const int maxn=220;typedef long long ll;
bool vis[maxn][maxn];
ll x[maxn],y[maxn];
map<ll,int> mx,my;struct point{ll x,y;
}p[maxn];vector<ll> x_len,y_len,ans;ll sum;int dx[]={0,0,-1,1};
int dy[]={1,-1,0,0};void dfs(int x,int y){vis[x][y]=1;sum+=x_len[x]*y_len[y];for(int i=0;i<4;i++){int tx=x+dx[i];int ty=y+dy[i];if(tx>=0&&tx<x_len.size()&&ty>=0&&ty<y_len.size()&&!vis[tx][ty]){dfs(tx,ty);}}
}void init(){x_len.clear();y_len.clear();mx.clear();my.clear();ans.clear();memset(vis,0,sizeof vis);
}int main(){int T;scanf("%d",&T);for(int cs=1;cs<=T;cs++){init();int n,m,k;scanf("%d%d",&n,&m);int cnt1=0,cnt2=0;x[cnt1++]=y[cnt2++]=0;x[cnt1++]=n;y[cnt2++]=m;scanf("%d",&k);for(int i=0;i<k;i++){scanf("%lld%lld",&p[i].x,&p[i].y);x[cnt1++]=p[i].x;y[cnt2++]=p[i].y;}sort(x,x+cnt1);sort(y,y+cnt2);cnt1=unique(x,x+cnt1)-x;cnt2=unique(y,y+cnt2)-y;for(int i=1;i<cnt1;i++){int len=x[i]-x[i-1];    //两个障碍点之间的距离。if(len>1){x_len.push_back(len-1); //包括障碍点，空白的点连接起来的长度}x_len.push_back(1); //障碍点mx[x[i]]=x_len.size()-1;}for(int i=1;i<cnt2;i++){int len=y[i]-y[i-1];    //两个障碍点之间的距离。if(len>1){y_len.push_back(len-1); //包括障碍点，空白的点连接起来的长度}y_len.push_back(1); //障碍点my[y[i]]=y_len.size()-1;}for(int i=0;i<k;i++){vis[mx[p[i].x]][my[p[i].y]]=1;}for(int i=0;i<x_len.size();i++){for(int j=0;j<y_len.size();j++){if(!vis[i][j]){sum=0;dfs(i,j);ans.push_back(sum);}}}sort(ans.begin(),ans.end());printf("Case #%d:\n%d\n",cs,ans.size());for(int i=0;i<ans.size();i++){printf(i==ans.size()-1?"%lld\n":"%lld ",ans[i]);}}return 0;
}

E. Mr. Frog’s Game

AC的C++语言程序：

#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<iostream>
using namespace std;int n, m, map[50][50], flag;
int f[4][2]= {{0, 1}, {1, 0}, {-1, 0}, {0, -1}};
int main() {std::ios::sync_with_stdio(false);int T;cin>>T;for(int t = 1; t <= T; t++) {cin >> n >> m;for(int i = 1; i <= n; i++)for(int j = 1; j <= m; j++)cin >> map[i][j];flag = 1;for(int i = 1; i <= n; i++)for(int j = i + 1; j <= n; j++)if(map[i][1] == map[j][1])flag = 0;for(int i = 1; i <= n; i++)for(int j = i + 1; j <= n; j++)if(map[i][m] == map[j][m])flag = 0;for(int i = 1; i <= m; i++)for(int j = i + 1; j <= m; j++)if(map[1][i] == map[1][j])flag = 0;for(int i = 1; i <= m; i++)for(int j = i + 1; j <= m; j++)if(map[n][i] == map[n][j])flag = 0;for(int i = 2; i < n; i++) {for(int j = 2; j < m; j++) {for(int k = 0; k < 4; k++) {int x = f[k][0] + i, y = j + f[k][1];if(map[i][j] == map[x][y])flag = 0;}}}cout << "Case #" << t << ": ";if(flag) cout << "No" << endl;else cout << "Yes" << endl;}return 0;
}

AC的C++语言程序：

#include<bits/stdc++.h>using namespace std;typedef long long ll;int g[40][40];int main()
{int T;scanf("%d",&T);int ca=1;while(T--){int n,m;scanf("%d%d",&n,&m);for(int i=0;i<n;i++){for(int j=0;j<n;j++){scanf("%d",&g[i][j]);}}map<int,int> ma;//上bool flag=0;for(int i=0;i<m;i++){ma[g[0][i]]++;if(ma[g[0][i]]>1) flag=1;}ma.clear();//下for(int i=0;i<m;i++){ma[g[n-1][i]]++;if(ma[g[n-1][i]]>1) flag=1;}ma.clear();//左for(int i=0;i<n;i++){ma[g[i][0]]++;if(ma[g[i][0]]>1) flag=1;}ma.clear();//右for(int i=0;i<n;i++){ma[g[i][m-1]]++;if(ma[g[i][m-1]]>1) flag=1;}for(int i=1;i<n;i++){for(int j=1;j<m;j++){if(g[i][j]==g[i-1][j]||g[i][j]==g[i][j-1]){flag=1;}}}if(flag==1){printf("Case #%d: Yes\n",ca++);}else{printf("Case #%d: No\n",ca++);}}return 0;
}

F. Auxiliary Set

AC的C++语言程序：

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
const int MAXN = 1e5 + 7;
struct node{int deep, fa, son, vis;bool operator < (const node &B) const{return deep < B.deep;}
}nod[MAXN];
bool cmp(int A, int B){return nod[A].deep > nod[B].deep;
}
int tmp[MAXN], se[MAXN];
vector<int>head[MAXN];
int n, m, k;
void dfs(int u, int f, int d){nod[u].vis = 1;nod[u].fa = f;nod[u].deep = d;for(int i = 0, l = head[u].size(); i < l; ++i){int v = head[u][i];if (!nod[v].vis){nod[u].son++;dfs(v, u, d + 1);}}
}int main(){int t, i;scanf("%d", &t);for(int test=1; test <= t;test++){scanf("%d%d", &n, &m);for(i = 1; i <= n; ++i){head[i].clear();nod[i].son = nod[i].vis = 0;}int u, v;for(i = 0; i < n - 1; i++){scanf("%d%d", &u, &v);head[u].push_back(v);head[v].push_back(u);}dfs(1, 0, 0);printf("Case #%d:\n", test);while(m--){scanf("%d", &k);int ans = n - k;for(i = 0; i < k; i++){scanf("%d", &se[i]);tmp[se[i]] = nod[se[i]].son;}sort(se, se + k, cmp);for (i = 0; i < k; i++){if (tmp[se[i]] >= 2) ans++;else if (!tmp[se[i]]) tmp[nod[se[i]].fa]--;}printf("%d\n", ans);}}return 0;
}

AC的C++语言程序：

#include<bits/stdc++.h>using namespace std;const int maxn=2e5+10;int dep[maxn];
int fa[maxn];
int son[maxn];
int son_[maxn];
int d[maxn];int head[maxn];
int tot;struct node{int to;int next;
}g[maxn];void addedge(int u,int v){g[tot].to=v;g[tot].next=head[u];head[u]=tot++;
}void dfs(int v,int pre){fa[v]=pre;dep[v]=dep[pre]+1;son[v]=0;for(int i=head[v];~i;i=g[i].next){if(g[i].to!=pre){dfs(g[i].to,v);son[v]++;}}
}bool cmp(int a,int b){return dep[a]>dep[b];
}void init(){memset(head,-1,sizeof head);tot=0;dep[0]=0;
}int main(){int T;scanf("%d",&T);for(int cs=1;cs<=T;cs++){init();int n,q;scanf("%d%d",&n,&q);for(int i=0;i<n-1;i++){int u,v;scanf("%d%d",&u,&v);addedge(u,v);addedge(v,u);}dfs(1,0);printf("Case #%d:\n",cs);while(q--){int m;scanf("%d",&m);int ans=n-m;for(int i=0;i<m;i++){scanf("%d",&d[i]);}sort(d,d+m,cmp);for(int i=0;i<m;i++) son_[d[i]]=son[d[i]];for(int i=0;i<m;i++){if(son_[d[i]]>=2) ans++;else if(son_[d[i]]==0) son_[fa[d[i]]]--;}printf("%d\n",ans);}}return 0;
}

G. Birthday Gift

题解链接：
【HDU5928 2016CCPC东北地区大学生程序设计竞赛 - 重现赛 G】
hdu 5928 极角排序+dp
【HDU】5928 Birthday Gift【极角排序+dp】

H. Basic Data Structure

AC的C++语言程序：

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
using namespace std;
const int maxn = 201001;
int dir, head, End, cnt, n, Cnt, S, E;
int stack[3 * maxn + 1], p[3], stack2[3 * maxn + 1];
char str[20];
void init(){dir = 1;S = head = 300001;E = End = 300000;memset(stack, 0, sizeof(stack));memset(stack2, 0, sizeof(stack2));stack2[S] = head;stack2[E] = End;cnt = 0;Cnt = 0;
}void push(){int x = 0;scanf("%d", &x);getchar();End += dir;stack[End] = x;if (x == 0){cnt++;E += dir;stack2[E] = End;}Cnt++;
}void pop(){if (stack[End] == 0) cnt--;if (End == stack2[E]) E -= dir;End -= dir;Cnt--;
}void reverse(){swap(head, End);swap(S, E);dir = -dir;
}void query(){int num = 0;if (Cnt == 0) printf("Invalid.\n");else if (head == End) cout << stack[head] << endl;else if (cnt == 0){if (Cnt % 2 == 1) puts("1");else puts("0");} else{num = abs(head - stack2[S]);if (!(cnt == 1 && stack2[S] == End)) num++;if (num % 2 == 0 && num > 0) puts("0");else puts("1");} 
}
int main(){int T;cin >> T;for (int test = 1; test <= T; test++){printf("Case #%d:\n", test);init();scanf("%d\n", &n);while (n--){scanf("%s", str);if (!strcmp(str, "PUSH")) push();else if (!strcmp(str, "POP")) pop();else if (!strcmp(str, "REVERSE")) reverse();else if (!strcmp(str, "QUERY")) query();}}return 0;
}

AC的C++语言程序：

#include<bits/stdc++.h>using namespace std;char s[10];const int maxn=2e5;int q[maxn*2+10];int main(){int T,ca=1;scanf("%d",&T);while(T--){int l=maxn-1,r=maxn;deque<int> dq;int n;bool flag=1;scanf("%d",&n);printf("Case #%d:\n",ca++);while(n--){scanf("%s",s);if(s[2]=='S'){int x;scanf("%d",&x);if(flag){q[r++]=x;if(x==0){dq.push_back(r-1);}}else{q[l--]=x;if(x==0){dq.push_front(l+1);}}}else if(s[2]=='P'){if(flag){int x=q[--r];if(x==0) dq.pop_back();}else{int x=q[++l];if(x==0) dq.pop_front();}}else if(s[2]=='V'){flag=!flag;}else{if(r==l+1) printf("Invalid.\n");else if(dq.empty()) printf("%d\n",(r-l-1)%2);else{if(flag) printf("%d\n",(dq.front()-l-1+(dq.front()!=r-1))%2);else printf("%d\n",(r-dq.back()-1+(dq.back()!=l+1))%2);}}}}return 0;
}