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

多校A层冲刺NOIP2024模拟赛19

时间:2024-11-07 18:58:10浏览次数:1  
标签:19 text 多校 times int using inline NOIP2024 mod

讲个笑话:

(讨论时间)

huge:(叹气)这讨论啊,就是改不了,这换了铃声了,也没……

众人:现在是讨论时间啊。

huge:(停顿)那刚才大课间那会哇啦哇啦的……

图书管理

简要题意

给定一个长度为\(n(n\le 10^4)\)的排列,求\(\sum\limits_{l=1}^n\sum\limits_{r=l}^n[r-l为偶数]l\times r\times f_{l,r}\)

solution

签到题,但我\(ccx\)被卡了。

部分分是对顶堆、主席树之类的带\(\log\)做法。

枚举中位数,假设当前枚举到\(i\),然后将大于它的数的记为1,小于它的数的记为-1,求前缀和\(s\),如果\(1\le l\le i\le r\le n\)能产生贡献时当且仅当\(s_r-s_{l-1}=0\)。

直接做就完了,用数组求常数较小,可以直接过。

点此查看代码
#include<bits/stdc++.h>
#include<bits/extc++.h>
// #include<sys/timeb.h>
using namespace __gnu_pbds;
using namespace std;
// struct timeb timer;
#define rep(i,s,t,p) for(int i = s;i <= t;i += p)
#define drep(i,s,t,p) for(int i = s;i >= t;i -= p)
#ifdef LOCAL
    FILE *InFile = freopen("in.in","r",stdin),*OutFile = freopen("out.out","w",stdout);
    // FILE *ErrFile = freopen("err.err","w",stderr);
#else
    FILE *InFile = freopen("book.in","r",stdin),*OutFile = freopen("book.out","w",stdout);
#endif
using ll = long long;using ull = unsigned long long;
using db = double;using ldb = long double;
const int N = 1e4 + 10;
int n,a[N];
namespace IO{
    char buf[1<<23],*p1,*p2;
    #define gc() (p1==p2&&(p2=(p1=buf)+fread_unlocked(buf,1,1<<23,stdin),p1==p2)?EOF:*p1++)
    #define pc putchar_unlocked
    template<class T>
    inline void read(T &x){
        x = 0;
        char s = gc();
        for(;s < '0' || s > '9';s = gc());
        for(;'0' <= s && s <= '9';s = gc()) x = (x<<1)+(x<<3)+(s^48);
    }
    template<class T,class... Args>
    inline void read(T &x,Args&... argc){read(x);read(argc...);}
    template<class T>
    inline void write(T x){
        static int sta[20],top = 0;
        do{sta[++top] = x%10,x /= 10;}while(x);
        do{pc(sta[top--]+'0');}while(top);
    }
    inline void write(char x){pc(x);}
    template<class T,class... Args>
    inline void write(T x,Args... argc){write(x);write(argc...);}
}using namespace IO;
int tp[N<<2];
inline void solve(){
    ll ans = 0;
    read(n);rep(i,1,n,1) read(a[i]);
    rep(l,1,n,1){
        int tot1 = 0,tot2 = 0;
        queue<int> q;
        rep(r,l,n,1){
            tot1 += (a[r] > a[l]),tot2 += (a[r] < a[l]);
            tp[tot1-tot2+n] += r;
        }
        tot1 = tot2 = 0;
        drep(j,l,1,1){
            tot1 += a[j] > a[l],tot2 += a[j] < a[l];
            ans += 1ll*j*tp[tot2-tot1+n]*a[l];
        }
        tot1 = tot2 = 0;
        rep(r,l,n,1){
            tot1 += (a[r] > a[l]),tot2 += (a[r] < a[l]);
            tp[tot1-tot2+n] = 0;
        }
    }    
    write(ans,'\n');
}
signed main(){
    // cin.tie(nullptr)->sync_with_stdio(false);
    solve();
}

两棵树

简要题意

给你两棵大小为\(n(n\le 2\times10^5)\)树,一个节点有\(\frac{1}{2}\)的概率出现在一棵树中,有\(\frac{1}{2}\)的概率出现在另一棵树中,求两棵树连通块个数乘积的期望数。

solution

