Posts

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 操作。唯一可能影响次数的就是顺序。

最近入手了x1 c 然后发现没办法支持 f22….. 没办法，只好上f24了。。。虽然明知道一堆bug… 最近发现。。之前在系统设置->键盘->打字 中的调整键盘延迟和速率的选项。。。不见了。。。

题目链接 题意：有n扇门，n种钥匙，一一对应。每扇门打开后可能得到k把钥匙（k可能为0）。一扇门还可以用一颗炸弹炸开。现在问要开所有门，使用炸弹的期望个数。 思路：状态压缩。用一个二进制串表示每扇门能打开的门的信息，对应的位上为1表示能打开，为0表示不能打开。

题目链接 题意：给出一个数，问包含这个数三个数组成的勾股数，输出另外两个数。 思路： 所谓勾股数，就是当组成一个直角三角形的三边长都为正整数时，我们就称这一组数为勾股数. 那么，组成一组勾股数的三个正整数之间，是否具有一定的规律可寻呢？下面我们一起来观察几组勾股数： 规律一：在勾股数（3,4,5）、（5,12,13）、（7,24,25）（9,40,41）中，我们发现 由（3,4,5）有：32=9=4+5 由（5,12,13）有：52=25=12+13 由（7,24,25）有：72=49=24+25 由（9,40,41）有：92=81=40+41. 即在一组勾股数中，当最小边为奇数时，它的平方刚好等于另外两个连续的正整数之和.因此，我们把它推广到一般，从而可得出以下公式： ∵（2n+1)²=4n²+4n+1=（2n²+2n）+（2n²+2n+1） ∴（2n+1)²+（2n²+2n)²=（2n²+2n+1)²（n为正整数） 证明（略） 勾股数公式一：（2n+1,2n²+2n,2n²+2n+1）（n为正整数） 规律二：在勾股数（6,8,10）、（8,15,17）、（10,24,26）中，我们发现 由（6,8,10）有：62=36+2×（8+10） 由（8,15,17）有：82=64=2×（15+17） 由（10,24,26）有：102=100=2×（24+26） 即在一组勾股数中，当最小边为偶数时，它的平方刚好等于两个连续整数之和的二倍，推广到一般，从而可得出另一公式： ∵（2n）2=4n2=2[（n2-1）+（n2+1）] ∴（2n）2+（n2-1）2=（n2+1）2（n≥2且n为正整数） 证明（略） 勾股数公式二：（2n,n²-1,n²+1）（n≥2且n为正整数） 利用以上两个公式，我们可以快速写出各组勾股数.

题目链接 题意：把一个数n(n<1000)转化成二进制输出。。。 思路：。。。搜acm bitset 搜到这题。。。所以其实这并不是“bitset”优化的题。。。只是题目名字交这个了2333。

1.定义与初始化 在定义 bitset 时，要明确 bitset 有多少位，这个位数是整形常量 (tips：如果长度和输入的数m有关，在做翻转操作以后再统计时候会多算，一个可以的做法是设置一个长度为m，所有位上都是1的位串，然后翻转之后先与一下。类似的技巧还有很多。)

题目链接 题意：n个城市，m条双向路，要从k条中选择一个，使得到其他n-k个城市中的某个城市的距离最短。 思路：直接暴力 枚举。1A 代码实现 1/* *********************************************** 2Author :111qqz 3Created Time :2016年08月20日 星期六 21时02分14秒 4File Name :code/cf/#368/B.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 <deque> 14#include <map> 15#include <string> 16#include <cmath> 17#include <cstdlib> 18#include <ctime> 19#define fst first 20#define sec second 21#define lson l,m,rt<<1 22#define rson m+1,r,rt<<1|1 23#define ms(a,x) memset(a,x,sizeof(a)) 24typedef long long LL; 25#define pi pair < int ,int > 26#define MP make_pair 27using namespace std; 28const double eps = 1E-8; 29const int dx4[4]={1,0,0,-1}; 30const int dy4[4]={0,-1,1,0}; 31const int inf = 0x3f3f3f3f; 32const int N =1E5+7; 33int n,m,k; 34vector <pair <int,LL> >edge[N]; 35int b[N]; 36bool cangku[N]; 37int main() 38{ 39 #ifndef ONLINE_JUDGE 40 freopen("code/in.txt","r",stdin); 41 #endif 42 ios::sync_with_stdio(false); 43 cin>>n>>m>>k; 44 ms(cangku,false); 45 for ( int i = 1 ; i <= m ; i++) 46 { 47 int u,v; 48 LL w; 49 cin>>u>>v>>w; 50 edge[u].push_back(make_pair(v,w)); 51 edge[v].push_back(make_pair(u,w)); 52 } 53 if (k==0) 54 { 55 cout<<-1<<endl; 56 return 0 ; 57 } 58 for ( int i = 1 ; i <= k ; i++) 59 { 60 cin>>b[i]; 61 cangku[b[i]] = true; 62 } 63 if (k==n) 64 { 65 cout<<-1<<endl; 66 return 0; 67 } 68 LL ans = inf; 69 for (int i = 1 ; i <= k ; i++) 70 { 71 int u = b[i]; 72 int siz = edge[u].size(); 73 for (int j = 0 ; j < siz ; j++) 74 { 75 int v = edge[u][j].fst; 76 if (cangku[v]) continue; 77 LL w = edge[u][j].sec; 78 ans = min(ans,w); 79 } 80 } 81 if (ans==inf) ans = -1; 82 cout<<ans<<endl; 83 #ifndef ONLINE_JUDGE 84 fclose(stdin); 85 #endif 86 return 0; 87}

题目链接 。。。这题也能成hack题。。。。有毒啊。。然后我room里所有人都写对了。。。是我看这道题看得太早了？ 代码实现 1/* *********************************************** 2Author :111qqz 3Created Time :2016年08月20日 星期六 21时01分57秒 4File Name :code/cf/#368/A.cpp 5************************************************ */ 6 7#include <cstdio> 8#include <cstring> 9#include <iostream> 10#include <algorithm> 11#include <vector> 12#include <queue> 13#include <set> 14#include <deque> 15#include <map> 16#include <string> 17#include <cmath> 18#include <cstdlib> 19#include <ctime> 20#define fst first 21#define sec second 22#define lson l,m,rt<<1 23#define rson m+1,r,rt<<1|1 24#define ms(a,x) memset(a,x,sizeof(a)) 25typedef long long LL; 26#define pi pair < int ,int > 27#define MP make_pair 28 29using namespace std; 30const double eps = 1E-8; 31const int dx4[4]={1,0,0,-1}; 32const int dy4[4]={0,-1,1,0}; 33const int inf = 0x3f3f3f3f; 34const int N=105; 35int n,m; 36int main() 37{ 38 #ifndef ONLINE_JUDGE 39 freopen("code/in.txt","r",stdin); 40 #endif 41 42 cin>>n>>m; 43 bool ok = false; 44 for ( int i = 1 ; i <= n ; i++) 45 for ( int j = 1 ; j <=m ; j++ ) 46 { 47 char col; 48 cin>>col; 49 if (col=='C'||col=='M'||col=='Y') ok = true; 50 } 51 if (ok) cout<<"#Color"<<endl; 52 else cout<<"#Black&White"<<endl; 53 54 #ifndef ONLINE_JUDGE 55 fclose(stdin); 56 #endif 57 return 0; 58}

