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

『模拟赛』NOIP2024加赛4

时间:2024-11-11 20:40:35浏览次数:1  
标签:qr int ll dis NOIP2024 加赛 fo 模拟 mod

Rank

给我唐完了,

image

又名,【MX-S5】梦熊 NOIP 2024 模拟赛 1


A. 王国边缘

好像简单倍增就做完了。

由于昨天 T5 在我脑海中留下了挥之不去的印象,今天一上来看到这题就发现是一个内向基环树森林。然后被硬控硬控硬控,最后一个小点加一点优化就能过没调出来,挂 30pts,菜菜菜菜菜。

注意到倍增理论复杂度是 \(\mathcal{O(n\log n)}\) 的,而我们基环树玩家的理论复杂度可以做到完全线性,所以一下午直接调出了 8.2k 基环树做法。

中途插曲还不少,包括但不限于判完完整环之后暴力查询过了,轻松卡成 \(\mathcal{O(n^2)}\);然后在环上加了前缀和优化,不过链上还是 \(\mathcal{O(n)}\) 跑,又过了;尝试交题解,被告知要贴代码,遂加入离线 dfs 优化,至此达成 \(\mathcal{O(n)}\)。

具体做法见此

点击查看代码
#include<bits/stdc++.h>
#define fo(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 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 = 2e5 + 5;
const int mod = 1e9 + 7;
ll n, m, q;
string s;
int las[N], fx[N], dfn[N], dt;
int hh[N], to[N], ne[N], cnt;
bool huan[N], vis[N], yz[N];
int bushu[N], daxiao[N], jieru[N];
ll len[N], w[N], dep[N], dis[N];
int newid[N], tot, st[N];
ll sumid[N];
ll ans[N];
namespace Wtask
{
    short main()
    {
        m %= mod;
        fo(i, 1, q)
        {
            ll qd = qr, k = qr;
            qd %= mod;
            k %= mod;
            printf("%lld\n", (qd + k * m % mod) % mod);
        }
        return Ratio;
    }
}
int h1[N], t1[N], n1[N], tnc;
ll w1[N];
vector<pii> que[N];
namespace Wlixian
{
    int deep[N];
    ll shendu[N];
    inline void Wdfs(int u, int sd)
    {
        for(pii qq : que[u])
        {
            int x = qq.fi, y = qq.se;
            ans[y] = (ans[y] + (shendu[u] - shendu[deep[sd - x]] + mod) % mod) % mod;
        }
        for(int i = h1[u]; i != -1; i = n1[i])
        {
            int v = t1[i];
            if(huan[v]) continue;
            deep[sd + 1] = v;
            shendu[v] = (shendu[u] + w1[i]) % mod;
            Wdfs(v, sd + 1);
        }
    }
    inline void Wwork()
    {
        fo(i, 1, n) if(huan[i]) deep[1] = i, Wdfs(i, 1);
    }
}
namespace Wisadel
{
    int siz[N];
    inline int Wfind(int x)
    {
        if(x == fx[x]) return x;
        return fx[x] = Wfind(fx[x]);
    }
    inline void Wmerge(int u, int v)
    {
        int _ = Wfind(u), __ = Wfind(v);
        if(siz[_] < siz[__]) fx[_] = __, siz[__] += siz[_];
        else fx[__] = _, siz[_] += siz[__];
    }
    inline void Wadd(int u, int v, ll val)
    {
        to[++cnt] = v;
        w[cnt] = val;
        ne[cnt] = hh[u];
        hh[u] = cnt;
    }
    inline void Wda(int u, int v, ll val)
    {
        t1[++tnc] = v;
        w1[tnc] = val;
        n1[tnc] = h1[u];
        h1[u] = tnc;
    }
    int tag = 1e9;
    inline void Wsearch(int u, int id, int tar)
    {
        newid[u] = id;
        for(int i = hh[u]; i != -1; i = ne[i])
        {
            int v = to[i];
            if(v == tar) return ;
            sumid[id + 1] = sumid[id] + w[i];
            Wsearch(v, ++tot, tar);
        }
    }
    inline void Wdfs(int u)
    {
        yz[u] = 1;
        vis[u] = 1;
        dfn[u] = ++dt;
        for(int i = hh[u]; i != -1; i = ne[i])
        {
            int v = to[i];
            if(vis[v])
            {
                tag = dfn[v];
                huan[u] = 1;
                sumid[++tot] = 0;
                st[Wfind(u)] = tot;
                Wsearch(v, ++tot, v);
                len[Wfind(u)] = (dep[u] - dep[v] + w[i] + mod) % mod;
            }
            else if(yz[v]) continue;
            else dep[v] = (dep[u] + w[i]) % mod, Wdfs(v);
        }
        vis[u] = 0;
        if(dfn[u] >= tag) jieru[u] = u, huan[u] = 1, daxiao[Wfind(u)]++;
        if(dfn[u] == tag) tag = 1e9;
    }
    inline void Wdfss(int u)
    {
        yz[u] = 1;
        for(int i = hh[u]; i != -1; i = ne[i])
        {
            int v = to[i];
            if(huan[v]) dis[u] = w[i], bushu[u] = 1, jieru[u] = v;
            else Wdfss(v), dis[u] = dis[v] + w[i], bushu[u] = bushu[v] + 1, jieru[u] = jieru[v];
        }
    }
    short main()
    {
        freopen("kingdom.in", "r", stdin), freopen("kingdom.out", "w", stdout);
        n = qr, m = qr, q = qr;
        fo(i, 1, n) fx[i] = i, siz[i] = 1;
        memset(h1, -1, sizeof h1);
        memset(hh, -1, sizeof hh);
        cin >> s;
        s = " " + s;
        int zaisuan = -1;
        fo(i, 1, n) if(s[i] == '1'){zaisuan = i - 1; break;}
        if(zaisuan == -1)
        {
            fo(i, 1, q)
            {
                ll qd = qr, k = qr;
                qd %= mod;
                k %= mod;
                printf("%lld\n", (qd + k) % mod);
            }
            return Ratio;
        }
        int ok = 1;
        fo(i, 1, n) if(s[i] != '1'){ok = 0; break;}
        if(ok) return Wtask::main();
        fo(i, zaisuan + 1, n) las[i] = s[i] == '1' ? i : las[i - 1];
        fo(i, 1, zaisuan) las[i] = las[n] - n;
        fo(i, 1, n)
        {
            if(i + m <= n)
            {
                ll dis;
                if(las[i + m] <= i)
                {
                    dis = 1;
                    Wmerge(i + 1, i);
                    Wadd(i, i + 1, dis);
                    Wda(i + 1, i, dis);
                }
                else
                {
                    dis = las[i + m] - i;
                    Wmerge(las[i + m], i);
                    Wadd(i, las[i + m], dis);
                    Wda(las[i + m], i, dis);
                }
            }
            else if(m < n)
            {
                int to = (m - (n - i)) % n;
                int zto = to;
                if(las[to] <= 0)
                {
                    zto = las[to] + n;
                    if(zto <= i)
                    {
                        ll dis = 1;
                        zto = i + 1;
                        if(zto > n) zto = 1;
                        Wmerge(zto, i);
                        Wadd(i, zto, dis);
                        Wda(zto, i, dis);
                    }
                    else
                    {
                        ll dis = zto - i;
                        Wmerge(zto, i);
                        Wadd(i, zto, dis);
                        Wda(zto, i, dis);
                    }
                }
                else
                {
                    ll dis = las[to] - i + n;
                    Wmerge(las[to], i);
                    Wadd(i, las[to], dis);
                    Wda(las[to], i, dis);
                }
            }
            else
            {
                ll to = (m - (n - i)) % n;
                ll tim = (m - (n - i)) / n;
                if(!to) to += n, tim--;
                int zto = las[to];
                if(zto <= 0) zto += n, tim--;
                ll dis = (n - i + zto + tim * n % mod) % mod;
                Wmerge(zto, i);
                Wadd(i, zto, dis);
                Wda(zto, i, dis);
            }
        }
        fo(i, 1, n) if(!yz[i]) Wdfs(i);
        fill(yz + 1, yz + 1 + n, 0);
        fo(i, 1, n) if(!yz[i] && !huan[i]) Wdfss(i);
        fo(i, 1, q)
        {
            ll qidian = qr, cishu = qr, res = 0;
            if(cishu == 0)
            {
                ans[i] = qidian % mod;
                continue;
            }
            int dxqidian = qidian % n;
            if(!dxqidian) dxqidian = n;
            int belong = Wfind(dxqidian);
            res = qidian % mod;
            if(cishu < bushu[dxqidian]) que[dxqidian].P_B(M_P(cishu, i));
            else
            {
                cishu -= bushu[dxqidian];
                ll timesl = cishu / daxiao[belong];
                cishu -= timesl * daxiao[belong];
                timesl %= mod;
                res = (res + timesl * len[belong] % mod) % mod;
                res = (res + dis[dxqidian]) % mod;
                if(cishu)
                {
                    if(newid[jieru[dxqidian]] - st[belong] + cishu <= daxiao[belong]) res = ((res + sumid[newid[jieru[dxqidian]] + cishu]) % mod - sumid[newid[jieru[dxqidian]]] + mod) % mod;
                    else
                    {
                        int zcc = newid[jieru[dxqidian]] + cishu - daxiao[belong];
                        res = (res + ((sumid[zcc] - sumid[newid[jieru[dxqidian]]] + mod) % mod + len[belong]) % mod) % mod;
                    }
                }
            }
            ans[i] = res;
        }
        Wlixian::Wwork();
        fo(i, 1, q) printf("%lld\n", ans[i]);
        return Ratio;
    }
}
signed main(){return Wisadel::main();}
// 佳墙坂诶迦币等渔塞

