NOIP 2025 游记

shuqiang · 2025-11-29 20:36:49 · 生活·游记

估分 100+24+0+5，感觉这次特别失败。

• 6:30 起床。
• 6:33-7:00 去学校。
• 7:06-8:00 坐学校包的车去 NOIP。
• 8:00-8:10 找考场+进考场。
• 8:10-8:27 发呆。
• 8:27-8:30 成功解压+创建文件
• 8:30-9:00 切掉 T1。
• 9:00-9:10 完成 T2 n \le 5 的暴力。
• 9:10-10:00 思考出来了 T2 的正确贪心策略，然后开始想如何解决。
• 10:00-11:00 完成 T2 n \le 10 的暴力，然后开始推式子。
• 11:00-12:20 敲了一个 n^4 的代码，然后发现发现 T3T4 的暴力没打。
• 12:20-12:30 读完 T3，感觉暴力要打好久，于是看 T4。
• 12:30-12:55 读完 T4 并且打了个 5pts 的暴力。

然后就来不及做 T2 了。

我当时没发现，其实那个代码很容易优化成正解。

这个是我还原的赛时代码，忘记排序了调了好久：

#include<iostream>
#include<algorithm>

using namespace std;
typedef long long ll; 

const int N = 5e3 + 10, V = 5e3, mod = 998244353;
int c, t, n, m, a[N], jc[N], fjc[N], ans;

int qpow(int x, int y){
    int res = 1;
    while(y){
        if(y&1) res = (ll)res * x % mod;
        y >>= 1;
        x = (ll)x * x % mod;
    }
    return res;
}

int C(int n, int m){
    if(n < m || n < 0 || m < 0) return 0;
    return (ll)jc[n] * fjc[m] % mod * fjc[n-m] % mod;
}

int main(){
    jc[0] = 1;
    for(int i = 1; i <= V; i++) jc[i] = (ll)jc[i-1] * i % mod;
    fjc[V] = qpow(jc[V], mod-2);
    for(int i = V-1; i >= 0; i--) fjc[i] = (ll)fjc[i+1] * (i+1) % mod;
    cin >> c >> t;
    while(t--){
        cin >> n >> m; ans = 0;
        for(int i = 1; i <= n; i++) cin >> a[i];
        sort(a + 1, a + 1 + n);
        for(int x = 1; x <= n; x++){
            for(int y = x+1; y <= n; y++){
                for(int z = y+1; z <= n; z++){
                    if(a[x]*2 < a[z] && a[y]*2 > a[z] && a[x] + a[y] < a[z]){
                        int s = 1, cnt = 0;
                        s = qpow(2, x-1);
                        for(int i = 0; i <= m-2; i++){
                            cnt = (cnt + (ll)C(z-y-1, i) * C(n-z, m-2-i-(n-z))) % mod;
                        }
                        ans = (ans + (ll)s*cnt) % mod;
                    }
                }
            }
        }
        for(int x = 1; x <= n; x++){
            for(int z = x+1; z <= n; z++){
                if(a[x] < a[z] && a[x]*2 > a[z]){
                    int cnt = 0;
                    for(int i = 0; i <= m-2; i++){
                        cnt = (cnt + (ll)C(z-x-1, i) * C(n-z, m-2-i-(n-z))) % mod;
                    }
                    ans = (ans + cnt) % mod;
                }
            }
        }
        ans = ((ll)qpow(2, n) - ans + mod) % mod;
        cout << ans << '\n';
    }
    return 0;
}

刚好 24pts，然而我顺着思路先把内层 for 循环合并：

#include<iostream>
#include<algorithm>

using namespace std;
typedef long long ll; 

const int N = 5e3 + 10, V = 5e3, mod = 998244353;
int c, t, n, m, a[N], jc[N], fjc[N], ans;

int qpow(int x, int y){
    int res = 1;
    while(y){
        if(y&1) res = (ll)res * x % mod;
        y >>= 1;
        x = (ll)x * x % mod;
    }
    return res;
}

int C(int n, int m){
    if(n < m || n < 0 || m < 0) return 0;
    return (ll)jc[n] * fjc[m] % mod * fjc[n-m] % mod;
}

