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

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

时间:2024-11-01 17:47:04浏览次数:1  
标签:ch const 17 int tot 模拟 mod NOIP2024 fo

Rank

一般

image

image

A. 网络

签不上的签到题。

首先考虑枚举路径的做法,如果先枚举再计算的话复杂度会是 \(\mathcal{O(\binom{n+m-2}{n-1}(n+m))}\) 的,稍微优化一点的过程中可以去掉后面的 \((n+m)\)。考虑此时我们要记什么,首先遇到加号其前面的值 \(z\) 就确定了,若上个符号为乘号那么需记录乘数 \(x\),同时显然还需记录当前的数 \(y\),可以得到 30pts。

迁移到 \(\mathcal{O(nm)}\) 的做法上,稍微改变一些定义,将记当前的数直接改为记当前的数与所记乘数的积。分讨三种转移:

  • 若当前位置为数字:\(y\leftarrow 10x+x\cdot a_{i,j}\)
  • 若当前位置为乘号:\(x\leftarrow y,\ y\leftarrow 0\)
  • 若当前位置为加号:\(z\leftarrow y+z,\ y\leftarrow 0,\ x\leftarrow 1\)

发现这样转移仍然是针对一个表达式的,优化也很简单,提前处理可能的 \(x\) 值,即到这个点一共有几种可能。感性理解就是:在这个点一共会进行棘刺这样的转移。然后就做完了,复杂度 \(\mathcal{O(nm)}\)。

点击查看代码
#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;
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 fi first
#define se second
#define pii pair<int, int>
#define P_B(x) push_back(x)
#define M_P(x, y) make_pair(x, y)
const int Ratio = 0;
const int N = 2000 + 5;
const int mod = 998244353;
int n, m;
string s[N];
ll z[N][N], x[N][N], y[N][N], zc[N][N];
namespace Wisadel
{
    short main()
    {
        freopen("grid.in", "r", stdin), freopen("grid.out", "w", stdout);
        n = qr, m = qr;
        fo(i, 1, n) cin >> s[i], s[i] = " " + s[i];
        zc[1][0] = 1;
        x[1][0] = 1;
        fo(i, 1, n) fo(j, 1, m)
        {
            x[i][j] = (x[i - 1][j] + x[i][j - 1]) % mod;
            y[i][j] = (y[i - 1][j] + y[i][j - 1]) % mod;
            z[i][j] = (z[i - 1][j] + z[i][j - 1]) % mod;
            zc[i][j] = (zc[i - 1][j] + zc[i][j - 1]) % mod;
            if(s[i][j] == '+')
            {
                z[i][j] = (z[i][j] + y[i][j]) % mod;
                x[i][j] = zc[i][j];
                y[i][j] = 0;
            }
            else if(s[i][j] == '*')
            {
                x[i][j] = y[i][j];
                y[i][j] = 0;
            }
            else y[i][j] = (y[i][j] * 10 % mod + (s[i][j] - '0') * x[i][j] % mod) % mod;
        }
        printf("%lld\n", (z[n][m] + y[n][m]) % mod);
        return Ratio;
    }
}
signed main(){return Wisadel::main();}

B. 矩形

正解是根号分治。不是很会,于是在 GGrun 的帮助下焯过去了。

