又是四校联考，ysy出的题……

1. 蛤布斯有$n$种商品，第$i$种物品的价格为$a_i$，价值为$b_i$。有$m$个人来向蛤布斯购买商品，每个人每种物品只能购买一个。第$j$个人有$c_j$的钱，他会不停选择一个能买得起的价格最高的商品买走（如果有多个则选择价值最高的）。你需要求出每个人购买的物品的价值和。

$n, m \leq 100000, 1 \leq a_i, b_i, c_j \leq 10^{12}$

【题解】

排序后，二分当前的钱所能买到的最高的价格的东西，再二分能买连续多少的一段，就能操作了，可以证明最多操作$log_2n$次，所以复杂度$O(mlog^2n)$。

# include <stdio.h>
# include <algorithm>
# include <cassert>
typedef long long ll;
# include <vector>
# define pll pair<ll,ll>
# define MP make_pair
using namespace std;

int n, m;
struct pai {
	ll w, p;
}p[200010];
inline int cmp(pai a, pai b) {
	return a.w<b.w || (a.w==b.w && a.p<b.p);
}
ll sw[200010], sp[200010];

int main() {
	freopen("pack.in", "r", stdin);
	freopen("pack.out", "w", stdout);
	scanf("%d%d", &n, &m);
	for (int i=1; i<=n; ++i) 
		scanf("%I64d%I64d", &p[i].w, &p[i].p);
	sort(p+1, p+n+1, cmp);
	for (int i=1; i<=n; ++i) {
		sw[i] = sw[i-1] + p[i].w;
		sp[i] = sp[i-1] + p[i].p;
	}
	/*
	printf("====sorted====\n");
	for (int i=1; i<=n; ++i) {
		printf("%I64d %I64d\n", p[i].w, p[i].p);
		printf("---%I64d %I64d\n", sw[i], sp[i]);
	}
	printf("======\n");
	*/
	int l, r, mid;
	ll s, ans;
	int pos, pos2;
	for (int i=1; i<=m; ++i) {
		ans = 0;
		scanf("%I64d", &s);
		// lower than s the maxinum
		pos2 = n+2;
		do {
			l=1, r=pos2-2, pos = 0;
			while(l<=r) {
				mid = l+r>>1;
				if(p[mid].w>s) r=mid-1;
				else {
					l=mid+1;
					pos = max(pos, mid);
				}
			}
			if(pos > 0) {
				pos2 = 0;
				l=1, r=pos;
				while(l<=r) {
					mid = l+r>>1;
					if(sw[pos]-sw[mid-1]>s) l=mid+1;
					else {
						r=mid-1;
						if(pos2 == 0) pos2 = mid;
						else pos2 = min(pos2, mid);
					}
				}
				ans = ans + sp[pos] - sp[pos2-1];
				s = s - sw[pos] + sw[pos2-1];
			} else break;
		}while(s>0);
		printf("%I64d\n", ans);
	}
	return 0;
}

2. 给定一个$1$到$n$的排列$x$，每次你可以将$x_1$到$x_i$翻转。你需要求出将序列变为升序的最小操作次数。有多组数据。

$T \leq 5, n \leq 25$

【题解】IDA*，估价函数为相邻两个相差1的个数。

# include <stdio.h>
# include <algorithm>
using namespace std;

inline int abs(int a) {
	return a>0?a:-a;
}

int T;
int n, p=0, id;
int a[26], bfa[26], cs=0;
bool flag=0;

inline void dfs() {
	if(flag) return;
	if(p+cs>id) return;
	if(p==0&&a[1]==1) {
		flag=1;
		return;
	}
	for (int i=2; i<=n; ++i) {
		if(i!=n) p += (abs(a[1]-a[i+1])!=1) - (abs(a[i]-a[i+1])!=1);
		for (int j=1; j<i+1-j; ++j)
			swap(a[j], a[i-j+1]);
		++cs;
		dfs();
		if(flag) return;
		--cs;
		for (int j=1; j<i+1-j; ++j)
			swap(a[j], a[i-j+1]);
		if(i!=n) p -= (abs(a[1]-a[i+1])!=1) - (abs(a[i]-a[i+1])!=1);
	}
}

int main() {
	freopen("sequence.in", "r", stdin);
	freopen("sequence.out", "w", stdout);
	scanf("%d", &T);
	while(T--) {
		p=0;
		scanf("%d", &n);
		for (int i=1; i<=n; ++i) scanf("%d", &a[i]), bfa[i]=a[i];
		for (int i=1; i<n; ++i)
			if(abs(a[i] - a[i+1]) > 1) ++p;
		int temp = p, to=2*n-2;
		for (id=0; id<=to; ++id) {
			for (int i=1; i<=n; ++i) a[i]=bfa[i];
			cs=0; p = temp; flag = 0;
			dfs();
			if(flag) {
				printf("%d\n", id);
				break;
			}
		}
	}
	return 0;
}

3. 你需要构造一个$1$到$n$的排列，使得它满足$m$个条件，每个条件形如$(a_i,b_i)$，表示$a_i$必须在$b_i$前面。在此基础上，你需要使它的字典序最小。

$n, m \leq 100000$

【题解】拓扑排序过程用堆维护即可。

# include <stdio.h>
# include <queue>
using namespace std;

int n, m, d[100010];
priority_queue< int, vector<int>, greater<int> > q;
int a[100010], an=0;
int tot=0, next[200010], head[100010], to[200010];
inline void add(int u, int v) {
	++tot;
	next[tot]=head[u];
	head[u]=tot;
	to[tot]=v;
}

int main() {
	freopen("dictionary.in", "r", stdin);
	freopen("dictionary.out", "w", stdout);
	scanf("%d%d", &n, &m);
	for (int i=1, aa, bb; i<=m; ++i) {
		scanf("%d%d", &aa, &bb);
		add(aa, bb);
		d[bb]++;
	}
	for (int i=1; i<=n; ++i)
		if(d[i]==0) q.push(i);
	while(!q.empty()) {
		int x=q.top();
		a[++an]=q.top();
		q.pop();
		for (int i=head[x]; i; i=next[i]) {
			d[to[i]]--;
			if(d[to[i]] == 0)
				q.push(to[i]);
		}
	}
	if(an != n) {
		puts("-1");
	} else {
		for (int i=1; i<=n; ++i) printf("%d ", a[i]);
		printf("\n");
	}
	return 0;
}

当场，写了第三题满分，第二题玄学，第一题50，稍微测了测第二题，感觉能60多

预计得分：50+60+100=210

实际得分：20+72+100=192

multiset还是没有卡过去，考场上怎么就没有想到两次二分呢。。估价函数对了，把A*改成IDA*就能A了。。

总有一些奇怪的错误。。