首页 > 其他分享 >『模拟赛』多校A层冲刺NOIP2024模拟赛03

『模拟赛』多校A层冲刺NOIP2024模拟赛03

时间：2024-10-07 19:59:49浏览次数：1  
标签：03 ch int qr 模拟 ans define NOIP2024 fo

Rank

炸了，触底反弹

image

A. 五彩斑斓（colorful）

签，又没签上。

考虑如何一步步优化暴力。最暴力的思想 \(\mathcal{O(n^4)}\) 枚举每个矩形，判断四个顶点颜色。稍微优化些，两次 \(\mathcal{O(n^2)}\) 跑出对于行/列每个点下一个与之颜色相同的坐标，利用容斥全部减去不合法的方案数，然后再枚举每个点，随机数据下跑得很快，颜色数量越少效率越低。

考虑正解，依旧容斥，我们可以直接枚举两行，再枚举列，记录每一个相同颜色组成的点对出现的数量，简单组合计数可知对于 \(n\) 组点对能组成的方案数为 \(\sum_{i=1}^n\ i\)，增加出现数量时直接在总 \(ans\) 里减一下就行了，每次统计后清空计数数组，这样复杂度为 \(\mathcal{O(n^3)}\)，可以轻松过。

据说有 \(\mathcal{O(n^4)}\) 算法各种大力优化碾过去了。

点击查看代码 
#include<bits/stdc++.h>
#define fo(x, y, z) for(register int (x) = (y); (x) <= (z); (x)++)
#define fu(x, y, z) for(register 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 fi first
#define se second
const int Ratio = 0;
const int N = 400 + 5;
const int mod = 998244353;
int n, m;
int c[N][N], tim[N * N];
ll ans;
namespace Wisadel
{
    short main()
    {
        freopen("colorful.in", "r", stdin) , freopen("colorful.out", "w", stdout);
        n = qr, m = qr;
        fo(i, 1, n) fo(j, 1, m) c[i][j] = qr;
        ans = 1ll * n * (n + 1) * m * (m + 1) / 4;
        fo(i, 1, n) fo(j, i, n)
        {
            fo(k, 1, m) if(c[i][k] == c[j][k]) tim[c[i][k]]++, ans -= tim[c[i][k]];
            fo(k, 1, m) if(c[i][k] == c[j][k]) tim[c[i][k]] = 0;
        }
        printf("%lld\n", ans);
        return Ratio;
    }
}
signed main(){return Wisadel::main();}

B. 错峰旅行（travel）

签，双没签上。

看到第一感觉是动态开点线段树，不过赛时怎么压都过不了最后一个大样例，卡到极限 70pts，自己画蛇添足唐错挂 10pts。

其实是可以用线段树做的。首先很显然的是，对于一段时间 \([s,t]\)，如果不拥挤城市数都是 \(n\)，那么总方案数为 \(\mathcal{n^{t-s+1}}\)。初始每一天合法城市数都是 \(n\)，由于题目说明了同一城市没有交集，所以每个限制条件相当于做了一次区间减的操作。我们用标记永久化的思想，每次正常区间减，不下放标记，最后做一次最坏 \(\mathcal{O(n)}\) 的查询就做完了。

点击查看代码 
#include<bits/stdc++.h>
#define fo(x, y, z) for(register int (x) = (y); (x) <= (z); (x)++)
#define fu(x, y, z) for(register 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 fi first
#define se second
const int Ratio = 0;
const int N = 1e6 + 5;
const int mod = 1e9 + 7;
int n, m, s, t, tot, ans = 1;
int v[N * 20], son[N * 20][2];
namespace Wisadel
{
    int Wqp(ll x, int y)
    {
        int res = 1;
        while(y){if(y & 1) res = 1ll * res * x % mod; x = x * x % mod; y >>= 1;}
        return res;
    }
    #define ls (son[rt][0])
    #define rs (son[rt][1])
    #define mid ((l + r) >> 1)
    void Wupd(int rt, int l, int r, int x, int y)
    {
        if(x <= l && r <= y)
        {
            v[rt]--;
            return;
        }
        if(x <= mid)
        {
            if(!ls) ls = ++tot;
            Wupd(ls, l, mid, x, y);
        }
        if(y > mid)
        {
            if(!rs) rs = ++tot;
            Wupd(rs, mid + 1, r, x, y);
        }
    }
    void Wq(int rt, int l, int r, int now)
    {
        if(!rt)
        {
            ans = 1ll * ans * Wqp(now, r - l + 1) % mod;
            return;
        }
        if(ls || rs) Wq(ls, l, mid, now + v[rt]), Wq(rs, mid + 1, r, now + v[rt]);
        else ans = 1ll * ans * Wqp(now + v[rt], r - l + 1) % mod;
    }
    short main()
    {
        freopen("travel.in", "r", stdin) , freopen("travel.out", "w", stdout);
        n = qr, m = qr, s = qr, t = qr;
        t -= s - 1;
        tot = 1, v[1] = n;
        fo(i, 1, m)
        {
            int x = qr, l = qr - s + 1, r = qr - s + 1;
            Wupd(1, 1, t, l, r);
        }
        Wq(1, 1, t, 0);
        printf("%d\n", ans);
        return Ratio;
    }
}
signed main(){return Wisadel::main();}

