http://codeforces.com/gym/100463

切了场GYM。

A题
简单树状数组。

C题
首先对每个点连出的边进行极角排序(范围内),由于题意是逆时针旋转,我们可以G[i][angle[j].y] = angle[j + 1].y;这样用邻接矩阵建图。
建好图后 DFS 下就可以求出所有圈的长度了。

(顺便吐槽下此题时限为 40 s)

D题
直接枚举红点一半的组合就行,不需要判断是否有其他红点在所选的红点围成的矩形内,因为在这种情况下,一定有比该矩形更小的矩形。

E题
并查集。合并的时候要讨论清楚:

  1. 当 x==y 时集合唯一确定,用一个布尔数组 uni 表示(uni 表示 unique);
  2. merge 时要合并人数,集合大小,uni 这三个。

I题
这题需要有特殊的 YY 技巧。
由于要使A集合与B集合扩张成一个对减法封闭的,所以必须要有单位元 1 和 -1,进一步分析发现我们要判断出是否可以从A集合中可重复地取出 x 个数,从B集合中可重复地取出 x-1 或 x 个数,使得对于某些取法 sumA-sumB=1,某些取法 sumA-sumB=-1。

显然答案与有关,设其值为g,则 g=1 时可以扩张成;由于还可以先往右边多走一步,则 g=2 且集合A中存在奇数时也可以扩张成(g=2 说明可以扩展成偶整数集合,此时只要集合A中有个奇数就可以扩张成);但是对于 g>2 的情况却不行,这是因为此时扩张成 {...,-2g,-g,0,g,2g,...} 的集合,但又由于,所以,令,则只能扩张成形如 mg+k 的集合。
优化:

  1. 可以简化为
  2. 根据此简化式,判断集合A中是否有奇数可以简化为判断是否为奇数;
  3. 判断

附代码:

(只贴出与题目有关的代码,宏定义见 GitHub

C题

/*5194 ms, 19960 KB*/
const int mx = int(2e3);

pair<int, int> p[mx];
vector<pair<double, int> > angle;
#define x first
#define y second
int G[mx][mx];

void init(int n)
{
    int i, j;
    double tmp;
    For(i, n)
    {
        angle.clear();
        For(j, n) if (j != i)
        {
            tmp = atan2(p[j].y - p[i].y, p[j].x - p[i].x);
            if (tmp < 0.0) tmp += pi;
            angle.PB(MP(tmp, j));
        }
        sort(all(angle)), angle.PB(angle[0]);
        For(j, n - 1) G[i][angle[j].y] = angle[j + 1].y;
    }
}

set<int> ans;
bool vis[mx][mx];

void dfs(int i, int j, int deep)
{
    if (vis[i][j])
    {
        ans.insert(deep);
        return;
    }
    vis[i][j] = true;
    dfs(G[i][j], i, ++deep);
}

void getCircleLength(int n)
{
    ans.clear(), mem(vis, 0);
    int i, j;
    For(i, n) For(j, n) if (i != j && !vis[i][j]) dfs(i, j, 0);
    siter it;
    loop(it, ans) printf(" %d", *it);
    Pn();
}

int main()
{
    int n, i, j;
    while (SI(n), n)
    {
        Pcas();
        For(i, n) SII(p[i].x, p[i].y);
        init(n);
        getCircleLength(n);
    }
    return 0;
}

D题

/*93 ms, 0 KB*/
const int mx = 25;

vector<p2> red, blue;
bool choose[mx];
int xmin, xmax, ymin, ymax;

inline bool in()
{
    int i;
    For(i, blue.size()) if (blue[i].x >= xmin && blue[i].x <= xmax && blue[i].y >= ymin && blue[i].y <= ymax) return true;
    return false;
}

int solve()
{
    int n = red.size(), m = n >> 1, i, ans = inf;
    For(i, m) choose[i] = true;
    Forr(i, m, n) choose[i] = false;
    do
    {
        xmin = ymin = inf, xmax = ymax = -inf;
        For(i, n) if (choose[i])
        {
            Qmin(xmin, red[i].x), Qmax(xmax, red[i].x);
            Qmin(ymin, red[i].y), Qmax(ymax, red[i].y);
        }
        if (!in()) Qmin(ans, (xmax - xmin) * (ymax - ymin));
    }
    while (prev_permutation(choose, choose + n));
    return ans == inf ? -1 : ans;
}

int main()
{
    int n, x0, y0, c;
    while (SI(n), n)
    {
        Pcas();
        red.clear(), blue.clear();
        while (n--) SIII(x0, y0, c), c ? blue.PB(MP(x0, y0)) : red.PB(MP(x0, y0));
        PI(solve());
    }
    return 0;
}

E题

/*249 ms, 1272 KB*/
const int mx = int(1e5) + 5;

int fa[mx], people[mx], sz[mx];
bool uni[mx]; /// 该集合是否唯一确定

int find(int x) {return ~fa[x] ? fa[x] = find(fa[x]) : x;}

inline bool merge(int x, int y)
{
    if (x == y) uni[find(x)] = true;
    x = find(x), y = find(y);
    x == y ? ++people[x] : (fa[y] = x, people[x] += people[y] + 1, sz[x] += sz[y], uni[x] |= uni[y]);
    return people[x] <= sz[x];
}

int solve(int n, int m)
{
    int x, y, i;
    while (n--)
    {
        SII(x, y);
        if (!merge(x, y))
        {
            while (n--) SII(x, y);
            return 0;
        }
    }
    ll ans = 1LL;
    For(i, m) if (fa[i] == -1) ans = ans * (people[i] < sz[i] ? sz[i] : (uni[i] ? 1LL : 2LL)) % mod;
    return ans;
}

int main()
{
    int n, m;
    while (SII(n, m), n)
    {
        Pcas();
        mem(fa, -1), mem(people, 0), fill(sz, sz + m, 1), mem(uni, 0);
        PI(solve(n, m));
    }
    return 0;
}

I题

/*124 ms, 0 KB*/
int gcd(int a, int b) {return b ? gcd(b, a % b) : a;}

int g, mina, maxa, minb, maxb, a0;

inline bool ok()
{
    if (maxa <= minb || maxb <= mina) return true;
    if (g == 1 || g == 2 && (a0 & 1)) return false;
    return true;
}

int main()
{
    int n, m, ai, b0, bi;
    while (SII(n, m), n)
    {
        Pcas();
        g = 0;
        SI(a0);
        maxa = mina = a0;
        while (--n)
        {
            SI(ai);
            g = gcd(abs(ai - a0), g);
            Qmin(mina, ai), Qmax(maxa, ai);
        }
        SI(b0);
        maxb = minb = b0;
        while (--m)
        {
            SI(bi);
            g = gcd(abs(bi - b0), g);
            Qmin(minb, bi), Qmax(maxb, bi);
        }
        g = gcd(abs(a0 - b0), g);
        puts(ok() ? "YES" : "NO");
    }
    return 0;
}

Comments

comments powered by Disqus