挑战赛 #7 全题解！

cjdstttttt

2024-08-07 17:16:42

发布于：湖南

79阅读

0回复

0点赞

T1

首先，看这数据就不是深搜能做的（深搜最坏情况 $O(2^n)$ ）
一眼动归，和走楼梯原理差不多

#include <iostream>
#include <cstdio>
using namespace std;
const int mod = 114514;
int a[100005];
int main(){
	a[1] = 1;
	int n;
	cin >> n;
	int x, to;
	for(int i = 1; i <= n; i++){
		cin >> x;
		for(int j = 1; j <= x; j++){
			cin >> to;
			a[to] = (a[to] + a[i]) % mod;//如果能到达，那么a[to]的情况数也要加上a[i]的
		}
	}
	cout << a[n];

	return 0;
}

T2

首先，我们要明白完美矩阵到底是怎样的
我这里画出一个例子来

f g h f 

h i i g

g i i h

f h g f

我们会发现，a[1][2],a[2][4],a[4][3],a[3][1] 都会对应相同
即所有的 a[i][j],a[j][n-i+1],a[n-i+1][n-j+1],a[n-j+1][i] 都必须相同才能构成完美矩阵
由于只能变成字典序下一位字符，所以我们只能找出每组的最大值

#include <iostream>
#include <cstdio>
#include <memory.h>
#include <vector>
using namespace std;
char a[1005][1005];
int solve(){
	memset(a, 0, sizeof(a));
	int n;
	cin >> n;
	for(int i = 1; i <= n; i++){
        scanf("%s", a[i] + 1);
	}
	int ct = 0;
	for(int i = 1; (i << 1) <= n; i++){
		for(int j = i; j <= n - i; j++){
			int mx = max(max(a[i][j], a[j][n - i + 1]), max(a[n - i + 1][n - j + 1], a[n - j + 1][i]));//找出最大值
			//cout << char(mx);
			ct += mx - a[i][j] + mx - a[j][n - i + 1] + mx - a[n - i + 1][n - j + 1] + mx - a[n - j + 1][i];//相加
		}
	}return ct;
}
int main(){
	int t;
	cin >> t;
	while(t--){
		cout << solve() << endl;
	}

	return 0;
}

T3

$\because a_j-a_i=j-i$
$\therefore a_j-j=a_i-i$ .
所以，我们只需要看减掉索引后 $a$ 中有几个相同元素就行了
一般来说，这种题目都是得一数组一桶的，但今天，我要打破常规！
单数组，启动！！！！！！

#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
int a[200005];
int main(){
	int n;
	cin >> n;
	for(int i = 1; i <= n; i++){
		cin >> a[i];
        a[i] -= i;//减去索引
	}
	sort(a + 1, a + n + 1);//排个序
	long long ct = 0;
	int ctt = 1, cur = a[1];
	for(int i = 2; i <= n; i++){
		if(cur != a[i]){
			ct += 1ll * ctt * (ctt - 1) / 2;//排列组合原理
			ctt = 1, cur = a[i]; 
		}else ctt++;
	}ct += 1ll * ctt * (ctt - 1) / 2;//最后也不要忘了加
	cout << ct;

	return 0;
}

什么？你想看正常解法？那就在这看吧！

T4

本来想 $O(1)$ 秒掉的，但始终有一个WA，帮我看看哪错了

#include <iostream>
#include <cstdio>
using namespace std;
int main(){
	int n, x1, y1, x2, y2;
	cin >> n >> x1 >> y1 >> x2 >> y2;
	if((y2 - y1) + (x2 - x1) % 4 == 2) cout << "NO";
	else if((y2 - y1) % 2 || (x2 - x1) % 2) cout << "NO";
	else cout << "YES";

	return 0;
}

没办法，只能写深搜了（别问为什么不是广搜，问就是太麻烦）

#include <iostream>
#include <cstdio>
using namespace std;
bool vis[505][505];
int dir[4][2] = {-2, -2, -2, 2, 2, -2, 2, 2};
int n, x1, y1, x2, y2;
bool check(int x, int y){
	if(x < 1 || x > n) return 0;
	if(y < 1 || y > n) return 0;
	if(vis[x][y]) return 0;
	return 1;
}
bool dfs(int x, int y){
	if(x == x2 && y == y2) return 1;
	vis[x][y] = 1;
	for(int i = 0; i < 4; i++){
		int xx = x + dir[i][0], yy = y + dir[i][1];
		if(check(xx, yy) && dfs(xx, yy)) return 1;
	}return 0;
}
int main(){
	cin >> n >> x1 >> y1 >> x2 >> y2;
	cout << (dfs(x1, y1) ? "YES" : "NO");

	return 0;
}

T5

$n\le10$ ，一看就是个深搜快乐题
就这个深搜爽！！！
但是 $l_i\le10^9$ ，很可能会爆
但我们又注意到 $r_i\le10^9$ ，即总共的不会超过 $10^{10}$
那么我们只需要判断是否超过 $1.8\times10^{10}$ 就行（大一点是因为如果开 $10^{10}$ 的话，有些极端数据可能不让过，而且这个数据恰好是ull能接受的）

#include <iostream>
#include <cstdio>
#define int unsigned long long
using namespace std;
int a[15], b[15];
int n;
int _abs(int l, int r){//由于开了ull，所以绝对值也得重写
	return (l < r ? r - l : l - r);
}
int dfs(int cur, int l, int r){
	if(l * a[cur] > 1.8e10) return 12321232123212321;//边界判断
	l *= a[cur], r += b[cur];
	if(cur == n) return _abs(l, r);
	int mx = _abs(l, r);
	for(int i = cur + 1; i <= n; i++){
		mx = min(mx, dfs(i, l, r));//深搜
	}
	return mx;
} 
signed main(){
	cin >> n;
	for(int i = 1; i <= n; i++){
		cin >> a[i] >> b[i];
	}
	int mn = 12321232123212321;
	for(int i = 1; i <= n; i++){
		mn = min(mn, dfs(i, 1, 0));//没说一定从1开始，所以得遍历所有开始的情况
	}
	cout << mn;

	return 0;
}

时间复杂度 $O(n\times2^n)$ ，之前Q群有人说这题专门卡深搜的，笑死我了🤣（

T6

布什，戈门
你又把签到题放最后
不解释了，读题，亮代码

#include <iostream>
#include <cstdio>
using namespace std;
char a[4][4];
int main(){
	for(int i = 1; i <= 3; i++){
		cin >> a[i] + 1;
		for(int j = 1; j <= 3; j++){
			if(a[i][j] == '?'){
				bool vis[3] = {0};
				for(int k = 1; k <= 3; k++){//C++给我的自信写三重循环
					if(a[i][k] == 'A') vis[0] = 1;
					if(a[i][k] == 'B') vis[1] = 1;
					if(a[i][k] == 'C') vis[2] = 1;
				}
				if(!vis[0]) cout << 'A';
				if(!vis[1]) cout << 'B';
				if(!vis[2]) cout << 'C';
				return 0;
			}
		} 
	}
}

最后给大家整个活：T3 python 7行！！！

n = int(input()); a = input().split(); ct = 0
for i in range(len(a)): a[i] = int(a[i]) - i
a.sort(); cur = a[0]; ctt = 0
for i in a:
    if i != cur: cur = i; ct += ctt * (ctt - 1) // 2; ctt = 1
    else: ctt += 1
ct += ctt * (ctt - 1) // 2; print(ct)