題目鏈接：https://codeforces.com/contest/1480
文章目錄
- A.Yet Another String Game
- B.The Great Hero
- C.Searching Local Minimum
- D1.Painting the Array I
- D2.Painting the Array II
- E.Continuous City
A.Yet Another String Game
貪心
題目大意為給定若干個字串，Alice和Bob輪流對字串每一位進行改變操作，每一位只能被改變一次，Alice先手，Alice要使字串字典序盡可能小，Bob要使字串字典序盡可能大，求最后結果，
貪心策略，一定是優先更改靠前的字符，Alice回合，若當前字符不為最小，則將其改為最小’a’，否則將其改為’b’，Bob同理，若當前字符不為最大，則將其改為最大’z’，否則將其改為’y’，
#include<bits/stdc++.h>
#define ll long long
#define next next_
#define y1 yy
using namespace std;
int _,len;
string s;
int main(){
scanf("%d",&_);
while(_--){
cin>>s;
len=s.size();
for(int i=0;i<len;i++){
if(i&1){
if(s[i]=='z') s[i]='y';
else s[i]='z';
}
else{
if(s[i]=='a') s[i]='b';
else s[i]='a';
}
}
cout<<s<<'\n';
}
return 0;
}
B.The Great Hero
排序，數學
題意要求判斷對于給定的所有怪物與英雄的攻擊力和血量，判斷英雄能否擊敗所有怪物（包括同歸于盡），
先對所有怪物按照攻擊力升序進行排序（攻擊力大的怪物放在最后，可以與其同歸于盡），再分別算出擊敗每個怪物所需的攻擊次數，并再整個程序中扣除英雄相應的血量，最后一只怪物特判能否與其同歸于盡，
#include<bits/stdc++.h>
#define ll long long
#define next next_
#define y1 yy
using namespace std;
ll _,A,B,n;
struct p{
ll a;
ll b;
}a[100010];
bool cmp(p x,p y){
if(x.a!=y.a) return x.a<y.a;
return x.b<y.b;
}
int main(){
scanf("%lld",&_);
while(_--){
bool ok=true;
scanf("%lld%lld%lld",&A,&B,&n);
for(ll i=1;i<=n;i++) scanf("%lld",&a[i].a);
for(ll i=1;i<=n;i++) scanf("%lld",&a[i].b);
sort(a+1,a+1+n,cmp);
for(ll i=1;i<=n;i++){
if(i==n){
ll num1=B/a[i].a+(B%a[i].a!=0),num2=a[i].b/A+(a[i].b%A!=0);
if(num1<num2) ok=false;
break;
}
ll num=a[i].b/A+(a[i].b%A!=0);
B-=num*a[i].a;
if(B<=0){
ok=false;
break;
}
}
if(ok) printf("YES\n");
else printf("NO\n");
}
return 0;
}
C.Searching Local Minimum
二分，互動
題意為給出一個排列的長度，每次你可以詢問得到一個下標元素的值，要求在100次詢問內找出滿足a[i]<min(a[i-1],a[i+1])的下標i，（a[0]=a[n+1]=∞）
二分查找即可，對于每次查找的mid，求出a[mid],a[mid-1],a[mid+1]并判斷a[mid],a[mid-1],a[mid+1]是否滿足條件，滿足則輸出，若不滿足，若a[mid]>a[mid-1]，則更新r=mid-1，反之則更新l=mid+1，
這里可以理解為二分查找一直往元素小的方向走，假設a[mid]>a[mid-1]，若[l,mid-2]區間內元素都比a[mid]大，則mid即為答案，若[l,mid-2]區間內元素都比a[mid]小，且為嚴格升序，則答案在邊界的位置，否則在區間中間一定存在a[i]<min(a[i-1],a[i+1])的結構，
#include<bits/stdc++.h>
#define ll long long
#define next next_
#define y1 yy
int n,a[100010];
int q(int t){
printf("? %d\n",t);
fflush(stdout);
int x;
scanf("%d",&x);
return x;
}
int main(){
scanf("%d",&n);
if(n==1) return printf("! 1"),0;
int l=1,r=n;
while(l<=r){
int mid=l+r>>1;
if(!a[mid]) a[mid]=q(mid);
if(mid-1>=1&&!a[mid-1]) a[mid-1]=q(mid-1);
if(mid+1<=n&&!a[mid+1]) a[mid+1]=q(mid+1);
if(mid==1){
if(a[mid]<a[mid+1]) return printf("! %d",mid),0;
else l=mid+1;
}
else if(mid==n){
if(a[mid]<a[mid-1]) return printf("! %d",mid),0;
else r=mid-1;
}
else{
if(a[mid]<a[mid-1]&&a[mid]<a[mid+1]) return printf("! %d",mid),0;
else{
if(a[mid]>a[mid-1]) r=mid-1;
else l=mid+1;
}
}
}
return 0;
}
D1.Painting the Array I
貪心
題意為給定一個數列，要求將其分為2個子序列，并將子序列中相鄰且相同的元素合并，求最后兩個子序列中的元素個數之和的最大值，
用a，b表示兩個子序列中的最后一個元素的位置下標，pos[i]表示下標為i的元素之后離它最近的與它相同的元素位置，
遍歷數列中的元素，若當前數與兩個序列中的最后一個數都相同，則只能將其合并，并將pos[c[i]]尾元素彈出，若兩個子序列末尾數有一與當前數相同，則將當前數壓入末尾數不同的序列中，并更新下標，若兩個子序列末尾數都與當前數不同，則比較與兩個序列末尾數相同的下一個數的距離，若a序列末尾數的下一個數的距離比b序列近，則對接下來結果影響較大的是a序列末尾數，則將當前數壓入序列a中，因為要使長度盡量長，要盡量避免相同的兩個數相鄰，反之，則將當前數壓入b序列中，最后將pos[c[i]]尾元素彈出，
最后統計數的個數，
#include<bits/stdc++.h>
#define ll long long
#define next next_
#define y1 yy
using namespace std;
vector<int> pos[100010];
int n,c[100010],next[100010],a,b,ans;
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++)
scanf("%d",&c[i]);
for(int i=n;i>=1;i--)
pos[c[i]].push_back(i);
for(int i=1;i<=n;i++){
if(c[a]==c[i]){
if(c[b]!=c[i]){
ans++;
b=i;
}
pos[c[i]].pop_back();
}
else if(c[b]==c[i]){
if(c[a]!=c[i]){
ans++;
a=i;
}
pos[c[i]].pop_back();
}
else{
if(!pos[c[a]].size()){
ans++;
b=i;
}
else if(!pos[c[b]].size()){
ans++;
a=i;
}
else if(pos[c[a]].back()<pos[c[b]].back()){
ans++;
a=i;
}
else{
ans++;
b=i;
}
pos[c[i]].pop_back();
}
}
cout<<ans;
return 0;
}
D2.Painting the Array II
貪心
題意與D1相同，只是改為求最小值，
遍歷一遍輸入數列，若當前兩個序列有一末尾數與當前數相同，則直接合并，若都不相同，則比較與兩個序列末尾數相同的下一個數的距離，若a序列末尾數的下一個數的距離比b序列近，則將當前數壓入b中，因為要使長度盡量短，要盡量使得相同的兩個數相鄰，反之，則將當前數壓入a序列中，最后將pos[c[i]]尾元素彈出，
最后統計數的個數，
#include<bits/stdc++.h>
#define ll long long
#define next next_
#define y1 yy
using namespace std;
vector<int> pos[100010];
int n,c[100010],next[100010],a,b,ans;
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++)
scanf("%d",&c[i]);
for(int i=n;i>=1;i--)
pos[c[i]].push_back(i);
for(int i=1;i<=n;i++){
if(c[a]==c[i]||c[b]==c[i]) pos[c[i]].pop_back();
else{
if(!pos[c[a]].size()){
ans++;
a=i;
}
else if(!pos[c[b]].size()){
ans++;
b=i;
}
else if(pos[c[a]].back()>pos[c[b]].back()){
ans++;
a=i;
}
else{
ans++;
b=i;
}
pos[c[i]].pop_back();
}
}
cout<<ans;
return 0;
}
E.Continuous City
二進制，圖論
題意為給你一個區間[l,r]，要求你構造一個有向圖，圖中的邊只能從序號小的點指向序號大的點，并且圖中從節點1到達節點n的所有路徑中，路徑的長度恰好分布在區間[l,r]中且每種長度出現且僅出現一次，
在解決多重背包問題時曾經運用到又給二進制優化的方法，即將相同的物品個數拆分成若干個二的整數次冪的和的形式，這里也自然會想到二進制拆分，但因為要求每種長度出現且僅出現一次，所以有一點變化，
首先特判l=r的情況，
考慮l=1的情況，若不考慮r，初始時放置2個點①，②，從①到②建立一條權值為1的邊，此時圖中覆寫了區間[1,1]內的所有值，
繼續加入點③，并建立一條從①到③的邊，權值為1，再建立一條從②到③的邊，權值為2，這時我們從1①出發，依照三條路徑經過②和③分別能得到1，2，3，此時圖中覆寫了區間[1,3]內的所有值，
如此往復加點，最終我們從①出發經過圖中的每個點時能分別得到區間[1,2n-1]中的所有值，
此時我們再從每個點上都引出一條指向終點的邊，便可得到區間[1,2n]中的所有值，
但這僅僅只是r為2的整數次冪的情況下，若r不為2的整數次冪，這種情況就行不通，而我們想到可以通過2的整數次冪來表示一個連續區間內的所有值，那么對這個區間邊界進行加減，就可以表示出其余的區間，于是自然想到將一個能夠表示區間[1,2i]的子圖末尾接上一條特定權值的邊再連向終點，但上圖的表示方式僅僅是在特定的點上能夠表示出特定的幾個值，我們需要構造一個圖，使其從①開始，經過中間的點最后到達終點時能夠表示出區間[1,2i]的所有值，如下圖，
只要從①出發，經過中間若干個點，最后到達⑤的所有路徑長度中完全覆寫了區間[1,23]內的所有數，此時再從⑤在引出一條邊，即可起到區間平移的作用，
那么最終的策略已經出來了，找出比r小且離r最近的2n，先仿照上圖構造出一個能夠表示區間[1,2n]內所有數的圖，再將r減去2n，多出來的一部磁區間利用從中間點引出新邊來產生，
以上圖為例若l=1，r=11，在點⑤的右側添加一條權值為1的邊，指向點⑥，同時從點①引出一條權值為1的邊，指向點⑥，此時圖中表示出了區間[1,23+1]內的所有數，此時r-9=2，2即為21，所以從點②引出一條權值為9的邊連接到點⑥上即可，
#include<bits/stdc++.h>
#define ll long long
#define next next_
#define y1 yy
using namespace std;
vector<tuple<ll,ll,ll> >app;
ll l,r,maxn,sum,wn,pos;
void work(ll l,ll r){
ll num=1;
maxn=1;
while(num*2<=r) num<<=1,maxn++;
maxn++;
for(ll i=1;i<=maxn;i++)
for(ll j=i+1;j<=maxn;j++) app.push_back({i,j,max(1ll,1ll<<(i-2))});
sum=num;
if(sum==r) return;
else{
maxn++;
app.push_back({1,maxn,1ll});
app.push_back({maxn-1,maxn,1ll});
sum++;
while(sum<r){
num=1;
pos=1;
while(num*2<=r-sum) num<<=1,pos++;
pos++;
app.push_back({pos,maxn,sum});
sum+=num;
}
}
}
int main(){
scanf("%lld%lld",&l,&r);
if(l==r) return printf("YES\n%lld %lld\n%lld %lld %lld",2ll,1ll,1ll,2ll,l),0;
wn=l-1;
l-=wn;
r-=wn;
work(l,r);
if(wn) app.push_back({maxn,maxn+1,wn}),maxn++;
printf("YES\n%lld %lld\n",maxn,(ll)app.size());
for(auto [x,y,z]:app) printf("%lld %lld %lld\n",x,y,z);
return 0;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/258525.html
標籤：其他
上一篇：利用C語言實作人機三子棋游戲