赛时EG，补KLIH

G

题意

给定一个字符串S，处理q次询问
每次询问给出另一字符串T和数字a
回答T和S有多少相同的区间满足 $S_{a+x-1}=T_x$

思路

签到题，将T和S直接按位对比有多少连续且相同的字母
每个连续区间对总答案的贡献是 $\frac{n(n-1)}{2}$
总复杂度： $O(n+\sum{|T|})$

代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
signed main(){
    int n,q;
    cin >> n >> q;

    string s;
    cin >> s;
    
    for(int i=0;i<q;i++){
        string t;
        cin >> t;
        t+=' ';
        int a;
        cin >> a;
        int tmp=0,ans=0;
        for(int j=0;j<t.size();j++){
            if(t[j]==s[j+a-1]&&j+a-1<s.size()){
                tmp++;
            }else{
                // cout << j << ' ' << tmp << endl;
                ans+=tmp*(tmp+1)/2;
                tmp=0;
            }
        }
        cout << ans << endl;
    }
    return 0;
}

E

题意

将所有可被两个整数的平方差表示的正整数排成序列
对于T组a,b,请问 $|a^{2}-b^{2}|$ 在序列中的序号

思路

观察发现，所有的奇数是可被表示的，4的倍数不含4是可以表示的，其它不可以表示
记： $tar=|a^2-b^2|$
所以 $ans=tar-(\frac{tar}{2}-\frac{tar}{4}+2)$
特别地，-2去除的是1和4，所以如果询问的是3会得到0,特判即可

代码

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

int main(){
    int t;
    cin >> t;
    while(t--){
        long long a,b;
        cin >> a >> b;
        long long tp=abs(a*a-b*b);
        cout << max(1ll,tp-(tp/2-tp/4+2)) << endl;
    }
    return 0;
}

L

题意

给定n个数，有k次查询，每次查询会让某一个数 $a_i$ 变为 $a_{i}+v$
每次查询后，严格小于其它n-1个数中至少 $\lceil\frac{n-1}{2}\rceil$

思路

如果维护中位数，直接对顶堆即可，但是题意所求其实是严格小于中位数的数字个数，如果使用对顶堆，不知道两侧堆中和中位数相同的数字个数
如果使用multiset，常数大会超时(赛时爆炸)
改用map维护，记录出现的数及出现次数，使用一个指针，总保证指针做左侧的个数少于等于一半的个数
同时维护一个cnt，记录左侧个数，每次询问后调整即可
记得开long long

代码

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
ll a[202020];
int main (){
    int t;
    scanf("%d",&t);
    while(t--){
        int n,q;
        map<ll,ll> mp;
        scanf("%d%d",&n,&q);
        for(int i=0;i<n;i++){
            scanf("%lld",&a[i]);
            mp[a[i]]++;
        }
        int mid=n-n/2;
        auto it=mp.begin();
        ll cnt=0;
        for(int i=0;i<q;i++){
            int id,v;
            scanf("%d%d",&id,&v);
            id--;
            ll pre=a[id];
            mp[a[id]]--;
            a[id]+=v;
            mp[a[id]]++;
            if(pre<it->first&&a[id]>=it->first){
                cnt--;
            }
            while(cnt+it->second<=mid){
                cnt+=it->second;
                it++;
            }
            printf("%lld\n",cnt);
        }
    }
    return 0;
}

K

题意

对于一个图n个点，每个点有不超过三个无向边
对于一个点，如果是从这个点的i号边进入，就要从i+1号边出，如果超出边数，就为1
对于给定的图，请输出从每个点第一个无向边出发，最多走几条不同的无向边

思路

