2025 ICPC 南昌全国邀请赛暨江西省赛(8题题解)

发布于：2025-05-24 ⋅ 阅读:(20) ⋅ 点赞:(0)

2025 ICPC 南昌全国邀请赛

A. Nezha Naohai

思路

这题没思路，直接输出吧。

#include <bits/stdc++.h>
 // #define int long long
#define PII pair<int,int>
#define endl "\n"
#define LL long long
#define fi first
#define se second
#define debug(a) cout<<#a<<"="<<a<<endl;
#define all(x) (x).begin(),(x).end()
#define pb push_back
#define sz(x) (int)x.size()
#define rd(x, y) rand() % (y - x + 1) + x
#define ls u << 1
#define rs u << 1 | 1
using namespace std;
   
const int N = 300010;
// int a[N], n, m, k;
 
signed main(){
    int a, b, c, d;
    cin >> a >> b >> c >> d;
    cout << (a + b + c) * d;
    return 0;
}

D. Virtuous Pope

思路

假设线段的两个端点为 ( x 1 , y 1 , z 1 ) (x_1, y_1, z_1) (x1​,y1​,z1​) 和 ( x 2 , y 2 , z 2 ) (x_2, y_2, z_2) (x2​,y2​,z2​)

  • 那么与该线段相交且垂直于坐标轴的平面 X , Y , Z X,Y,Z X,Y,Z，满足 x 1 ≤ X ≤ x 2 x_1 \leq X \leq x_2 x1​≤X≤x2​, y 1 ≤ Y ≤ y 2 y_1 \leq Y \leq y_2 y1​≤Y≤y2​， z 1 ≤ Z ≤ z 2 z_1 \leq Z \leq z_2 z1​≤Z≤z2​
  • 所以对于每条线段，做 3 3 3 次差分，最后求一次前缀和
  • 答案就是 3 3 3个前缀和数组的最大值
  • 由于数据比较大，所以要提前离散化搞一搞
#include <bits/stdc++.h>
 // #define int long long
#define PII pair<int,int>
#define endl "\n"
#define LL long long
#define fi first
#define se second
#define debug(a) cout<<#a<<"="<<a<<endl;
#define all(x) (x).begin(),(x).end()
#define pb push_back
#define sz(x) (int)x.size()
#define rd(x, y) rand() % (y - x + 1) + x
#define ls u << 1
#define rs u << 1 | 1
using namespace std;
   
const int N = 1000010;
int a[N], n, m, k;

vector<int>alls;
vector<array<int,6>>q;
int d1[N], d2[N], d3[N];

void add(int l, int r, int d[]){
    d[l] += 1, d[r + 1] -= 1;
}

int find(int x){
    return lower_bound(all(alls), x) - alls.begin() + 1;
}
signed main(){
    cin >> n >> m >> m >> m;
    for(int i = 1; i <= n; i ++ ){
        array<int,6>y;
        for(int j = 0; j < 6; j ++ ){
            int x; cin >> x; alls.pb(x);
            y[j] = x;
        }
        for(int j = 0; j <= 2; j ++ )
             if(y[j] > y[j + 3]) 
                swap(y[j], y[j + 3]); 
        q.pb(y);   
    }
    sort(all(alls));
    alls.erase(unique(all(alls)), alls.end());
    for(int i = 0; i < n; i ++ ){
        add(find(q[i][0]), find(q[i][3]), d1);
        add(find(q[i][1]), find(q[i][4]), d2);
        add(find(q[i][2]), find(q[i][5]), d3);
    }
    for(int i = 1; i <= 1000000; i ++ ){
        d1[i] += d1[i - 1];
        d2[i] += d2[i - 1];
        d3[i] += d3[i - 1];
    }
    cout << max({*max_element(d1 + 1, d1 + 1 + 1000000),*max_element(d2 + 1, d2 + 1 + 1000000),*max_element(d3 + 1, d3 + 1 + 1000000)});
    return 0;
}

