ACM

cf689C 题意：给出一个m。。问恰好使得不超过某个n的a*b^3（a,b是正整数）的方案数为m的n是多少。。。 思路：暴力+二分。。。 代码实现 1/* *********************************************** 2Author :111qqz 3Created Time :2016年07月18日 星期一 15时58分55秒 4File Name :code/2016whust/G.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 <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 27 28using namespace std; 29const double eps = 1E-8; 30const int dx4[4]={1,0,0,-1}; 31const int dy4[4]={0,-1,1,0}; 32const int inf = 0x3f3f3f3f; 33LL m,n; 34LL ans; 35LL cal( LL x) 36{ 37 LL res = 0LL; 38 for ( LL i =2 ; i * i * i <= x ; i++) 39 res+=x/(i*i*i); 40 return res; 41} 42int main() 43{ 44 #ifndef ONLINE_JUDGE 45 freopen("code/in.txt","r",stdin); 46 #endif 47 48 cin>>m; 49 n = 0 ; 50 51 LL cur = 1LL<<60; 52// cout<<"cur:"<<cur<<endl; 53 while (cur!=0LL) 54 { 55 LL tmp = cal(n+cur); 56 if (tmp<m) n +=cur; 57 58 cur >>=1LL; 59 } 60 n++; 61// cout<<" n:"<<n<<endl; 62 if (cal(n)!=m) ans = -1; 63 else ans = n; 64 65 cout<<ans<<endl; 66 67 68 #ifndef ONLINE_JUDGE 69 fclose(stdin); 70 #endif 71 return 0; 72}

cf689B题目链接 题意：n点。。点i到点j的代价是|i-j|..给出n条近路。。。a[i]表示点i到a[i]的代价为1（注意近路不一定就近） 思路：一开始建边卡了一下。。。实际上只要连相邻的就好了。。。然后边表只开了2N蠢哭。。。实际上应该3M…因为连相邻的边是双向的。。。再加上近路的单向。。。然后spfa就好了。。。。

cf689A 思路：一个老式的电话键盘。。。。给出一个拨号的移动路径。。。问这个路径是否唯一。 思路：如果唯一就说明。。。不能平移。。。否则不唯一。。 平移可以上下左右。。所以先写4个常亮数组。。。标记平移后的结果。。。设置不合法位就可以了。。。

cf682C题目链接 题意：给一棵树。。有点权和边权。。。如果一个点v的子树中存在某点u，满足dis(u,v)>a[u]，那么点v就非常sad… dis(u,v)表示点u到v的距离。。。a[u]是u的点权。。现在问最少要删除多少个叶子节点才能使得没有点节点感到sad..

cf682B题目链接 题意：给出n个数。。每个数可以任意减小到一个正整数。。。问进行恰当的操作后。。。最小的没有出现的正整数的最大可能取值。。 思路：傻逼题。。。直接离散化。。。。注意不能超过初始。。。

cf682A题目链接 题意：两个数组，分别为1..n和1..m。。。从两个数组中各取一个，问和能被5整除的方案数。。。 思路：傻逼题。。。统计%5。。。然后乘法原理。。 代码实现 1/* *********************************************** 2Author :111qqz 3Created Time :2016年07月18日 星期一 12时32分22秒 4File Name :code/2016whust/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 <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 27 28using namespace std; 29const double eps = 1E-8; 30const int dx4[4]={1,0,0,-1}; 31const int dy4[4]={0,-1,1,0}; 32const int inf = 0x3f3f3f3f; 33const int N=1E6+7; 34int n,m; 35LL a[N],b[N]; 36int main() 37{ 38 #ifndef ONLINE_JUDGE 39 freopen("code/in.txt","r",stdin); 40 #endif 41 42 cin>>n>>m; 43 ms(a,0); 44 ms(b,0); 45 for ( int i = 1 ; i <= n ; i++) 46 { 47 int x = i % 5; 48 a[x]++; 49 } 50 for ( int i = 1 ; i <= m ; i++) 51 { 52 int x = i % 5; 53 b[x]++; 54 } 55 LL ans = 0; 56 ans = a[0]*b[0]+a[1]*b[4]+a[2]*b[3]+a[3]*b[2]+a[4]*b[1]; 57 cout<<ans<<endl; 58 59 #ifndef ONLINE_JUDGE 60 fclose(stdin); 61 #endif 62 return 0; 63}

hdu 4123 题目链接 题意：一棵树，定义 d[i] 为点 i 到树上某点的最大距离。给出若干查询，每个查询一个 x，问最多能有多少点满足这些点中，最大的 d 与最小的 d 的差小于等于 x。要求这些点的编号必须是连续的。

题目链接 题意：一棵树。。然后初始两个推雪机在点s，问如何选择路径使得处理完所有边上的积雪所耗费的汽油最少（走过一条有雪的边和一条没雪的边耗费的汽油一样） 思路：很容易想到，我们应该尽可能不走已经被清理过雪了的边，因为这样很浪费。。。这样不难想到应该是和树的直径有关。但是初始的位置是给定的。。。怎么办？突然发现由于是给了两个推雪机。。所以其实相当于。。。只有一个推雪机&我们可以从任意位置开始推雪。。。第二个问题是。。。对于不在直径上的边。。我们怎么算cost？解决办法是读边的时候进行记录。。。然后求直径的时候记录路径。。。对于一条边。。。只要有一个点不在直径上。。。那么这条边的代价就是2倍。。。

hdu3873题目链接 题意：n个点的图。。。每个点可能被若干其他点保护。。。被保护的意思是。。。如果想访问某个点。。那么必须先访问保护该点的所有点。。。问从点1到点n的最小代价。。 思路：。。一开始写了spfa。。。然后一脸懵逼。。。因为我第一次访问某个点的时候无法保证距离是最短的。。。所以还是上dij吧。。。

poj 2031 题意：三维空间中n个球要相连。。。通路的代价是距离。。。如果球相交（切）或者包含那么不用建通路就能联系。。。问联系所有球的最小代价。。。 思路：裸的最小生成树。。。。先预处理球和球表面的距离。。。距离是负数的处理成0.。。然后mst搞之。。。不算CE的话是1A….

poj1789题目链接 题意：其实题目不难理解。。。直接按照定义去搞就行了。。。 思路：由于距离在分母上。。所以要quality最大。。。就是要分母最小。。。 然后由于题目中说每一种类型的type只能由其他一种派生出来。。。我们可以把这个派生关系看做一条边。。。把每种类型看成点。。

Poj2349题目链接 题意：给出n个点坐标。。。然后可以建s个卫星基站。。。有卫星基站的地方之间可以互相免费通信。。现在要建一些无线电通讯线路（不同于卫星基站，是另一种通信方式），两个点之间线路的代价是他们的距离。。。问最小距离是多少。。。使得任意两个点之间都可以直接或者间接联系。。。

poj1751题目链接 题意：一开始有一些边，然后添加一些边，使得代价之和最小。 思路：先把给定的边merge掉。。然后计算其余可以添加的边。。。接下来就是最小生成树。。。 然而因为多开了一个750*750的数组空间被卡了常。。。毫无人性。。。。

hdu4607题目链接 题意：给出一棵树。。。边权都为1. m个查询。。每个查询给一个k，表示只访问k个点。。。问每次的最小路径和是多少。。。 思路：我们发现。。会使路径和变大的一个不利因素是折返。。也就是访问某景点后。。必须要回去才能继续前进。。这样的距离是2倍。。那为了使得路径和尽可能小。。我们就尽量不要访问这样的点。。。而不是这样的点一定在直径上。。。以及我们还发现。。。不在直径上的点。。 。。不管深度如何（深度的意思是说，与和该点最近的直径上的点的距离），距离的贡献是一样的。。都是2倍。。所以我们可以推出一个公式。。。如果树的直径是d，那么k<=d+1的时候，答案为k-1，否则答案为d+(k-d-1)*2。。。

poj 3310 题目链接 题意：给出一个无向图，问是否满足：连通，并且无环，并且能找到一条路径，图中所有的顶点要么在这条路径上，要么与这条路径上的顶点相邻。 思路：一个一个来。连通的话任意起点开始跑一遍 dfs？开一个 bool 数组标记走过的点，最后扫一遍，看是否有点没走过。

poj1679 题意：问最小生成树是否唯一。。 思路：求一下次小生成树。。。如果无解，或者次小生成树的权值之和和最小生成树的权值之和不同，那么唯一，否则不唯一。1A 代码实现 1/* *********************************************** 2Author :111qqz 3Created Time :2016年07月12日 星期二 16时16分52秒 4File Name :code/poj/1679.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=105; 32int n,m; 33int ans; 34int f[N]; 35struct Edge 36{ 37 int u,v,w; 38 int in; 39 void input() 40 { 41 scanf("%d%d%d",&u,&v,&w); 42 } 43 bool operator < (Edge b)const 44 { 45 return w<b.w; 46 } 47}edge[N*N]; 48void init() 49{ 50 for ( int i = 1 ; i <= n ; i++) f[i] = i; 51} 52int root ( int x) 53{ 54 if (x!=f[x]) f[x] = root(f[x]); 55 return f[x]; 56} 57void merge( int x,int y) 58{ 59 int rx = root(x); 60 int ry = root(y); 61 if (rx==ry) return ; 62 f[rx] = ry; 63} 64void kruskal( int k) 65{ 66 for ( int i = 1 ; i <= n; i++) f[i] = i; 67 int cnt = 0 ; 68 int cur = 0 ; 69 for ( int i = 1; i <= m ; i++) 70 { 71 int u = edge[i].u; 72 int v = edge[i].v; 73 int w = edge[i].w; 74 if (i==k) continue; 75 if (root(u)==root(v)) continue; 76 merge(u,v); 77 cnt++; 78 cur+=w; 79 if (cnt>=n-1) break; 80 } 81 // cout<<"cnt:"<<cnt<<endl; 82 if (cnt<n-1) return ; 83 ans = min(ans,cur); 84} 85int main() 86{ 87 #ifndef ONLINE_JUDGE 88 freopen("code/in.txt","r",stdin); 89 #endif 90 int T; 91 scanf("%d",&T); 92 while (T--) 93 { 94 scanf("%d%d",&n,&m); 95 init(); 96 for ( int i = 1; i <= m ; i++) edge[i].input(); 97 sort(edge+1,edge+m+1); 98 int cnt = 0 ; 99 int mst = 0 ; 100 for ( int i = 1 ; i <= m ; i++) 101 { 102 int u = edge[i].u; 103 int v = edge[i].v; 104 int w = edge[i].w; 105 if (root(u)==root(v)) continue; 106 edge[i].in = 1; 107 merge(u,v); 108 cnt++; 109 mst+=w; 110 } 111 ans = inf; 112 for ( int i = 1 ; i <= m ; i++) 113 { 114 if (edge[i].in==0) continue; 115 //cout<<"i:"<<i<<endl; 116 kruskal(i); 117 } 118 // cout<<"mst:"<<mst<<endl; 119 // cout<<"ans:"<<ans<<endl; 120 if (ans==inf) 121 { 122 printf("%d\n",mst); 123 }else 124 { 125 if (ans==mst) puts("Not Unique!"); 126 else printf("%d\n",mst); 127 } 128 } 129 #ifndef ONLINE_JUDGE 130 fclose(stdin); 131 #endif 132 return 0; 133}

hdu 4514 题意：给出一个无向图，问是否有环，有的话输出 YES。如果没有环的话，输出最长路径。 思路：无向图判环用并查集就好。关于最长路径这里，一开始以为就是树的直径。 但是需要注意的是，题目并没有保证图一定是联通的，所以 gg 了。

hdu 2196 题意：给出一棵树，求距离每个点的最远距离是多少。 思路：最远距离什么的，能想到树的直径，但是有什么关系呢？我们在求树的直径的时候，直径的两个端点是可以知道的。如果再从两个端点分别做两次 bfs，每个点取两个距离的较大值就是答案。。？

poj2631 题意：一棵树中求两个点的最远距离。。。 思路：就是求树的直径。。。裸体。。。。1A 代码实现 1/* *********************************************** 2Author :111qqz 3Created Time :2016年07月12日 星期二 13时03分39秒 4File Name :code/poj/2631.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 <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 27 28using namespace std; 29const double eps = 1E-8; 30const int dx4[4]={1,0,0,-1}; 31const int dy4[4]={0,-1,1,0}; 32const int inf = 0x3f3f3f3f; 33const int N=1E4+7; 34int n,m; 35vector < pi> edge[N]; 36int lst; 37int ans; 38int d[N]; 39bool vis[N]; 40 41 42void bfs( int s) 43{ 44 ms(d,0x3f); 45 ms(vis,false); 46 queue<int>q; 47 q.push(s); 48 vis[s] = true; 49 d[s] = 0 ; 50 51 while (!q.empty()) 52 { 53 int u = q.front() ; q.pop(); 54 lst = u ; 55// cout<<"u:"<<u<<endl; 56 int siz = edge[u].size(); 57 58 for ( int i = 0 ; i < siz ; i++) 59 { 60 int v = edge[u][i].fst; 61 if (vis[v]) continue; 62 vis[v] = true; 63 d[v] = d[u] + edge[u][i].sec; 64 ans = max(d[v],ans); 65 q.push(v); 66 } 67 } 68 69 int mx = 0; 70 for ( int i = 1 ; i <= n ; i++) 71 { 72// cout<<"i:"<<i<<" d[i]:"<<d[i]<<endl; 73 if (d[i]>mx) 74 { 75 mx = d[i]; 76 lst = i ; 77 } 78 } 79 80} 81int main() 82{ 83 #ifndef ONLINE_JUDGE 84 freopen("code/in.txt","r",stdin); 85 #endif 86 87 int u,v,w; 88 m = 0; 89 n = 0; 90 while (scanf("%d%d%d",&u,&v,&w)!=EOF) 91 { 92 edge[u].push_back(make_pair(v,w)); 93 edge[v].push_back(make_pair(u,w)); 94 m++; 95 n = max(n,u); 96 n = max(n,v); 97 } 98 ans = inf; 99 bfs(1); 100 ans = 0; 101// cout<<"lst:"<<lst<<endl; 102 bfs(lst); 103 cout<<ans<<endl; 104 105 #ifndef ONLINE_JUDGE 106 fclose(stdin); 107 #endif 108 return 0; 109}

poj1985 题意：求树上两点的最长距离。。。也就是传说中的树的直径。。。 思路： 两遍BFS ：先任选一个起点BFS找到最长路的终点，再从终点进行BFS，则第二次BFS找到的最长路即为树的直径； 原理： 设起点为u，第一次BFS找到的终点v一定是树的直径的一个端点 证明： 1) 如果u 是直径上的点，则v显然是直径的终点(因为如果v不是的话，则必定存在另一个点w使得u到w的距离更长，则于BFS找到了v矛盾) 2) 如果u不是直径上的点，则u到v必然于树的直径相交(反证)，那么交点到v 必然就是直径的后半段了 所以v一定是直径的一个端点，所以从v进行BFS得到的一定是直径长度