Problem A. Ticket Swapping
Brief description:
… 给定一个直线形的地铁站，一共 n 站，只能向一个方向移动。。每一站单站价格是从 n 开始每次减 1。
。。bug 是这个系统可以通过在站内交换车票来达到 cheat 的效果。。
。。给定 m 个请求 l, r, p 表示从 l 发出 p 个客流倒 r。
。。问整个系统最多会损失多少￥。。。
( n <= 1e9, m <= 1e3 .. )
Analysis:
。。直接把每个请求拆成一个入事件一个出事件混在一起排序 O(mlogm)。。之后接一个栈扫一遍就行了。。O(m)。。
...
stack<event> S; REP(i, 2*m){
if (E[i].p > 0) S.push(E[i]);
else {
while (E[i].p){
int d = min(S.top().p, -E[i].p);
res -= f(E[i].x - S.top().x) * d;
E[i].p += d, S.top().p -= d;
if (!S.top().p) S.pop();
}
}
}
参考代码。。
。。比赛时候的话。。最好像 Tourist 一样直接爆 O(m^2) 的。。。
Problem B. Many Prizes
Brief description:
… 2^n 个人进行 n 轮淘汰赛。问：
。。一定进前 p 名的人有多少个。。。。
。。可以进前 p 名的人有多少个。。
Analysis:
。f1(n, p) n 个人里有多少人一定排前 p 名。
。f2(n, p) n 个人里有多少人可能排前 p 名。
。。似乎没有二分答案以外的方法，设
。ff1(n, p) n 个人里排名为 p 的人，的 最坏 排名。
。ff2(n, p) n 个人里排名为 p 的人，的 最好 排名。
考虑 ff1 情况。。这个显然可以递归。。
。。每一次都要尽可能进入败者组。。
。。同时。。要尽可能多的让高名次的玩家也进入败者组。
。。方法是配对。。同时预留出一个可以击败当前玩家的。
ff2 的情况类似，不过是让名次低的进行配对以尽可能多的进入胜者组。
...
LL ff1(LL n, LL x){
if (!x) return 0; // 无法进入败者组
return n/2 + ff1(n/2, (x-1)/2);
}
..
LL ff2(LL n, LL x){
if (x == n-1) return x; // 无法进入胜者组
return ff2(n/2, n/2-((n-x))/2);
}
Note：
看了题解后。。发现其实两个问题是紧密联系的。。
Let’s begin by an observation that will make our life a bit easier: if we reverse all the team numbers (that is, team 0 becomes team 2^N-1, team 1 becomes team 2^N-2, etc.), without changing the tournament list. This will result in the final ranks of the teams also being reversed, since it’s relatively easy to see that all the records will be reversed (wins becoming losses and vice versa). This means that the problem of having a team rank as low as possible to get into the first P is equivalent to the problem of a team ranked as high as possible to get into the bottom P (or, in other words, not get into the top 2^N – P). Thus, if we are able to answer the question what is the lowest rank that can possibly get into the top P, we can run the same code to see what’s the lowest rank that can possibly be in the top 2^N – P, subtract one, and reverse, and this will be the lowest rank that will always get a prize. This means we only have to solve one problem — lowest ranked team guaranteed to be in the top P .. .
。。。通过这个关系。。。解出任意一个就行了（主要此时需要加额外的一组边界条件）。。Orz。。。
。。。并且。。明显问题2 其实更容易些。。。
Problem C. Erdős–Szekeres
Brief description:
…
Analysis:
… 差分约束后不能保证没有重复数字。。因此还要执行一遍 dfs()。。。
。。。但实际上直接 dfs() 就行了。。）
D. Multiplayer Pong
