Codeforces Round 486 (Div. 3)

2024-02-18 10:20
文章标签 codeforces round div 486

本文主要是介绍Codeforces Round 486 (Div. 3),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

目录

A. Diverse Team

B. Substrings Sort

C. Equal Sums

D. Points and Powers of Two

E. Divisibility by 25

F. Rain and Umbrellas


A. Diverse Team

 找出不重复的同时存下下标即可,依次遍历map判断重复最后判断数量即可

void solve(){cin>>n>>m;map<int,int> mp;vector<int> res;for(int i=1;i<=n;i++){int x; cin>>x;if(!mp.count(x))res.push_back(i);mp[x]++;}if(res.size()<m) cout<<"NO"<<endl;else{cout<<"YES"<<endl;for(int i=0;i<m;i++) cout<<res[i]<<' ';cout<<endl;}return ;
}

B. Substrings Sort

如果前一个是后一个的字串那么后一个的长度一定大于等于前一个,所以我没按照长度排序最后检查是不是满足都是字串即可

bool cmp(string a,string b){return a.size()<b.size();
}
void solve(){cin>>n;vector<string> s(n);for(auto&v:s) cin>>v;sort(s.begin(),s.end(),cmp);bool ok=true;for(int i=0;i<n;i++){for(int j=i+1;j<n;j++){if(s[j].find(s[i])==-1) ok=false;}}if(!ok) cout<<"NO"<<endl;else{cout<<"YES"<<endl;for(auto&v:s) cout<<v<<endl;}return ;
}

C. Equal Sums

我没对删除每一个位置的数的结果记录起来用map记录前面的方案即可,为了防止自己这一排我没使用先遍历自己的答案最后把自己的加入即可

void solve(){cin>>n;bool ok=false;map<LL,PII> mp;for(int i=1;i<=n;i++){cin>>m;vector<int> a(m);LL sum=0;for(int j=0;j<m;j++){cin>>a[j];sum+=a[j];}if(ok) continue;for(int j=0;j<m;j++){if(mp.count(sum-a[j])){ok=true;cout<<"YES"<<endl;auto [pos,id]=mp[sum-a[j]];cout<<pos<<' '<<id<<endl;cout<<i<<' '<<j+1<<endl;break;}}for(int j=0;j<m;j++){mp[sum-a[j]]={i,j+1};}}if(!ok) cout<<"NO"<<endl;return ;
}

D. Points and Powers of Two

我没研究性质可以发现其实最多只有三个不同的数出现因为如果还有更多的数的话一定不会是2的次方我们考虑三个数x-2^d,x,x+2^d,如果再加入一个数明显不成立所以最多三种我们不妨考虑枚举中间位置的数,然后枚举二进制即可

void solve(){cin>>n;map<int,int> mp;for(int i=0;i<n;i++){int x; cin>>x;mp[x]++;}int ans=0,id,pw;for(auto&[v,w]:mp){for(int j=1,cnt=1;cnt<=31;cnt++,j*=2){int now=w;if(mp.count(v-j)) now+=mp[v-j];if(mp.count(v+j)) now+=mp[v+j];if(now>ans){ans=now;id=v,pw=j;}}}cout<<ans<<endl;while(mp.count(id) && mp[id]--) cout<<id<<' ';while(mp.count(id+pw) && mp[id+pw]--) cout<<id+pw<<' ';while(mp.count(id-pw) && mp[id-pw]--) cout<<id-pw<<' ';return ;
}

E. Divisibility by 25

25的倍数一定是25,50,75,00作为结尾,我们考虑依次移动到后面即可,接着发现可能会出现00的情况我们假设最后是00375我们可以把3移动到最前面即可所以加入一个特判即可

int ans=1e9;
void check(char a,char b){string ss(s);reverse(ss.begin(),ss.end());int cnt=0;for(int i=0;i<ss.size();i++){if(ss[i]==b){cnt+=i;for(int j=i;j>0;j--){swap(ss[j],ss[j-1]);}break;}}for(int i=1;i<ss.size();i++){if(ss[i]==a){cnt+=i-1;for(int j=i;j>1;j--){swap(ss[j],ss[j-1]);}break;}}reverse(ss.begin(),ss.end());bool ok=false;for(int i=0;i<ss.size();i++){if(ss[i]!='0'){ok=true;cnt+=i;break;}}if(!ok) cnt=1e9;ans=min(ans,cnt);
}
void solve(){cin>>s;vector<int> cnt(10);for(auto&v:s) cnt[v-'0']++;if(cnt[2]>=1 && cnt[5]>=1) check('2','5');if(cnt[5]>=1 && cnt[0]>=1) check('5','0');if(cnt[7]>=1 && cnt[5]>=1) check('7','5');if(cnt[0]>=2) check('0','0');cout<<(ans==1e9 ? -1 : ans)<<endl;return ;        
}

F. Rain and Umbrellas

我们明显的可以考虑到dp,有些时候我们可以简单的思考问题我的上一个状态是前面的所有状态还是可以简化位就上一个位置的状态这里明显可以这样来思考这个问题,我们必须要从合法的状态转移过来,也就是我在第i个点手上拿着第几个伞,第0个表示没有伞,然后判断我上一个位置有没有伞我这个位置有没有雨来转移

