TopCoder SRM 633div1

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在所到达的范围内即可.

代码：

 1 #include <bits/stdc++.h>
 2 #define pb push_back
 3 #define mp make_pair
 4 #define esp 1e-14
 5 #define lson   l, m, rt<<1
 6 #define rson   m+1, r, rt<<1|1
 7 #define sz(x) ((int)((x).size()))
 8 #define pf(x) ((x)*(x))
 9 #define pb push_back
10 #define pi acos(-1.0)
11 #define in freopen("solve_in.txt", "r", stdin);
12 #define bug(x) printf("Line : %u >>>>>>
", (x));
13 #define TL cerr << "Time elapsed: " << (double)clock() / CLOCKS_PER_SEC * 1000 << " ms" << endl;
14 #define inf 0x0f0f0f0f
15 using namespace std;
16 typedef long long LL;
17 typedef unsigned US;
18 typedef pair<int, int> PII;
19 typedef map<PII, int> MPS;
20 typedef MPS::iterator IT;
21 vector<int> len;
22 
23 class PeriodicJumping {
24 public:
25     int minimalTime(int x, vector <int> jump) {
26         LL tmp = 0;
27         for(int y: jump)
28             tmp += 2*y;
29         x = abs(x);
30         if(x == 0) return 0;
31         int n = jump.size();
32         int ans = 1LL*((x-1)/tmp)*n*2;
33        LL a = 0, b = (x-1)/tmp*tmp;
34         
35         while(1) {
36             for(int y:jump) {
37                 
38                 if(a > y) {
39                     a = a-y;
40                 } else if(y <= b) {
41                     a = 0;
42                 } else {
43                     a = y-b;
44                 }
45                 b+=y;
46                 ans++;
47                 if(x >= a && x <= b)
48                     break;
49             }
50             if(x >= a && x <= b)
51                 break;
52         }
53         return ans;
54     }
55 };

View Code

500pts DoubleTree

题意：两棵树，共n个结点，对应编号的结点权值相同，可正可负，求从中选出一个结点结合，使得选出的集合在两棵树上都是一棵子树，即都联通，权值要求最大.

限制：2 <= n <= 50, |权值 | <= 1000.

分析：

选出任意个结点构成一棵子树的条件时，这些结点间相互可达，也就是都能到达同一个结点，因为树中路径唯一，不妨把这个点当做根结点。

依次考虑每个结点做根时，考虑剩下的结点选中时的情形，两棵树中这个结点到根路径上所有结点都要选中，这样又会引入一些选中的结点，总结起来就是，所有选中的结点在两棵树中到根的路径上其他结点都要选中。

具体建图时，分别对两棵树dfs，每个节点到其父节点连边，当要选中这个结点时，必须从这个结点出发，将所有能达的点全部选中，同时使得权值和最大，问题就转化为最大权闭合图了。这个可以参考胡伯涛的论文。

代码：

  1 #include <bits/stdc++.h>
  2 #define pb push_back
  3 #define mp make_pair
  4 #define esp 1e-14
  5 #define lson   l, m, rt<<1
  6 #define rson   m+1, r, rt<<1|1
  7 #define sz(x) ((int)((x).size()))
  8 #define pf(x) ((x)*(x))
  9 #define pb push_back
 10 #define pi acos(-1.0)
 11 #define in freopen("solve_in.txt", "r", stdin);
 12 #define bug(x) printf("Line : %u >>>>>>
