250pts PeriodicJumping
题意：从起点开始，每次按找数组jump给定的长度，即jump[0], jump[1], jump[2].....jump[n-1], 向各个方向跳，跳完后从从头开始,问最后能否达到(x,0).
限制：|x| <= (int)1e9，n <= 50, 1 <= len[i] <= (int)1e9.
分析：
题解分析的很详细，每次跳完后可达的范围离原点的距离总是一个区间[a,b]，考虑下一次跳的长度r之后，可达的范围，
(1). r < a, a = a-r;
(2). a <= r <= b, a = 0;
(3). r > b , a = r-b;
而b不论r取值如何总是变为b+r.一个周期内跳跃总长度为S，那么一开始连续跳跃两个周期，看做两次跳跃长度都是S, 可达范围是[0,2S]，求出在到达x之前最多跳跃多少个2S,剩下的直接模拟，直到x在所到达的范围内即可.
代码：
#include <bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define esp 1e-14
#define lson l, m, rt<<1
#define rson m+1, r, rt<<1|1
#define sz(x) ((int)((x).size()))
#define pf(x) ((x)*(x))
#define pb push_back
#define pi acos(-1.0)
#define in freopen("solve_in.txt", "r", stdin);
#define bug(x) printf("Line : %u >>>>>>\n", (x));
#define TL cerr << "Time elapsed: " << (double)clock() / CLOCKS_PER_SEC * 1000 << " ms" << endl;
#define inf 0x0f0f0f0f
using namespace std;
typedef long long LL;
typedef unsigned US;
typedef pair<int, int> PII;
typedef map<PII, int> MPS;
typedef MPS::iterator IT;
vector<int> len; class PeriodicJumping {
public:
int minimalTime(int x, vector <int> jump) {
LL tmp = ;
for(int y: jump)
tmp += *y;
x = abs(x);
if(x == ) return ;
int n = jump.size();
int ans = 1LL*((x-)/tmp)*n*;
LL a = , b = (x-)/tmp*tmp; while() {
for(int y:jump) { if(a > y) {
a = a-y;
} else if(y <= b) {
a = ;
} else {
a = y-b;
}
b+=y;
ans++;
if(x >= a && x <= b)
break;
}
if(x >= a && x <= b)
break;
}
return ans;
}
};
500pts DoubleTree
题意： 两棵树，共n个结点，对应编号的结点权值相同，可正可负，求从中选出一个结点结合，使得选出的集合在两棵树上都是一棵子树，即都联通，权值要求最大.
限制：2 <= n <= 50, |权值 | <= 1000.
分析：
选出任意个结点构成一棵子树的条件时，这些结点间相互可达，也就是都能到达同一个结点，因为树中路径唯一，不妨把这个点当做根结点。
依次考虑每个结点做根时，考虑剩下的结点选中时的情形，两棵树中这个结点到根路径上所有结点都要选中，这样又会引入一些选中的结点，总结起来就是，所有选中的结点在两棵树中到根的路径上其他结点都要选中。
具体建图时，分别对两棵树dfs，每个节点到其父节点连边，当要选中这个结点时，必须从这个结点出发，将所有能达的点全部选中，同时使得权值和最大，问题就转化为最大权闭合图了。这个可以参考胡伯涛的论文。
代码：
#include <bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define esp 1e-14
#define lson l, m, rt<<1
#define rson m+1, r, rt<<1|1
#define sz(x) ((int)((x).size()))
#define pf(x) ((x)*(x))
#define pb push_back
#define pi acos(-1.0)
#define in freopen("solve_in.txt", "r", stdin);
#define bug(x) printf("Line : %u >>>>>>\n", (x));
#define TL cerr << "Time elapsed: " << (double)clock() / CLOCKS_PER_SEC * 1000 << " ms" << endl;
#define inf 0x0f0f0f0f
using namespace std;
typedef long long LL;
typedef unsigned US;
typedef pair<int, int> PII;
typedef map<PII, int> MPS;
typedef MPS::iterator IT;
const int maxn = ; int src, sink; struct Edge {
int u, v, c;
Edge() {}
Edge(int u, int v, int c):u(u), v(v), c(c) {}
}; struct MaxFlow {
int n, m;
vector<int> G[maxn];
vector<Edge> edges;
int Now[maxn], Dfn[maxn]; void init(int n) {
this->n = n;
for(int i = ; i < n; i++)
G[i].clear();
edges.clear();
}
void add(int u, int v, int c) {
// cout << u << ' ' << v << endl;
edges.pb(Edge(u, v, c));
edges.pb(Edge(v, u, ));
m = edges.size();
G[u].pb(m-);
G[v].pb(m-);
}
int ISAP(int s, int flow) {
if(s == sink) return flow;
int now = , vary, tab = n, v;
for(int i = ; i < (int)G[s].size(); i++) {
Edge &e = edges[G[s][i]];
if(e.c > ) {
if(Dfn[s] == Dfn[v = e.v] + )
vary = ISAP(v, min(flow-now, e.c)), now += vary,
e.c -= vary, edges[G[s][i]^].c += vary;
if(Dfn[src] == n) return now;
if(e.c > ) tab = min(tab, Dfn[v]);
if(flow == now) break;
}
}
if(now == ) {
if(--Now[Dfn[s]] == )
Dfn[src] = n;
Now[Dfn[s] = tab+]++;
} return now;
}
int getAns() {
memset(Now, , sizeof Now);
memset(Dfn, , sizeof Dfn);
Now[] = n;
int ans = ;
while(Dfn[src] < n)
ans += ISAP(src, inf);
return ans;
}
} solver; class DoubleTree {
public:
int n;
int g[maxn][maxn];
vector<int> tree[][maxn];
int rt;
void add(int id, int u, int v) { tree[id][u].pb(v);
tree[id][v].pb(u);
}
void dfs(int id, int u, int fa) {
if(fa != - && fa != rt) {
g[u][fa] = ;
}
for(int i = ; i < sz(tree[id][u]); i++) {
int v = tree[id][u][i];
if(v == fa) continue;
dfs(id, v, u);
}
}
int maximalScore(vector <int> a, vector <int> b, vector <int> c, vector <int> d, vector <int> s) {
n = sz(a)+;
int mx, z; for(int i = ; i < n-; i++) {
add(, a[i], b[i]);
add(, c[i], d[i]);
}
int ans = ;
src = n, sink = n+; for(int i = ; i < n; i++ ){
mx = z = ;
memset(g, , sizeof g); for(int j = ; j < n; j++) {
mx += (i != j ? abs(s[j]) : );
z += (i != j && s[j] > ? s[j] : );
}
mx+=;
rt = i;
dfs(, i, -);
dfs(, i, -);
//for(int ii = 0; ii < n; ii++, puts("")) for(int j = 0; j < n; j++)
// cout << g[ii][j] << ' ';
solver.init(n+);
for(int u = ; u < n; u++) {
if(u != rt) {
if(s[u] > ) solver.add(src, u, s[u]);
else solver.add(u, sink, -s[u]);
}
for(int v = ; v < n; v++) {
if(!g[u][v]) continue;
solver.add(u, v, mx);
}
} ans = max(ans, z-solver.getAns()+s[i]);
}
return ans;
}
};
int main(){
return ;
} // Powered by FileEdit
1000pts GCDLCM
题意：现有n个正整数，给出4个数组，描述x[A[i]],x[B[i]],的LCM或GCD为C[i],问能否找到这样一组正整数。
n <= 200, m <= 200.
分析：GCD要求A[i]，B[i]的相应质因子p的个数最小值 = m(m为C[i]包含的质因子p的个数), 即min(A[i], B[i]) = m。即A[i] = m && B[i] >= m 或 B[i] = m && A[i] >= m.LCM则是将min改为max.
这样对C[]分解质因数后，单独考虑其中每个质因子的问题，对A[i], B[i], C[i]分析可得到一系列条件, 将A[i] = m && B[i] >= m , B[i] = m && A[i] >= m 分别看成X,Y表达式，原来的GCD[i]或LCM[i]问题变成了，X[i]或Y[i]的表达式，注意对于每个i，X[i]和Y[i]中至少有一个成立，当然可以有两个同时成立，然后便是X[i],Y[i],X[j],Y[j]中必然会存在矛盾，处理一下，最后用2-sat解决.
代码：
#include <bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define esp 1e-14
#define lson l, m, rt<<1
#define rson m+1, r, rt<<1|1
#define sz(x) ((int)((x).size()))
#define pf(x) ((x)*(x))
#define pb push_back
#define pi acos(-1.0)
#define in freopen("solve_in.txt", "r", stdin);
#define bug(x) printf("Line : %u >>>>>>\n", (x));
#define TL cerr << "Time elapsed: " << (double)clock() / CLOCKS_PER_SEC * 1000 << " ms" << endl;
#define inf 0x0f0f0f0f
using namespace std;
typedef long long LL;
typedef unsigned US;
typedef pair<int, int> PII;
typedef map<PII, int> MPS;
typedef MPS::iterator IT; const int maxn = + ;
//2-sat
struct twoSat {
int n;
int mark[maxn], S[maxn];
vector<list<int> > g;
int c;
void init(int n) {
this->n = n;
g.resize(n*);
for(auto &x:g)
x.clear();
memset(mark, , sizeof mark);
}
void add(int x, int y) {
g[x].pb(y);
}
bool dfs(int x) {
if(mark[x^]) return false;
if(mark[x]) return true;
S[c++] = x;
mark[x] = ;
for(int y: g[x]) {
if(!dfs(y)) return false;
}
return true;
}
bool solve() {
for(int i = ; i < n*; i += ) {
if(!mark[i] && !mark[i+]) {
c = ;
if(!dfs(i)) {
while(c) mark[S[--c]] = ;
if(!dfs(i+)) return false;
}
}
}
return true;
}
} solver;
struct State {
int a, b, c, d;
State() {}
State(int a, int b, int c, int d):a(a), b(b), c(c), d(d) {}
};
vector<State> sta; class GCDLCM {
public:
set<int> div;//relevant primes
vector<PII> factor[ + ];
//get prime factor of n, store in vec
void getPrimeFac(int n) {
for(int i = ; i <= n/i; i++) { if(n%i == ) {
while(n%i == ) {
n /= i;
}
div.insert(i);
}
}
if(n != ) {
div.insert(n);
}
}
bool contradiction(int x, int y) {
int a0 = sta[x].a, b0 = sta[x].b, c0 = sta[x].c, d0 = sta[x].d;
int a1 = sta[y].a, b1 = sta[y].b, c1 = sta[y].c, d1 = sta[y].d;
if(a0 == a1 && c0 != c1) {
return true;
}
if(a0 == b1 && ((d1 && c0 < c1) || (!d1 && c0 > c1))) {
return true;
}
if(b0 == a1 && ((d0 && c1 < c0) || (!d0 && c1 > c0))) {
return true;
}
if(b0 == b1 && ((d0 > d1 && c0 > c1) || (d0 < d1 && c0 < c1))) {
return true;
}
return false;
}
string possible(int n, string type, vector <int> A, vector <int> B, vector <int> C) {
int m = sz(A);
for(int i = ; i < m; i++)
getPrimeFac(C[i]);
for(int u: div) {
sta.clear();
for(int j = ; j < m; j++) {
int r = ;
int y = C[j];
while(y%u == ) {
r++;
y /= u;
}
sta.pb(State(A[j], B[j], r, type[j] == 'G'));
sta.pb(State(B[j], A[j], r, type[j] == 'G'));
} solver.init(sz(sta));
//add edge x->~y, ~y->x,etc.
for(int i = ; i < sz(sta); i += ) {
//solver.add(i<<1, (i+1)<<1|1);
solver.add((i+)<<|, i<<);
//solver.add((i+1)<<1, i<<1|1);
solver.add(i<<|, (i+)<<);
}
for(int i = ; i < sz(sta); i++) for(int j = ; j < sz(sta); j++) {
if(contradiction(i, j)) {
solver.add(i<<, j<<|);
solver.add(j<<, i<<|);
}
}
if(!solver.solve()) return "Solution does not exist";
}
return "Solution exists";
}
};
学习了一下list，和vector最大区别便是不支持随机存取，可以看做是STL中的双向链表，支持首尾插入，删除。