Archive for the ‘OI’ Category

用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;
}

Summary for SCTSC


29 May

对我来说最后一次的省选已经结束了, 有一些遗憾,但我无悔。
第一试一般,第二试爆了,于是就与正式名额无缘了。
如果总的来说,总分弱弱,是由于没有把自己的水平发挥出来。
什么叫“发挥出水平呢”,我不禁自问。
其实也很好衡量,坐时光机去拉来去年的我来考今年的试,分数基本也不会比110低。
差分约束暑假就学会了。去年的我,剩下就裸点分,说不定还因为学插头DP不久,一咬牙把一试二题做了。
事实是,今年的我肯定比去年的牛x多了。但是多的这些东西,也就是说一年来的练习,思考做题,最终没有在考场上转化为生产力。
Theo的一句话点到了本质:“看你做了那么多题,没有什么效果啊。”
对,目前的问题就是这个。
不谈和别人的比较,单单就自己而言,水平是可以进队的,使使劲NOI也是可以拿银牌的。
如果说会的占1,那么我能尽多大限度发挥,是10%,还是50%, 抑或是90%,甚至200%?
在比赛前固然可以提高那个1来保证即使是10%也能因为1的扩大而扩大。但是事实是,提高百分比更为有效,它能让自己努力立竿见影,也能完全显露自己几斤几两。
我们不能总期待题有所谓的高区分度,能做的是在相同情况下,把自己的十八般武艺展现无疑,那么自然就没有遗憾了。

善,为之奈何?

就拿一试二题来说,这道题虽说是一个典型的插头DP,却并不是基于连通性的,讨论的情况也相当清晰明了,况且联赛前的暑假专门练习了4、5道相关的题目。但是因为我考前曾经对自己说过,如果有插头DP就果断裸搜,于是就放弃了进一步的思考。我在这一刻害怕了。相反,一些没有做过连通性插头DP的同学反而想得简单明了,得了相当可观的分数。
如果学会做一个自己都不敢在考场写的东西,那还不如学些别的。换而言之,在这个特殊时期,知识一定要设法让它变成生产力。

另外在考试中暴露出来的一个问题是,我临场思维时间太长了,容易陷进去,这是在考前就知道的,但是即便是知道,临场时也难逃厄运。虽然说二试一题,我在读完题后就断定这题我能拿80分,但是在思考实现的问题上,不断的修改原来的想法,一时间很多想法以及问题涌上来,等我按照想法写好,却发现考虑漏了,于是就在原来繁琐的算法基础上修修改改。(把某些部分变得更裸)但是这个是导致我二试爆掉的直接原因,本来应该推翻重来,写个平衡树和并差集就轻松拿到80,但是我当时思维已经陷进去,不能自拔,在原来的基础上反反复复修改,脑袋一度一片空白。
看了三题,想的时候又始终不忘一题。原本制定好的先做80分一题,再使劲强攻三题的计划已被打乱。败局已定。

虽然我在前段时间的训练中,对自己编码时间进行了缩短,但是有很多题是我想来想去,想了好一会儿,
然后再敲出来的。我并没有把思考的这部分时间进行刻意压缩,而是信马由缰,想够。虽然这对我思考能力提升有帮助,但是比赛是在有一定压力和紧张的情况下进行的,平时那种闲庭信步的坦然在临场时就可能会荡然无存。而进入状态越快,思维不会随思考加深而迟钝的人才会在考场上从容不迫。在一个思路已经复杂繁琐难以琢磨了以后真的要学会舍弃,有舍才有得。

今后的考试就要努力调整,给自己制造紧张感,把每场考试当作省选或是NOI。
在八中OJ上做题,要进行思考和实现的双重控时,并虚心听取他人意见和新思路,不断改进,做最好的自己。

Yesterday && TOMORROW


19 May

5月的时光在机翼和奔走脚步间流逝。简而言之,CTSC乱考,APIO纯windows无vim环境吃不消故二题不敢展开写,在FDU举办的Google杯ACM全国邀请赛被江苏的各种神队虐。最终结果是:CTSC无奖,APIO Cu牌,ACM目前不确定铜奖还是银奖(75名,只做了3题,其实后来发现有5道都是可做的)。

 

在APIO及其不爽的考试过后,我果断在windows下写题,至于对拍的问题,在北京最后几天我们和lrj的闲谈中我提及此事,他说他写的一本书上有可用的bat脚本,于是看了一下发现可以用,但是linux的管道在windows下不知道有没有替代品。

明天就是传说中的省选了。近来经历为我指明了考试方向:

1.我不是神牛,把会做的做起,不会做的暴力,然后喝点水开始研究不会做的,骗个什么分。

2.前几名不是咱的,不要去想

3.当一道题的想法开始“收敛”,猜想的做法开始变得繁琐而ws时,继续思考已经失去意义,即便是想出来了,不见得能在短时间写出来。所以思考要用EPS来剪枝。

4.拿到题无论某道题多么简单,都要通读全题

 

bless all

 

Teddy

Studies,OI and Love