2015年4月25日浙江省ACM比赛题解

68 阅读 0 评论 45 点赞

我是靠谱客的博主故意香烟，最近开发中收集的这篇文章主要介绍2015年4月25日浙江省ACM比赛题解，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

A、Ace of Aces（ZOJ 3869）
有n个人投票，求出来票数最多的那个人的id。如果多个人票数一样，输出“Nobody”。

#include <stdio.h>
#include <string.h>

#define N 1010

int num[N];

int main(void)
{
    int t;
    scanf("%d", &t);
    while (t--) {
          int n;
          scanf("%d", &n);
          memset(num, 0, sizeof(num));
          for (int i = 0; i <n ;++i) {
              int x;
              scanf("%d", &x);
              num[x]++;
          }
          int pos = 1;
          int flag = 0;
          for (int i = 1; i <=1000; ++i) {
              if (num[pos] < num[i]) {
                 pos = i; 
              }    
          }
          int m = 0;
          for (int i = 1; i <= 1000; ++i) {
              if (num[i] == num[pos]) {
                         ++m;
              }
          }
          if (m ==  1) {
                printf("%dn", pos);
          } else {
                printf("Nobodyn");
          }
    }
    return 0;
}

B、Team Formation（ZOJ 3870）
有n个数，从这n个数中任选两个数a,b，问有多少组数满足a^b > max(a, b)。
我们假定有两个数x，y。其中1

#include <cstdio>
#include <cstring>
#include <cstdlib>

#include <iostream>
#include <algorithm>

using namespace std;

#define N 100010

typedef long long ll;

// mp[i], number >= 2^i && < 2^(i+1)
ll num[N], mp[40];

ll get2(ll n)
{
    int res = 0;
    while (n) {
        n >>= 1;
        ++res;
    }
    return res - 1;
}

int main(void)
{
    int t;
    scanf("%d", &t);
    while (t--) {
        int n;
        scanf("%d", &n);
        for (int i = 0; i < n; ++i) {
            scanf("%d", &num[i]);
        }
        sort(num, num + n);
        memset(mp, 0, sizeof(mp));
        for (int i = 0; i < n; ++i) {
            int idx = get2(num[i]);
            mp[idx]++;
        }
        ll ans = 0;
        for (int i = 0; i < n; ++i) {
            int a = num[i];
            int m = 0;
            while (a) {
                if ((a & 1) == 0) {
                    ans += mp[m];
                    //printf("%d...n", mp[m]);
                }
                a >>= 1;
                ++m;
            }
        }
        printf("%dn", ans);
    }
    return 0;
}

D、Beauty of Array（ZOJ 3872）
定义了一个数组的美丽值，就是数组中不同数值加起来的和。让求的是给定一个数组中所有连续的子数组的美丽值的和。我们用dp[i]表示前i个数连续字数组的美丽值的和。
每加进来一个数，dp[i+1]要在加上dp[i]的基础上额外加上某些num[i + 1]，这取决于之前最后一次出现num[i + 1]的位置，用另外一个组数记录这个位置就行了。

#include <cstdio>
#include <cstring>
#include <cstdlib>

#include <iostream>
#include <algorithm>

using namespace std;

typedef long long ll;

#define N 100010

ll num[N], dp[N];
int vis[1000010];

int main(void)
{
    int t;
    scanf("%d", &t);
    while (t--) {
        int n;
        scanf("%d", &n);
        for (int i = 1; i <= n; ++i) {
            scanf("%lld", &num[i]);
        }
        memset(vis, 0, sizeof(vis));
        memset(dp, 0, sizeof(dp));
        dp[1] = num[1];
        ll sum = num[1];
        vis[num[1]] = 1;
        for (int i = 2; i <= n; ++i) {
            dp[i] = dp[i - 1];
            // 两种情况可以合成一种 
            //if (!vis[num[i]]) {
            //  vis[num[i]] = i;
            //  dp[i] += i * num[i];
            //} else {
                dp[i] += (i - vis[num[i]]) * num[i];
                vis[num[i]] = i;
            //}
            sum += dp[i];
        }
        printf("%lldn", sum);
    }
    return 0;
}

G、Lunch Time（ZOJ 3875）
简单的求中位数的，不过偶数的情况是取贵的那一个菜。因为有三种菜，计算三次就行了。

#include <cstdio>
#include <cstring>
#include <cstdlib>

#include <iostream>
#include <algorithm>

using namespace std;

#define N 110

struct Node {
    char name[N];
    int val;
    void input(void)
    {
        scanf("%s%d", name, &val);
    }
}x[N], y[N], z[N];

