A.构造C的歪

喜欢歪的等差数列吗？

只需要把任意一个数字当作等差数列的中项，然后利用等差数列 的性质，，即可推导出题目的 。

void solve(){
    i64 a,b;
    cin>>a>>b;
    cout<<(2*b-a);
}

B. 不要三句号的歪

没想到还可以这么做吧~

按照题意模拟，找出第一个数字和第三个数字，然后求个数即可。 做法一:使用scanf直接按照格式读入

void solve(){
    i64 a,b,c;
    scanf("%lld,%lld,...,%lld",&a,&b,&c);
    cout<<c-b-1;
}

第二种:使用substr+stoll转换

void solve(){
    string s;
    cin>>s;
    int w1=s.find(',',0);
    int w2=s.find(',',w1+1);
    int w3=s.find(',',w2+1);
    i64 a=stoll(s.substr(0,w1));
    i64 b=stoll(s.substr(w3+1,s.size()-w3-1));
    cout<<b-a-2;
}

C.仰望水面的歪

喜欢我的三角形吗？

只需要考虑二维平面，如图所示: 为起点， 位终点， 为所求的折射点。 考虑折射的性质必然满足 ▲ ≌ ▲ 。 所以 的坐标为 。 再同时除以三个数的最大公约数即可达到最简向量。

void solve(){
    int n;
    i64 h;
    cin>>n>>h;
    for(int i=1;i<=n;i++){
        i64 x,y,z;
        cin>>x>>y>>z;
        i64 nz=h*2-z;
        i64 Gcd=__gcd(__gcd(x,y),nz);
        cout<<x/Gcd<<" "<<y/Gcd<<" "<<nz/Gcd<<"\n";
    }
}

D. 小心火烛的歪

因为最优解wa了吗？内测的数据的可行解全是最少次数，导致看错题意也能过，后来加强了数据。

注意到数据范围最大是 。 所以直接二进制枚举每个计划要不要，然后更新给一个方阵，最后检查此方阵和初始的图是否存在一个位置不满足题意，按照此方法模拟即可,存在满足条件的方案的当前的方案比较次数，若存在更少次数的方案更新。

void solve(){
    int n,m,q;
    cin>>n>>m>>q;
    vector<string>mp1(n+1);
    vector<vector<string>>mp2(q+1,vector<string>(n+1));
    for(int i=1;i<=n;i++){
        cin>>mp1[i];
        mp1[i]='&'+mp1[i];
    }
    for(int i=1;i<=q;i++){
        for(int j=1;j<=n;j++){
            cin>>mp2[i][j];
            mp2[i][j]='%'+mp2[i][j];
        }
    }
    vector<int>res;
    for(int i=0;i<10;i++) res.push_back(1);
    for(int i=0;i<=(1ll<<q);i++){
        vector<vector<char>>temp(n+1,vector<char>(m+1,'0'));
        vector<bool>choose(q+1,false);
        for(int j=0;j<q;j++){
            if((i>>j)&1){
                choose[j+1]=true;
                for(int x=1;x<=n;x++){
                    for(int y=1;y<=m;y++){
                        if(mp2[j+1][x][y]=='1'){
                            temp[x][y]='1';
                        }
                    }
                }
            }
        }
        bool ok=true;
        for(int x=1;x<=n;x++){
            for(int y=1;y<=m;y++){
                if(mp1[x][y]==temp[x][y]){
                    ok=false;
                    break;
                }
            }
            if(!ok) break;
        }
        if(ok){
            
            vector<int>ans;
            for(int j=1;j<=q;j++){
                if(choose[j]){
                    ans.push_back(j);
                }
            }
            if(res.size()>ans.size()){
                swap(res,ans);
            }
        }
    }
    if(res.size()==10){
        cout<<"-1";
    }else{
        cout<<res.size()<<"\n";
        for(auto t:res){
            cout<<t<<" ";
        }
    }
}

E.喜欢切数组的红

是您喜欢的毛毛冲做法吗？我又来毛毛虫啦~

本题也有 的做法，可以悟一下，内测时候第一反应有啥做法就写了。 首先考虑数字分成三份，且总和相等，必然先要满足总和是 的倍数。

然后对于每个 点，记录前面的 的点中有多少个前缀中的正数个数是少于此 点的个数，然后同时满足后 点的正数个数也是大于 的。这样便可得到总的方案数。

维护前缀正数的个数可以使用树状数组。

using i64=long long;
#define pi acos(-1)
#define lowbit(x) x & (-x)
struct BIT
{
    int n;
    vector<i64> tree;
    void init(int x)
    {
        n = x;
        tree.resize(x + 10);
    }
    void add(int x, int c)
    {
        for (int i = x; i <= n; i += lowbit(i))
        {
            tree[i] += c;
        }
    }
    i64 sum(int x)
    {
        i64 ans = 0;
        for (int i = x; i > 0; i -= lowbit(i))
        {
            ans = ans + tree[i];
        }
        return ans;
    }
};
void solve(){
    int n;
    cin>>n;
    vector<i64>a(n+1);
    vector<int>prepos(n+2);
    vector<i64>s(n+5);
    for(int i=1;i<=n;i++){
        cin>>a[i];
        s[i]=s[i-1]+a[i];
        prepos[i]=prepos[i-1]+(a[i]>0);
    }
    if(s[n]%3!=0){
        cout<<0;
        return ;
    }
    i64 sum=0,pos_num=0;
    BIT T;
    T.init(2e5);
    i64 ans=0;
    for(int i=1;i<=n;i++){
        sum+=a[i];
        if(sum==s[n]/3){
            if(prepos[i]>0)
            T.add(prepos[i],1);
        }else if(sum==s[n]/3*2){
            
            if(prepos[n]-prepos[i]>0&&prepos[i]>1)ans+=T.sum(prepos[i]-1);
        }
    }
    cout<<ans;
}

