首页 > 其他分享 >『模拟赛』CSP-S模拟11

『模拟赛』CSP-S模拟11

时间：2024-10-14 20:24:51浏览次数：1  
标签：11 ch int max zc define CSP 模拟 fo

Rank

地狱场，一般

image

A. 玩水 (water)

签。

发现 \(n\le 1000\)，\(T\le 10\)，\(\mathcal{O(Tn^2)}\) 可过，所以简单考虑。

我写的好像是 dp？为每个点开一个大小为 26 的状态，表示从哪个字母转移而来的方案数，到该点的全部合法方案数即为 \(\max_{i\in\left[0,25\right]}\ cnt_i\)。由于是只能往下或往右走，因此一点最多由两点转移。由什么字母转移就加到什么状态上就行。特殊处理由两个相同字母转移的，此时合法方案数应为 \(\max_{i\in\left[0,25\right]}\ cnt_{a1,i}+cnt_{a_2,i}\)。然后就做完了，复杂度 \(\mathcal{O(Tn^2)}\)。

点击查看代码 
#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 pil pair<int, ll>
#define fi first
#define se second
#define int ll
const int Ratio = 0;
const int N = 1000 + 5;
int n, m;
int a[N][N][26];
char ch[N][N];
namespace Wisadel
{
    short main()
    {
        freopen("water.in", "r", stdin) , freopen("water.out", "w", stdout);
        // freopen(".err", "w", stderr);
        int T = qr;
        while(T--)
        {
            n = qr, m = qr;
            fo(i, 1, n) fo(j, 1, m) fo(k, 0, 25) a[i][j][k] = 0;
            fo(i, 1, n) fo(j, 1, m) cin >> ch[i][j];
            a[1][1][0] = 1;
            fo(i, 1, n) fo(j, 1, m)
            {
                int zc = 0;
                if(i == 1 && j == 1) continue;
                if(i == 1)
                {
                    fo(k, 0, 25) zc = max(zc, a[i][j - 1][k]);
                    a[i][j][ch[i][j - 1] - 'a'] = zc;
                }
                else if(j == 1)
                {
                    fo(k, 0, 25) zc = max(zc, a[i - 1][j][k]);
                    a[i][j][ch[i - 1][j] - 'a'] = zc;
                }
                else
                {
                    if(ch[i - 1][j] == ch[i][j - 1])
                    {
                        fo(k, 0, 25) zc = max(zc, a[i - 1][j][k] + a[i][j - 1][k]);
                        a[i][j][ch[i - 1][j] - 'a'] = zc;
                    }
                    else
                    {
                        fo(k, 0, 25) zc = max(zc, a[i - 1][j][k]);
                        a[i][j][ch[i - 1][j] - 'a'] = zc;
                        zc = 0;
                        fo(k, 0, 25) zc = max(zc, a[i][j - 1][k]);
                        a[i][j][ch[i][j - 1] - 'a'] = zc;
                    }
                }
            }
            int ok = 0;
            fo(i, 0, 25) if(a[n][m][i] >= 3){ok = 1; break;}
            if(ok) printf("1\n");
            else printf("0\n");
        }
        return Ratio;
    }
}
signed main(){return Wisadel::main();}

B. AVL 树

ex 题。

赛时头脑一热就全砸这题上了，假贪心 16pts，改掉唐错 21pts。

注意 AVL 树的性质，每个点的左右子树高度差 \(\le 1\)，并不要求同一层全选/全不选，可以通过一些智慧的方式来使得树更加偏于一方，如图：

image

然后通过手模打表，发现树的深度与最小大小成斐波那契数列关系。

深度 1 2 3 4 5
大小 1 2 4 7 12
关系 - - \(f_1+f_2+1\) \(f_2+f_3+1\) \(f_3+f_4+1\)

更好理解的，相当于是将一棵深度为 \(d-1\) 的最小 AVL 树与一棵深度为 \(d-2\) 的最小 AVL 树用一个根节点连接在一起形成了一棵深度为 \(d\) 的最小 AVL 树。

再根据题目，要求求出字典序最小的方案。由于 AVL 树还是一棵二叉搜索树，所以我们直接按先序遍历贪心加点做就行。因为选中一个点则必定要选其所有父节点，因此中序遍历是一样的。

考虑选中某个点使树仍为 AVL 树，我们直接从该点开始向根节点跳。由于我们先遍历左子树后遍历右子树，因此左子树的方案在遍历右子树时是已确定了的，我们只用在一点为其父节点的左子节点时考虑另一边的情况，最好情况即为按斐波那契数列求出的最小大小。

在遍历过程中，我们会出现钦定某个节点的右子树大小的情况，为了不与之前的抉择冲突，我们记录每个子树合法深度下界的最大值。

