首页 > 其他分享 >2024.11.2 2024ICPC成都站

2024.11.2 2024ICPC成都站

时间:2024-11-03 15:30:20浏览次数:1  
标签:pii typedef 2024.11 2024ICPC int cin 成都 && id

Solved:7/13

Penalty:793

Rank:40

Rank(ucup):152


L. Recover Statistics

输出 50 个 P50、45 个 P95,4 个 P99 和 1 个 P99+1 即可。

#include<bits/stdc++.h>
using namespace std;
int main(){
    ios::sync_with_stdio(0);cin.tie(0);
    int a,b,c;
    cin>>a>>b>>c;
    cout<<100<<'\n';
    for(int i=1;i<=50;++i)cout<<a<<' ';
    for(int i=1;i<=45;++i)cout<<b<<' ';
    for(int i=1;i<=4;++i)cout<<c<<' ';
    cout<<c+1<<'\n';
}

A. Arrow a Row

题意:用形如 >—>>> (中间可以有任意多个 -)来构造给定字符串,如果可以输出方案。\(n\leq 2\times 10^5\)。

简单构造,但是卡了很久。

结论是 a[1],a[n-2],a[n-1],a[n]必须是>,且至少要有一个-。

构造就是先把最后一段连续的>都造出来,再造前面的>。

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

void solve(){
    string a;
    cin>>a;
    int n=a.size();
    if(a[0]=='-'||a[n-1]=='-'||a[n-2]=='-'||a[n-3]=='-'){
        cout<<"No\n";
        return;
    }
    int pos=-1;
    for(int i=n-4;i>=0;--i)if(a[i]=='-'){pos=i;break;}
    if(!~pos){
        cout<<"No\n";
        return;
    }
    vector<pii> ans;
    for(int i=n-1;i>=pos+3;--i)ans.emplace_back(0,i);
    for(int i=1;i<pos;++i)if(a[i]=='>')ans.emplace_back(i,pos+3);
    cout<<"Yes "<<ans.size()<<'\n';
    for(int i=0;i<ans.size();++i)cout<<ans[i].first+1<<' '<<ans[i].second-ans[i].first+1<<'\n';
}

int main(){
    ios::sync_with_stdio(0);cin.tie(0);
    int T;
    cin>>T;
    while(T--)solve();
}

G.Expanding Array

题意:给一个序列,每次可以在两个数中间插入它们的按位与、按位或、按位异或。问最多能构造出多少个不同的数。\(n\leq 2\times 10^5\)。

能构造出的数只有 \(0,a_i,a_i\land a_{i+1},a_i\lor a_{i+1},a_i\oplus a_{i+1},a_i\backslash a_{i+1},a_{i+1}\backslash a_i\)。全都扔进 set 然后输出 size 即可。

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

int main(){
    ios::sync_with_stdio(0);cin.tie(0);
    int n;
    cin>>n;
    vector<int> a(n);
    for(int& x:a)cin>>x;
    set<int> s;
    s.insert(0);
    for(int i=0;i<a.size()-1;++i){
        s.insert(a[i]);
        s.insert(a[i+1]);
        s.insert(a[i]&a[i+1]);
        s.insert(a[i]|a[i+1]);
        s.insert(a[i]^a[i+1]);
        s.insert(a[i]&(a[i]^a[i+1]));
        s.insert(a[i+1]&(a[i]^a[i+1]));
    }
    cout<<s.size()<<'\n';
}

I.Good Partitions

题意:维护一个序列,支持单点修改,查询存在多少个 \(k\) 满足将序列分成每 \(k\) 个一段每段都是单调不减的。\(n\leq 2\times 10^5\)。

设所有满足 \(a_i>a_{i+1}\) 的 \(i\) 的集合为 \(S\),则答案就是 \(\gcd(S)\)。

因此只需支持插入、删除一个数,维护全体的 \(\gcd\)。

一开始写了个逆天的 vector 套 set,要枚举约数复杂度达到了 \(O((n+q)d(n)\log n)\),然后 TLE on 13。

然后改成了线段树维护 gcd,不存在的位置就填 0,复杂度 \(O(n\log^2 n)\)。

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

const int N=2e5+5;
int d[N];
void init(int n){
    for(int i=1;i<=n;++i)
        for(int j=i;j<=n;j+=i)++d[j];
}

