• 简单
  • E 简单模拟
  • F 模拟
• 中等
  • A 瞎搞，预处理
  • B 打表瞎搞
  • G
  • H 贪心
  • D 简单模拟
• 困难
  • C 瞎搞，思维
  • I 枚举

A Memory Management System Gym - 102152B

题意

给你一个\(m\)长的空间，其间有部分空间已被\(n\)个\(l_i—r_i\)长的文件占据。现给出\(q\)个新文件的大小\(x_j\)，试找到能放下\(x_j\)的空县连续空间(满足\(r_j\)最大的同时\(l_j\)也最大)；如果没有能放下\(x_j\)长度新文件的空现空间，便输出-1。

题解

这题方法很多

• 方法一是先处理给定的序列，然后把所有答案打表出来，处理询问的时候直接输出对应答案就好。
• 方法二，我两年前写的代码，有兴趣的可以领会一下。

AC代码

//方法一
#include <iostream>
#include <algorithm>
#include <cmath>
#include<ctime>
#include <cstring>
using namespace std;
typedef long long ll;

int s[100005];
int ansl[100005], ansr[100005];
int main() {
	int t, n, m, q,x;
	scanf("%d", &t);
	while (t--) {
		int o = 0;
		scanf("%d%d%d", &n, &m, &q);
		for (int i = 1; i <= m; i++) {
			ansl[i]=ansr[i]=s[i] = -1;
		}
		for (int i = 0; i < n; i++) {
			int l, r;
			scanf("%d%d", &l, &r);
			for (int j = l; j <= r; j++)s[j] = 0;
		}
		int len = 0,last=0;
		for (int i = m; i > 0; i--) {
			if (s[i]) {
				if (last==0) {
					last = i;
				}
				len++;
			}
			else if(last){
				last = len = 0;
			}
			if (last&&ansl[len]==-1) {
				ansl[len] = i;
				ansr[len] = last;
			}
		}
		while (q--) {
			scanf("%d", &x);
			printf("%d %d\n", ansl[x], ansr[x]);
		}
		
	}
}

//方法二
#include<iostream>

using namespace std;
int s[100005];
int sy[100000];
int cl[100000];
int main() {
	int t, n, m, q;
	scanf("%d", &t);
	while (t--) {
		int o = 0;
		scanf("%d%d%d", &n, &m, &q);
		s[0] = s[m + 1] = 0;
		for (int i = 1; i <= m; i++) {
			s[i] = -1;
			sy[i] = 0;
		}
		for (int i = 0; i < n; i++) {
			int l, r;
			scanf("%d%d", &l, &r);
			for (int j = l; j <= r; j++)s[j] = 0;
		}

		for (int i = 1, j; i <= m;) {
			for (; s[i] == 0; i++);
			if (i > m)break;
			for (j = 0; s[i]; i++)j++;
			for (; j; j--)sy[j] = i - 1;
		}
		for (int i = 0; i < q; i++) {
			int k, x = -1, y = -1;
			scanf("%d", &k);
			if (sy[k]) {
				y = sy[k];
				x = y - k + 1;
			}
			printf("%d %d\n", x, y);
		}
		
	}



}

B Large GCD Gym - 102152C

题意

给定\(n,m\),求\(F(n,m)=gcd(5^n+7^n,5^m+7^m)\),保证\(gcd(n,m)≡1\)

题解

直接证明难度较大，但实际上打个表就知道规律了，很明显，有的时候学会猜答案也是很重要的。
证明：
我不会，大概就有公式

\[gcd(B^n+A^n,B^m+A^m)=B+(−1)^{m+n}A \]

还有一个类似的公式

\[gcd(B^n-A^n,B^m-A^m)= gcd(a^m−b^m,a^{n\;mod\;m}−b^{n\;mod\;m}) \]

\[即gcd(B^n-A^n,B^m-A^m)= B^{gcd(n,m)}-A^{gcd(n,m)} \]

有兴趣可以看以下证明
https://math.stackexchange.com/questions/262130/how-to-prove-gcdam-bm-an-bn-a-gcdm-n-b-gcdm-n
https://math.stackexchange.com/questions/1998803/let-m-and-n-be-positive-integers-such-that-gcdm-n-1-compute-gcd5m7

AC代码

#include<iostream>
#include <math.h>
using namespace std;
typedef long long ll;
int gcd(ll a, ll b) {
	return b == 0 ? a : gcd(b, a%b);
}


