1.转圈游戏:
解析部分略，快速幂就可以过
Code:
1 #include<iostream> 2 #include<fstream> 3 using namespace std; 4 ifstream fin("circle.in"); 5 ofstream fout("circle.out"); 6 long long k; 7 long long n; 8 long long result; 9 long long x; 10 long long m; 11 long long _pow(int a, int pos){ 12 if(pos == 1) return a%n; 13 long long temp = _pow(a,pos/2); 14 if(pos % 2 == 1) return ( temp * temp*a)%n; 15 return ( temp * temp )%n; 16 } 17 int main(){ 18 fin>>n>>m>>k>>x; 19 fout<<(x+m*_pow(10, k))%n; 20 return 0; 21 }
2.火柴排队
假设现在有两队火柴 a和b
a: 1 3 4 2
b: 1 2 3 5
因为它们的差的总值是一定的（化简一下，开开括号就得到了），为了使它们的差的平方的和最小，
所以a数列的第k小应该和b数列的第k小并在一起求差再求平方。
无论把a排成b，还是把b排成a都差不多，那就随便选一个，
下面又有一个问题，求什么的逆序对
将b中的元素应该在的位数写下来 1 4 2 3
如果将它排成1 2 3 4（带着原来的数一起排，绑定在一起）就意味着b数组被“排”成a数组了
所以应该是求它的逆序对（交换次数）
另外，注意，变算边取模
Code:
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<algorithm> 5 #define _next(a) ((a)&(-a)) 6 using namespace std; 7 typedef class IndexedTree{ 8 public: 9 int *list; 10 int size; 11 IndexedTree():list(NULL),size(size){} 12 IndexedTree(int size):size(size){ 13 list = new int[(const int)(size + 1)]; 14 memset(list, 0, sizeof(int) * (size + 1)); 15 } 16 void add(int index, int value){ 17 while(index <= size){ 18 list[index] += value; 19 index += (_next(index)); 20 } 21 } 22 long long getSum(int index){ 23 long long result = 0; 24 while(index > 0){ 25 result += list[index]; 26 result %= 99999997; 27 index -= (_next(index)); 28 } 29 return result; 30 } 31 }IndexedTree; 32 FILE *fin = fopen("match.in","r"); 33 FILE *fout= fopen("match.out","w"); 34 IndexedTree MyTree; 35 typedef struct mdata{ 36 int index; 37 int height; 38 }mdata; 39 mdata *a; 40 mdata *b; 41 mdata *c; 42 int n; 43 long long result = 0; 44 typedef bool boolean; 45 boolean cmpare(const mdata &a, const mdata &b){ 46 return a.height < b.height; 47 } 48 int main(){ 49 fscanf(fin,"%d",&n); 50 a = new mdata[(const int)(n + 1)]; 51 c = new mdata[(const int)(n + 1)]; 52 b = new mdata[(const int)(n + 1)]; 53 MyTree = IndexedTree(n); 54 for(int i = 1;i <= n;i++){ 55 fscanf(fin,"%d",&a[i].height); 56 a[i].index = i; 57 } 58 sort(a + 1, a + n + 1, cmpare); 59 for(int i = 1;i <= n;i++){ 60 fscanf(fin,"%d",&b[i].height); 61 b[i].index = i; 62 c[i] = b[i]; 63 } 64 sort(b + 1, b + n + 1, cmpare); 65 for(int i = 1;i <= n;i++){ 66 c[b[i].index].index = a[i].index; 67 } 68 for(int i = 1;i <= n;i++){ 69 MyTree.add(c[i].index, 1); 70 result += i - MyTree.getSum(c[i].index); 71 result %= 99999997; 72 } 73 fprintf(fout,"%ld",result); 74 return 0; 75 }
3.货车运输
60分程序:
思路就是先最大生成树，把无用的边都去掉，接着spfa
1 #include<iostream> 2 #include<queue> 3 #include<cstdio> 4 #include<cstring> 5 #include<algorithm> 6 #define _min(a,b) ((a) < (b))?(a):(b) 7 using namespace std; 8 int n,m,k; 9 FILE *fin = fopen("truck.in","r"); 10 FILE *fout= fopen("truck.out","w"); 11 typedef class Edge{ 12 public: 13 int next; 14 int end; 15 int z; 16 Edge():next(0),end(0),z(0){} 17 Edge(int next, int end, int z):next(next),end(end),z(z){} 18 }Edge; 19 int *h; 20 int *h1; 21 Edge *edge1; 22 int _now = 0; 23 typedef struct gdata{ 24 int from; 25 int end; 26 }gdata; 27 typedef bool boolean; 28 gdata g; 29 int buffer[3]; 30 void add(int from, int end, int v){ 31 edge1[++_now] = Edge(h[from], end, v); 32 h[from] = _now; 33 } 34 typedef struct Edge1{ 35 int from; 36 int end; 37 int v; 38 }Edge1; 39 int *fset; //并查集 40 int _find(int found){ 41 if(fset[found] != found) return ( fset[found] = _find(fset[found]) ); 42 return fset[found]; 43 } 44 void unit(int &a, int &b){ 45 int af = _find(a); 46 int bf = _find(b); 47 fset[bf] = af; 48 } 49 queue<int> que; 50 boolean *visited; 51 int *f; 52 Edge1 *edge; 53 int solve(){ 54 memset(visited, false, sizeof(boolean) * (n + 1)); 55 memset(f,-1, sizeof(int) * (n + 1)); 56 if(h[g.end] == 0||h[g.from] == 0) return -1; 57 f[g.from] = 1000000; 58 visited[g.from] = true; 59 que.push(g.from); 60 while(!que.empty()){ 61 int u = que.front(); 62 que.pop(); 63 visited[u] = false; 64 for(int i = h[u];i != 0;i = edge1[i].next){ 65 int eu = edge1[i].end; 66 if(f[eu] < (_min(f[u] ,edge1[i].z))){ 67 f[eu] = (_min(f[u] ,edge1[i].z)); 68 if(!visited[eu]){ 69 visited[eu] = true; 70 que.push(eu); 71 } 72 } 73 } 74 } 75 if(f[g.end] < 0) return -1; 76 return f[g.end]; 77 } 78 boolean cmpare(const Edge1& a, const Edge1& b){ 79 return a.v > b.v; 80 } 81 void init_myTree(){ 82 fset = new int[(const int)(n + 1)]; 83 sort(edge+1, edge + m * 2 + 1, cmpare); 84 for(int i = 1;i <= n; i++) fset[i] = i; 85 int _count = 0; 86 for(int i = 1;i <= m;i++){ 87 if(_count == n - 1) break; 88 if(_find(edge[i].from) != _find(edge[i].end)){ 89 add(edge[i].from, edge[i].end, edge[i].v); 90 add(edge[i].end, edge[i].from, edge[i].v); 91 unit(edge[i].from, edge[i].end); 92 _count++; 93 } 94 } 95 delete[] edge; 96 delete[] fset; 97 } 98 int main(){ 99 fscanf(fin,"%d%d",&n,&m); 100 h = new int[(const int)(n + 1)]; 101 edge = new Edge1[(const int)(m * 2 + 1)]; 102 memset(h, 0, sizeof(int) * (n + 1)); 103 visited = new boolean[(const int)(n + 1)]; 104 f = new int[(const int)(n + 1)]; 105 edge1 = new Edge[(const int)(n * 2 + 1)]; 106 for(int i = 1;i <= m;i++){ 107 fscanf(fin,"%d%d%d",&edge[i].from,&edge[i].end,&edge[i].v); 108 } 109 init_myTree(); 110 fscanf(fin,"%d",&k); 111 for(int i = 1;i <= k;i++){ 112 fscanf(fin,"%d%d",&g.from,&g.end); 113 fprintf(fout,"%d ",solve()); 114 } 115 return 0; 116 }
100分程序:
思路是这样的：
1.用并查集，把无用的边都去掉，得到几棵树
2.dfs进行初始化，注意不是只有一棵树
3.构造倍增数组，用up[i][j]表示i的第2j 个父节点是多少，dis[i][j]表示i到up[i][j]的最大载重
4.进行倍增找lca，得到答案
Code（倍增）
1 /** 2 * codevs.cn & vijos.org 3 * Problem#3287 Problem#1843 4 * Accepted Accepted 5 * Time:416ms Time:385ms 6 * Memory:2108k Memory:2472k 7 */ 8 #include<iostream> 9 #include<cstdio> 10 #include<fstream> 11 #include<cstring> 12 #include<queue> 13 #include<cctype> 14 #include<algorithm> 15 using namespace std; 16 typedef bool boolean; 17 #define INF 0xfffffff 18 #define smin(a, b) a = min(a, b) 19 #define smax(a, b) a = max(a, b) 20 template<typename T> 21 inline void readInteger(T& u){ 22 char x; 23 while(!isdigit((x = getchar()))); 24 for(u = x - '0'; isdigit((x = getchar())); u = (u << 1) + (u << 3) + x - '0'); 25 ungetc(x, stdin); 26 } 27 ///map template starts 28 typedef class Edge{ 29 public: 30 int end; 31 int next; 32 int w; 33 Edge(const int end = 0, const int next = 0, const int w = 0):end(end), next(next), w(w){} 34 }Edge; 35 typedef class MapManager{ 36 public: 37 int ce; 38 int *h; 39 Edge *edge; 40 MapManager(){} 41 MapManager(int limit, int points):ce(0){ 42 h = new int[(const int)(points + 1)]; 43 edge = new Edge[(const int)(limit + 1)]; 44 memset(h, 0, sizeof(int) * (points + 1)); 45 } 46 inline void addEdge(int from, int end, int w){ 47 edge[++ce] = Edge(end, h[from], w); 48 h[from] = ce; 49 } 50 inline void addDoubleEdge(int from, int end, int w){ 51 addEdge(from, end, w); 52 addEdge(end, from, w); 53 } 54 }MapManager; 55 ///map template ends 56 typedef class union_found{ 57 public: 58 int *f; 59 union_found():f(NULL) {} 60 union_found(int points) { 61 f = new int[(const int)(points + 1)]; 62 for(int i = 0; i <= points; i++) 63 f[i] = i; 64 } 65 int find(int x) { 66 if(f[x] != x) return f[x] = find(f[x]); 67 return f[x]; 68 } 69 void unit(int fa, int so) { 70 int ffa = find(fa); 71 int fso = find(so); 72 f[fso] = ffa; 73 } 74 boolean connected(int a, int b) { 75 return find(a) == find(b); 76 } 77 }union_found; 78 79 template<typename T>class Matrix{ 80 public: 81 T *p; 82 int lines; 83 int rows; 84 Matrix():p(NULL){ } 85 Matrix(int lines, int rows):lines(lines), rows(rows){ 86 p = new T[(lines * rows)]; 87 } 88 T* operator [](int pos){ 89 return (p + pos * lines); 90 } 91 }; 92 93 #define m_begin(g, i) (g).h[(i)] 94 #define m_end(g, i) (g).edge[(i)].end 95 #define m_next(g, i) (g).edge[(i)].next 96 #define m_w(g, i) (g).edge[(i)].w 97 98 typedef class _Edge{ 99 public: 100 int from; 101 int end; 102 int w; 103 _Edge():from(0), end(0), w(0){} 104 }_Edge; 105 106 int n; 107 int m; 108 _Edge* es; 109 inline void init(){ 110 readInteger(n); 111 readInteger(m); 112 es = new _Edge[(const int)(m + 1)]; 113 for(int i = 1; i <= m; i++){ 114 readInteger(es[i].from); 115 readInteger(es[i].end); 116 readInteger(es[i].w); 117 } 118 } 119 120 boolean cmpare(const _Edge& a, const _Edge& b){ 121 return a.w > b.w; 122 } 123 124 MapManager g; 125 union_found uf; 126 inline void init_map(){ 127 g = MapManager(n * 2, n); 128 uf = union_found(n); 129 sort(es + 1, es + m + 1, cmpare); 130 int finished = 0; 131 for(int i = 1; i <= m; i++){ 132 if(!uf.connected(es[i].from, es[i].end)){ 133 uf.unit(es[i].from, es[i].end); 134 g.addDoubleEdge(es[i].from, es[i].end, es[i].w); 135 finished++; 136 } 137 if(finished == n - 1) break; 138 } 139 delete[] es; 140 } 141 142 int* depth; 143 boolean* visited; 144 int* fa; 145 int* df; 146 void dfs(int node, int last, int dep, int dis){ 147 visited[node] = true; 148 fa[node] = last; 149 df[node] = dis; 150 depth[node] = dep; 151 for(int i = m_begin(g, node); i != 0; i = m_next(g, i)){ 152 int& e = m_end(g, i); 153 if(visited[e]) continue; 154 dfs(e, node, dep + 1, m_w(g, i)); 155 } 156 } 157 158 inline void init_dfs(){ 159 depth = new int[(const int)(n + 1)]; 160 visited = new boolean[(const int)(n + 1)]; 161 fa = new int[(const int)(n + 1)]; 162 df = new int[(const int)(n + 1)]; 163 memset(visited, false, sizeof(boolean) * (n + 1)); 164 for(int i = 1; i <= n; i++){ 165 if(!visited[i]) 166 dfs(i, 0, 1, 0); 167 } 168 } 169 170 Matrix<int> up; 171 Matrix<int> dis; 172 inline void init_bz(){ 173 up = Matrix<int>(16, n + 1); 174 dis = Matrix<int>(16, n + 1); 175 memset(up.p, 0, sizeof(int) * 16 * (n + 1)); 176 memset(dis.p, 0x7f, sizeof(int) * 16 * (n + 1)); 177 for(int i = 1; i <= n; i++){ 178 up[i][0] = fa[i]; 179 dis[i][0] = df[i]; 180 } 181 for(int j = 1; j <= 14; j++){ 182 for(int i = 1; i <= n; i++){ 183 up[i][j] = up[up[i][j - 1]][j - 1]; 184 dis[i][j] = min(dis[i][j - 1], dis[up[i][j - 1]][j - 1]); 185 } 186 } 187 } 188 189 int lca(int a, int b){ 190 if(!uf.connected(a, b)) return -1; 191 int result = 0xfffffff; 192 if(depth[a] < depth[b]) swap(a, b); 193 int c = depth[a] - depth[b]; 194 for(int i = 0; i <= 14; i++){ 195 if(c & (1 << i)){ 196 smin(result, dis[a][i]); 197 a = up[a][i]; 198 } 199 } 200 if(a == b) return result; 201 for(int i = 14; i >= 0; i--){ 202 if(up[a][i] != up[b][i]){ 203 smin(result, dis[a][i]); 204 smin(result, dis[b][i]); 205 a = up[a][i]; 206 b = up[b][i]; 207 } 208 } 209 smin(result, dis[a][0]); 210 smin(result, dis[b][0]); 211 return result; 212 } 213 214 int q; 215 inline void solve(){ 216 readInteger(q); 217 for(int i = 1, a, b; i <= q; i++){ 218 readInteger(a); 219 readInteger(b); 220 int l = lca(a, b); 221 printf("%d ", l); 222 } 223 } 224 225 ///Main Funtion 226 int main(int argc, char* argv[]){ 227 init(); 228 init_map(); 229 init_dfs(); 230 init_bz(); 231 solve(); 232 return 0; 233 }
（代码有点长，还是比较便于理解）