对于任意一个路径总能走成一个环
整个图最后会变为若干环，每个环的大小答案
赛时没看出来会跑成环，建了个图硬搜没搜出来
赛后实现感觉很繁琐的一个题，过程如下：
- 从结果往回推最后需要对环判断，要知道每个点属于哪个环，以及每个环的大小
- 同时由于最终会成环所以每个单向边都只会被访问一次
- 从某一个边开始搜索，直到成环，然后再搜下一个环
- 由于对边操作，对每个边编号，同样地，由于最后判断的是无向边，还需要记录每个单向边是属于哪个无向边之中
- 最终，只要输出每个点的1号边属于的环的大小就行

代码

#include<bits/stdc++.h>

#define pii pair<int,int>
using namespace std;
const int N = 6*202020;

vector<pii>e[N];
bool vis[N];
int fa[N];
int val[N];
pii oud[N];

int main(){
    int n;
    cin >> n;
    int tot=0;
    //建图，每个边除了记录邻接点还留一个位置记录编号
    for(int i=1;i<=n;i++){
        int ct;
        cin >> ct;
        tot+=ct;
        e[i].resize(ct);
        for(int j=0;j<ct;j++){
            cin >> e[i][j].first;
            e[i][j].second=0;
        }
    }
    //给每个边编号，同时它的反向边直接在原边的基础上加上总边数一半即可
    //开一个oud记录编号为idx的边指向的点以及这个边在终点中的编号
    //方便后续遍历环的时候使用
    int idx=0;
    tot/=2;
    for(int i=1;i<=n;i++){
        for(int j=0;j<e[i].size();j++){
            if(e[i][j].second) continue;//已经编完号了
            e[i][j].second=++idx;
            int to=e[i][j].first;
            //找反向边
            for(int k=0;k<e[to].size();k++){
                if(e[to][k].first==i){
                    e[to][k].second=tot+idx;
                    oud[idx].first=to,oud[idx].second=k;
                    oud[idx+tot].first=i,oud[idx+tot].second=j;
                }
            }
        }
    }
    //搜环，cyn记录环个数,val记录环大小，path记录当前环有哪几个边
    //用path更新大小，对应的两个单向边在模边数一半的意义下代表同一个无向边
    //用完记得清空
    int cyn=0;
    for(int i=1;i<=tot*2;i++){
        if(fa[i]) continue;
        cyn++;
        vector<int> path;
        for(int j=i;!fa[j];){
            fa[j]=cyn;
            path.push_back(j);
            int nxt=e[oud[j].first][(oud[j].second+1)%e[oud[j].first].size()].second;
            j=nxt;
        }
        int ans=0;
        for(auto j:path){
            if(!vis[j%tot]){
                vis[j%tot]=1;
                ans++;
            }
        }
        for(auto j:path){
            vis[j%tot]=0;
        }
        val[cyn]=ans;
    }
    //输出
    for(int i=1;i<=n;i++){
        int id=e[i][0].second;
        cout << val[fa[id]] << endl;
    }
}

I

题意

n段铁棒，拼成了一根铁棒，重新切开，每次切割存在消耗 $min(l_1,l_2)* \lceil log_{2}(l_1+l_2) \rceil$ 和不平衡度
要求保证不平衡度不增，且消耗最小

思路

n<=420可能是一个区间dp
每次切割都和子段价值(l,r)的结果取决于从 $[l,r]$ 中选择的分割点以及像个小区间的价值和不平衡度，小区间的平衡度不大于大区间，从满足条件的小区间转移即可
状态与转移
- 记 $dp[l][r]$ 表示(l,r)的最小价值
- $dp[l][r]=dp[l][k]+dp[k+1][r]+val[l][r]$
- 枚举len，枚举l，枚举k，枚举小区间的不平衡度，复杂度 $O(n^4)$
- 考虑优化
  - 把每个区间(l,r)中可能的价值和不平衡度都存下来
  - 算完一个区间后按不平衡度排序，然后对价值做前缀最小
  - 就能快速得到某一个不平衡度下的最小价值，然后找的过程对不平衡度二分
  - 优化至 $O(n^{3}logn)$ 可以通过
  - 优化至 $O(n)不会了$

