【2022第十三届蓝桥杯】cc++ 大学c组 解题报告

【问题描述】 给定 n 个整数 a1, a2, · · · , an ，求它们两两相乘再相加的和，即 S = a1 · a2 + a1 · a3 + · · · + a1 · an + a2 · a3 + · · · + an−2 · an−1 + an−2 · an + an−1 · an.

【输入格式】 输入的第一行包含一个整数 n 。

第二行包含 n 个整数 a1, a2, · · · an。

【输出格式】 输出一个整数 S，表示所求的和。

请使用合适的数据类型进行运算。

【样例输入】 4 1 3 6 9

【样例输出】 117

【评测用例规模与约定】 对于 30% 的数据，1 ≤ n ≤ 1000，1 ≤ ai ≤ 100。

对于所有评测用例，1 ≤ n ≤ 200000，1 ≤ ai ≤ 1000。

  乍一看没啥思路，先想暴力，两层循环枚举所有的数两两相乘，但是此题n为1e5*2，如果时间复杂度为O(n^2)，会TLE；

  所以 来分析一波，可以发现，S=A m*A m+1+A m*A m+2+......+Am*An;

  整理可得S=An*(A1+A2+...+An-1);就是每一个数乘以它前一项的前缀和。

这样可以把时间复杂度优化到O（n），应该可以，不知道对不对， 仅供参考；

#include
#include
using namespace std;
typedef long long LL;
const int N=200010;
int s[N];
int a[N];
int n;
int main(){
	cin >> n;
	LL ans=0;
	for(int i=1;i<=n;++i){
		scanf("%d",&a[i]);
		s[i]+=s[i-1]+a[i];
	}
	
	for(int i=n;i>=1;i--){
		ans+=a[i]*s[i-1];
		
	}
	printf("%lld",ans);
	
	return 0;
}

【问题描述】 小蓝对一个数的数位之和很感兴趣，今天他要按照数位之和给数排序。

当 两个数各个数位之和不同时，将数位和较小的排在前面，当数位之和相等时， 将数值小的排在前面。

例如，2022 排在 409 前面，因为 2022 的数位之和是 6，小于 409 的数位 之和 13。

又如，6 排在 2022 前面，因为它们的数位之和相同，而 6 小于 2022。

给定正整数 n，m，请问对 1 到 n 采用这种方法排序时，排在第 m 个的元 素是多少？

【输入格式】 输入第一行包含一个正整数 n。

第二行包含一个正整数 m。

【输出格式】 输出一行包含一个整数，表示答案。

【样例输入】 13 5

【样例输出】 3

【样例说明】 1 到 13 的排序为：1, 10, 2, 11, 3, 12, 4, 13, 5, 6, 7, 8, 9。

第 5 个数为 3。

【评测用例规模与约定】 对于 30% 的评测用例，1 ≤ m ≤ n ≤ 300。

对于 50% 的评测用例，1 ≤ m ≤ n ≤ 1000。

对于所有评测用例，1 ≤ m ≤ n ≤ 10^6。

  m，n的规模为10^6，应该选择O（nlogn）以内的算法，应该是快排加自定义规则。

定义一个结构体，里面两个变量分别是该数字的数为和还有该数字原版的值，重载一下小于号，然后按数位和为第一优先级排序，数值为第二优先级排序。

（后来才想到直接用pair就行了，当时考试的时候重载运算不知道为什么传两个参数就是不可以，还debug了半个多小时，麻了）

#include
#include
#include
using namespace std;
const int N=1e6+5;

struct A{
	int n1;
	int s1;

	bool operator < (const A a)const{
	
		if(a.s1!=s1)return a.s1>s1;
		if(a.s1==s1)return a.n1>n1;
	} 
}a[N];



int main(){
	int num1,num2;
	cin >> num1 >> num2;
	
	for(int i=1;i<=num1;++i){
		a[i].n1 = i;
		int k=a[i].n1;
		int sum=0;
		while(k){
			sum+=k%10;
			k/=10;
		}
		a[i].s1=sum;	
	}
	
	sort(a+1,a+num1+1);

	
	cout << a[num2].n1;
	
	
	
}

【问题描述】 给定一个长度为 n 的数列 A1, A2, · · · , An 和一个非负整数 x，给定 m 次查 询, 每次询问能否从某个区间 [l,r] 中选择两个数使得他们的异或等于 x 。

【输入格式】 输入的第一行包含三个整数 n, m, x 。

第二行包含 n 个整数 A1, A2, · · · , An 。

接下来 m 行，每行包含两个整数 li ,ri 表示询问区间 [li ,ri ] 。

【输出格式】 对于每个询问, 如果该区间内存在两个数的异或为 x 则输出 yes, 否则输出 no。

【样例输入】 4 4 1 1 2 3 4 1 4 1 2 2 3 3 3

【样例输出】 yes no yes no 试题 F: 选数异或 8 第十三届蓝桥杯大赛软件赛省赛 C/C++ 大学 C 组 【样例说明】 显然整个数列中只有 2, 3 的异或为 1。