#define lc (x<<1)
#define rc (x<<1|1)
#define mid ((l+r)>>1)
int n,q,x,y,a[N],s[N*4];
void bld(int x,int l,int r){
    if(l==r){s[x]=a[l]>a[l+1]?l:0;return;}
    bld(lc,l,mid),bld(rc,mid+1,r);
    s[x]=__gcd(s[lc],s[rc]);
}
void upd(int x,int l,int r,int p,int v){
    if(l==r){s[x]=v;return;}
    if(p<=mid)upd(lc,l,mid,p,v);
    else upd(rc,mid+1,r,p,v);
    s[x]=__gcd(s[lc],s[rc]);
}

void solve(){
    cin>>n>>q,d[0]=n;
    for(int i=1;i<=n;++i)cin>>a[i];
    if(n==1){
        cout<<1<<'\n';
        while(q--)cin>>x>>y,cout<<1<<'\n';
        return;
    }
    bld(1,1,n-1);
    cout<<d[s[1]]<<'\n';
    while(q--){
        cin>>x>>y;
        if(x>1&&a[x-1]>a[x]&&a[x-1]<=y)upd(1,1,n-1,x-1,0);
        if(x>1&&a[x-1]<=a[x]&&a[x-1]>y)upd(1,1,n-1,x-1,x-1);
        if(x<n&&a[x]>a[x+1]&&y<=a[x+1])upd(1,1,n-1,x,0);
        if(x<n&&a[x]<=a[x+1]&&y>a[x+1])upd(1,1,n-1,x,x);
        a[x]=y;
        cout<<d[s[1]]<<'\n';
    }
}

int main(){
    init(2e5);
    ios::sync_with_stdio(0);cin.tie(0);
    int T;
    cin>>T;
    while(T--)solve();
}

J. Grand Prix of Ballance

简单模拟,map 乱杀。

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

const int N=1e5+5;
int n,m,q,op,id,x;
pii a[N];
int r[N];
set<pii> e;

void solve(){
    cin>>n>>m>>q;
    for(int i=1;i<=m;++i)a[i]={0,i};
    memset(r,0,sizeof(int)*(n+1));
    e.clear();
    int cur=0;
    while(q--){
        cin>>op;
        if(op==1){
            cin>>x;
            cur=x;
        }
        else if(op==2){
            cin>>id>>x;
            if(x!=cur||e.find(pii(id,x))!=e.end())continue;
            a[id].first-=m-r[x];
            e.insert({id,x}),++r[x];
        }
        else{
            cin>>id>>x;
            if(x!=cur||e.find(pii(id,x))!=e.end())continue;
            e.insert({id,x});
        }
    }
    sort(a+1,a+m+1);
    for(int i=1;i<=m;++i)cout<<a[i].second<<' '<<-a[i].first<<'\n';
}

int main(){
    ios::sync_with_stdio(0);cin.tie(0);
    int T;
    cin>>T;
    while(T--)solve();
}

B. Athlete Welcome Ceremony

题意:一个全是abc的字符串,其中某些位置未定,要求相邻位置不同,多次询问,每次询问限制 a 的数量不超过 x,b 的数量不超过 y,c 的数量不超过 z,求方案数。 \(1\leq n\leq 300,1\leq q\leq 10^5\)。

先 dp 求出 恰好使用 i 个 a、j 个 b、k 个 c 的方案数,然后三维前缀和。

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

const int N=305,mod=1e9+7;
int n,q,c[3];
string a;
ll f[N][N][N][3],s[N][N][N];

int main(){
    ios::sync_with_stdio(0);cin.tie(0);
    cin>>n>>q>>a,a=" "+a;
    for(int i=1;i<=n;++i)if(a[i]!='?')++c[a[i]-'a'];
    f[1][0][0][0]=f[0][1][0][1]=f[0][0][1][2]=1;
    for(int i=0;i<=n;++i)
        for(int j=0;i+j<=n;++j)
            for(int k=0;i+j+k<=n;++k)if(i+j+k>0){
                if(a[i+j+k]=='a')f[i][j][k][1]=f[i][j][k][2]=0;
                if(a[i+j+k]=='b')f[i][j][k][0]=f[i][j][k][2]=0;
                if(a[i+j+k]=='c')f[i][j][k][0]=f[i][j][k][1]=0;
                if(i+j+k<n){
                    (f[i+1][j][k][0]+=f[i][j][k][1]+f[i][j][k][2])%=mod;
                    (f[i][j+1][k][1]+=f[i][j][k][0]+f[i][j][k][2])%=mod;
                    (f[i][j][k+1][2]+=f[i][j][k][0]+f[i][j][k][1])%=mod;
                }
            }
    for(int i=0;i<=n;++i)
        for(int j=0;j<=n;++j)
            for(int k=0;k<=n;++k){
                if(i+j+k==n)s[i][j][k]=f[i][j][k][0]+f[i][j][k][1]+f[i][j][k][2];
                if(i>0)s[i][j][k]+=s[i-1][j][k];
                if(j>0)s[i][j][k]+=s[i][j-1][k];
                if(k>0)s[i][j][k]+=s[i][j][k-1];
                if(i>0&&j>0)s[i][j][k]-=s[i-1][j-1][k];
                if(i>0&&k>0)s[i][j][k]-=s[i-1][j][k-1];
                if(j>0&&k>0)s[i][j][k]-=s[i][j-1][k-1];
                if(i>0&&j>0&&k>0)s[i][j][k]+=s[i-1][j-1][k-1];
                s[i][j][k]=(s[i][j][k]%mod+mod)%mod;
            }
    while(q--){
        int x,y,z;
        cin>>x>>y>>z;
        x=min(x+c[0],n),y=min(y+c[1],n),z=min(z+c[2],n);
        cout<<s[x][y][z]<<'\n';
    }
}

