2025寒假专场2

直接模拟

统计出第一个和第二个字符串中'@'的数量。

桶排出所有小写字母在第一个字符串中的数量，然后再第二个字符串中相应减去，减去后这个个字符不为0，,且不是

atcoder

中的一个，则肯定不行。否则算入修改的数量。

最后判断修改的数量是否会超标。

203二进制变换

贪心：

将初始字符串中的'?'看成0，得到一个数值

tmp

若

tmp > n

则结束，这是当前最小的数值了。

否则从最高位开始，若遇到'?'，则该位置改成1。

CPP

#include<bits/stdc++.h>
using namespace std;
long long n;
string t;
char s[100];

int main(){
	cin >> t >> n;
	
	for(int i = t.size() - 1; i >= 0; i--)
		s[t.size() - i - 1] = t[i]; // 索引为0的位置个各位 
	
	long long tmp = 0;
	for(int i = 0; i < t.size(); i++)
		if(s[i] == '1')
			tmp = tmp | (1ll << i);
	
	if(tmp > n){
		puts("-1");
		return 0;
	}
		
	for(int i = t.size() - 1; i >= 0; i--){
		if(s[i] == '?'){
			if( (tmp | (1ll << i)) <= n){
				tmp = (tmp | (1ll << i));
			}
		}
	}
	cout << tmp << endl;

	return 0;
}

204糖果方格

注意到糖的数量非常少，只有18颗，可以进行状压。

预处理所有的糖果点，计算出相互之间的最短距离，存在

d[][]

当中。

设

f[i][s]

表示第

i

个点状态为

s

时的最少步数，

f[i][s] = min(f[i][s], f[j][s -( (1 << j))] + d[j][i]);

CPP

#include<bits/stdc++.h>
#define INF 1e9
#define N 305
#define M 20
#define S 1048576
using namespace std;
int n, m, k, cnt, ans;
int sx, sy, tx, ty;
const int dx[]={1, 0, -1, 0};
const int dy[]={0, 1, 0, -1};
int dis[N][N], f[M][S], d[M][M];
bool vis[N][N];
pair<int, int>node[M];
char s[N][N];
bool check(int i,int j){
	return 1 <= i && i <= n && 1 <= j && j <= m && s[i][j] != '#' && !vis[i][j];
}

void BFS(int x,int y){
	for(int i=0;i<=n;++i) 
		for(int j=0;j<=m;++j) 
			dis[i][j] = INF,vis[i][j] = false;
			
	queue< pair<int, int> >q;
	q.push({x, y}), dis[x][y] = 0;
	vis[x][y] = true;
	
	while(!q.empty()){
		pair<int, int> now = q.front(); q.pop();
		int xx = now.first, yy = now.second;
		for(int i = 0; i < 4; ++i){
			int nx = xx + dx[i];
			int ny = yy + dy[i];
			if(check(nx, ny)){
				dis[nx][ny] = dis[xx][yy] + 1;
				vis[nx][ny] = true;
				q.push({nx, ny});
			}
		}
	}
}
int main(){
	scanf("%d%d%d", &n, &m, &k);
	for(int i = 1; i <= n; ++i){
		for(int j = 1; j <= m; ++j){
			cin >> s[i][j];
			if(s[i][j] == 'S') sx = i,sy = j;
			if(s[i][j] == 'G') tx = i,ty = j;
			if(s[i][j] == 'o') node[++cnt] = {i, j};
		}
	}
	node[0] = {sx, sy}, node[++cnt] = {tx, ty};
	for(int i = 0; i <= cnt; ++i){
		int x = node[i].first, y = node[i].second;
		BFS(x, y);
		for(int j = 0; j <= cnt; ++j){
			int nx = node[j].first;
			int ny = node[j].second;
			d[i][j] = dis[nx][ny];
		}
	}
	
	//for(int i = 0; i <= cnt; i++) cout << node[i].first << ' ' << node[i].second << endl;
	 
	memset(f, 0x3f, sizeof f);
			
	f[0][0] = f[0][1] = 0;
	for(int s = 0; s < (1 << (cnt + 1)); s++){
		for(int i = 0; i <= cnt; i++){
			for(int j = 0; j <= cnt; j++){
				if(s & (1 << j) && f[j][s & (~(1 << j))] <= k)
					f[i][s] = min(f[i][s], f[j][s &( ~(1 << j))] + d[j][i]);
			}
		}
	}
	
	for(int s = 0; s < (1 << cnt + 1); s++) 
		if(f[cnt][s] <= k) 
			ans = max(ans, __builtin_popcount(s));
	printf("%d\n", ans < 2 ? - 1 : ans - 2);
	return 0;
}

文章操作

相关推荐

评论

2025寒假专场2