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

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

时间：2024-10-13 10:45:56浏览次数：6  
标签：ch 06 int zc num 模拟 fo NOIP2024 define

Rank

比较还行

image

image

A. 小 Z 的手套（gloves）

签。

最大值最小，一眼二分答案。双指针 check 一下就完了，复杂度 \(\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
const int Ratio = 0;
const int N = 1e5 + 5;
const int mod = 10007;
int n, m;
int a[N], b[N];
namespace Wisadel
{
    bool Wck(int x)
    {
        int j = 1;
        fo(i, 1, n)
        {
            while(j <= m && abs(a[i] - b[j]) > x) j++;
            if(j > m) return 0;
            j++;
        }
        return 1;
    }
    short main()
    {
        freopen("gloves.in", "r", stdin) , freopen("gloves.out", "w", stdout);
        // freopen(".err", "w", stderr);
        n = qr, m = qr;
        fo(i, 1, n) a[i] = qr; sort(a + 1, a + 1 + n);
        fo(i, 1, m) b[i] = qr; sort(b + 1, b + 1 + m);
        if(n > m)
        {
            fo(i, 1, n) swap(a[i], b[i]);
            swap(n, m);
        }
        int l = 0, r = 1e9;
        while(l < r)
        {
            int mid = (l + r) >> 1;
            if(Wck(mid)) r = mid;
            else l = mid + 1;
        }
        printf("%d\n", r);
        return Ratio;
    }
}
int main(){return Wisadel::main();}

B. 小 Z 的字符串（string）

分讨 dp。

赛时考虑了很久贪心做法，一直没有简单易行的方案，于是想了 dp，但没思路，于是交了假做法 50pts。

正解考虑设 \(f_{i,j,k,0/1/2}\) 表示目前 \(i\) 个 0，\(j\) 个 1，\(k\) 个 2，第 \(i+j+k\) 位为 0/1/2 的方案数。首先特判出不合法的情况，然后直接 dp 就完了，转移限制条件即为当前位与上一位不同，为方便统计坐标差，最后 \(\min\left(f_{num_0,num_1,num_2,0/1/2}\right)\) 除以 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
const int Ratio = 0;
const int N = 5e4 + 5;
const int mod = 10007;
int n;
int num[3], q[3][405], f[205][205][205][3];
string s;
namespace Wisadel
{
    short main()
    {
        freopen("string.in", "r", stdin) , freopen("string.out", "w", stdout);
        // freopen(".err", "w", stderr);
        cin >> s;
        n = s.size(); s = " " + s;
        fo(i, 1, n)
            if(s[i] == '0') num[0]++, q[0][num[0]] = i;
            else if(s[i] == '1') num[1]++, q[1][num[1]] = i;
            else num[2]++, q[2][num[2]] = i;
        int zc = (n + 1) / 2;
        if(num[0] > zc || num[1] > zc || num[2] > zc){puts("-1"); return Ratio;}
        memset(f, 0x3f, sizeof f);
        f[0][0][0][0] = f[0][0][0][1] = f[0][0][0][2] = 0;
        fo(i, 0, num[0]) fo(j, 0, num[1]) fo(k, 0, num[2])
        {
            int zc = i + j + k;
            if(i) f[i][j][k][0] = min(f[i - 1][j][k][1], f[i - 1][j][k][2]) + abs(zc - q[0][i]);
            if(j) f[i][j][k][1] = min(f[i][j - 1][k][0], f[i][j - 1][k][2]) + abs(zc - q[1][j]);
            if(k) f[i][j][k][2] = min(f[i][j][k - 1][0], f[i][j][k - 1][1]) + abs(zc - q[2][k]); 
        }
        int ans = 1e9;
        fo(i, 0, 2) ans = min(ans, f[num[0]][num[1]][num[2]][i]);
        ans /= 2;
        printf("%d\n", ans);
        return Ratio;
    }
}
int main(){return Wisadel::main();}

C. 一个真实的故事（truth）

我赛时 A 线段树啦！ 被 hack 了，悲（

看到修改查询首先考虑线段树。赛时思路被 T2 略微干扰了下于是考虑记 \(nxt_{i,j}\) 为 \(i\) 位置下一个 \(j\) 种类的坐标，答案为 \(\min\left(\max_{i\in\left[1,n\right]\left(nxt_{i,j}\right)}\right)\)，线段树统计答案是 \(\mathcal{O(1)}\) 的，但是修改操作很困难，主要是无法实现动态处理 \(nxt\) 数组，赛时尝试自我 hack 但是失败了，最慢跑了 0.5s。

考虑正解是如何优化的，改为记每个区间所有种类最靠左和最靠右的位置，pushup 时答案只会从 \(ans_{ls}\)，\(ans_{rs}\) 和左区间靠右、右区间靠左的所有种类合并出的答案。合并时取出上述至多 \(2\times k\) 个位置，然后双指针找出最小答案即可，合并其它信息比较简单。然后就做完了，\(\mathcal{O(\log n)}\) 修改 \(\mathcal{O(1)}\) 查询，带一个 \(k\) 的常数。

点击查看代码 
#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 = 5e4 + 5;
const int mod = 10007;
int n, k, m;
int a[N];
int las[N << 2], Lt[N << 2][31], Rt[N << 2][31], cnt[31], ans[N << 2];
namespace Wisadel
{
    #define ls (rt << 1)
    #define rs (rt << 1 | 1)
    #define mid ((l + r) >> 1)
    void Wpushup(int rt)
    {
        int res = 1e9, ok = 0; memset(cnt, 0, sizeof cnt);
        pii zc[2 * k + 1]; int zcz = 0;
        fo(i, 1, k) if(Rt[ls][i]) zc[++zcz] = {Rt[ls][i], i};
        fo(i, 1, k) if(Lt[rs][i]) zc[++zcz] = {Lt[rs][i], i};
        sort(zc + 1, zc + zcz + 1, [](pii &x, pii &y){return x.fi < y.fi;});
        int j = 1;
        fo(i, 1, zcz)
        {
            if(j < i) j = i;
            while(j <= zcz && ok < k)
            {
                if(!cnt[zc[j].se]) ok++;
                ++cnt[zc[j].se]; ++j;
            }
            if(ok == k) res = min(res, zc[j - 1].fi - zc[i].fi + 1);
            cnt[zc[i].se]--;
            if(!cnt[zc[i].se]) ok--;
        }
        if(res != 1e9) ans[rt] = res;
        if(ans[ls]) ans[rt] = min(ans[rt], ans[ls]);
        if(ans[rs]) ans[rt] = min(ans[rt], ans[rs]);
        fo(i, 1, k)
        {
            if(Lt[ls][i]) Lt[rt][i] = Lt[ls][i];
            else Lt[rt][i] = Lt[rs][i];
            if(Rt[rs][i]) Rt[rt][i] = Rt[rs][i];
            else Rt[rt][i] = Rt[ls][i];
        }
    }
    void Wbuild(int rt, int l, int r)
    {
        ans[rt] = 1e9;
        if(l == r)
        {
            Lt[rt][a[l]] = Rt[rt][a[l]] = l;
            las[rt] = a[l];
            return ;
        }
        Wbuild(ls, l, mid), Wbuild(rs, mid + 1, r);
        Wpushup(rt);
    }
    void Wupd(int rt, int l, int r, int x, int v)
    {
        ans[rt] = 1e9;
        if(l == r)
        {
            Lt[rt][las[rt]] = Rt[rt][las[rt]] = 0;
            Lt[rt][v] = Rt[rt][v] = x;
            las[rt] = v;
            return ;
        }
        if(x <= mid) Wupd(ls, l, mid, x, v);
        else Wupd(rs, mid + 1, r, x, v);
        Wpushup(rt);
    }
    short main()
    {
        freopen("truth.in", "r", stdin) , freopen("truth.out", "w", stdout);
        // freopen(".err", "w", stderr);
        n = qr, k = qr, m = qr;
        fo(i, 1, n) a[i] = qr;
        Wbuild(1, 1, n);
        fo(i, 1, m)
        {
            int op = qr, x, y;
            if(op == 1) x = qr, y = qr, Wupd(1, 1, n, x, y);
            else printf("%d\n", ans[1] == 1e9 ? -1 : ans[1]);
        }
        return Ratio;
    }
}
int main(){return Wisadel::main();}

D. 异或区间（xor）

trie 树和静态 RMQ，要用到笛卡尔树优化，仙姑。

末

由于一些原因导致现在才发。

打的还行，可能是前一天的动员产生了一点作用。

总是场切不了 T2 有点恼，总是 T3 打假做法有点恼，总是不会 T4 很多暴力有点恼。

起码在进步，稳住就行。

你说得对但我去的时候是 5 车厢，有一块的吗。

完结撒花~

标签：ch,06,int,zc,num,模拟,fo,NOIP2024,define
From： https://www.cnblogs.com/Ratio-Yinyue1007/p/18461954

相关文章

  • CSP 模拟 46
    A二分答案，每个数去找范围内最左边的。B相同的数不会交换，所以设\(f_{i,j,k,u}\)为到\(i\)，有了\(j\)个0，\(k\)个1，当前位置是\(u\)的最小代价，转移是暴力的，如果一个数要去前面，那么最优的方案一定不会把他往后面换，所以两次移动只有一次贡献，最终的答案要除以\(2\)。C首先......
  • 「模拟赛」多校 A 层联训 5
    A.好数（number）很签，打完之后“不是这题我能做一个小时？？”对于每个数，都把它与前面的所有数的加和求一遍存进桶里，再遇到一个新数\(a_i\)时，枚举前面的所有\(a_j，j\in[1,i-1]\)，找桶里是否存在一个数\(x\)使得\(x=a_i-a_j\)即可。因为这些数中有负数，所以我们可能会想到用map作......
  • 多校A层冲刺NOIP2024模拟赛06
    A.小Z的手套（gloves）明现的二分，我们先排序，假定\(a\)数组个数少，我们就对每一个\(a_i\)找一个\(b_i\)使其差不超过二分的值，然后贪心来讲，肯定找相差最大的那组但差不超过二分值的那个数最优，且先找比他小的那组（因为排过序了），然后套个\(multiset\)就过了，虽然\(n{log_n}^2\)......
  • [赛记] 多校A层冲刺NOIP2024模拟赛06
    小Z的手套（gloves）100pts最大值最小，考虑二分答案；首先排序，然后每次找出数量较少的那个数组中的每个数$x$在另一个数组中有没有值在范围$[x-mid,x+mid]$的（其中$mid$为二分的答案），其实只需找$x-mid$就行，最后判断一下所有数是否合法即可；因为已经升序排序，所以......
  • 多校A层冲刺NOIP2024模拟赛06
    多校A层冲刺NOIP2024模拟赛06\(T1\)A.小Z的手套（gloves）\(100pts/100pts\)容易发现将选出的左右手套各升序排序后，同一个位置上的两只手套的尺码差距一定在答案的候选集合里，画个数轴分讨一下就证完了。部分分\(20\%\)：因为\(n=m\)所以不用管谁选谁不选的问题，故\(......
  • 多校 A 层冲刺 NOIP2024 模拟赛 06
    多校A层冲刺NOIP2024模拟赛06T小Z的手套（gloves）签到题答案显然具有单调性，排序后二分答案即可。T小Z的字符串（string）签到题注意到\(n\)较小，可以使用\(O(n^3)\)的算法，直接上大\(DP\)。设计状态\(f_{i,j,k,0/1/2}\)表示从左往右填到\(i\)位，已经填了\(j\)个\(0......
  • [赛记] 多校A层冲刺NOIP2024模拟赛05
    这场数数好数（number）100pts找三个数的和，而且允许$\Theta(n^2)$，那么我们可以维护出两个数的和，然后每次顺序遍历找这个数减去前面的某个数在任意两个数的和中有没有出现过，这个也是$\Theta(n^2)$的；所以时间复杂度：$\Theta(n^2)$，如果带$\log$会过不去，要用桶维护；点击......
  • 模拟退火与爬山法
    通过向chatGPT-4o-mini提问，我注意到所有爬山法可以解决的问题模拟退火都可以解决，所以爬山法死了我不想学爬山法。具体的，对于一个多峰函数求解最值的题目都可以用模拟退火来做。如果现在在较优解\(x\)，发现了一个新的解\(x'\)，如果\(x'\)比\(x\)优那么\(x\getsx'\)否则......
  • 第106天：权限提升-WIN 系统&AD域控&NetLogon&ADCS&PAC&KDC&CVE 漏洞
    知识点1、WIN-域内用户到AD域控-CVE-2014-63242、WIN-域内用户到AD域控-CVE-2020-14723、WIN-域内用户到AD域控-CVE-2021-422874、WIN-域内用户到AD域控-CVE-2022-26923WIN-域控提权-CVE-2014-6324前提条件：1、需要域环境下一台主机普通用户账号密码2、一台主机的管理员权......
  • 多校A层冲刺NOIP2024模拟赛04
    02表示法直接递归即可，稍微写个高精。点击查看代码#include<bits/stdc++.h>usingnamespacestd;//#defineint__int128constintN=1e4;strings;intb[N],c[N],len;inta[N],tot;intread(){ intf=1,s=0;charch=getchar(); while(ch<'0'||ch>'9......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99