Day7

T1

题目：

给你一个括号序列，统计最少需要有多少个括号换位置才能使得这个序列合法？

思路：

统计一下有多少个右括号找不到左括号即可。

代码：

#include<bits/stdc++.h>
using namespace std;
int T;
int n;
string s;
void solve(){
    cin >> n; 
    cin >> s;
    int cnt = 0;
    stack<char> st;
    for(int i = 0;i < s.size();i++) {
        if(s[i] == '(') st.push(s[i]);
        else {
            if( st.empty() ) {
                cnt ++;
            } else {
                st.pop();
            }
        }
    }
    cout<<cnt<<"\n";
}
int main() {
    cin >> T;
    while(T--)solve(); 
    return 0;
} 

T2:

题目:

给定一个区间[l,r],你可以从数组中删除若干元素。求最少删除多少个元素，才能使剩余所有元素的按位与结果不为 0。

思路：

将一些数字&起来，只有存在一个二进制位都是1才能才能保证结果不为0.所以，我们可以枚举[l,r]中要保留哪一位。保留的这个位一定是所有数中有1的数最多的那一位。

所以我们可以求一个前缀数组p[30][200005]，p[b][i]表示第i个数字及以前的所有数字的第b位有1的数字的数量，预处理出来，询问的时候再枚举每一个二进制位即可。

代码：

/*
0010 0011 0100 0101 0110 0111 1000
2*10^5->2^20
对于[l,r]中的数每一位
b[i]描述第i位的1的数量。
1的数量最多者即为答案。
预处理出b[1~2*10^5][30]即可，再用前缀和.
*/
#include <bits/stdc++.h>
using namespace std;
int T;
long long b[50][200005];
void solve() {
    int l,r;
    cin >> l >> r;
    long long ans = -1;
    for(int i = 1;i <= 30; i++) {
        long long tmp = b[i][r]-b[i][l-1];
        if(tmp > ans) ans = tmp;
    }
    ans = (r-l+1) - ans;
    cout << ans << "\n";
}
int main() {
    for(int i = 1;i <= 200000;i++){
        int x = i;
        int p = 1;
        while(x) {
            b[p][i] = (x&1) + b[p][i-1];
            p ++;
            x = x>>1;
        }
    }
    cin >> T;
    while(T--) solve();
    return 0;
}

T3:

题目：

给定一个长度为n的数组a

f(l,r)为将a[l]~a[r]中的所有数 按位与 起来的值给定l,k,找出满足l<=r<=n且f(l,r)>=k的最大的r.

思路：

f(l,r)越长越小，具有单调递减的性质。

暴力：求一个数组f[l][r]，每次查询的时候查找即可。O(n^2+q*log n)

优化思路：

可以用st[b][i]维护从i开始，长度为2^b的这一段的区间按位与的结果。

查询：l<=r<=n且f(l,r)>=k的最大的r可以二分这个r,因为越长的区间的区间按位与越小。用st表的公式，然后收缩区间。

#include<bits/stdc++.h>
using namespace std;
int T;
int n,a[200005];
int f[30][200005];
int Log2[200005];
int l,k;
void solve() {
    cin >> n;
    for(int i = 1;i <= n;i ++)scanf("%d",a+i);
    for(int i = 1;i <= n;i ++)f[0][i] = a[i];
    for(int b = 1;(1<<b) <= n;b ++) {
        for(int i = 1;i+(1<<b) <= n+1;i ++) {
            f[b][i] = f[b-1][i] & f[b-1][i + (1<<(b-1))];
        }
    }
    int q;
    cin >> q;
    while(q--) {
        scanf("%d%d",&l,&k);
        if(a[l]<k) {
            cout << -1 << " ";
            continue;
        } 
        int i = l, j = n,mid;
        while(i<j){
            mid = (i+j+1)/2;
            int b = Log2[mid-l+1];
            int tmp = 
                f[b][l]&f[b][mid-(1<<b)+1];
            if(tmp < k) j=mid-1;
            else i = mid;
        }
        printf("%d ",i);
    }
    puts("");
}
int main() {
    Log2[0]=-1;
    for(int i = 1;i <= 200000;i ++)Log2[i]=Log2[i/2]+1;
    cin >> T;
    while(T--) solve();    
    return 0;
}

T4:

题目：

给定一个长度为n的整数数组a,现在要求你把这个整数数组分成三个非空连续部分，使得这三个部分的和相同。

思路：

求一个sum0为整个数组的和。如果sum0不能被3整除，则0.如果n<=3,则0。

求一个前缀和p.

设我们的分割点一个是i,一个是j.