正解给出的是差分的思想，也很简单，有用的信息最多 \(2\times m\) 个，我们记录每个限制信息的左右端点，到左端点处合法城市数减一，到右端点 +1 处合法城市数加一。实现也很简单，pair 记录后 sort 一遍，加入首末时间 \(\mathcal{O(m)}\) 跑一遍就行，效率比上面做法高很多。

点击查看代码 
#include<bits/stdc++.h>
#define fo(x, y, z) for(register int (x) = (y); (x) <= (z); (x)++)
#define fu(x, y, z) for(register 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 fi first
#define se second
const int Ratio = 0;
const int N = 1e6 + 5;
const int mod = 1e9 + 7;
int n, m, s, t, tot, ans = 1;
pii p[N << 1];
namespace Wisadel
{
    int Wqp(ll x, int y)
    {
        int res = 1;
        while(y){if(y & 1) res = 1ll * res * x % mod; x = x * x % mod; y >>= 1;}
        return res;
    }
    short main()
    {
        freopen("travel.in", "r", stdin) , freopen("travel.out", "w", stdout);
        n = qr, m = qr, s = qr, t = qr;
        fo(i, 1, m)
        {
            int x = qr, l = qr, r = qr;
            p[++tot] = {l, -1}, p[++tot] = {r + 1, 1};
        }
        sort(p + 1, p + 1 + tot);
        p[0] = {s, 0};
        p[++tot] = {t + 1, 0};
        fo(i, 0, tot - 1)
        {
            n += p[i].se;
            if(p[i].fi != p[i + 1].fi)
                ans = 1ll * ans * Wqp(n, p[i + 1].fi - p[i].fi) % mod;
        }
        printf("%d\n", ans);
        return Ratio;
    }
}
signed main(){return Wisadel::main();}

C. 线段树（segment）

签（？），叒没签上。

还以为真是线段树，赛时脑子被禁锢了转不了，暴力都没写出来。

据 wang54321 说这是他们暑假第二场模拟赛原题。

正解区间 dp。考虑维护包含 \([i,j]\) 的询问数量 \(s_{i,j}\)，设 \(f_{i,j}\) 表示所有询问在区间 \([i,j]\) 子树内的答案，我们枚举所有区间，然后枚举其中可行的分割点，则有状态转移方程：

\[f_{i,j} = min\left\{f_{i,k}+f_{k +1,r}-s_{i.j} \right\}\ k\in\left(l,r\right) \]

边界处理上，初始化 \(f_{i,i} = s_{i,i}\)，其余赋为极大值即可。复杂度 \(\mathcal{O(n^3)}\)。

点击查看代码 
#include<bits/stdc++.h>
#define fo(x, y, z) for(register int (x) = (y); (x) <= (z); (x)++)
#define fu(x, y, z) for(register 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 fi first
#define se second
const int Ratio = 0;
const int N = 500 + 5;
const int mod = 1e9 + 7;
int n, m;
int sum[N][N], f[N][N];
namespace Wisadel
{
    short main()
    {
        // freopen(".in", "r", stdin) , freopen(".out", "w", stdout);
        freopen("segment.in", "r", stdin) , freopen("segment.out", "w", stdout);
        n = qr, m = qr;
        memset(f, 0x3f, sizeof f);
        fo(i, 1, m)
        {
            int a = qr, b = qr;
            sum[a][b]++;
        }
        fo(i, 1, n) fu(j, n, i) sum[i][j] += sum[i][j + 1];
        fo(j, 1, n) fo(i, 1, j) sum[i][j] += sum[i - 1][j];
        fo(i, 1, n) f[i][i] = sum[i][i];
        fo(len, 2, n) fo(l, 1, n - len + 1)
        {
            int r = l + len - 1;
            fo(k, l, r - 1)
                f[l][r] = min(f[l][r], f[l][k] + f[k + 1][r] - sum[l][r]);
        }
        printf("%d\n", f[1][n]);
        return Ratio;
    }
}
signed main(){return Wisadel::main();}

