首页 > 其他分享 >『模拟赛』NOIP2024加赛2

『模拟赛』NOIP2024加赛2

时间：2024-11-06 20:09:39浏览次数：5  
标签：se ch int NOIP2024 fi 加赛 fo 模拟 define

Rank

一直烂，什么时候触底反弹（

image

A. 新的阶乘

赛时觉得线筛一遍同时统计每个质数的指数就做完了，然后本机怎么跑不进 1s，卡常卡了半个小时，最后没 T，但是 vector 炸了，70pts。

可以换思路考虑，赛时一直没转换过来。对于每个质数枚举其倍数统计贡献。复杂度不知道多少，跑得中等速度。

点击查看代码 
#include<bits/stdc++.h>
#define fo(x, y, z) for(int (x) = (y); (x) <= (z); (x)++)
#define fu(x, y, z) for(int (x) = (y); (x) >= (z); (x)--)
using namespace std;
typedef long long ll;
#define lx ll
inline lx qr()
{
    char ch = getchar(); lx x = 0, f = 1;
    for(; ch < '0' || ch > '9'; ch = getchar()) if(ch == '-') f = -1;
    for(; ch >= '0' && ch <= '9'; ch = getchar()) x = (x << 3) + (x << 1) + (ch ^ 48);
    return x * f;
}
#undef lx
#define qr qr()
#define pii pair<int, int>
#define pll pair<ll, ll>
#define fi first
#define se second
#define M_P(x, y) make_pair(x, y)
#define P_B(x) push_back(x)
const int Ratio = 0;
const int N = 1e7 + 5;
const int mod = 1e9 + 7;
int n;
int pri[N], tot;
bool yz[N];
namespace Wisadel
{
    inline short main()
    {
        freopen("factorial.in", "r", stdin), freopen("factorial.out", "w", stdout);
        n = qr;
        printf("f(%d)=", n);
        fo(i, 2, n)
        {
            if(!yz[i]) pri[++tot] = i;
            fo(j, 1, tot)
            {
                if(i * pri[j] > n) break;
                yz[i * pri[j]] = 1;
                if(i % pri[j] == 0) break;
            }
        }
        bool ss = 1;
        fo(i, 1, tot)
        {
            if(!ss) putchar('*');
            ss = 0;
            ll num = 0;
            for(int j = pri[i]; j <= n; j += pri[i])
            {
                int zc = j, cz = 0;
                while(zc % pri[i] == 0) zc /= pri[i], cz++;
                num += 1ll * cz * (n - j + 1);
            }
            if(num == 1) printf("%d", pri[i]);
            else printf("%d^%lld", pri[i], num);
        }
        putchar('\n');
        return Ratio;
    }
}
signed main(){return Wisadel::main();}

B. 博弈树

上来猜出结论和直径有关，但是忘了怎么打，打了巨大长时间，然后判断条件写错了挂 40pts。

从必胜开始倒着推。考虑若移动前在直径的一端，那么移动直径后后手无法移动，即此时先手必胜。考虑在距直径一端距离为 1 时，只需移动直径减二的长度，那么后手只能移动直径减一的长度到直径一端，先手必胜。以此类推，扩展发现当在直径上存在对称点时必胜，即可以找到一个与当前点不同的、到直径一端距离等于当前点到直径另一端的距离的点时必胜。

正确性：设当前点到直径两端较短距离为 \(x\)，那么若此时可移动 \(d-2x\) 长度，那么对手一定最少只能移动 \(d-2x+1\) 长度，此时当前点到直径两端较短距离成为 \(x-1\)，可以重复上述操作直到 \(x=0\)，走一遍直径结束游戏。

这么一看，显然只有直径长度为偶数（边）时的中点无法先手必胜。

考虑如何做。赛时选了一种比较麻烦的判断方法：先 dfs 一遍，找到直径的两个端点，然后分别以两个端点为根做 dfs 并记录深度，后手必胜判断条件为 \(dis_1+dis_2=d\) 且 \(dis_1=dis_2\)。