int main(){
    jc[0] = 1;
    for(int i = 1; i <= V; i++) jc[i] = (ll)jc[i-1] * i % mod;
    fjc[V] = qpow(jc[V], mod-2);
    for(int i = V-1; i >= 0; i--) fjc[i] = (ll)fjc[i+1] * (i+1) % mod;
    cin >> c >> t;
    while(t--){
        cin >> n >> m; ans = 0;
        for(int i = 1; i <= n; i++) cin >> a[i];
        sort(a + 1, a + 1 + n);
        for(int x = 1; x <= n; x++){
            for(int y = x+1; y <= n; y++){
                for(int z = y+1; z <= n; z++){
                    if(a[x]*2 < a[z] && a[y]*2 > a[z] && a[x] + a[y] < a[z]){
                        int s = 1, cnt = 0;
                        s = qpow(2, x-1);
//                      for(int i = 0; i <= m-2; i++){
//                          cnt = (cnt + (ll)C(z-y-1, i) * C(n-z, m-2-i-(n-z))) % mod;
//                      }
                        cnt = C(z-y-1+n-z, m-2-(n-z));
                        ans = (ans + (ll)s*cnt) % mod;
                    }
                }
            }
        }
        for(int x = 1; x <= n; x++){
            for(int z = x+1; z <= n; z++){
                if(a[x] < a[z] && a[x]*2 > a[z]){
                    int cnt = 0;
//                  for(int i = 0; i <= m-2; i++){
//                      cnt = (cnt + (ll)C(z-x-1, i) * C(n-z, m-2-i-(n-z))) % mod;
//                  }
                    cnt = C(z-x-1+n-z, m-2-(n-z));
                    ans = (ans + cnt) % mod;
                }
            }
        }
        ans = ((ll)qpow(2, n) - ans + mod) % mod;
        cout << ans << '\n';
    }
    return 0;
}

然后容易发现，s 仅与 x 有关，cnt 仅与 y,z 有关，然后很容易就可以双指针优化了。

#include<iostream>
#include<algorithm>

using namespace std;
typedef long long ll; 

const int N = 5e3 + 10, V = 5e3, mod = 998244353;
int c, t, n, m, a[N], jc[N], fjc[N], pw2[N], ans;

int qpow(int x, int y){
    int res = 1;
    while(y){
        if(y&1) res = (ll)res * x % mod;
        y >>= 1;
        x = (ll)x * x % mod;
    }
    return res;
}

int C(int n, int m){
    if(n < m || n < 0 || m < 0) return 0;
    return (ll)jc[n] * fjc[m] % mod * fjc[n-m] % mod;
}

int main(){
    jc[0] = pw2[0] = 1;
    for(int i = 1; i <= V; i++) jc[i] = (ll)jc[i-1] * i % mod, pw2[i] = pw2[i-1]*2%mod;
    fjc[V] = qpow(jc[V], mod-2);
    for(int i = V-1; i >= 0; i--) fjc[i] = (ll)fjc[i+1] * (i+1) % mod;
    cin >> c >> t;
    while(t--){
        cin >> n >> m; ans = 0;
        for(int i = 1; i <= n; i++) cin >> a[i];
        sort(a + 1, a + 1 + n);
        for(int z = 3; z <= n; z++){
            int k = m-2-(n-z);
            int x = 0, s = 0;
            for(int y = z-1; y >= 2; y--){
                if(a[y]*2 <= a[z]) break;
                while(x+1 < y && a[x+1]*2 < a[z] && a[x+1] < a[z] - a[y]){
                    s = (s + pw2[x]) % mod;
                    x++;
                }
                ans = (ans + (ll)s*C(n-1-y, k)) % mod;
            }
        }
        for(int x = 1; x <= n; x++){
            for(int z = x+1; z <= n; z++){
                if(a[x] < a[z] && a[x]*2 > a[z]){
                    ans = (ans + C(z-x-1+n-z, m-2-(n-z))) % mod;
                }
            }
        }
        ans = ((ll)qpow(2, n) - ans + mod) % mod;
        cout << ans << '\n';
    }
    return 0;
}

赛时不知道在想什么，打暴力分去了，这次应该一直做 T2 的，这样绝对能拿满分，200pts 大概率够一等了。

所以下次绝对不能打暴力......

ups: 反向挂分，得了 90+52+0+15=157。