2025寒假专场8

入门题

入门模拟题

考虑到直接计算出分数的值，容易出现浮点数误差，所以可以想办法把分式拆掉。

如果第

i

的人的胜率高于第

j

个人，即

A_i \over {A_i+B_i}

A_j \over {A_j+B_j}

，这个式子可以转化为

A_i \times (B_i+B_j) > B_i \times (A_i + A_j)

。

Snuke 的迷宫

简单搜索，

DFS

或者

BFS

。

CPP

#include <bits/stdc++.h>
using namespace std;
 
string s[505];
int dx[4] = {0, 0, -1, 1};
int dy[4] = {-1, 1, 0, 0};
int n, m, f = 0;
bool vis[505][505];
map<char, int> g;
 
void dfs(int x, int y, int id) {
    if (f || (x == n - 1 && y == m - 1)) {
        f = 1;
        return ;
    }
 
    for (int i = 0; i < 4; i++) {
        int nx = x + dx[i];
        int ny = y + dy[i];
        if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
        if (vis[nx][ny]) continue;
 
        if ((g[s[nx][ny]] == id + 1) || (id == 5 && g[s[nx][ny]] == 1)) {
            vis[nx][ny] = 1;
            dfs(nx, ny, g[s[nx][ny]]);
        }
 
    }
}
 
int main() {
    g['s'] = 1; g['n'] = 2; g['u'] = 3;
    g['k'] = 4; g['e'] = 5;
    cin >> n >> m;
    for (int i = 0; i < n; i++) cin >> s[i];
    vis[0][0] = 1;
    dfs(0, 0, g[s[0][0]]);
    if (f) cout << "Yes";
    else cout << "No";
    return 0;
}

BFS代码：

CPP

#include<bits/stdc++.h>
using namespace std;
const int N=510;
int n,m,f[N][N];
int mx[4][2]={{1,0},{0,1},{-1,0},{0,-1}};
char s[N][N],a[6]={' ','s','n','u','k','e'};
struct node{
	int x,y;
}u,v;
bool bfs(){
	if(s[1][1]!='s') return false;
	queue<node>q;
	u.x=1,u.y=1;
	q.push(u);
	f[1][1]=1;
	while(!q.empty()){
		u=q.front();q.pop();
		if(u.x==n&&u.y==m) return true;
		char nxt=a[(f[u.x][u.y]%5)+1];
		for(int i=0;i<4;i++){
			v.x=u.x+mx[i][0],v.y=u.y+mx[i][1];
			if(v.x>=1&&v.x<=n&&v.y>=1&&v.y<=m&&f[v.x][v.y]==0&&s[v.x][v.y]==nxt){
				f[v.x][v.y]=f[u.x][u.y]+1;
				q.push(v);
			}
		}
	}
	return false;
}
int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
			cin>>s[i][j];
	
	if(bfs()) printf("Yes");
	else printf("No");
	return 0;
}

三元求和

所有的

(A_i, A_j, A_k)

只有

3^3=27

种组合方式。所以我们可以遍历这些组合方式

(a,b,c)

，每次都遍历数组，不断更新有多少满足

S_i = M, A_i = a, S_iS_j = ME, A_j = b, S_iS_jS_k = MEX

A_k=c

的方案。他们对答案的贡献的是方案数 ×

mex(a,b,c)

。

CPP

#include<bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10;
int n, a[N];
string s;

int mex(int x, int y, int z){
	for(int i = 0; i <= 3; i++)
		if(i != x && i != y && i != z)
			return i;
}

int main(){

	cin >> n;
	for(int i = 1; i <= n; i++)
		scanf("%d", &a[i]);
	cin >> s;	
	s = ' ' + s;
	
	long long res = 0;
	for(int ai = 0; ai <= 2; ai++)
		for(int aj = 0; aj <= 2; aj++)
			for(int ak = 0; ak <= 2; ak++){
				long long cnti = 0, cntj = 0, cntk = 0; // 注意long long 
				for(int i = 1; i <= n; i++){
					if(s[i] == 'M' && a[i] == ai)
						cnti += 1;
					if(s[i] == 'E' && a[i] == aj)
						cntj += cnti;
					if(s[i] == 'X' && a[i] == ak)
						cntk += cntj; 
				}
				res += 1ll * cntk * mex(ai, aj, ak);
			}
	printf("%lld\n", res);
	return 0;
}

商品优惠券

按照出售价格从小往大，因为有一个条件

L>D

，所以不可能出现折扣大于商品的情况，用一个堆保存小于该商品售价所有

L

对应的折扣

D

，每次贪心取折扣最大的，取完就弹出堆，保证只取一次。

经典贪心

CPP

#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10;
typedef long long ll;
ll n, m, p[N], ans;
priority_queue<int> q;
pair<int, int> c[N];
 
int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        cin >> p[i];
        ans += p[i];
    }
    for (int i = 1; i <= m; i++) cin >> c[i].first;
    for (int i = 1; i <= m; i++) cin >> c[i].second;
    sort(p + 1, p + 1 + n);
    sort(c + 1, c + 1 + m);
    for (int i = 1, pos = 1; i <= n; i++) {
        while (pos <= m && c[pos].first <= p[i]) {// 符合条件的优惠券都可以进入队列
            q.push(c[pos].second);
            pos++;
        }
        if (!q.empty()) {// 选择最大的抵扣
            ans -= q.top(); q.pop();
        }
    }
    cout << ans << endl;
    return 0;
}

文章操作

相关推荐

评论

2025寒假专场8