点击查看代码 
#include<bits/stdc++.h>
#define fo(x, y, z) for(register int (x) = (y); (x) <= (z); (x)++)
#define fu(x, y, z) for(int (x) = (y); (x) >= (z); (x)--)
using namespace std;
typedef long long ll;
#define lx ll
inline lx qr()
{
    char ch = getchar(); lx x = 0, f = 1;
    for(; ch < '0' || ch > '9'; ch = getchar()) if(ch == '-') f = -1;
    for(; ch >= '0' && ch <= '9'; ch = getchar()) x = (x << 3) + (x << 1) + (ch ^ 48);
    return x * f;
}
#undef lx
#define qr qr()
#define pii pair<int, int>
#define pll pair<ll, ll>
#define fi first
#define se second
#define M_P(x, y) make_pair(x, y)
#define P_B(x) push_back(x)
const int Ratio = 0;
const int N = 1e5 + 5;
const int mod = 1e9 + 7;
int n, m, r1, r2;
int dp[3][N], ans;
pii mdl[N], mdr[N];
int hh[N], to[N << 1], ne[N << 1], cnt;
namespace Wisadel
{
    void Wadd(int u, int v)
    {
        to[++cnt] = v;
        ne[cnt] = hh[u];
        hh[u] = cnt;
    }
    void Wdfs(int u, int fa)
    {
        mdl[u] = M_P(0, 0);
        mdr[u] = M_P(0, 0);
        for(int i = hh[u]; i != -1; i = ne[i])
        {
            int v = to[i];
            if(v == fa) continue;
            Wdfs(v, u);
            if(!mdl[v].fi)
            {
                if(!mdl[u].fi) mdl[u].fi = 1, mdl[u].se = v;
                else if(!mdr[u].fi) mdr[u].fi = 1, mdr[u].se = v;
            }
            else if(mdl[v].fi + 1 > mdl[u].fi) mdr[u] = mdl[u], mdl[u].fi = mdl[v].fi + 1, mdl[u].se = mdl[v].se;
            else if(mdl[v].fi + 1 > mdr[u].fi) mdr[u].fi = mdl[v].fi + 1, mdr[u].se = mdl[v].se;
        }
        if(mdl[u].fi + mdr[u].fi > ans)
        {
            r1 = mdl[u].se, r2 = mdr[u].se;
            ans = mdl[u].fi + mdr[u].fi;
        }
    }
    void Wser(int u, int fa, int id)
    {
        dp[id][u] = dp[id][fa] + 1;
        for(int i = hh[u]; i != -1; i = ne[i])
        {
            int v = to[i];
            if(v == fa) continue;
            Wser(v, u, id);
        }
    }
    inline short main()
    {
        freopen("tree.in", "r", stdin), freopen("tree.out", "w", stdout);
        n = qr, m = qr;
        memset(hh, -1, sizeof hh);
        fo(i, 1, n - 1)
        {
            int a = qr, b = qr;
            Wadd(a, b), Wadd(b, a);
        }
        Wdfs(1, 0);
        dp[1][0] = dp[2][0] = -1;
        if(!r2) r2 = 1;
        Wser(r1, 0, 1); Wser(r2, 0, 2);
        fo(i, 1, m)
        {
            int a = qr;
            if(dp[1][a] == dp[2][a] && dp[1][a] + dp[2][a] == ans) puts("Bob");
            else puts("Alice");
        }
        return Ratio;
    }
}
signed main(){return Wisadel::main();}

C. 划分

结论题。赛时想到结论没想到怎么实现，鉴定为 hash 彩笔。

首先发现在最高位为 1 的情况下位数越多越优。考虑什么时候存在无用的位数，发现数据含有一个 \(\forall i\in [1,k],s_i=0\) 的特殊点。思考发现当前 \(x\) （\(x\gt k-1\)）个字符均为 0 时，答案显然可以计数得出 \(\sum_{i=k-1}^{x-1}\ \binom{x-1}{i}\)，当然这些 0 还可以作前缀加到后面一坨数上，所以总答案即为 \(\sum_{i = k-1}^x\sum_{j=k-1}^{i-1}\ \binom{i-1}{j}\)，化简一下得出原式 \(=\sum_{i=k-1}^{x}\ \binom{x+1}{i+1}\)，方法依然是昨天用的杨辉三角，手模一下很快出来。

