暑假第一次积分赛

68 阅读 0 评论 45 点赞

我是靠谱客的博主兴奋鱼，最近开发中收集的这篇文章主要介绍暑假第一次积分赛，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

A 辞树的QAQ水题
题目描述蒟蒻的辞树又被吊打了嘤嘤嘤。留下了属于弱者的眼泪QAQAQAQAQAAQAAQA······ 现在我们定义辞树的悲伤值 F 。F的值为主串中子序列为”QAQ”的个数。注意字母“QAQ”不一定是连续的，但是字母的顺序应该是准确的。
输入输入一个整数T（0 ≤ T ≤ 20）,代表有T组数据。每组数据会给出一个字符串S,长度为len，0 < len ≤ 1000000
输出
根据每组的字符串，输出辞树的悲伤值F，每组数据换行。
输入样例
2

QAQAQYSYIOIWIN

QAQQ
输出样例
4

解题思路：

此题关键在于 "QAQ" 不一定是连续的，所以可以发现，

当一个 A 前的 Q 的数量为 L ，后面 Q 的数量为 R 时，其所构成的 QAQ 序列的数量一定是 L * R 。

故我们以 A 为中心，分析并记录每一个 A 前后Q 的数量 L 和 R ；以结构体表示为 a[i].L 和 a[i].R

其所构成的 QAQ 的总数量就为 sum :

伪代码

for i in n :

sum += a[i].L * a[i].R ;

B 排序去重
时间限制内存限制出题人 1 Second 512 Mb
问题描述
用计算机生成了N个1到1000之间的随机整数（1≤N≤1000 ），对于其中重复的数字，只保留一个，把其余相同的数去掉，然后再把这些数从小到大排序。
输入
多组输入，有2行，第1行为1个正整数，表示所生成的随机数的个数： N 第2行有N个用空格隔开的正整数，为所产生的随机数。
输出
也是2行，第1行为1个正整数M，表示不相同的随机数的个数。第2行为M个用空格隔开的正整数，为从小到大排好序的不相同的随机数
输入样例
15

5 8 55 2 6 4 7 56 47 18 222 546 254 56 32
输出样例
14 2 4 5 6 7 8 18 32 47 55 56 222 254 546

在此就不说了，一个简单的 set 集合去重应用，谁做谁开心

C 简单的划分问题
时间限制内存限制出题人 1 Second 512 Mb
题目描述
A国有一支由n个人组成的小队，小队中每个人的位置是固定的，并且每个人都有对应的能力值，这些人的能力值构成一个序列，现在A国要将这一支小队分为x个小组，并对这x个小组进行能力分析，这x个小组每个小组都有一个最低能力值，一共x个，问怎样划分才能使这x个能力最弱的人中能力值最高的那个人的能力值最大，并输出这个最大值
输入
多组输入，处理到文件结束第一行输入n和x,1 < n <= 1500,1 <= x <= n <= 1500,代表人数和要划分的组数第二行输入n个整数，代表n个人的能力值
输出
最大的能力值
输入样例
8 1 1 2 3 4 5 9 3 6
输出样例
1
输入样例
7 6 997 425 851 236 789 527 195
输出样例
997
注意
划分小组时人的位置顺序不能改变

解题思路

当 x==1时，发现只能取最小值min

当x==n时，发现我们可以把每一个人分为一组，故可以取最大值max

当x==2时，分为三种情况

第一种，将第一个人作为一组，将后面的人分为一组

第二种，将最后一个人作为一组，前面的人为一组

第三种，从中间分开，作为两组

可以发现，我们取第一个人和最后一个人中最大的值

当x==3时，我们可以把最大的值孤立作为一组，故取最大值max

当x >3 时，同上

D NHK协会的阴谋
时间限制内存限制出题人 1 Second 512 Mb
题目描述
“阴谋啊，这一定是NHK协会的阴谋” 事实上，NHK协会是真实存在的，NHK协会会为每个人分配一个特征码(只包含大写字母的字符串)以及一个改变系数Q。然后NHK协会会根据以下规则将满足条件的人列为NEET:规定特征码中所有的0N0,0H0,0K0最多能组合成”NHK”的个数为P 。要求1.P > K 2.Q < L; K,L是常数。找出真正的NEET之后，对这些人按以下规则排序:对每个人计算出X = P∗(L−Q)，按X由大到小对这些人进行排序，对于X相同的人按照姓名字典序最小排序，保证给出的姓名都不相同。
输入 T(1 ≤ T ≤ 100)组数据第二行输入K,L,M，K,L依次对应题目描述中的K,L。 M表示一共M个人然后M行每行输入每个人的信息依次为姓名,特征码,改变系数Q. 姓名是长度不超过20的字符串，特征码是长度不超过1000的字符串，输入的数值均为正整数。 1 ≤ M ≤ 100,1 ≤ L ≤ 100,1 ≤ K,Q ≤ 10
输出
对排好序且满足条件的人的姓名分别输出一行如果没有NEET则输出”FINE!”输出不包含引号
输入样例
2

