Codeforces Round #535 (Div. 3)
题目总链接: https://codeforces.com/contest/1108
太懒了啊~ 好久之前的我现在才更新, 赶紧补上吧, 不能漏掉了.
A. Two distinct points
题意:
给出两个区间的左右边界, 输出两个数, 满足两个数分别在两个区间内且这两个数不相等.
题解:
直接输出左端点然后判断一下就行了.
代码如下:
- #include <bits/stdc++.h>
- using namespace std;
- typedef long long ll;
- int q;
- int l1,r1,l2,r2;
- int main(){
- cin>>q;
- for(int i=1;i<=q;i++){
- cin>>l1>>r1>>l2>>r2;
- if(l1==l2) l2++;
- cout<<l1<<" "<<l2<<endl;
- }
- return 0;
- }
- View Code
- B. Divisors of Two Integers
题意:
给出 n 个数, 这 n 个数都为两个数的因子, 最后要求你输出这两个数为什么.
题解:
既然是因子, 那么答案也肯定包含在这 n 个数中, 并且因子应该是较大的数.
那么我们排序后从后往前枚举, 遇到一个没有被删除的数我们就把它当作我们的答案, 并且在其它数中删掉它的因子.
代码如下:
- #include <bits/stdc++.h>
- using namespace std;
- typedef long long ll;
- const int N = 200;
- int n;
- int d[N],del[N];
- vector <int> vec[N];
- int main(){
- scanf("%d",&n);
- for(int i=1;i<=n;i++) scanf("%d",&d[i]);
- sort(d+1,d+n+1);
- for(int i=1;i<=n;i++){
- int x=d[i];
- for(int j=2;j*j<=x;j++){
- if(x%j==0){
- vec[i].push_back(j);
- if(j*j!=x) vec[i].push_back(x/j);
- }
- }
- }
- for(int i=n;i>=1;i--){
- if(del[i]) continue ;
- int cnt = 0;
- while(cnt<vec[i].size()){
- for(int j=2;j<=i;j++){
- if(del[j]) continue ;
- if(d[j]==vec[i][cnt]){
- cnt++;
- del[j]=1;
- break ;
- }
- }
- }
- }
- int tot=0;
- for(int i=3;i<=n;i++) if(!del[i]) tot++;
- int now = 0;
- int x=1,y=1;
- for(int i=3;i<=n;i++){
- if(now==tot-1){
- if(!del[i]) y*=d[i];
- }
- else if(!del[i]) x*=d[i],now++;
- }
- cout<<x<<" "<<y;
- return 0;
- }
- View Code
- C. Nice Garland
题意:
给出一个字符串, 这个字符串只由三个大写字母 "B","G","R" 构成, 然后问你最少需要修改多少个字符, 可以使得这个串成为一个 "好串".
好串的定义是, 对于每一个字符, 它和其它相同字符位置相差都为 3 的倍数.
题解:
因为相差都为 3 的倍数, 那么我们可以断定前三个字符是互不相同的, 并且之后每三个字符也是互不相同的.
另外也可以知道, 后面的位置与前三个的位置是一一对应的, 这样才满足相差为 3 的倍数这个条件.
那么我们就枚举前三个的所有可能情况, 然后根据这个去统计后面需要的修改次数, 最后取最小值就行了.
直接枚举太麻烦, 所以使用全排列函数 next_permutation.
代码如下:
- #include <bits/stdc++.h>
- using namespace std;
- typedef long long ll;
- const int N = 2e5+5;
- int n;
- char s[N],a[N];
- char p[10]={'R','B','G'};
- int main(){
- scanf("%d",&n);
- scanf("%s",s);
- int ans = 0;
- sort(p,p+3);
- ans=0x3f3f3f3f3f;
- int tot=0;
- do{
- tot++;
- int cnt = 0;
- for(int i=0;i<min(n,3);i++){
- if(p[i]!=s[i]) cnt++;
- }
- for(int i=3;i<n;i++){
- if(p[i%3]!=s[i]) cnt++;
- }
- if(ans>cnt){
- ans=cnt;
- for(int i=0;i<3;i++) a[i]=p[i];
- }
- }while(next_permutation(p,p+3));
- cout<<ans<<endl;
- for(int i=0;i<n;i++) cout<<a[i%3];
- return 0;
- }
- View Code
- D. Diverse Garland
题意:
还是给出一个只由 "R","G","B" 构成的字符串, 现在问最少的修改次数使得两两相邻的字符不想等为多少.
题解:
这题可以 dp 吧, 但是我是直接贪心来做的.
直接这样想, 对于一段连续且相等的串, 我们只需要改变其偶数位置就行了. 注意一下改变的时候不要和前面以及后面的相等了.
代码如下:
- #include <bits/stdc++.h>
- using namespace std;
- typedef long long ll;
- const int N = 2e5+5;
- int n;
- char s[N],p[N];
- char a[N]={'R','B','G'};
- void change(int x){
- for(int i=0;i<3;i++){
- p[x]=a[i];
- if(p[x]!=s[x-1] && p[x]!=s[x+1]) return ;
- }
- return ;
- }
- int main(){
- scanf("%d",&n);
- scanf("%s",s+1);
- int ans = 0;
- int tot=0;
- for(int i=1;i<=n;i++) p[i]=s[i];
- for(int i=1;i<=n;i++){
- if(s[i]!=s[i-1]) tot=1;
- else{
- tot++;
- if(tot%2==0){
- change(i);
- ans++;
- }
- }
- }
- cout<<ans<<endl;
- for(int i=1;i<=n;i++) cout<<p[i];
- return 0;
- }
- View Code
- E1. Array and Segments (Easy version)
题意:
给出 n 个数 ai 以及 m 个区间, 现在要求你选择一些区间, 然后每个区间里面的所有数减去 1, 最后问选择区间过后, n 个数中最大值减去最小值最大为多少.
题解:
简单版本的数据范围比较小, 直接暴力就行了.
暴力的话考虑枚举最后最小的位置是哪一个, 然后就选择所有覆盖这个点的区间, 暴力计算就 ok.
代码如下:
- #include <bits/stdc++.h>
- #define INF 0x3f3f3f3f
- using namespace std;
- typedef long long ll;
- const int N = 305,M = 305;
- int a[N],mx[N],mn[N],b[N];
- struct seg{
- int l,r,id;
- bool operator <(const seg &A)const{
- return r<A.r;
- }
- }p[M];
- int n,m;
- int main(){
- scanf("%d%d",&n,&m);
- for(int i=1;i<=n;i++) scanf("%d",&a[i]),b[i]=a[i];
- for(int i=1;i<=m;i++) scanf("%d%d",&p[i].l,&p[i].r),p[i].id=i;
- sort(p+1,p+m+1);
- memset(mn,INF,sizeof(mn));
- for(int i=1;i<=n+1;i++) mx[i]=-INF;
- for(int i=n;i>=1;i--)
- mx[i]=max(mx[i+1],a[i]);
- for(int i=n;i>=1;i--)
- mn[i]=min(mn[i+1],a[i]);
- int ans = mx[1]-mn[1];
- int num=0;
- for(int i=1;i<=n;i++){
- for(int j=1;j<=n;j++) a[j]=b[j];
- for(int j=1;j<=m;j++){
- if(p[j].l<=i && p[j].r>=i){
- for(int k=p[j].l;k<=p[j].r;k++) a[k]--;
- }
- }
- int minx = INF,maxx = -INF;
- for(int j=1;j<=n;j++) minx=min(minx,a[j]),maxx=max(maxx,a[j]);
- if(ans<maxx-minx){
- ans=maxx-minx;
- num=i;
- }
- }
- cout<<ans<<endl;
- int tot=0;
- vector <int> vec;
- for(int i=1;i<=m;i++){
- if(p[i].l<=num && p[i].r>=num) tot++,vec.push_back(p[i].id);
- }
- cout<<tot<<endl;
- for(auto v:vec) cout<<v<<" ";
- return 0;
- }
- View Code
- E2. Array and Segments (Hard version)
题意:
这题和 E1 的题目描述都是一样的, 不同的就是数据范围变大了, 现在是 n<=1e5,m<=300, 显然不能直接暴力枚举每个最小值了.
题解:
区间个数还是那么多, 注意到区间个数比 n 小很多, 那么我们可以考虑离散化, 这样数轴上最多只剩下 600 个点, 然后我们记录一下每一段的最大最小值.
这样段数也只有最多 600 个, 区间还是 300 个, 暴力枚举就不会超时了.
为啥可以把每一段看成点呢? 因为对于被区间 "分隔" 的每一段区间, 它们所拥有的区间覆盖都是相同的, 这个画下图就知道了.
给出代码:
- #include <bits/stdc++.h>
- #define INF 0x3f3f3f3f
- using namespace std;
- typedef long long ll;
- const int N = 1e5+5,M = 305;
- int a[N],l[N],r[N],b[N],c[N];
- int n,m,tot;
- int mx[N],mn[N];
- int main(){
- scanf("%d%d",&n,&m);
- for(int i=1;i<=n;i++) scanf("%d",&a[i]);
- for(int i=1;i<=m;i++){
- scanf("%d%d",&l[i],&r[i]);
- r[i]++;
- b[++tot]=l[i];
- b[++tot]=r[i];
- }
- b[++tot]=1;b[++tot]=n+1;
- sort(b+1,b+tot+1);
- tot = unique(b+1,b+tot+1)-(b+1);
- for(int i=1;i<=m;i++){
- l[i]=lower_bound(b+1,b+tot+1,l[i])-b;
- r[i]=lower_bound(b+1,b+tot+1,r[i])-b;
- }
- int t1=-INF,t2=INF;
- for(int i=1;i<tot;i++){
- mx[i]=mn[i]=a[b[i]];
- for(int j=b[i]+1;j<b[i+1];j++){
- mx[i]=max(mx[i],a[j]);
- mn[i]=min(mn[i],a[j]);
- }
- t1=max(t1,mx[i]);t2=min(t2,mn[i]);
- }
- vector <int> ans[N];
- int Ans=t1-t2,pos=0;
- for(int x=1;x<tot;x++){
- memset(c,0,sizeof(c));
- for(int j=1;j<=m;j++){
- if(l[j]<=x && r[j]>x)
- ans[x].push_back(j);
- }
- if(!ans[x].size()) continue ;
- for(auto v:ans[x]){
- c[l[v]]--;c[r[v]]++;
- }
- int s = 0,minx = INF,t=0,maxx=-INF;
- for(int i=1;i<tot;i++){
- s+=c[i];
- if(!t || mn[i]+s<minx) minx=mn[t=i]+s;
- }
- s = 0;
- for(int i=1;i<tot;i++){
- s+=c[i];
- if(mx[i]+s>maxx) maxx=mx[i]+s;
- }
- if(maxx-minx>Ans){
- Ans=maxx-minx;
- pos=x;
- }
- }
- cout<<Ans<<endl<<ans[pos].size()<<endl;
- for(auto v:ans[pos]) cout<<v<<" ";
- return 0;
- }
- View Code
还有一种更巧妙地解法, 用不上离散化, 直接搞就是了.
就是还是从 1~n 进行枚举, 只有当前点为某个区间的端点时进行更新, 然后再暴力求最大最小值来计算.
这个复杂度是 O(n*m) 的.
代码如下:
- #include <bits/stdc++.h>
- #define INF 0x3f3f3f3f
- using namespace std;
- typedef long long ll;
- const int N = 1e5+5,M = 305;
- int n,m;
- int a[N],b[N],l[N],r[N];
- vector <int> pl[N],pr[N];
- int main(){
- cin>>n>>m;
- int mx = -INF ,mn= INF;
- for(int i=1;i<=n;i++){
- scanf("%d",&a[i]);
- mx=max(mx,a[i]);
- mn=min(mn,a[i]);
- }
- for(int i=1;i<=m;i++){
- scanf("%d%d",&l[i],&r[i]);
- pl[l[i]].push_back(i);
- pr[r[i]+1].push_back(i);
- }
- int ans = mx-mn,pos=-1,tmp;
- for(int i=1;i<=n;i++){
- int len1=pl[i].size(),len2=pr[i].size();
- if(len1){
- for(auto v:pl[i]){
- for(int j=l[v];j<=r[v];j++) a[j]--;
- }
- }
- if(len2){
- for(auto v:pr[i]){
- for(int j=l[v];j<=r[v];j++) a[j]++;
- }
- }
- if(len1 || len2){
- mx = -INF,mn = INF;
- for(int i=1;i<=n;i++){
- mx=max(mx,a[i]);
- if(a[i]<mn){
- mn=a[i];
- tmp=i;
- }
- if(mx-mn>ans){
- ans=mx-mn;
- pos=tmp;
- }
- }
- }
- }
- cout<<ans<<endl;
- int cnt = 0;
- for(int i=1;i<=m;i++){
- if(l[i]<=pos && r[i]>=pos) cnt++;
- }
- cout<<cnt<<endl;
- for(int i=1;i<=m;i++){
- if(l[i]<=pos && r[i]>=pos) cout<<i<<" ";
- }
- return 0;
- }
- View Code
- F. MST Unification
题意:
给出一个无向图, 每条边有相应边权, 然后现在你可以对某些边的边权加上一个值.
现在问你最少需要多少次操作, 可以使得这个图的最小生成树唯一.
题解:
这个思路还是挺巧妙的, 也是求最小生成树. 我们假设目前边权为 x 的边有 c 条, 那么我们先剔除不用的边 a, 再尽可能地在途中加边 b, 最后的 c-a-b 条边就是我们需要对其进行操作的边.
然后稍微修改一下 Kruskal 就行了, 具体见代码吧:
- #include <bits/stdc++.h>
- using namespace std;
- typedef long long ll;
- const int N = 2e5+5;
- int n,m;
- int f[N];
- struct Edge{
- int u,v,w;
- bool operator <(const Edge &A)const{
- return w<A.w;
- }
- }e[N];
- int find(int x){
- return f[x]==x ? f[x] : f[x]=find(f[x]);
- }
- int main(){
- scanf("%d%d",&n,&m);
- for(int i=1;i<=m;i++){
- int u,v,w;
- scanf("%d%d%d",&u,&v,&w);
- e[i]={u,v,w};
- }
- sort(e+1,e+m+1);
- for(int i=1;i<=n+1;i++) f[i]=i;
- int ans = 0;
- for(int i=1,j=1;i<=m;i=j){
- while(e[i].w==e[j].w) j++;
- int cnt = j-i;
- for(int k=i;k<j;k++){
- int fx=find(e[k].u),fy=find(e[k].v);
- if(fx==fy) cnt--;
- }
- for(int k=i;k<j;k++){
- int fx=find(e[k].u),fy=find(e[k].v);
- if(fx==fy) continue ;
- cnt--;
- f[fx]=fy;
- }
- ans+=cnt;
- }
- cout<<ans;
- return 0;
- }
- View Code
这份题解总算写完了~ 还有几个找时间再补吧.
来源: http://www.bubuko.com/infodetail-2945224.html