Y2期末测试

总结：

本次模拟未达到目标，第一题做题时间太长了，随后又在第二题上浪费时间，导致后面的题都没来及看，一二题是思维题，后面的题也没想到有什么好的算法，还是要多练

题目

1.划分区间

主要是一个找规律的题，找到第一个r的位置和最后一个l的位置，在这之间的都不可行，其余的都可行，随后考虑全是l或全是r的输入，就可以了，当时想复杂了，导致做了很长时间

2.序列操作

题目描述：

给定一个长度为 n 的序列 a，然后进行 q 次操作 ，然后打印次操 q 作后序列最小值的位置。
操作一：输入方式为1 l r，表示将序列[l,r] 区间的全部元素全部升序排列。
操作二：输入方式为2 l r，表示将序列 [l,r] 区间的全部元素全部降序排列。
操作三：输入方式为3 l r，表示将序列 [l,r] 区间的全部元素进行翻转。
操作四：输入方式为4 l r k，表示将序列 [l,r] 区间的全部元素按照swap(a[i],a[i+k])规则进行交换
保证 r+k≤n,1≤k并且最终答案唯一，即序列中不存在相同元素。
输入T组数据
1≤T≤10,1≤n,q≤2×1e5
1≤a​i​​ ≤1e9
​​输入：
1
6 5
1 2 3 4 5 6
2 1 4
1 2 3
3 2 4
4 1 3 2
4 1 2 3
输出：
1

题解：

这个题主要还是找规律。可以先将数列里最小值的位置找到，设最小值的位置为ans，在操作一中，从小到大排序，可以看做ans=l，在操作二中，从大到小排序，可以看做ans=r，在操作三中，翻转操作，可以看做ans=l+r-ans,那么在操作四中，就要分类讨论，具体看代码详解。

代码：

#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
const int maxn=2e6+10;
int a[maxn],mn=INT_MAX;
int main(){
	int t;
	cin>>t;
	while(t--){
		int n,q,ans;
		cin>>n>>q;
		for(int i=1;i<=n;i++){
			cin>>a[i];
			if(mn>a[i]){
				mn=a[i];
				ans=i;
			}
		}
		while(q--){
			int x;
			cin>>x;
			if(x==1){
				int l,r;
				cin>>l>>r;
				if(l<=ans&&ans<=r) ans=l;
			}
			if(x==2){
				int l,r;
				cin>>l>>r;
				if(l<=ans&&ans<=r) ans=r;
			}
			if(x==3){
				int l,r;
				cin>>l>>r;
				if(l<=ans&&ans<=r) ans=l+r-ans;
			}
			if(x==4){
				int l,r,k;
				cin>>l>>r>>k;
				if(k<=r-l){
					if(l<=ans&&ans<l+k){
						int t=(int)((r-ans+k)/k);
						ans+=k*t;
					}
					else if(l+k<=ans&&ans<=r+k) ans-=k;
				}
				if(k>=r-l+1){
					if(l<=ans&&ans<=r) ans+=k;
					else if(l+k<=ans&&ans<=r+k) ans-=k;
					continue;
				}
			}
		}
		cout<<ans<<"\n";
		mn=INT_MAX;
	}
	return 0;
}

3.划分区间

题目描述：

给定一个包含n个区间的集合 S，请你将 S 划分为一个或多个区间组，每个区间属于且仅属于一个区间组内， 同一个区间组内的任意两个区间不相交。区间相交指两个区间无重叠部分。例如区间 [2, 4] 与区间 [3, 5] 是重叠的，区间 [2, 3] 与区间 [4, 5] 是不重叠的。请问集合 S 最少可以划分为多少区间组？
输入：
5
5 10
6 8
1 5
2 3
1 10
输出：
3

题解：

本题我们考虑贪心的策略，尽量让靠得近的两个区间为一个组。首先将所有区间按左端点排序，第一个区间分一个组，随后我们比较下一个的区间，如果下一个的区间的左端点大于某个组的最大右端点，我们就把他放进这个组里，更新这个组的最大右端，如果找遍所有组都没有合适的，哪个我们就把它自成一个组，最终答案就是组的数量。

代码：

#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
const int maxn=1e6+10;
struct aaa{
	int x,y;
}s[maxn];
bool cmp(aaa a,aaa b){
	return a.x<b.x;
}
int f[maxn];
int main(){
	int n;
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>s[i].x>>s[i].y;
	}
	sort(s+1,s+n+1,cmp);
	int ans=0;
	ans++;
	f[ans]=s[1].y;
	for(int i=2;i<=n;i++){
		bool flag=false;
		for(int j=1;j<=ans;j++){
			if(s[i].x>f[j]){
				flag=true;
				f[j]=s[i].y;
				break;
			}
		}
		if(flag==false){
			ans++;
			f[ans]=s[i].y;
		}
	}
	cout<<ans<<"\n";
	return 0;
}

4.数字匹配

题目描述：

给定 m 个长度为 n 且仅有0和1构成的字符串构成集合 S，集合 S 可能有重复，再给定一个长度为 n 的整数序列 w。关于两个字符串 s、t 匹配方案的定义如下所示：
1：设字符串 s 的各位字符从左到右依次为 s1 到 s​n​​ 。
2：设字符串 t 的各位字符从左到右依次为 t​1到tn​​ 。
3：定义两个字符串的匹配收益为 V，且初始时 V=0。
4：对于所有 i(1≤i≤n)，如果 s​i​​ =t​i​​ ，则 V 加上 w​i​​ 。
现在，给出 q 个询问，每个询问包含一个长度为 n 的 01 字符串 t 以及一个整数 k，具体询问内容为：请你计算并输出集合 S 中有多少个元素满足，与给定字符串 t 的匹配价值不大于 k。
注意，如果集合中多个相同的元素均满足询问条件，则每个元素均应被计数。
输入：

题解：

可以考虑二进制的转换，将01串当成二进制转化为整数，随后可以做预处理，即提前就加好，
随后做前缀和，输出。

代码：

#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
int a[15];
char str[15];
int cnt[5000];
int f[5000][110];
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int n,m,q;
	cin>>n>>m>>q;
	for(int i=0;i<n;i++) cin>>a[n-i-1];
	while(m--){
		cin>>str;	
	    int s=0;
	    for(int i=0;i<n;i++){
	    	if(str[i]=='1') s=s*2+1;
	    	else s*=2;
		}
		cnt[s]++;
	}
	for(int i=0;i<1<<n;i++){
		if(cnt[i]==0) continue;
		for(int j=0;j<1<<n;j++){
			int sum=0,s=i^j;
			for(int k=0;k<n;k++){
				if((s>>k&1)==0) sum+=a[k];
			}
			if(sum<=100) f[j][sum]+=cnt[i];
		}
	}
	for(int i=0;i<1<<n;i++){
		for(int j=1;j<=100;j++){
			f[i][j]+=f[i][j-1];
		}
	}
    while(q--){
    	int k;
    	cin>>str>>k;
    	int s=0;
	    for(int i=0;i<n;i++){
	    	if(str[i]=='1') s=s*2+1;
	    	else s*=2;
		}
		cout<<f[s][k]<<"\n";
	} 
	return 0;
}