考虑到连通块数=剩余的点数-剩余的边数,则贡献\(X\times Y\)可以拆成4部分,为\(\text{点}\times\text{点}-\text{边}\times\text{点}-\text{点}\times\text{边}+\text{边}\times\text{边}\)。

  1. \(\text{点}\times\text{点}\)的贡献。

    考虑在\(T\)中选择点\(x\),\(U\)中选择点\(y\)。若\(x = y\),则贡献为\(0\),反之,贡献为\(\frac{1}{4}\)。所以总贡献为\(\frac{\mathrm{C}_{n}^2}{4}\)

  2. \(\text{边}\times\text{点}\)的贡献。

    考虑\(T\)中留下边\((x,y)\),\(U\)中留下点\(k\),则当\(x=k\)或\(y=k\)时贡献为0,反之贡献为\(\frac{1}{8}\)。所以总贡献为\(\frac{(n-1)\times (n-2)}{8}\)。

  3. \(\text{边}\times\text{边}\)的贡献。

    考虑\(T\)中留下\((x,y)\),\(U\)中留下\((u,v)\),当\(x,y,u,v\)中存在两个相同时,贡献为0,反之,贡献为\(\frac{1}{16}\)。

    考虑如何计算,可以枚举\((x,y)\),统计符合条件的\((u,v)\)个数,就是\(n-1-deg_{U}x-deg_{U}y+[U\text{中存在}(u,v)=(x,y)]\)

点此查看代码
#include<bits/stdc++.h>
using namespace std;
#define rep(i,s,t,p) for(int i = s;i <= t;i += p)
#define drep(i,s,t,p) for(int i = s;i >= t;i -= p)
#ifdef LOCAL
    FILE *InFile = freopen("in.in","r",stdin),*OutFile = freopen("out.out","w",stdout);
#else
    FILE *InFile = freopen("tree.in","r",stdin),*OutFile = freopen("tree.out","w",stdout);
#endif
using ll = long long;using ull = unsigned long long;
using db = double;using ldb = long double;
constexpr int N = 2e5 + 10,mod = 998244353;
struct node{int x,y;}a[N],b[N];
int n,d[N];
inline int power(int a,int b,int mod){
    int res = 1;
    for(;b;b >>= 1,a = 1ll*a*a%mod)
        if(b&1) res = 1ll*res*a%mod;
    return res;
}
inline int Inv(int x){return power(x,mod-2,mod);}
set<int> st[N];
inline void solve(){
    cin>>n;
    rep(i,1,n-1,1) cin>>a[i].x>>a[i].y;
    rep(i,1,n-1,1) 
        cin>>b[i].x>>b[i].y,
        st[b[i].x].insert(b[i].y),st[b[i].y].insert(b[i].x),
        d[b[i].x]++,d[b[i].y]++;
    int ans = 0;
    ans = (ans + 1ll*n*(n-1)%mod*Inv(4)%mod)%mod;
    ans = (ans - 1ll*(n-1)%mod*(n-2)%mod*Inv(4)%mod + mod) % mod;
    if(n >= 4) rep(i,1,n-1,1) 
        ans = (ans + 1ll*(n-1-d[a[i].x]-d[a[i].y] + st[a[i].x].count(a[i].y))*Inv(16)%mod)%mod;
    cout<<ans<<'\n';    
}
signed main(){
    cin.tie(nullptr)->sync_with_stdio(false);
    solve();
}

函数

简要题意

定义一个函数\(f(x)=(x\oplus a)-b\),其中\(a,b\)为给定的参数。

有一个长度为\(n(n\le 10^6)\)的序列\(x\),给出\(q(q\le 10^6)\)次询问,每次给定\(a,b\),问是否存在\(i\in [1,n)\),满足\(f(x_i)\times f(x_{i+1})\le 0\)。

solution

简单题,可是赛时没想到用Trie。

考虑求出\(x_i\oplus a\)最大的位置\(maxpos\)和最小的位置\(minpos\),如果\(f(x_{maxpos})\times f(x_{minpos}) > 0\)显然无解。

反之,考虑二分,每次取中点\(mid\),易知\(f(x_{mid})\)肯定与\(f(x_{maxpos})\)或\(f(x_{minpos})\)中的一个异号,所以\(f(x_{maxpos})\)或\(f(x_{minpos})\)与\(f(x_{mid})\)中必然有一对异号,正确性显然。

时间复杂度\(O(n\log V + q\times(\log n+\log V))\approx 2e8\)略微卡常。

点此查看代码
#include<bits/stdc++.h>
using namespace std;
#define rep(i,s,t,p) for(int i = s;i <= t;i += p)
#define drep(i,s,t,p) for(int i = s;i >= t;i -= p)
#ifdef LOCAL
    FILE *InFile = freopen("in.in","r",stdin),*OutFile = freopen("out.out","w",stdout);
#else
    FILE *InFile = freopen("fun.in","r",stdin),*OutFile = freopen("fun.out","w",stdout);
