当前位置: 首页 > news >正文

Codeforces 874 div3 A-G

A. Musical Puzzle

分析

每两个相邻的字母都要录制一段,开个set记录一下,然后输出set的大小

C++代码:

#include<iostream>
#include<set>
using namespace std;
void solve(){int n;string s;cin>>n>>s;set<string> se;for(int i=0;i<s.size()-1;i++)se.insert(s.substr(i,2));cout<<(int)se.size()<<endl;
}
int main(){int t;cin>>t;while(t--){solve();}return 0;
}

B. Restore the Weather

分析

这题的k只是个幌子,根本没用

a从小到大对应b的从小到大

直接让b排序,然后根据a的大小按照对应位置放好就行

C++代码:

#include<iostream>
#include<algorithm>
using namespace std;
typedef pair<int,int> PII;
const int N=100010;
PII a[N];
int b[N],c[N],n,k;
void solve(){cin>>n>>k;for(int i=1;i<=n;i++){cin>>a[i].first;a[i].second=i;}sort(a+1,a+1+n);for(int i=1;i<=n;i++)cin>>b[i];sort(b+1,b+1+n);for(int i=1;i<=n;i++){c[a[i].second]=b[i];}for(int i=1;i<=n;i++)cout<<c[i]<<" ";cout<<endl;
}
int main(){int t;cin>>t;while(t--){solve();}return 0;
}

C. Vlad Building Beautiful Array

分析

如果全是奇数或者全是偶数,则输出Yes

如果存在奇数,则不可能将所有数都变成偶数,因为最小的那个奇数就不可能变成偶数

所以存在奇数就要把所有的偶数都变成奇数,则对于所有的偶数,都必须要有比当前数小的奇数,否则不可能全变成奇数

C++代码:

