省选模拟赛[HBOI2012]“编程题”

比赛过程

18:00

浏览了一遍题目… 怎么又有原题??? 第三题tyh以前考过的. 再看一下第二题… 傻逼数据结构? 范围还只有1e5…. 呵呵裸的莫队… 不要说1e5了1e6我上个主席树都能做.(后来听说可以离线树状数组?

19:30

Ａ掉了2， 3题， 第一题毫无思路… 遇到多项式我就死… 戴上耳机听了半个小时的音乐， 顺便睡了会儿觉, 什么多项式鬼玩意都去死吧… 我连暴力都写不来.

20:00

睡醒了… 怎么考试还有2h??? 只有又看第一题， 推了一页的草稿纸. 等下… 分数形式的p/q， 一个是a0的约数一个是an的约数? 暴力枚举暴力check就行了嘛? 数太大了取个模? 这不大水题吗!!! 赶快半小时写了一发， 调了几下就过样例了， 此时身心舒畅.
今天又能AK?(赛后的我就呵呵了

21:30

对拍了一下t2没什么问题… 话说数据真的只有1e5? 怎么会这么水? 再怎么说都应该是1e6搞个主席树? 心中觉得不妙… 决定写棵主席树以防万一. 这种东西20min就能写完… 算了时间打紧还是检查一下吧… 反正如果真的数据范围给错了我不背锅.

赛后

为什么只有200? 不科学啊? t1死了? AK梦破碎. 测了一下数据发现我的输出的排序方式有问题? 把排序方式写的详细一点， 再交上去… A了!!! 我的AK啊!!!没想到居然死在了输出排序上， 有生以来第一次… 算是吃教训了. 真省选的时候就千万不能出这种岔子了.

Akai的数学作业

#include
#include
#include
using namespace std;
typedef long long dnt;
const int maxm = 105;
const int maxn = 1e6;
const dnt mod = 1e9 + 7;
int n, cnt, na, nb;
dnt pwx[maxm], pwy[maxm];
int a[maxn], b[maxn], c[maxm];
int gcd(int a, int b) {
    return (!b) ? a : gcd(b, a % b);
}
struct query {
    int u, d, f; //means up and down
    friend bool operator < (const query &x, const query &y) {
        if (x.f == -1 && y.f == +1)
            return true;
        if (x.f == +1 && y.f == -1)
            return false;
        if (x.f ==  1 && y.f ==  1)
            return 1ll * x.u * y.d < 1ll * y.u * x.d;
        if (x.f == -1 && y.f == -1)
            return 1ll * x.u * y.d > 1ll * y.u * x.d;
    }
}q[maxm];
inline void init() {
    int fr = 0;
    while (!c[fr]) ++ fr;
    if (!fr) return;
    n = n - fr;
    for (int i = 0; i <= n; ++ i)
        c[i] = c[i + fr];
    q[++ cnt].u = 0, q[cnt].d = 1, q[cnt].f = 1;
}
inline void frac(int x, int *array, int &num) {
    int lim = (int)sqrt(x);
    for (int i = 1; i <= lim; ++ i) // it should be <= 
        if (x % i == 0) {
            array[++ num] = i;
            array[++ num] = x / i;
        }
    if (lim * lim == x) -- num; 
}
inline void calc(dnt x, dnt y) {
    int f = 1;
    dnt ans = 0, ret = 0;
    if (x < 0) f = -1, x = -x;
    for (int i = 1; i <= n; ++ i)
        pwx[i] = (pwx[i - 1] * x) % mod,
        pwy[i] = (pwy[i - 1] * y) % mod;
    for (int i = 0; i <= n; ++ i) {
        ret = c[i] * pwx[i] % mod * pwy[n - i] % mod;
        if (i & 1)
            ret = (ret * f + mod) % mod;
        ans = (ans + ret) % mod;
    }
    if (!ans)
        q[++ cnt].u = x, q[cnt].d = y, q[cnt].f = f; 
}
inline void bruce_solve() {
    pwx[0] = pwy[0] = 1;
    for (int i = 1; i <= na; ++ i)
        for (int j = 1; j <= nb; ++ j)
            if (gcd(a[i], b[j]) == 1)
                calc(a[i], b[j]), calc(-a[i], b[j]);
}
int main() {
    freopen("akai.in", "r", stdin);
    freopen("akai.out", "w", stdout);
    scanf("%d", &n);
    for (int i = 0; i <= n; ++ i)
        scanf("%d", &c[i]);
    init();
    frac(abs(c[0]), a, na), frac(abs(c[n]), b, nb);
    bruce_solve();
    sort(q + 1, q + cnt + 1);
    printf("%d\n", cnt);
    for (int i = 1; i <= cnt; ++ i) {
        if (q[i].f == -1) putchar('-');
        if (q[i].u % q[i].d == 0) printf("%d\n", q[i].u / q[i].d);
        else printf("%d/%d\n", q[i].u, q[i].d);
    }
    return 0;
}

采花

#include
#include
#include
using namespace std;
const int maxn = 1e5 + 5;
int n, m, block, ret, c;
int blo[maxn], cnt[maxn], col[maxn], ans[maxn];
inline const int read() {
    register int x = 0;
    register char ch = getchar();
    while (ch < '0' || ch > '9') ch = getchar();
    while (ch >= '0' && ch <= '9') x = (x << 3) + (x << 1) + ch - '0', ch = getchar();
    return x;
}
struct query {
    int id, l, r;
    inline friend bool operator < (const query &x, const query &y) {
        return blo[x.l] < blo[y.l] || (blo[x.l] == blo[y.l] && x.r < y.r); 
    }
}q[maxn];
inline void update(int x, int opt) {
    cnt[col[x]] += opt;
    if (opt ==  1 && cnt[col[x]] == 2) ret ++;
    if (opt == -1 && cnt[col[x]] == 1) ret --;
}
inline void Captain_Mo() {
    int l = 1, r = 0;
    sort(q + 1, q + m + 1);
    for (int i = 1; i <= m; ++ i) {
        while (l < q[i].l) update(l ++, -1);
        while (l > q[i].l) update(-- l, +1);
        while (r < q[i].r) update(++ r, +1);
        while (r > q[i].r) update(r --, -1);
        ans[q[i].id] = ret;
    }
}
int main() {
    freopen("flower.in", "r", stdin);
    freopen("flower.out", "w", stdout);
    n = read(), c = read(), m = read();
    for (int i = 1; i <= n; ++ i) col[i] = read();
    for (int i = 1; i <= m; ++ i)
        q[i].l = read(), q[i].r = read(), q[i].id = i;
    block = (int)sqrt(n);
    for (int i = 1; i <= n; ++ i) blo[i] = (i - 1) / block + 1;
    Captain_Mo();
    for (int i = 1; i <= m; ++ i)
        printf("%d\n", ans[i]);
    return 0;
}

朋友圈

#include
#include
#include
#define permi(a) memset(a, true, sizeof(a))
using namespace std;
const int maxn = 3050;
bool mp[maxn][maxn];
int na, nb, ans, tim1 ,tim2, num, m, T;
int a[maxn], b[maxn], match[maxn], tim[maxn], h[maxn], vis[maxn], mark[maxn];
struct edge{ int nxt, v;}e[maxn * maxn];
inline void add(int u, int v) {
    e[++ num].v = v, e[num].nxt = h[u], h[u] = num;
}
inline bool check(int x) {
    int cnt = 0;
    if (!x) return 0; 
    for (int i = x; i; i -= i & -i) ++ cnt;
    return cnt & 1;
}
bool find(int u) {
    if (mark[u] == tim1) return false;
    for (int i = h[u]; i; i = e[i].nxt) {
        int v = e[i].v;
        if (vis[v] != tim2 && mark[v] != tim1){
            vis[v] = tim2;
            if (tim[v] != tim1 || !match[v] || find(match[v])) {
                tim[v] = tim1;
                return match[v] = u;
            }
        }
    }
    return false;
}
inline int work(int x = 0, int y = 0) {
    tim1 ++;
    int cnt = 0;
    for (int i = 1; i <= nb; ++i)
        if (mp[x][i] || mp[y][i]) mark[i] = tim1, ++ cnt;
    for (int i = 1; i <= nb; ++i)
        if(b[i] & 1) {
            ++ tim2;
            if(find(i)) ++ cnt;
        }
    return nb - cnt;
}
int main() {
    permi(mp); 
    scanf("%d%d%d", &na, &nb, &m);
    for (int i = 1; i <= na; ++ i) scanf("%d", &a[i]);
    for (int i = 1; i <= nb; ++ i) scanf("%d", &b[i]);
    for (int i = 1; i <= m; ++i){
        int x, y;
        scanf("%d%d", &x, &y);
        mp[x][y] = false;
    }
    for (int i = 1; i <= nb; ++ i) mp[0][i] = false;
    for (int i = 1; i <= nb; ++ i)
        if (b[i] & 1)
            for (int j = 1; j <= nb; ++ j)
                if (~ b[j] & 1)
                    if (!check(b[i] | b[j])) add(i, j);
    ans = work();
    for (int i = 1; i <= na; ++ i)
        ans = max(ans, work(i) + 1);
    for (int i = 1; i <= na; ++ i)
        if (a[i] & 1)
            for (int j = 1; j <= na; ++ j)
                if (~ a[j] & 1)
                    ans = max(ans, work(i,j) + 2);
    printf("%d\n", ans);
    return 0;
}