char ans[N * 2];
int cnt;

bool cmp(Node u, Node v)
{
    return u.val < v.val;
}

int f(Node node[], int n)
{
    //printf("%d %d %s...n", n / 2, node[n / 2].val, node[n / 2].name);
    ++cnt;
    strcat(ans, node[n / 2].name);
    if (cnt < 3) {
        strcat(ans, " ");
    }
    return node[n / 2].val;
}

int main(void)
{
    int t;
    scanf("%d", &t);
    while (t--) {
        int s, m, d;
        scanf("%d%d%d", &s, &m, &d);
        ans[0] = '';
        for (int i = 0; i < s; ++i) {
            x[i].input();
        }
        cnt = 0;
        sort(x, x + s, cmp);
        int res = f(x, s);
        for (int i = 0; i < m; ++i) {
            y[i].input();
        }
        sort(y, y + m, cmp);
        res += f(y, m);
        for (int i = 0; i < d; ++i) {
            z[i].input();
        }
        sort(z, z + d, cmp);
        res += f(z, d);
        printf("%d %sn", res, ans);
    }
    return 0;
}

H、May Day Holiday（ZOJ 3876）
这道题可以简化成已知2015年5月1号是周5，求其他年份的5月1号是周几。每过七天，周几就会重复，所以，经过的天数模上7就好了，这里需要注意，周日用0表示。因为还有通过2015年计算出来比2015年小的年份的5月1号的周几，所以，也可以通过减算出来。
一周只有七天，知道了周几，在来计算放几天假就很好计算了。

#include <cstdio>
#include <cstring>
#include <cstdlib>

#include <iostream>
#include <algorithm>

using namespace std;

#define N 10100

int week[N];

int leap(int y)
{
    if ((y % 4 == 0 && y % 100 != 0) || y % 400 == 0) {
        return 1;
    } else {
        return 0;
    }
}

int workday(int x)
{
    x = (x + 7) % 7;
    if (x >= 1 && x <= 5) {
        return 1;
    } else {
        return 0;
    }
}

int main(void)
{
    week[2015] = 5;
    for (int i = 2016; i < 10000; ++i) {
        int x = week[i - 1] + 365;
        if (leap(i)) {
            ++x;
        }
        week[i] = x % 7;
    }
    for (int i = 2014; i >= 1928; --i) {
        int x = week[i + 1] + 7 - (365 + leap(i + 1)) % 7;
        week[i] = (x + 7) % 7;
    }
    int t;
    scanf("%d", &t);
    while (t--) {
        int year;
        scanf("%d", &year);
        int x = week[year];
        int ans = 0;
        if ((x >= 3 && x <= 6)) {
            ans = 5;
        }
        if (x == 2 || x == 0) {
            ans = 6;
        }
        if (x == 1) {
            ans = 9;
        }
        printf("%dn", ans);
    }
    return 0;
}

J、Convert QWERTY to Dvorak（ZOJ 3878）
其实是一道很水的题，不过两种布局的键盘对应关系稍微有点扯淡。我是从键盘上一次按键得到的。

#include <cstdio>
#include <cstring>
#include <cstdlib>

#include <iostream>
#include <algorithm>

using namespace std;

#define N 1000010

char str[N];
char mp1[] = "`1234567890-=qwertyuiop[]\asdfghjkl;'zxcvbnm,./~!@#$%^&*()_+QWERTYUIOP{}|ASDFGHJKL:"ZXCVBNM<>? ";
char mp2[] = "`1234567890[]',.pyfgcrl/=\aoeuidhtns-;qjkxbmwvz~!@#$%^&*(){}"<>PYFGCRL?+|AOEUIDHTNS_:QJKXBMWVZ ";

int main(void)
{
    while (gets(str)) {
        int len = strlen(str);
        for (int i = 0; i < len; ++i) {
            int x = 0;
            for (x = 0; str[i] != mp1[x]; ++x) {
                ;
            }
            printf("%c", mp2[x]);
        }
        printf("n");
    }
    return 0;
}

L、Demacia of the Ancients（ZOJ 3880）
给定n个数，计算有多少个数比6000大就行了。

#include <stdio.h>

#define N 1000

int num[N];

int main(void)
{
    int t;
    scanf("%d", &t);
    while (t--) {
        int n;
        scanf("%d", &n);
        int cnt = 0;
        for (int i = 0; i <n ;++i) {
            int x;
            scanf("%d", &x);
            if (x > 6000) {
                cnt++;
            }
        }
        printf("%dn", cnt);
    }
    return 0;
}