D. 量子隧穿问题（experiment）

叕没做出来（？）

一个 trick 是计数转概率，答案 \(=\) 总方案数 \(\times\) 合法概率。

这样一来，盒子的状态可以得出有猫的概率，状态转移方程如下：

\[f_i'=f_i\times f_{to_i} \]

\[f_{to_i}'=f_{to_i}+f_i\times (1-f_{to_i}) \]

然后就可以做 dp 了。吗？

显然这么简单就不至于放 T4 了。发现每个隧道有可能连成环，整个图是一个基环树。当 \(n\) 存在与一个环内时转移时就会因为二者概率不独立而出错。因此我们需要断一条边，枚举两点的概率 1/0，然后再根据上面的转移方程就能无后效性地 dp 了。

注意由于 巴甫洛夫的狗 是从 1 到 \(n\) 运动的，我们断的必须是第一个与 \(n\) 在一个环内的盒子的边，可以用并查集辅助解决。

点击查看代码 
#include<bits/stdc++.h>
#define fo(x, y, z) for(register int (x) = (y); (x) <= (z); (x)++)
#define fu(x, y, z) for(register 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 fi first
#define se second
const int Ratio = 0;
const int N = 1e5 + 5;
const int mod = 1e9 + 7;
int n, m;
int to[N], p[N], fx[N];
bool in[N];
string s;
namespace Wisadel
{
    int Wfind(int x)
    {
        if(x == fx[x]) return x;
        return fx[x] = Wfind(fx[x]);
    }
    short main()
    {
        freopen("experiment.in", "r", stdin) , freopen("experiment.out", "w", stdout);
        int T = qr;
        while(T--)
        {
            n = qr; cin >> s;
            memset(in, 0, sizeof in);
            fo(i, 1, n) to[i] = qr, fx[i] = i;
            int st = 0, ans = 0;
            fo(i, 1, n) fx[Wfind(i)] = Wfind(to[i]);
            fo(i, 1, n) in[i] = (Wfind(i) == Wfind(n));
            fo(i, 1, n) fx[i] = i;
            fu(i, n, 1)
            {
                int _ = Wfind(i), __ = Wfind(to[i]);
                if(in[i] && _ != __) fx[_] = __;
                else if(in[i]) st = i;
            }
            fo(x, 0, 1) fo(y, 0, 1)
            {
                fo(i, 0, n - 1)
                    if(s[i] == 'C') p[i + 1] = 1;
                    else if(s[i] == '.') p[i + 1] = 0;
                    else p[i + 1] = (1 + mod) / 2;
                int res = 1;
                fo(i, 1, n)
                {
                    if(i == st)
                    {
                        res = 1ll * (x ? p[i] : (1 - p[i])) * (y ? p[to[i]] : (1 - p[to[i]])) % mod;
                        p[i] = x;
                        p[to[i]] = y;
                    }
                    int xx = p[i], yy = p[to[i]];
                    p[i] = 1ll * xx * yy % mod;
                    p[to[i]] = (1ll * yy + 1ll * xx * (1 - yy) % mod) % mod;
                }
                ans = (ans + 1ll * res * p[n] % mod) % mod;
            }
            fo(i, 0, n - 1) if(s[i] == '?') ans = ans * 2 % mod;
            printf("%d\n", (ans + mod) % mod);
        }
        return Ratio;
    }
}
signed main(){return Wisadel::main();}

末

怀疑这个出题人看过 某人 和 某人 的唐博，开幕巴甫洛夫的狗雷击整个机房。

挺烂的，作为 17 岁 的开局有点糟糕，希望低开高走吧。

一整天状态不太好，好在下午及时调整过来了。

一些消极的话，有反转

今天的超链接好像放的过于多了

完结撒花~

image

最后再祝自己生日快乐！

标签：03,ch,int,qr,模拟,ans,define,NOIP2024,fo
From： https://www.cnblogs.com/Ratio-Yinyue1007/p/18450400

相关文章

  • CSP2024 前集训：多校A层冲刺NOIP2024模拟赛03
    前言T1没想到正难则反，脑瘫了没敢用bitset（复杂度擦边但卡常能过），T2空间开大了挂了\(100pts\)，\(T3\)是原。T1五彩斑斓部分分\(20pts\)：\(O(n^4)\)暴力。部分分\(20+?pts\)：进行一些优化，极限数据下仍是\(O(n^4)\)。部分分\(60\sim100pts\)：bitset优化一下，\(O(\f......
  • 多校A层冲刺NOIP2024模拟赛03
    多校A层冲刺NOIP2024模拟赛03还有一个半小时结束才来，题基本没打，全口胡。T1五彩斑斓（colorful）直接统计答案难做，考虑统计四个顶点都一样的。知道\(n\)行\(m\)列的矩阵有\(\frac{n\times(n+1)\timesm\times(m+1)}{4}\)个子矩阵，这个想成选择矩阵的边界就可以证明。如何统计四......
  • 20241002 模拟赛
    这场爆零了。（惨先把题目发上来吧。A.躲避技能难度：绿机房大佬又给出解法：对于每个账号的位置，我们+1；而关键点，我们-1。（这里其实可以不必考虑正负，最后取abs就行了）然后遍历一遍整棵树，将每个节点（除了根节点）作为根的子树点权和算出来，乘上该节点与其父亲连的边的边权，每个节......
  • 10.7 模拟赛
    复盘T1看上去不难。一开始以为枚举\(a,b\)，然后考虑平方差。于是想出了这道题的解法。但是转化不过去。后来发现因为\(k\)很小直接暴力预处理就行。30min左右过大样例。T2一眼不会。想到了P1521求逆序对但还是不会做。T3,T4显然不可做。有了前几场的经验，先把所有......
  • 多校 A 层冲刺 NOIP2024 模拟赛 03
    多校A层冲刺NOIP2024模拟赛03T1五彩斑斓（colorful）签到题直接暴力枚举是\(O(n^4)\)，考虑使用\(bitset\)优化，对每个点开个\(bitset\)，预处理它所在一行它及它之前相同颜色的位置，这样就只用枚举另一个点所在列，时间复杂度为\(O(n^3+\frac{n^4}{w})\)。T2错峰旅行（travel）......
  • 网站403forbidden怎么解决
    遇到“403Forbidden”错误通常表示服务器拒绝了请求访问某个资源。解决这个问题可以从以下几个方面入手：1.检查权限设置服务器文件权限：确认服务器上的文件和目录权限是否正确。通常文件权限应为 644，目录权限应为 755。使用命令 chmod 和 chown 调整权限：sudochm......
  • 信息学奥赛复赛复习14-CSP-J2021-03网络连接-字符串处理、数据类型溢出、数据结构Map
    PDF文档公众号回复关键字:202410071P7911[CSP-J2021]网络连接[题目描述]TCP/IP协议是网络通信领域的一项重要协议。今天你的任务，就是尝试利用这个协议，还原一个简化后的网络连接场景。在本问题中，计算机分为两大类：服务机（Server）和客户机（Client）。服务机负责建立连接，客户机......
  • CSP-S 模拟赛 35
    CSP-S模拟赛35rnk14，\(45+45+15+18=123\)。T1送花愚蠢题。看到区间想到线段树，预处理出每个位置的颜色上一次出现的位置，记为\(\mathit{las}_i\)。从左到右扫右端点，给\([\max(1,\mathit{las}_{\mathit{las}_i}),\mathit{las}_i]\)减去\(d(c_i)\)，给\((\mathit{las}_i,i]\)......
  • CSP-S 模拟赛 34
    CSP-S模拟赛34rnk12，\(24+50+20+0=94\)。T1玩游戏有一个痿正解：从\(k\)到\(1\)扫左端点，对于每个左端点扫它最远能到达的右端点。如果在任何一时刻它的右端点位置\(<k\)，则断定输出No。否则检查当左端点到\(1\)时右端点能否到\(n\)。注意这里扫右端点的方式，不要每次都......
  • CSP-S 模拟赛 33
    CSP-S模拟赛33rnk19，\(30+20+40+15=105\)。T1构造字符串10pts：输出\(-1\)。30pts：对于所有\(z_i=0\)的情况，也就是说给定的两个位置字符都不同。记录有哪些位置的字符是不同的，然后从\(1\)到\(n\)扫一遍，输出除去不同的字符之外的字典序最小的字符。70pts：暴搜。枚举每个......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99