AcWing 打卡记录day 7

108. 奇数码问题
因为之前ysj写九宫格的时候就说过这个事情，怎么判断是否有解。是根据逆序对来求。
不过九宫格的答案是固定的，这个题目的结束态是他给你的。

这里就涉及了一个结论。
因为n一定是个奇数。所以你向上或者向下移动，相当于在一个一维数组中，前进或者后退了n-1位。
n-1一定是个偶数，假设你这n-1个数中， 有a个比你大，b个比你小。a+b=n-1 ，即a+b是偶数。
假如你后退n-1位，那么你一开始对这个区间逆序对的影响是a，后退完后对这个区间的影响是b。
那么你对整个数组的影响就是 b-a,而b-a一定是个偶数，一个数加减一个偶数奇偶性不变。
前进同理。
所以这个问题就转换成了，初始态和结果态的逆序对的奇偶性是否一致。

同样是树状数组求逆序对。

#include 

using namespace std;
#define ll long long
#define endl 'n'
const ll inf = 0x3f3f3f3f;
const ll MAXN = 3e5 + 10;
ll n, m, T;
ll flag;

ll t[MAXN];
ll lowbit(ll i) {
	return (i)&(-i);
}
ll getsum(ll x) {
	ll sum = 0;
	for (ll i = x; i; i -= lowbit(i)) {
		sum += t[i];
	}
	return sum;
}

void update(ll x) {
	for (ll i = x; i <=n*n; i += lowbit(i)) {
		t[i] ++;
	}
}
int main()
{
	std::ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	while (cin >> n) {
		ll num1=0,num2=0;
		ll a;
		for (ll i = 0; i < n*n; i++) {
			cin>>a;
			if(a){
				num1+=getsum(n*n)-getsum(a);
				// num1=num1%2;
				update(a);
			}
		}
		memset(t,0,sizeof(t));
		
		for (ll i = 0; i < n*n; i++) {
			cin>>a;
			if(a){
				num2+=getsum(n*n)-getsum(a);
				// num2=num2%2;
				update(a);
			}
		}
// 		cout< 
110. 防晒
 贪心，就是每头牛从大到小找到合适的防晒霜即可。
 匈牙利算法
 
#include 

using namespace std;
#define ll long long
#define endl 'n'
const int inf=0x3f3f3f3f;
const int MAXN=1e5+10;
int n,m,T;
int flag; 

struct cows{
	int minn,maxn;
};

struct node{
	int pow,num;
};

cows a[3005];
node b[3005];

bool cmp1(cows x,cows y){
	if(x.minn==y.minn){
		return x.maxn>y.maxn;
	}
	return x.minn>y.minn;
}

bool cmp2(node x,node y){
	return x.pow>y.pow;
}
int main() 
{
	std::ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		cin>>a[i].minn>>a[i].maxn;
	}
	for(int i=1;i<=m;i++){
		cin>>b[i].pow>>b[i].num;
	}
	sort(a+1,a+1+n,cmp1);
	sort(b+1,b+1+m,cmp2);
	int cnt=1;
	int num=0;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			if(a[i].minn<=b[j].pow&&a[i].maxn>=b[j].pow&&b[j].num){
				b[j].num--;
				num++;
				break;
			}
		}
	}
	cout< 
111. 畜栏预定
 一开始看完题目，看到是第一个是求最少需要多少个畜栏。想着直接差分就求出来了。
 然后看到后面要分配给每头牛畜栏，就迷了。
 其实就是 ，你先根据 每头牛的开始吃的时间排序，然后一个一个的放进优先队列里面，
 优先队列里面是根据牛吃完的时间升序排序的，因为无论你什么时候开始吃，当你开始吃之后，我们就只关心你什么时候吃完了。当下一头牛放进去的时候，如果最快吃完的牛还没有吃完，就说明畜栏不够用了，得加一个，然后分给现在要放进来的牛，如果吃完了，那么吃完的牛的这个畜栏就可以分配给现在要进来的牛用。
 全模拟一遍即可分配完。
 
#include 

using namespace std;
#define ll long long
#define endl 'n'
const int inf=0x3f3f3f3f;
const int MAXN=1e5+10;
int n,m,T;
int flag; 

struct node{
	int l,r;
	int set;
	bool operator<(const node &x)const{
		if(r==x.r){
			return l>x.l;
		}
		return r>x.r;
	}
};
node a[MAXN];
int d[1001000];

bool cmp(node x,node y){
	if(x.l==y.l){
		return x.r>n;
	int maxn=0;
	for(int i=1;i<=n;i++){
		cin>>a[i].l>>a[i].r;
		a[i].set=i;
		maxn=max(maxn,a[i].r);
		d[a[i].l]++;
		d[a[i].r+1]--;
	}
	int minn=0;
	for(int i=1;i<=maxn;i++){
		d[i]+=d[i-1];
		minn=max(minn,d[i]);
	}
	cout<q;
	int ans[MAXN];
	for(int i=1;i<=n;i++){
		if(!q.empty()&&q.top().r