Archive for July, 2011

偶然听到的Moonlight Meadow


21 Jul

今天我们OI Team去接受了心理辅导,正巧碰到2014级夏令营有个班在排练闭幕式节目。他们朗诵的配乐非常有感觉,于是我鼓起勇气问两个正在练习此曲的MM,得知是Twilight系列中Moonlight的一个配乐,叫Meadow。

Audio clip: Adobe Flash Player (version 9 or above) is required to play this audio clip. Download the latest version here. You also need to have JavaScript enabled in your browser.

用Simpson求多边形面积并


20 Jul
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <iostream>
#include <vector>
#include <cmath>
 
typedef long double ld;
const ld EPS = 1e-8;
const ld SIM_EPS = 1e-8;
const ld INF = 1e100;
using std::vector;
 
struct Vect {
 
    ld x, y;
 
    Vect(ld _x, ld _y) { x = _x, y = _y; }
    Vect() {}
};
 
struct Line {
 
    ld y;
    bool ch;
 
    Line(ld _y, bool _ch) { y = _y, ch = _ch; }
    Line() {}
 
    bool operator<(const Line &b) const {
 
        return y > b.y;
    }
};
 
typedef std::pair<ld, ld> Pair_t;
typedef vector<Vect> VectArr_t;
typedef vector<Pair_t> PairArr_t;
typedef vector<Line> LineArr_t;
 
ld lfabs(ld x) { return x < 0 ? -x : x; }
 
struct Poly {
 
    VectArr_t arr;
    Pair_t bound;
 
    void get_seg(ld x0, PairArr_t *seq) {
 
        if (x0 - bound.first < -EPS || x0 - bound.second > EPS) return;
        static LineArr_t res;
        res.clear();
        Vect o(x0, 0);
        for (VectArr_t::iterator it = arr.begin(); it != arr.end() - 1; it++)
        {
            Vect st = *it, ed = *(it + 1);
            ld dl = x0 - st.x, dr = x0 - ed.x;
            ld dd = dl * dr;
 
            if (dd < EPS)
            {
                ld dx = ed.x - st.x;
                if (lfabs(dx) > EPS) 
                {
                    res.push_back(
                            Line(st.y + (ed.y - st.y) * dl / dx,
                                (lfabs(dd) < EPS ? (dl > EPS || dr > EPS) : 1)
                                )
                            );
                }
            }
        }
        if (res.begin() == res.end()) return;
        std::sort(res.begin(), res.end());
 
        bool t = res.begin() -> ch;
        for (LineArr_t::iterator it = res.begin() + 1; it != res.end(); it++)
        {
            ld prev = (it - 1) -> y, now = it -> y;
            t ^= it -> ch;
            if (!(t & 1)) seq -> push_back(Pair_t(now, prev));
        }
    }
 
};
 
typedef vector<Poly> PolyArr_t;
PolyArr_t polys;
 
ld f(ld x) {
 
    static PairArr_t seq;
 
    seq.clear();
    Pair_t t;
    for (PolyArr_t::iterator it = polys.begin(); it != polys.end(); it++)
        it -> get_seg(x, &seq);
 
    std::sort(seq.begin(), seq.end());
    ld res = 0, inc = 0, r = -INF;
    for (PairArr_t::iterator it = seq.begin(); it != seq.end(); it++)
        if (it -> second > r)
        {
            if (it -> first > r) 
            {
                res += inc;
                inc = it -> second - it -> first;
            }
            else inc += it -> second - r;
 
            r = it -> second;
        }
    return res + inc;
}
 
ld s(ld l, ld r, ld fl, ld fm, ld fr) {
 
    return (r - l) / 6.0 * (fl + 4 * fm + fr);
}
 
ld sim(ld l, ld r, ld fl, ld fm, ld fr) {
 
    ld m = (l + r) / 2;
    ld flm = f((l + m) / 2),
       frm = f((m + r) / 2);
 
    ld al = s(l, r, fl, fm, fr),
       sl = s(l, m, fl, flm, fm),
       sr = s(m, r, fm, frm, fr);
 
    if (lfabs(sl + sr - al) < SIM_EPS) return al;
    return sim(l, m, fl, flm, fm) + sim(m, r, fm, frm, fr);
}
 
ld L = INF, R = -INF;
 
PairArr_t interv;
 