然后考虑其他情况。此时由于已发现的结论，串一定被划分成 1 个长度为 \(n-k+1\) 的串和 \(k-1\) 个长度为 1 的串。考虑那么问题就转化成了求出值最大的长度为 \(n-k+1\) 的串并记录其数量。比较两个字符串可以用 hash + 二分，注意只用比较前 \(n-k\) 位，因为最后一位无论放在这里还是单拿出来贡献是一样的，然后就做完了。对于情况一复杂度是 \(\mathcal{O(n)}\) 的，情况二大概是 \(\mathcal{O(k\log n+n)}\) 的。

细节 n 多个。首先 \(n=k\) 要特判，不然二分直接似了。然后二分边界问题和取值问题，卡我很久。然后第二个包加了自然溢出的 hack。然后注意一些初始化问题。然后没了。

点击查看代码 
#include<bits/stdc++.h>
#define fo(x, y, z) for(register int (x) = (y); (x) <= (z); (x)++)
#define fu(x, y, z) for(int (x) = (y); (x) >= (z); (x)--)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define lx ll
inline lx qr()
{
    char ch = getchar(); lx x = 0, f = 1;
    for(; ch < '0' || ch > '9'; ch = getchar()) if(ch == '-') f = -1;
    for(; ch >= '0' && ch <= '9'; ch = getchar()) x = (x << 3) + (x << 1) + (ch ^ 48);
    return x * f;
}
#undef lx
#define qr qr()
#define pii pair<int, int>
#define pll pair<ll, ll>
#define fi first
#define se second
#define M_P(x, y) make_pair(x, y)
#define P_B(x) push_back(x)
const int Ratio = 0;
const int N = 2e6 + 5;
const int mod = 998244353;
const int base = 233;
int n, k;
string s;
ll has[N], bas[N];
ll ans, num;
namespace Wtask
{
    ll jc[N], ny[N];
    ll Wqp(ll x, int y){ll res = 1; while(y){if(y & 1) res = res * x % mod; x = x * x % mod; y >>= 1;} return res;}
    ll Wc(int n, int m){return jc[n] * ny[m] % mod * ny[n - m] % mod;}
    short main()
    {
        jc[0] = ny[0] = 1;
        fo(i, 1, n) jc[i] = jc[i - 1] *i % mod;
        ny[n] = Wqp(jc[n], mod - 2);
        fu(i, n - 1, 1) ny[i] = ny[i + 1] * (i + 1) % mod;
        int tot = 0;
        fo(i, 1, n) if(s[i] == '0') tot++;
                    else break;
        if(tot == n) tot--;
        ll sum = 0;
        fo(i, tot + 1, n) sum = (sum * 2 % mod + (s[i] == '1')) % mod;
        ll num = 0;
        fo(i, k - 1, tot) num = (num + Wc(tot, i)) % mod;
        printf("%lld %lld\n", sum, num);
        return Ratio;
    }
}
namespace Wisadel
{
    ll Wgh(int l, int r){return (has[r] - has[l - 1] * bas[r - l + 1] % mod + mod) % mod;}
    short main()
    {
        freopen("divide.in", "r", stdin), freopen("divide.out", "w", stdout);
        n = qr, k = qr;
        cin >> s;
        s = " " + s;
        if(n == k)
        {
            ll zc = 0;
            fo(i, 1, n) zc += s[i] == '1';
            printf("%lld %d\n", zc, 1);
            return Ratio;
        }
        bool task = 1;
        fo(i, 1, k - 1) if(s[i] != '0'){task = 0; break;}
        if(task) return Wtask::main();
        bas[0] = 1;
        fo(i, 1, n) bas[i] = bas[i - 1] * base % mod;
        fo(i, 1, n) has[i] = (has[i - 1] * base % mod + (s[i] == '1')) % mod;
        int nl = 1;
        int num = 1;
        fo(i, 2, k)
        {
            int l = 0, r = n - k;
            while(l < r)
            {// 匹配位数
                int mid = ((l + r + 1) >> 1);
                if(Wgh(nl, nl + mid - 1) == Wgh(i, i + mid - 1)) l = mid;
                else r = mid - 1;
            }
            if(l == n - k) num++;
            else if(s[nl + l] < s[i + l]) nl = i, num = 1;
        }
        ll zc = 0;
        fo(i, nl, nl + n - k) zc = (zc * 2 % mod + (s[i] == '1')) % mod;
        fo(i, 1, n) if(i < nl || i > nl + n - k) zc = (zc + (s[i] == '1')) % mod;
        printf("%lld %d\n", zc, num);
        return Ratio;
    }
}
signed main(){return Wisadel::main();}