E. God’s String on This Wonderful World

思路

  • 很显然的一个结论：假设区间 [ l , r ] [l, r] [l,r] 满足题意，那么 [ l , r ] [l, r] [l,r] 中所有字符出现的次数都是 k k k 的倍数。
  • 我们令 array<int,30>记录前 i i i 个字符，每个字符出现的次数并对 k k k 取模的结果。假设在下标为 i d x 1 , i d x 2 idx1, idx2 idx1,idx2 的两个array<int,30> 是一样的，代表 [ i d x 1 + 1 , i d x 2 ] [idx1 + 1,idx2] [idx1+1,idx2]是一个合法的区间。
  • 那么题目转化为对于每一个询问区间，有多少array<int,30> 是一样的。
  • 可以对每一个不同的 array<int,30> 进行哈希处理，哈希的结果存在一个数组里面，假设数组为 a a a。
  • 题目变成：对于每一个询问区间，有多少对 ( i , j ) (i, j) (i,j), 满足 a i = a j a_i = a_j ai​=aj​
  • 题目变成了：小Z的袜子了。
  • 使用分块/莫队解决即可。
#include <bits/stdc++.h>
#define int long long
#define PII pair<int,int>
#define endl "\n"
#define LL long long
#define fi first
#define se second
#define debug(a) cout<<#a<<"="<<a<<endl;
#define all(x) (x).begin(),(x).end()
#define pb push_back
#define sz(x) (int)x.size()
#define rd(x, y) rand() % (y - x + 1) + x
#define ls u << 1
#define rs u << 1 | 1
using namespace std;
const int N = 300010;
int idx, n, k, q, a[N];
map<array<int,30>,int>mp;
string s;
vector<array<int,3>>que;
int ans[N], res, cnt[N];

void add(int u){
	res += cnt[a[u]];
	cnt[a[u]] ++;
}

void del(int u){
	cnt[a[u]] --;
	res -= cnt[a[u]];
}
signed main(){
	cin >> n >> k >> q >> s;
	s = " " + s;
	array<int,30> x = {0};
	mp[x] = ++ idx;
	for(int i = 1; i <= n; i ++ ){
		x[s[i] - 'a'] ++;
		x[s[i] - 'a'] %= k;
		if(!mp[x]) mp[x] = ++ idx;
		a[i] = mp[x];
	}
	for(int i = 1; i <= q; i ++ ){
		int l, r; cin >> l >> r;
		que.pb({l, r, i});
	}
	int Block = sqrt(n);
	sort(all(que), [&](array<int,3>A, array<int,3>B){
		if(A[0] / Block != B[0] / Block) return A[0] / Block < B[0] / Block;
		return A[1] < B[1];
	});
	a[0] = 1;
	int l = 1, r = 0;
	for(auto [x, y, i] : que){
		x --;
		while(l < x) del(l), l ++;
		while(l > x) -- l, add(l);
		while(r < y) ++ r, add(r);
		while(r > y) del(r), -- r;
		ans[i] =  res;
	}
	for(int i = 1; i <= q; i ++ ){
		cout << ans[i] << "\n";
	}
	cout << endl;
    return 0;
}

F.Caloric Difference

思路

先分析式子 c i = p × c i − 1 + ( 1 − p ) × r i − 1 c_i = p \times c_{i - 1} + (1 - p) \times r_{i - 1} ci​=p×ci−1​+(1−p)×ri−1​。

  • 假设第 r i r_i ri​ 增大 x x x，那么 c i − r i c_i - r_i ci​−ri​ 就会减少 x x x， c i + 1 c_{i + 1} ci+1​会增加 ( 1 − p ) × x (1 - p) \times x (1−p)×x，总体的增量为 − x + ( 1 − p ) × x = − p × x -x + (1 - p) \times x = -p \times x −x+(1−p)×x=−p×x
  • p p p 是正的实数，所以 x x x 越小越好
  • 所以对于那些没有确定的 r i r_i ri​ 都设置成 L L L，这样的贡献最大。