int main() {
	int t;
	scanf("%d", &t);
	while (t--) {
		int n, m;
		scanf("%d%d", &n, &m);
		/*printf("%d\n", gcd(pow(5, n) + pow(7, n), pow(5, m) + pow(7, m)));*/
		if (n % 2 && m % 2) {
			printf("12\n");
		}
		else {
			printf("2\n");
		}

	}
    return 0;
}

C XOR Permutations Gym - 102152D

题意

给你三个十位的二进制数字，你可以任意改变他们的“0”和“1”的位置，求这三个二进制数字异或的最大值。

题解

实际上很简单，我难度给高是因为我们当时没人出，但我现在一看题目就差不多有答案了。
因为可以任意改“0”和“1”的位置，所以位置信息完全没用，我们只要知道3个二进制串中1的个数就好了，如果3个串中1的个数和少于等于10，那就直接错开排列，就有最多的1也就可以组成最大值。如果和大于10，那么我们为了使异或后1的数量增加，我们肯定要3个1一排，这样子他还是1，就帮助我们消除了多余的1了，比如12个1，我们可以1个3（3指3个1并排）+9个1，这样子的方法排列就有10个1达到最大，但问题是很多时候你不能3个1并排，比如这个样例
1111111111
0000000000
1111111111
中间那行一个1都没有，不论你其他行怎么排都没办法有3个1并列，所以我们加一个限制，就是3行中最少的1的数量，设a[i]为第i行的1的数量，限制就是min（a[1],a[2],a[3]）,用这个方法把1消耗掉后，如果还是大于10，那就只能两两排了，两两排的答案是20-（剩余1的数量）。

给你们几组样例方便你们debug。

3
1111111111
0000000000
1111111111
1111111111
0000000000
1111111110
1111111111
1000000000
1111111110

0000000000
1000000000
1100000000

AC代码

#include <cstdio>
#include <algorithm>
#include <set>
#include <vector>
#include <queue>
#include <cstring>
#include <string>
#include <iostream>
#include <map>
#include <cmath>
#include <stack>
using namespace std;
typedef long long ll;
const int N = 1e6 + 10;

int main(){
	int t;
	scanf("%d", &t);
	while (t--) {
		int a[3] = {0}, x;
		for (int i = 0; i < 3; i++) {
			for (int j = 0; j < 10; j++) {
				scanf("%1d", &x);
				if (x)a[i]++;
			}
		}
		int ans = 0;
		int sum = a[0] + a[1] + a[2];
		int mn = min(a[0], min(a[1], a[2]));
		if ( sum<= 10) {
			ans =sum;
		}
		else {
			ans = sum;
			while (ans > 10 && mn) {
				mn--;
				ans -= 2;
			}
			if (ans > 10)ans = 20-ans ;
		}
		for (int i = 0; i < ans; i++)printf("1");
		for (int i = ans+1; i <= 10; i++)printf("0");
		printf("\n");
	}

	return 0;
}

D Building Strings Gym - 102152E

题意

给3个字符串s、c、p，c是由数字组成的，s和c对应，如得到一个s[i]字符的花费是c[i],问要构成字符串p，最小花费是多少，如果不能构成则输出-1。

题解

简单模拟

AC代码

#include<iostream>

using namespace std;
char s[2000],c[2000], p[2000];
int book[200];
int main() {
	int t;
	scanf("%d", &t);
	while (t--) {
		for (int i = 0; i <= 200; i++)book[i] = 10;
		int n, m, sum = 0;
		scanf("%d%d", &n, &m);
		scanf("%s%s%s", s,c,p);

		for (int i = 0; i < n; i++) {
			if (book[s[i]]>c[i]-'0') 
				book[s[i]] = c[i] - '0';
		}
		for (int i = 0; i < m; i++) {
			if (book[p[i]] == 10) {
				sum = -1;
				break;
			}
			sum += book[p[i]];
		}
		printf("%d\n", sum);
	}

}

E camelCase; Gym - 102152F

题意

判断驼峰字符串是否在7词以内，保证给出的都是驼峰字符串。

题解

简单模拟

AC代码

