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-它的前面比它小的数的个数，即求出逆序对个数
总的说，树状数组就起了个标记+求前缀和的作用，整个思想巧妙简单，要记牢，并且写法优美，值得一记
具体明天再来，下班