#endif
using ll = long long;using ull = unsigned long long;
using db = double;using ldb = long double;
namespace IO{
    char buf[1<<23],*p1,*p2;
    #define gc() (p1==p2&&(p2=(p1=buf)+fread_unlocked(buf,1,1<<23,stdin),p1==p2)?EOF:*p1++)
    #define pc putchar_unlocked
    template<class T>
    inline void read(T &x){
        x = 0;
        char s = gc();
        for(;s < '0' || s > '9';s = gc());
        for(;'0' <= s && s <= '9';s = gc()) x = (x<<1)+(x<<3)+(s^48);
    }
    template<class T,class... Args>
    inline void read(T &x,Args&... argc){read(x);read(argc...);}
    template<class T>
    inline void write(T x){
        static int sta[20],top = 0;
        do{sta[++top] = x%10,x /= 10;}while(x);
        do{pc(sta[top--]+'0');}while(top);
    }
    inline void write(char x){pc(x);}
    template<class T,class... Args>
    inline void write(T x,Args... argc){write(x);write(argc...);}
}using namespace IO;
const int N = 1e6 + 10,V = 1e9 + 10,LV = 29;
int n,q,x[N];
struct Trie{
    int tree[N*30][2],tot,en[N*30],ex[N*30];
    inline void insert(int x,int pos){
        int p = 0;
        drep(i,LV,0,1){
            bool k = (x>>i)&1;
            if(!tree[p][k]) tree[p][k] = ++tot;
            p = tree[p][k];
        }
        if(!en[p]) en[p] = pos;
        ex[p] = max(ex[p],pos);
    }
    inline int qryn(int x){
        int p = 0;
        drep(i,LV,0,1){
            bool k = (x>>i)&1;
            if(tree[p][k]) p = tree[p][k];
            else p = tree[p][!k];
        }
        return en[p];
    }
    inline int qryx(int x){
        int p = 0;
        drep(i,LV,0,1){
            bool k = (x>>i)&1;
            if(tree[p][!k]) p = tree[p][!k];
            else p = tree[p][k];
        }
        return ex[p];
    }
}trie;
inline bool cmp(int x,int y){return (x<=0&&y>=0)||(x>=0&&y<=0);}
inline void solve(){
    read(n,q);rep(i,1,n,1) read(x[i]);
    rep(i,1,n,1) trie.insert(x[i],i);
    while(q--){
        int a,b;read(a,b);
        int l = trie.qryn(a);int r = trie.qryx(a);
        if(l > r) swap(l,r);
        auto f = [&](int pos){return (x[pos]^a)-b;};
        if(!cmp(f(l),f(r))){puts("-1");continue;}
        int pos1 = l,pos2 = r,ans = 0;
        int f1 = f(pos1),f2 = f(pos2);
        bool flag = true;
        while(l <= r){
            int mid = (l + r) >> 1;
            if(cmp(f2,f(mid))) flag = false,ans = mid,l = mid + 1;
            else  flag = true,ans = mid,r = mid - 1;
        }
        if(flag) write(ans-1,'\n');
        else write(ans,'\n');
    }
}
signed main(){solve();}

编辑

简要题意

给定\(k(k\le 30)\)和两个字符串\(S,T(|S|,|T|\le 5\times 10^4)\),\(\forall i\in[0,k]\),求出\(T\)中多少个非空子串与\(S\)的编辑距离恰好为\(i\)。

solution

严格弱化版:[BJOI2015] 隐身术

部分分直接暴力DP。正解好像很难的样子,不会。

30pts

枚举 \(T\) 的某一子串进行编辑距离求解的DP,具体状态为让 \(A\) 变成 \(B\),现在只考虑 \(A[1:i]\) 变成 \(B[1:j]\) 的编辑距离为 \(f[i][j]\),转移时考虑删除,添加,修改第 \(i+1\) 个位置即可,时间复杂度为 \(O(n^4)\)​。

100pts

枚举每个后缀,\(f_{i,j}\) 表示最大的 \(x\),使得 \(S[1:x]\) 和 \(T[1:x+j]\) 可以在 \(i\) 次编辑内得到,显然若 \(x\) 可以,所有\(x_0 \leq x\), \(S[1:x_0]\) 和 \(T[1:x_0+j]\) 都可以在 \(i\) 次编辑内得到。

考虑如何转移,先考虑做完第 \(j\) 次编辑操作后往外延申,可以延申的即为 \(S\) 的一个后缀和 \(T\) 的一个后缀的最长公共前缀,即\(f_{i,j} = f_{i,j} + \text{LCP}(S[f_{i,j + 1}:|S|],T [f_{i,j} + j + 1 . .: |T|])\),随后我们可以通过对\(f_{i+1,j-1},f_{i+1,j},f_{i+1,j+1}\) 三项进行转移,即考虑下一次的编辑的具体操作是删除添加还是修改。

