首页 > 其他分享 >2024.10.30 2022广西省赛

2024.10.30 2022广西省赛

时间：2024-10-30 19:00:04浏览次数：1  
标签：2024.10 mn totu int 30 long totq 2022 ans

Solved：11/12

Penalty：1059

Rank：1/146（N+2)

Dirt：48%

Problem A B C D E F G H I J K L 题数 罚时
Time 11 2 214 127 107 61 28 39 84 159 16 11 1059
dirt 3 1 1 3 2

A，B，G，H，L：签到

F

直接扔一个带修莫队板子上去就过了。虽然1000的值域应该有点说法。。。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

const int MN=2e5+5;
struct QUE{int l,r,t,id,typ,ans;}q[MN];
struct UPD{int fr,to,x;}u[MN];
int N,M,T,a[MN],pos[MN],totq,totu;
int ans;
inline bool cmp(const QUE&o,const QUE&oo)
{return (pos[o.l]^pos[oo.l])?(pos[o.l]<pos[oo.l]):((pos[o.r]^pos[oo.r])?(pos[o.r]<pos[oo.r]):(o.t<oo.t));}
int num[1000005];
inline bool cmp2(const QUE&o,const QUE&oo){return o.id<oo.id;}

int main()
{
    cin>>N>>M;
    T=1357;
    for(int i=1;i<=N;++i) cin>>a[i],pos[i]=(i-1)/T+1;
    for(int i=1;i<=M;++i)
    {
        int op;
        cin>>op;
        if(op==1||op==2)
        {
            ++totq;
            cin>>q[totq].l>>q[totq].r;
            q[totq].id=totq;
            q[totq].typ=op;
            q[totq].t=totu;
        }
        else
        {
            ++totu;
            cin>>u[totu].x;
            cin>>u[totu].to;
            u[totu].fr=a[u[totu].x];
            a[u[totu].x]=u[totu].to;
        }
    }
    for(int i=totu;i;--i) a[u[i].x]=u[i].fr;
    std::sort(q+1,q+totq+1,cmp);
    register int i=1,j=0,l=1,r=0,ans=0;
    for(i=1;i<=totq;++i)
    {
        for(;l>q[i].l;--l) ans+=((num[a[l-1]]^=1)?1:-1);
        for(;l<q[i].l;++l) ans+=((num[a[l]]^=1)?1:-1);
        for(;r<q[i].r;++r) ans+=((num[a[r+1]]^=1)?1:-1);
        for(;r>q[i].r;--r) ans+=((num[a[r]]^=1)?1:-1);
        for(;j<q[i].t;++j)
        {
            a[u[j+1].x]=u[j+1].to;
            if(u[j+1].x<=q[i].r&&u[j+1].x>=q[i].l)
                ans+=((num[u[j+1].fr]^=1)?1:-1),ans+=((num[u[j+1].to]^=1)?1:-1);
        }
        for(;j>q[i].t;--j)
        {
            a[u[j].x]=u[j].fr;
            if(u[j].x<=q[i].r&&u[j].x>=q[i].l)
                ans+=((num[u[j].fr]^=1)?1:-1),ans+=((num[u[j].to]^=1)?1:-1);
        }
        q[i].ans=q[i].typ==1?(ans==0||ans==1000):ans;
    }
    std::sort(q+1,q+totq+1,cmp2);
    for(i=1;i<=totq;++i) printf("%d\n",q[i].ans);
}

I

结论：当且仅当\(a\)是\(b\)的原根（特判\(b=2\)）。

证明：考虑模b剩余系下的操作，则加b操作相当于没有，因此想取到所有的数必须要a的幂次遍历1到b-1，必要性得证。充分性考虑通过一系列操作得到若干\(k_rb+r(r=1,2,\dots,b-1)\)，那只需要把这些数加充分多个b就能让它们变成连续段，后面的数就只要不断加b就可以了。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

const int N=1e6;
bool vis[N];
int main(){
    int a,b;
    cin>>a>>b;
    a%=b;
    if(a==1){
        if(b<=2)cout<<"YES\n";
        else cout<<"NO\n";
        return 0;
    }
    vis[0]=vis[1]=1;
    ll r=a;
    while(!vis[r]){
        vis[r]=1;
        r=r*a%b;
    }
    bool fl=1;
    for(int i=0;i<b;++i)
        if(!vis[i]){fl=0;break;}
    cout<<(fl?"YES":"NO")<<'\n';
}

