2025寒假专场9

数据范围较小，直接模拟

CPP

#include<bits/stdc++.h>
using namespace std;
const int N = 110;
int n, m;
int p[N];
set<int>S[N];

int main(){
	scanf("%d%d", &n, &m);
	for(int i = 0; i < n; i++){
		int cnt;
		scanf("%d%d", &p[i], &cnt);
		while(cnt--){
			int x; scanf("%d", &x);
			S[i].insert(x);
		}
	}
	
	for(int i = 0; i < n; i++){
		for(int j = 0; j < n; j++){
			if(i != j && p[i] >= p[j]){
				bool ok = true;
				for(auto x: S[i]){
					if(S[j].count(x) == 0){
						ok = false;
						break;
					}
				}
				if(ok && (p[i] > p[j] || S[j].size() > S[i].size())){
					puts("Yes");
					return 0;
				}
			}
		}
	}
	puts("No");
	return 0;
}

不同球棍

对于一个字符串和其翻转后的字符串，用字典序更小的来表示这个字符串, 可以利用set来去重。注意，将每个字符串字典序小的放入set中。

CPP

#include <bits/stdc++.h>
using namespace std;
set<string>se;
int n;
void solve(){
    cin >> n;
    for (int i = 1; i <= n; i++ ){
        string s;
        cin >> s;
        string t = s;
        reverse(t.begin(), t.end());
        if (s > t) swap(s, t); // 只把字典序小的放进集合 
        se.insert(s);
    }

    cout << se.size() << "\n";
}

int main(){
	solve();
    return 0;
}

和谐的球队

数据范围较小，暴力枚举

n

个人分到的组别，再判断是否冲突。

CPP

#include<bits/stdc++.h>
using namespace std;
const int N = 100;
int a[N], b[N];
int n, t, m;
int vis[N], ans; // vis[i]记录第i个运动员的组别 
void dfs(int h, int tot){
	if(h == n + 1){
		if(tot != t) return ;
		for(int i = 1; i <= m; i++){
			if(vis[a[i]] == vis[b[i]])
				return ;
		}
		ans++;
		return;
	}
	for(int i = 1; i <= tot + 1; i++){
		vis[h] = i;
		dfs(h + 1, max(i, tot)); // 下一个人的组数是较大值 
		vis[h] = 0;
	}
}
int main(){
	scanf("%d%d%d", &n, &t, &m);
	for(int i = 1; i <= m; i++)
		scanf("%d%d", &a[i], &b[i]);
	dfs(1, 0);
	printf("%d\n", ans);
	return 0;
}

计算难题

直接计算显然是

O(n^2)

的时间复杂度。

这里我们枚举以

i

位置为右端点时的贡献。

若 $s[i]$ 为0, 因为0与任何数运算的结果都是1，所以前面 $0$ ~ $i-1$ （索引从 $0$ 开始）都会贡献答案。
若 $s[i]$ 为1, 找到左侧最近的0的位置为 $p$ 。则 $p$ 前面开始的所有起点到 $p$ 时，结果肯定为 $1$ , 那么先观察一下 $i$ 结尾的连续的 $1$ 的长度 $len$ ，这里 $len$ 个1贡献为 $(len + 1) / 2$ 。另外，若 $len$ 为奇数，则以 $p$ 为结尾的部分运算结果为 $1$ ，再与这 $len$ 个 $1$ 运算的话，不会贡献答案，只有 $p$ 位置上的 $0$ 可以贡献答案。若 $len$ 为偶数，则恰好相反， $0$ ~ $p-1$ 都能贡献答案，而 $p$ 不能贡献。

CPP

#include<bits/stdc++.h>
using namespace std;
int n;
string s;
long long ans = 0;

int main(){
	cin >> n >> s;
	int p = -1;
	for(int i = 0; i < n; i++){
		if(s[i] == '0'){
			p = max(p, i); // 最后一个0的位置
			ans += 1ll * i; // 0~i-1都有贡献 
		}
		else{
			int len = i - p; // i之前连续的1的长度
			ans += 1ll * (len + 1) / 2; //连续1的贡献
			if(p != -1){ // 左侧最近的0存在 
				if(len % 2 == 1) ans++; // 只有p位置(为0)会贡献 
				else ans += 1ll * p; // 否则0~p-1都会产生贡献 
			}	
		}
	}
	cout << ans << '\n'; 
	return 0;
}

冰方格

先沿着一个方向走到底，走到下一步是墙才会停下来，然后再以目前点继续沿着一个方向走到底...所以有可能会走到重复的点。

将走过的点标记一下，最后统计标记过的点有多少即可。

CPP

#include<bits/stdc++.h>
using namespace std;
const int N = 210;
int vis[N][N];
int n, m;
string st[N];
int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};
bool ok(int x, int y){
	return  x >= 0 && x < n && y >= 0 && y < m;
}
void dfs(int x, int y){
	for(int i = 0; i < 4; i++){
		int tx = x, ty = y;
		while(1){
			if(!ok(tx + dx[i], ty + dy[i]) || st[tx + dx[i]][ty + dy[i]] == '#'){
				if(!vis[tx][ty]){
					vis[tx][ty] = 1;
					dfs(tx, ty);	
				}
				break;
			}
			vis[tx][ty] = 1;
			tx += dx[i];
			ty += dy[i]; 	
		}
	}
}
int main(){
	scanf("%d%d", &n, &m);
	for(int i = 0; i < n; i++)
		cin >> st[i];
	vis[1][1] = 1;
	dfs(1, 1);
	int ans = 0;
	for(int i = 0; i < n; i++)
		for(int j = 0; j < m; j++)
			ans += vis[i][j];
	printf("%d\n", ans);	
	return 0;
}

文章操作

相关推荐

评论

2025寒假专场9