A - Hacker Cups and Balls
題意：給出一個長度為n（n為奇數(shù)迷帜，）的數(shù)組殖卑，給出m個操作，
执泰，每一個操作包含一個
和
宋下，如果給出的
嗡善，那么將這段排序成遞增，如果
学歧，將這段排序成遞減罩引。最后輸出數(shù)組最中間的那個數(shù)字。
思路：
二分答案
枝笨，記
的數(shù)為0袁铐，
的數(shù)為1，那么區(qū)間排序就是把區(qū)間中的0和1提取出來然后再按順序刷回去横浑，用一個支持區(qū)間賦值區(qū)間求和的線段樹維護即可剔桨，最后求出
處的值，若為0則k可能更小徙融，否則必須更大洒缀，復雜度
saltyfish/2016-2017 National Taiwan University World Final Team Selection Contest
B - Bored Dreamoon
C - Crazy Dreamoon
題意：一個 的格子，輸入n條線段欺冀，求被觸碰到的格子的數(shù)量树绩。
思路：按照線段斜率模擬。若或
隐轩，觸格正好在斜對角上饺饭；若
或者
，觸及到的格子都是在線段的左职车、右砰奕，左、右提鸟，向上延伸的军援，如果是
或者
，觸及到的格子都是在線段的上称勋、下胸哥，上、下赡鲜，向上延伸的空厌，對于中間有某個點正好卡在整數(shù)坐標上庐船，就直接continue。注意函數(shù)每次的變化值就是+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個線段為
和
的連線赋朦，第二行為線段對應的權值
÷ǔ澹現(xiàn)在要把這些線段刪掉，刪一個線段的同時可以把與它相交的所有線段都刪掉宠哄，但花費僅是這一條線段的權值壹将。求最小花費。
思路：判斷線段相交/不相交的條件非常簡單毛嫉，若 且
或者
且
诽俯，那么兩條線段必然不相交。然后按照貪心的取法承粤，盡量去取權值小的暴区。但是存儲和查找相交線段的復雜度比較不可觀，這樣的思路無法實現(xiàn)辛臊。
F - Lonely Dreamoon 2
G - Dreamoon and NightMarket
題意：主人公去吃飯颜启，現(xiàn)在有N種價值的食物（），他每天都要吃與之前不同且最便宜的組合浪讳，問第K（
,
）天他花了多少錢缰盏。
思路：我理解的是01背包k優(yōu)解?
聽說有的隊伍優(yōu)先隊列過的
H - Split Game
I - Tree Game
J - Zero Game
Gym - 101234J
題意：給出一個由0、1組成的串淹遵，現(xiàn)在允許你進行Q種操作口猜，每種操作可以進行步，每次操作可以隨意挑一個數(shù)字移動位置透揣。問操作后能夠得到的最長的連續(xù)的0串有多長济炎。
思路：單調(diào)隊列
枚舉答案中最左邊0的位置，對應的方案應該是刪除該位置右側(cè)的連續(xù)若干段1辐真，設delta=刪除1后加入的0的個數(shù)-刪除的1的個數(shù)须尚，問題便轉(zhuǎn)化為維護delta的最大值，用一個單調(diào)隊列即可