当然还有细节处理。我们发现并不是所有样例的 AVL 树都是左偏的，会出现许多右子树深度大于左子树的情况。对于这种情况，我们考虑优先让左子树满足该点的合法深度下界，否则让右子树满足，以符合字典序最小的原则。并且为达到在某一深度最小，我们只需钦定一个子树的下界为该点下界，另一个为该点下界 \(-1\) 即可。不用担心漏选，因为如果还有剩余我们会先遍历它。

然后就做完了，AVL 树的深度是接近 \(\log n\) 的，因此我们的复杂度是 \(\mathcal{O(n\log 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 pil pair<int, ll>
#define fi first
#define se second
#define int ll
const int Ratio = 0;
const int N = 5e5 + 5;
int n, k, rot, tot;
int siz[N];
int dep[N], mxdp[N], midp[N], h[N];
int ls[N], rs[N], fx[N];
bool yz[N];
namespace Wisadel
{
    void Wpre(int u)
    {
        dep[u] = dep[fx[u]] + 1, mxdp[u] = dep[u];
        if(ls[u]) Wpre(ls[u]), mxdp[u] = max(mxdp[u], mxdp[ls[u]]);
        if(rs[u]) Wpre(rs[u]), mxdp[u] = max(mxdp[u], mxdp[rs[u]]);
    }
    bool Wck(int u)
    {
        int now = dep[u], ned = 0;
        while(u)
        {
            if(!yz[u]) ned++;
            now = max(now, h[u]);
            if(u == ls[fx[u]])
                ned += siz[max(now - 1, midp[rs[fx[u]]]) - dep[fx[u]]];
            u = fx[u];
        }
        return ned <= k - tot;
    }
    void Wins(int u)
    {
        int now = max(h[u], dep[u]);
        while(u)
        {
            h[u] = max(h[u], now);
            if(!yz[u]) yz[u] = 1, tot++;
            if(u == ls[fx[u]] && rs[fx[u]])
                midp[rs[fx[u]]] = max(midp[rs[fx[u]]], h[u] - 1);
            u = fx[u];
        }
    }
    void Wsol(int u)
    {
        if(Wck(u)) Wins(u);
        if(ls[u] && rs[u])
        {
            if(mxdp[ls[u]] < midp[u])
                midp[ls[u]] = max(midp[ls[u]], midp[u] - 1),
                midp[rs[u]] = max(midp[rs[u]], midp[u]);
            else
                midp[ls[u]] = max(midp[ls[u]], midp[u]),
                midp[rs[u]] = max(midp[rs[u]], midp[u] - 1);
            Wsol(ls[u]), Wsol(rs[u]);
        }
        else
        {
            if(ls[u]) midp[ls[u]] = max(midp[ls[u]], midp[u]), Wsol(ls[u]);
            if(rs[u]) midp[rs[u]] = max(midp[rs[u]], midp[u]), Wsol(rs[u]);
        }
    }
    short main()
    {
        freopen("avl.in", "r", stdin) , freopen("avl.out", "w", stdout);
        // freopen(".err", "w", stderr);
        n = qr, k = qr;
        fo(i, 1, n)
        {
            int fa = qr;
            if(fa == -1) rot = i;
            else
            {
                if(i < fa) ls[fa] = i;
                else rs[fa] = i;
                fx[i] = fa;
            }
        }
        siz[1] = 1, siz[2] = 2;
        fo(i, 3, 30) siz[i] = siz[i - 1] + siz[i - 2] + 1;
        Wpre(rot);
        Wsol(rot);
        fo(i, 1, n) printf("%d", yz[i]);
        return Ratio;
    }
}
signed main(){return Wisadel::main();}

C. 暴雨

阅读理解题。

先放个勾氏题面

image

什么是 \(1\times N\) 的矩阵？什么是 \(1\times 1\) 的土地？

什么是土地内部或边界？

什么是长度为 \(N\) 的两边？

什么是一个点左右存在高度相同属于土地的点？

一个三维空间几何体积水让您说的这么勾氏也是很牛了。

南平。不过题本身也很勾氏，看懂了也就打个暴力。

这种全局性问题一般是考虑 dp 吧。设 \(f_{i,j,k,0/1}\) 表示到第 \(i\) 块土地，最大高度为 \(j\) 且之后有不低于它的土地，拆了 \(k\) 块后积水体积为奇/偶的方案数。

发现一块地两侧都是能积水的，非常不好转移，于是我们分开求，正着求一遍倒着求一遍，最大值一闭一开最后合并即可。

由于 \(k\le 25\)，所以只需记录前 \(k+1\) 高的土地的相关方案数就够了，空间复杂度是 \(\mathcal{O(n\times 25^2\times 2\times 2)}\)，long long 只能开过程量，不然会 MLE。

采用映射的方法，记录到第 \(i\) 块前 \(k+1\) 高度的土地和位置，然后考虑转移，分两种情况：

  • \(v_{i,j}\ge a_{i+1}\)：

\[f_{i+1,j',k,0/1}\leftarrow f_{i,j,k,0/1} \]

\[f_{i+1,j',k+1,0/1}\leftarrow f_{i,j,k,0/1} \]

  • 相反：

\[f_{i+1,mp_{a_{i+1}},k,0/1}\leftarrow f_{i,j,k,0/1} \]

\[f_{i+1,j',k+1,0/1}\leftarrow f_{i,j,k,0/1} \]

最后枚举最高点乘法原理拼接即可。

点击查看代码 
#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 pil pair<int, ll>
#define fi first
#define se second
const int Ratio = 0;
const int N = 25000 + 5;
const int mod = 1e9 + 7;
int n, m;
int a[N], id[N];
multiset<int>::iterator it;
ll ans;
namespace Wisadel
{
    struct rmm
    {
        int f[N][26][26][2], val[N][26], cnt[N];
        multiset<int> st;
        unordered_map<int,int> mp[N];
        void Wsol()
        {
            st.insert(0);
            fo(i, 1, n)
            {
                st.insert(a[i]);
                it = st.end(); it--;
                for(; ; it--)
                {
                    mp[i][*it] = ++cnt[i];
                    val[i][cnt[i]] = *it;
                    if(it == st.begin() || cnt[i] == m + 1) break;
                }
            }
            f[0][1][0][0] = 1, val[0][cnt[0] = 1] = 0;
            fo(i, 0, n - 1) fo(j, 1, cnt[i]) fo(k, 0, m) fo(p, 0, 1)
                if(f[i][j][k][p])
                {
                    int zc, zt;
                    if(val[i][j] >= a[i + 1])
                    {
                        zc = mp[i + 1][val[i][j]], zt = p ^ (val[i][j] - a[i + 1] & 1);
                        f[i + 1][zc][k][zt] = (f[i + 1][zc][k][zt] + f[i][j][k][p]) % mod;
                        zt = p ^ (val[i][j] & 1);
                        if(k < m) f[i + 1][zc][k + 1][zt] = (f[i + 1][zc][k + 1][zt] + f[i][j][k][p]) % mod;
                    }
                    else
                    {
                        zc = mp[i + 1][a[i + 1]], zt = p ^ (val[i][j] & 1);
                        f[i + 1][zc][k][p] = (f[i + 1][zc][k][p] + f[i][j][k][p]) % mod;
                        zc = mp[i + 1][val[i][j]];
                        if(k < m) f[i + 1][zc][k + 1][zt] = (f[i + 1][zc][k + 1][zt] + f[i][j][k][p]) % mod;
                    }
                }
        }
    } Q, H;
    short main()
    {
        freopen("rain.in", "r", stdin) , freopen("rain.out", "w", stdout);
        // freopen(".err", "w", stderr);
        n = qr, m = qr;
        fo(i, 1, n) a[i] = qr, id[i] = i;
        Q.Wsol(); reverse(a + 1, a + 1 + n);
        H.Wsol(); reverse(a + 1, a + 1 + n);
        sort(id + 1, id + n + 1, [](int aa, int bb){return a[aa] > a[bb];});
        fo(pop, 1, n)
        {
            if(a[id[pop]] < a[id[m + 1]]) break;
            int i = id[pop], vv = a[i];
            fu(j, Q.cnt[i - 1], 1)
            {
                if(Q.val[i - 1][j] > vv) break;
                fu(k, H.cnt[n - i], 1)
                {
                    if(H.val[n - i][k] >= vv) break;
                    fo(u, 0, m)
                        ans = (ans + 1ll * Q.f[i - 1][j][u][0] * H.f[n - i][k][m - u][0] % mod) % mod,
                        ans = (ans + 1ll * Q.f[i - 1][j][u][1] * H.f[n - i][k][m - u][1] % mod) % mod;
                }
            }
        }
        printf("%lld\n", ans);
        return Ratio;
    }
}
signed main(){return Wisadel::main();}

D. 置换

手题，不很会。

E. 传统题

炉石题组合推式子题，不很会。

末

因为公告所以开场磕了会 T4 发现不会然后转战 T1，还好在 huge 加题前就扔了，赢（？）。

然后由于 T3 逆天题面和 T4 不写，打完 T5 暴力就全磕 T2 了，结果还是假了，甚至比暴力分低（

还因为你们能比学长强点

还是算了

标签：11,ch,int,max,zc,define,CSP,模拟,fo
From： https://www.cnblogs.com/Ratio-Yinyue1007/p/18464934

相关文章

  • 【JPCS独立出版 | ISSN:1742-6596 | 往届均稳定EI检索】第九届计算机技术与机械电气工
    第九届计算机技术与机械电气工程国际学术论坛（ISCME2024）将于2024年11月8-10日在中国南京隆重召开。本次论坛将围绕“计算机技术”、“机械电气工程”等多个学术领域进行深度探讨，旨在融合各专业的最新研究成果，以促进相关学科和行业的创新与发展。会议将汇聚来自全球的学者......
  • 「模拟赛」CSP-S 模拟 11（T2 超详细）
    比赛链接A.玩水(water)签到。发现如果要找两条路径的话，能找到的充要条件是存在一个点的上方和左方的字母相同。（即使两条走过的点截然不同的路径也符合，这时终点会成为这个点）。即存在一个位置\((i,j)\)使得\(s_{i-1,j}=s_{i,j-1}\)，我们称位置\((i,j)\)是好位置。扩展到三......
  • 2024.10.13 模拟赛
    2024.10.13模拟赛T1「KDOI-10」商店砍价赛时直接口胡出一个错误的贪心。一开始的想法是按照\(v[i]\)排序，然后假设输入的长度为\(n\)位。那么对于排序后\(n-5\)位直接选择操作一。对于剩下的，直接bdfs所有情况选答案，复杂度\(O(n\logn)\)。貌似可行，结果随便一个数据......
  • [47] (CSP 集训) CSP-S 模拟 11
    因为有人想看T3\(nk^2\)所以先发一下A.玩水注意到只有在形如下面这样的地方才会发生分叉?aa?所以\(f_{i,j}\)表示从\((1,1)\)到\((i,j)\)的矩阵中的最大路径方案数，考虑转移普通的转移是\(f_{i,j}=\max(f_{i,j-1},f_{i-1,j})\)如果\(a_{i-1,j}=a_{i,j-1}\)，则有......
  • 2024/10/13 模拟赛总结
    人机体检，\(0+0+0+0=0\)，打代码源去了#A.一般图最小匹配下次看到这种范围一定要想到dp啊，令\(dp_{i,j}\)为前\(i\)个元素选了\(j\)对点的最小代价由于边权是绝对值，可以对原数组排一遍序，选取的两个点就一定在排序后数组的相邻节点那么就可以得出式子：\(dp_{i,j}=\min\{dp_......
  • 【2024潇湘夜雨】WIN10_Ent-G_22H2.19045.5011软件选装纯净特别版10.14
    【系统简介】=============================================================1.本次更新母盘来自WIN10_Ent-G_22H2.19045.5011.进桌面后稍等片刻，等待后续部分优化完成。2.全程离线精简、无人值守调用优化处理制作。部分优化适配系统可能要重启几次，即使显示适配失败也不要在意，可能......
  • 题解：P11132 【MX-X5-T4】「GFOI Round 1」epitaxy
    ProblemLink【MX-X5-T4】「GFOIRound1」epitaxy题目描述给你两个正整数\(n,m\)。定义一个\(1\simn\)的排列\(p\)的价值为所有的\(n-m+1\)个长度为\(m\)的连续子串内最大值的最大公因数。（规定单个数的最大公因数为其自身。）请你求出一个在所有\(1\simn\)......
  • 题解：P11145 Strange Homura Game
    ProblemLinkStrangeHomuraGame题意让你猜测一个数\(n\)，你只能输出两次，每次输出一个数\(x\)，返回\(x\bmodn\)。Solution令输入的数为\(A,B\)，输出的数为\(a,b\)，答案为\(n\)。一开始想的是CRT，但只能询问\(2\)次。发现输入的值是经过\(\bmodn\)的，已知\((A-a)......
  • 题解：P11063 【MX-X4-T3】「Jason-1」数对变换
    ProblemLink【MX-X4-T3】「Jason-1」数对变换题外话场上把贪心注重在一个奇怪地方了，导致交的时候已经有\(9\)个人\(\textcolor{green}{AC}\)了（哭）。题意简述对于数对\((x,y)\)，你可以执行以下两种变换：类型1：取\(1\lek\lex\)，令\((x,y)\gets(\lfloor\frac{x}{k}......
  • 省选模拟赛
    认为只有k个位置有值的序列差分之后会形成k个颜色段，建议送回普及组重学差分与前缀和A考虑把硬币序列异或差分，操作变成选两个距离为\(a_i\)的位置翻转，差分完序列上只有\(2k\)个\(1\)，对其中任意两个\(1\)预处理出把它们同时变为\(0\)的最小操作数，状压BFS即可。B......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99