1. 拨动数字
已知小红每次可以把一个数字向下拨动,即9变成8,8变成7...1变成0,0变成9。
她想知道从第一个状态变成第二个状态需要最少拨动多少次?
简单打卡
int main() {
string a,b;
cin>>a>>b;
int res =0;
for(int i=0;i<a.size();i++){
int num1 = a[i]-'0';
int num2 = b[i]-'0';
if(num1>=num2) res+=(num1-num2);
else res+= (num1+10-num2);
}
cout<<res<<endl;
return 0;
}
2. 小红和小紫玩游戏
小红和小紫正在玩一个游戏,每一关都有一个分数。如果某人某一关分数比上一关高,但另一个人这一关分数比上一关低,那么他就可以嘲笑对方。
如果两个人这一关游戏的分数都比上一关多,则增量更多的可以嘲笑对方;如果两个人这一关游戏的分数都比上一关少,则减量更少的可以嘲笑对方。只有当他们的增量相同或者减量相同时,才不会互相嘲笑。
例如,假设小红第一关的分数为5,第二关的分数为10;小紫第一关的分数为2,第二关的分数为8,显然小红增加的比小紫多,那么小红就可以嘲笑小紫。
现在给定了小红和小紫每一关的分数,你可以选择一段连续的关卡,使得这一段关卡中两个人都不会互相嘲笑,问最多可以选择多少个关卡。特别的,一段连续关卡中的第一关两人不会互相嘲笑。
简单动态规划
int main() {
int n;
cin>>n;
vector<int> nums1(n);
vector<int> nums2(n);
for(int i=0;i<n;i++)
cin>>nums1[i];
for(int i=0;i<n;i++)
cin>>nums2[i];
int res = 0;int cur = 0;
for(int i=1;i<n;i++){
if(nums1[i]-nums1[i-1]==nums2[i]-nums2[i-1]) cur++;
else cur = 0;
res = max(res,cur);
}
cout<<res+1<<endl;
return 0;
}
3. 括号匹配
对于一个仅由左括号'('和右括号')'组成的字符串,小红想知道它的最长合法前缀的长度是多少。
对于某一个前缀,我们定义它是合法的,当且仅当该前缀满足以下条件:存在一种拆分方案,
可以将该前缀拆分为若干对匹配的括号'()', 如'()','()()','(())'都是合法的,而')()(','))'是非法的。特殊的,空串我们认为也是合法的。
栈都用不上
int main() {
int n;
cin>>n;
string s;
cin>>s;
int cnt = 0;int res = 0;
for(int i=0;i<n;i++){
if(s[i]=='(') cnt++;
else cnt--;
if(cnt<0) break;
if(cnt==0) res = i+1;
}
cout<<res<<endl;
return 0;
}