周三_刷题班2_COPY版本

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+10;
bool cmp(string s1,string s2){
	return s1>s2;
}
//先按x从小到大，如果x相同，就按y从小到大，如果y还相同，就保持木块在地面时的先后顺序不变
bool cmp2(st s1,st s2){
	if(s1.x!=s2.x){
		return s1.x<s2.x;
	}
	if(s1.y!=s2.y){
		return s1.y<s2.y;
	}
	return s1.id<s2.id;
}
//先按y从小到大，如果y相同，就按x从小到大，如果x还相同，就保持木块在地面时的先后顺序不变
bool cmp3(st s1,st s2){
	if(s1.y!=s2.y){
		return s1.y<s2.y;
	}
	if(s1.x!=s2.x){
		return s1.x<s2.x;
	}
	return s1.id<s2.id;
}
struct st{
	int id,x,y;//id是这个物品的编号或者说位置
};
st s[100010];
int main(){
	//problem F
	//先给数组排序，排序不影响结果
	//对于每一次查询L和R，查找大于等于L第一次出现的位置，假设是p1
	//查找小于等于R 最后一次出现的位置，假设是p2 
	//那么这次查询的答案  就是 p2-p1+1;
	//  1 1 1 1 1 1 1 1 2 2 2 2 2 2 2 3 3 3 3 3 3 4 5 6
	//problem E
	// r[i]: 记录以第i个数字 结尾  有多少个连续的范围  总和是7的倍数
	// b[i]: 记录前缀和当中  取模于7的结果 等于i的 有多少个
	//problem A
	int  x,y;
	cin>>x>>y;
	int((1.0*x/y  - x/y)*10);
	//problem B  操作很多次，每次会把数组L到R这段范围的数字 后移一个位置
	int n,a[10010],m,l,r;
	cin>>n;
	for(int i=1;i<=n;i++) cin>>a[i];
	cin>>m;
	while(m--){
		cin>>l>>r;
		int tem=a[r];
		//i=r-1
		for(int i=r-1;i>=l;i--) a[i+1]=a[i];
		a[l]=tem;
	}
	for(int i=1;i<=n;i++) cout<<a[i]<<" ";
	//problem C
	int n;
	string s[6010];
	cin>>n;
	for(int i=1;i<=n;i++) {
		cin>>s[i];
		s[i]=s[i].substr(0,3);
	}
	sort(s+1,s+1+n);
	cout<<s[n]<<s[n-1];
	//problem D
	int n;
	cin>>n;
	for(int i=1;i<=n;i++){
		s[i].id=i;
		cin>>s[i].x>>s[i].y;
	}
	sort(s+1,s+1+n,cmp2);
	for(int i=1;i<=n;i++) cout<<s[i].id<<" ";
	cout<<endl;
	sort(s+1,s+1+n,cmp3);
	for(int i=1;i<=n;i++) cout<<s[i].id<<" ";

}

小迪老师笔记：
A. 盗墓 7 
abs(x - y) % 10
(x + y) / 10 % 10
(x * y) / 100 % 10
(int)(10.0 * x / y) % 10

B. 盗墓 1
l = 2  r = 4
a[l] ... a[r] 向右移动一个格子 
a[2] ... a[4]
a[2] -> a[3]
a[3] -> a[4]
a[j] -> a[j + 1]:a[j + 1] = a[j]
a[r] -> a[l](特殊处理) 

C. 盗墓 2
abcdefghij
xyzkkxxxkx
xbcfzibaoejab
枚举所有组合(超时)： 
abcxyz
abcxbc
xbcabc
xyzabc
xbcxyz
xyzxbc
正解：贪心，按照字典序排序，取字典序最大的 2 个

D. 盗墓 3
bool cmp1(mk a, mk b) {
	if (a.x != b.x) return a.x < b.x;
	if (a.y != b.y) return a.y < b.y;
	return a.shunxu < b.shunxu;
}
bool cmp2(mk a, mk b) {
	if (a.y != b.y) return a.y < b.y;
	if (a.x != b.x) return a.x < b.x;
	return a.shunxu < b.shunxu;
}

E. 盗墓 9
(s[r] - s[l - 1]) % 7 == 0
s[r] % 7 - s[l - 1] % 7 == 0
s[r] % 7 == s[l - 1] % 7
1、b[0]++ 需要特殊处理
2、每次计算前缀和 s
3、统计前面有多少个和 s % 7 相同
4、b[s % 7]++ 

F. 道路监控
暴力枚举：a[1] ... a[n] 有多少个 a[i] >= l && a[i] <= r
满分解法：二分 
查找第一个大于等于 l -> 下标为 p1
查找最后一个小于等于 r -> 下表为 p2 
累加 p2 - p1 + 1
需要特判查找不到的情况，p1 或 p2 为 -1 的情况时不用累加