F.研究red子序列的红

我们都是小红人！原来是想给校招的题，后来没活就上这个了。

交换的本质上是模拟，所以实际上是考虑如何实时维护一个字符串的 子序列。 我们可以考虑线段树来维护，一个大区间如何由左右两个小区间合并过来？ 显然对于大区间的 可以由两个小区间的 直接加。 大区间的 可以由左区间的 和右区间的 直接乘以及加上两个小区间的含有的自身数量。 大区间的 可以由左区间的 和右区间的 直接乘以及加上两个小区间的含有的自身数量。 大区间的 可以由两个小区间的 数量之和得到，同时加上左区间的 乘以右区间的 ，还有左区间的 乘右区间 。 这样便可以做到 级别维护。 最后求和做一下差即可。

#define ls p<<1
#define rs p<<1|1
struct T
{
    int l;
    int r;
    i64 R,E,D,RE,ED,RED;
};
struct SegTree{
    vector<T>tree;
    string s;
    void init(int n,string t){
        s=t;
        tree.resize(n*4+5);
        return ;
    }
    void build(int p,int l,int r){
        tree[p].l=l;
        tree[p].r=r;
        if(l==r){
            tree[p].R=tree[p].E=tree[p].D=tree[p].RE=tree[p].ED=tree[p].RED=0;
            if(s[l]=='r')tree[p].R=1;
            if(s[l]=='e') tree[p].E=1;
            if(s[l]=='d') tree[p].D=1;
            return ;
        }
        int mid=(l+r)>>1;
        build(ls,l,mid);
        build(rs,mid+1,r);
        tree[p].R=tree[ls].R+tree[rs].R;
        tree[p].E=tree[ls].E+tree[rs].E;
        tree[p].D=tree[ls].D+tree[rs].D;
        tree[p].RE=tree[ls].RE+tree[rs].RE+tree[ls].R*tree[rs].E;
        tree[p].ED=tree[ls].ED+tree[rs].ED+tree[ls].E*tree[rs].D;
        tree[p].RED=tree[ls].RED+tree[rs].RED+tree[ls].RE*tree[rs].D+tree[ls].R*tree[rs].ED;
        return ;
    }
    void upt(int p,int x,char t){
         if(tree[p].l==x&&tree[p].r==x){
            if(s[x]=='r') tree[p].R--;
            else if(s[x]=='e') tree[p].E--;
            else if(s[x]=='d') tree[p].D--;
            s[x]=t;
            if(s[x]=='r') tree[p].R++;
            else if(s[x]=='e') tree[p].E++;
            else if(s[x]=='d') tree[p].D++;
            return ;
        } 
        int mid=(tree[p].l+tree[p].r)>>1;
        if(x<=mid) upt(ls,x,t);
        if(x>mid) upt(rs,x,t); 
        tree[p].R=tree[ls].R+tree[rs].R;
        tree[p].E=tree[ls].E+tree[rs].E;
        tree[p].D=tree[ls].D+tree[rs].D;
        tree[p].RE=tree[ls].RE+tree[rs].RE+tree[ls].R*tree[rs].E;
        tree[p].ED=tree[ls].ED+tree[rs].ED+tree[ls].E*tree[rs].D;
        tree[p].RED=tree[ls].RED+tree[rs].RED+tree[ls].RE*tree[rs].D+tree[ls].R*tree[rs].ED;
        return ;
    }
    array<i64,6> ask(int p,int l,int r){
        if(tree[p].l>=l&&tree[p].r<=r){
            return {tree[p].R,tree[p].E,tree[p].D,tree[p].RE,tree[p].ED,tree[p].RED};
        }
        int mid=(tree[p].l+tree[p].r)>>1;
        array<i64,6>g1,g2,g3;
          if(l<=mid){
            g1=ask(ls,l,r);
        }
        if(r>mid){
            g2=ask(rs,l,r);
        }
        g3[0]=g1[0]+g2[0];//R
        g3[1]=g1[1]+g2[1];//E
        g3[2]=g1[2]+g2[2];//D
        g3[3]=g1[3]+g2[2]+g1[0]*g2[1];//RE
        g3[4]=g1[4]+g2[4]+g1[1]*g2[2];//ED
        g3[5]+=g1[3]*g2[2];//RED
        g3[5]+=g1[0]*g2[4];
        g3[5]+=g1[5]+g2[5];
        return g3;
    }
};
void solve(){
    int n,q;
    string s,t;
    cin>>n>>q;
    cin>>s>>t;
    s='%'+s;
    t='%'+t;
    SegTree Ts,Tt;
    Ts.init(n,s),Tt.init(n,t);
    Ts.build(1,1,n);
    Tt.build(1,1,n);
    while(q--){
        int x;
        cin>>x;
        char t1=Ts.s[x],t2=Tt.s[x];
        Ts.upt(1,x,t2);
        Tt.upt(1,x,t1);
        auto g1=Ts.ask(1,1,n);
        auto g2=Tt.ask(1,1,n);
        cout<<g1[5]-g2[5]<<"\n"; 
    }
    
}