題目鏈接：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;
}