K. Magical Set

题意:给一个集合,每次可选一个数除掉它的一个非 1 约数,且需保证集合中任何时刻没有相同的数。求最多能操作的次数。

最优方案下每次一定除的一定是质数。因此求出每个数及其所有约数的质因子数量 \(p_i\),然后对每个数向它的约数连一条 \(p_i-p_j\) 的边,二分图最大权匹配即可。

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

const int V=6e5+5,E=3e7+5,inf=0x3f3f3f3f;
int s,t,v=0,e=1,fir[V],to[E],nxt[E],w[E],c[E];
inline void adde(int x,int y,int z,int t){
	to[++e]=y,nxt[e]=fir[x],fir[x]=e,w[e]=z,c[e]=t;
	to[++e]=x,nxt[e]=fir[y],fir[y]=e,w[e]=0,c[e]=-t;
}
int dis[V],q[E];
bool vis[V];
bool spfa(){
	memset(dis,63,sizeof(dis));
	memset(vis,0,sizeof(vis));
	int l=1,r=0;
	q[++r]=t,dis[t]=0;
	while(l<=r){
		int u=q[l++];vis[u]=0;
		for(int i=fir[u],v=to[i];i;v=to[i=nxt[i]]){
			if(!w[i^1]||dis[v]<=dis[u]+c[i^1])continue;
			dis[v]=dis[u]+c[i^1];
			if(!vis[v])vis[v]=1,q[++r]=v;
		}
	}
	return dis[s]<inf;
}
int cur[V];
int dfs(int u,int flow){
	if(u==t||!flow)return flow;
	vis[u]=1;
	int nowf=flow;
	for(int& i=cur[u];i;i=nxt[i]){
		int v=to[i];
		if(dis[v]+c[i]!=dis[u]||vis[v])continue;
		int f=dfs(v,min(w[i],nowf));
		w[i]-=f,w[i^1]+=f;
		if(!(nowf-=f))return flow;
	}
	return flow-nowf;
}
int MCMF(){
	int flow=0,res=0;
	while(spfa()){
		memcpy(cur,fir,sizeof(cur));
		memset(vis,0,sizeof(vis));
		int f=dfs(s,inf);
		flow+=f,res+=dis[s]*f;
	}return res;
}

const int N=305;
map<int,int> id;
int n,a[N],p[V];
int main(){
    ios::sync_with_stdio(0);cin.tie(0);
    cin>>n;
    s=++v,t=++v;
    for(int i=1;i<=n;++i){
        cin>>a[i];
        if(!id.count(a[i]))id[a[i]]=++v;
        adde(s,id[a[i]],1,0);
        for(int j=1;j*j<=a[i];++j)if(!(a[i]%j)){
            if(!id.count(j))id[j]=++v;
            if(!id.count(a[i]/j))id[a[i]/j]=++v;
        }
    }
    for(auto &[x,u]:id){
        int tt=x;
        for(int i=2;i*i<=tt;++i)if(!(tt%i)){
            while(!(tt%i))tt/=i,++p[u];
        }
        if(tt>1)++p[u];
        adde(u,t,1,0);
    }
    for(int i=1;i<=n;++i)
        for(auto &[x,u]:id)
            if(!(a[i]%x))adde(id[a[i]],u,1,-(p[id[a[i]]]-p[u]));
    cout<<-MCMF()<<'\n';
}

