2025寒假专场8

compaq · 2025-01-24 14:22:41 · 题解

默认价格

入门题

顺时针移动

入门模拟题

排名

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

如果第 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。

#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代码：

#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) 。

#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 ，每次贪心取折扣最大的，取完就弹出堆，保证只取一次。

经典贪心

#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;
}