問題 A: 阿Q的記憶
時間限制: 1 Sec 記憶體限制: 128 MB
題目描述
阿Q登山回來，覺得山都長得一個樣子，她記得某一段：她往下走了1米，再往下走了1米，然后往上走了1米，然后balabalabala……用一個包含U和D的字串表示，U表示向上1米，D表示向下1米，她還記得全程起點的高度，終點的高度，以及她一共走了多少時間（一個單位時間內，她會使自己海拔升高或降低1米），她知道山的任意位置的海拔都是非負的，她想知道，自己的記憶有沒有自相矛盾，
輸入
多組測驗資料，對于每組測驗資料：第一行，三個整數n,S,T，表示走的次數，起點、終點海拔；第二行，由U和D構成字串，表示中間某一段的情況；
輸出
對于每組測驗資料，如果自相矛盾，輸出NO，否則輸出YES，
樣例輸入 Copy
4 0 4
UU
4 0 4
D
樣例輸出 Copy
YES
NO
提示
對于100%的資料n,S,T<=100000 字串長度<=50
題意： 可以走
n
n
n步，起點是
s
s
s ，終點
t
t
t，給出你走的中間一段走的方式位置大于等于零 問你是否能滿足條件
思路： 你先按這他給的走，如果位置小于零時，你走多走一步讓你先上來，之后再走，判斷步數與總步數大小，
- 不夠肯定就不能滿足條件
- 正好夠用，就判斷當前能到的位置是不是終點位置，能到可以，不能到則不滿足條件
- 步數小于總步數，算出你走完這些步數還剩多少步可以走（還可以走的），再算出從你最后到的與終點的距離（應該走的），然后還可以走的如果小于應該走的肯定就不行，大于則需要多出的是否是偶數，就是消耗這些多的步數，
#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4.1,sse4.2,avx,avx2,popcnt,tune=native")
#include <immintrin.h>
#pragma GCC optimize(2)
#include <map>
#include <queue>
#include <string>
#include<iostream>
#include<stdio.h>
#include<string.h>
#include <algorithm>
#include <math.h>
typedef long long ll;
typedef unsigned long long ull;
using namespace std;
typedef pair<ll,ll> pii;
#define mem(a,x) memset(a,x,sizeof(a))
#define debug(x) cout << #x << ": " << x << endl;
#define rep(i,n) for(int i=0;i<(n);++i)
#define repi(i,a,b) for(int i=int(a);i<=(b);++i)
#define repr(i,b,a) for(int i=int(b);i>=(a);--i)
const int maxn=1e5+1010;
#define inf 0x3f3f3f3f
#define sf scanf
#define pf printf
const int mod=1e9+7;
const int MOD=10007;
inline int read() {
int x=0;
bool t=false;
char ch=getchar();
while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();
if(ch=='-')t=true,ch=getchar();
while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();
return t?-x:x;
}
ll n,m,p;
string str;
int main() {
while(~scanf("%lld%lld%lld",&n,&m,&p)) {
cin>>str;
ll len=str.size();
ll sum=len;
for(int i=0;i<len;i++){
if(str[i]=='U') m++;
else m--;
if(m<0) m++,sum++;///多用一次
}
if(sum>n){
cout<<"NO"<<endl;
}else if(sum==n){
if(m==p) cout<<"YES"<<endl;
else cout<<"NO"<<endl;
}else {
ll ans1=n-sum;///還有
ll ans2=abs(p-m);///需要
ll ans=ans1-ans2;
if(ans<0) cout<<"NO"<<endl;
else {
if(ans%2) cout<<"NO"<<endl;
else cout<<"YES"<<endl;
}
}
}
return 0;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/226955.html
標籤：其他