ACM

题目链接 题意：找两个不相交点集使得对于每一条边至少有一个顶点在点集中 思路：判断能否构成二分图。染色即可。 需要注意的是。。。答案有特判。。和样例不一样我还以为是自己做错了2333.

题目链接：题目链接 题意：给出一个无向图，该图是通过仅包含‘a’ ‘b’ ‘c’三个字母，以规则“i,j之间有边，当且仅当s[i]和s[j]相同，或者s[i]和s[j]在字母表中相邻”（也就是只有’a’和’c’是没有边相连的）得到的，现在问能否还原这个字符串，如果能，输出任意一个解。

题目链接：hdu 5285 题目lianjie 题意：给定n个小朋友，以及小朋友之间的关系，要求将小朋友分成两组，**并且每组至少一个人，**现在问能否这样分组，如果有解，输出两组的人数，并保证第一组的人数尽可能地大。

hdu 5215 思路：询问一个无向图，是否存在奇数环，以及是否存在偶数环。（不同的环之间可以有相同的点，不能有相同的边） 思路：一开始的想法是，根据染色的奇偶性，如果染色到某个之前染色过的点，和当前要染的颜色相同，说明存在奇数环，不同，说明存在偶数环。

hdu 2444题目链接 题意：判断一个有向图是否是二分图，是的话求最大匹配数。 思路：交叉染色判二分图，是的话跑遍匈牙利即可。1A. 代码实现 1/* *********************************************** 2Author :111qqz 3Created Time :2016年09月01日 星期四 14时24分36秒 4File Name :code/hdu/2444.cpp 5************************************************ */ 6#include <cstdio> 7#include <cstring> 8#include <iostream> 9#include <algorithm> 10#include <vector> 11#include <queue> 12#include <set> 13#include <map> 14#include <string> 15#include <cmath> 16#include <cstdlib> 17#include <ctime> 18#define fst first 19#define sec second 20#define lson l,m,rt<<1 21#define rson m+1,r,rt<<1|1 22#define ms(a,x) memset(a,x,sizeof(a)) 23typedef long long LL; 24#define pi pair < int ,int > 25#define MP make_pair 26using namespace std; 27const double eps = 1E-8; 28const int dx4[4]={1,0,0,-1}; 29const int dy4[4]={0,-1,1,0}; 30const int inf = 0x3f3f3f3f; 31const int N=205; 32int n,m; 33vector<int>edge[N]; 34int col[N]; 35int link[N]; 36bool vis[N]; 37void init() 38{ 39 for ( int i = 0 ; i <= n ; i++) edge[i].clear(); 40 ms(col,-1); 41} 42bool dfs( int u,int x) 43{ 44 col[u] = x; 45 int siz = edge[u].size(); 46 for ( int i = 0 ; i < siz; i++) 47 { 48 int v = edge[u][i]; 49 if (col[v]==1-x) continue; 50 if (col[v]==x) return false; 51 if (!dfs(v,1-x)) return false; 52 } 53 return true; 54} 55bool solve() 56{ 57 for ( int i = 1 ; i <= n ; i++) if (col[i]==-1) if (!dfs(i,0)) return false; 58 return true; 59} 60bool Find( int u) 61{ 62 int siz = edge[u].size(); 63 for ( int i = 0 ; i < siz; i ++) 64 { 65 int v = edge[u][i]; 66 if (vis[v]) continue; 67 vis[v] = true; 68 if (link[v]==-1||Find(link[v])) 69 { 70 link[v] = u; 71 return true; 72 } 73 } 74 return false; 75} 76int hung( int n) 77{ 78 int ans = 0 ; 79 ms(link,-1); 80 for ( int i = 1 ; i <= n ; i++) 81 { 82 ms(vis,false); 83 if (Find(i)) ans++; 84 } 85 return ans; 86} 87int main() 88{ 89 #ifndef ONLINE_JUDGE 90 freopen("code/in.txt","r",stdin); 91 #endif 92 while (~scanf("%d %d",&n,&m)) 93 { 94 init(); 95 for ( int i = 1 ; i <= m ; i++) 96 { 97 int u,v; 98 scanf("%d%d",&u,&v); 99 edge[u].push_back(v); 100 } 101 if (!solve()) 102 { 103 puts("No"); 104 } 105 else 106 { 107 int ans = hung(n); 108 printf("%d\n",ans); 109 } 110 } 111 #ifndef ONLINE_JUDGE 112 fclose(stdin); 113 #endif 114 return 0; 115}