B. 买东西题

反悔贪心板子。

其实做完两个特殊性质就把正解启发得差不多了,结合一下就过了。

考虑物品按 \(a_i\) 升序,券按 \(w_i\) 升序,双指针扫,这样能够保证当前券可被之前的所有物品使用,方便反悔操作。

发现 \(a_i-b_i\) 实质上就是优惠价给的满减值,我们维护一个堆存放当前可选的满减值,每次操作只有取或不取。若从堆中取了满减,那么将 \(a_i-b_i\) 加入堆。这个操作还挺好理解的,如果 \(a_i-b_i\) 在之后某次抉择中成了最优决策,那么将 \(i\) 用的券给当前物品用,然后 \(i\) 直接用优惠价买一定是优的。

然后就做完了,复杂度 \(\mathcal{O(n\log n)}\)。

点击查看代码
#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;
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 ppp pair<pii, pii>
#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 = 1e6 + 5;
const int mod = 1e9 + 7;
int n, m;
struct good{int a, b;} g[N];
struct rmm{int w, v;} c[N];
priority_queue<int, vector<int>, less<int> > q;
namespace Wisadel
{
    short main()
    {
        freopen("buy.in", "r", stdin), freopen("buy.out", "w", stdout);
        n = qr, m = qr;
        fo(i, 1, n) g[i].a = qr, g[i].b = qr;
        fo(i, 1, m) c[i].w = qr, c[i].v = qr;
        sort(g + 1, g + 1 + n, [](good A, good B){return A.a < B.a;});
        sort(c + 1, c + 1 + m, [](rmm A, rmm B){return A.w < B.w;});
        int j = 1; ll ans = 0;
        fo(i, 1, n)
        {
            while(j <= m && c[j].w <= g[i].a) q.push(c[j++].v);
            if(q.empty() || g[i].a - g[i].b >= q.top()) ans += g[i].b;
            else
            {
                ans += g[i].a - q.top(); q.pop();
                q.push(g[i].a - g[i].b);
            }
        }
        printf("%lld\n", ans);
        return Ratio;
    }
}
signed main(){return Wisadel::main();}
// 佳墙坂诶迦币等渔塞

