Hey left 1 Codeforces Round 918 (Div. 4)

题目链接

A.

3个数，其中2个数相同，输出不相同的那个
可以用if else判断，较为麻烦
用的map，输出出现一次的

#include <bits/stdc++.h>
using namespace std;

const int N=1e5+10;

void solve(){
    map<int,int>mp;
    for(int i=0,x;i<3;i++){
        cin>>x;
        mp[x]++;
    }
    for(auto t:mp){
        if(t.second==1)cout<<t.first<<endl;
    }
}


signed main(){
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    int hey_left=1;
    cin>>hey_left;
    while(hey_left--){
        solve();
    }
    return 0;
}

B.

3种字符每行只有一个，那么就有3个，同时每列也要有一个
所以3种字符都应该出现三次
map计数，不等于3并且不是？就输出

#include <bits/stdc++.h>
using namespace std;

const int N=1e5+10;

void solve(){
    map<char,int>mp;
    for(int i=0;i<9;i++){
        char c;cin>>c;
        mp[c]++;
    }
    for(auto t:mp){
        if(t.second!=3&&t.first!='?')cout<<t.first<<endl;
    }
}


signed main(){
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    int hey_left=1;
    cin>>hey_left;
    while(hey_left--){
        solve();
    }
    return 0;
}

D.

难点在两种音节都满足条件的情况下，应该选哪一种音节
考虑从音节本身的特点出发，能不能唯一确定
结构为 CV 或 CVC
可以发现，从后往前看
如果最后一个字母是V，那么能唯一确定取两个字符的音节
如果最后一个字母是C，那么能唯一确定取三个字符的音节
至此，思路解决

debug的一个点：
我把得到的音节都储存在一个栈里
题目要求输出的音节之间有一个分隔符，最后一个音节后面不要分隔符
我的处理方式是先用一个变量si记录栈的容量
然后用while（si--）的方式来特判最后一个音节
错误：if(si!=1)cout<<'.';
正确：if(si!=0)cout<<'.';
语法糖了属于是，while时si是1，但循环内si已经变为0

#include <bits/stdc++.h>
using namespace std;

void solve(){
    stack<string>st;
    int n;cin>>n;
    string s;cin>>s;
    int i=s.size()-1;
    while(i>=0){
        string t="";
        if(s[i]=='a'||s[i]=='e'){
            t.push_back(s[i-1]);t.push_back(s[i]);
            st.push(t);
            i-=2;
        }else {
            t.push_back(s[i-2]);t.push_back(s[i-1]);t.push_back(s[i]);
            st.push(t);
            i-=3;
        }
    }
    int si=st.size();
    while(si--){
        cout<<st.top();st.pop();
        if(si!=0)cout<<'.';
    }
    cout<<endl;
}


signed main(){
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    int hey_left=1;
    cin>>hey_left;
    while(hey_left--){
        solve();
    }
    return 0;
}

E.

这道题因为之前有人说过，算是第二次做了
话说第一次做的时候没做出来，绕在了定性思维，看了下1300分的题，好好好，惭愧

判断是否存在一个子序列，奇数位的和等于偶数位的和
如果把偶数位数值取反，相当于这段和为0，消去了
族友提供了一个很新颖的办法（可能对我来说），跑一遍前缀和，用map存下每个值，如果某个值的个数大等于2，说明一定有一段和为0，才会出现相等的情况
当时还debug了一个点，map里要预先mp[0]++，因为前缀和开始的数值是0

#include <bits/stdc++.h>
using namespace std;

const int N=2e5+10;
#define int long long

void solve(){
    int n;cin>>n;
    int a[N];
    for(int i=1;i<=n;i++){
        cin>>a[i];
        if(i%2==0)a[i]=-a[i];
    }
    map<int,int>mp;
    mp[0]++;
    int sum=0;
    for(int i=1;i<=n;i++){
        sum+=a[i];
        mp[sum]++;
    }
    for(auto t:mp){
        if(t.second>=2){
            cout<<"YES"<<endl;return ;
        }
    }
    cout<<"NO"<<endl;
}


signed main(){
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    int hey_left=1;
    cin>>hey_left;
    while(hey_left--){
        solve();
    }
    return 0;
}

G.

初步思路：两个人a和b，若a的起点比b的起点小，且a的终点比b的终点大，那么他们俩一定会相遇
直接用例子讲：
8 10
6 7
3 4
-2 5
-4 9

从上往下，每个数之和这个数之下的数去比较
有几个比第二维大的，答案就加几
如0+1+2+1=4

记得之前浅学了一个伸展树的模板，属于无脑毒瘤数据结构了
在线算法，插入一个数后，可以求当前数的排名（比当前数小的数的个数+1）
那么我们要求比当前数小的数，直接排名-1即可
于是乎风风火火地贴模板，过了样例，但T2

正解原来是求逆序对！
这个题应该做过至少两次了，这次还是不会做，又忘了，逆序对也忘了
直接重开

先整个树状数组的结构体封装（已测）

#include <bits/stdc++.h>
using namespace std;

#define int long long
template <typename T>
struct TreeArray{
    vector<T> tree;

    TreeArray(T n){
        tree.resize(n+1,T(0));
    }

    void update(T index,T value){
        while(index<tree.size()){
            tree[index]+=value;
            index+=index&(-index);
        }
    }

    T query(T index){
        T sum=0;
        while(index>0){
            sum+=tree[index];
            index-=index&(-index);
        }
        return sum;
    }
};

void solve(){
    int n,m;cin>>n>>m;
    TreeArray<long long> ta(n);
    for(int i=1,x;i<=n;i++){
        cin>>x;
        ta.update(i,x);
    }
    for(int i=0;i<m;i++){
        int op,x,y;cin>>op>>x>>y;
        if(op==1){
            ta.update(x,y);
        }else if(op==2){
            cout<<ta.query(y)-ta.query(x-1)<<'\n';
        }
    }
}


signed main(){
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    int hey_left=1;
    //cin>>hey_left;
    while(hey_left--){
        solve();
    }
    return 0;
}

树状数组求逆序对的思想：
一列数，我们求第i个数的逆序对的个数，也就是它的前面有几个比它大的数
那么可以用i-它的前面比它小的数的个数
注意，为什么这样转换呢
因为数组下标天然有序且是正序，我们可以把数和下标对应起来，出现的数我们把数组值设为1，那么我们求第i个数的前缀和-1，不就算出了第i个数前面有几个小于它的数了吗
用i-它的前面比它小的数的个数，即求出逆序对个数
总的说，树状数组就起了个标记+求前缀和的作用，整个思想巧妙简单，要记牢，并且写法优美，值得一记

具体明天再来，下班