2015年浙江acm省赛题解（部分）

╰半夏微凉° 2022-05-27 08:13 273阅读 0赞

# 2015年浙江acm省赛题解 #

## A.Ace of Aces ##

题意：输入一堆数，选择出出现最多的数字，如果像2、2、3、3，次数一样的情况输出Nobody

思路：利用桶排序，排序，ok

#include<cstdio>
    #include<iostream>
    #include<algorithm>
    using namespace std;
    const int maxn = 1000+10;
    int n;
    int a[maxn];
    struct node
    {
        int num;
        int sum;
        bool operator < (const node&b)const {
            return sum > b.sum;
        }
    }b[maxn];
    
    
    void init()
    {
    
        for(int i=0; i<maxn; i++){
            a[i] = 0;
            b[i].num = 0;
            b[i].sum = 0;
        }
    }
    
    int main()
    {
        int T;
    
        cin >> T;
        while(T--){
            init();
            cin >> n;
            for(int i=0; i<n; i++){
                cin >> a[i];
                b[a[i]].sum++;
                b[a[i]].num = a[i];
            }
            sort(b, b+maxn);
            if(b[0].sum == b[1].sum){
                cout << "Nobody" << endl;
            }
            else{
                cout << b[0].num << endl;
            }
        }
    
    
        return 0;
    }

## B.Team Formation ##

题意：给出一堆数字，找出一组数字A，B。使得 A^B > max(A,B)， 如果成立，答案+1，找出所有成立的组数。

思路：异或值指的是二进制中相同值为0，不同值为1  
在本题中，如果A>B，A的二进制中从左边起第一个0的位置，与B中相对应的位置为1，那么条件一定成立，例如1010,100，异或值为1110  
所以，把数字从大到小排列（为的是尽可能的找出偏左的0），然后计算出当前数字的二进制存入mark数组中，把mark数组中0的位置用另一个数组record记录（统一样例中，记录一直保持，并且会自增），那么在每一次计算mark数组后，mark\[j-1\]，即数字二进制最高位，一定为1，那么只需知道当前record数组中记录j-1位置的值即可，即当前此位置（j-1）0个数的总和，这样的话，对于这个数字来说，已经找到了j-1位置可以使A^B > max(A,B)成立的部分组合。  
由于是从大到小排列，一定会枚举出所有最高位的1的位置。

#include<stdio.h>
    #include<string.h>
    #include<algorithm>
    #include<iostream>
    using namespace std;
    
    int num[100010];
    int cmp(int a,int b){
        return a>b;
    }
    int main(){
        int T,i,j,n;
        scanf("%d",&T);
        while(T--){
            scanf("%d",&n);
            for(i=1;i<=n;i++){
                scanf("%d",&num[i]);
            }
            sort(num+1,num+1+n,cmp);
            int record[100],mark[100];
            memset(record,0,sizeof(record));
            int ans=0;
            for(i=1;i<=n;i++){
                j=1;
                int x=num[i];
                while(x){
                    mark[j++]=x%2;
                    x/=2;
                }
                ans+=record[j-1];
                for(int k=1;k<j;k++)
                if(!mark[k]) record[k]++;
            }
            printf("%d\n",ans);
        }
        return 0;
    }

## D.Beauty of Array ##

题意：给出一串数字，找出所有部分和的和，部分和有一个条件，如果有重复数字，只加一遍，要求计算出总和。

思路：首先根据样例，2,3,3,2  
2 2+3 2+3+3 2+3+3+2  
3 3+3 3+3+2  
3 3+2  
2  
实际上真实的加和是  
2 2+3 2+3 2+3  
3 3 3+2  
3 3+2  
2  
我们不妨倒过来加（个数慢慢递增），计算方式是 个数 \* 数字  
首先是: 2 == dp\[1\] == 1 \* num\[1\];  
然后是: 8 == dp\[2\] == 2 \* num\[2\];  
为什么呢，倒数第一行只有一个数字，倒数第二行是倒数第一行加上两个3  
所以在数字不重复的情况下，前面的系数，默认是计算的次数（1和2），但是实际上其中是有重复数字的，那么要排除重复数字

