D. Unnatural Language Processing
给字符串元素按要求间隔”.“
#include<bits/stdc++.h>
using namespace std;
void solve(){
int n;
string s;
cin>>n>>s;
string o=s;
for(int i=0;i<n;i++){
if(s[i]=='c'||s[i]=='d'||s[i]=='b')s[i]='C';
if(s[i]=='a'||s[i]=='e')s[i]='V';
}
for(int i=0;i<n-2;i++){
cout<<o[i];
if(s[i]=='V'&&s[i+1]=='C'&&s[i+2]!='C'){
cout<<".";
continue;
}
if(s[i]=='C'&&s[i+1]=='C'){
cout<<".";
continue;
}
}
for(int i=n-2;i<n;i++){
cout<<o[i];
}
cout<<"\n";
}
int main(){
ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
int t=1;
cin>>t;
for(int i=1;i<=t;i++)solve();
return 0;
}
E. Romantic Glasses
题意：找出一个区间，里面奇偶下表的元素之和相等
首先你要知道的是怎么看一个区间里面奇偶下表之和相等。假使一个数组是2 4 -2 3 -5
做一个前缀和 2 6 4 7 2 // 2 和 2 出现两次，因为是前缀和说明中间的子数组和为0，由此判断。注意的是特殊的 1 3 2，分别对奇偶下表前缀 1 1 3 ，0 3 3然后相减1 -2 0，乍一看没有相等的，但是答案是yes。那是因为要提前把0计算进去，因为0是特殊的，如果是0代表的是前缀相等，那么自然满足条件。
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=2e5+10;
void solve(){
int n;
cin>>n;
vector<int>a(n+1);
for(int i=1;i<=n;i++)cin>>a[i];
vector<int>o(n+1);
vector<int>e(n+1);
for(int i=1;i<=n;i++){
o[i]=o[i-1];
e[i]=e[i-1];
if(i&1){
o[i]+=a[i];
}else{
e[i]+=a[i];
}
}
map<int,int>mp;
for(int i=1;i<=n;i++){
int x=o[i]-e[i];
mp[x]++;
}
mp[0]++;
for(auto c:mp){
if(c.second>=2){
cout<<"YES\n";
return;
}
}
cout<<"NO\n";
}
signed main(){
ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
int t=1;
cin>>t;
for(int i=1;i<=t;i++)solve();
return 0;
}
F. Greetings
人在区间里跑，跑到终点结束，遇见就ans++，不难看出只有一个区间套在另一个区间的时候人才能遇见，那么只需要枚举区间即可，按起点小的排序。看终点比自己小的。一直循环下去。
然后就能看出实际上就是对排序后的终点数组求逆序对。
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=2e5+10;
int mergeSort(vector<int>& nums, int left, int right) {
if (left >= right) return 0;
int mid = left + (right - left) / 2;
// 分治递归
long long count = mergeSort(nums, left, mid) + mergeSort(nums, mid + 1, right);
// 归并合并
vector<int> temp(right - left + 1);
int i = left, j = mid + 1, k = 0;
while (i <= mid && j <= right) {
if (nums[i] <= nums[j])
temp[k++] = nums[i++];
else {
temp[k++] = nums[j++];
count += mid - i + 1; // 统计逆序对数量
}
}
while (i <= mid)
temp[k++] = nums[i++];
while (j <= right)
temp[k++] = nums[j++];
for (int p = 0; p < k; ++p)
nums[left + p] = temp[p];
return count;
}
void solve(){
int n;
cin>>n;
vector<pair<int,int>>a(n+1);
for(int i=1;i<=n;i++){
cin>>a[i].first>>a[i].second;
}
sort(a.begin()+1,a.begin()+1+n);
vector<int>b;
for(int i=1;i<=n;i++){
b.push_back(a[i].second);
}
int ans=mergeSort(b,0,n-1);
cout<<ans<<"\n";
}
signed main(){
ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
int t=1;
cin>>t;
for(int i=1;i<=t;i++)solve();
return 0;
}