题解42:https://ac.nowcoder.com/acm/problem/21874 好串

思路:a与b要配对,因为是a先b后,而且b是与最近的a配对(插入ab),所以考虑栈 有a就入栈,有b就去出栈(与a配对),如果无栈可出,说明配不上对->Bad

AC代码:

#include<iostream>
#include<stack>
#include<string>
using namespace std;
int main()
{
    string s;cin>>s;
    stack<bool> st;
    for(int i=0;i<s.size();++i)
    {
        if(s[i]=='a') {st.push(1);}
        else 
        {
            if(!st.empty()) {st.pop();}
            else {cout<<"Bad";return 0;}
        }
    }
    if(st.empty()) {cout<<"Good";}
    else {cout<<"Bad";}
    return 0;
}

题解43:https://ac.nowcoder.com/acm/problem/16663 [NOIP2004]合并果子

思路:因为每次只能将两堆合并成一堆(堆数-1),所以合并次数一定是n-1次.那么只要让每次合并消耗的体力值最小即可(永远选择最小的两堆).可以用优先队列.但这里用两个队列实现:因为根据策略,先合并的永远小一些,所以可以单独开一个队列记录合并后的每一堆的水果数量(单调递增).然后取两次两个队列队首两者的最小值(因为两个队列此时都有单调性了)

注意:在对栈做操作前(插入除外),一定要先判断栈是不是空的!!! =>!st.empty()

AC代码:

#include<queue>
#include<iostream>
#include<algorithm>
using namespace std;
int fruit[10010];
int main()
{
    ios::sync_with_stdio(0);cin.tie(0);
    int n;cin>>n;
    queue<int> ori,merge;
    int t;
    for(int i=1;i<=n;++i) {cin>>fruit[i];}
    sort(fruit+1,fruit+1+n);//排序:使第一个队列单调
    for(int i=1;i<=n;++i) {ori.push(fruit[i]);}
    int t1,t2;
    long long cnt=0;
    for(int i=1;i<n;++i)
    {
        if((!ori.empty() && ori.front()<=merge.front()) || merge.empty()) {t1=ori.front();ori.pop();}
        else {t1=merge.front();merge.pop();}
        if((!ori.empty() && ori.front()<=merge.front()) || merge.empty()) {t2=ori.front();ori.pop();}
        else {t2=merge.front();merge.pop();}
        cnt+=t1+t2;//消耗的体力值
        merge.push(t1+t2);
    }
    cout<<cnt;
    return 0;
}

题解44:https://ac.nowcoder.com/acm/problem/16430 [NOIP2016]蚯蚓

前言:跟上道题差不多,也是实时求最大值,但这里不是合并成一份,而是切成两份,所以需要三个队列,索性开个数组了,类比int a[N], stack a[N]中的每一个a[n]就是stack.这道题请先仔细读题,并看清楚要输出什么

PS:因为蚯蚓后切的没有前面切的那么大(前面切的也会长,而且是先切大的再切小的),所以三个队列各自照样有序(类比题解43)

思路&AC代码:

#include<iostream>
#include<algorithm>
#include<queue>
using namespace std;
//#define ll long long
#define minres -1e9;
int a[100010];
int main()
{
    ios::sync_with_stdio(0);cin.tie(0);
    int n,m,q,u,v,t;cin>>n>>m>>q>>u>>v>>t;
    for(int i=1;i<=n;++i) {cin>>a[i];}
    sort(a+1,a+1+n);//使队列0有序
    queue<int> qu[3];
    for(int i=n;i>=1;--i) {qu[0].push(a[i]);}
    for(int i=1;i<=m;++i)
    {
        long long maxn=minres;
        int pos=-1;
        //找当前最大值,及其所在队列
        for(int j=0;j<=2;++j)
        {
            if(!qu[j].empty() && qu[j].front()>maxn)
            {
                maxn=qu[j].front();pos=j;
            }
        }
        maxn+=(i-1)*q;//我们不可能实时更新蚯蚓长度(性能开销太大),但是在每次切的时候要以当前的长度乘系数         (i-1)代表这一秒及以前蚯蚓长了多长,这一秒不长
        qu[pos].pop();//切掉了蚯蚓
  		qu[1].push(maxn*u/v-i*q);//用double存浮点数性能开销大了点,而int t=u/v会直接变成0,所以在这里连乘除,刚好又可以利用上int向下取整
  		//-i*q是因为要还原回去(不然没切的与被切的蚯蚓不同步),不是(i-1)是因为被切的蚯蚓这一秒不长,相对其他蚯蚓就少了一个q,保持了相对值不变.还有利于后面计算总长度,一举两得
  		qu[2].push((maxn-maxn*u/v)-i*q);//原长-被切掉的长度==另一半长度
        if(i%t==0) {cout<<maxn<<' ';}//输出第kt秒的
    }
    cout<<'\n';//有没有数据都要换行
    int tmpcnt=1;//记录下这是第几大了
    while(!qu[0].empty() || !qu[1].empty() || !qu[2].empty())//保证访问stack合法
    {
        int maxn=minres;
        int pos=-1;
        for(int i=0;i<=2;++i)
        {
            if(!qu[i].empty() && qu[i].front()>maxn)
            {
                maxn=qu[i].front();pos=i;
            }
        }
  		//找出当前最大值
        qu[pos].pop();//已经找过了,不用再后面再找了
        if(tmpcnt%t==0) {cout<<maxn+m*q<<' ';}//切的那一秒不长已经在前面减去了,这里+上全程都长的长度
        ++tmpcnt;
    }
    cout<<'\n';//有没有数据都要换行
    return 0;
}

题解45:https://ac.nowcoder.com/acm/problem/14661 简单的数据结构

熟悉熟悉一些STL的方法

有了STL,在此基础上添加一些新功能,优化优化 思路:反转了奇数次,front的操作变为back操作,back操作变为front操作

AC代码:

#include<iostream>
#include<algorithm>
#include<deque>
using namespace std;
inline bool comp(int x,int y)
{
   return x>y;
}
int main()
{
   bool cnt=1;
   ios::sync_with_stdio(0);cin.tie(0);
   deque<int> de;
   int m;cin>>m>>m;
   int oper;
   int tmp;
   while(m--)
   {
       cin>>oper;
       switch (oper) 
       {
           case 1:
               cin>>tmp;
               if(cnt) {de.push_front(tmp);}
               else {de.push_back(tmp);}
               break;
           case 2:
               if(cnt) {de.pop_front();}
               else {de.pop_back();}
               break;
           case 3:
               cin>>tmp;
               if(cnt) {de.push_back(tmp);}
               else {de.push_front(tmp);}
               break;
           case 4:
               if(cnt) {de.pop_back();}
               else {de.pop_front();}
               break;
           case 5:
               cnt^=1;//利用上异或的特性,初始为1,偶数次反转不变,仍为1,奇数次反转变,为0
               break;
           case 6:
               cout<<de.size()<<'\n';
               if(cnt)
               {
                   for(auto it=de.begin();it!=de.end();++it)//迭代器遍历,也可改为用下标遍历
                   {
                       cout<<*it<<' ';
                   }
               }
               else//反转了就要反着输出
               {
                   for(auto it=de.end()-1;it!=de.begin()-1;--it)
                   {
                       cout<<*it<<' ';
                   }
               }
               cout<<'\n';
               break;
           default:
               if(cnt){sort(de.begin(),de.end());}
               else {sort(de.begin(),de.end(),comp);}//反转了,,如146253,反转排序后要反着输出654321,就必须要反着排序
       }
   }
   return 0;
}