第八届郑州轻工业学院ACM（程序设计大赛）校内预选赛

郑州轻工业学院有一个大赛，把几个有趣的题目分享一下。下面是题目连接，喜欢了就点点。。。

斗破苍穹  

礼上往来  

统计人数  

神の数  

炉石传说  

Mathematics and Geometry 

马拉松后记

 

斗破苍穹

Time Limit: 1 Sec  Memory Limit: 128 MB Submit: 205  Solved: 46
SubmitStatusWeb Board

Description

有一天, 我们帅气的LC来到加玛帝国. 有时候, 缘分就是这么奇怪, LC和加玛帝国的公主一见钟情, 奈何公主的父王不同意, 因为他觉得LC除了长得特别帅之外, 并没有一技之长.

LC对此呵呵一笑, 他说, 我可是创新实验室走出来的学生, 我会的技能可多着呢, 先说个简单的吧, 只要你给我任意一串字符串, 我就能立马算出这串字符串当中最长回文串的长度. 国王很是吃惊, 说要考一考LC.

于是国王想让你帮忙写一个程序, 用来比对LC的答案, 快来帮帮国王吧!

Input

第一行输入一个T(T <= 50), 表示一共有T组测试数据. 接下来T行, 每行为一组由小写字母组成, 长度不超过10^5的字符串.

Output

每行一个整数X, 表示该组字符串中所包含的最长回文长度.

Sample Input

3 aba abc aabaa

Sample Output

3 1 5
题解：manacher算法：
代码：
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<vector>
#define mem(x,y) memset(x,y,sizeof(x))
using namespace std;
typedef long long LL;
const int INF = 0x3f3f3f3f;
const int MAXN = 200100;
int p[MAXN];
char str[MAXN],s[MAXN];
int Manacher(char *s,int len){
    mem(p,0);
    p[0] = p[1] = 1;
    int id = 1,mx = 1;
    int ans=0;
    for(int i = 2;i < len; i++){
       if(mx>i)
            p[i]=min(p[2*id-i],mx-i);
        else
            p[i]=1;
        while(s[i-p[i]] == s[i+p[i]])
            p[i]++;
        if(p[i] + i > mx)mx = p[i] + i,id = i;
        ans = max(ans,p[i]);
    }
    return ans - 1;
}
int main(){
    int T;
    scanf("%d", &T);
    while(T--){
        scanf("%s",str);
        int len = strlen(str);
        s[0]='@';
        for(int i = 0; i < len; i++){
            s[2*i + 1] = '#';
            s[2*i + 2] = str[i];
        }
        s[2 * len + 1] = '#';
        printf("%d
", Manacher(s, 2*len + 2));
    }
    return 0;
}
/**************************************************************
    Problem: 1861
    User: handsomecui
    Language: C++
    Result: Accepted
    Time:286 ms
    Memory:2500 kb
****************************************************************/
View Code

礼上往来

Time Limit: 1 Sec  Memory Limit: 128 MB Submit: 225  Solved: 69
SubmitStatusWeb Board

Description

每当节日来临，女友众多的xxx总是能从全国各地的女友那里收到各种礼物。

有礼物收到当然值得高兴，但回礼确是件麻烦的事！

无论多麻烦，总不好意思收礼而不回礼，那也不是xxx的风格。

　　

现在，即爱面子又抠门的xxx想出了一个绝妙的好办法：他准备将各个女友送来的礼物合理分配，再回送不同女友，这样就不用再花钱买礼物了！

　　

假设xxx的n个女友每人送他一个礼物（每个人送的礼物都不相同），现在他需要合理安排，再回送每个女友一份礼物，重点是，回送的礼物不能是这个女友之前送他的那个礼物，不然，xxx可就摊上事了，摊上大事了......

　　

现在，xxx想知道总共有多少种满足条件的回送礼物方案呢？ 

Input

输入数据第一行是个正整数T，表示总共有T组测试数据（T <= 100）； 每组数据包含一个正整数n，表示叽叽哥的女友个数为n( 1 <= n <= 100 )。

Output

请输出可能的方案数，因为方案数可能比较大，请将结果对10^9 + 7 取模后再输出。 每组输出占一行。

Sample Input

3 1 2 4

Sample Output

0 1 9
题解：错排公式；
代码：
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
using namespace std;
const int INF = 0x3f3f3f3f;
const int MOD = 1e9 + 7;
typedef long long LL;
LL f[110];
int main(){
    int T, n;
    f[1] = 0;
    f[2] = 1;
    f[3] = 2;
    f[4] = 9;
    for(int i = 5; i <= 100; i++){
        f[i] = (i - 1) * f[i - 2] % MOD + (i - 1) * f[i - 1] % MOD;
        f[i] %= MOD;
    }
    scanf("%d",&T);
    while(T--){
        scanf("%d", &n);
        printf("%lld
", f[n]);
    }
    return 0;
}
 
/**************************************************************
    Problem: 1867
    User: handsomecui
    Language: C++
    Result: Accepted
    Time:0 ms
    Memory:1328 kb
****************************************************************/
View Code

统计人数

Time Limit: 1 Sec  Memory Limit: 128 MB Submit: 303  Solved: 77
SubmitStatusWeb Board

Description

HS想要统计镇上总共有多少人，但是他并不想一个一个的去数有多少个人，他想了一个其他的方法，他在镇上找了N个人，然后问每一个人“你知道 除你之外 镇上和你姓氏相同的人有多少个吗？”，现在HS想要知道，镇上最少有多少人？我们保证HS不会问同一个人两次。

Input

第一行一个正整数T（T <= 100)，表示T组测试样例; 每组样例有两行， 第一行一个正整数N(N <= 50)，表示被问到的人数， 第二行N个数（在0 ～ 1000000之间)，表示每个人的回答。