我们需要标记一下重复数字出现的位置，为的是去重，例如在倒数第二行到倒数第三行时，增加的只有一个3，以此类推可以推出表达式

（当前位置-标记位置）\\\* num\[当前位置\] + dp\[上一个位置\]

最后叠加dp即可。

#include<cstdio>
    #include<cstring>
    #include<iostream>
    #include<algorithm>
    #define MAX 100010
    using namespace std;
    int book[MAX*10],num[MAX];
    long long int dp[MAX]; 
    /*dp[i] = (i-book[num[i]])*num[i] + dp[i-1]*/ 
    int main(void){
        int t,n;
        scanf("%d",&t);
        while(t--){
            memset(book,0,sizeof(book));
            scanf("%d",&n);
            for(int i=1;i<=n;i++)
                scanf("%d",&num[i]);
            reverse(num+1,num+1+n);
            for(int i=1;i<=n;i++){
                dp[i] = (i-book[num[i]])*num[i] + dp[i-1];
                book[num[i]] = i;
            }
            long long int sum = 0;
            for(int i=1;i<=n;i++) 
                sum += dp[i];
            printf("%lld\n",sum);
        }
        return 0;
    }

## G.Lunch Time ##

题意：给你三种饭，每种选出一个，选择的准则是，选出中等价格的，如果是偶数个，那么选出偏贵的那一种。

思路：创建一个结构体，分别存储名字和价格，对于三种饭，分别存储，分别排序，选择出符合条件的输出即可。

#include<cstdio>
    #include<iostream>
    #include<algorithm>
    using namespace std;
    const int maxn = 100+10;
    struct Node
    {
        string a;
        int cot;
    }s[maxn],m[maxn],d[maxn];
    
    bool cmp(Node a,Node b){
        return a.cot<b.cot;
    }
    
    int main()
    {
        int T;
        int S,M,D;
        while(cin >> T)
        {
            while(T--){
                init();
                cin >> S >> M >> D;
                for(int i=1; i<=S; i++){
                    cin >> s[i].a >> s[i].cot;
                }
                sort(s+1, s+S+1, cmp);
    
                for(int i=1; i<=M; i++){
                    cin >> m[i].a >> m[i].cot;
                }
                sort(m+1, m+M+1, cmp);
    
                for(int i=1; i<=D; i++){
                    cin >> d[i].a >> d[i].cot;
                }
                sort(d+1, d+D+1, cmp);
    
                int ans = s[S/2+1].cot + m[M/2+1].cot + d[D/2+1].cot;
                cout << ans << ' ';
                cout << s[S/2+1].a << ' ';
                cout << m[M/2+1].a << ' ';
                cout << d[D/2+1].a << endl;
            }
    
        }
    
    
    
        return 0;
    }

## H.May Day Holiday ##

题意：给出一个年份，输出5月1号可以放多长时间假期，计算规则是如果是周一，那么加上两端的周末，一共是9天，就是说，从5月1号开始到5月5号是一定放假的，如果有周末交集那么区最大值。，年份取值\[1928,9999\] 。

思路：从1928年开始计算平年闰年，对于输入的年份X，计算出x-1年中一共多少天，然后根据X是否明年闰年，加上从1月1号到5月1号的天数对7取余。  
注意周日取余后为0。取余天数对应放假天数：mp\[10\] = \{6,9,6,5,5,5,5\}；

