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总算法基础课的求逆序对
逆序对的定义如下::对于数列的第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;
}
G.Bicycles
算法分析:二维dijstra
请允许蒻蒟还不会吧,呜呜