Output

每行输出一个正整数，表示镇上最少人数。

Sample Input

2 4 1 1 2 2 1 0

Sample Output

Case 1: 5 Case 2: 1
题解：其实就是相同数字的个数不能大于x+1；模拟下就好了；
代码：
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
using namespace std;
const int INF = 0x3f3f3f3f;
int a[100];
int main(){
    int T, N, kase = 0;
    scanf("%d", &T);
    while(T--){
        scanf("%d", &N);
        for(int i = 0; i < N; i++){
            scanf("%d", a + i);
        }
        sort(a, a + N);
        int cnt = 1, ans = a[0] + 1;
        for(int i = 1; i < N; i++){
            if(a[i] == a[i - 1]){
                cnt++;
                if(cnt > a[i] + 1){
                    cnt = 1;
                    ans += a[i] + 1;

                }
            }
            else{
                cnt = 1;
                ans += a[i] + 1;
            }
        }
        printf("Case %d: %d
", ++kase, ans);
    } 
    return 0;
}
/**************************************************************
    Problem: 1865
    User: handsomecui
    Language: C++
    Result: Accepted
    Time:0 ms
    Memory:1328 kb
****************************************************************/
View Code

神の数

Time Limit: 1 Sec  Memory Limit: 128 MB Submit: 204  Solved: 36
SubmitStatusWeb Board

Description

有一天，有一个小朋友送给萌萌的韬韬一本书，书的名字叫做《数》，韬韬对于数字有着无比的狂热，一拿到这本书就沉迷于数的世界无法自拔，不久韬韬看到一个数字被称为神の数字——36，觉得很好奇，从未听说过，又继续往下看，发现原来36好厉害呢，有好多神奇的性质。

   36 = (1 + 3 + 5 +7) + (2 + 4 + 6 + 8) 是前4个奇数与前4个偶数的和

   36 = 1^3+2^3+3^3 还是前3个自然数的立方和

   《三十六计》是一个神奇的东西，可以解决好多神奇的问题，是杰出的军事家孙子大大写就的一篇传世巨擘。

   人体能承受的安全电压是36V，好巧耶。

   … …

   韬韬看到了这么多36的神奇性质，想到了一个问题，给定区间范围[l, r]内有多少跟36相关的数呢，韬韬在想什么样的数是和36相关的呢，换句话说，韬韬在思考如何给“36相关的数”一个定义。

   一个“36相关的数”，首先它的十进制表示中必须得有36吧，嘛，相关度还得够，一定不能有单个的3或者6，单个的3或6不是真的36呀。36036是一个“36相关的数”，而36633不是呢。好像漏掉了什么东西，“这还不够”，韬韬说道。

   一个“36相关的数”，它必须能被36整除，这才是真的和36相关嘛，韬韬发现在[1, 36]区间中只有36这个数满足这些要求。韬韬想知道第二个这样的数是多少呢，很遗憾，貌似100以内找不到这样的数了呢。

   韬韬非常沮丧，他热切地想知道区间[l, r]中“36相关的数”有多少。好像又漏掉了点什么呢，韬韬还想知道[l, r]区间中这些36相关数中有多少“36”存在，毕竟是36嘛。

   既然韬韬现在很沮丧，一点算数的心情都没有了，但是他很想知道上面提到的这些数呢，亲爱的小伙伴你可以帮帮他嘛？

Input

第一行是测试样例数 t (1 <= t <= 10^5) 接下来t行每行包括两个正整数 l, r (1  <=  l <=  r  <=  10^5).

Output

输出包括t行，每行对应一次询问，每行包括2个数 — 区间[l, r]中36相关数的数量, 36相关数中“36”的数量。

Sample Input

2 1 36 1 3636

Sample Output

1 1 8 9

HINT

[1, 3636]中36相关数有36, 360, 936,1368, 1836, 2736, 3600, 3636这8个, “36”出现了9次

题解：
这个水题。。。木啥说的；
代码：
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
using namespace std;
const int INF = 0x3f3f3f3f;
const int MAXN = 1e5 + 100;
int d1[MAXN],d2[MAXN];
void find(int x, int &n1, int &n2){
    n1 = 0; n2 = 0;
//  int p = x;
    while(x){
        if(x % 100 == 36){
            n1++;
            n2++;
            x /= 100;
            continue;
        }
        else if(x % 10 == 3 || x % 10 == 6){
            n1 = 0;n2 = 0;
            return;
        }
        x /= 10;
    }
    if(n1 > 1)n1 = 1;
    //if(n1)printf("%d
",p);
}
int main(){
    int T, l, r;
    memset(d1,0,sizeof(d1));
    memset(d2,0,sizeof(d2));
    for(int i = 36;i < MAXN; i++){
        int n1 = 0,n2 = 0;
        if(i % 36 == 0)find(i,n1,n2);
        d1[i] = d1[i - 1] + n1;
        d2[i] = d2[i - 1] + n2;
    }
    scanf("%d",&T);
    while(T--){
        scanf("%d%d",&l,&r);
        printf("%d %d
",d1[r] - d1[l - 1], d2[r] - d2[l - 1]);
    }
    return 0;
}
/**************************************************************
    Problem: 1863
    User: handsomecui
    Language: C++
    Result: Accepted
    Time:99 ms
    Memory:2108 kb
****************************************************************/
View Code

炉石传说

Time Limit: 1 Sec  Memory Limit: 128 MB Submit: 228  Solved: 71
SubmitStatusWeb Board

Description

最近韬韬周围的小伙伴们都在玩炉石传说, 感觉好厉害的样子, 可是韬韬早都不玩游戏了呢, 自从入坑ACM之后。“不能没有我的蜡烛”, 韬韬天天都能听到这样的句子 - -

   听说炉石传说开放了新冒险模式——探险者协会！开放了一种新的技能：“发现”！

   它的效果是提供三张卡牌(随从卡 / 法术卡), 你可以获得任意一张, 并丢掉另外两张。

   现在你可以使用 n 次“发现”技能, 当然到最后你会得到 n 张卡牌, 如今已经给出每次使用技能后可以选择的三张卡的属性, 韬韬很想知道能否获得至少 a 张随从卡以及 b 张法术卡。

   亲爱的小伙伴你可以帮帮韬韬嘛？

Input

第一行是测试样例数t (1 <= t <= 1000) 每组输入数据的第一行是三个正整数 n, a, b含义见上述 数据范围1 <= n <= 1000 , 1 <= a, b <= n 接下来 n 行, 每行三个数(0或1), 0代表随从卡, 1代表法术卡

Output

对于每组数据, 输出一行 YES 或者 NO

Sample Input

2 1 1 0 1 1 1 3 1 2 0 1 1 0 0 0 1 1 1

Sample Output

NO YES

HINT

对于第一组样例, n=1,a=1, b=0, 使用1次“发现”技能, 至少获得1张随从卡.由于提供的3张都是法术卡(3个1), 所以不能达到要求

   对于第二组样例, n=3,a=1, b=2, 使用3次“发现”技能, 至少获得1张随从卡, 2张法术卡. 那么只要在第一次和第三次选法术卡, 第二次选随从卡即可

题解：又是水题。。。
代码：
  
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
using namespace std;
const int INF = 0x3f3f3f3f;
int main(){
    int T, n, a, b;
    scanf("%d",&T);
    while(T--){
        int na = 0,nb = 0,nc = 0;
        scanf("%d%d%d",&n, &a, &b);
        int x,y,z;
        for(int i = 0; i < n; i++){
            scanf("%d%d%d",&x,&y,&z);
            if(x == y && x == z && x == 0)
                na++;
            else if(x == y && x == z && x == 1)
                nb++;
            else
                nc++;
        }
        if(na < a){
            nc -= (a - na);
        }
        if(nb < b){
            nc -= (b - nb);
        }
        if(nc < 0)puts("NO");
        else puts("YES");
    }
    return 0;
}
/**************************************************************
    Problem: 1864
    User: handsomecui
    Language: C++
    Result: Accepted
    Time:313 ms
    Memory:1328 kb
****************************************************************/
View Code

Mathematics and Geometry

Time Limit: 1 Sec  Memory Limit: 128 MB Submit: 193  Solved: 50
SubmitStatusWeb Board

Description

给你一个n，求方程 2x + y + 2z = n 解的个数，其中x, y, z, n 都是非负整数

Input

第一行一个整数T(T<=1000)，表示测试数据组数，接着T行，每行一个整数n(n<=1000000)

Output

每组数据输出一行Case #x: ans 其中x表示样例组数，ans表示解的个数

Sample Input

3 1 2 3

Sample Output

Case #1: 1 Case #2: 3 Case #3: 3
题解：规律挺好找，但是会超时，所以要进一步推规律，注意奇数偶数有区别；
代码：
#include<stdio.h>
#include<string.h>
#include<math.h>
#include<map>
#include<stack>
#include<algorithm>
#include<iostream>
#define INF 0x3f3f3f3f
#define ull unsigned long long
#define ll long long
#define IN __int64
#define N 1010
#define M 1000000007
using namespace std;
const int MAXN = 1000010;
int main()
{
    int T=1,t,n,m,i,j,x,y;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d",&n);
        if(n&1)
            j=1;
        else
            j=0;
        ll sum=0;
        if(n&1){
        ll k = (n - j) / 2 + 1;
    //  printf("k=%lld
",k);
         
        sum = (k * n- k * k )/2;
        sum += k;
        printf("Case #%d: %lld
",T++,sum );
        }
        else{
            ll k = (n - j) / 2 + 1;
    //  printf("k=%lld
",k);
         
        sum = (k * n - k*(k-1))/2;
        sum += k;
        printf("Case #%d: %lld
",T++,sum);
        }
    }
    return 0;
}
/**************************************************************
    Problem: 1869
    User: handsomecui
    Language: C++
    Result: Accepted
    Time:0 ms
    Memory:1328 kb
****************************************************************/

马拉松后记

Time Limit: 1 Sec  Memory Limit: 128 MB Submit: 54  Solved: 21
SubmitStatusWeb Board

Description

毛毛雨学姐跑完了半程马拉松，接下来决定去参加山地越野赛了，主办方听说毛毛雨学姐是一位ACMer，就想让她来帮忙解决一下
赛场问题：已知在山地越野场地有N座土坡（1<=N<=1000），每座土坡都有一个在0到100之间的整数海拔，考虑到参赛选手
大多都是业余选手，所以主办方决定将土坡的高度差限定在17米（即最高和最低相差不超过17米），然而想改变一座土坡x米需
要花费x^2元（改变只能是整数x米），请你们帮助毛毛雨学姐来计算出主办方最少的支出。

Input

第一行：一个整数N
第二行至第N+1行：每座土坡的高度
多组测试样例

Output

主办方的最少支出

Sample Input

5 4 20 1 21 24

Sample Output

18

HINT

 

Source

题解：暴力就行。。。注意是每个数字的暴力。。。

代码：

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<cmath>
 5 #include<algorithm>
 6 using namespace std;
 7 const int MAXN = 1010;
 8 typedef long long LL;
 9 int num[MAXN];
10  
11 int main(){
12     int N;
13     while(~scanf("%d",&N)){
14         for(int i = 0; i < N; i++){
15             scanf("%d",num + i);
16         }
17         sort(num, num + N);
18         LL ans = (LL)0x3f3f3f3f3f3f3f3f;
19         for(int i = num[0]; i < num[N - 1]; i++){
20             LL temp = 0;
21             for(int j = 0; j < N; j++){
22                 if(num[j] < i){
23                     temp += (i - num[j]) * (i - num[j]);
24                 }
25                 else if(num[j] > i + 17){
26                     temp += (num[j] - i - 17) * (num[j] - i -17);
27                 }
28             }
29             ans = min(ans, temp);
30         }
31         printf("%lld
",ans);
32     }
33     return 0;
34 }
35 /**************************************************************
36     Problem: 1870
37     User: handsomecui
38     Language: C++
39     Result: Accepted
40     Time:6 ms
41     Memory:1332 kb
42 ****************************************************************/
【推广】 免费学中医，健康全家人
原文地址：https://www.cnblogs.com/handsomecui/p/5383644.html