Educational Codeforces Round 179 (Rated for Div. 2)(A-E)

题目链接：Dashboard - Educational Codeforces Round 179 (Rated for Div. 2) - Codeforces

A. Energy Crystals

思路

贪心地模拟一下过程很容易就看出来了，每次变成尽可能大的数

1 1 0 -> 1 1 3 -> 3 3 5 -> 5 5 11....我们只需要关注最大的数直到它大于等于x然后再进行两步操作将剩余的俩数变成x

代码

void solve(){int x;cin>>x;int ct=0;int now=1;while(now<x){ct++;now=now*2+1;}cout<<ct*2+3<<"\n";
}

B. Fibonacci Cubes

思路

因为是斐波那契数，我们能够发现只有两种摆放方式是合法的，

1.最大的放在底部，其余的放在最大的上面(可以证明这是能够放下的)此类方法要求l与w必须>=x，h要>=x+y,其中x为最大正方体的边长，y为次大的

2.最大的和次大的都放在底部，其余的都放在次大的上面，这样我们的h只需要>=x即可，l和h必须都>=x且至少有一个是>=x+y的

代码

#include<bits/stdc++.h>
using namespace std;#define vcoistnt ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); 
#define int long long
#define vi vector<int>
#define vb vector<bool>
typedef pair<int,int> pll;const int N=2e5+10;
const int inf=1e18;
const int mod=998244353;void solve(){int n,m;cin>>n>>m;vector<int> dp(n+10);dp[1]=1;dp[2]=2;for(int i=3;i<=n;i++){dp[i]=dp[i-1]+dp[i-2];}int x=dp[n];int y=dp[n-1];vector<int> ans(m+10,0);for(int i=1;i<=m;i++){int w,l,h;cin>>w>>l>>h;if(w>=x&&l>=x&&h>=(x+y)){ans[i]=1;}if(w>=x&&l>=x&&h>=x&&(w-x>=y||l-x>=y)){ans[i]=1;}}for(int i=1;i<=m;i++){cout<<ans[i];}cout<<"\n";
}
signed main() {vcoistntcout<<fixed<<setprecision(2);int _=1;cin>>_;while(_--) solve();return 0;
}

C. Equal Values

思路

直接带有贪心的思想暴力枚举一下就可以了，有一连串相同的数一定是选左端和右端

代码

void solve(){int n;cin>>n;vi a(n+10);for(int i=1;i<=n;i++){cin>>a[i];}int i=1;int ans=inf;while(i<=n){int ti=i;while((ti+1)<=n&&a[ti+1]==a[i]){ti++;}ans=min(ans,(i-1)*a[i]+(n-ti)*a[ti]);i=ti+1;}cout<<ans<<"\n";
}

D. Creating a Schedule

思路

贪心，首先两个教室可以供两个小组来进行，一个小组：x  y x y x y 另一个：y x y x y x

我们按照教室的层数排序，每两个小组选择剩余两端点的两个教室然后移除(可以用双指针实现)

注意奇数时最后一个小组要单独处理

代码

#include<bits/stdc++.h>
using namespace std;#define vcoistnt ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); 
#define int long long
#define vi vector<int>
#define vb vector<bool>
typedef pair<int,int> pll;const int N=2e5+10;
const int inf=1e18;
const int mod=998244353;bool cmp(int x,int y){return x/100>y/100;
}void solve(){int n,m;cin>>n>>m;vi a(m+10);for(int i=1;i<=m;i++){cin>>a[i];}sort(a.begin()+1,a.begin()+1+m,cmp);int l=1,r=m;for(int i=2;i<=n;i+=2){for(int j=1;j<=3;j++){cout<<a[l]<<" "<<a[r]<<" ";}cout<<"\n";for(int j=1;j<=3;j++){cout<<a[r]<<" "<<a[l]<<" ";}cout<<"\n";l++;r--;}if(n%2){for(int i=1;i<=3;i++){cout<<a[l]<<" "<<a[r]<<" ";}cout<<"\n";}
}
signed main() {vcoistntcout<<fixed<<setprecision(2);int _=1;cin>>_;while(_--) solve();return 0;
}

E. Changing the String

思路

贪心

因为在执行操作的时候我们可以选择什么也不做，所以可以先将所有操作给统计出来（注意是有顺序的），然后再遍历字符串看能否将其变小

1.当s[i]=='a'时，我们是不需要进行操作的因为a已经是最小了

2.当s[i]=='b'时，如果当前b->a的操作有剩余，将其变成a

否则，看是否能够完成操作b->c->a (注意此时要求b->c操作需要在c->a操作之前)

3.当s[i]=='c'时

首先我们需要看c->a操作是否有剩余，将其变成a。其次看c->b->a是否有，最后再看c->b

代码

#include<bits/stdc++.h>
using namespace std;#define vcoistnt ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); 
#define int long long
#define vi vector<int>
#define vb vector<bool>
typedef pair<int,int> pll;const int N=2e5+10;
const int inf=1e18;
const int mod=998244353;void solve(){int n,q;cin>>n>>q;string s;cin>>s;int ct1=0;  //b->aint ct2=0;  //b->cint ct3=0;  //c->aint ct4=0;  //c->bint ct5=0;  //在b->c前面有的基础上c->a  b->c->aint ct6=0;  //在c->b前面有的基础上b->a  c->b->afor(int i=1;i<=q;i++){char x,y;cin>>x>>y;if(x=='a') continue;if(x=='b'&&y=='a') ct1++;if(x=='b'&&y=='c') ct2++;if(x=='c'&&y=='a') ct3++;if(x=='c'&&y=='b') ct4++;if(x=='c'&&y=='a'){if(ct5<ct2) ct5++;}if(x=='b'&&y=='a'){if(ct6<ct4) ct6++;}}for(int i=0;i<n;i++){if(s[i]=='b'){if(ct1){ct1--;s[i]='a';}else{if(ct5&&ct2&&ct3){ct5--;ct2--;ct3--;s[i]='a';}}}else if(s[i]=='c'){if(ct3){ct3--;s[i]='a';}else{if(ct6&&ct4&&ct1){ct6--;ct4--;ct1--;s[i]='a';}else if(ct4){ct4--;s[i]='b';}}}}cout<<s<<"\n";
}
signed main() {vcoistntcout<<fixed<<setprecision(2);int _=1;cin>>_;while(_--) solve();return 0;
}