8.9 字符串中的位运算

今天的题目简单，很简单。。。（第五题光是推公式的时间就比做前三道题加起来的时间还长，第六题没时间做了） 1 Move brackets（签到题）{ 1. 题意：有一个字符串，其中有一半是左括号，一半是右括号，你可以将字符串中的任意一个括号删除并重新添加到末尾，求最少进行多少次操作才能使原串合法 2. 思路：这题如果只要判断合法的话非常简单，只需要扫描一遍字符

潘政勋发布于 2026-8-9 16:23:22 · 已更新

综合/学习笔记

今天的题目简单，很简单。。。（第五题光是推公式的时间就比做前三道题加起来的时间还长，第六题没时间做了）

1 Move brackets（签到题）{

题意：有一个字符串，其中有一半是左括号，一半是右括号，你可以将字符串中的任意一个括号删除并重新添加到末尾，求最少进行多少次操作才能使原串合法
思路：这题如果只要判断合法的话非常简单，只需要扫描一遍字符串，如果遇到左括号那么cnt++,反之则cnt--，如果cnt小于等于0则需要一次这样的操作

}

水题，直接上代码：

#include <bits/stdc++.h>
using namespace std;
int main(){
    int t;
    cin>>t;
    while(t--){
        int len; cin >> len;
        string s;
        cin >> s;
        int cnt=0,ans=0;
        for(int i=0;i<len;i++){
            if(s[i]=='('){//如果为左括号
                cnt++;
            }
            else{
                if(cnt>0) cnt--;
                else ans++;//没法匹配了
            }
        }
        cout<<ans<<endl;
    }
}

2 And it’s Non-zero{

题意：给定一组区间，你可以对区间内的所有元素进行位与求值，求最少需要删除给定区间内的多少个元素才能使最后的位与和严格大于0
思路：不难发现只要两个数的二进制中在同一位上都是1，那么最终结果一定大于0。肯定也能想到我们需要在区间内找到同一位上都是1的最大数，因此我们可以预处理前缀和。因为这题区间最大到2e5，因此我们可以只枚举0到20位，然后再在所有数里统计为1的位的个数，最后计算答案时，枚举每个位数，并求出所在区间内的数在第j位上为1的个数，求出最大的ans,就可以求出我们最少需要删除多少数
算法：前缀和 O(20*(区间长度))

}

#include <bits/stdc++.h>
using namespace std;
const int N=2e5+10;
const int M=20;
int pre[N+1][M+1];
int main(){
    int t;
    cin >> t;
    for(int i=1;i<=N;i++){
        for(int j=0;j<M;j++){
            pre[i][j]=pre[i-1][j];
            if(i&(1<<j)){
                pre[i][j]++;//预处理所有可行范围内所有数二进制上1的个数
            }
        }
    }
    while(t--){
        int l,r;
        cin >> l >> r;
        int len=r-l+1;
        int ans=1e9;
        for(int j=0;j<M;j++){
            int cnt=pre[r][j]-pre[l-1][j];//区间内第j位为1的数的个数
            int lemax=len-cnt;
            ans=min(ans,lemax);
        }
        cout<<ans<<endl;
    }
}

3 Iva & Pav{

题意：有一个数组a，规定函数f(l,r)=(a[l]&a[l+1]&...&a[r]),现给出区间的l,求一个最大的r,使得f(l,r)>=k，k会在题目中给出
思路：这题的数组范围很大，高达2e5,而如果查询次数过多的话会导致每次查询的时间复杂度接近O(n),我们显然不能接受如此高的复杂度。因此我们可以使用ST表来存储每个可分割的区间内的位与值，对于每次查询，我们可以利用二分查询区间内的位与值，不断查找最大右端点，只要还能够大于k就一直向右移，否则向左移
算法：ST表，二分

}

#include <bits/stdc++.h>
using namespace std;
const int N=2e5+10;
const int LOG=20;
int a[N];
int st[N][LOG];
int lg[N];
int query(int l, int r) {
    int k=lg[r-l+1];
    return st[l][k] & st[r-(1<<k)+1][k];
}
int main() {
    lg[1]=0;
    for (int i=2;i<N;i++) {
        lg[i]=lg[i/2]+1;
    }
    int T;
    cin >> T;
    while (T--) {
        int n;
        cin >> n;
        for (int i=1;i<=n;i++) {
            cin >> a[i];
            st[i][0]=a[i];
        }
        for (int j=1;(1<<j)<=n;j++) {//st表快速查询
            for (int i=1;i+(1<<j)-1<=n;i++) {
                st[i][j]=st[i][j-1] & st[i+(1<<(j-1))][j-1];
            }
        }
        int q;
        cin >> q;
        while (q--) {
            int l,k;
            cin >> l >> k;
            if (a[l]<k) {
                cout<<-1<<' ';
                continue;
            }
            int low=l,high=n,ans=l;
            while (low<=high) {//二分答案
                int mid=(low+high)/2;
                if (query(l,mid)>=k) {
                    ans=mid;
                    low=mid+1; 
                } else {
                    high=mid-1;
                }
            }
            cout<<ans<<' ';
        }
        cout<<endl;
    }
    return 0;
}

4 Number of Ways{
1.题意：有一个数组，现让你给数组划分成三段，使得这三段中的元素和相等。输出方案数，如果没有合法分割方案输出0

思路：因为这题划分的三段中的元素和都相等，我们可以理解为这个数组中的元素和可以被3整除，因此我们可以预处理前缀和，在遍历整个数组的过程中，如果发现此时的前缀和刚好等于所有元素和的1/3，那么cnt++,如果刚好等于原来元素和的两倍那么也就意味着前面的所有分割情况都由cnt决定，ans+=cnt加入答案，最后输出ans

3.算法：前缀和

}

核心代码：

 long long tr=pre[n]/3;//对原数组每一段的分割值
    long long pref=0,cnt=0,ans=0;
    for(int i=1;i<=n-1;i++){
        pref+=a[i];
        if(pref==2*tr){//刚好能分割两段
            ans+=cnt;
        }
        if(pref==tr){
            cnt++;
        }
    }

5 XOR Subsequence{

题意：有一个数组，选择一组递增的下标b[1]<b[2]<...<b[r]<b[n].现在规定如果一个数组的子序列满足a[b[l]]^a[b[l+1]]<a[b[l+1]]^a[b[l]],那么称这个子序列为美丽子序列，现让你求最长的美丽子序列的长度
思路：看到最长子序列我们就很容易想到最长上升子序列，也就是线性DP的模型，但是这题只用最长上升子序列的模型来做显然会超时，每次的查找都是O(n^2).因此我们需要对原来的公式进行简化。

因为子序列中的b[l]和b[l+1]实际上就是a[l]和a[l+1],因此我们可以简化原式编程：a[l]^(l+1)<a[l+1]^l.这就是解决这题的根本。

之后只需要无脑写一遍DP并运用这个公式判断答案是否合法即可

算法：线性DP，位运算

}

核心代码：

    for(int i=0;i<n;i++){//异或结果最多受前8位影响
             int st=max(0,i-256);
             for(int j=st;j<i;j++){//i+1
                if((num[j]^i)<(num[i]^j)){//对应题目公式
                    dp[i]=max(dp[i],dp[j]+1);
                }
             }
             ans=max(ans,dp[i]);
        }

6 Shuffling songs{

题意：有一组歌单，其中包含歌单的作者和流派，我们规定：如果两首歌之间存在相同的作者或流派，我们就称这两首歌互为“精彩歌单”。求最少删除多少首歌才能使数组内的所有歌都两两互为精彩歌单
思路：因为这题的n的范围最多只到16，因此我们可以试着（暴力）状压。我们定义一个bool数组dp，表示此歌是否能成为精彩歌单。第一维mask,表示当前歌单的状态，1表示有几首歌参与选择。i,表示当前歌单中的最后一首歌能否被选择。因此我们要在最后计算所有合法歌单中的1最多有多少，这样我们用歌曲总数减去最多要保留的歌曲数就是最少删除的歌曲数
状态转移：

If(dp[mask][i]){ dp[mask|(1<<nxt)][nxt]=true }(如果这个状态能够被选择，那么将当前状态mask与此时的nxt进行合并，并标记为true)

AC代码：

#include <bits/stdc++.h>
using namespace std;
int main(){
     int t;
     cin >> t;
     while(t--){
        int n;
        cin >> n;
        vector<string> s(n),h(n);
        vector<vector<bool>> can(n,vector<bool>(n,false));
        for(int i=0;i<n;i++){
            cin >> s[i] >> h[i];
        }
        vector<vector<bool>> dp(1<<n,vector<bool>(n,false));
        for(int i=0;i<n;i++) dp[(1<<i)][i]=true;
        for(int i=0;i<n;i++){
            for(int j=i+1;j<n;j++){
                if(s[i]==s[j]||h[i]==h[j]){
                    can[i][j]=can[j][i]=true;//标记合法情况
                }
            }
        }
        for(int mask=0;mask<(1<<n);mask++){
          for(int i=0;i<n;i++){
            if(!dp[mask][i]) continue;
            for(int nxt=0;nxt<n;nxt++){
                if(!can[i][nxt]) continue;//不能成为合法歌单
                if(mask&(1<<nxt)) continue;//不为1
                    dp[mask|(1<<nxt)][nxt]=true;//1表示能成为合法歌单
        }
        }
        }
        int ans=0;
        for(int mask=0;mask<(1<<n);mask++){
            for(int i=0;i<n;i++){
                if(dp[mask][i]){
                    ans=max(ans,__builtin_popcount(mask));//记录彼此能成为精彩歌单的最大值
                    break;
                }
            }
        }
         cout<<n-ans<<endl;//总数减去最大数就是最少删除的数量
     }
}

7 traveler’s problem(附加题){

题意：有n个城市，你必须从1号城市游览完n个城市之后回到1号城市，每个城市之间都有其对应的花费，求最少花费
思路：这题是哈密顿路径模型的其中之一：由0到n再到0。主要做法是状压，因为这题数据同样不超过20，时间复杂度为O(2^n*n^2)

我们令dp[mask]为当前已到城市的的状态，并先初始化为0，最后我们希望mask的二进制位数中全为1。dp[i]表示当前到达的最后一座城市的花费，枚举每一个后来的城市j,如果(mask&(1<<j))表示如果j已访问过，continue,如果(dp[mask][i]),表示如果当前状态不可达，continue最后的状态转移：dp[mask|(1<<j)][j]=min(dp[mask|(1<<j)][j],dp[mask][i]+wei[i][j])( Wei表示当前城市到第j个城市的花费，整个式子表示将当前状态与目前可达的第j个城市进行合并，然后将原先花费加上去往第j个城市的花费，最后取min得到花费最小值

算法：状态压缩

}

核心代码：

for(int mask=0;mask<(1<<n);mask++){
        for(int i=0;i<n;i++){
            if(dp[mask][i]==1e10) continue;//状态不可达
            for(int j=0;j<n;j++){
                if(mask&(1<<j)) continue;//j已访问
                int nxt=mask|(1<<j);
                dp[nxt][j]=min(dp[nxt][j],dp[mask][i]+wei[i][j]);
            }
        }
     }

今天的题目简单，很简单。。。（第五题光是推公式的时间就比做前三道题加起来的时间还长，第六题没时间做了）

评论

还没有账户？

登录