【评测用例规模与约定】 对于 20% 的评测用例，1 ≤ n, m ≤ 100； 对于 40% 的评测用例，1 ≤ n, m ≤ 1000； 对于所有评测用例，1 ≤ n, m ≤ 100000 ，0 ≤ x < 2 20 ，1 ≤ li ≤ ri ≤ n ， 0 ≤ Ai < 2 20。

  没想出来。

。

。

写的暴力骗分，两层循环枚举区间，O（n^2),应该可以拿到百分之40把，等大佬更新题解学习一下吧。

【问题描述】 在一个字符串 S 中，如果 S i = S i−1 且 S i , S i+1 ，则称 S i 和 S i+1 为边缘 字符。

如果 S i , S i−1 且 S i = S i+1，则 S i−1 和 S i 也称为边缘字符。

其它的字符 都不是边缘字符。

对于一个给定的串 S，一次 *** 作可以一次性删除该串中的所有边缘字符 （ *** 作后可能产生新的边缘字符）。

请问经过 2 64 次 *** 作后，字符串 S 变成了怎样的字符串，如果结果为空则 输出 EMPTY。

【输入格式】 输入一行包含一个字符串 S 。

【输出格式】 输出一行包含一个字符串表示答案，如果结果为空则输出 EMPTY。

【样例输入 1】 edda 【样例输出 1】 EMPTY

【样例输入 2】 sdfhhhhcvhhxcxnnnnshh 【样例输出 2】 s 

【评测用例规模与约定】 对于 25% 的评测用例，|S | ≤ 103 ，其中 |S | 表示 S 的长度； 对于 50% 的评测用例，|S | ≤ 104 ； 对于 75% 的评测用例，|S | ≤ 105 ； 对于所有评测用例，|S | ≤ 106，S 中仅含小写字母。

  这题和下一题都没做。

我写异或数列那道暴力的时候，数组下标写错了，第一考试可能有点紧张？D了四十多分钟硬是没搞出来，后来才发现，我那个悔恨 啊，导致后来时间就来不及了，心也开始浮躁了，不然可以再写两道的（想不出来写暴力也行 啊！懊恼中！）。

【问题描述】 给定一个数组 A 和一些查询 Li , Ri，求数组中第 Li 至第 Ri 个元素之和。

小蓝觉得这个问题很无聊，于是他想重新排列一下数组，使得最终每个查 询结果的和尽可能地大。

小蓝想知道相比原数组，所有查询结果的总和最多可 以增加多少?

【输入格式】 输入第一行包含一个整数 n。

第二行包含 n 个整数 A1, A2, · · · , An，相邻两个整数之间用一个空格分隔。

第三行包含一个整数 m 表示查询的数目。

接下来 m 行，每行包含两个整数 Li、Ri ，相邻两个整数之间用一个空格分 隔。

【

输出格式】 输出一行包含一个整数表示答案。

【样例输入】 5 1 2 3 4 5 2 1 3 2 5

【样例输出】 4

【问题描述】 小蓝最近正在玩一款 RPG 游戏。

他的角色一共有 N 个可以加攻击力的技 能。

其中第 i 个技能首次升级可以提升 Ai 点攻击力，以后每次升级增加的点数 都会减少 Bi。

⌈ Ai Bi ⌉ (上取整) 次之后，再升级该技能将不会改变攻击力。

现在小蓝可以总计升级 M 次技能，他可以任意选择升级的技能和次数。

请 你计算小蓝最多可以提高多少点攻击力？

【输入格式】 输入第一行包含两个整数 N 和 M。

以下 N 行每行包含两个整数 Ai 和 Bi。

【输出格式】 输出一行包含一个整数表示答案。

【样例输入】 3 6 10 5 9 2 8 1

【样例输出】 47 【评测用例规模与约定】 对于 40% 的评测用例，1 ≤ N, M ≤ 1000； 对于 60% 的评测用例，1 ≤ N ≤ 10^4 , 1 ≤ M ≤ 10^7； 对于所有评测用例，1 ≤ N ≤ 10^5，1 ≤ M ≤ 2 × 10^9，1 ≤ Ai , Bi ≤ 10^6。

就剩半小时了，又写的暴力。

（懊恼+99999，数据友好的话也许能拿60的分？）

#include
#include
#include
#include
using namespace std;
int n,m;
const int N=1e5+5;
int c[N],cnt[N];
#define x first
#define y second
typedef pair > PII;
pair > a[N];
int main(){
	cin >> n >> m;//m是可以升级的次数
	int ans=0;
	for(int i=1;i<=n;++i){
		scanf("%d%d",&a[i].x,&a[i].y.x);
		if(a[i].x%a[i].y.x==0)a[i].y.y=a[i].x/a[i].y.x;
		else a[i].y.y = a[i].x/a[i].y.x + 1;
			}
	sort(a+1,a+n+1,greater() );
	for(int i=1;i<=m;++i){
		ans+=a[1].x;
		
		a[1].x-=a[1].y.x;
		
		cnt[a[1].x]++;
		if(cnt[a[1].x]>=a[1].y.y)a[1].x=0;
		
	
		sort(a+1,a+n+1,greater());
		
		
	}

	cout<