A. Yet Another String Game
題目傳送門：
A. Yet Another String Game
水題
#include<bits/stdc++.h>
using namespace std;
int main()
{
int t;
scanf("%d",&t);
while(t--)
{
string str;
cin>>str;
for(int i=0;i<str.length();i++)
{
if(i%2==0)
{
if(str[i]!='a') printf("a");
else printf("b");
}
else
{
if(str[i]!='z') printf("z");
else printf("y");
}
}
printf("\n");
}
//system("pause");
return 0;
}
B. The Great Hero
題目傳送門：
B. The Great Hero
題目大意：
hero有A點攻擊力和B點血量，有n只怪獸，每只怪獸有ai點攻擊力和bi點血量，問hero能不能殺死所有怪獸，即使在殺完最后一只怪獸時死完，
思路：
其實這題可以寫的非常的簡單，
我們可以想到當能殺死怪獸時而又最慘烈的情況那就是hero用最后一滴血，殺死了攻擊力最高的怪獸，也就是B - 1 + maxn >= sum (maxn為怪獸的最高攻擊力，sum為殺死所有怪獸需要承受的攻擊)
AC Code
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N=1e5+10;
LL a[N],b[N];
int main()
{
int t;
scanf("%d",&t);
while(t--)
{
LL p,q;
int n;
LL maxn=0;
scanf("%lld%lld%d",&p,&q,&n);
for(int i=1;i<=n;i++)
{
scanf("%lld",&a[i]);
maxn=max(maxn,a[i]);
}
for(int i=1;i<=n;i++)
scanf("%lld",&b[i]);
q=maxn-1+q;
LL sum=0;
int flag=0;
for(int i=1;i<=n;i++)
{
int k=b[i]/p;
if(b[i]%p) k++;
q=q-k*a[i];
if(q<0) flag=1;
}
if(flag==1) printf("NO\n");
else printf("YES\n");
}
//system("pause");
return 0;
}
C. Searching Local Minimum（新穎的二分查找）
題目傳送門：
C. Searching Local Minimum
題目大意：
這是一個互動題，你可以查詢最多100個位置的數，經過查詢之后輸出任意一個數 ai < min{ ai?1,ai+1} 的位置，
思路：
我們可以想到當區間中的任意位置有mid，如果a[mid] > a[mid+1]，那么區間 [ mid+1 , n ]中一定存在答案，因為a[n+1]為無窮大，那么反之如果a[mid]<a[mid+1] , 那么區間[ 1 , mid ]中一定存在答案，想到這里，再結合資料范圍，就很容易想到二分查找，
AC Code
#include<bits/stdc++.h>
using namespace std;
int main()
{
int n;
scanf("%d",&n);
int l=1,r=n;
int x,y;
while(l<r)
{
int mid=(l+r)/2;
printf("? %d\n",mid);
fflush(stdout);
scanf("%d",&x);
printf("? %d\n",mid+1);
fflush(stdout);
scanf("%d",&y);
if(x>y) l=mid+1;
else r=mid;
}
printf("! %d",l);
fflush(stdout);
//system("pause");
return 0;
}
D1. Painting the Array I（貪心好題）
參考了大佬的題解
題目傳送門：
D1. Painting the Array I
思路：
考慮貪心
我們記當前a0陣列最前面的元素為p，a1最前面的元素為q，那么a中的每一個元素，我們依次考慮分配給a0更優還是分配給a1更優，
當p==q時
顯然這時候a[i]給到哪個子陣列都無所謂，
當p!=a[i]&&q==a[i]
顯然把a[i]丟在a0后更優
當q!=a[i]&&p==a[i]
顯然把a[i]丟在a1后更優
當one!=two&&one!=a[i]&&two!=a[i]
此時放哪個位置都會讓答案加一，那么怎么選擇呢？？
定義nxt[i]為數字i出現最近的位置
如果 nxt[p] < nxt[q] ,放在p后面更優
如果nxt[p]>nxt[q]，放在q后面更優
（這里我的理解是：nxt 即為下一個相同數字的位置，那么 nxt 位置更遠的中間就會存在有更多的數可以阻止兩者合并，于是我們就先把當前這個數放在 nxt 更近的數后面）
AC Code
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+10;
vector<int>vec[maxn];
int id[maxn],a[maxn],n;
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
vec[a[i]].push_back(i);
}
int p=-1,q=-1;
int num=0;
for(int i=1;i<=n;i++)
{
id[a[i]]++;
if(p==q) //如果相等，就隨便仍一個，
{
if(p!=a[i])
num++;
p=a[i];
}
else if(p!=a[i]&&q==a[i])
{
p=a[i];
num++;
}
else if(p==a[i]&&q!=a[i])
{
q=a[i];
num++;
}
else
{
if(p==-1)
{
q=a[i];
num++;
}
else if(q==-1)
{
p=a[i];
num++;
}
else
{
int x=n+1,y=n+1;
if(id[p]<vec[p].size()) x=vec[p][id[p]];
if(id[q]<vec[q].size()) y=vec[q][id[q]];
if(x>y) q=a[i];
else p=a[i];
num++;
}
}
}
printf("%d\n",num);
//system("pause");
return 0;
}
D2. Painting the Array II
題目傳送門：
D2. Painting the Array II
方法和上面是一樣的，只是各種條件反一下即可
AC Code
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+10;
vector<int>vec[maxn];
int a[maxn],idx[maxn];
int main()
{
int n;
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
vec[a[i]].push_back(i);
}
int num=0;
int p=-1,q=-1;
for(int i=1;i<=n;i++)
{
idx[a[i]]++;
if(p==q)
{
if(p!=a[i])
num++;
p=a[i];
}
else if(p==a[i]||q==a[i])
continue;
else
{
if(p==-1) p=a[i];
else if(q==-1) q=a[i];
else
{
int x=n+1,y=n+1;
if(idx[p]<vec[p].size()) x=vec[p][idx[p]];
if(idx[q]<vec[q].size()) y=vec[q][idx[q]];
if(x<y) q=a[i];
else p=a[i];
}
num++;
}
}
printf("%d\n",num);
//system("pause");
return 0;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/ruanti/258065.html
標籤：其他