hdu 4751 题目链接 题意：n个人，给出每个人认识的人的信息。问能否将这些人分成两组，保证每组至少1个人，并且两两互相认识。 思路：首先是反向建图。由于要求同组内两个人互相认识，那么两个人u,v，只要u不认识v或者v不认识有一个满足，就连接双向边u,v，表示u,v不能分到同一组。

uva10004题目链接 题意：给出一个无向图，问是否可以组成二分图。 思路：交叉染色法。 首先任意取出一个顶点进行染色，和该节点相邻的点有三种情况： **　1.未染色 那么继续染色此节点(染色为另一种颜色)**

3680: 吊打XXX # Time Limit: 10 Sec Memory Limit: 128 MBSec Special Judge Submit: 2043 Solved: 732 [Submit][Status][Discuss] Description # gty又虐了一场比赛，被虐的蒟蒻们决定吊打gty。gty见大势不好机智的分出了n个分身，但还是被人多势众的蒟蒻抓住了。蒟蒻们将 n个gty吊在n根绳子上，每根绳子穿过天台的一个洞。这n根绳子有一个公共的绳结x。吊好gty后蒟蒻们发现由于每个gty重力不同，绳 结x在移动。蒟蒻wangxz脑洞大开的决定计算出x最后停留处的坐标，由于他太弱了决定向你求助。 不计摩擦，不计能量损失，由于gty足够矮所以不会掉到地上。

hdu 5017 题目链接 题意：给出椭球方程的 6 个参数 a,b,c,d,e,f 问椭球上的点到原点 (0,0,0) 的最小距离是多少。 思路：感觉难点在于，如何保证搜到的点一直在椭球上。 一开始我考虑用椭球的参数方程，然后发现不记得是什么了 2333。

poj 2069 题目链接 题意：给出n个点，找出包含这n个点的最小半径的外接球。求球的半径。 思路：模拟退火。不过在走的时候，不是随机上下左右前后6个方向走，而是每次往距离当前球心最远的点的方向走。这样才能通过（随机6个方向的写法样例也是可以通过的）

貌似香港赛区的规则和大陆有所不同？ 来整理一波。 **D. **中国大陆赛站及境外赛站的关系。 (a)** **中国大陆各赛站及香港，北朝鲜赛站同为亚洲East Continent子赛区的一部分。

poj 1385 题目链接 题意：求多边形的重心。 思路： 抄模板（逃 嘛。。三角形的重心是三个点坐标的平均数。。。 多边形的重心其实就是先求三角形的重心然后再加权平均一下就好了。。。权值是面积比。

poj 2420 题意：求多边形费马点，也就是距离所有点的距离之和最小的点。 思路：模拟退火裸题。 关于模拟退火的学习： 模拟退火讲解 我就记住了一句话2333： 爬山算法：兔子朝着比现在高的地方跳去。它找到了不远处的最高山峰。但是这座山不一定是珠穆朗玛峰。这就是爬山算法，它不能保证局部最优值就是全局最优值。

题目链接 题意：问一个小矩形能否放在一个大矩形中，给定两个矩形的尺寸。 思路：主要是斜着放比较难判断。学弟貌似写了离散化角度旋转。。。我的做法是。。直接考虑对角线。。。因为我认为对角线是最有可能放进去的位置。

poj 1386 题意：n个单词，问能否形成一个串（单词接龙，收尾相连，当且仅当前一个单词的末尾字母和后一个单词的首字母相同） 思路：欧拉路。 关于欧拉路： (1)有向图G为欧拉图(存在欧拉回路)，当且仅当G的基图连通（弱联通，），且所有顶点的入度等于出度。