代码

#include<bits/stdc++.h> 
#define endl '\n'
using namespace std;
#define ll long long
#define pii pair<ll,ll> 
/**
 * 区间dp
 * 从短的处理到长的
 * 满足max(短区间的不平衡度)小于等于长区间的不平衡度
 * 用一个三位数组all记录(l,r)不同切割点的代价和不平衡度
 * dp[l][r]从l到r最小代价
 * dp[l][r]=min(dp[l][k]+dp[k+1][r]+cost(l,r,k))
 * dp[i][i]=sum-2*min
 */

ll a[450];
vector<pii> all[450][450];
ll dp[450][450];
ll check(int a,int b,ll ib){
    int l=0,r=all[a][b].size()-1;
    while(l<=r){
        int m=(l+r)>>1;
        if(all[a][b][m].first>ib)
            r=m-1;
        else
            l=m+1;
    }
    if(r<0){
        //没找到
        return 2e18;
    }else{
        return all[a][b][r].second;
    }

}
bool cmp(pii a,pii b){ return a.first<b.first; }


int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    int t;
    cin >> t;
    while(t--){
        int n ;
        cin >> n;

        a[0]=0;
        memset(dp,0x3f,sizeof(dp));
        for(int i=0;i<=n;i++){
            for(int j=0;j<=n;j++){
                all[i][j].clear();
            }
        }


        for(int i=1;i<=n;i++){
            cin >> a[i];
            a[i]+=a[i-1];
            dp[i][i]=0;
            all[i][i].push_back({0,0});
        }


        for(int len=2;len<=n;len++){
            for(int l=1;l+len-1<=n;l++){
                int r=l+len-1;
                for(int k=l;k<r;k++){
                    ll llen=a[k]-a[l-1],rlen=a[r]-a[k];
                    ll ib=abs(llen-rlen);
                    ll cost=min(llen,rlen)*(ll)ceil(log2(llen+rlen));
                    cost+=check(l,k,ib);
                    cost+=check(k+1,r,ib);
                    cost=min(cost,(ll)2e18);
                    all[l][r].push_back({ib,cost});
                    dp[l][r]=min(dp[l][r],cost);
                    if(len==n) cout << (cost>=2e18?-1:cost) << ' ';
                }
                // cout << l << ' ' << r << ' ' << dp[l][r] << endl;
                sort(all[l][r].begin(),all[l][r].end(),cmp);

                //代价最小化
                for(int i=1;i<all[l][r].size();i++){
                    all[l][r][i].second=min(all[l][r][i].second,all[l][r][i-1].second);
                }
                if(len==n) cout << endl;
            }
        }
        // cout << dp[1][n] << endl;
    }
    return 0;
}

H

题意

给定长度为n的二进制串s，有q次查询，查询有两种
1. 给定(l,r)，翻转(l,r)的每一位
2. 给定(l,a,b)，计算有多少区间满足 $S_{a+x+1}=S_{b+x-1}$
$1<=n,q<=10^6$ ，第二类询问个数不超过2500

思路

朴素考虑：每次把这两段拿出来，一位位比较，复杂度 $O(nq)$
考虑优化：
- 对于第一种操作：可以使用一个flip数组记录是否翻转过了，通过标记两个点代表一个区间， $flip[i]=1$ 表明i往后都翻转过一次，标记开头和结尾+1，最后通过异或和恢复，这样子可以把第一类操作压缩到 $O(1)$
- 对于第二种操作：
  - 考虑将二进制串分块，用一个ull一次性记录64位，这样就不用一位位比较，可以直接判断两个块异或后连续0的个数。同时由于连续0可能跨块，所以还需要记录每个块的前导0和后导0个数
  - 对于一个b位的块，我们需要知道：内部0的贡献，前导0，后导0，这三个部分可以预处理出来，复杂度都是 $O(2^b)$ ，这样查询时对每一个块都可以 $O(1)$ 解决
  - 完成优化后第二种查询的复杂度为 $O(\frac{nq}{b})$
  - 同时flip也变为完整块的直接操作，不完整的异或一段前导连续1或者后导连续1来翻转
  - 最后，只剩下从某一位获取到长为b的一段数，只需要把这个位数所在块的所在位后面的部分和下一个块前面的部分拼起来就可以