标签:pii,typedef,2024.11,2024ICPC,int,cin,成都,&&,id
From: https://www.cnblogs.com/EssentialSingularity/p/18523504

相关文章

  • 2024.11.2 模拟赛
    2024.11.2模拟赛T1P11242碧树把\(n\)个点往外连即可。最终答案为\(n-\max_{i=1}^na_i+1\)T2P11243繁花感觉我的做法麻烦了,而且随机复杂度()显然的,从左往右看可以分层,遇到一次大于号分一次。对于每段,遍历一遍,每遇到一次小于号计算一次答案。如果不考虑等于号,这段的......
  • ICPC 成都游记
    提前声明:本文可能包含剧透。Day-1一天赶完三个ddl,终于空出一个周末了!Day0六点半就起床打车去机场,结果发现某队长把起飞时间记早了1h,于是整队在赛百味悠闲地吃了个早餐休息了一下。飞机上重刷了缓存的巴别塔之茧(的前1/3),然后一路打瞌睡地到了比赛场地。进来的时候发现热身......
  • 2024.11.02模拟赛
    挂了至少30分!!不——开——心——钢哥说,大家要休息好,于是模拟赛晚点,变成了3小时3道题。T1打的正解(但没调出来版),T2T3打的暴力(但全挂了版),预计总分120+,但实际总分80。小小总结一下:昨晚多睡了一小时,今天思路确实感觉更清晰了(但也有可能是因为题目不难……)。但今天时间没分配......
  • 日记 2024.11.1:2024 syzx 秋季训练 4
    E令\(m=s/2\)。将\(r<m\)的区间称作A类,\(m<l\)的B类,\(l\leqm\leqr\)的C类。A、B类可以互相匹配,过程如下:将B翻转,假如A类都叫\([l_i,r_i]\),B类对称翻转后叫作\([l_j,r_j]\),将\(l_i,r_j\)混合从小到大排序,维护一个升序的set,遇到\(l_i\)时将\(r_i\)插......
  • 2024.11.01模拟赛
    唉不——开——心——有些话就不说了。T1打假了,打了T3、T4的特殊样例(共10分),原本是抱着爆0的心态的,结果没想到T1数据水到直接给了我70分——但T3T4爆掉了,总分70分。差点爆0,不——开————心——————题目小链接T1【二分图匹配】题目大意:给出两个长度分别为n,m(1......
  • 2024.11.1 test
    B维护长度为二的次幂的数组,支持单点修改,区间和,全局执行以下三种操作之一:for(inti=0;i<n;i++)b[i]=0;for(inti=0;i<n;i++)b[i()x]+=a[i];for(inti=0;i<n;i++)a[i]=b[i];()里为或,且,异或中的一种。\(n\le2^{19}\)。考虑线段树维护。注意到如果为或/且,那么相当于对......
  • 2024.11.1总结
    本文于github博客同步更新。OI相关:A:分为两种情况处理:\(u\)到\(lca\)和\(lca\)到\(v\)。我的做法是先树剖,将每条链单独拿出来拉出来,根据\(a_i\)和\(b_i\)连边,正反各建一棵树,维护一下\(k\)级祖先。然后从\(u\)到\(v\)的时候每次根据从dfs序由小到大还是由......
  • MindSponge分子动力学模拟——增强采样(2024.11)
    技术背景关于增强采样(EnhancedSampling)算法的具体原理,这里暂不做具体介绍,感兴趣的童鞋可以直接参考下这篇综述文章:Enhancedsamplinginmoleculardynamics。大致的作用就是,通过统计力学的方法,使得目标分子的CV(CollectiveVariables)具有一个尽可能大的采样子空间,并且可以将其还......
  • 蓝桥杯备赛&学习计划 2024.11—2025.4
    学习计划概览2024年11月到12月-巩固基础,学习基本算法。2025年1月到2月-学习中级算法和数据结构。2025年3月-进阶算法学习和刷题练习。2025年4月-复习重点知识,专注于比赛准备。详细周计划2024年11月:基础知识&基础算法第1-2周:复习基本控制结构(循环、条件语......
  • java计算机毕业设计成都医学院考研信息交流平台(开题+程序+论文)
    本系统(程序+源码)带文档lw万字以上 文末可获取一份本项目的java源码和数据库参考。系统程序文件列表开题报告内容研究背景随着高等教育的普及和就业压力的增加,越来越多的本科毕业生选择继续深造,攻读硕士学位。成都医学院作为四川省的一所重要医学院校,吸引了大量学生报考其......