每次要算的两个后缀的前缀下标不会差超过 \(k\),因此一共至多求 \(O(nk)\) 次 LCP,可以利用二分+ hash 的方式解决。

记录每个后缀中 \(f_{i,j}=|S|\) 的那些状态,即可计算出最终答案,时间复杂度为 \(O(nk^2+nk \log n)\)。

P

image

标签:19,text,多校,times,int,using,inline,NOIP2024,mod
From: https://www.cnblogs.com/hzoi-Cu/p/18533780

相关文章

  • 多校A层冲刺NOIP2024模拟赛19
    多校A层冲刺NOIP2024模拟赛19\(T1\)A.图书管理(book)\(90pts/90pts\)部分分\(90pts\):平衡树/线段树、主席树上二分/对顶堆暴力维护中位数,同luoguP3871[TJOI2010]中位数|luoguP1168中位数,时间复杂度为\(O(n^{2}\logn)\),需要适当卡常。点击查看代码in......
  • Oracle 19c Rac环境部署
    Oracle19cRac环境部署前言搭建Oracle19cRac环境部署,使用dns进行解析。一、软件包linuxx64_193000_grid_home.ziplinuxx64_193000_db_home.zip二、配置信息1.IP地址规划编辑/etc/hosts#publicip10.1.50.213kezcc1kezcc1.zcc.com10.1.50.214kezcc......
  • BTTPS|cas:1341215-19-7
    BTTPS是一种化学物质,以下是对其的详细介绍:一、基本信息CAS号:1341215-19-7分子式:C20H34N10O4S分子量:510.62外观:淡灰白色固体溶解度:可溶于水、DMSO、DMF、甲醇等存储条件:避光,在-20摄氏度下保存保存时间:三年结构式:二、化学性质与用途性质:BTTPS是一种铜盐催化的“叠氮-炔基”......
  • 【题解】CF1944
    CF1944A简要题意给定完全图删k条边使得从一号点开始的可达点最少Solution注意到最多需要删n-1条边就可以使得任意一个其他点都到达不了又注意到只要删的边少于n-1就可以从一号点走出去,主要走出去就可以走到任何点所以这题答案只有两种如果k≤n-1答案为n否则答案为1......
  • NOIP2024集训Day71 贪心
    NOIP2024集训Day71贪心B.[CCO2015]饥饿的狐狸显然的,要求出最大美味值,应该先交错吃温度最大的和最小的饼干。所以我们给所有饼干按照温度排序,交替选择左右端点吃,如果喝水能够达到更大那就先喝水再吃,反正水管够。分两种情况,即左右端点谁先开始,再取个\(\operatorname{max}\)。......
  • 3193. 统计逆序对的数目
    3193.统计逆序对的数目题目链接:3193.统计逆序对的数目代码如下:classSolution{public: intnumberOfPermutations(intn,vector<vector<int>>&requirements) { vector<int>req(n,-1); req[0]=0; for(auto&p:requirements) { req[p[0]]=......
  • LOJ6119 「2017 山东二轮集训 Day7」国王
    题意给定一颗树,每个点有权值\(1\)和\(-1\),称一条路径是好的当且仅当路径上所有点的权值和为\(0\)。求连续编号区间\([l,r]\)使得两个点都在\([l,r]\)的好路径比两个点都不在\([l,r]\)的好路径数严格多的方案数。\(n\le10^5\)。Sol两个端点都在区间内不好做,......
  • 多校A层冲刺NOIP2024模拟赛18
    多校A层冲刺NOIP2024模拟赛18T1选彩笔(rgb)签到题,但是没签上。。。没想到三维前缀和,直接上了个bitset。就是直接二分答案,然后枚举这三维每维的区间的起点,前缀和查数量是否大于等于$K$即可,也可以把二分答案改为第一维的双指针,少一个$log$。T2兵蚁排序(sort)比T1还签......
  • CSP2024 前集训:NOIP2024加赛 2
    前言T2开太晚了,没打完,别的没怎么挂。哦对,T1以为埃筛复杂度是\(nlog^2\),实际上是\(n\ln(\ln(n))\),结果以为复杂度是错的,然后本地不开O2都飞快,我甚至还在惊叹本地竟然能跑\(5e9\)……还有我之前不知道树的直径的中点时唯一的……T1新的阶乘直接埃筛做完了。点击查......
  • NOIP2024 模拟赛 #15 总结
    Larunatrecy:信心赛。赛时T1求中位数,想起前两天做过的[ABC203D]Pond,考虑了二分答案。看出二分答案后不会做了,罚坐\(20\)min。然后发现我傻逼了,选出一个区间翻转,可以通过钦定右端点,找到最优的左端点得到,神仙Heldivis就出过一道这样的题。写完后调了下二分边界过了大样......