E

模拟题，写得清楚点就行。

set会T（垃圾pta）

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

const int N=1e6+5;

int m,c[2],o;
int mx[2][2],mn[2][2];
ll w[2][2];

string op[4]={"EF","EFX","EF1","E"};

int check(int x,int y){
    if(w[x][x]>=w[x][y])return 0;
    if(w[x][x]>=w[x][y]-mn[x][y])return 1;
    if(w[x][x]>=w[x][y]-mx[x][y])return 2;
    return 3;
}

int main(){
    ios::sync_with_stdio(0);cin.tie(0);
    cin>>m;
    mn[0][0]=mn[0][1]=mn[1][0]=mn[1][1]=2e9;
    for(int i=1;i<=m;++i){
        cin>>c[0]>>c[1]>>o;
        mx[0][o]=max(mx[0][o],c[0]);
        mn[0][o]=min(mn[0][o],c[0]);
        mx[1][o]=max(mx[1][o],c[1]);
        mn[1][o]=min(mn[1][o],c[1]);
        w[0][o]+=c[0];
        w[1][o]+=c[1];
        cout<<op[max(check(0,1),check(1,0))]<<'\n';
    }
}

D

分层图最短路。建\(\log w\)层，第k层表示加速k次的图。加速的点连向下一层的同一个点，坏路直接连回第0层。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,int> pll;

const int N=2e4*21+5;
int id(int x,int i){return (x-1)*21+i;}
vector<pii> e[N];
void adde(int x,int y,int z){
    e[x].push_back(pii(y,z));
}
int n,m,S,T,x,y,z,p;
string ch;
ll dis[N];
bool vis[N];

int main(){
    ios::sync_with_stdio(0);cin.tie(0);
    cin>>n>>m>>S>>T;
    for(int i=1;i<=m;++i){
        string ch;
        cin>>x>>y>>z>>ch;
        if(ch=="G"){
            for(int j=0;j<=20;++j)adde(id(x,j),id(y,j),(z+(1<<j)-1)>>j);
        }
        else{
            for(int j=0;j<=20;++j)adde(id(x,j),id(y,0),(z+(1<<j)-1)>>j);
        }
    }
    cin>>p;
    for(int i=1;i<=p;++i){
        cin>>x>>z;
        for(int j=0;j<20;++j)adde(id(x,j),id(x,j+1),z);
    }
    priority_queue<pll,vector<pll>,greater<pll>> pq;
    memset(dis,63,sizeof(dis));
    dis[id(S,0)]=0;
    pq.push(pll(0,id(S,0)));
    while(!pq.empty()){
        int u=pq.top().second;
        pq.pop();
        if(vis[u])continue;
        vis[u]=1;
        for(auto [v,w]:e[u]){
            if(dis[v]>dis[u]+w){
                dis[v]=dis[u]+w;
                pq.push(pll(dis[v],v));
            }
        }
    }
    ll ans=1e18;
    for(int i=0;i<=20;++i)ans=min(ans,dis[id(T,i)]);
    if(ans>1e16)cout<<"-1\n";
    else cout<<ans<<'\n';
}

J

dp+容斥。暴力枚举约数更新即可。

\[f_i=\sum_{d\neq 1, d|a_i}-\mu(d)g_{d,i}, g_{d,i} = g_{d,i-1}+f_i[d|i] \]

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

const int N=1e5+5,mod=1e9+7;
bool np[N];
int pri[N],cnt,mu[N];
void sieve(int n){
    for(int i=2;i<=n;++i){
        if(!np[i])pri[++cnt]=i,mu[i]=-1;
        for(int j=1;j<=cnt&&i*pri[j]<=n;++j){
            np[i*pri[j]]=1;
            if(!(i%pri[j]))break;
            mu[i*pri[j]]=-mu[i];
        }
    }
}

int n,x;
ll f[N],g[N];

