长沙理工大学ACMore编程协会2018年新生赛（重现赛）

古城微笑少年丶 2022-04-03 19:51 293阅读 0赞

A 送气球.jpg  
链接：https://ac.nowcoder.com/acm/contest/318/A  
来源：牛客网

题目描述  
ACM-ICPC程序设计大赛是大学级别最高的脑力竞赛，素来被冠以"程序设计的奥林匹克"的尊称。大赛至今已有近40年的历史，是世界范围内历史最悠久、规模最大的程序设计竞赛。比赛形式是：从各大洲区域预赛出线的参赛队伍，于指定的时间、地点参加世界级的决赛，由1个教练、3个成员组成的小组应用一台计算机解决7到13个生活中的实际问题。在正式赛场中，一个队伍每解决一个新的问题就会有一个相应的气球作为奖励送到这个队伍所在的位置。  
Dillonh作为这次ACM-ICPC的志愿者，当然是时刻关注着场上的过题情况的，每当有一个队伍通过新的问题的时候，他就会马上送上气球。但由于参赛队伍实在是太多了，他也不清楚每个队伍得到了多少个气球。在比赛结束之后，他拿到了一份这场比赛的题目提交情况，他想知道现场参加比赛的队伍每个队伍能获得气球，聪明的你能帮帮他吗？

输入描述:  
第一行包含一个整数T（T≤10），表示总共有T组测试样例；  
第二行输入一个整数n，m；  
n表示有多少个队伍参加这次的比赛（1≤n≤50）；  
m表示有多少条提交记录（1≤m≤1000）；  
接下来输入m行，每行输入格式如下：  
team\_id problem\_id submit\_status  
team\_id 代表着队伍的编号(1 <= team\_id <= n)；problem\_id代表着题目编号（为A~M的大写字母）;submit\_status代表着这个题目提交的结果（可能是"AC",“PE”,“TLE”,“MLE”,“WA”,“RE”,"CE"其中的一种）。  
hint：每次提交只有提交结果是"AC"的题目才可以得到气球。如果一个队伍如果通过同一个题目多次，他也只能获得一个气球。  
输出描述:  
对于每组样例  
第一行输出一行“Case \#x:”，x表示当前为第几组样例（详细见样例）；  
第二行输出n个数（每两个数之间用空格隔开）代表着第 i 个队可以获得的气球数量。（注意不要在每一行的末尾输出多余的空格）。  
示例1  
输入

1
    5 10
    1 A WA
    1 A AC
    2 A AC
    3 C TLE
    2 C TLE
    1 C AC
    3 A AC
    4 A AC
    1 A AC
    5 A WA

输出

Case #1:
    2 1 1 1 0

模拟，set去重。

#include<bits/stdc++.h>
    using namespace std;
    const int maxn=1000;
    set<char>s[maxn];
    int main(){
    	int t;
    	cin>>t;
    	int flag=1;
    	while(t--){
    		int n,m;
    		cin>>n>>m;
    		
    		for(int i=0;i<m;i++){
    			int index;
    			char b;
    			string c;
    			cin>>index>>b>>c;
    			if(c=="AC"){
    				s[index].insert(b);
    			}
    		}
    		printf("Case #%d:\n",flag);
    		
    		for(int i=1;i<n;i++){
    			cout<<s[i].size()<<" ";
    			s[i].clear();
    		}
    		cout<<s[n].size()<<endl;
    		s[n].clear();
    		flag++;
    	}
    	
    }

B 签到题  
链接：https://ac.nowcoder.com/acm/contest/318/B  
来源：牛客网

题目描述  
IG牛逼!!!

众所周知，IG是英雄联盟S8世界总决赛冠军，夺冠之夜，数亿人为之欢呼！

赛后某百分百胜率退役ADC选手的某表情包意外走红，某苟会长看到此表情包也想模仿。

于是有n个友爱的萌新决定每人都送会长一根长为ai面包。(数据保证没有面包的长度相等)

会长无聊时把面包摆成一排，他惊人地发现他喜欢这样一类区间，区间\[i, j\]满足条件：

区间里的面包没有比左端点i号面包短的，同时也没有比右端点j号面包长的。

Gey会长在思考这样一个问题：

所有满足条件的区间中j-i的最大值是多少？

输入描述:

t组数据。
    每组样例第一行输入整数n，接下来一行输入n个正整数。
    (t≤30, n≤1000, ai≤1000000)

输出描述:

输出满足条件的区间中j-i的最大值。

