Regionals 2012 :: Asia - Dhaka

时间：2023-11-24 21:43:26

水 B Wedding of Sultan

题意：求每个点的度数

分析：可以在，每个字母的的两个端点里求出的的出度，那么除了起点外其他点还有一个入度，再+1

/************************************************

* Author        :Running_Time

* Created Time  :2015/11/4 星期三 13:22:03

* File Name     :B.cpp

 ************************************************/

#include <cstdio>

#include <algorithm>

#include <iostream>

#include <sstream>

#include <cstring>

#include <cmath>

#include <string>

#include <vector>

#include <queue>

#include <deque>

#include <stack>

#include <list>

#include <map>

#include <set>

#include <bitset>

#include <cstdlib>

#include <ctime>

using namespace std;

#define lson l, mid, rt << 1

#define rson mid + 1, r, rt << 1 | 1

typedef long long ll;

const int N = 1e3 + 10;

const int INF = 0x3f3f3f3f;

const int MOD = 1e9 + 7;

const double EPS = 1e-10;

const double PI = acos (-1.0);

int vis[33];

char s[N];

int p1[33], p2[33];

int ans[33];

int main(void)    {

    int T, cas = 0; scanf ("%d", &T);

    while (T--) {

        scanf ("%s", &s);

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

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

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

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

        int len = strlen (s);

        for (int i=0; i<len; ++i)    {

            if (ans[s[i]-'A'] == -1)    ans[s[i]-'A'] = 0;

            if (p1[s[i]-'A'] == -1) p1[s[i]-'A'] = i;

            else    p2[s[i]-'A'] = i;

        }

        for (int i=0; i<len; ++i)   {

            if (vis[s[i]-'A'] == 1)  continue;

            int j = p1[s[i]-'A'] + 1;

            if (j == p2[s[i]-'A'])  {

                //ans[s[i]-'A'] = 1;  vis[s[i]-'A'] = 1;

                continue;

            }

            while (j < p2[s[i]-'A'])   {

                ans[s[i]-'A']++;

                j = p2[s[j]-'A'] + 1;

            }

            vis[s[i]-'A'] = 1;

        }

        for (int i=0; i<26; ++i)    ans[i]++;

        ans[s[0]-'A']--;

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

        for (int i=0; i<26; ++i)    {

            if (ans[i] <= 0)    continue;

            printf ("%c = %d\n", 'A' + i, ans[i]);

        }

    }

   //cout << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";

    return 0;

}

水 C Memory Overflow

/************************************************

* Author        :Running_Time

* Created Time  :2015/11/4 星期三 12:55:22

* File Name     :C.cpp

 ************************************************/

#include <cstdio>

#include <algorithm>

#include <iostream>

#include <sstream>

#include <cstring>

#include <cmath>

#include <string>

#include <vector>

#include <queue>

#include <deque>

#include <stack>

#include <list>

#include <map>

#include <set>

#include <bitset>

#include <cstdlib>

#include <ctime>

using namespace std;

#define lson l, mid, rt << 1

#define rson mid + 1, r, rt << 1 | 1

typedef long long ll;

const int N = 5e2 + 10;

const int INF = 0x3f3f3f3f;

const int MOD = 1e9 + 7;

const double EPS = 1e-10;

const double PI = acos (-1.0);

char s[N];

int main(void)    {

    int T, cas = 0;  scanf ("%d", &T);

    while (T--) {

        int n, k;   scanf ("%d%d", &n, &k);

        scanf ("%s", &s);

        int ans = 0;

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

            bool flag = false;

            for (int j=max (0, i-k); j<i; ++j)  {

                if (s[j] == s[i])   {

                    flag = true;    break;

                }

            }

            if (flag)   ans++;

        }

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

    }

   //cout << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";

    return 0;

}

暴力/高斯消元 E Poker End Games

只会暴力

/************************************************

* Author        :Running_Time

* Created Time  :2015/11/4 星期三 18:34:27

* File Name     :E.cpp

 ************************************************/

#include <cstdio>

#include <algorithm>

#include <iostream>

#include <sstream>

#include <cstring>

#include <cmath>

#include <string>

#include <vector>

#include <queue>

#include <deque>

#include <stack>

#include <list>

#include <map>

#include <set>

#include <bitset>

#include <cstdlib>

#include <ctime>

using namespace std;

#define lson l, mid, rt << 1

#define rson mid + 1, r, rt << 1 | 1

typedef long long ll;

const int N = 1e5 + 10;

const int INF = 0x3f3f3f3f;

const int MOD = 1e9 + 7;

const double EPS = 1e-10;

const double PI = acos (-1.0);

int main(void)    {

    int T, cas = 0; scanf ("%d", &T);

    while (T--) {

        int a, b;   scanf ("%d%d", &a, &b);

        double p = 1.0, round = 0, win = 0;

        int n = 1e6;

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

            if (a == b) {

                round += p * i;

                win += p * 0.5;

                break;

            }

            if (a > b)  {

                a -= b; b += b;

                round += p * i * 0.5;

                win += p * 0.5;

            }

            else if (a < b) {

                b -= a; a += a;

                round += p * i * 0.5;

            }

            p *= 0.5;

        }

        printf ("Case %d: %.6f %.6f\n", ++cas, round, win);

    }

   //cout << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";

    return 0;

}

　　

水 F Overlapping Characters