#include<iostream>
#include<algorithm>
using namespace std;
void solve(){int n,sum1=0,sum2=0;cin>>n;int a[n+5];for(int i=1;i<=n;i++){cin>>a[i];if(a[i]%2==0)sum1++;else sum2++;}if(sum1==n||sum2==n)puts("Yes");else{sort(a+1,a+n+1);//如果有奇数,则必须全变成奇数,那么对于每个偶数都必须要有比他小的奇数 int t=0,flag=0;for(int i=1;i<=n;i++)//a[i]为偶数且没有比a[i]小的奇数if(a[i]%2==0&&!t)flag=1;else if(a[i]%2)t=1;if(flag)puts("No");else puts("Yes");}
}
int main(){int t;cin>>t;while(t--){solve();}return 0;
}

D. Flipper

分析

要数组最大,则让n在第一个数最大

如果n本来就在第一个数,进行操作则n不可能还在第一个数,那么让n-1在第一个数

所以让要找的数的下标的前一个下标作为右端点 r ,如果要找的数的下标为n,则让n作为右端点r,然后暴力枚举左端点,找进行操作后最大的数组

C++代码:

#include<bits/stdc++.h>
using namespace std;
int n;
vector<int> get(int l,int r,vector<int> a){vector<int> res;for(int i=r+1;i<=n;i++)res.push_back(a[i]);//[r+1,n]变成前缀 for(int i=r;i>=l;i--)res.push_back(a[i]);//反转区间[l,r] for(int i=1;i<=l-1;i++)res.push_back(a[i]);//[1,l-1]变成后缀 return res;
}
void solve(){cin>>n;vector<int> a(n+1);for(int i=1;i<=n;i++)cin>>a[i];int t=find(a.begin(),a.end(),n)-a.begin();//找到n的位置if(t==1){//如果n是第一个数 t=find(a.begin(),a.end(),n-1)-a.begin();//找到n-1的位置 }int r=t==n?t:t-1;vector<int> ans(n,1);for(int l=1;l<=r;l++)ans=max(ans,get(l,r,a));//vector可以直接这样比大小for(int i=0;i<n;i++)cout<<ans[i]<<" \n"[i==n-1];
}
int main(){int t;cin>>t;while(t--){solve();}return 0;
}

E. Round Dance

分析

直接用并查集记录连通块的个数,然后看有几个连通块有环的存在

这题是n个点n条边,每个点最多只有两个邻点,且可能有重边,所以一个连通块最多一个环,在合并两个点的时候,记录是否有环,如果有,则sum3++,记录连通块的个数sum2

所以最多sum2个,最少sum3+(sum2-sum3>0)个,除了环剩下的都可以接在一起合并成一个

C++代码:

#include<iostream>
#include<map>
using namespace std;
typedef pair<int,int> PII;
const int N=200010;
int p[N];
map<PII,int> st;
int n;
int find(int x){if(p[x]!=x)p[x]=find(p[x]);return p[x];
}
int merge(int a,int b){int pa=find(a),pb=find(b);if(pa!=pb){p[pa]=pb;return true;}return false;//会形成环 
}
void solve(){cin>>n;st.clear();for(int i=1;i<=n;i++)p[i]=i;int sum1=0,sum2=0,sum3=0;for(int i=1;i<=n;i++){int x;cin>>x;if(!st[{i,x}]){if(!merge(i,x))sum3++;//如果有环}st[{i,x}]++,st[{x,i}]++;}for(int i=1;i<=n;i++)if(p[i]==i)sum2++;sum1=sum3+(sum2-sum3>=1);cout<<sum1<<" "<<sum2<<'\n';
}
int main(){int t;cin>>t;while(t--){solve();}return 0;
}

F. Ira and Flamenco

分析

区间内数的个数等于m且互不相同,且区间极值小于m,显然这m个数只能是连续的数

先记录数组a中每个数出现的次数,然后对a排序去重

对于第一个样例,m=4,n=7

8 10 10 9 6 11 7

排序去重后的结果为6,7,8,9,10,11,个数分别为1,1,1,1,2,1

合法区间:

6,7,8,9,该方案的个数为1*1*1*1=1

7,8,9,10,该方案的个数为1*1*1*2=2

8,9,10,11,该方案的个数为1*1*2*1=2

一共有1+2+2=5种方案

从前往后搜索每个数

假设搜到了一个合法的区间,假设当前区间每个数个数相乘之和为 t,然后到了下一个区间,就要将该区间的第一个数去掉,类似于滑动窗口,把数去掉的同时还要除以第一个数的个数,新加一个数就要乘以新加的数的个数

这题如果直接做会爆long long,但是看到有除法还有对质数取模,就可以考虑用逆元来做了,直接把除法变成乘法

C++代码:

#include<bits/stdc++.h>
using namespace std;
const int N=200010,mod=1e9+7;
typedef long long LL;
int n,m;
LL qmi(LL a,LL k,LL p){LL res = 1;while(k){if(k&1)res=res*a%p;a=a*a%p;k>>=1;}return res;
}
void solve()
{cin>>n>>m;vector<int> a(n);map<int,int> cnt;for(int i=0;i<n;i++)cin>>a[i],cnt[a[i]]++;sort(a.begin(),a.end());//排序 a.erase(unique(a.begin(),a.end()),a.end());//去重 if(m==1){int ans=0;for(auto t:cnt)ans=(ans+t.second)%mod;cout<<(ans+mod)%mod<<endl;return;}LL sum=1,ans=0,t=cnt[a[0]];for(int i=1;i<a.size();i++){if(a[i]==a[i-1]+1)sum++,t=(t*cnt[a[i]])%mod;else sum=1,t=cnt[a[i]];if(sum==m){ans=(ans+t)%mod;sum--;t=t*qmi(cnt[a[i-m+1]],mod-2,mod)%mod;}}cout<<(ans+mod)%mod<<endl;
}
int main(){int t;cin>>t;while(t--){solve();}return 0;
}

G. Ksyusha and Chinchilla

分析

连续的三个节点即可连成一条树枝

直接dfs搜索整棵树,然后记录以每个节点为根的子树的大小,如果当前子树大小刚好为3,则让该子树大小变成0(因为已经用过了,不能让别的节点再用该子树种的任何节点),然后把连接该子树的边的编号加入到答案种去,详见代码

C++代码:

//#include<bits/stdc++.h>
#include<iostream>
#include<vector>
#include<functional>
using namespace std;
const int N=200010,M=N*2;
typedef pair<int,int> PII;
void solve(){int n;cin>>n;vector<PII> e[n+1]; for(int i=1;i<n;i++){int a,b;cin>>a>>b;//加边,a-b这条边的编号为ie[a].push_back({b,i});e[b].push_back({a,i}); }vector<int> ans,sz(n+1);//ans记录答案,sz记录子树大小//第一次尝试这样写函数,不写在外面,边写边学hhfunction<void(int,int,int)> dfs=[&](int u,int fa,int from){//from表示从哪条边过来的sz[u]=1;//以u为根的子树大小for(auto [v,i]:e[u]){//u的所有邻点if(v==fa)continue;dfs(v,u,i);sz[u]+=sz[v];}if(sz[u]==3){//如果子树大小刚好为3,则让子树大小为0,防止u的父节点加上这三个点sz[u]=0;if(from)ans.push_back(from);//加上编号为from的边}};dfs(1,-1,0);//dfs遍历整棵树if(sz[1]!=0)cout<<-1<<'\n';else{cout<<ans.size()<<endl;for(auto x:ans)cout<<x<<" ";cout<<'\n';}
}
int main(){int t;cin>>t;while(t--){solve();}return 0;
} 

http://www.lryc.cn/news/420007.html

相关文章:

  • 暑期数据结构 空间复杂度
  • 【Android Studio】图标一键生成 Image Asset Studio(一键各机型适配图标生成工具-告别一个一个替换)
  • C++ | Leetcode C++题解之第332题重新安排行程
  • 使用Python实现简单的网页爬虫:抓取网站标题
  • 视觉SLAM ch3—三维空间的刚体运动
  • 计算机毕业设计选题推荐-二手图书交易系统-Java/Python项目实战
  • 4.MySQL数据类型
  • 快递查询新纪元:一键批量获取多家快递物流详情
  • docker部署redis和mongoDB
  • 了解LVS,配置LVS
  • 目标检测综述文章解读——Object Detection in 20 Years: A Survey
  • Android make_vbmeta_image的参数值定义
  • 代码规范 —— 并发编程规范
  • 仪器仪表控制:pymeasure常用模块以及API
  • 如何理解openfoam案例里面的blockMesh文件里面的simpleGrading
  • 算法竞赛的制胜法宝:被严重低估的位运算究竟有什么用?
  • Qt QTableWidget 去除序号列
  • 【C++】5.类和对象(3)
  • CTF-RCE
  • 谷歌账号登录时,多次验证后变成“您的计算机或网络可能在发送自动查询内容”,原因分析和解决建议
  • 【SpringMVC】详细介绍SpringMVC的执行流程
  • 工地云SaaS系统,通过物联网与可视化等先进技术的综合应用,搭建的智慧工地管理云平台源码
  • 使用自定义注解和AOP解决登录校验问题
  • 【数据结构初阶】队列
  • 《决胜B端 产品经理升级之路》 知识点总结
  • 2024年6月 青少年python一级等级考试真题试卷
  • TCFormer:通过标记聚类Transformer实现视觉识别
  • haproxy实现七层负载均衡详解(基本配置与算法)
  • 海量日志数据收集监控平台应该怎么设计和实现
  • Windows图形界面(GUI)-MFC-C/C++ - CSliderCtrl