NOIP2025游记

ayzhr435619 · 2025-11-24 16:38:16 · 生活·游记

居然能打NOIP。

不抱希望。

<100可以自由落体了。

已完成今日压力自己。

没事，只是体验一场。（无效安慰）

对于一个初三oier，我深知自己太菜了。

flag : 超过250学习珂朵莉树。（骗你的没有也学）

upd:250？做梦去吧！

等这场NOIP结束后

保龄之人与400pts的众人

人人本着oi之名

长存不灭的WA，逐渐消散的AC

DAY -5

不会写差分约束。自闭了。感觉药丸。

DAY -2

摆烂

DAY -1

上动车。临时抱佛脚。

睡了1小时（

摆了。祝我rp++。

DAY 0

省流：T1挂了

T1

神秘贪心，20min（没判sum > m） 洛谷上90pts

希望CCF数据水。>90pts我给造数据的跪下了。

思路贪心，以x升序排序，求全局 x+y 最小值 mn

很显然的可以枚举选多少个奇数的，剩下的全选 mn

T2

?

luogu，yundou过了。

？

何意味。代码很短。

省流：https://www.luogu.com.cn/article/dq022f0z

和我思路一模一样

正难则反。考虑统计不合法状态。

看了 20min 样例，终于看懂。

首先这样排序有很好的性质，只要按顺序取，中间不分开，一定是最优的。

首先做 m=2，观察到只有第一个 w_1 = 1，第二个 w_2 = 2，然后后面第一个 w_j = 1，只需 a_1 + a_j < a_2 即可（这里下标均为按题目要求排序后的结果）。先对原数组 a 升序排序。容易得出a_n即为第一个遍历的w_p = 2 的，然后枚举选的第一个 w_p = 1 的下标 i，按照题意，a_i \times 2 > a_n。 剩下 j 枚举即可，注意 a_i + a_j < a_n，剩下的取1, 2 都可以。

然后m > 2时还是同样思路，但是第一个遍历的需要枚举，然后 j 可以 O(n^2) 预处理，到i时一定要只剩下2个就行了。这一步为 C(n - i - 1, m - (n - p) - 2)，乘起来即可。

我是不是考场换人了？现在根本说不清考场思路。被题解 范德蒙德卷积 吓哭了。

也许是赢了？

const int N = 5e3 + 7, mod = 998244353;
int cc;
int n, m;
int a[N], q[N], pw[N], fac[N], inv[N];
int j[N][N];
inline int C(int n, int m){
    if(n < m || m < 0) return 0;
    return fac[n] * inv[m] % mod * inv[n - m] % mod;
}
signed main() {
//  Open("sale");
    cc = read();
    pw[0] = fac[0] = inv[0] = 1;
    up(1, 5000, i) pw[i] = (pw[i - 1] << 1) % mod, fac[i] = fac[i - 1] * i % mod, inv[i] = ksm(fac[i], mod - 2, mod);
    TTr{
        n = read(), m = read();
        up(1, n, i) a[i] = read();
        sort(a + 1, a + 1 + n);
        up(1, n, i){
            q[i] = lower_bound(a + 1, a + 1 + n, a[i] * 2) - a - 1;
        }
        dn(n, 1, i){
            int jj = 0;
            up(i + 1, n, p){
                while(jj + 1 < i && a[jj + 1] + a[i] < a[p]) jj++;
                j[i][p] = jj;
            }
        }
        int ans = 0;
        dn(n, 1, i){
            dn(q[i], i + 1, p){
                int s = n - p;
                if(s > m - 2) brk;
                int res = pw[j[i][p]] - 1 + (a[p] > a[i]);
                res = (res % mod + mod) % mod;
                ans += res * C(n - i - 1, m - 2 - s) % mod;
                ans %= mod;
            }
        }
        ans = (pw[n] - ans + mod) % mod;
        writeln(ans);
    }

T3

出题人

不是你出两道黑的是干什么？

National Ohmygod IOI Plus

8pts没调出来

T4

出题人

不是你出两道黑的是干什么？

National Ohmygod IOI Plus

Never gOnna gIve you uP