int main(){
    sieve(1e5);
    ios::sync_with_stdio(0);cin.tie(0);
    cin>>n;
    f[1]=1;
    for(int i=1;i<=n;++i){
        cin>>x;
        for(int j=1;j*j<=x;++j)if(!(x%j)){
            f[i]=(f[i]-mu[j]*g[j])%mod;
            if(j*j<x)f[i]=(f[i]-mu[x/j]*g[x/j])%mod;
        }
        for(int j=1;j*j<=x;++j)if(!(x%j)){
            g[j]=(g[j]+f[i])%mod;
            if(j*j<x)g[x/j]=(g[x/j]+f[i])%mod;
        }
    }
    cout<<(f[n]%mod+mod)%mod<<'\n';
}

C

你们出字符串都喜欢板子套板子吗.jpg

对所有串的正串和反串分别建一棵trie，把结束节点的二元组记下来。

对每个询问，相当于查询x[i]在a在T1中的节点子树、y[i]在b在T2中的节点子树的二元组数量。

DFS序转一下，就变成静态矩阵求和了。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

const int N=1e5+5,MN=1e6+5;
string rev(string s){
    int len=s.length();
    for(int i=0;i<len-i-1;++i)swap(s[i],s[len-i-1]);
    return s;
}
int n,m;
struct trie{
    int tot,c[MN][26],val[MN],dfn[MN],nfd[MN],id,sz[MN];
    trie(){tot=1,id=0;}
    int insert(string s){
        int u=1;
        for(char ch:s){
            int o=ch-'a';
            if(!c[u][o])c[u][o]=++tot;
            u=c[u][o];
        }
        return u;
    }
    void dfs(int u){
        dfn[u]=++id,nfd[id]=u,sz[u]=1;
        for(int i=0;i<26;++i)if(c[u][i])dfs(c[u][i]),sz[u]+=sz[c[u][i]];
    }
    int find(string s){
        int u=1;
        for(int ch:s){
            int o=ch-'a';
            if(!c[u][o])return 0;
            u=c[u][o];
        }
        return u;
    }
}T[2];

int pos[MN],tim[MN];

int cnt=0;
struct QUE{
    int id,x,y,typ;
    bool operator<(const QUE& q)const{
        return x<q.x;
    }
}q[N*2];
int ans[N];

int c[MN];
void upd(int x,int y){
    for(;x<=T[1].tot;x+=x&-x)c[x]+=y;
}
int qry(int x){
    int r=0;
    for(;x;x-=x&-x)r+=c[x];
    return r;
}

int main(){
    cin>>n>>m;
    for(int i=1;i<=n;++i){
        string s;
        cin>>s;
        int u=T[0].insert(s);
        int v=T[1].insert(rev(s));
        pos[u]=v,++tim[u];
    }
    T[0].dfs(1);
    T[1].dfs(1);
    for(int i=1;i<=m;++i){
        string s,t;
        cin>>s>>t;
        int u=T[0].find(s),v=T[1].find(rev(t));
        if(u&&v){
            q[++cnt]=(QUE){i,T[0].dfn[u]-1,v,-1};
            q[++cnt]=(QUE){i,T[0].dfn[u]+T[0].sz[u]-1,v,1};
        }
    }
    sort(q+1,q+cnt+1);
    for(int i=1,j=1;i<=T[0].tot;++i){
        if(pos[T[0].nfd[i]])upd(T[1].dfn[pos[T[0].nfd[i]]],tim[T[0].nfd[i]]);
        while(q[j].x==i){
            ans[q[j].id]+=q[j].typ*(qry(T[1].dfn[q[j].y]+T[1].sz[q[j].y]-1)-qry(T[1].dfn[q[j].y]-1));
            ++j;
        }
    }
    for(int i=1;i<=m;++i)cout<<ans[i]<<'\n';
}

标签：2024.10,mn,totu,int,30,long,totq,2022,ans
From： https://www.cnblogs.com/EssentialSingularity/p/18516393