示例1  
输入

2
    4
    5 4 3 6
    4
    6 5 4 3

输出

1
    0

暴力，双重遍历确定起点和终点，终点为这一区间最大值时更新区间长度。

#include<bits/stdc++.h>
    using namespace std;
    const int maxn=1005;
    int a[maxn];
    int main(){
        int t;
        cin>>t;
        while(t--)
        {
            int n;
            cin>>n;
            for(int i=1;i<=n;i++)
                scanf("%d",&a[i]);
            int ans=0;
            for(int i=1;i<n;i++)
            {
                int mx=a[i];
                for(int j=i+1;j<=n;j++)
                {
                    if(a[j]<a[i]) break;
                    mx=max(mx,a[j]);
                    if(mx==a[j])
                        ans=max(ans,j-i);
                }
            }
            cout<<ans<<endl;
        }
        return 0;
    }

G LLLYYY的数字思维  
链接：https://ac.nowcoder.com/acm/contest/318/G  
来源：牛客网

题目描述  
LLLYYY很喜欢写暴力模拟贪心思维。某一天在机房，他突然抛给了队友ppq一  
个问题。问题如下：  
有一个函数f ()：  
int f(int x)\{  
int tmp = 0;  
while(x != 0)\{  
tmp += x % 10;  
x /= 10;  
\}  
return tmp;  
\}  
接着LLLYYY给定一个整数 c，要求在c范围内找两个整数a和b,使得a + b = c，且f(a) + f(b)的值最大。  
输入描述:

采用多组输入方式。
    每行输入一个整数 c (1≤c≤1012)。

输出描述:

对于每一个 c,找到一组 a,b ，使 f(a) + f(b)最大 且 a + b = c，输出这个f(a) + f(b)(0≤a,b≤c)。

示例1  
输入

35
    10000000000

输出

17
    91

说明

在第一个样例中，可以选择 a = 17,b = 18，这样得到的f(a) + f(b)值最大为 17。
    在第二个样例中, 可以选择 a = 5000000001,b = 4999999999.这样得到的f(a) + f(b)值最大为 91。

9越多越好

#include <bits/stdc++.h>
    using namespace std;
    typedef long long ll;
    int f(ll x){
        int tmp = 0;
        while(x != 0){
        tmp += x % 10;
        x /= 10;
        }
        return tmp;
    }
    int main(){
        ll c,n;
        while(cin>>c){
            n=0;int s=0;
            while((n*10+9)<c) n=n*10+9;
            printf("%d\n",f(n)+f(c-n));
        }
        return 0;
    }

J 王者荣耀  
链接：https://ac.nowcoder.com/acm/contest/318/J  
来源：牛客网

题目描述  
“无论何时何地，都会遵守约定”。“奋力逃吧”。“关于取下敌人性命这件事，也从不失约”。

小懒虫zmx平时最喜欢玩的游戏就是《王者荣耀》，在这款游戏中它也最喜欢百里守约这个英雄。最近，zmx准备冲国服百里，所以它开始练英雄，你有很多个时间段来练习英雄，每个时间段有一个开始时间点和结束时间点，以及可以获得的熟练度。不过现在你可以随意修改任意练习时间段的开始和结束时间点，但是你不能修改时间段的长度和获得的熟练度！由于要学习，你只能在固定时间段玩游戏，问你最多可以获得多少熟练度？

