Regionals 2012, Asia - Jakarta 解题报告

时间：2024-07-26 18:35:08

啥都不会做了。。

做题慢死

A.Grandpa's Walk

签到题。

直接DFS就行。

注意先判断这个点可以作为一个路径的起点不。

然后再DFS。

否则处理起来略麻烦

#include <iostream>

#include <algorithm>

#include <cstring>

#include <cstdio>

#include <map>

#define MAXN 111111

#define INF 1000000007

using namespace std;

int h[55][55];

int dp[55][55];

int n, m;

int xx[] = {0, 0, -1, 1};

int yy[] = {1, -1, 0, 0};

int vis[55][55];

void dfs(int x, int y)

{

    dp[x][y] = 0;

    vis[x][y] = 1;

    int flag = 0;

    for(int i = 0; i < 4; i++)

    {

        int tx = x + xx[i];

        int ty = y + yy[i];

        if(tx >= 0 && ty >= 0 && tx < n && ty < m )

        {

            if(h[x][y] <= h[tx][ty] ) continue;

            flag = 1;

            if(!vis[tx][ty])

                dfs(tx, ty);

            dp[x][y] += dp[tx][ty];

        }

    }

    if(flag == 0) dp[x][y] = 1;

}

int main()

{

    int T;

    int cas = 0;

    scanf("%d", &T);

    while(T--)

    {

        memset(dp, -1, sizeof(dp));

        scanf("%d%d", &n, &m);

        memset(vis, 0, sizeof(vis));

        for(int i = 0; i < n; i++)

            for(int j = 0; j < m; j++)

                scanf("%d", &h[i][j]);

        int ans = 0;

        //ans += dfs(1, 1);

        for(int i = 0; i < n; i++)

            for(int j = 0; j < m; j++)

            {

                int flag = 0;

                for(int k = 0; k < 4; k++)

                {

                    int tx = i + xx[k];

                    int ty = j + yy[k];

                    if(tx >= 0 && ty >= 0 && tx < n && ty < m)

                        if(h[tx][ty] > h[i][j])

                            flag = 1;

                }

                if(flag) continue;

                dfs(i, j);

                ans += dp[i][j];

            }

        printf("Case #%d: %d\n", ++cas, ans);

    }

    return 0;

}

B.
Let's Go Green

很容易想到一种贪心的思想

就是一个结点。

从父节点流过来的边。

能跟去往子结点的边流多少  就流多少

然后子结点如果还有留下的流量

就两两配对搞一下

但是可能会出现某个分支流量很大。

别的所有分支跟这个分支配对完，这个分支还有剩余

那么就要特殊判断一下。

所以就要求一下所有分支的流量总和，以及最大值。

然后看sum - max 与max的关系。

#include <iostream>

#include <algorithm>

#include <cstring>

#include <cstdio>

#include <map>

#include <vector>

#define MAXN 111111

#define INF 1000000007

using namespace std;

vector<pair<int, int> >g[MAXN];

int n, ans;

void dfs(int u, int fa, int pre)

{

    int sz = g[u].size();

    int mx = 0;

    int sum = 0;

    for(int i = 0; i < sz; i++)

    {

        int v = g[u][i].first;

        int w = g[u][i].second;

        if(v == fa) continue;

        dfs(v, u, w);

        sum += w;

        mx = max(mx, w);

    }

    int t = mx + mx - sum;

    if(t > pre) ans += mx - pre;

    else if(sum >= pre) ans += (sum - pre + 1) / 2;

}

int main()

{

    int T, u, v, w;

    int cas = 0;

    scanf("%d", &T);

    while(T--)

    {

        scanf("%d", &n);

        ans = 0;

        for(int i = 1; i <= n; i++) g[i].clear();

        for(int i = 1; i < n; i++)

        {

            scanf("%d%d%d", &u, &v, &w);

            g[u].push_back(make_pair(v, w));

            g[v].push_back(make_pair(u, w));

        }

        dfs(1, 0, 0);

        printf("Case #%d: %d\n", ++cas, ans);

    }

    return 0;

}

C.Stop Growing!

签到题。

发现和是翻倍增长即可

D.Retrenchment

没看

E.Bee Tower

简单的一个二维DP

dp[i][j] 表示的是从第i个塔在第j个位置时登上塔所需要得最小花费

注意的是最高的塔不能动！！

所以找答案的时候要找对状态

#include <iostream>

#include <algorithm>

#include <cstring>

#include <cstdio>

#include <map>

#include <vector>

#include <queue>

#define MAXN 555

#define INF 1000000007

using namespace std;

int dp[MAXN][MAXN];

typedef pair<int, int> P;

P tow[MAXN];

int n, H, W, mx, ans;

void gao()