#include<cstdio>
    #include<iostream>
    #include<algorithm>
    using namespace std;
    const int maxn = 10000;
    int mp[10] = {
       6,9,6,5,5,5,5};
    int ans[maxn];
    bool judge(int i)
    {
        if( (i%100 != 0 && i%4==0) || i %400==0)
            return true;
        return false;
    }
    
    void init()
    {
    
        for(int i=1929; i<=9999; i++)
        {
    
            if(judge(i-1)){
                ans[i]=ans[i-1] + 366;
            }
            else{
                ans[i] = ans[i-1] + 365;
            }
        }
    }
    
    int main()
    {
        init();
        int YEAR;
        int T;
        int ANS;
        while(cin >> T)
        {
            while(T--){
                cin >> YEAR;
                if(judge(YEAR)){
                    ANS = ans[YEAR] + 121;
                    ANS %= 7;
                    cout << mp[ANS] << endl;
                }
                else{
                    ANS = ans[YEAR] + 120;
                    ANS %= 7;
                    cout << mp[ANS] << endl;
                }
    
            }
        }
        return 0;
    }

## J.Convert QWERTY to Dvorak ##

题意：键盘如图，已经打乱，根据键盘对应输出正确的输入

思路：用map对应输出，没有告知输入数据的多少，用getline输入。

#include<cstdio>
    #include<iostream>
    #include<algorithm>
    #include<map>
    #include<cstring>
    using namespace std;
    map<char, char> mp;
    
    void init()
    {
        mp['_'] = '{';
        mp['-'] = '[';
        mp['='] = ']';
        mp['+'] = '}';
        mp['q'] = '\'';
        mp['Q'] = '"';
        mp['w'] = ',';
        mp['W'] = '<';
        mp['e'] = '.';
        mp['E'] = '>';
        mp['r'] = 'p';
        mp['R'] = 'P';
        mp['T'] = 'Y';
        mp['t'] = 'y';
        mp['Y'] = 'F';
        mp['y'] = 'f';
        mp['U'] = 'G';
        mp['u'] = 'g';
        mp['I'] = 'C';
        mp['i'] = 'c';
        mp['o'] = 'r';
        mp['O'] = 'R';
        mp['P'] = 'L';
        mp['p'] = 'l';
        mp['{'] = '?';
        mp['['] = '/';
        mp[']'] = '=';
        mp['}'] = '+';
        mp['S'] = 'O';
        mp['s'] = 'o';
        mp['D'] = 'E';
        mp['d'] = 'e';
        mp['F'] = 'U';
        mp['f'] = 'u';
        mp['G'] = 'I';
        mp['g'] = 'i';
        mp['H'] = 'D';
        mp['h'] = 'd';
        mp['J'] = 'H';
        mp['j'] = 'h';
        mp['K'] = 'T';
        mp['k'] = 't';
        mp['L'] = 'N';
        mp['l'] = 'n';
        mp[';'] = 's';
        mp[':'] = 'S';
        mp['\''] = '-';
        mp['"'] = '_';
        mp['Z'] = ':';
        mp['z'] = ';';
        mp['X'] = 'Q';
        mp['x'] = 'q';
        mp['C'] = 'J';
        mp['c'] = 'j';
        mp['V'] = 'K';
        mp['v'] = 'k';
        mp['B'] = 'X';
        mp['b'] = 'x';
        mp['N'] = 'B';
        mp['n'] = 'b';
        mp[','] = 'w';
        mp['<'] = 'W';
        mp['.'] = 'v';
        mp['>'] = 'V';
        mp['/'] = 'z';
        mp['?'] = 'Z';
    }
    string s;
    int main()
    {
        init();
        while(getline(cin,s)){
            int len = s.size();
            for(int i=0;i<len;i++){
                if(mp[s[i]]){
                    printf("%c",mp[s[i]]);
                }else{
                    printf("%c",s[i]);
                }
            }
            printf("\n");
        }
        return 0;
    }

## L.Demacia of the Ancients ##

题意：输入一串数字，计算出比6000大的数字的个数

思路：边输入边计算，然后输出

#include<cstdio>
    #include<iostream>
    #include<algorithm>
    using namespace std;
    
    int main() {
        int t, n, x, ans=0;
        cin >> t;
        while(t--) {
            cin >> n;
            ans=0;
            for(int i = 1;i <= n; i++) {
                cin >> x;
                if(x > 6000) ans++;
            }
            cout << ans << endl;
        }
    }