r i , p , c i , l , r 都是实数，记得都开 d o u b l e ，否则就 R E 了 \large{r_i, p, c_i, l, r 都是实数，记得都开double，否则就RE了} ri​,p,ci​,l,r都是实数，记得都开double，否则就RE了

#include <bits/stdc++.h>
 #define int long long
#define PII pair<int,int>
#define endl "\n"
#define LL long long
#define fi first
#define se second
#define debug(a) cout<<#a<<"="<<a<<endl;
#define all(x) (x).begin(),(x).end()
#define pb push_back
#define sz(x) (int)x.size()
#define rd(x, y) rand() % (y - x + 1) + x
#define ls u << 1
#define rs u << 1 | 1
using namespace std;
   
const int N = 300010;
int a[N], n, m, k;
double c[N], p, l, r, b[N];

void solve(){
    cin >> n >> k;
    cin >> b[0] >> c[0] >> p >> l >> r;
    for(int i = 1; i <= n; i ++ ) b[i] = 0;
    while(k -- ){
        int x;
        double y;
        cin >> x >> y;
        b[x] = y;
    }
    for(int i = 1; i <= n; i ++ ){
        if(!b[i]) b[i] = l;
    }
    for(int i = 1; i <= n; i ++ ){
        c[i] = p * c[i - 1] + (1 - p) * b[i - 1];
    }
    double ans = 0;
    for(int i = 1; i <= n; i ++ ) ans += c[i] - b[i];
    std::cout << std::fixed << std::setprecision(12);
    cout << ans << endl;
}
 
signed main(){
    int tt = 1;
    cin >> tt;
    while(tt -- ){
        solve();
    }
    return 0;
}

G.Exploratio

思路

  • 因为 d ≥ 2 d \geq 2 d≥2 且 x i ≤ 10 9 x_i \leq 10^9 xi​≤109，所以最多走 31 31 31 条边体力值就消耗为 0 0 0。

  • 利用类似于动态规划的思想预处理出每一个结点走 31 31 31 步最大的体力消耗

    • d p i , j dp_{i, j} dpi,j​ 表示第 i i i 个点走 j j j 步最多的体力消耗

  • 最后循环遍历 d p dp dp 数组，找到一个 ≥ \geq ≥ x i x_i xi​ 的就是答案了。

用 c i n , c o u t 的记得解除绑定，不然会超时 ! \large{用cin, cout 的记得解除绑定，不然会超时!} 用cin,cout的记得解除绑定，不然会超时!

#include <bits/stdc++.h>
 #define int long long
#define PII pair<int,int>
#define endl "\n"
#define LL long long
#define fi first
#define se second
#define debug(a) cout<<#a<<"="<<a<<endl;
#define all(x) (x).begin(),(x).end()
#define pb push_back
#define sz(x) (int)x.size()
#define rd(x, y) rand() % (y - x + 1) + x
#define ls u << 1
#define rs u << 1 | 1
using namespace std;
   
const int N = 200010, M = 1000000001;
int a[N], n, m, q;

vector<PII>edges[200010];
int dp[N][35];

signed main(){
    ios::sync_with_stdio(false);cin.tie(0);
    cin >> n >> m >> q;
    for(int i = 1; i <= m; i ++ ){
        int a, b, c;
        cin >> a >> b >> c;
        edges[a].pb({b, c});
        dp[a][1] = max(dp[a][1], c);
    }
    for(int i = 2; i <= 31; i ++ ){
        for(int j = 1; j <= n; j ++ ){
            for(auto [ver, dis] : edges[j]){
                dp[j][i] = max(dp[j][i], dis * dp[ver][i - 1]);
                dp[j][i] = min(M, dp[j][i]);
            }
        }
    }
    while(q -- ){
        int v, s;
        cin >> v >> s;
        for(int i = 1; i <= 31; i ++ ){
            if(dp[v][i] > s){
                cout << i << endl;
                break;
            }
        }
    }
    return 0;
}

