2016中国大学生程序设计竞赛

参考自：http://blog.csdn.net/queuelovestack/article/details/52205196#t30

1001：A water problem

题意：

两个星球从宇宙大爆炸开始就产生了

Xixi星球一年有73天,Haha星球一年有137天

问宇宙大爆炸开始第N天是否是两个星球一年当中的第一天

题解：

就是求一个超大的数，长度是10000000，对137和73取余是否都等于0。

你要知道乘法和加法对取余运算是没有任何影响的，那么假如这个数是456，那么先对73取余456%73 == (4%73)*(100%73)+(5%73)*(10%73)+(6%73)*(1%73) 取余173同理。

那么我们就可以先预处理a[i],b[i]数组，存的分别是10^(i-1)%73和10^(i-1)%137的数，最后输入字符串，每个相乘，之后在相加，最后取余就好了。我写的先是int数组，居然爆了内存，之后幸好我还记得有short这么的类型，改完就可以了。

之后又看了篇博客，写的好简单，但思路和我是差不多的，= = 还是我菜啊。。

我的代码：

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
const int MAXN = 10000000 + 5 ;
const short MO1 = 73 ;
const short MO2 = 137 ;
int K;
char in[MAXN];
short a[MAXN], b[MAXN];

int main() {
    ll te = 1;
    for (int i = 0; i < MAXN; i++) {
        a[i] = te %= MO1;
        te *= 10;
    }
    te = 1;
    for (int i = 0; i < MAXN; i++) {
        b[i] = te %= MO2;
        te *= 10;
    }
    while (~scanf("%s", in)) {
        int an1 = 0, an2 = 0;
        int l = strlen(in);
        for (int i = 0; i < l; i++) {
            int d = in[i] - '0';
            an1 += d * a[l - i];
            an1 %= MO1;
            an2 += d * b[l - i];
            an2 %= MO2;
        }
        if (an1 == 0 && an2 == 0)printf("Case #%d: YES
", ++K);
        else printf("Case #%d: NO
", ++K);
    }
    return 0;
}

View Code

别人的代码：

#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<iostream>
//计算二进制中多少个1
#define bitnum(a) __builtin_popcount(a)
using namespace std;
const int N = 10000005;
const int M = 10005;
const int inf = 1000000007;
const int mod = 1000000007;
char s[N];
int main()
{
    int ans1,ans2,p=1,i,k;
    while(~scanf("%s",s))
    {
        ans1=ans2=0;
        k=strlen(s);
        for(i=0;i<k;i++)
        {
            ans1=(ans1*10+s[i]-'0')%73;
            ans2=(ans2*10+s[i]-'0')%137;
        }
        if(!ans1&&!ans2)
            printf("Case #%d: YES
",p++);
        else
            printf("Case #%d: NO
",p++);
    }
    return 0;
}

View Code

1004：Danganronpa

题意：

n种礼物,每种有a[i]个,所有的礼物可以作为普通礼物,也可以作为神秘礼物发放给孩子

现在从第一个人开始,每人可以收到一个普通礼物和一个神秘礼物,相邻两个人不能收到相同的普通礼物,神秘礼物没限制,发完为止

问最多有多少个人可以拿到两件礼物

题解：

这题数据有问题，写个sum/2就能过，做的时候就瞎想一通，不知道怎么的就a了，但看完别人博客发现写的不对，正确应该是这样的：

暂时先不考虑普通礼物的限制

那么最多有sum/2个人可以拿到两件礼物(sum为总的礼物件数,即a[1]+a[2]+……+a[n])

那么在考虑普通礼物限制的情况下,我们肯定先要发放普通礼物,直到不能发或超过sum/2为止,这时多出来的礼物就作为神秘礼物补齐发到过普通礼物的孩子

那么说明情况是不能发呢?因为相邻两人要获得不同的普通礼物

所以我们可以借助优先队列,每次将队首的两种礼物取出来发放

假设队首两种礼物的数量为a,b(a>b)

那么可以有2*b个孩子拿到普通礼物,没发完的第一种礼物还剩a-b件,丢进优先队列重新来过

最终得到答案ans,与sum/2取个小值就行了

代码：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = 10 + 5 ;
int a[MAXN], n, K;
void Solve() {
    ll sum = 0, ans = 0;
    priority_queue<int> priority;
    scanf("%d", &n);
    for (int i = 0; i < n; i++) scanf("%d", &a[i]), priority.push(a[i]), sum += a[i];
    int t = 0, te1 = 0, te2 = 0;
    while (!priority.empty()) {
        if (t) {
            te2 = priority.top();
            priority.pop();
            ans += te2 * 2;
            priority.push(te1 - te2);
        }
        else {
            te1 = priority.top();
            priority.pop();
        }
        t ^= 1;
    }
    printf("Case #%d: %lld
", ++K, min(sum / 2, ans));
}
int main() {
    int T;
    cin >> T;
    while (T--)
        Solve();
    return 0;
}

View Code