hdu 1754 题目链接 题意：单点更新，区间查询最大值。 思路：线段树。 一开始借鉴了 clj 的 pointer 写法，wjmzbmr’s code 直接 MLE，看来也许只能在 cf 上用。 下面是 MLE 的代码： 代码实现 1/* *********************************************** 2Author :111qqz 3Created Time :2016年08月18日 星期四 18时40分24秒 4File Name :code/hdu/1754.cpp 5************************************************ */ 6#include <cstdio> 7#include <cstring> 8#include <iostream> 9#include <algorithm> 10#include <vector> 11#include <queue> 12#include <stack> 13#include <set> 14#include <map> 15#include <string> 16#include <cmath> 17#include <cstdlib> 18#include <deque> 19#define fst first 20#define sec second 21#define lson l,m,rt<<1 22#define rson m+1,r,rt<<1|1 23#define ms(a,x) memset(a,x,sizeof(a)) 24typedef long long LL; 25#define pi pair < int ,int > 26#define MP make_pair 27using namespace std; 28const double eps = 1E-8; 29const int dx4[4]={1,0,0,-1}; 30const int dy4[4]={0,-1,1,0}; 31const int inf = 0x3f3f3f3f; 32const int N=2E5+7; 33int a[N],n,m; 34int _max( int x,int y) 35{ 36 if (x==-1||y==-1) 37 return x==-1?y:x; 38 return a[x]>a[y]?x:y; 39} 40struct Tree 41{ 42 Tree *pl,*pr; 43 int l,r,mx; 44 void update() 45 { 46 mx = _max(pl->mx,pr->mx); 47 } 48 Tree(int l,int r) : 49 l(l),r(r) 50 { 51 if ( l + 1 == r) 52 { 53 mx = l ; 54 return ; 55 } 56 pl = new Tree(l,(l+r)>>1); 57 pr = new Tree((l+r)>>1,r); 58 update(); 59 } 60 void change(int p,int x) 61 { 62 if (p < l|| p>=r) return; 63 if (l+1==r) 64 { 65 a[l] = x; 66 return ; 67 } 68 pl->change(p,x); 69 pr->change(p,x); 70 update(); 71 } 72 int queryMax(int L,int R) 73 { 74 if (L <= l && r <= R) return mx; 75 if (L>=r || l >=R) 76 return -1; 77 return _max(pl->queryMax(L,R),pr->queryMax(L,R)); 78 } 79}*rt; 80int main() 81{ 82 #ifndef ONLINE_JUDGE 83 freopen("code/in.txt","r",stdin); 84 #endif 85 while (~scanf("%d%d",&n,&m)) 86 { 87 ms(a,0); 88 for ( int i = 0 ; i < n ; i++) scanf("%d",a+i); 89 rt = new Tree(0,n); 90 while (m--) 91 { 92 char opt[3]; 93 int x,y; 94 scanf("%s %d %d",opt,&x,&y); 95 x--; 96 if (opt[0]=='Q') 97 printf("%d\n",a[rt->queryMax(x,y)]); 98 else rt->change(x,y); 99 } 100 } 101 #ifndef ONLINE_JUDGE 102 fclose(stdin); 103 #endif 104 return 0; 105} 关于线段树的理解，见代码注释：