{

    tow[0].second = 0;

    memset(dp, 0x3f, sizeof(dp));

    for(int i = 1; i <= n; i++)

    {

        int tmp = tow[i].second - tow[i - 1].second;

        if(tow[i].second <= H)

            for(int j = 1; j <= 500; j++)

                dp[i][j] = min(dp[i][j], abs(tow[i].first - j) * tow[i].second);

        if(tmp > H) continue;

        for(int j = 1; j <= 500; j++)

            for(int k = 1; k <= W; k++)

            {

                if(j - k < 1) break;

                dp[i][j] = min(dp[i][j], abs(tow[i].first - j) * tow[i].second + dp[i - 1][j - k]);

            }

    }

}

void getans()

{

    for(int i = 1; i <= n; i++)

        if(tow[i].second == mx)

            ans = min(ans, dp[i][tow[i].first]);

}

int main()

{

    int T, cas = 0;

    scanf("%d", &T);

    while(T--)

    {

        scanf("%d%d%d", &n, &H, &W);

        mx = 0, ans = INF;

        for(int i = 1; i <= n; i++)

        {

            scanf("%d%d", &tow[i].first, &tow[i].second);

            mx = max(tow[i].second, mx);

        }

        sort(tow + 1, tow + 1 + n);

        gao();

        getans();

        for(int i = 1; i <= n; i++) tow[i].first = 501 - tow[i].first;

        sort(tow + 1, tow + 1 + n);

        gao();

        getans();

        if(ans == INF) ans = -1;

        printf("Case #%d: %d\n", ++cas, ans);

    }

    return 0;

}

F.Knots

呃。。神题吧。

G.Unique Path

就是求边的双连通分量。

然后把涉及到的边的两个端点都给标记掉。

其实就是跟求桥相反。 不是桥的边得端点肯定不行。

剩余的点组成了若干个连通块

每个连通块内，点与点之间都符合要求

#include <iostream>

#include <algorithm>

#include <cstring>

#include <cstdio>

#include <map>

#define MAXN 111111

#define INF 1000000007

using namespace std;

int n, m;

struct Edge

{

    int u, v, next;

}edge[MAXN * 2];

int tmpdfn, e, top, num[MAXN];

int head[MAXN], vis[MAXN * 2];

int dfn[MAXN], low[MAXN], fa[MAXN];

int cnt;

void init()

{

    e = 0, tmpdfn = 0, top = -1;

    cnt = 0;

    memset(head, -1, sizeof(head));

    memset(vis, 0, sizeof(vis));

    memset(dfn, 0, sizeof(dfn));

    memset(num, 0, sizeof(num));

}

void insert(int x, int y)

{

    edge[e].u = x;

    edge[e].v = y;

    edge[e].next = head[x];

    head[x] = e++;

}

int find(int x)

{

    if(x == fa[x]) return x;

    int t = find(fa[x]);

    fa[x] = t;

    return t;

}

void dfs(int u, int fath)

{

    dfn[u] = low[u] = ++tmpdfn;

    for(int i = head[u]; i != -1; i = edge[i].next)

    {

        int v = edge[i].v;

        if(!dfn[v])

        {

            dfs(v, u);

            low[u] = min(low[u], low[v]);

            if(low[v] <= dfn[u])

                vis[u] = vis[v] = 1;

        }

        else if(v != fath) low[u] = min(low[u], dfn[v]);

    }

}

int main()

{

    int T, u, v;

    int cas = 0;

    scanf("%d", &T);

    while(T--)

    {

        scanf("%d%d", &n, &m);

        init();

        for(int i = 0; i < m; i++)

        {

            scanf("%d%d", &u, &v);

            insert(u, v);

            insert(v, u);

        }

        for(int i = 1; i <= n; i++) fa[i] = i, num[i] = 1;

        for(int i = 1; i <= n; i++)

            if(!dfn[i]) dfs(i, 0);

        for(int i = 1; i <= n; i++)

            for(int j = head[i]; j != -1; j = edge[j].next)

            {

                int v = edge[j].v;

                if(!vis[i] && !vis[v])

                {

                    int fx = find(i);

                    int fy = find(v);

                    if(fx != fy)

                    {

                        fa[fy] = fx;

                        num[fx] += num[fy];

                        num[fy] = 0;

                    }

                }

            }

        printf("Case #%d: ", ++cas);

        memset(vis, 0, sizeof(vis));

        long long ans = 0;

        for(int i = 1; i <= n; i++)

        {

            int t = find(i);

            if(!vis[t])

            {

                vis[t] = 1;

                ans += (long long)(num[t]) * (long long)(num[t] - 1) / 2;

            }

        }

        printf("%lld\n", ans);

    }

    return 0;

}

H.Alien Abduction

这题的话。

注意到

操作到的人次不会超过5W

也就是要快速找到这些符合要求的人

那么。

还是那个技巧。

所有点左旋45度

然后坐标转换。

用set给存下来

就能很快的找到这些点了

#include <iostream>

#include <cstdio>

#include <set>

#include <vector>

