A - Hacker Cups and Balls
题意：给出一个长度为n（n为奇数，）的数组，给出m个操作，
，每一个操作包含一个
和
，如果给出的
，那么将这段排序成递增，如果
，将这段排序成递减。最后输出数组最中间的那个数字。
思路：
二分答案
，记
的数为0，
的数为1，那么区间排序就是把区间中的0和1提取出来然后再按顺序刷回去，用一个支持区间赋值区间求和的线段树维护即可，最后求出
处的值，若为0则k可能更小，否则必须更大，复杂度
saltyfish/2016-2017 National Taiwan University World Final Team Selection Contest
B - Bored Dreamoon
C - Crazy Dreamoon
题意：一个 的格子，输入n条线段，求被触碰到的格子的数量。
思路：按照线段斜率模拟。若或
，触格正好在斜对角上；若
或者
，触及到的格子都是在线段的左、右，左、右，向上延伸的，如果是
或者
，触及到的格子都是在线段的上、下，上、下，向上延伸的，对于中间有某个点正好卡在整数坐标上，就直接continue。注意函数每次的变化值就是+k。
AC代码：
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#define eps 1e-8
using namespace std;
const int maxn = 2000 + 100;
bool mark[maxn][maxn];
int n, cnt;
void solve(double x1, double y1, double x2, double y2) {
double k = (y2 - y1) / (x2 - x1);
if( fabs(k-1) < eps ) {
int st = (int)x1, ed = (int)x2, sty = (int)y1;
for(int i = st; i < ed; ++i) {
if(!mark[i][sty]) {
mark[i][sty] = true;
++cnt;
}
++sty;
}
}
else if( fabs(k+1) < eps ) {
int st = (int)x1, ed = (int)x2, sty = (int)y1 - 1;
for(int i = st; i < ed; ++i) {
if(!mark[i][sty]) {
mark[i][sty] = true;
++cnt;
}
--sty;
}
}
else if( k > 0 && k < 1 ) { // left & right
int st = (int)x1 + 1, ed = (int)x2;
double d = y1;
for(int i = st; i < ed; ++i) {
d += k;
int d1 = (int)d, d2 = (int)d + 1;
if(fabs(d1 - d) < eps || fabs(d2 - d) < eps)
continue;
if(!mark[i-1][d1]) {
mark[i-1][d1] = true;
++cnt;
}
if(!mark[i][d1]) {
mark[i][d1] = true;
++cnt;
}
}
}
else if( k < 0 && k > -1 ) { // left & right
int st = (int)x1 + 1, ed = (int)x2;
double d = y1;
for(int i = st; i < ed; ++i) {
d += k;
int d1 = (int)d, d2 = (int)d + 1;
if(fabs(d1 - d) < eps || fabs(d2 - d) < eps)
continue;
if(!mark[i-1][d1]) {
mark[i-1][d1] = true;
++cnt;
}
if(!mark[i][d1]) {
mark[i][d1] = true;
++cnt;
}
}
}
else if(k > 1){ // up & down
double kk = (x2 - x1) / (y2 - y1);
int st = (int)y1 + 1, ed = (int)y2;
double d = x1;
for(int i = st; i < ed; ++i) {
d += kk;
int d1 = (int)d, d2 = (int)d + 1;
if(fabs(d1 - d) < eps || fabs(d2 - d) < eps)
continue;
if(!mark[d1][i-1]) {
mark[d1][i-1] = true;
++cnt;
}
if(!mark[d1][i]) {
mark[d1][i] = true;
++cnt;
}
}
}
else if(k < -1){ // up & down
double kk = (x2 - x1) / (y2 - y1);
int st = (int)y1 - 1, ed = (int)y2, b = (int)x1;
double d = x1;
for(int i = st; i > ed; --i) {
d -= kk;
int d1 = (int)d, d2 = (int)d + 1;
if(fabs(d1 - d) < eps || fabs(d2 - d) < eps)
continue;
if(!mark[d1][i-1]) {
mark[d1][i-1] = true;
++cnt;
}
if(!mark[d1][i]) {
mark[d1][i] = true;
++cnt;
}
}
}
}
int main() {
double x1, y1, x2, y2;
cnt = 0;
scanf("%d", &n);
for(int i = 0; i < n; ++i) {
scanf("%lf%lf%lf%lf", &x1, &y1, &x2, &y2);
if(fabs(x1-x2) < eps || fabs(y1-y2) < eps)
continue;
if(x1 > x2) {
swap(x1, x2);
swap(y1, y2);
}
solve(x1, y1, x2, y2);
}
printf("%d\n", cnt);
return 0;
}
D - Forest Game
E - Lines Game
Gym - 101234E
题意：给出n () 个线段和权值，给出第一行
，表示第i个线段为
和
的连线，第二行为线段对应的权值
。现在要把这些线段删掉，删一个线段的同时可以把与它相交的所有线段都删掉，但花费仅是这一条线段的权值。求最小花费。
思路：判断线段相交/不相交的条件非常简单，若 且
或者
且
，那么两条线段必然不相交。然后按照贪心的取法，尽量去取权值小的。但是存储和查找相交线段的复杂度比较不可观，这样的思路无法实现。
F - Lonely Dreamoon 2
G - Dreamoon and NightMarket
题意：主人公去吃饭，现在有N种价值的食物（），他每天都要吃与之前不同且最便宜的组合，问第K（
,
）天他花了多少钱。
思路：我理解的是01背包k优解?
听说有的队伍优先队列过的
H - Split Game
I - Tree Game
J - Zero Game
Gym - 101234J
题意：给出一个由0、1组成的串，现在允许你进行Q种操作，每种操作可以进行步，每次操作可以随意挑一个数字移动位置。问操作后能够得到的最长的连续的0串有多长。
思路：单调队列
枚举答案中最左边0的位置，对应的方案应该是删除该位置右侧的连续若干段1，设delta=删除1后加入的0的个数-删除的1的个数，问题便转化为维护delta的最大值，用一个单调队列即可
网友评论