思路很平凡,将同一列和同一行的提前处理出来,然后看哪个少用哪个。求答案时朴素实现是枚举两列,双指针移动找匹配段,然后用 \(\frac{x(x-1)}{2}\) 贡献统计答案。发现会 TLE,于是考虑少些无用的枚举。我们枚举一列,然后枚举上面的每个点,再枚举该点所在行上的点,更新这些点所在列的贡献。我们将 \(\frac{x(x-1)}{2}\) 拆成 \(\frac{x^2}{2}-\frac{x}{2}\),发现可以根据转移式 \((x+1)^2=x^2+2x+1\) 直接更新二者的值,最后再枚举每一列统计贡献即可,然后就过了,复杂度 \(\mathcal{O(能过)}\)。(我的实现常数过大会被卡

焯代码
#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;
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 fi first
#define se second
#define pii pair<int, int>
#define P_B(x) push_back(x)
#define M_P(x, y) make_pair(x, y)
const int Ratio = 0;
const int N = 2e5 + 5;
const int mod = 998244353;
int n, tot;
int prex[N], prey[N];
ll sum[N], ans, ans1[N], ans2[N];
struct rmm
{
    int x, y;
    bool operator < (const rmm &A) const
    {
        return y == A.y ? x < A.x : y < A.y;
    }
} d[N], p[N];
pii xx[N], yy[N];
namespace Wisadel
{
    bool cmpn(rmm A, rmm B){return A.x == B.x ? A.y < B.y : A.x < B.x;}
    bool cmpm(rmm A, rmm B){return A.y == B.y ? A.x < B.x : A.y < B.y;}
    short main()
    {
        freopen("rect.in", "r", stdin), freopen("rect.out", "w", stdout);
        n = qr;
        ll c = 1;
        fo(i, 2, n) sum[i] = sum[i - 1] + c, c++;
        fo(i, 1, n) d[i].x = p[i].x = qr, d[i].y = p[i].y = qr;
        sort(d + 1, d + 1 + n, cmpn);
        sort(p + 1, p + 1 + n, cmpm);
        int zoz = 0;
        fo(i, 1, n) if(d[i].x != d[i - 1].x) xx[++tot].fi = d[i].x, xx[tot].se = i, prex[d[i].x] = tot;
        fo(i, 1, n) if(p[i].y != p[i - 1].y) yy[++zoz].fi = p[i].y, yy[zoz].se = i, prey[p[i].y] = zoz;
        if(zoz < tot)
        {
            swap(tot, zoz);
            fo(i, 1, max(tot, zoz)) swap(xx[i], yy[i]);
            fo(i, 1, n) swap(d[i].x, p[i].y), swap(d[i].y, p[i].x), swap(prex[i], prey[i]);
        }
        xx[tot + 1].se = n + 1;
        yy[zoz + 1].se = n + 1;
        fo(i, 1, tot)
        {
            int z1 = xx[i].se;
            while(z1 <= xx[i + 1].se - 1)
            {
                int z2 = lower_bound(p + 1, p + 1 + n, (rmm){d[z1].x, d[z1].y}) - p;
                int bz = prey[p[z2].y]; z2++;
                while(z2 <= yy[bz + 1].se - 1)
                {
                    ans1[prex[p[z2].x]] += ans2[prex[p[z2].x]] * 2 + 1, ans2[prex[p[z2].x]]++;
                    z2++;
                }
                z1++;
            }
            fo(j, i + 1, tot)
                ans += (ans1[j] - ans2[j]) / 2, ans1[j] = ans2[j] = 0;
        }
        printf("%lld\n", ans);
        return Ratio;
    }
}
signed main(){return Wisadel::main();}

正解晚上补。

C. 集合

容斥 + FFT,男蚌。

赛时猜了个结论拿了 10pts。

D. 倒水

期望 + 线段树优化,牛魔。

赛时打了个暴力拿了 24pts。

比昨天强点,但不多。

开题一眼三道取模压迫感就来了,因为 T1 看了会不会打就先通读了一遍,然后打 T4,打完打的 T2,结果空间没改 + 取模没改直接嗯挂 52pts。

T1 最后 15min 想到了过程中计算,少了个很大的常数但没有多得分,其实感觉到这再想想就能做出来了,可惜回看得太晚来不及了。

突然想到一场比赛三道 dp,两道计数(


完结撒花~

www 怎么状态越来越差了(

image

标签:ch,const,17,int,tot,模拟,mod,NOIP2024,fo
From: https://www.cnblogs.com/Ratio-Yinyue1007/p/18520977

相关文章

  • NOIP2024 模拟赛 #12
    学长出的模拟赛,风格挺好。赛时8:00T1会了一个\(O(n^2\logn)\)的做法,先写一下,看看能不能过样例。8:20过了小样例,大样例跑得慢但是是对的。8:40发现一个好的做法,可以枚举\(c_i\)最小的那一天选了哪个,再枚举\(k\)天,这样纯枚举复杂度是\(O(k)\)的。但是有些细节不太......
  • 11.01模拟赛
    T1把所有的薯片按热量排序,\(l,r\)表示选取的区间的左右端点,当区间中的种类数等于\(k\)时,这个区间合法,更新答案并\(l\)++,否则\(r\)++,直到\(r=n\),最后的话要看\(l\)能否往上加,开始没有写,所以最后一个大样例一直不过,调了20min左右。T2构造题,感觉很难啊,就想着先找最多数量......
  • Navicat 17下载与安装
    1、安装包 Navicat17:链接:https://pan.quark.cn/s/c75e892c4705提取码:YvyFNavicat16:链接:https://pan.quark.cn/s/63c07b20ea7b提取码:B9ij2、安装教程(这里以安装Navicat17为例)1)       如之前已安装的需卸载当前Navicat,如未安装,直接双击无限试用Navicat.bat脚......
  • 2023CSP-S 复赛模测(日记和×××) - 模拟赛记录
    Preface这套题说实话挺水的,它的水不仅仅是在数据上(实际得分比期望得分高了\(50+\)分),而且正解也神奇得不像个正解(全是各种分类讨论卡子任务的,感觉像是出题人水平不够一样)。日记和最短路(shortway)(话说最短路的英语不应该是shortestpath吗?)题目中给了一个DAG,然后要求用两种方......
  • 2024.10.7 模拟赛 多校3
    模拟赛水题场。T1colorful签。感觉题挺好,正难则反,找出四角都相同的。在这两排有6个四角相同的矩形对于两排来说,我们只需要记录相同的列的个数,然后能直接算出个数。发现桶排每次清空复杂度太高,考虑每次只开一排的桶,只会有\(n\)个。code#include<bits/stdc++.h>u......
  • 2024-11-1校内模拟赛总结
    前言:从下了早读一直打到吃午饭,\(4h\)左右的时间,\(IOI\)赛制,\(6\)道\(ABC203\)、\(204\)的\(CDE\)题,\(318\)分。赛时:T1:水,直接模拟即可。\(100\)分。T2:中位数二分答案,有点难,但之前写过,也是直接拿下了啊。100分。T3:也是模拟,但是我开\(map\)存的是\(pair<int,int>......
  • MindSponge分子动力学模拟——增强采样(2024.11)
    技术背景关于增强采样(EnhancedSampling)算法的具体原理,这里暂不做具体介绍,感兴趣的童鞋可以直接参考下这篇综述文章:Enhancedsamplinginmoleculardynamics。大致的作用就是,通过统计力学的方法,使得目标分子的CV(CollectiveVariables)具有一个尽可能大的采样子空间,并且可以将其还......
  • CesiumJS 案例 P17:添加文本、文本样式、删除文本、移动文本
    CesiumJSCesiumJSAPI:https://cesium.com/learn/cesiumjs/ref-doc/index.htmlCesiumJS是一个开源的JavaScript库,它用于在网页中创建和控制3D地球仪(地图)一、添加文本<!DOCTYPEhtml><htmllang="en"> <head> <metacharset="UTF-8"/> &l......
  • Kafka python模拟整理
    模拟需要用到kafka的包,需要pip安装,但注意pipinstallkafka不适用于python3.x的某个版本以上,均已经换成kafka-python推荐使用版本2.0.2,目前稳定pip没有的问题如果是windows环境,可通过直接去官网下载python版本,指定版本会顺带安装pip如果是linux环境,有节点是不带pip的,可使用yu......
  • 【C++】string 类模拟实现:深入探索字符串操作原理
     快来参与讨论......