I. Dating Day

思路

这题其实你模拟完第一个样例，思路就出来了，简单的组合数学加上一点容斥原理：

  • 先预处理出所有最长连续包含 k k k 个1的子序列

    • 例如 101011 101011 101011，可以预处理出几个区间(下标从1开始) ：[1, 4]，[2, 5], [4, 6]
    • 可以对于原字符串中的每一个 1，当作当前子序列中第一个1，从往左边和右边二分处理
      • 往左边找到最后一个连续的0的位置
      • 往右边找到子序列中第 k + 1 k + 1 k+1 个1的前面一个位置

  • 假设只考虑当前子序列的区间[l, r]，产生的贡献是 C r − l + 1 s u m [ l 1 , r 1 ] C_{r - l + 1}^{sum[l1, r1]} Cr−l+1sum[l1,r1]​， s u m [ l 1 , r 1 ] sum[l1, r1] sum[l1,r1]指的是在区间 [ l , r ] [l, r] [l,r]中间 1 1 1 的数目，这个可以用前缀和维护

  • 考虑区间部分重合问题，假设有两个区间为 [ l 1 , r 1 ] , [ l 2 , r 2 ] [l_1,r_1], [l_2, r_2] [l1​,r1​],[l2​,r2​]，其中 r 1 > l 2 r1 > l2 r1>l2，那么产生的贡献是 C r − l + 1 s u m [ l 1 , r 1 ] + C r − l + 1 s u m [ l 2 , r 2 ] − C r 1 − l 1 + 1 s u m [ l 1 , r 1 ] C_{r - l + 1}^{sum[l1, r1]} + C_{r - l + 1}^{sum[l2, r2]} - C_{r1 - l1 + 1}^{sum[l1, r1]} Cr−l+1sum[l1,r1]​+Cr−l+1sum[l2,r2]​−Cr1−l1+1sum[l1,r1]​

  • 抄对组合数学的板子

#include <bits/stdc++.h>
 #define int long long
#define PII pair<int,int>
#define endl "\n"
#define LL long long
#define fi first
#define se second
#define debug(a) cout<<#a<<"="<<a<<endl;
#define all(x) (x).begin(),(x).end()
#define pb push_back
#define sz(x) (int)x.size()
#define rd(x, y) rand() % (y - x + 1) + x
#define ls u << 1
#define rs u << 1 | 1
using namespace std;
   
const int N = 300010, mod = 998244353;
int a[N], n, m, k;
string s;
int fact[N], infact[N], sum[N];

int qmi(int k, int s, int m){
    int res = 1;
    while(s){
        if(s & 1) res = (LL)res * k % mod;
        s >>= 1, k = (LL)k * k % mod;
    }
    return res;
}
int get(int a, int b){
    return (LL)fact[a] * infact[a - b] % mod * infact[b] % mod;
}

void init(int x){
    fact[0] = 1, infact[0] = 1;
    for(int i = 1; i <= x; i ++ ){
        fact[i] = (LL)fact[i - 1] * i % mod;
        infact[i] = (LL)infact[i - 1] * qmi(i, mod - 2, mod) % mod;
    }    
}