", (x));
 13 #define TL cerr << "Time elapsed: " << (double)clock() / CLOCKS_PER_SEC * 1000 << " ms" << endl;
 14 #define inf 0x0f0f0f0f
 15 using namespace std;
 16 typedef long long LL;
 17 typedef unsigned US;
 18 typedef pair<int, int> PII;
 19 typedef map<PII, int> MPS;
 20 typedef MPS::iterator IT;
 21 const int maxn = 55;
 22 
 23 int src, sink;
 24 
 25 struct Edge {
 26     int u, v, c;
 27     Edge() {}
 28     Edge(int u, int v, int c):u(u), v(v), c(c) {}
 29 };
 30 
 31 struct MaxFlow {
 32     int n, m;
 33     vector<int> G[maxn];
 34     vector<Edge> edges;
 35     int Now[maxn], Dfn[maxn];
 36 
 37     void init(int n) {
 38         this->n = n;
 39         for(int i = 0; i < n; i++)
 40             G[i].clear();
 41         edges.clear();
 42     }
 43     void add(int u, int v, int c) {
 44    // cout << u << ' ' << v << endl;
 45         edges.pb(Edge(u, v, c));
 46         edges.pb(Edge(v, u, 0));
 47         m = edges.size();
 48         G[u].pb(m-2);
 49         G[v].pb(m-1);
 50     }
 51     int ISAP(int s, int flow) {
 52         if(s == sink) return flow;
 53         int now = 0, vary, tab = n, v;
 54         for(int i = 0; i < (int)G[s].size(); i++) {
 55             Edge &e = edges[G[s][i]];
 56             if(e.c > 0) {
 57                 if(Dfn[s] == Dfn[v = e.v] + 1)
 58                     vary = ISAP(v, min(flow-now, e.c)), now += vary,
 59                             e.c -= vary, edges[G[s][i]^1].c += vary;
 60                 if(Dfn[src] == n) return now;
 61                 if(e.c > 0) tab = min(tab, Dfn[v]);
 62                 if(flow == now) break;
 63             }
 64           }
 65             if(now == 0) {
 66                 if(--Now[Dfn[s]] == 0)
 67                     Dfn[src] = n;
 68                 Now[Dfn[s] = tab+1]++;
 69             }
 70 
 71         return now;
 72     }
 73     int getAns() {
 74         memset(Now, 0, sizeof Now);
 75         memset(Dfn, 0, sizeof Dfn);
 76         Now[0] = n;
 77         int ans = 0;
 78         while(Dfn[src] < n)
 79             ans += ISAP(src, inf);
 80         return ans;
 81     }
 82 } solver;
 83 
 84 class DoubleTree {
 85 public:
 86     int n;
 87     int g[maxn][maxn];
 88     vector<int> tree[2][maxn];
 89     int rt;
 90     void add(int id, int u, int v) {
 91 
 92         tree[id][u].pb(v);
 93         tree[id][v].pb(u);
 94     }
 95     void dfs(int id, int u, int fa) {
 96         if(fa != -1 && fa != rt) {
 97             g[u][fa] = 1;
 98         }
 99         for(int i = 0; i < sz(tree[id][u]); i++) {
100             int v = tree[id][u][i];
101             if(v == fa) continue;
102             dfs(id, v, u);
103         }
104     }
105     int maximalScore(vector <int> a, vector <int> b, vector <int> c, vector <int> d, vector <int> s) {
106         n = sz(a)+1;
107         int mx, z;
108 
109         for(int i = 0; i < n-1; i++) {
110             add(0, a[i], b[i]);
111             add(1, c[i], d[i]);
112         }
113         int ans = 0;
114         src = n, sink = n+1;
115 
116         for(int i = 0; i < n; i++ ){
117             mx = z = 0;
118             memset(g, 0, sizeof g);
119 
120             for(int j = 0; j < n; j++) {
121                 mx += (i != j ? abs(s[j]) : 0);
122                 z += (i != j && s[j] > 0 ? s[j] : 0);
123             }
124             mx+=10;
125             rt = i;
126             dfs(0, i, -1);
127             dfs(1, i, -1);
128              //for(int ii = 0; ii < n; ii++, puts("")) for(int j = 0; j < n; j++)
129          //  cout << g[ii][j] << ' ';
130             solver.init(n+2);
131             for(int u = 0; u < n; u++) {
132                 if(u != rt) {
133                     if(s[u] > 0) solver.add(src, u, s[u]);
134                     else solver.add(u, sink, -s[u]);
135                 }
136                 for(int v = 0; v < n; v++) {
137                     if(!g[u][v]) continue;
138                     solver.add(u, v, mx);
139                 }
140             }
141 
142             ans = max(ans, z-solver.getAns()+s[i]);
143         }
144         return ans;
145     }
146 };
147 int main(){
148     return 0;
149 }
150 
151 
152 // Powered by FileEdit

View Code

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 >>>>>>
", (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 = 800 + 10;
//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*2);
        for(auto &x:g)
            x.clear();
        memset(mark, 0, sizeof mark);
    }
    void add(int x, int y) {
        g[x].pb(y);
    }
    bool dfs(int x) {
        if(mark[x^1]) return false;
        if(mark[x]) return true;
        S[c++] = x;
        mark[x] = 1;
        for(int y: g[x]) {
            if(!dfs(y)) return false;
        }
        return true;
    }
    bool solve() {
        for(int i = 0; i < n*2; i += 2) {
            if(!mark[i] && !mark[i+1]) {
                c = 0;
                if(!dfs(i)) {
                    while(c) mark[S[--c]] = 0;
                    if(!dfs(i+1)) 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[200 + 10];
    //get prime factor of n, store in vec
    void getPrimeFac(int n) {
        for(int i = 2; i <= n/i; i++) {

            if(n%i == 0) {
                while(n%i == 0) {
                    n /= i;
                }
                div.insert(i);
            }
        }
        if(n != 1) {
            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 = 0; i < m; i++)
            getPrimeFac(C[i]);
        for(int u: div) {
            sta.clear();
            for(int j = 0; j < m; j++) {
                int r = 0;
                int y = C[j];
                while(y%u == 0) {
                    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 = 0; i < sz(sta); i += 2) {
                //solver.add(i<<1, (i+1)<<1|1);
                solver.add((i+1)<<1|1, i<<1);
                //solver.add((i+1)<<1, i<<1|1);
                solver.add(i<<1|1, (i+1)<<1);
            }
            for(int i = 0; i < sz(sta); i++) for(int j = 0; j < sz(sta); j++) {
                    if(contradiction(i, j)) {
                        solver.add(i<<1, j<<1|1);
                        solver.add(j<<1, i<<1|1);
                    }
                }
            if(!solver.solve()) return  "Solution does not exist";
        }
        return  "Solution exists";
    }
};

View Code

学习了一下list，和vector最大区别便是不支持随机存取，可以看做是STL中的双向链表，支持首尾插入，删除。