#include <cstring>

#include <algorithm>

#define INF 100000005

#define MAXN 70000

using namespace std;

int N, Q, W, H;

int X, Y, E, a, b, c, d, e, f, x, y;

typedef pair<int, int> P;

P ans[MAXN];

typedef pair<int, P> PP;

set<P>s[MAXN];

set<int>xx;

vector<PP>g;

typedef set<int>::iterator Iter;

typedef set<P>::iterator Pter;

typedef long long LL;

int getx(int tx, int ty)

{

    return (tx - H + ty) / 2;

}

int gety(int tx, int ty)

{

    return (ty - tx + H) / 2;

}

int main()

{

    int T;

    int cas = 0;

    scanf("%d", &T);

    while(T--)

    {

        scanf("%d%d%d%d", &N, &Q, &W, &H);

        for(int i = 0; i <= W + H; i++) s[i].clear();

        xx.clear();

        for(int i = 1; i <= N; i++)

        {

            scanf("%d%d", &x, &y);

            s[x - y + H].insert(make_pair(x + y, i));

            xx.insert(x - y + H);

        }

        for(int i = 0; i < Q; i++)

        {

            scanf("%d%d%d%d%d%d%d%d%d", &X, &Y, &E, &a, &b, &c, &d, &e, &f);

            x = X - Y + H;

            y = X + Y;

            Iter it1 = xx.lower_bound(x - E);

            Iter it2 = xx.upper_bound(x + E);

            g.clear();

            for(Iter it = it1; it != it2; it++)

            {

                int nowx = *it;

                Pter pt1 = s[nowx].lower_bound(make_pair(y - E, -1));

                Pter pt2 = s[nowx].upper_bound(make_pair(y + E, INF));

                for(Pter pt = pt1; pt != pt2; pt++)

                {

                    P tmp = *pt;

                    g.push_back(make_pair(nowx, tmp));

                }

            }

            for(int j = 0; j < g.size(); j++)

            {

                int tx = g[j].first;

                int ty = g[j].second.first;

                int id = g[j].second.second;

                s[tx].erase(g[j].second);

                if(s[tx].size() == 0) xx.erase(tx);

                x = getx(tx, ty);

                y = gety(tx, ty);

                LL newx = ((LL)x * (LL)a % W + (LL)y * (LL)b % W + (LL)id * (LL)c % W) % W;

                LL newy = ((LL)x * (LL)d % H + (LL)y * (LL)e % H + (LL)id * (LL)f % H) % H;

                tx = (newx - newy + H);

                ty = newx + newy;

                s[tx].insert(make_pair(ty, id));

                xx.insert(tx);

            }

        }

        for(Iter it = xx.begin(); it != xx.end(); it++)

        {

            int now = *it;

            for(Pter pt = s[now].begin(); pt != s[now].end(); pt++)

            {

                P tmp = *pt;

                ans[tmp.second].first = getx(now, tmp.first);

                ans[tmp.second].second = gety(now, tmp.first);

            }

        }

        printf("Case #%d:\n", ++cas);

        for(int i = 1; i <= N; i++)

            printf("%d %d\n", ans[i].first, ans[i].second);

    }

    return 0;

}

I.Tiling

这题的话。。

刚开始百思不得其解

然后经zhou神一说就知道了。。

这题的模型可以转化成求某一列相邻两点的距离

首先可以发现第(0,0)点显然是可以的。。

然后求一个尽量小的(X, 0)就行了。

我们先用两个两个向量去凑

对于(x1, y1)和(x2, y2)

我们可以凑成

(x1 * y2 - x2 * y1, y1 * y2 - y2 * y1)

即(x1 * y2 - x2 * y1, 0 )

然后有三个向量就有三种可能

假设这三种分别凑成了(a,0) (b,0) (c,0)

根据线性方程的话。

gcd(a, b, c) 是这三种数能凑成的最小的间隔

就是答案了。。

#include <iostream>

#include <cstdio>

#include <set>

#include <vector>

#include <cstring>

#include <algorithm>

#define INF 100000005

#define MAXN 70000

using namespace std;

int f(int x1, int y1, int x2, int y2)

{

    return x1 * y2 - y1 * x2;

}

int main()

{

    int T, cas = 0;

    int x1, x2, y1, y2, x3, y3;

    scanf("%d", &T);

    while(T--)

    {

        scanf("%d%d%d%d%d%d", &x1, &y1, &x2, &y2, &x3, &y3);

        int a = f(x1, y1, x2, y2);

        int b = f(x1, y1, x3, y3);

        int c = f(x2, y2, x3, y3);

        printf("Case #%d: %d\n", ++cas, __gcd(abs(a), __gcd(abs(b), abs(c))));

    }

    return 0;

}

J.
Perfect Matching

貌似最裸的暴力是能在oj上过的。

但是从现场的感觉来看

不应该是那么裸才是

相关文章