p[i]=p[j]-p[i-1]=p[n]-p[j-1]

通过观察，可以发现满足条件的p[i]应为sum0/3,p[j]应为sum0/3*2。

#include<bits/stdc++.h>
using namespace std;
int n;
long long sum=0;
int a[500005];
long long pre[500005];
long long l[500005],r[500005];
long long ans=0;
int main() {
    cin >> n;
    for(int i = 1;i <= n;i ++) {
        cin >> a[i];
        sum += a[i];
        pre[i] = pre[i-1] + a[i];
    }
    if(sum%3 != 0) {
        cout << 0;
        return 0;
    }
    sum = sum/3;
    if(n<=2){
        cout<<0;
        return 0;
    }
    int cntl=0;
    for(int i=1;i<=n-1;i++){
        if(pre[i]==2*sum)ans+=cntl;
        if(pre[i]==sum)cntl++;
    }
    cout << ans;
    return 0;
}

T5

题目：

在长度为n的数组中选择m个数，设他们的下标为b[0]~b[m-1],对于每个0<=p<m-1都满足

$a_{b_p} \oplus b_{p+1} < a_{b_{p+1}} \oplus b_p,$

暴力的话会超时。这时我们发现a[i]不会超过2^8次方.

所以观察选择的两个下标i,j,假设i>j,仅当i和j的差距不超过256的时候才有可能满足以上条件。所以j不能超过i+256

代码：

#include<bits/stdc++.h>
using namespace std;
int T;
int n;
int a[300005];
int dp[300005];
void solve() {
	cin >> n;
	memset(dp,0,sizeof dp);
	for(int i = 1;i <= n;i ++) {
		dp[i]=1;
        cin >> a[i];
    }
	for(int i = 1;i <= n;i ++) {
		for(int j = i;j <= min(n,i+512);j ++) {
			if((a[i]^(j-1))<(a[j]^(i-1))) {
				dp[j] = max(dp[j],dp[i]+1);
			}
		} 
	}
	int ans = 0;
	for(int i = 1;i <= n;i ++) ans = max(ans,dp[i]);
	cout << ans << "\n"; 
}
int main() {
	cin >> T;
	while(T--) solve();
	return 0;
}

T6

题目：

给定首歌曲，每首歌有两个属性：流派和作者。

• 允许删除任意歌曲，然后对剩余歌曲任意排序。
• 若排序后，任意相邻两首歌满足 作者相同 或 流派相同，则称该序列为“精彩的”。

思路：

根据n<=16可知这道题可以用状态压缩DP来写。

定义dp[20][2^18],dp[i][mask]表示当前状态为mask的时候且最后一首歌是i的时候是否可以构成一个美丽的歌单。

代码

#include<bits/stdc++.h>
using namespace std;
int T;
int n;
bool dp[20][500005];
struct node{
    string g,w;
}song[20];
struct node1{
    int g,w;
}s[20];
void solve(){
    memset(dp,0,sizeof dp);
    memset(s,0,sizeof s);
    cin >> n;
    map<string,int> mp1,mp2;
    int cnt1 = 1,cnt2 = 1;
    for(int i = 1;i <= n;i ++) {
        cin >> song[i].g >> song[i].w;
         if(mp1.find(song[i].g) == mp1.end()) {
             mp1[song[i].g] = cnt1;
             cnt1 ++; 
        }
        if(mp2.find(song[i].w) == mp2.end()) {
            mp2[song[i].w] = cnt2;
            cnt2 ++;
        }
        s[i].g = mp1[song[i].g];
        s[i].w = mp2[song[i].w];
    }
    for(int i = 1;i <= n;i ++) dp[i][1<<i] = true;
    for(int mask = 0;mask < (1<<(n+1));mask ++) {
        for(int j = 1;j <= n;j ++){
            if(~mask & (1<<j)) 
                continue;
            if(!dp[j][mask]) continue;
            for(int i = 1;i <= n;i ++){
                if(mask & (1<<i)) 
                    continue;
                if(s[j].g == s[i].g || s[j].w == s[i].w) 
                    dp[i][mask | (1<<i)] = true;
            }
        }
    }
    int ans = 0;
    for(int mask = 0;mask < (1<<(n+1));mask ++) {
        for(int i = 1;i <= n;i ++) {
            if(dp[i][mask]) {
                int cnt = 0;    
                int m = mask;
                while(m) {
                    if(m & 1) cnt ++;
                    m>>=1;
                }
                ans = max(ans,cnt);
            }
        }
    }
    cout << n-ans << "\n";
}
int main() {
    cin >> T;
    while(T--) solve();
    return 0;
}