C. IMAWANOKIWA (Construction ver.)

大粪掏题。

D. 魔法少女们

魔法题。

为什么只写了两个题就发,你是不是想摆烂?

因为 T1 打了一个下午,T3 看起来就要改很长时间,怕来不及记录就先发了。

谁问你了?

开场直接被隔壁发现是原题,甚至三天前的比赛直接搬。然后因为没人做过所以正常进行,输麻了。

状态?感觉不是,可能主要因为 T1 打了太久被影响了心态。其实 T1 当时已经打了正解的 \(\frac{3}{4}\) 左右了,考虑当时只剩一个半小时就没继续看,结果错误是弱智取模,输麻了。

T2 感觉也不该是想不出来的,不过丁真

image

T3 T4 压根不想看,感觉 T4 讲的优化是那种学了一辈子用不上几次的那种,粉兔讲题更是直言我卡你那个了就不会再卡这个,有点玄学。


完结撒花~

没有

标签:qr,int,ll,dis,NOIP2024,加赛,fo,模拟,mod
From: https://www.cnblogs.com/Ratio-Yinyue1007/p/18540498

相关文章

  • 2024年全国高校计算机能力挑战赛C语言计算机能力挑战赛赛前模拟
    2024年全国高校计算机能力挑战赛C语言计算机能力挑战赛赛前模拟18拉手游戏某个班级共n(2<n<100)人玩报数游戏,同学们最初手拉手围成一圈。小明最开始站在第m(0<m<n)个位置,现在从圈内第一个位置开始报数,但凡报到3就退出圈子,问小明是第几个退出圈子的人?输入格式:一行输入两个......
  • NOIP2024加赛4
    简评:搬的梦熊的,一签一难两不可做。王国边缘倍增板子(但我不会打倍增所以场上调了半天)。记\(f_{i,j}\)表示从\(i\)开始走\(2^j\)次时走的距离,\(g_{i,j}\)表示从\(i\)开始走\(2^j\)次时走到的点,这个用倍增。处理\(f_{i,0}\)和\(g_{i,0}\)时分讨即可,卡不卡常无所谓。时空复杂度\(O......
  • 地下水数值模拟软件Visual MODFLOW Flex安装,PEST操作方法,Aquifer Test抽水试验设计,地
    主要围绕的目前应用较为广泛的VisualModflowFlex6.1软件版本开展,结合具体应用场景,实例讲解软件的全流程应用过程,包括数据处理分析、数值模型构建以及模拟结果的输出等。本教程有助于提升技术人员地下水模拟软件的操作能力,解决地下水数值模拟技术实施过程中遇到的困难。同时,......
  • 11.11 NOIP模拟赛
    T1字符串,两个相同的串一个从前往后,一个从后往前,选完后正着看都一样的话,就能拼成一个回文串,考虑两倍字符串,用kmp找到n~2n中间的一个i,如果i-n+1到i和1到n组成的字符相同的话,答案就为(m-1)*n+(2n-i)。m=1时直接输出nxt[n]。T2找规律,能\(O(1)\)求出任意位置的价值的......
  • [2024.11.11]NOIP模拟赛T2
    赛时T1提议看懂以后立马意识到就是让求最长Border。对于\(n\timesm\le10^6\)可以暴力建串然后直接KMP。容易发现如果\(s\)循环元为\(n\),那么答案就是\(n\times(m-1)\)。否则加上最长循环元长度即可。循环元还是用KMP求。T2让我想起了之前一道硬控我3h的题目......
  • NOIP2024加赛4
    NOIP2024加赛4\(T1\)luoguP11267【MX-S5-T1】王国边缘\(85pts\)预处理前缀中最后一个\(1\)出现的位置然后就可以倍增跳了。点击查看代码constllp=1000000007;intnxt[200010][62],f[200010][62],last[200010];chart[200010];lldivide(lls,llk){llan......
  • 1分钟学会在Linux下模拟网络延迟
    1.背景为了测试程序的健壮性以及在弱网环境下程序的表现,通常需要创造一个“不那么稳定”的网络环境,但这种模拟十分不好控制变量,比如希望控制网络延迟在500ms时,现实环境则是难以实现的,那有什么解决的办法呢?答案是,可以在Linux下使用tc命令来模拟延迟。2.安装在不同的发行......
  • WebMagic 抓取,selenium模拟点击操作,模拟将抓取的数据入库
    动态页面爬虫前的准备:https://www.cnblogs.com/maohuidong/p/18517953java添加maven依赖:<dependency><groupId>us.codecraft</groupId><artifactId>webmagic-core</artifactId><version>0.7.4</version></dependency><......
  • 拓扑AC NOIP模拟赛2
    100+35+10+10拿下rk7,拓扑AC的A题也太过困难了吧……T1题意给定数组\(a\),数组长度为\(n\)。定义\(f(x)\)表示有多少对\((i,j)\)满足\((a_i+x)\)是\((a_j+x)\)的子集。给定\(k\),保证\(a_i<2^k\),求\(\sum_{i=0}^{2^{k-1}}f(i)\)。\(n\leq20000,k\leq60\)。赛......
  • 多校A层冲刺NOIP2024模拟赛20
    多校A层冲刺NOIP2024模拟赛20昨天晚上打ABC了,所以今天才发。T1星际联邦直接上菠萝(Borůvka)算法就行了,当然还可以用线段树优化prim算法,但是没打过只是口胡:就是维护当前的连通块,但一个点$i$加入连通块时,后面那些点就可以有$a_j-a_i$的贡献,前面的点可以有$a_i-......