1.转圈游戏:
解析部分略，快速幂就可以过
Code:
#include<iostream>
#include<fstream>
using namespace std;
ifstream fin("circle.in");
ofstream fout("circle.out");
long long k;
long long n;
long long result;
long long x;
long long m;
long long _pow(int a, int pos){
if(pos == ) return a%n;
long long temp = _pow(a,pos/);
if(pos % == ) return ( temp * temp*a)%n;
return ( temp * temp )%n;
}
int main(){
fin>>n>>m>>k>>x;
fout<<(x+m*_pow(, k))%n;
return ;
}
转圈游戏
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:
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define _next(a) ((a)&(-a))
using namespace std;
typedef class IndexedTree{
public:
int *list;
int size;
IndexedTree():list(NULL),size(size){}
IndexedTree(int size):size(size){
list = new int[(const int)(size + )];
memset(list, , sizeof(int) * (size + ));
}
void add(int index, int value){
while(index <= size){
list[index] += value;
index += (_next(index));
}
}
long long getSum(int index){
long long result = ;
while(index > ){
result += list[index];
result %= ;
index -= (_next(index));
}
return result;
}
}IndexedTree;
FILE *fin = fopen("match.in","r");
FILE *fout= fopen("match.out","w");
IndexedTree MyTree;
typedef struct mdata{
int index;
int height;
}mdata;
mdata *a;
mdata *b;
mdata *c;
int n;
long long result = ;
typedef bool boolean;
boolean cmpare(const mdata &a, const mdata &b){
return a.height < b.height;
}
int main(){
fscanf(fin,"%d",&n);
a = new mdata[(const int)(n + )];
c = new mdata[(const int)(n + )];
b = new mdata[(const int)(n + )];
MyTree = IndexedTree(n);
for(int i = ;i <= n;i++){
fscanf(fin,"%d",&a[i].height);
a[i].index = i;
}
sort(a + , a + n + , cmpare);
for(int i = ;i <= n;i++){
fscanf(fin,"%d",&b[i].height);
b[i].index = i;
c[i] = b[i];
}
sort(b + , b + n + , cmpare);
for(int i = ;i <= n;i++){
c[b[i].index].index = a[i].index;
}
for(int i = ;i <= n;i++){
MyTree.add(c[i].index, );
result += i - MyTree.getSum(c[i].index);
result %= ;
}
fprintf(fout,"%ld",result);
return ;
}
火柴排队
3.货车运输
60分程序:
思路就是先最大生成树，把无用的边都去掉，接着spfa
#include<iostream>
#include<queue>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define _min(a,b) ((a) < (b))?(a):(b)
using namespace std;
int n,m,k;
FILE *fin = fopen("truck.in","r");
FILE *fout= fopen("truck.out","w");
typedef class Edge{
public:
int next;
int end;
int z;
Edge():next(),end(),z(){}
Edge(int next, int end, int z):next(next),end(end),z(z){}
}Edge;
int *h;
int *h1;
Edge *edge1;
int _now = ;
typedef struct gdata{
int from;
int end;
}gdata;
typedef bool boolean;
gdata g;
int buffer[];
void add(int from, int end, int v){
edge1[++_now] = Edge(h[from], end, v);
h[from] = _now;
}
typedef struct Edge1{
int from;
int end;
int v;
}Edge1;
int *fset; //并查集
int _find(int found){
if(fset[found] != found) return ( fset[found] = _find(fset[found]) );
return fset[found];
}
void unit(int &a, int &b){
int af = _find(a);
int bf = _find(b);
fset[bf] = af;
}
queue<int> que;
boolean *visited;
int *f;
Edge1 *edge;
int solve(){
memset(visited, false, sizeof(boolean) * (n + ));
memset(f,-, sizeof(int) * (n + ));
if(h[g.end] == ||h[g.from] == ) return -;
f[g.from] = ;
visited[g.from] = true;
que.push(g.from);
while(!que.empty()){
int u = que.front();
que.pop();
visited[u] = false;
for(int i = h[u];i != ;i = edge1[i].next){
int eu = edge1[i].end;
if(f[eu] < (_min(f[u] ,edge1[i].z))){
f[eu] = (_min(f[u] ,edge1[i].z));
if(!visited[eu]){
visited[eu] = true;
que.push(eu);
}
}
}
}
if(f[g.end] < ) return -;
return f[g.end];
}
boolean cmpare(const Edge1& a, const Edge1& b){
return a.v > b.v;
}
void init_myTree(){
fset = new int[(const int)(n + )];
sort(edge+, edge + m * + , cmpare);
for(int i = ;i <= n; i++) fset[i] = i;
int _count = ;
for(int i = ;i <= m;i++){
if(_count == n - ) break;
if(_find(edge[i].from) != _find(edge[i].end)){
add(edge[i].from, edge[i].end, edge[i].v);
add(edge[i].end, edge[i].from, edge[i].v);
unit(edge[i].from, edge[i].end);
_count++;
}
}
delete[] edge;
delete[] fset;
}
int main(){
fscanf(fin,"%d%d",&n,&m);
h = new int[(const int)(n + )];
edge = new Edge1[(const int)(m * + )];
memset(h, , sizeof(int) * (n + ));
visited = new boolean[(const int)(n + )];
f = new int[(const int)(n + )];
edge1 = new Edge[(const int)(n * + )];
for(int i = ;i <= m;i++){
fscanf(fin,"%d%d%d",&edge[i].from,&edge[i].end,&edge[i].v);
}
init_myTree();
fscanf(fin,"%d",&k);
for(int i = ;i <= k;i++){
fscanf(fin,"%d%d",&g.from,&g.end);
fprintf(fout,"%d\n",solve());
}
return ;
}
骗分版
100分程序:
思路是这样的：
1.用并查集，把无用的边都去掉，得到几棵树
2.dfs进行初始化，注意不是只有一棵树
3.构造倍增数组，用up[i][j]表示i的第2j 个父节点是多少，dis[i][j]表示i到up[i][j]的最大载重
4.进行倍增找lca，得到答案
Code（倍增）
/**
* codevs.cn & vijos.org
* Problem#3287 Problem#1843
* Accepted Accepted
* Time:416ms Time:385ms
* Memory:2108k Memory:2472k
*/
#include<iostream>
#include<cstdio>
#include<fstream>
#include<cstring>
#include<queue>
#include<cctype>
#include<algorithm>
using namespace std;
typedef bool boolean;
#define INF 0xfffffff
#define smin(a, b) a = min(a, b)
#define smax(a, b) a = max(a, b)
template<typename T>
inline void readInteger(T& u){
char x;
while(!isdigit((x = getchar())));
for(u = x - ''; isdigit((x = getchar())); u = (u << ) + (u << ) + x - '');
ungetc(x, stdin);
}
///map template starts
typedef class Edge{
public:
int end;
int next;
int w;
Edge(const int end = , const int next = , const int w = ):end(end), next(next), w(w){}
}Edge;
typedef class MapManager{
public:
int ce;
int *h;
Edge *edge;
MapManager(){}
MapManager(int limit, int points):ce(){
h = new int[(const int)(points + )];
edge = new Edge[(const int)(limit + )];
memset(h, , sizeof(int) * (points + ));
}
inline void addEdge(int from, int end, int w){
edge[++ce] = Edge(end, h[from], w);
h[from] = ce;
}
inline void addDoubleEdge(int from, int end, int w){
addEdge(from, end, w);
addEdge(end, from, w);
}
}MapManager;
///map template ends
typedef class union_found{
public:
int *f;
union_found():f(NULL) {}
union_found(int points) {
f = new int[(const int)(points + )];
for(int i = ; i <= points; i++)
f[i] = i;
}
int find(int x) {
if(f[x] != x) return f[x] = find(f[x]);
return f[x];
}
void unit(int fa, int so) {
int ffa = find(fa);
int fso = find(so);
f[fso] = ffa;
}
boolean connected(int a, int b) {
return find(a) == find(b);
}
}union_found; template<typename T>class Matrix{
public:
T *p;
int lines;
int rows;
Matrix():p(NULL){ }
Matrix(int lines, int rows):lines(lines), rows(rows){
p = new T[(lines * rows)];
}
T* operator [](int pos){
return (p + pos * lines);
}
}; #define m_begin(g, i) (g).h[(i)]
#define m_end(g, i) (g).edge[(i)].end
#define m_next(g, i) (g).edge[(i)].next
#define m_w(g, i) (g).edge[(i)].w typedef class _Edge{
public:
int from;
int end;
int w;
_Edge():from(), end(), w(){}
}_Edge; int n;
int m;
_Edge* es;
inline void init(){
readInteger(n);
readInteger(m);
es = new _Edge[(const int)(m + )];
for(int i = ; i <= m; i++){
readInteger(es[i].from);
readInteger(es[i].end);
readInteger(es[i].w);
}
} boolean cmpare(const _Edge& a, const _Edge& b){
return a.w > b.w;
} MapManager g;
union_found uf;
inline void init_map(){
g = MapManager(n * , n);
uf = union_found(n);
sort(es + , es + m + , cmpare);
int finished = ;
for(int i = ; i <= m; i++){
if(!uf.connected(es[i].from, es[i].end)){
uf.unit(es[i].from, es[i].end);
g.addDoubleEdge(es[i].from, es[i].end, es[i].w);
finished++;
}
if(finished == n - ) break;
}
delete[] es;
} int* depth;
boolean* visited;
int* fa;
int* df;
void dfs(int node, int last, int dep, int dis){
visited[node] = true;
fa[node] = last;
df[node] = dis;
depth[node] = dep;
for(int i = m_begin(g, node); i != ; i = m_next(g, i)){
int& e = m_end(g, i);
if(visited[e]) continue;
dfs(e, node, dep + , m_w(g, i));
}
} inline void init_dfs(){
depth = new int[(const int)(n + )];
visited = new boolean[(const int)(n + )];
fa = new int[(const int)(n + )];
df = new int[(const int)(n + )];
memset(visited, false, sizeof(boolean) * (n + ));
for(int i = ; i <= n; i++){
if(!visited[i])
dfs(i, , , );
}
} Matrix<int> up;
Matrix<int> dis;
inline void init_bz(){
up = Matrix<int>(, n + );
dis = Matrix<int>(, n + );
memset(up.p, , sizeof(int) * * (n + ));
memset(dis.p, 0x7f, sizeof(int) * * (n + ));
for(int i = ; i <= n; i++){
up[i][] = fa[i];
dis[i][] = df[i];
}
for(int j = ; j <= ; j++){
for(int i = ; i <= n; i++){
up[i][j] = up[up[i][j - ]][j - ];
dis[i][j] = min(dis[i][j - ], dis[up[i][j - ]][j - ]);
}
}
} int lca(int a, int b){
if(!uf.connected(a, b)) return -;
int result = 0xfffffff;
if(depth[a] < depth[b]) swap(a, b);
int c = depth[a] - depth[b];
for(int i = ; i <= ; i++){
if(c & ( << i)){
smin(result, dis[a][i]);
a = up[a][i];
}
}
if(a == b) return result;
for(int i = ; i >= ; i--){
if(up[a][i] != up[b][i]){
smin(result, dis[a][i]);
smin(result, dis[b][i]);
a = up[a][i];
b = up[b][i];
}
}
smin(result, dis[a][]);
smin(result, dis[b][]);
return result;
} int q;
inline void solve(){
readInteger(q);
for(int i = , a, b; i <= q; i++){
readInteger(a);
readInteger(b);
int l = lca(a, b);
printf("%d\n", l);
}
} ///Main Funtion
int main(int argc, char* argv[]){
init();
init_map();
init_dfs();
init_bz();
solve();
return ;
}
（代码有点长，还是比较便于理解）