poj 1383题目链接 题意：一个迷宫图，求最远两点的距离是多少，保证每两个点都是联通的。 思路：树的直径。 代码实现 1#include <cstdio> 2#include <cstring> 3#include <iostream> 4#include <algorithm> 5#include <vector> 6#include <queue> 7#include <set> 8#include <map> 9#include <string> 10#include <cmath> 11#include <cstdlib> 12#include <ctime> 13#define fst first 14#define sec second 15#define lson l,m,rt<<1 16#define rson m+1,r,rt<<1|1 17#define ms(a,x) memset(a,x,sizeof(a)) 18typedef long long LL; 19#define pi pair < int ,int > 20#define MP make_pair 21using namespace std; 22const double eps = 1E-8; 23const int dx4[4]={1,0,0,-1}; 24const int dy4[4]={0,-1,1,0}; 25const int inf = 0x3f3f3f3f; 26const int N=1E3+7; 27char maze[N][N]; 28bool vis[N][N]; 29int ans; 30int n,m; 31struct Point 32{ 33 int x,y; 34 int d; 35 bool ok () 36 { 37 if (x<0||y<0||x>=n||y>=m) return false; 38 if (maze[x][y]=='#') return false; 39 if (vis[x][y]) return false; 40 return true; 41 } 42 void out() 43 { 44 cout<<"x:"<<x<<" y:"<<y<<endl; 45 } 46}S,lst; 47void bfs(Point S) 48{ 49 queue<Point>q; 50 S.d = 0; 51 q.push(S); 52 ms(vis,false); 53 vis[S.x][S.y] = true; 54 while (!q.empty()) 55 { 56 Point cur = q.front(); 57 q.pop(); 58 for ( int i = 0 ; i < 4 ; i++) 59 { 60 Point nxt; 61 nxt.x = cur.x + dx4[i]; 62 nxt.y = cur.y + dy4[i]; 63 nxt.d = cur.d + 1; 64 if (!nxt.ok()) continue; 65 q.push(nxt); 66 vis[nxt.x][nxt.y] = true; 67 if (ans<nxt.d) 68 { 69 ans = nxt. d; 70 lst = nxt; 71 } 72 } 73// cout<<"ans:"<<ans<<endl; 74 } 75} 76int main() 77{ 78 #ifndef ONLINE_JUDGE 79 freopen("code/in.txt","r",stdin); 80 #endif 81 int T; 82 cin>>T; 83 while(T--) 84 { 85 ms(vis,false); 86 scanf("%d%d",&m,&n); 87 for ( int i = 0; i < n ; i++) scanf("%s",maze[i]); 88 for ( int i = 0 ; i < n ; i++) 89 for ( int j = 0 ; j < m ; j++) 90 if (maze[i][j]=='.') 91 { 92 S.x = i ; 93 S.y = j ; 94 } 95 ans = 0; 96 bfs(S); 97 ans = 0 ; 98 bfs(lst); 99 printf("Maximum rope length is %d.\n",ans); 100 } 101 #ifndef ONLINE_JUDGE 102 fclose(stdin); 103 #endif 104 return 0; 105}

poj 1379题目链接 题意：给出一个矩形区域的长宽，给出区域中若干点，问距离所有点的最近距离的最大值是多少。 思路：很容易想到模拟退火。 比赛的时候因为忘记判断矩形边界导致答案错得离谱2333

题目链接 题意：把一个长度为 n 的只由数字构成的串分成 k 个不为空的子串，使得最大的串最小（大小是指串所对应的十进制数的大小）。 思路：由于长度为 x 的串肯定大于长度为 x-1 的串，因此很容易想到，我们要尽可能使得 k 组串的长度平均（避免出现某一个串的长度非常大的情况）。

题目链接 思路：注意xy-(x-2)*(y-2)=2x+2y-4，一定被2整除。因此siz为2的也是合法的。这个比较容易忘掉。 其他的判定条件都很好想。具体见代码； 代码实现 1#include <cstdio> 2#include <cstring> 3#include <iostream> 4#include <algorithm> 5#include <vector> 6#include <queue> 7#include <set> 8#include <map> 9#include <string> 10#include <cmath> 11#include <cstdlib> 12#include <ctime> 13#define fst first 14#define sec second 15#define lson l,m,rt<<1 16#define rson m+1,r,rt<<1|1 17#define ms(a,x) memset(a,x,sizeof(a)) 18typedef long long LL; 19#define pi pair < int ,int > 20#define MP make_pair 21using namespace std; 22const double eps = 1E-8; 23const int dx4[4]={1,0,0,-1}; 24const int dy4[4]={0,-1,1,0}; 25const int inf = 0x3f3f3f3f; 26int X,Y; 27bool ok( int a) 28{ 29 if (a==2) return true; 30 if (X%a==0&&(Y-2)%a==0) return true; 31 if (Y%a==0&&(X-2)%a==0) return true; 32 if (X%a==1&&Y%a==1) return true; 33 34 return false; 35} 36int main() 37{ 38 // freopen("in.txt","r",stdin); 39 40 while (~scanf("%d%d",&X,&Y)) 41 { 42 int n; 43 scanf("%d",&n); 44 while (n--) 45 { 46 int x; 47 scanf("%d",&x); 48 // cout<<"x:"<<x<<endl; 49 if (ok(x)) puts("YES"); 50 else puts("NO"); 51 } 52 } 53return 0; 54}

题目链接 题意：n个数围成一圈，对于负数可以进行magic操作，也就是取反，但是会影响到左右相邻的，加上这个负数。问最少进行多少次magic操作，使得所有数都是非负。 思路：我们知道，如果一个负数想变成整数的话，只能通过magic 操作。唯一可能影响次数的就是顺序。