3 28 3

SAKI DDDDD 4

ABB NDSHKHHKKNN 3

BCC HHKKNN 5
4 36 3

SATO NHKNHKNHKNHKNHKNHK 1

QUEEN NHKNHKQRNRHRKHNRKNHK 8

DIOOO WRYYYYYNHKNHKNHKKHNNHK 5
输出样例
FINE!
SATO

DIOOO

QUEEN

解题思路

分别统计序列中 H ，K ，N 的数量，组成 NHK 序列的数量就是三者数量的最小值

其次，便是对map容器的应用，即 map< string, map< string ,int >

E Pair and Straight
时间限制内存限制出题人 3 Second 32768 kB
题目描述
人生当苦无妨，良人当归即好。 —《雪中悍刀行》
我们现在有很多很多很多数字，现在我们想知道这些数字里面有最多有多少个 P 与 S。
我们定义 P的含义为大小相同的两个数字的个数，例如一组数字里面有两个1 那么这两个1就是一个P,四个1,那么就是2个P。 S的含义为连续的是三个数字，例如1,2,3就是一个S。
还请acmer 请将可以得到的最多的P与S输出
输入第1行输入T(1 ≤ T ≤ 20)组数据第2行输入n(1 ≤ n ≤ 1e5) 第3行输入n个数字x(1 ≤ x ≤ n),
输出
输出最多的 P + S
输入样例
4

1 2 3 4 5 6 7

1 1 1 2 2 2 3 3 3

2 2 3 3 3 3

1 2 3 3 4 5
输出样例
2

HINT

Case 1（1，2，3）（4，5，6）

Case 2（1，2，3）（1，1）（2，2）（3，3）

Case 3（2，2）（3，3）（3，3）

Case 4（1，2，3）（3，4，5）

解题思路

该题是贪心的思想，因 P 和 S 等价，构成一个P 需要需要两个数，构成一个S 则需要三个数，根据贪心算法，取最优解，先取 P的数量，再求S 的数量

#include <iostream>
#include <stdio.h>
#include <string.h>
 
using namespace std;
 
const int N = 1e6+10;
int data[N];
 
int main()
{
    int n,a,t;
    cin >> t;
    while(t--) {
    	cin >> n;
        memset(data, 0, sizeof(int) * (n + 2));
        for(int i = 1; i <= n; i++) {
        	cin >> a;
            data[a]++;
        }
        long long ans = 0;
        for(int i = 1; i <= n; i++) {
            ans += data[i] / 2;
            data[i] %= 2;
            if(data[i - 1] && data[i] && data[i + 1]) {
                ans++;
                data[i- 1]--;
                data[i]--;
                data[i + 1]--;
            }
        }
        cout << ans << endl; 
    }
    return 0;
}

F 画线条
时间限制内存限制出题人 1 Second 512 Mb
题目描述
zxy无聊的在纸上划着线条，队友不能容忍，于是借机给他出了一个简单的问题，让他把自己画的n线条选择一部分摆到数轴上，且两两没有重合,然后问他最大的摆放数量k
输入
第一行为一个正整数 n；在接下来的 n 行中，每行有 2个数 ai,bi描述每条线段。 n,ai,bi(0 < n,ai,bi ≤ 106)
输出
输出一个整数，为 k的最大值。
输入样例
3

0 2

2 4

1 3
输出样例
2

解题思路

先将结构体定义的数组，按右端点进行从小到大的排序。

当为第一个元素时，与第二个元素进行对比，就是第一个的右端点，小于第二个的左端点时，说明两区间没有相交，数量k+1，并更新右端点（将第二个的右端点更新为右端点）；以此类推。。。

#include <iostream>
#include<algorithm>
#include<set>
#include<map>
#include<vector>
#include<string>
#include<cstring>
#include<cmath>
using namespace std;

typedef long long ll;
struct node
{
    ll l,r;
}data[200002];
bool cmp(node x,node y)
{
    return x.r<y.r;
}
int main()
{
    ll t,n,m,s,res,i;
        cin >> n;
        for(i=0;i<n;i++){
            cin >>data[i].l >>data[i].r;
        }
        sort(data,data+n,cmp);
        s=data[0].r;
        res=1;
        for(i=1;i<n;){
            if(data[i].l>=s){
                res++;
                s=data[i].r;
                i++;
            }
            else i++;
        }
        cout << res << endl;
    return 0;
}

G 又是毕业季
时间限制内存限制出题人 1 Second 512 Mb
题目描述
为了把毕业晚会办得更好，老师想要挑出默契程度最大的k个人参与毕业晚会彩排。可是如何挑呢？老师列出全班同学的号数1，2，……，n，并且相信k个人的默契程度便是他们的最大公约数（这不是迷信哦）。这可难为了他，请你帮帮忙吧！ PS：一个数的最大公约数即本身。
输入
多组输入，两个空格分开的正整数n和k。（n大于等于k，k大于等于1）
输出
一个整数，为最大的默契值。
输入样例
4 2
输出样例
2
提示
对于20%的数据，k小于等于2，n小于等于1000 对于另30%的数据，k大于等于10,n小于等于100 对于100%的数据，k小于等于1e9,n小于等于1e9（神犇学校，人数众多）