例如：你可以把\[2,3），修改为\[1,2）或者\[3,4）等等，他们的长度都是1。

注意：对于某个时间段，不管你有没有修改，必须练完整个时间段长度才能获得熟练度！

输入描述:

第一行，三个整数n,S,T(0<n<=1000,0<S<T<1000)代表n个时间段和你能在[S,T）时间段内玩游戏。
    
    接下来n行，每行三个整数a,b(0<a<b<1000),c(0<c<1e7)，用空格分开，代表时间段起始时间[a,b）和可以获得的熟练度。

输出描述:

输出一行，包括一个整数，表示zmx能获得的最大熟练度。

示例1  
输入

3 1 3
    1 3 5
    2 4 6
    4 7 8

输出

示例2  
输入

5 1 5
    1 2 1
    2 3 2
    1 3 3
    3 4 2
    3 6 4

输出

以时间间隔作为背包容量，  
每段时间间隔作为消耗，经验作为价值。背包。

#include<bits/stdc++.h>
    using namespace std;
    const int maxn=2000;
    int n;
    long long f[maxn];
    int main(){
        int s,t,v;
        scanf("%d%d%d",&n,&s,&t);
        v=t-s;
        for(int i=1;i<=n;++i) {
            int w;
            scanf("%d%d%d",&s,&t,&w);
            int c=t-s;
            for(int j=v;j>=c;j--) {
                f[j]=max(f[j],f[j-c]+w);
            }
        }
      
        cout<<f[v]<<endl;
        return 0;
    }

L 彪神666  
链接：https://ac.nowcoder.com/acm/contest/318/L  
来源：牛客网

题目描述  
在国外，666代表魔鬼，777代表上帝。

所以牛逼的彪神就非常不喜欢6这个数字。

有一天彪神突发奇想，，他想求一些书与6无关的数。

如果一个数能被6整除，或者它的十进制表示法中某位上的数字为6，则称其为与6相关的数。彪神要求所有小于等于N的与6无关的正整数的平方和。

输入描述:

第一行一个数T表示有T组数据。（T≤20）
    
    后面T行数每行一个N，表示求所有小于等于N的与6无关的正整数的平方和。(N≤106)

输出描述:

T行，每行一个数表示求所有小于等于N的与6无关的正整数的平方和。

示例1  
输入

5
    4
    5
    6
    7
    8

输出

30
    55
    55
    104
    168

暴力

#include<bits/stdc++.h>
    using namespace std;
    typedef long long ll;
    ll calculate(ll num){
        if(num%6==0)
            return 0;
        ll x=num;
        while(x){
            if(x%10==6)
                return 0;
            x/=10;
        }
        return num*num;
    }
    ll ans;
    int n,t;
    int main()
    {
        cin>>t;
        while(t--){
            cin>>n;
            for(ll i=1;i<=n;++i)
                ans+=calculate(i);
            cout<<ans<<endl;
            ans=0;
        }
        return 0;
    }

M 被打脸的潇洒哥  
链接：https://ac.nowcoder.com/acm/contest/318/M  
来源：牛客网

题目描述  
“画个圈圈诅咒你！”  
在一次青青草原ACM个人赛中，潇洒哥被喜洋洋以30s罚时压制，委屈的当了个第二。潇洒哥蹲在角落说出了他的口头禅，并画起了圈圈。  
突然，他想出了一个有趣的题目，跑去给喜洋洋做。喜洋洋看到题目后懵逼了，但是看到潇洒哥脸上欠揍的笑容就不爽，暗想一定要做出来狠狠的打潇洒哥的脸。  
于是，他以上厕所为名义跑出来用手机把题目发给了你，希望你能帮你做出来让他可以嘲讽潇洒哥。  
你收到的题目如下：  
平面上有n个圆，求使这n个圆两两相交（即每两个圆之间恰好有两个交点）后最多能把平面划分成多少个区域。

输入描述:

一个正整数t，表示有t(1≤t≤100)组数据。
    接下来t行，每行一个整数n(0≤n≤1000)，代表平面内圆的个数。

输出描述:

输出共t行。每行一个正整数，表示对应的n个圆将该平面划分成的最大的区域数。

示例1  
输入

3
    1
    2
    3

输出

2
    4
    8

说明

第一个样例，平面只有一个圆，此时将平面划分成圆内和圆外两个区域；
    第二个样例，平面上有两个圆，两圆相交可以将平面划分成四个区域（见下图）。

一个圆最多能把平面分成2个部分，  
2个圆最多能把平面分成4个部分；  
3个圆最多能把平面分成8个部分；  
现在加入第4个圆，为了使分成的部分最多，第4个圆必须与前面3个圆都有两个交点；

因此得6个交点将第4个圆的圆周分成6段圆弧，而每一段圆弧将原来的部分一分为二，即增加了一个部分，于是4个圆最多将平面分成8+6=14个部分，  
同理，5个圆最多将平面分成14+8=22个部分，  
一般地，n个圆最多分平面为：  
2+1×2+2×2+…+（n-1）×2，  
=2+2\[1+2+…+（n-1）\]，  
=n2-n+2；  
当n=10时，最多可以分成：102-10+2=92（部分），  
答：10个圆最多可以把平面分成92部分．  
故答案为：92．

这题注意特判0的情况

#include<bits/stdc++.h>
    using namespace std;
    typedef long long ll;
    int main(){
    	int t;
    	cin>>t;
    	while(t--){
    		ll n;
    		cin>>n;
    	    ll sum=n*n-n+2;
    	    
    	    cout<<sum<<endl;
    	}
    }