void solve(){
    cin >> n >> k;
    cin >> s;
    vector<PII>q;
    s = " " + s;
    for(int i = 1; i <= n; i ++ ){
        sum[i] = sum[i - 1];
        if(s[i] == '1') sum[i] ++;
    } 
    for(int i = 1; i <= n; i ++ ){
        if(s[i] == '0') continue;
        int ansl, ansr;
        int l = 1, r = i;
        while(l < r){
            int mid = l + r  >> 1;
            if(sum[i] - sum[mid - 1] <= 1) r = mid;
            else l = mid + 1;
        }
        ansl = l;
        l = i, r = n;
        while(l < r){
            int mid = l + r + 1 >> 1;
            if(sum[mid] - sum[i - 1] <= k) l = mid;
            else r = mid - 1;
        }
        if(sum[r] - sum[i - 1] == k){
            q.pb({ansl, l});
        }
    }
    int ans = 0;
    int lastl = -1, lastr = -1;
    for(auto [l, r] : q){
        if(lastl == -1){
            ans = (ans + get(r - l + 1, k)) % mod;
        }else{
            ans = (ans + get(r - l + 1, k)) % mod;
            int len = lastr - l + 1;
            ans = (ans + mod - get(len, sum[lastr] - sum[l - 1])) % mod;
        }
        lastl = l, lastr = r;
    }
    cout << ans << endl;
}
 
signed main(){
    ios::sync_with_stdio(false);cin.tie(0);
    init(100000);
    int tt = 1;
    cin >> tt;
    while(tt -- ){
        solve();
    }
    return 0;
}

K - Rotation

思路

先利用操作一把所有雕像的方向统一，然后再进行操作二。

#include <bits/stdc++.h>
 // #define int long long
#define PII pair<int,int>
#define endl "\n"
#define LL long long
#define fi first
#define se second
#define debug(a) cout<<#a<<"="<<a<<endl;
#define all(x) (x).begin(),(x).end()
#define pb push_back
#define sz(x) (int)x.size()
#define rd(x, y) rand() % (y - x + 1) + x
#define ls u << 1
#define rs u << 1 | 1
using namespace std;
   
const int N = 300010;

using namespace std;

int main() {
    int n;
    cin >> n;
    vector<int> s(4, 0);
    for (int i = 0; i < n; ++i) {
        int a;
        cin >> a;
        s[a]++;
    }
    int ans = 1e9;
    for (int i = 0; i < 4; i ++ ) {
        int tmp = s[(i + 1) % 4] * 1 + s[(i + 2) % 4] * 2 + s[(i + 3) % 4] * 3;
        int dir = (tmp + i) % 4;//最后的方向
       ans = min(ans, tmp + (4 - dir) % 4);
    }

    cout << ans << endl;

    return 0;
}

L. Regnaissance

不懂，只会做根是1的。

M. Divide coins

思路

本题思维难度感觉比后面很多题都要高一点，但这题在考场上过穿了，也许可以打表发现规律：

  • 当 m = 0 m = 0 m=0的时候，

    • n n n 是偶数，平分1即可
    • n n n 是奇数，平分1以后，把剩下的那个翻面放在任意一堆即可。

  • 当 m = n m = n m=n的时候

    • 随便放在任意一堆即可

  • 其他情况：

    • 可以考虑构造 n − m n - m n−m 个 2 2 2 和 m m m 个 3 3 3，可以用数学归纳法证明是正确的。
#include <bits/stdc++.h>
 // #define int long long
#define PII pair<int,int>
#define endl "\n"
#define LL long long
#define fi first
#define se second
#define debug(a) cout<<#a<<"="<<a<<endl;
#define all(x) (x).begin(),(x).end()
#define pb push_back
#define sz(x) (int)x.size()
#define rd(x, y) rand() % (y - x + 1) + x
#define ls u << 1
#define rs u << 1 | 1
using namespace std;
   
const int N = 300010;
int a[N], n, m, k;
 
signed main(){
    cin >> n >> m;
    if(m == 0){
        for(int i = 1; i <= n / 2; i ++ ) cout << 1;
        for(int j = 1; j <= n / 2; j ++) cout << 3;
        if(n & 1) cout << 2;
    }else if(m == n){
        for(int i = 1; i <= n; i ++ ) cout << 1;
    }else{
        for(int i = 1; i <= n - m; i ++ ) cout << 2;
        for(int i = 1; i <= m; i ++ ) cout << 3;
    }

    return 0;
}

网站公告

今日签到

点亮在社区的每一天
去签到

热门文章

最新发布