相关文章

  • 20222412 2024-2025-1 《网络与系统攻防技术》实验三实验报告
    202224122024-2025-1《网络与系统攻防技术》实验三实验报告1.实验内容(1)正确使用msf编码器，veil-evasion，自己利用shellcode编程等免杀工具或技巧正确使用msf编码器，使用msfvenom生成如jar之类的其他文件veil，加壳工具使用C+shellcode编程(2)通过组合应用各种技术实现恶......
  • （30-6）基于NLP用户舆情的交易策略：使用增加嵌入维度的深度学习模型
    30.5.4 使用增加嵌入维度的深度学习模型还有继续提升模型性能的空间，特别是因为我们拥有一个相对较大的数据集，并且数据是由专家进行标注的。嵌入层似乎是构建优秀模型的关键，因此我们将尝试一种使用嵌入层的深度学习方法。我们的深度学习模型将使用20,000的词汇表，并将最大文......
  • 10月30日记录（《代码大全》（第二版）精读笔记）
    《代码大全》中对于“代码质量”和“设计原则”的探讨深刻而全面，给我留下了深刻的印象。在当今快速发展的软件开发环境中，理解和应用这些概念对于提升开发效率和软件质量至关重要。首先，关于代码质量，麦克康奈尔强调了代码不仅需要正确实现功能，还必须具备良好的可读性和可维护性。代......
  • 10.30
    actionlib_server_node.cppactionlib_client_node.cppActionlibExMsg.action#goaldefinitionint32whole_distance---#resultdefinitionboolis_finish---#feedbackint32moving_meter<build_depend>message_generation</build_depend><ex......
  • CF2030 题解
    因为cf炸了所以没办法提供代码，抱歉喵。A给定序列，定义$mn_i=\min_{j\lei}a_j,mx_i=\max_{j\lei}a_j$。重排该序列，最大化$\sum_{i=1}^nmx_i-mn_i$。$n\le10^5$正解手玩出一个构造，把最大和最小值放在前两个位置，这样的价值是\((n-1)\times(mx-mn)\)。由于\(m......
  • 闲话 10.30
    别样的丁真让我讲T2，所以提前写点东西出来。诗人小G首先根据题意，比较好写的是\(\mathcal{O(n^2)}\)的转移：\[f_i=\min_{j=0}^{i-1}\f_{j}+abs(sum_i-sum_j-L-1)^p\]其中\(sum\)为句子长度的前缀和。发现可优化的点是后面一坨柿子，我们把它记为\(G_{i,j}=abs(sum_i-sum_j-......
  • 【GiraKoo】常用编码的对比（ASCII，GB2312，GBK，GB18030，UCS，Unicode）
    甯哥敤缂栫爜鐨勫姣旓紙ASCII锛孏B2312锛孏BK锛孏B18030锛孶CS锛孶nicode锛�鍦ㄧ▼搴忓紑鍙戜腑锛屾枃瀛楃紪鐮佷竴鐩存壆婕旂潃浜虹暅鏃犲锛屽嵈鑳屽悗鎹呬竴鍒€鐨勮鑹层€�鍙兘鍦ㄦ簮浠ｇ爜鏂囦欢涓紝娉ㄩ噴鑾悕鍏跺鍦板彉鎴愪簡涔辩爜銆�鍙兘鏄彂閫佺粰鍒......
  • SS241030B. 世界(world)
    SS241030B.世界(world)题意在一个\(n\)列的竖着的二维世界里。每列有一个高度为\(a_i\)的石柱。你从\((1,a_1)\)的石头上面出发。每次可以往左或右边走一步（前提是左边或右边没有石头）、或者挖掉左边或者右边的石头、或者挖掉自己脚底下的石头。挖掉一个石头会使得它上面......
  • USB协议详解第30讲（USB枚举过程详解及抓包分析）
    当USB设备连接到或从USB中移除时，主机使用总线枚举过程来识别和管理接入的设备。当USB设备连接到一个已经被上电的端口，采取以下顺序行动：1.设备上电用户把USB设备插入USB端口（主机下的根hub或主机下行端口上的hub端口）或系统启动时设备上电。此时，USB设备处于加电状态，它所连接的端口......
  • 2024-10-30：或值至少 K 的最短子数组 I。用go语言，给定一个非负整数数组 nums 和一个整
    2024-10-30：或值至少K的最短子数组I。用go语言，给定一个非负整数数组nums和一个整数k，我们需要判断数组中是否存在一个最短的非空子数组，使得该子数组所有元素的按位或（OR）运算结果至少为k。如果找到了这样的子数组，返回其长度；如果不存在，则返回-1。输入：nums=[1,2,3],k=2。......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99