D. 灯笼

原题 [EGOI2021] Lanterns / 灯笼 。

赛时一点不会打，想不到什么好的转移方式就没写。

神仙 dp，感觉状态设计就不是一般人能想到的。先从暴力说起，设 \(f_{l,r,i}\) 为当前灯火范围为 \([l,r]\) 且位于 \(i\) 段山峰走完全程的最小代价，那么转移时需要满足当前可以从 \(i\) 走到 \(j\)。复杂度大概是 \(\mathcal{O(n^4)}\)。

首先状态三维就很过不去，我们需要将其压到至多两维。考虑改设 \(f_{x,y}\) 表示第 \(x\) 盏灯提供最小灯火值，\(y\) 盏灯提供最大灯火值，且满足 \([a_x,b_y]\) 的灯火值都被提供，经过所有位置的最小值。这样设计既可以得到当前可经过的区间，也能得到当前所在区间，非常神的设计。

我们需要提前处理出购买第 \(i\) 盏灯后可经过的山峰区间，使得在得到 \(x,y\) 后可以通过取交集来得出当前可经过山峰区间。预处理是 \(\mathcal{(?,n^2]}\) 的，比较好写。

然后是难点转移。发现如果暴力枚举灯还是 \(\mathcal{O(n^3)}\) 的，过不去。怎么优化？假设当前需要向右走，左端点先不动，当遇到一个不合法的转移时（当前山峰区间 \([L,R]\) 无法不包含 \(p_i\)，或 \([a_i,b_i]\) 与 \([a_x,b_x]\) 无交集），对于更小的右端点，该转移依然无法进行。出现了单调性，我们可以直接分别按左端点升序、右端点降序排序，然后上堆优化转移，这样复杂度就被降到 \(\mathcal{O(n^2\log n)}\) 级别的了，可行。

边界上，当 \(a_x=1\) 且 \(b_y=n\) 时表示已经走完了，所以有 \(f_{x,y}=0\)，其余由于是求最小值，赋成极大值即可。当遇到 \(a_x\gt a_y\) 或 \(b_x\gt b_y\) 时，此时比较显然我们可以直接将 \(f_{y,y}/f_{x,x}\) 的值赋给 \(f_{x,y}\) 即可。