解题思路

n / k 就是我们要的答案，得到最大公约数 a ， a * i ( 1 <= i <= k ) <= n;

H X and Y
时间限制内存限制出题人 1 Second 512 Mb
题目描述
已知：
      
y1 = k·x1

y2 = k·x2

z = min{y1·y2/k^2 }

y 1,y2,k,x1,x2 ∈ Z+

给定 y1,y2 求 z
输入多组输入，每行输入两个数字：y1,y2，请求到文件结束(EOF) 0 < y1,y2 < 231
输出
每行输出一个整数 z ,最后一组输出数据末尾没有换行符
输入样例
3 2

3 5

2 7
输出样例
6

14
解题思路

本题就是求 y1 与 y2 的最大公约数 k ，从而使 k^2 最大，z 最小

I Sequence Of Number
时间限制内存限制出题人 1 Second 512 Mb
题目描述
有一个由n个数组成的数列，但其中缺少一项，请你任意添加该项，使整个数列的值y和下标x (1 : n)满足函数：y = kx + b. 其中k,b是不为0的整数. 如果满足，输出YES，并输出数列缺少的那一项的最小值，否则，输出NO. ps: 数列是由一列有序的正整数组成的连续数字.
输入第一行一个T，表示T组测试数据.(1 ≤ T ≤ 100) 每一组数据分两行，第一行一个整数 N，第二行是由N−1个数组成的正整数数列. (1 ≤ N ≤ 3) 输入的所有数据不超过int，且为正整数.
输出
若满足输出YES，并输出数列缺少的最小数字，否则输出NO.
输入样例
1 2 3
输出样例
YES 1
样例解释
输入数3的下标可能是1 or 2，当是1的时候，缺项可以是1 2 4 5 7...取最小值为1；当下标为2的时候，缺项可以是1 2 4 5 6 7...取最小值为1；
解题思路

本题要点是数列构成的直线不过原点；使数列构成递增与递减两种分别进行分析

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;

typedef long long LL;
const int MAXN = 1e5 + 10;
LL a[MAXN];

int main() {
    int n, T;
    scanf("%d", &T);
    while(T--) {
        scanf("%d", &n);
        for(int i = 1; i < n; ++i) scanf("%lld", &a[i]);
        if(n == 1) puts("YES 1");
        else if(n == 2) {
            if(a[1] == 1) puts("YES 2");
            else puts("YES 1");
        }
        else if(n == 3) {
            LL cnt = -1;
            LL ans = a[2] - a[1];
            if(ans > 0) {
                if(a[1] - ans > 0 && a[1] - ans != ans) cnt = a[1] - ans;
                else if(ans % 2 == 0 && a[1] - ans / 2 != 0) cnt = a[1] + ans / 2;
                else if(a[1] - ans != 0) cnt = a[2] + ans;
            }
            else if(ans < 0) {
                if(a[2] + ans > 0) cnt = a[2] + ans;
                else if(ans % 2 == 0) cnt = a[1] + ans / 2;
                else cnt = a[1] - ans;
            }
            if(cnt == -1) puts("NO");
            else printf("YES %lldn", cnt);
        }
    }
    return 0;
}

J Jack与Pony的战斗
时间限制内存限制出题人 1 Second 512 Mb
题目描述
Jack和Pony分别是两股势力的头目，一直以来他们之间总是冲突不断。最近他们又开始了T轮新的竞争，在每轮竞争中他们会进行多次的PK。在每轮竞争前他们的起始积分都为0，在每次PK中，赢的一方会加2x积分，输的一方会加x积分（注：x为一个任意正整数）。然后针对每轮竞争GM会给出两个值m,n，判断经过这轮的多次PK他们两个的积分是否能得到这两个值。若能得到则输出“Yes”，若不能得到则输出“No”。
输入输入包含T轮竞争(1 ≤ T ≤ 100)。每轮竞争输入两个整数 m,n(1 ≤ m,n ≤ 10000000)。
输出
对于每轮竞争，若经过数次PK他们两人的积分能得到GM给出的值，则输出“Yes”，否则输出 “No”。
输入样例
3 10 5 121 123 12 100000
输出样例
Yes No No
解题思路

设 J 赢得场数为 a，那么 J 获得 a* 2x， P获得 a * x，

P 赢得场数为 b ，那么 J 获得 b * x， P获得 b *2 x，

综上，J的分数为 a * 2x + b * x = m

P的分数为 a * x + b * 2x = n ，因 a，b 都是整数，故我们可以将 a * x 当成 a ，b * x 当成 b ，两方程联立解 a ，b

若 a,b >=0 说明有解，否则无解