2025寒假专场9

· · 题解

产品功能

数据范围较小， 直接模拟

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

#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个人分到的组别，再判断是否冲突。

#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位置为右端点时的贡献。

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

冰方格

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

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

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