注意区间角标和64到16需要进行位移

代码

#include<bits/stdc++.h>
#define endl '\n'
using namespace std;

using u64=unsigned long long;
constexpr u64 mx = (1<<16)-1;
constexpr u64 MX=ULLONG_MAX;
constexpr int B=16;
const int maxn=1e6+7;

int a[maxn];

int bk[1<<16],pre[1<<16];
u64 sum[1<<16];

void init(){
    for (int i=0; i<(1<<B); i++) {
        for (int j=0;j<16; j++) {
            if((i>>j)&1) {
                break;
            }else{
                pre[i]++;
            }
        }
        for (int j=15;j>=0;j--) {
            if(i >> j & 1) {
                break;
            }else{
                bk[i]++;
            }
        }
        int cur=0;
        for (int j=0;j<16; j++) {
            if (i>>j&1) {
                cur=0;
            }else{
                cur++;
            }
            sum[i]+=cur;
        }
    }  
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    init();
    int n,q;
    cin >> n >> q;
    std::vector<u64> a(n);
    string s;
    cin >> s;
    for(int i=0;i<n;i++){
        a[i]=s[i]-'0';
    }
    
    const int N=(n+63)/64;
    vector<u64> b(N+20);

    auto get=[&](int x){
        int pos=x/64;
        int res=x%64;
        u64 ans=0;
        ans=(b[pos]>>res)|(b[pos+1]<<(64-res));
        return ans;
    };

    for(int i=0;i<n;i++){
        b[i/64]|=(a[i]<<(i%64));
    }
    
    vector<u64> lobit(65), hibit(65);
    for(int i=0;i<64;i++){
        lobit[i+1]=lobit[i]|(1ull<<i);
        hibit[i+1]=hibit[i]|(1ull<<(63-i));
    }

    vector<int> flip(N+20);
    while(q--){
        int op;
        cin >> op;
        if(op==1){
            int l,r;
            cin >> l >> r;
            l--;r--;
            int bl=l/64,br=r/64;
            if(bl==br){//同一个块内
                b[bl]^=(lobit[r-l+1]<<(l-bl*64));
            }else{
                b[bl]^=(hibit[64-l%64]);
                b[br]^=(lobit[r%64+1]);
                flip[bl+1]^=1;
                flip[br]^=1;
            }
        }else{
            int l,x,y;
            cin >> l >> x >> y;
            x--,y--;
            //处理之前的翻转
            int v=0;
            for(int i=0;i<N;i++){
                v^=flip[i];
                if(v){
                    b[i]^=MX;
                }
                flip[i]=0;
            }
            //计算结果
            u64 ans=0;
            u64 cur=0;
            int len=l/64;
            int res=l%64;
            for(int i=0;i<len;i++){
                u64 u=get(x)^get(y);
                for(int i=0;i<4;i++){
                    u64 now=u&mx;
                    ans+=sum[now]+1ull*cur*pre[now];
                    if (bk[now] == 16) {
                        cur+=16;
                    } else {
                        cur=bk[now];
                    }
                    u>>=16;
                }
                x+=64,y+=64;
            }
            if(res){
                u64 u=get(x)^get(y);
                for(int i=0;i<res;i++){
                    if(u>>i&1) cur=0;
                    else cur++;
                    ans+=cur;
                }
            }
            cout << ans << endl;
        }
    }
    return 0;
}

牛客多校01

G

题意

思路

代码

E

题意

思路

代码

L

题意

思路

代码

K

题意

思路

代码

I

题意

思路

代码

H

题意

思路

代码