A 辞树的QAQ水题
时间限制 1s 内存限制 512Mb
蒟蒻的辞树又被吊打了嘤嘤嘤。留下了属于弱者的眼泪QAQAQAQAQAAQAAQA······ 现在我 们定义辞树的悲伤值 F 。F的值为主串中子序列为”QAQ”的个数。注意字母“QAQ”不一定是 连续的，但是字母的顺序应该是准确的。
输入
输入一个整数T（0 ≤ T ≤ 20）,代表有T组数据。每组数据会给出一个字符串S,长度为len，0 < len ≤ 1000000 输出 根据每组的字符串，输出辞树的悲伤值F，每组数据换行。
输入样例
2
QAQAQYSYIOIWIN
QAQQ
输出样例
4
2
思路：题意很明显，寻找有多少个不同的QAQ组合，因此我们只需要寻找每个A前后的Q的个数sum1,sum2然后相乘求和即可得到最终答案
代码如下：
#include<math.h>
#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
int main()
{
long long sum,n,i,j,sum1,sum2,q,len;
int y[1000010]={0},t;
char str[1000010];
scanf("%d",&t);
while(t--)
{
scanf("%s",str);
sum2=0;
sum1=0;
len=strlen(str);
for(i=0;i<len;i++){
if(str[i]=='Q')
sum1++;
if(str[i]=='A')
y[sum2++]=sum1;
}
sum=0;
for(i=0;i<sum2;i++)
sum+=y[i]*(sum1-y[i]);
printf("%lld\n",sum);
}
return 0;
}
B 排序去重
时间限制 1s 内存限制 512Mb
用计算机生成了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函数就可直接水过(下面是比赛代码，没用set函数)
#include<math.h>
#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
int main()
{
int a[10000],n,i,sum;
while(~scanf("%d",&n))
{
sum=n;
for(i=0;i<n;i++)
scanf("%d",&a[i]);
sort(a,a+n);
for(i=1;i<n;i++)
if(a[i]==a[i-1])
sum--;
printf("%d\n",sum);
for(i=0;i<n;i++)
if(a[i]!=a[i-1])
printf("%d ",a[i]);
printf("\n");
}
return 0;
}
C 简单的划分问题
时间限制 1s 内存限制 512Mb
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时，只能分成一整份，所以结果肯定是这组数据中的最小值；
当x>=3时，我们直接把这组数中的最大值分成一份，那这个最大值即为它所在这组中的最小值，因此直接输出最大值即可。
当x=2时，分类讨论，若最大值在数组开始或结尾，则可以把最大值分为一组，输出最大值，若最大值在数组中间则只需要判断开头和结尾那个数字更大即可。
例如 按照从小到大排列，第一个数字在这个数组里面第K小，第二个数字在数组里面第k+1小，如果将第一个数字分为一组，则结果为第K-1小的数字（K!=1），若第一二个数字分为一组，结果依然为第K-1小的数字。
若第一个数字在这个数组里面第K小，第二个数字在数组里面第k-1小，如果将第一个数字分为一组，则结果为第K-1小的数字（K!=1），若第一二个数字分为一组，那么结果将变成第K-2小的数字（K！=2），所以要将第一个数字分为一组。最后一个数字的情况一样，所以我们只要找到两端最大的数字，分为一组，即为最终答案。
代码如下：
#include<math.h>
#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
int main()
{
int a[10000],n,i,j,max,pos,min,x;
while(~scanf("%d %d",&n,&x))
{
max=0;
min=1e9;
for(i=0;i<n;i++){
scanf("%d",&a[i]);
if(min>a[i])
min=a[i];
if(max<=a[i]){
max=a[i];
pos=i;
}
}
if(a[0]==max)
max=a[0];
if(x==1)
printf("%d\n",min);
else if(x==2){
if(max==0 || max==n-1)
printf("%d\n",max);
else
printf("%d\n",a[0]>a[n-1]?a[0]:a[n-1]);
}
else
printf("%d\n",max);
}
return 0;
}
D NHK协会的阴谋
时间限制 1s 内存限制 512Mb
“阴谋啊，这一定是NHK协会的阴谋”
事实上，NHK协会是真实存在的，NHK协会会为每个人分配一个特征码(只包含大写字母的 字符串)以及一个改变系数Q。然后NHK协会会根据以下规则将满足条件的人列为NEET:规定特 征码中所有的0N0 , 0 H0 , 0 K0最多能组合成”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则输出”F INE!”输出不包含引号
输入样例
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
思路：这个题题目很繁杂冗长，但是意思很明确，对于每个样例，先计算每个人的X值如果至少有一个人符合，就接下去进行。
然后根据每个人的X值排序，X值相同按照名字字典序排序即可。
代码如下：
#include<math.h>
#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
struct xxx
{
char name[1000];
char te[1000];
int q;
int N;
int H;
int K;
int p;
int x;
}a[1000];
int cmp(xxx i,xxx j)
{
if(i.x==j.x)
return strcmp(i.name,j.name)<0;
return i.x>j.x;
}
int main()
{
int t,n,i,j,k,l,m,len,sum;
scanf("%d",&t);
while(t--)
{
sum=0;
memset(a,0,sizeof(a));
scanf("%d %d %d",&k,&l,&m);
for(i=0;i<m;i++)
{
scanf("%s %s %d",a[i].name,a[i].te,&a[i].q);
len=strlen(a[i].te);
for(j=0;j<len;j++)
{
if(a[i].te[j]=='N')
a[i].N++;
if(a[i].te[j]=='H')
a[i].H++;
if(a[i].te[j]=='K')
a[i].K++;
}
a[i].p=a[i].H>a[i].K?a[i].K:a[i].H;
a[i].p=a[i].p>a[i].N?a[i].N:a[i].p;
a[i].x=a[i].p*(l-a[i].q);
if(a[i].p>k && a[i].q<l)
sum++;
}
if(sum==0)
{
printf("FINE!\n");
continue;
}
sort(a,a+m,cmp);
for(i=0;i<m;i++)
{
if(a[i].p>k && a[i].q<l)
printf("%s\n",a[i].name);
else
continue;
}
}
return 0;
}
E Pair and Straight
时间限制 3s 内存限制 32768kB
人生当苦无妨，良人当归即好。
—《雪中悍刀行》
我们现在有很多很多很多数字，现在我们想知道这些数字里面有最多有多少个 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
7
1 2 3 4 5 6 7
9
1 1 1 2 2 2 3 3 3
6
2 2 3 3 3 3
6
1 2 3 3 4 5
输出样例
2
4
3
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）
这道题为 2017ACM/ICPC广西邀请赛题目（题面不一样，题目所求结果一样），杭电6188号题目。
思路：这道题目中的每个数字只能使用一次。
有P S 两种组合方式，P需要两个数字，S需要三个数字，所以我们尽可能的将数字都合成P。
当我们从第一个数开始遍历，当第一个数的个数sum1>=2时，我们将其尽可能的合成为P，若剩的还有一个，则判断一下第二个数字的个数是否为奇数，第三个数字的个数是否为0。若第三个数字个数为零，则继续进行for循环。
当第二个数字的个数为2n，若果我们将其拿来用作合成S，则剩余2n-1个，下一步可以在合成n-1个P；但是我们将其用来组成P，则可以组成n个P，而且节省了第三个数的个数（由于第一个数的左边已经没有数字，所以只能和右边的数字结合，根据上述情况，只能将这个数字浪费掉）。
当第二个数字的个数为2n-1，则我们可以直接用来合成S，因为如果我们不用它来合成S，则会有可能将其浪费掉，但是如果用来结合，可能会多加一个S。
代码如下：
#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
int main()
{
int t,n,i,j,res,x;
int num[100010];
scanf("%d",&t);
while(t--)
{
memset(num,0,sizeof(num));
scanf("%d",&n);
for(i=0;i<n;i++){
scanf("%d",&x);
num[x]++;
}
sort(num,num+n);
res=0;
for(i=0;i<n;i++)
{
if(num[i]>=2){
res+=num[i]/2;
num[i]%=2;
}
if(num[i] && num[i+1]&1 && num[i+1]){
num[i]--;
num[i+1]--;
num[i+2]--;
res++;
}
}
printf("%d\n",res);
}
return 0;
}F 画线条
时间限制 1s 内存限制 512Mb
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
思路：这道题是很经典的贪心算法题目，可以参考杭电2037号题目。
这个题目的思路为将所有线条按照bi从小到大排列，如果bi相同则按照ai大小排序，然后直接遍历即可。
代码如下：
#include<math.h>
#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
struct name
{
int x;
int y;
}a[1000010];
int cmp(name i,name j)
{
if(i.y==j.y)
return i.x<j.x;
return i.y<j.y;
}
int main()
{
int n,i,j,q,sum;
scanf("%d",&n);
for(i=0;i<n;i++)
scanf("%d %d",&a[i].x,&a[i].y);
sort(a,a+n,cmp);
q=a[0].y;
sum=1;
for(i=1;i<n;i++)
{
if(a[i].x>=q)
{
q=a[i].y;
sum++;
}
}
printf("%d\n",sum);
return 0;
}G 又是毕业季
时间限制 1s 内存限制 512Mb
为了把毕业晚会办得更好，老师想要挑出默契程度最大的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（神犇学校，人数众多）
思路：这道题目也算是比较水的题目，就是求k个数的最大公约数，直接求n/k即可。
假设n=10,k=2;
如果最大公约数为1，则可能的人为1 2 3 4 5 6 7 8 9 10。（暂时不考虑选的k个数字有更大的公约数的情况）
如果最大公约数为2，则可能的人为2 4 6 8 10。
如果为3，则可能的人为3 6 9。
如果为4，则可能的人为4 8。
如果为5，则可能的人为5 10。
如果为6，则可能的人数为6。个数小于k值，因此结果就为5。
多试几组数据后就能找到规律。
代码如下：
#include<math.h>
#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
int main()
{
int n,k;
while(~scanf("%d %d",&n,&k))
printf("%d\n",n/k);
return 0;
}
H X and Y
时间限制 1s 内存限制 512Mb
已知：
给定 y1, y2 求 z
输入
多组输入，每行输入两个数字：y1, y2，请求到文件结束(EOF)
0 < y1, y2 < 2 31
输出
每行输出一个整数 z ,
最后一组输出数据末尾没有换行符
输入样例
3 2
3 5
2 7
输出样例
6
15
14
思路：也算是简单的题目，根据公式，这个题目就是求y1*y1/gcd(y1,y2)^2.
代码如下：
#include<math.h>
#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
int find(int y1,int y2)
{
return y2?find(y2,y1%y2):y1;
}
int main()
{
long long y1,y2,z,x;
while(~scanf("%lld %lld",&y1,&y2))
{
if(y1>y2)
printf("%lld\n",y1*y2/find(y1,y2)/find(y1,y2));
else
printf("%lld\n",y1*y2/find(y2,y1)/find(y2,y1));
}
return 0;
}
I Sequence Of Number
时间限制 1s 内存限制 512Mb
有一个由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.
需要注意的有一点，虽然输入不超过int，但是输出时可能超过int的，所以我们写代码时需要用long long
输入样例
1
2
3
输出样例
YES 1
样例解释
输入数3的下标可能是1 or 2，当是1的时候，缺项可以是1 2 4 5 7...取最小值为1；当下标为2的 时候，缺项可以是1 2 4 5 6 7...取最小值为1；
思路：这个题意很明显，求满足方程 y=k*x+b 的 y 值 ( k != 0, b != 0 )。
当n=1等于1，x=1,因此如果y值等于1则方程就为y=x，那么b=0，不符合题意。因此结果为2.
当n等于2时，输入的数的x=1或x=2。
假设输入的数为1，如果其对应的x=1，那么结果可能是3，4，5，......如果其对应的x=2，那么结果可能是2,3,4，....因此最终结果为2；
如果输入其他的数n，则数组就可以写为{n，1}，k,b肯定不为零，因此结果为1。
当n=3时，情况有七种：
当第一个数大于第二个数，k<0，对应下标可能为1，2或2，3或1，3。
k<0,函数图像为
必定有解，因此我们指需要按顺序计算一下下标为1,2 1,3 2,3的情况即可。
当第一个数等于第二个数时，不符合题意 输出NO
当第一个数字小于第二个数字时，k>0，对应下标可能为1，2或2，3或1，3。
函数可能的图像为
因此我们在按照下标为2,3 1,3 1,2 的顺序计算结果时必须同时考虑b=0的情况。
代码如下：
#include<stdio.h>
int main()
{
long long n,t,i,a[10],res;
scanf("%lld",&t);
while(t--)
{
scanf("%lld",&n);
for(i=0;i<n-1;i++)
scanf("%lld",&a[i]);
if(n==1)
res=2;
else if(n==2){
if(a[0]==1)
res=2;
else
res=1;
}
else if(n==3){
if(a[0]==a[1])
res=-1;
else if(a[0]<a[1]){
if(a[0]*2>a[1] && 2*a[1]!=3*a[0]) res=a[0]-(a[1]-a[0]);
else if((a[1]-a[0])%2==0) res=(a[0]+a[1])/2;
else if(a[0]*2!=a[1]) res=a[1]+a[1]-a[0];
else res=-1;
}
else{
if(a[0]<a[1]*2) res=a[1]-(a[0]-a[1]);
else if((a[0]+a[1])%2==0) res=(a[0]+a[1])/2;
else res=a[0]+(a[0]-a[1]);
}
}
if(res>0)
printf("YES %lld\n",res);
else
printf("NO\n");
}
return 0;
}
J Jack与Pony的战斗
时间限制 1s 内存限制 512Mb
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
思路：这个题目的要求是每个样例可以进行多次PK，看最终是否能得到所给的结果。
这个情况很少，直接讨论一下就可以。
首先，两个数之间的差值不能超过一倍。假如m>n，则m<=2n。如果不符合，则为NO。
其次，两个数的和必定为三的倍数。
如果符合，假设两个数之间的差值为k=m-n(m>n),设最后一回x为值为K，在在最后一句之前两个人平局，那么倒数第二句两个人的比分为n'=n-(m-n)=2n-m=3n-(n+m)，m'=m-(m-n)*2=2n-m=3n-(n-m),恒为3的倍数，因此每次x值都为1，那么必定能达到3n-(n+m)的局面。因此，两个数的和必定为3的倍数，和第二条重复。
所以，最终我们只需要判断前面两个条件即可得出结果。
代码如下：
#include<math.h>
#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
int main()
{
int t,m,n,i,j,x,y;
scanf("%d",&t);
while(t--)
{
scanf("%d %d",&x,&y);
if((x+y)%3!=0)
printf("No\n");
else if(x*2<y || y*2<x)
printf("No\n");
else
printf("Yes\n");
}
return 0;
}
京公网安备 11010502036488号