题意：判断能否根据某个点是'*'来区别出形状，必须是‘*'，其他的都是'.'才行。

/************************************************

* Author        :Running_Time

* Created Time  :2015/11/4 星期三 14:03:02

* File Name     :F.cpp

 ************************************************/

#include <cstdio>

#include <algorithm>

#include <iostream>

#include <sstream>

#include <cstring>

#include <cmath>

#include <string>

#include <vector>

#include <queue>

#include <deque>

#include <stack>

#include <list>

#include <map>

#include <set>

#include <bitset>

#include <cstdlib>

#include <ctime>

using namespace std;

#define lson l, mid, rt << 1

#define rson mid + 1, r, rt << 1 | 1

typedef long long ll;

const int N = 1e5 + 10;

const int INF = 0x3f3f3f3f;

const int MOD = 1e9 + 7;

const double EPS = 1e-10;

const double PI = acos (-1.0);

char s[40][20][50];

char ss[40];

int id[40];

int ans[20];

int f(char ch) {

    if (ch >= 'A' && ch <= 'Z') return ch - 'A';

    else    return 26 + (ch - '0');

}

int main(void)    {

    int n, m, cas = 0;   scanf ("%d%d", &n, &m);

    scanf ("%s", &ss);

    //printf ("%s\n", ss);

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

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

        id[f (ss[i])] = i;

        for (int j=0; j<17; ++j)    {

            scanf ("%s", s[i][j]);

        }

        /*

        for (int j=0; j<17; ++j)    {

            printf ("%s\n", s[i][j]);

        }

        */

    }

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

        scanf ("%s", &ss);

        int len = strlen (ss);

        for (int j=0; j<len; ++j)   {

            ans[j] = 0;

            if (id[f (ss[j])] == -1)    continue;

            for (int k=0; k<16 && !ans[j]; ++k)    {       //row

                for (int l=0; l<43 && !ans[j]; ++l)    {       //col

                    bool flag = true;

                    if (s[id[f (ss[j])]][k][l] != '*')    continue;

                    for (int ii=0; ii<len; ++ii)    {

                        if (ii == j)    continue;

                        if (id[f (ss[ii])] == -1)   continue;

                        if (s[id[f (ss[ii])]][k][l] != '.')  {

                            flag = false;   break;

                        }

                    }

                    if (flag)   ans[j] = 1;

                }

            }

        }

        printf ("Query %d: ", ++cas);

        for (int i=0; i<len; ++i)   {

            printf ("%c", ans[i] ? 'Y' : 'N');

        }

        puts ("");

    }

   //cout << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";

    return 0;

}

　　

DP I Learning Vector

题意：给了一些向量，问选出一些与x坐标轴组成的多变形面积最大

分析：开始以为贪心，因为很难想DP把之前的选的向量保存起来。看题解才知道，dp[i][j][h] 表示前i个选择了j个，最后高度为h组成的面积，那么状态转移时不需要知道之前的长度，用梯形面积公式累加多出来的面积就行了。另外，向量应该先极角排序。

/************************************************

* Author        :Running_Time

* Created Time  :2015/11/4 星期三 15:47:19

* File Name     :I_2.cpp

 ************************************************/

#include <cstdio>

#include <algorithm>

#include <iostream>

#include <sstream>

#include <cstring>

#include <cmath>

#include <string>

#include <vector>

#include <queue>

#include <deque>

#include <stack>

#include <list>

#include <map>

#include <set>

#include <bitset>

#include <cstdlib>

#include <ctime>

using namespace std;

#define lson l, mid, rt << 1

#define rson mid + 1, r, rt << 1 | 1

typedef long long ll;

const int N = 1e5 + 10;

const int INF = 0x3f3f3f3f;

const int MOD = 1e9 + 7;

const double EPS = 1e-10;

const double PI = acos (-1.0);

int dcmp(double x)  {       //三态函数，减少精度问题

    if (fabs (x) < EPS) return 0;

    else    return x < 0 ? -1 : 1;

}

struct Vec    {

    int x, y;

    Vec () {}

    Vec (int x, int y) : x (x), y (y) {}

}vs[55];

bool cmp(Vec A, Vec B)    {

    return dcmp (A.x * B.y - A.y * B.x) < 0;

}

int dp[55][55][2550];

int main(void)    {

    int T, cas = 0; scanf ("%d", &T);

    while (T--) {

        int n, k;   scanf ("%d%d", &n, &k);

        int H = 0;

        for (int x, y, i=1; i<=n; ++i) {

            scanf ("%d%d", &vs[i].x, &vs[i].y);

            H += vs[i].y;

        }

        sort (vs+1, vs+1+n, cmp);

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

        dp[0][0][0] = 0;

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

            for (int j=0; j<=i && j<=k; ++j)    {

                for (int h=0; h<=H; ++h)    {

                    if (dp[i][j][h] == -1)  continue;

                    dp[i+1][j][h] = max (dp[i+1][j][h], dp[i][j][h]);

                    if (j < k)  {

                        int hh = h + vs[i+1].y;

                        dp[i+1][j+1][hh] = max (dp[i+1][j+1][hh], dp[i][j][h] + (h + hh) * vs[i+1].x);

                    }

                }

            }

        }

        int ans = 0;

        for (int i=0; i<=H; ++i)    if (ans < dp[n][k][i])  ans = dp[n][k][i];

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

    }

   //cout << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";

    return 0;

}

　　

相关文章