cf 918(D-G)div4

D.Unnatural Language Processing

算法分析:string模拟+贪心

贪心策略:把元音字母看作0,辅音字母作为1，因为是等价的,构造字符串，寻找a.find("101"),a.find("10");判断合理性,贪心选择101还是10,最后把原数组打印，erase删除前面的"101"/"10"串,直到串删为空

~~不要偷懒递归，会爆内存，博主就是偷懒的~~

#include<bits/stdc++.h>
using namespace std;
int t;
typedef long long ll;
#define str  string
 int n;
void ustr(str a, str b)
{
 
    while(1)
    {
        int pose = b.find("10");
    int npose = b.find("101");
    if (npose > 0)
    {
        if (b.size() > 2)
            cout << a.substr(0, 2) << '.';
        else
            {cout << a.substr(0, 2)<<endl;break;}
        a.erase(0,2);
        b.erase(0,2);
    }
    else
    {
        if (b.size() > 3)
        {
            if (b[3] == '0')
            {
                if (b.size() > 2)
                    cout << a.substr(0, 2) << '.';
                else
                    {
                        cout << a.substr(0, 2) << endl;
                        break;
                    }
             a.erase(0,2);
        b.erase(0,2);
            }
            else
            {
                cout << a.substr(0, 3) << '.';
                b.erase(0,3);
                a.erase(0,3);
            }
        }
        else
            {
                cout << a << endl;
                break;
            }
      }
    }
}
int main()
{
    ios::sync_with_stdio(false);cin.tie();cout.tie();
    cin >> t;
    while (t--)
    {
        cin >> n;
        string a, b;
        cin >> a;
        b = a;
        for (int i = 0; i < n; i++)
        {
            if (a[i] == 'a' || a[i] == 'e')b[i] = '0';
            else b[i] = '1';
        }
        ustr(a, b);
    }
   return 0;
  }

E.Romantic Glasses

算法分析:set判断+贪心策略

将奇数项和偶数项分别作为整数和负数

当出现一段大小不变说明可以产生连续相等串(res+=a[i];set.insert(res);

也就是后面一段存在和为0的

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll t,n;
ll a[200020];
int main()
{
    ios::sync_with_stdio(false);cin.tie();cout.tie();
cin>>t;
while(t--)
{
cin>>n;
for(int i=1;i<=n;i++)cin>>a[i];
for(int i=2;i<=n;i+=2)a[i]=-a[i];
  set<ll>s;
  s.insert(0);
  ll res=0;
  bool df=false;
  for(int i=1;i<=n;i++)
  {
   res+=a[i];
   if(s.count(res))
   {
    cout<<"YES\n";df=true;
    break;
   }
   s.insert(res);
  }
  if(!df)
  cout<<"NO\n";
}
    return 0;
}

F.Greetings

观察贪心本题目实际是求包含(下面左端点x，右端点y)

也就是左端点L,右端点R

L1<=l2,R2<=R1；

我们很自然想到排序左端点

但是接下来如何求包含呢，一个神奇的东西出现了，y总算法基础课的求逆序对

788. 逆序对的数量 - AcWing题库

逆序对的定义如下：：对于数列的第i个和第j个元素，如果满足i<j且a[i]>a[j],则其为一个逆序对；否则不是

如果我们将区间按照左端点排序,我们要求的其实就是后面的点(x排序后)且符合其y小于等于我们现在的右端点，我们只要小改逆序对定于为a[i].y>=a[j].y即可符合此题目

//ac代码
#include<bits/stdc++.h>
 using namespace std;
int t;
const int N=2e5+10;
int n;
typedef long long ll;
struct p{
    int x,y;
}a[N],tmp[N];
bool cmp(p c,p d)
{
   if(c.x==d.x)return c.y<d.y;
    return c.x<d.x;
}
ll my_sort(int l,int r)
{
    if(l>=r)return 0;
    int mid=(l+r)>>1;
    ll res=my_sort(l,mid)+my_sort(mid+1,r);
    int k=0,i=l,j=mid+1;
    while(i<=mid&&j<=r)
   if(a[i].y<a[j].y)tmp[k++].y=a[i++].y;
    else
    {
        res+=mid-i+1;
        tmp[k++].y=a[j++].y;
    }
    while(i<=mid)tmp[k++].y=a[i++].y;
    while(j<=r)tmp[k++].y=a[j++].y;
    for(int i=l,j=0;i<=r;i++,j++)
  a[i].y=tmp[j].y;
  return res;
}
void sovle()
{
    cin>>n;
    for(int i=1;i<=n;i++)cin>>a[i].x>>a[i].y;
    int l=1,r=n;
    sort(a+1,a+1+n,cmp);
    cout<<my_sort(l,r)<<endl;
}
int main()
{
    ios::sync_with_stdio(false);cin.tie();cout.tie();
    cin>>t;
    while(t--)
    sovle();
    return 0;
}