#include<iostream>
#include<string.h>
using namespace std;
char s[200];
int main() {
	int t;
	scanf("%d", &t);
	while (t--){
		scanf("%s", s);
		int len = strlen(s);
		int sum = 1;
		for (int i = 0; i < len; i++) {
			if (s[i] <= 'Z') 
				sum++;
		}
		if (sum <= 7)printf("YES\n");
		else printf("NO\n");
	}

F The Universal String Gym - 102152H

题意

判断字符串是否是无限个“abcdefghijklmnopqrstuvwxyz”构成的字符串的子串。

题解

模拟

AC代码

#include<iostream>
#include<string.h>
using namespace std;

char x[2000];
int book[200];
int main() {
	int t;
	for (int i = 'a'; i < 'z'; i++) 
		book[i] = i+1;
	book['z'] = 'a';

	scanf("%d", &t);
	while (t--) {
		int flag = 1;
		scanf("%s", x);
		int len = strlen(x);
		for (int i = 0; i<len-1; i++) {
			if (x[i+1]!=book[x[i]])
				flag = 0;
		}
		if (flag)printf("YES\n");
		else printf("NO\n");
	}

}

G The Hell Boy Gym - 101532J

题意

给出数组的子集累乘的累和。

题解

高中数学，\((1+a)*(1+b)*(1+c)=1+a+b+c+ab+ac+bc+abc\)

AC代码

#include<iostream>
using namespace std;
typedef long long ll;
const ll mod = 1e9 + 7;
int main() {
	int t, n;
	scanf("%d", &t);
	while (t--) {
		ll ans = 1,x;
		scanf("%d", &n);
		for (int i = 0; i < n; i++) {
			scanf("%lld", &x);
			ans =ans*(x + 1)%mod;
		}
		printf("%lld\n", (ans-1+mod)%mod);

	}
}

H Grid Beauty Gym - 102152J

题意

给你一个n*m的二维数组，你可以随意交换同行数字，问最大化的 the beauty of the grid 的值是多少, the beauty of the grid 定义是相邻行中相同的数字的对数。

题解

贪心,因为可以随意移动行，所以实际你只要贪心匹配就好，匹配第i行和第i-1行有几个相同的，累和起来就是答案了。

AC代码

#include<iostream>
#include<map>
using namespace std;
map<int, int> book[1005];
int main() {
	int t;
	scanf("%d", &t);
	while (t--){
		int n, m,sum=0,x;
		scanf("%d%d", &n, &m);	
		for(int i=1;i<=n;i++)book[i].clear();
		for(int i=1;i<=n;i++){
			for(int j=1;j<=m;j++){
				scanf("%d",&x);
				if(book[i-1][x]){
					sum++;
					book[i-1][x]--;
				}
				book[i][x]++;
			}
		}
		printf("%d\n", sum);
	}
	return 0;
}

I Subarrays OR Gym - 102152K

题意

给你一个数组，问你这个数组的所有子数组的按位或总共能得到几种不同的数字。数据范围1e5。

题解

直接枚举加个优化，

if (l[j] == ans)break;
l[j] = ans;

这个的意思是在上一次循环的这个位置的累或相同，那么就直接跳出，因为后面要或上一样的值，既然目前值和后面要或上的值都相同，那就可以直接跳出了。
复杂度分析： 在最坏的情况下这种优化的复杂度，一种很坏的情况是，前几个数字的某个二进制位，后面的数字都没有，比如001 000 010 100 110 ，在第二次循环的时候由于后面的数字都没有1这个二进制位，所以都不能被这个方法优化，同样的0001 0010 0000 0100 1000 1100 ，第二和第三次循环都不能被优化，但很明显这种情况最坏是15次循环，因为数据范围1e9 大概有31位二进制位，数组长度1e5，大概是16个二进制位，所以说最多在前面构造出15个后面都没有的独立二进制位，所以复杂度最多也就15 * 1e5,1e6左右。实际上这种构造方法也是答案数最多的构造方法之一，最多的答案数也是15 * 1e5,1e6左右，所以可以直接枚举，并且使用set，set的复杂度是O(NlogN)综上所述，最终复杂度是O(NlogN)，N为1e6左右。

AC代码

#include<iostream>
#include<set>
using namespace std;
int s[100005];
int l[100005];

int main() {
	int t;
	scanf("%d", &t);
	while (t--) {
		set<int>m;
		int n;
		scanf("%d", &n);
		for (int i = 0; i < n; i++) {
			scanf("%d", &s[i]);
			l[i]=-1;
		}
		for (int i = 0; i < n; i++) {
			int ans = 0;
			for (int j = i; j < n; j++) {
				ans |= s[j];
				m.insert(ans);
				if (l[j] == ans)break;
				l[j] = ans;
			}
		}
		printf("%d\n", m.size());

	}

}