11-13 周赛
Wrestling Match
Problem Description
Input
Output
Sample Input
Sample Output
题目要求
给你N场比赛的双方对战情况，每场比赛必定有一方是Good Player另一方是Bad Player。你的任务是判断是否所有的人都可以被分为Good Players or Bad Player。
参考AC代码
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 85 86 87 88 89 90 91 92 93 94 95
| using namespace std; vector<int>G[MAX]; int color[MAX]; int N,M,X,Y; bool DFS(int v,int c) { color[v]=c; for(int i=0;i<G[v].size();i++) { if(color[G[v][i]]==c) return false; if(color[G[v][i]]==0&&!DFS(G[v][i],-c)) return false; } return true; } void solve() { for(int i=1;i<=N;i++) { if(color[i]==1) { if(!DFS(i,1)) { printf("NO\n"); return ; } } else if(color[i]==-1) { if(!DFS(i,-1)) { printf("NO\n"); return ; } } } for(int i=1;i<=N;i++) { if(color[i]==0) { if(!DFS(i,1)) { printf("NO\n"); return ; } } } for(int i=1;i<=N;i++) { if(color[i]==-5) { printf("NO\n"); return ; } } printf("YES\n"); } int main() { int a,b; while(scanf("%d%d%d%d",&N,&M,&X,&Y)!=EOF) { for(int i=1;i<=N;i++) { G[i].clear(); color[i]=-5; } for(int i=1;i<=M;i++) { scanf("%d%d",&a,&b); color[a]=0; color[b]=0; G[a].push_back(b); G[b].push_back(a); } for(int i=1;i<=X;i++) { scanf("%d",&a); color[a]=1; } for(int i=1;i<=Y;i++) { scanf("%d",&a); color[a]=-1; } solve(); } return 0; }
|
思路
二分图染色即可。交叉染色法的基本思路：
首先任意取出一个顶点进行染色,和该节点相邻的点有三种情况:
1.未染色—–那么继续染色此节点(染色为另一种颜色)
2.已染色但和当前节点颜色不同—–跳过该点
3.已染色并且和当前节点颜色相同—–返回失败(该图不是二分图)
宽搜+队列或深搜+交叉染色都可以，这里只给出后者的AC代码。
注意事项
存在单独的连通块，若不知道他是好还是坏那么输出NO。
To begin or not to begin
Problem Description
Input
Output
Sample Input
Sample Output
题目要求
有x个黑球和1个红球，抽到红球算游戏胜利，问先手和后手谁赢得几率大或者一样大。
参考AC代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14
| using namespace std; int main() { int n; while(cin>>n) { if(n&1) cout<<"0"<<endl; else cout<<"1"<<endl; } return 0; }
|
思路
多写几组样例可以发现是判断奇偶性的问题。
最大的位或
Problem Description
Input
Output
Sample Input
Sample Output
参考AC代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23
| using namespace std; int main() { int t; cin>>t; while(t--) { long long l,r; cin>>l>>r; long long i; for(i=1;(l|i)<=r;i<<=1) l|=i; if(l+1<=r) { l|=i; cout<<l<<endl; } else cout<<l<<endl; } return 0; }
|
思路
通过位运算找到小于r的1最多的数，判断自加后仍在不在r范围内，若不在原数就是所求，否则两数相或就是所求。
Convex
Problem Description
Input
Output
Sample Input
Sample Output
题目要求
求图形面积
参考AC代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
| using namespace std; int main() { int n,d; while(cin>>n>>d) { double re=0; int x; for(int i=1;i<=n;i++) { cin>>x; re+=d*d*sin(PI*x/180)/2; } printf("%.3f\n",re); } return 0; }
|
思路
简单数学模拟。
把图形面积划为求三角形面积，运用公式s=1/2absinα。题中的ab和角度都已给出。
注意事项
使用math中的sin函数需注意角度是弧度制。
CRB and His Birthday
Problem Description
Input
Output
Sample Input
Sample Output
题目要求
背包问题，给出背包容量，物品种类，物品花费和获得糖果的表达式。
参考AC代码
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
| using namespace std; int v,n; int w[N<<1],a[N<<1],b[N<<1]; int dp[N<<1]; int main() { int t; scanf("%d",&t); while(t--) { scanf("%d%d",&v,&n); for(int i=1;i<=n;i++) { int x,y,z; scanf("%d%d%d",&x,&y,&z); w[i]=x,a[i]=y+z; w[i+n]=x,a[i+n]=y; } memset(dp,0,sizeof(dp)); for(int i=1;i<=n;i++) for(int j=v;j>=w[i];j--) dp[j]=max(dp[j],dp[j-w[i]]+a[i]); for(int i=n+1;i<=2*n;i++) for(int j=w[i];j<=v;j++) dp[j]=max(dp[j],dp[j-w[i]]+a[i]); printf("%d\n",dp[v]); } return 0; }
|
思路
观察Ai×x+Bi的表达式可以发现，第一次买物品获得的价值为Ai+Bi，以后每次的价值为Ai，所以题目可以划为一次01背包和多重背包。
注意事项
由于把所物品化成Ai+Bi和Ai两种价值，相当于物品的种类扩大了两倍，所以数组必须开为原来的两倍。
Counting Cliques
Problem Description
Input
Output
Sample Input
Sample Output
题目要求
给你一张无向图，要你求元素个数是S的团的个数。
团的定义：任意两个点之间都有一条边相邻图。
参考AC代码
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
| using namespace std; int s,u,v,ans; int g[111][111]; int data[111]; vector<int>e[1111]; int dfs(int id,int size){ if(size==s){ ans++; return 0; } for(int i=0;i<e[id].size();i++){ int ep=e[id][i]; bool flag=true; for(int j=1;j<=size;j++){ if(!g[ep][data[j]]){ flag=false; break; } } if(flag){ data[++size]=ep; dfs(ep,size); data[size--]=0; } } } int main(){ // freopen("input.txt","r",stdin); int t; cin>>t; while(t--){ int n,m; cin>>n>>m>>s; memset(g,0,sizeof(g)); for(int i=1;i<=n;i++) e[i].clear(); for(int i=1;i<=m;i++){ cin>>u>>v; if(u>v) swap(u,v); e[u].push_back(v); g[u][v]=g[v][u]=1; } ans=0; for(int i=1;i<=n;i++){ data[1]=i; dfs(i,1); } cout<<ans<<endl; } return 0; }
|
思路
让每一条边都是u指向v,这里有u<v。这样建边，dfs的时候如果出现过1，2，4，8这种情况后，不会再出现2，4，8，1这类的重复计算。
使用vector前向星存贮图。使用深搜遍历所有的情况即可。