点击查看代码 
#include<bits/stdc++.h>
#define fo(x, y, z) for(register int (x) = (y); (x) <= (z); (x)++)
#define fu(x, y, z) for(int (x) = (y); (x) >= (z); (x)--)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define lx ll
inline lx qr()
{
    char ch = getchar(); lx x = 0, f = 1;
    for(; ch < '0' || ch > '9'; ch = getchar()) if(ch == '-') f = -1;
    for(; ch >= '0' && ch <= '9'; ch = getchar()) x = (x << 3) + (x << 1) + (ch ^ 48);
    return x * f;
}
#undef lx
#define qr qr()
#define pii pair<int, int>
#define pll pair<ll, ll>
#define fi first
#define se second
#define M_P(x, y) make_pair(x, y)
#define P_B(x) push_back(x)
const int Ratio = 0;
const int N = 2e3 + 5;
const int mod = 998244353;
int n, k;
int h[N], p[N], c[N], a[N], b[N];
pii uc[N], dc[N]; // 上下界可达区间 : upcan, downcan
int idl[N], idr[N]; // 按左/右边界排序后下标
int f[N][N];
priority_queue<pii, vector<pii>, greater<pii> > Ql[N], Qr[N];
namespace Wisadel
{
    void Wsolvel(int l, int r, int L, int R)
    {
        while(Ql[l].size() && (p[Ql[l].top().se] < L || p[Ql[l].top().se] > R || a[Ql[l].top().se] > b[r] || a[l] > b[Ql[l].top().se]))
            Ql[l].pop();
        if(Ql[l].size()) f[l][r] = min(f[l][r], Ql[l].top().fi);
    }
    void Wsolver(int l, int r, int L, int R)
    {
        while(Qr[r].size() && (p[Qr[r].top().se] < L || p[Qr[r].top().se] > R || a[Qr[r].top().se] > b[r] || a[l] > b[Qr[r].top().se]))
            Qr[r].pop();
        if(Qr[r].size()) f[l][r] = min(f[l][r], Qr[r].top().fi);
    }
    short main()
    {
        freopen("lantern.in", "r", stdin), freopen("lantern.out", "w", stdout);
        n = qr, k = qr;
        fo(i, 1, n) h[i] = qr;
        fo(i, 1, k) p[i] = qr, c[i] = qr, a[i] = qr, b[i] = qr;
        fo(i, 1, k)
        {
            uc[i] = dc[i] = M_P(p[i] + 1, p[i] - 1);
            while(uc[i].fi > 1 && h[uc[i].fi - 1] <= b[i]) uc[i].fi--;
            while(uc[i].se < n && h[uc[i].se + 1] <= b[i]) uc[i].se++;
            while(dc[i].fi > 1 && h[dc[i].fi - 1] >= a[i]) dc[i].fi--;
            while(dc[i].se < n && h[dc[i].se + 1] >= a[i]) dc[i].se++;
        }
        fo(i, 1, k) idl[i] = idr[i] = i;
        sort(idl + 1, idl + 1 + k, [](int x, int y){return a[x] < a[y];});
        sort(idr + 1, idr + 1 + k, [](int x, int y){return b[x] > b[y];});
        fo(i, 1, k) fo(j, 1, k)
        {
            int l = idl[i], r = idr[j];
            f[l][r] = 2e9;
            int L = max(dc[l].fi, uc[r].fi), R = min(dc[l].se, uc[r].se);
            if(p[l] < L || p[l] > R || p[r] < L || p[r] > R || (a[l] > a[r] && b[l] > b[r])) continue;
            // 出生点不符合要求                                  不满足定义
            if(a[l] == 1 && b[r] == n) f[l][r] = 0; // 到头了
            else if(a[l] > a[r]) f[l][r] = f[r][r];
            else if(b[l] > b[r]) f[l][r] = f[l][l]; // 直接转移
            else
            {
                Wsolvel(l, r, L, R);
                Wsolver(l, r, L, R);
            }
            if(f[l][r] < 2e9)
            {
                Ql[l].push(M_P(f[l][r] + c[r], r));
                Qr[r].push(M_P(f[l][r] + c[l], l));
            }
        }
        fo(i, 1, k) printf("%d\n", (f[i][i] >= 2e9) ? -1 : f[i][i] + c[i]);
        return Ratio;
    }
}
signed main(){return Wisadel::main();}

末

还是烂，不过打得烂确实能暴露出自己的很多问题：想不到正解，想到错解后不愿再优化改进等。这一场就是这样，T1 感觉上就假的做法硬卡了半小时常，T2 T3 的结论都想到了，但是就是有细节问题。

字符串和 dp 还是太不熟了，得加练，但真的还有时间吗？抓好每一道模拟赛题，尽量提升吧。

还有就是达到最后无论如何不能摆烂，T4 暴力不会抓紧回看前面，已经出现不止两次因为回看太晚导致发现错却来不及改的痛苦情况了。

完结撒花~

标签：se,ch,int,NOIP2024,fi,加赛,fo,模拟,define
From： https://www.cnblogs.com/Ratio-Yinyue1007/p/18530753