void pre_work() {
 
    int N, n;
    ld x, y, x0, y0;
 
    double alpha = 0 / 180 * M_PI;
    scanf("%d", &N);
    for (int i = 1; i <= N; i++)
    {
        Poly t;
        ld l = INF, r = -INF;
        scanf("%d", &n);
        for (int j = 1; j <= n; j++)
        {
            scanf("%Lf %Lf", &x0, &y0);
            x = x0 * cos(alpha) + y0 * sin(alpha);
            y = y0 * cos(alpha) - x0 * sin(alpha);
 
            l = std::min(l, x);
            r = std::max(r, x);
            t.arr.push_back(Vect(x, y));
        }
        t.arr.push_back(*t.arr.begin());
        t.bound = Pair_t(l, r);
        polys.push_back(t);
 
        interv.push_back(t.bound);
        L = std::min(L, l);
        R = std::max(R, r);
    }
}
 
void work() {
 
    ld ans = 0;
 
    ld fl = f(L), fm = f((L + R) / 2), fr = f(R);
    ans += sim(L, R, fl, fm, fr);
    printf("%.2Lf\n", ans);
}
 
int main() {
 
    freopen("simpson.in", "r", stdin);
 
    pre_work();
    work();
 
    return 0;
}

神一般的Dinic


18 Jul

啥也不解释,直接上代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
 
const int MAXVTX = 200000 + 2;
const int MAXE = 100000 + MAXVTX * 2;
const int MAXPE = MAXE * 2;
const int INF = 0x3f3f3f3f;
 
struct Edge {
 
    int to, ca;
    Edge *next, *inv;
 
} edges[MAXPE + 1], *head[MAXVTX + 1];
 
int N, M, S, T, vcnt, ecnt;
 
Edge *add_edge(int st, int ed, int ca) {
 
    Edge *ptr = edges + (++ecnt);
    ptr -> next = head[st];
    ptr -> to = ed;
    ptr -> ca = ca;
    return head[st] = ptr;
}
 
void add_pair(int st, int ed, int ca) {
 
    Edge *e1 = add_edge(st, ed, ca);
    Edge *e2 = add_edge(ed, st, 0);
    e1 -> inv = e2;
    e2 -> inv = e1;
}
 
#define RPART(x) ((x) << 1)
#define LPART(x) (RPART(x) - 1)
 
 
void pre_work() {
 
    int st, ed;
 
    scanf("%d %d", &N, &M);
    S = RPART(N) + 1, T = S + 1;
    vcnt = T;
 
    for (int i = 1; i <= M; i++)
    {
        scanf("%d %d", &st, &ed);
        add_pair(LPART(st), RPART(ed), 1);
    }
 
    for (int i = 1; i <= N; i++)
    {
        add_pair(S, LPART(i), 1);
        add_pair(RPART(i), T, 1);
    }
}
 
int dist[MAXVTX + 1];
 
bool relabel() {
 
    static int q[MAXVTX], v;
 
    memset(dist + 1, -1, sizeof(int) * vcnt);
    dist[*q = S] = 0;
    for (int l = 0, r = 1; l != r; l++)
    {
        int u = q[l];
        for (Edge *i = head[u]; i; i = i -> next)
            if (i -> ca && dist[v = i -> to] == -1) 
                q[r++] = v, dist[v] = dist[u] + 1;
    }
    return dist[T] != -1;
}
 
int find_aug(int u, int flow) {
 
    if (u == T) return flow;
    int res = 0, v, t; 
    Edge *i;
    for (i = head[u]; i; i = i -> next)
        if (i -> ca && (dist[v = i -> to] == dist[u] + 1))
        {
            res += t = find_aug(v, std::min(i -> ca, flow));
            i -> ca -= t, i -> inv -> ca += t;
            if (!(flow -= t)) break;
        }
    if (!i) dist[u] = -1;
    return res;
}
 
int dinic() {
 
    int res = 0;
    while (relabel()) res += find_aug(S, INF);
    return res;
}
 
 
void work() {
 
    printf("%d\n", N - dinic());
}
 
int main() {
 
    pre_work();
    work();
 
    return 0;
}

最BT的数论题——解高次同余方程


13 Jul
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <cmath>
#include <map>
 
typedef long long ll;
 
const int MAXP = 100000;
int p[MAXP], pcnt;
int T, ans, N;
 