int dp[M][M];// 表示到第i个点时用的是第j个位置的雨伞// 0 表示现在没有伞
int cho[M];
int w[M];
int rain[M];
int S;void solve()
{cin>>S>>n>>m;for(int i=1;i<=n;i++){int l,r; cin>>l>>r;for(int j=l+1;j<=r;j++)rain[j]=1;// 表示这个位置在下雨}	 w[0]=INF;for(int i=1;i<=m;i++){int v; cin>>v>>w[i];if(w[i]<=w[cho[v]]) cho[v]=i;}// 表示记录下来每一个位置的雨伞的权重,以及每一个雨伞在什么位置memset(dp,0x3f,sizeof dp);dp[0][0]=0;for(int i=1;i<=S;i++){for(int j=0;j<=m;j++){if(!rain[i]){// 如果我这个位置没有雨直接扔掉伞dp[i][0]=min(dp[i][0],dp[i-1][j]);}// 表示我接着用上一个位置的伞dp[i][j]=min(dp[i][j],dp[i-1][j]+w[j]);if (cho[i-1]){// 对于这个位置的上一个位置有伞换一手dp[i][cho[i-1]]=min(dp[i][cho[i-1]],dp[i-1][j]+w[cho[i-1]]);}}}int ans=INF;for(int i=0;i<=m;i++) ans=min(ans,dp[S][i]);cout<<(ans==INF ? -1 : ans)<<endl;return ;
}

这篇关于Codeforces Round 486 (Div. 3)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/720848

相关文章

Codeforces Round #240 (Div. 2) E分治算法探究1

Codeforces Round #240 (Div. 2) E  http://codeforces.com/contest/415/problem/E 2^n个数,每次操作将其分成2^q份,对于每一份内部的数进行翻转(逆序),每次操作完后输出操作后新序列的逆序对数。 图一:  划分子问题。 图二: 分而治之,=>  合并 。 图三: 回溯:

Codeforces Round #261 (Div. 2)小记

A  XX注意最后输出满足条件,我也不知道为什么写的这么长。 #define X first#define Y secondvector<pair<int , int> > a ;int can(pair<int , int> c){return -1000 <= c.X && c.X <= 1000&& -1000 <= c.Y && c.Y <= 1000 ;}int m

Codeforces Beta Round #47 C凸包 (最终写法)

题意慢慢看。 typedef long long LL ;int cmp(double x){if(fabs(x) < 1e-8) return 0 ;return x > 0 ? 1 : -1 ;}struct point{double x , y ;point(){}point(double _x , double _y):x(_x) , y(_y){}point op

Codeforces Round #113 (Div. 2) B 判断多边形是否在凸包内

题目点击打开链接 凸多边形A, 多边形B, 判断B是否严格在A内。  注意AB有重点 。  将A,B上的点合在一起求凸包,如果凸包上的点是B的某个点,则B肯定不在A内。 或者说B上的某点在凸包的边上则也说明B不严格在A里面。 这个处理有个巧妙的方法,只需在求凸包的时候, <=  改成< 也就是说凸包一条边上的所有点都重复点都记录在凸包里面了。 另外不能去重点。 int

Codeforces 482B 线段树

求是否存在这样的n个数; m次操作,每次操作就是三个数 l ,r,val          a[l] & a[l+1] &......&a[r] = val 就是区间l---r上的与的值为val 。 也就是意味着区间[L , R] 每个数要执行 | val 操作  最后判断  a[l] & a[l+1] &......&a[r] 是否= val import ja

CSS实现DIV三角形

本文内容收集来自网络 #triangle-up {width: 0;height: 0;border-left: 50px solid transparent;border-right: 50px solid transparent;border-bottom: 100px solid red;} #triangle-down {width: 0;height: 0;bor

创建一个大的DIV,里面的包含两个DIV是可以自由移动

创建一个大的DIV,里面的包含两个DIV是可以自由移动 <body>         <div style="position: relative; background:#DDF8CF;line-height: 50px"> <div style="text-align: center; width: 100%;padding-top: 0px;"><h3>定&nbsp;位&nbsp;

Codeforces Round 971 (Div. 4) (A~G1)

A、B题太简单,不做解释 C 对于 x y 两个方向,每一个方向至少需要 x / k 向上取整的步数,取最大值。 由于 x 方向先移动,假如 x 方向需要的步数多于 y 方向的步数,那么最后 y 方向的那一步就不需要了,答案减 1 代码 #include <iostream>#include <algorithm>#include <vector>#include <string>

CF#271 (Div. 2) D.(dp)

D. Flowers time limit per test 1.5 seconds memory limit per test 256 megabytes input standard input output standard output 题目链接: http://codeforces.com/contest/474/problem/D We s

CF #278 (Div. 2) B.(暴力枚举+推导公式+数学构造)

B. Candy Boxes time limit per test 1 second memory limit per test 256 megabytes input standard input output standard output 题目链接: http://codeforces.com/contest/488/problem/B There