相关文章

  • 「模拟赛」NOIP2024 模拟 2
    Rank14，190pts比赛链接新的阶乘容易发现只需要处理1~n的质因子分解即可，每个数\(i\)本来有\(n-i+1\)个我们在欧拉筛的过程中同时维护每个数的一个质因子\(pri\)每次从\(n\)到1把遇到的非质数\(i\)现有的个数加到他的质因子\(pri_i\)和\(\frac{i}{pri_i......
  • 【考试题解】NOIP2024加赛2
    目录A.新的阶乘(factorial)题目内容部分分?pts正解思路代码B.博弈树(tree)题目内容部分分80pts正解思路代码C.划分(divide)题目内容部分分10pts14pts正解思路代码D.灯笼(lantern)A.新的阶乘(factorial)题目内容定义运算\(f(x)=x^1\times(x-1)^2\times(x-2)^3\dots2^{x-1......
  • NOIP加赛2
    rank15T1100，T280，T39，T40本来不想交的，但快结束的时候回头看见huge在看着我就慌了。T1新的阶乘签到题，将跑个类似于埃氏筛的东西就行了，时间复杂度\(O(n\log\logn)\)。点此查看代码#include<bits/stdc++.h>usingnamespacestd;#definerep(i,s,t,p)for(inti=s;i......
  • noip模拟7
    新的阶乘考虑从这个式子下手，怎么更优秀的求得答案。\[\begin{aligned}f(x)&=x_1\times(x-1)^2\times(x-2)^3...2^{x-1}\times1^x\\&=\prod_{k=0}^{x-1}(x-k)^{k+1}\\&=x!\times\prod_{k=0}^{x-2}(x-1-k)^{k+1}\\&=x!\timesf(x-1)\\&=\prod_{k=1}......
  • NOIP2024加赛2
    NOIP2024加赛2题目来源：2023NOIPA层联测18\(T1\)HZTG5733.新的阶乘\(100pts\)预处理素数后直接对\(1\simn\)进行质因数分解因为有太多冗余枚举导致无法通过。考虑枚举最终形式。具体地，从质因数的角度入手，设当前枚举的质数为\(p\)，暴力求出\(ip\)中\(p\)的指......
  • [2024.11.06]NOIP 模拟赛
    不会tarjan不会广义串并联图……赛时T1看上去很可做。看到中位数首先想到二分。在二分的背景下，问题转化为求当前最多能使多少个元素大于等于某个定值。我们不妨先让所有的元素都选择\(a\)值，然后相当于要选择一段连续的\(b\)替换一些\(a\)，要求最后总和最大。所以可以新设......
  • 11.6 模拟赛
    A.大副令\(m\)的最高一位\(1\)在\(k\)上。构造\(\lfloorn/2\rfloor\)个\(2^k\)，\(n-\lfloorn/2\rfloor\)个\(2^k-1\)，即可达到答案上界\((2^{k+1}-1)\times\lfloorn/2\rfloor\times(n-\lfloorn/2\rfloor)\)。B.机械师首先小甜水糖水不等式。多人同时破......
  • 7.7 g(x)=(10a)/(10b+(a-10b)e^(asinx))，取a=1.1，b=0.01，计算x=1,2,...,20时，g(x)对应的函
    importnumpyasnpimportmatplotlib.pyplotaspltfromscipy.optimizeimportcurve_fit,leastsq,least_squaresfromscipy.constantsimportedefg(x,a,b):return(10*a)/(10*b+(a-10*b)*np.exp(a*np.sin(x)))a=1.1b=0.01x_values=np.......
  • 1105模拟
    \(T1\),注意对白三角形进行搜索，每次搜到曾经走过点判断能否构成三角形是错的，我本来以为我是从总三角形中去掉每条白边影响那里错了。这启示我们什么？即使对看起来最简单的地方也要进行严谨证明，不要一眼过。然后可以想总三角形减异色三角形，就能做了\(T2\),注意如果要进行搜索，枚......
  • CSP2024 前集训：NOIP2024加赛 1
    前言赛时本来rk3，赛后自己加hack卡自己于是成rk4了。因为这场是假做法大战，T1假贪心有\(92pts\)；T2\(O(n^2m)\)能过（是因为数据里\(m\le10\)）；T3相当抽象，赛时我打的爆搜只加了一个剪枝能得\(70pts\)，赛后发现无解的时候会跑满，于是提前判掉无解就过了甚至最优解\(30ms\)......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99