void get_primes(int R) {
 
    bool comp[MAXP];
 
    for (int i = 2; i <= R; i++)
    {
        if (!comp[i]) p[++pcnt] = i;
        int bound = R / i;
        for (int j = 1; j <= pcnt && p[j] <= bound; j++)
        {
            comp[i * p[j]] = 1;
            if (!(i % p[j])) break;
        }
    }
}
 
ll pow(ll b, ll p, ll m) {
 
    ll res = 1, e = b;
    while (p)
    {
        if (p & 1) res = (res * e) % m;
        e = (e * e) % m;
        p >>= 1;
    }
    return res;
}
 
ll inv(ll x, ll m) { return pow(x, m - 2, m); }
 
bool check_proot(ll m, ll r) {
 
    ll x = m - 1;
    get_primes(int(sqrt(x)));
 
    for (int i = 1; i <= pcnt; i++)
        if (!(x % p[i]))
        {
            if (pow(r, (m - 1) / p[i], m) == 1) return 0;
            while (!(x % p[i])) x /= p[i];
        }
 
    if (x != 1 && pow(r, (m - 1) / x, m) == 1) return 0;
 
    return 1;
}
 
ll get_proot(ll m) {
 
    if (m == 2) return 1;
    for (int i = 2; i < m; i++)
        if (check_proot(m, i)) return i;
}
 
typedef std::map<int, int> Hash_t;
 
int discrete_log(int b, int a, int m) {
 
    Hash_t hash;
    int d = int(sqrt(m - 2));
    for (int j = 0; j < d; j++) 
        hash[int((a * inv(pow(b, j, m), m)) % m)] = j;
 
    int t = 1;
    for (int i = 0; i * d <= m - 2; i++)
    {
        if (hash.count(t)) return hash[t] + d * i;
        t = (t * pow(b, d, m)) % m;
    }
}
 
ll ext_gcd(ll a, ll b, ll &x, ll &y) {
 
    if (b == 0)
    {
        x = 1, y = 0;
        return a;
    }
    int ret = ext_gcd(b, a % b, x, y);
    int ox = x;
    x = y, y = ox - a / b * y;
    return ret;
}
 
ll get_ft(ll t) {
 
    if (t == 1) return 2;
    int bound = int(sqrt(t));
    for (int i = 2; i <= bound; i++)
        if (!(t % i)) return 2;
    return t;
}
 
int sol[100000], scnt;
 
int solve(int m) {
 
    ll r = get_proot(m);
    ll p = N, d = m - 1, c = discrete_log(r, ans, m);
 
    ll x, y, lb, rb;
    ll g = ext_gcd(p, d, x, y);
 
    if (c % g) return -1; // no solution
 
    x = c * x / g, y = c * y / g; // find a special solution
 
    lb = ll(ceil(double(x - (m - 2)) * g / d));
    rb = ll(floor(double(x) * g / d));
    for (int t = lb; t <= rb; t++)
        sol[++scnt] = x - d / g * t;
    // generate all solutions
    return r;
}
 
void pre_work() {
 
    int A, s, w;
    scanf("%d %d %d %d", &N, &ans, &T, &A);
    for (int i = 1; i < N; i++)
        scanf("%d %d", &s, &w); // read rubbish
 
}
 
int cmp_int(int a, int b) { return a < b; }
 
void work() {
 
    int m = get_ft(T);
 
    if (ans == 0) sol[scnt = 1] = 0;
    else
    {
        int r = solve(m);
        if (r != -1)
            for (int i = 1; i <= scnt; i++)
                sol[i] = pow(r, sol[i], m);
    }
 
 
    for (int i = 1; i <= scnt; i++)
        sol[i] = ((sol[i] + 1) * pow(sol[i], N - 1, m)) % m;
 
    std::sort(sol + 1, sol + scnt + 1, cmp_int);
    scnt = std::unique(sol + 1, sol + scnt + 1) - sol - 1;
 
    printf("%d\n", scnt);
    for (int i = 1; i <= scnt; i++) printf("%d ", sol[i]);
    printf("\n");
}
 
int main() {
 
    freopen("WA.in", "r", stdin);
    freopen("WA.out", "w", stdout);
    pre_work();
    work();
 
    return 0;
}

Teddy

Studies,OI and Love