NOIP 2016提高组，看满分大神如何玩转复赛
NOIP 2016提高组复赛中
全国涌现了18位满分大神，他们是：
何宇轩，雅礼中学；袁宇韬，雅礼中学
张千帆，雅礼中学；闫书弈，福州三中
陈旭，福州一中；钟知闲，福州一中
堵君懿，常州中学；徐海珂，南京外国语
洪华敦，绍兴一中；张乐行，绍兴一中
胡翰文，镇海中学；李泊宁，镇海蛟川书院
方汤骐，衢州实验学校；谢兴宇，东营胜利一中
张子禾，人大附中；刘明锐，上海格致中学
李奥，中山一中；唐宇豪，成都七中
Day1
1、玩具谜题（toy)
【问题描述】
小南有一套可爱的玩具小人，它们各有不同的职业。
有一天，这些玩具小人把小南的眼镜藏了起来。小南发现玩具小人们围成了一个圈，它们有的面朝圈内，有的面朝圈外。如下图：
这时 singer 告诉小南一个谜题：“眼镜藏在我左数第 3 个玩具小人的右数第 1 个玩具小人的左数第 2 个玩具小人那里。”
小南发现，这个谜题中玩具小人的朝向非常关键，因为朝内和朝外的玩具小人的左右方向是相反的：面朝圈内的玩具小人，它的左边是顺时针方向，右边是逆时针方向；而面向圈外的玩具小人，它的左边是逆时针方向，右边是顺时针方向。
小南一边艰难地辨认着玩具小人，一边数着：
“singer 朝内，左数第 3 个是 archer。
“archer 朝外，右数第 1 个是 thinker。
“thinker 朝外，左数第 2 个是 writer。
“所以眼镜藏在 writer 这里！”
虽然成功找回了眼镜，但小南并没有放心。如果下次有更多的玩具小人藏他的眼镜，或是谜题的长度更长，他可能就无法找到眼镜了。所以小南希望你写程序帮他解决类似的谜题。这样的谜题具体可以描述为：
有 n 个玩具小人围成一圈，己知它们的职业和朝向。现在第 1 个玩具小人告诉小南一个包含 m 条指令的谜题，其中第 i 条指令形如“左数/右数第 si 个玩具小人”。你需要输出依次数完这些指令后，到达的玩具小人的职业。
【输入格式】
从文件 toy.in 中读入数据。
输入的第一行包含两个正整数 n,m ，表示玩具小人的个数和指令的条数。
接下来 n 行，每行包含一个整数和一个字符串，以逆时针为顺序给出每个玩具小人的朝向和职业。其中 0 表示朝向圈内， 1 表示朝向圈外。保证不会出现其他的数。字符串长度不超过 10 且仅由小写字母构成，字符串不为空，并且字符串两两不同。整数和字符串之间用一个空格隔开。
接下来 m 行，其中第 i 行包含两个整数 ai, si ，表示第 i 条指令。若 ai = 0 ，表示向左数 si 个人；若 ai = 1 ，表示向右数 si 个人。保证 ai 不会出现其他的数， 1 ≤ si < n。
【输出格式】
输出到文件 toy.out 中。
输出一个字符串，表示从第一个读入的小人开始，依次数完 m条指令后到达的小人的职业。
【样例 1 输入】
73
0singer
0reader
0mengbier
1thinker
1archer
0writer
1mogician
03
11
02
【样例 1 输出】
writer
【样例 2 输入】
1010
1c
0r
0p
1d
1e
1m
1t
1y
1u
0v
17
11
14
05
03
01
16
12
08
04
【样例 2 输出】
y
模拟操作过程，分类讨论即可。时间复杂度：O(n+m)
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using name space std;
struct node{
int dir;
char name[15];
};
node p[100010];
int n, m;
int main(){
scanf("%d%d", &n, &m);
for(int i = 1; i <= n; i ++)scanf("%d%s", &p[i].dir, p[i].name+1);
int now = 1;
for(int i = 1; i <= m; i ++){
int a, b;
scanf("%d%d", &a,&b);
if(p[now].dir == 0){
if(a == 0) now = ((now - b) % n +n) % n;
else now = (now + b) % n;
}else{
if(a == 0) now = (now + b) % n;
else now = ((now - b) % n + n) % n;
}
if(now == 0) now = n;
}
printf("%s", p[now].name+1);
return 0;
}
2、天天爱跑步（running)
【问题描述】
小 C 同学认为跑步非常有趣，于是决定制作一款叫做《天天爱跑步》的游戏。
《天天爱跑步》是一个养成类游戏，需要玩家每天按时上线，完成打卡任务。
这个游戏的地图可以看作一棵包含 n 个结点和 n − 1 条边的树，每条边连接两个结点，且任意两个结点存在一条路径互相可达。树上结点编号为从 1 到 n 的连续正整数。
现在有 m 个玩家，第 i 个玩家的起点为 Si ，终点为 Ti 。每天打卡任务开始时，所有玩家在第 0 秒同时从自己的起点出发，以每秒跑一条边的速度，不间断地沿着最短路径向着自己的终点跑去，跑到终点后该玩家就算完成了打卡任务。（由于地图是一棵树，所以每个人的路径是唯一的）
小 C 想知道游戏的活跃度，所以在每个结点上都放置了一个观察员。在结点 j 的观察员会选择在第 Wj 秒观察玩家，一个玩家能被这个观察员观察到当且仅当该玩家在第 Wj 秒也正好到达了结点 j 。小 C 想知道每个观察员会观察到多少人？
注意：我们认为一个玩家到达自己的终点后该玩家就会结束游戏，他不能等待一段时间后再被观察员观察到。即对于把结点 j 作为终点的玩家：若他在第 Wj 秒前到达终点，则在结点 j 的观察员不能观察到该玩家；若他正好在第 Wj 秒到达终点，则在结点 j 的观察员可以观察到这个玩家。
【输入格式】
从文件 running.in 中读入数据。
第一行有两个整数 n 和 m 。其中 n 代表树的结点数量，同时也是观察员的数量，m 代表玩家的数量。
接下来 n − 1 行每行两个整数 u 和 v ，表示结点 u 到结点 v 有一条边。
接下来一行 n 个整数，其中第 j 个整数为 Wj ，表示结点 j 出现观察员的时间。
接下来 m 行，每行两个整数 Si 和 Ti ，表示一个玩家的起点和终点。
对于所有的数据，保证 1 ≤ Si , Ti ≤ n ， 0 ≤ Wj ≤ n 。
【输出格式】
输出到文件 running.out 中。
输出 1 行 n 个整数，第 j 个整数表示结点 j 的观察员可以观察到多少人。
【样例 1 输入】
63
23
12
14
45
46
02 5 1 2 3
15
13
26
【样例 1 输出】
20 0 1 1 1
【样例 2 输入】
53
12
23
24
15
01 0 3 0
31
14
55
【样例 2 输出】
12 1 0 1
读入第i个点的观察时间是val[i]。
通过DFS预处理，可以预处理得到每个节点的深度deep[i]和倍增需要的up[Max][MaxLog]数组，用倍增求得lca，在求得lca以后，我们可以把在lca路径上的点的操作转化为从起点和终点分别到根节点的操作-lca到根节点的操作-lca的父节点到根节点的操作。这样对于每一个跑步者的一个操作，我们把它分成了4个部分。
定义对与第i组询问，是从u[i]到v[i]的路径，路径长度是len[i]，lca是lca[i]。具体的来说我们把问题转换成了从一个点x到根节点的路径中，所有满足deep[x]+val[x]==deep[u[i]]或者deep[x]−val[x]==deep[v[i]]−len[i]的点的值加1或者减1。
不难发现，一个节点x的答案被增加，只有可能受到以x为根的子树中某个点的影响。而且需要满足的增加条件是定值（就是deep[u[i]]或deep[v[i]]−len[i]），然后就可以开一个桶，维护定值出现的次数，用邻接链表储存这些定值，根据dfs的性质（只有当子树全部访问完以后才会回到根），在访问子树之前记录下当前节点的定值，在操作完子树，维护了自己本身的节点以后，直接像前缀和一样，把新的值与操作前的值相减就好了。
时间复杂度：O(nlogn+n) （时间的瓶颈在求lca，lca如果用tarjan离线求可以做到并查集复杂度O(an)）。
#include<cstdio>
#include<cstring>
#include<iostream>
#include<cstdio>
using name space std;
const int maxn = 300010;
struct node{
int begin, end, lca, len;
};
node p[maxn];
int n, m, val[maxn];
int _first[maxn], _next[maxn*2], _to[maxn*2], cnt;
int ins1[maxn], ins2[maxn], del1[maxn], del2[maxn];
int nxt[maxn*4], v[maxn*4], cnt1;
int deep[maxn], up[maxn][20];
int ans[maxn];
int ct1[maxn*2], ct2[maxn*2];
inline void add1(int a, int b, int c){
nxt[++cnt1] = ins1[a];
v[ins1[a] = cnt1] = c;
nxt[++cnt1] = del1[b];
v[del1[b] = cnt1] = c;
}
inline void add2(int a, int b, int c){
nxt[++cnt1] = ins2[a];
v[ins2[a] = cnt1] = c;
nxt[++cnt1] = del2[b];
v[del2[b] = cnt1] = c;
}
inline void add(int a, int b){
_next[++cnt] = _first[a];
_to[_first[a] = cnt] = b;
}
void dfs(int x){
for(int i = 1; i <= 18; i ++){
up[x][i] = up[up[x][i-1]][i-1];
}
for(int i = _first[x]; i; i = _next[i]){
if(_to[i] == up[x][0]) continue;
up[_to[i]][0] = x, deep[_to[i]] =deep[x]+1;
dfs(_to[i]);
}
}
void lca(){
for(int ii = 1; ii <= m; ii ++){
int x = p[ii].begin, y = p[ii].end;
if(deep[x] < deep[y]) swap(x, y);
if(deep[x] != deep[y])
for(int i = 18; i >= 0; i --)
if(deep[up[x][i]] >=deep[y]) x = up[x][i];
if(x != y){
for(int i = 18; i >= 0; i --)
if(up[x][i] != up[y][i]) x =up[x][i], y = up[y][i];
x = up[x][0];
}
p[ii].lca = x;
p[ii].len = deep[p[ii].begin] - deep[x]+ deep[p[ii].end] - deep[x];
}
}
inline void dfs1(int x){
ans[x] = - ct1[deep[x]+val[x]] -ct2[deep[x]-val[x]+n];
for(int i = _first[x]; i; i = _next[i]){
if(_to[i] == up[x][0]) continue;
dfs1(_to[i]);
}
for(int i = ins1[x]; i; i = nxt[i])ct1[v[i]] ++;
for(int i = del1[x]; i; i = nxt[i])ct1[v[i]] --;
for(int i = ins2[x]; i; i = nxt[i])ct2[v[i]+n] ++;
for(int i = del2[x]; i; i = nxt[i])ct2[v[i]+n] --;
ans[x] += ct1[deep[x]+val[x]] +ct2[deep[x]-val[x]+n];
}
int main(){
scanf("%d%d", &n, &m);
for(int i = 1; i < n; i ++){
int a, b;
scanf("%d%d", &a, &b);
add(a, b), add(b, a);
}
deep[1] = 1, dfs(1);
for(int i = 1; i <= n; i ++)scanf("%d", &val[i]);
for(int i = 1; i <= m; i ++)scanf("%d%d", &p[i].begin, &p[i].end);
lca();
for(int i = 1; i <= m; i ++){
add1(p[i].begin, up[p[i].lca][0],deep[p[i].begin]);
add2(p[i].end, p[i].lca,deep[p[i].end]-p[i].len);
}
dfs1(1);
for(int i = 1; i < n; i ++)printf("%d ", ans[i]); printf("%d", ans[n]);
return 0;
}
3、换教室（classroom)
【问题描述】
对于刚上大学的牛牛来说，他面临的第一个问题是如何根据实际情况申请合适的课程。
在可以选择的课程中，有 2n 节课程安排在 n 个时间段上。在第 i ( 1 ≤ i ≤ n )个时间段上，两节内容相同的课程同时在不同的地点进行，其中，牛牛预先被安排在教室ci上课，而另一节课程在教室 di 进行。
在不提交任何申请的情况下，学生们需要按时间段的顺序依次完成所有的 n 节安排好的课程。如果学生想更换第 i 节课程的教室，则需要提出申请。若申请通过，学生就可以在第 i 个时间段去教室 di 上课，否则仍然在教室 ci 上课。
由于更换教室的需求太多，申请不一定能获得通过。通过计算，牛牛发现申请更换第 i 节课程的教室时，申请被通过的概率是一个己知的实数 ki ，并且对于不同课程的申请，被通过的概率是互相独立的。
学校规定，所有的申请只能在学期开始前一次性提交，并且每个人只能选择至多 m 节课程进行申请。这意味着牛牛必须一次性决定是否申请更换每节课的教室，而不能根据某些课程的申请结果来决定其他课程是否申请；牛牛可以申请自己最希望更换教室的 m 门课程，也可以不用完这 m 个申请的机会，甚至可以一门课程都不申请。
因为不同的课程可能会被安排在不同的教室进行，所以牛牛需要利用课间时间从一间教室赶到另一间教室。
牛牛所在的大学有 v 个教室，有 e 条道路。每条道路连接两间教室，并且是可以双向通行的。由于道路的长度和拥堵程度不同，通过不同的道路耗费的体力可能会有所不同。当第 i （ 1 ≤ i ≤ n − 1 ）节课结束后，牛牛就会从这节课的教室出发，选择一条耗费体力最少的路径前往下一节课的教室。
现在牛牛想知道，申请哪几门课程可以使他因在教室间移动耗费的体力值的总和的期望值最小，请你帮他求出这个最小值。
【输入格式】
从文件 classroom.in 中读入数据。
第一行四个整数 n, m, v, e 。 n 表示这个学期内的时间段的数量； m 表示牛牛最多可以申请更换多少节课程的教室； v 表示牛牛学校里教室的数量； e 表示牛牛的学校里道路的数量。
第二行 n 个正整数，第 i （ 1 ≤ i ≤ n ）个正整数表示 ci ，即第 i 个时间段牛牛被安排上课的教室；保证 1 ≤ ci ≤ v 。
第三行 n 个正整数，第 i （ 1 ≤ i ≤ n ）个正整数表示 di ，即第 i 个时间段另一间上同样课程的教室；保证 1 ≤ di ≤ v 。
第四行 n 个实数，第 i （ 1 ≤ i ≤ n ）个实数表示 ki ，即牛牛申请在第 i 个时间段更换教室获得通过的概率。保证 0 ≤ ki ≤ 1 。
接下来 e 行，每行三个正整数 aj ， bj ， wj ，表示有一条双向道路连接教室 aj , bj ，通过这条道路需要耗费的体力值是 wj ；保证 1 ≤ aj, bj ≤ v ， 1 ≤ wj ≤ 100 。
保证 1 ≤ n ≤ 2000 ， 0 ≤ m ≤ 2000 ， 1 ≤ v ≤ 300 ， 0 ≤ e ≤ 90000 。
保证通过学校里的道路，从任何一间教室出发，都能到达其他所有的教室。
保证输入的实数最多包含 3 位小数。
【输出格式】
输出到文件 classroom.out 中。
输出一行，包含一个实数，四舍五入精确到小数点后恰好 2 位，表示答案。你的输出必须和标准输出完全一样才算正确。
测试数据保证四舍五入后的答案和准确答案的差的绝对值不大于 4×10-3 。（如果你不知道什么是浮点误差，这段话可以理解为：对于大多数的算法，你可以正常地使用浮点数类型而不用对它进行特殊的处理）
【样例 1 输入】
32 3 3
21 2
12 1
0.80.2 0.5
12 5
13 3
23 1
【样例 1 输出】
2.80
对于期望的概念，举例来说，已知A转换为B的代价为p1，现在有0.6的可能性让A转换为B的代价变为p2，那么A转换为B的期望代价就是p1∗0.4+p2∗0.6。进行期望计算的时候，一定要保证所有的项出现的概率之和为1。上面的例子中，0.4+0.6=1。
对于这个题，我们可以先用Floyd预处理每两个点之间的最短路，这样走一定是最优的。剩下的部分可以用动态规划来实现，设dp[i][j][0/1]表示考虑前i个物品，已经换了j个的最小期望代价。时间复杂度：O(e3+nm)
#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
using name space std;
const int inf = 2e9;
int n, m, v, e;
int a1[2010], a2[2010];
double dp[2010][2010][2], dis[310][310], w[2010], ans;
int main(){
scanf("%d%d%d%d", &n, &m,&v, &e);
for(int i = 1; i <= n; i ++)scanf("%d", &a1[i]);
for(int i = 1; i <= n; i ++)scanf("%d", &a2[i]);
for(int i = 1; i <= n; i ++)scanf("%lf", &w[i]);
for(int i = 0; i <= v; i ++)
for(int j = 0; j <= v; j ++)
if(i == j) dis[i][j] = 0;
else dis[i][j] = inf;
for(int i = 1; i <= e; i ++){
int a, b; double c;
scanf("%d%d%lf", &a,&b, &c);
dis[a][b] = min(dis[a][b], c);
dis[b][a] = min(dis[b][a], c);
}
for(int k = 1; k <= v; k ++)
for(int i = 1; i <= v; i ++)
for(int j = 1; j <= v; j ++)
if(dis[i][j] >dis[i][k]+dis[k][j])
dis[i][j] =dis[i][k]+dis[k][j];
for(int i = 0; i <= n; i ++)
for(int j = 0; j <= m; j ++)
dp[i][j][0] = dp[i][j][1] = inf;
dp[1][0][0] = 0;
dp[1][1][1] = 0;
for(int i = 2, up; i <= n; i ++){
up = min(i, m);
for(int j = 0; j <= up; j ++){
dp[i][j][0] = min(dp[i][j][0],dp[i-1][j][0]
+dis[a1[i]][a1[i-1]]);
dp[i][j][0] = min(dp[i][j][0],dp[i-1][j][1]
+dis[a1[i]][a2[i-1]]*w[i-1]
+dis[a1[i]][a1[i-1]]*(1-w[i-1]));
if(j-1 >= 0) dp[i][j][1] =min(dp[i][j][1], dp[i-1][j-1][0]
+dis[a2[i]][a1[i-1]]*w[i]
+dis[a1[i]][a1[i-1]]*(1-w[i]));
if(j-1 >= 0) dp[i][j][1] =min(dp[i][j][1], dp[i-1][j-1][1]
+dis[a2[i]][a2[i-1]]*w[i]*w[i-1]
+dis[a2[i]][a1[i-1]]*w[i]*(1-w[i-1])
+dis[a1[i]][a2[i-1]]*(1-w[i])*w[i-1]
+dis[a1[i]][a1[i-1]]*(1-w[i])*(1-w[i-1]));
}
}
ans = inf;
for(int i = 0; i <= m; i ++) ans =min(ans, min(dp[n][i][0], dp[n][i][1]));
printf("%.2lf", ans);
return 0;
}
Day2
1、组合数问题（problem)
【问题描述】
组合数
其中 n! = 1 × 2 × • • • × n 。
小葱想知道如果给定 n, m 和 k ，对于所有的 0 ≤ i ≤ n, 0 ≤ j ≤ min(i, m) 有多少对(i, j) 满足
【输入格式】
从文件 problem.in 中读入数据。
第一行有两个整数 t, k ，其中 t 代表该测试点总共有多少组测试数据，k 的意义见【问题描述】。
接下来 t 行每行两个整数 n, m ，其中 n, m 的意义见【问题描述】。
【输出格式】
输出到文件 problem.out 中。
t行，每行一个整数代表所有的 0 ≤ i ≤ n, 0 ≤j ≤ min(i, m) 中有多少对 (i, j) 满足
【样例 1 输入】
12
33
【样例 1 输出】
1
【样例 2 输入】
25
45
67
【样例 2 输出】
0
7
预处理杨辉三角，每次转移时把相加后的值对k取模，结果用二维前缀和记录。时间复杂度：O(nm+T) 。
#include<cstdio>
#include<iostream>
using name space std;
int T, k;
int sum[2010][2010], val[2010][2010];
int a[10010], b[10010], p1, p2;
int main(){
scanf("%d%d", &T, &k);
for(int i = 1; i <= T; i ++){
scanf("%d%d", &a[i],&b[i]);
p1 = max(p1, a[i]);
p2 = max(p2, b[i]);
}
for(int i = 0; i <= p1; i ++){
for(int j = 0; j <= min(p2, i); j++){
if(j == 0){val[i][j] = 1;continue;}
val[i][j] = (val[i-1][j] +val[i-1][j-1]) % k;
if(val[i][j] == 0) sum[i][j] = 1;
}
}
for(int i = 1; i <= p1; i ++){
for(int j = 1; j <= p2; j ++){
sum[i][j] = sum[i-1][j] +sum[i][j-1] + sum[i][j] - sum[i-1][j-1];
}
}
for(int i = 1; i <= T; i ++){
printf("%d\n",sum[a[i]][b[i]]);
}
return 0;
}
2、蚯蚓（earthworm)
【问题描述】
本题中，我们将用符号 LcJ 表示对 c 向下取整，例如： L3.0J = L3.1J = L3.9J =3。
蛐蛐国最近蚯蚓成灾了！隔壁跳蚤国的跳蚤也拿蚯蚓们没办法，蛐蛐国王只好去请神刀手来帮他们消灭蚯蚓。
蛐蛐国里现在共有 n 只蚯蚓（ n 为正整数）。每只蚯蚓拥有长度，我们设第 i 只蚯蚓的长度为 ai ( i = 1, 2, . . . , n)，并保证所有的长度都是非负整数（即：可能存在长度为0的蚯蚓）。
每一秒，神刀手会在所有的蚯蚓中，准确地找到最长的那一只（如有多个则任选一个）将其切成两半。神刀手切开蚯蚓的位置由常数 p （是满足 0 < p < 1 的有理数）决定，设这只蚯蚓长度为 x ，神刀手会将其切成两只长度分别为 LpxJ 和 x − LpxJ 的蚯蚓。特殊地，如果这两个数的其中一个等于 0 ，则这个长度为 0 的蚯蚓也会被保留。此外，除了刚刚产生的两只新蚯蚓，其余蚯蚓的长度都会增加 q（是一个非负整常数）。
蛐蛐国王知道这样不是长久之计，因为蚯蚓不仅会越来越多，还会越来越长。蛐蛐国王决定求助于一位有着洪荒之力的神秘人物，但是救兵还需要 m 秒才能到来......（m 为非负整数）蛐蛐国王希望知道这 m 秒内的战况。
具体来说，他希望知道：
m秒内，每一秒被切断的蚯蚓被切断前的长度（有 m 个数）；
m秒后，所有蚯蚓的长度（有 n + m 个数）。
蛐蛐国王当然知道怎么做啦! 但是他想考考你......
【输入格式】
从文件 earthworm.in 中读入数据。
第一行包含六个整数 n, m, q, u, v, t ，其中： n, m, q 的意义见【问题描述】； u, v, t 均为正整数；你需要自己计算 p = u/v （保证 0 < u < v ）；t 是输出参数，其含义将会在【输出格式】中解释。
第二行包含 n 个非负整数，为 a1, a2, . . . , an ，即初始时 n 只蚯蚓的长度。
同一行中相邻的两个数之间，恰好用一个空格隔开。
保证 1≤n≤105，0≤m≤7×106，0 < u < v≤109，0≤q≤200，1≤t≤71，0≤ai≤108 。
【输出格式】
输出到文件 earthworm.out
第一行输出
第二行输出
同一行中相邻的两个数之间，恰好用一个空格隔开。即使某一行没有任何数需要输出，你也应输出一个空行。
请阅读样例来更好地理解这个格式。
【样例 1 输入】
37 1 1 3 1
33 2
【样例 1 输出】
34 4 4 5 5 6
66 6 5 5 4 4 3 2 2
【样例 2 输入】
37 1 1 3 2
33 2
【样例 2 输出】
44 5
65 4 3 2
【样例 3 输入】
37 1 1 3 9
33 2
【样例 3 输出】
2
因为每一次蚯蚓的长度都会增加，而时间又不允许把所有的长度都进行增减，考虑到我们只需要知道所有蚯蚓的相对大小关系，所以把剩余的打标记，把新切出来的减去其余增加的长度，模拟每次操作。
每次取出来切的蚯蚓一定是最长的一个，切完之后的新生成的蚯蚓不会比原来的蚯蚓长。基于这一点，我们考虑优化。如果我们现将输入的n个数按长度排序，然后把新生成的两个小的插入到输入的这n个元素序列中，时间复杂度是O(n)的，思考归并排序的思想，因为取出来分割的比例是固定的，所以比较长的分割出来的新蚯蚓的长度，一定比较短的分割出来的新蚯蚓的长度要长。所以说有单调性，然后就可以像归并排序一样维护最大值了。
具体的，我们开两个队列，分别维护每次分割完以后较长的一段和较短的一段的长度，加上输入序列，三个数列全部满足单调性。每次要切的蚯蚓从输入数列中和新开的两个队列中取最大值。实现的细节是要注意队列的边界。时间复杂度：O(nlogn+(n+m))
#include<cstdio>
#include<iostream>
#include<algorithm>
#define MAX(a,b) (((a)>(b))?(a):(b))
#define MIN(a,b) (((a)<(b))?(a):(b))
using name space std;
inline int gt(){
char _ch = ' ';
int _num = 0, _op = 1, _ok = 0;
while(1){
_ch = getchar();
if(_ch == '-') _op *= -1;
else if(_ch >= '0' && _ch <='9') _num = _num*10 + _ch - '0', _ok = 1;
else if(_ok) return _op * _num;
}
}
int n, m, q, u, v, t;
int left1;
int len[100010], q1[8000010], q2[8000010];
int out[1000010], cnt;
int main(){
scanf("%d%d%d%d%d%d", &n,&m, &q, &u, &v, &t);
for(int i = 1; i <= n; i ++) len[i] =gt();
sort(len+1, len+1+n);
int p1 = 1, p2 = 0, p3 = 1, p4 = 0, p5 = n,now = 0;
for(int i = 1; i <= m; i ++){
if(p5 >= 1 && len[p5] >=MAX(q1[p1], q2[p3])) now = len[p5--] + left1;
else if(p1 <= p2 && q1[p1]>= q2[p3]) now = q1[p1++] + left1;
else if(p3 <= p4) now = q2[p3++] +left1;
if(i%t == 0) out[++cnt] = now;
left1 += q;
int new1 = ((long long)now*(longlong)u)/(long long)v;
int new2 = now - new1;
q1[++p2] = MAX(new1, new2) - left1;
q2[++p4] = MIN(new1, new2) - left1;
}
for(int i = 1; i <= cnt; i ++)printf("%d ", out[i]);
printf("\n");
for(int i = 1, w = 0; i <= n+m; i ++, w= 0){
if(p5 >= 1 && len[p5] >=MAX(q1[p1], q2[p3])) w = len[p5--] + left1;
else if(p1 <= p2 && q1[p1]>= q2[p3]) w = q1[p1++] + left1;
else if(p3 <= p4) w = q2[p3++] +left1;
if(i%t != 0) continue;
printf("%d ", w);
}
return 0;
}
3、愤怒的小鸟（angrybirds)
【问题描述】
Kiana最近沉迷于一款神奇的游戏无法自拔。
简单来说，这款游戏是在一个平面上进行的。
有一架弹弓位于 (0, 0) 处，每次 Kiana 可以用它向第一象限发射一只红色的小鸟，小鸟们的飞行轨迹均为形如 y = ax2 + bx 的曲线，其中 a, b 是 Kiana 指定的参数，且必须满足 a < 0。
当小鸟落回地面（即 x 轴）时，它就会瞬间消失。
在游戏的某个关卡里，平面的第一象限中有 n 只绿色的小猪，其中第 i 只小猪所在的坐标为 (xi, yi)。
如果某只小鸟的飞行轨迹经过了 (xi, yi) ，那么第 i 只小猪就会被消灭掉，同时小鸟将会沿着原先的轨迹继续飞行；
如果一只小鸟的飞行轨迹没有经过 (xi, yi) ，那么这只小鸟飞行的全过程就不会对第 i 只小猪产生任何影响。
例如，若两只小猪分别位于 (1, 3) 和 (3, 3) ，Kiana 可以选择发射一只飞行轨迹为 y =
−x2+ 4x 的小鸟，这样两只小猪就会被这只小鸟一起消灭。
而这个游戏的目的，就是通过发射小鸟消灭所有的小猪。
这款神奇游戏的每个关卡对 Kiana 来说都很难，所以 Kiana 还输入了一些神秘的指令，使得自己能更轻松地完成这个游戏。这些指令将在【输入格式】中详述。
假设这款游戏一共有 T 个关卡，现在 Kiana 想知道，对于每一个关卡，至少需要发射多少只小鸟才能消灭所有的小猪。由于她不会算，所以希望由你告诉她。
【输入格式】
从文件 angrybirds.in 中读入数据。
第一行包含一个正整数 T ，表示游戏的关卡总数。
下面依次输入这 T 个关卡的信息。每个关卡第一行包含两个非负整数 n, m ，分别表示该关卡中的小猪数量和 Kiana 输入的神秘指令类型。接下来的 n 行中，第 i 行包含两个正实数 xi, yi ，表示第 i 只小猪坐标为 (xi, yi) 。数据保证同一个关卡中不存在两只坐标完全相同的小猪。
如果m = 0 ，表示 Kiana 输入了一个没有任何作用的指令。
如果m = 1 ，则这个关卡将会满足：至多用
如果m = 2 ，则这个关卡将会满足：一定存在一种最优解，其中有一只小鸟消灭了至少
保证 1 ≤ n ≤ 18 ， 0 ≤ m ≤ 2 ， 0 < xi, yi < 10 ，输入中的实数均保留到小数点后两位。
【输出格式】
输出到文件 angrybirds.out 中。
对每个关卡依次输出一行答案。
输出的每一行包含一个正整数，表示相应的关卡中，消灭所有小猪最少需要的小鸟数量。
【样例 1 输入】
2
20
1.003.00
3.003.00
52
1.005.00
2.008.00
3.009.00
4.008.00
5.005.00
【样例 1 输出】
1
1
【样例 2 输入】
3
20
1.412.00
1.733.00
30
1.111.41
2.341.79
2.981.49
50
2.722.72
2.723.14
3.142.72
3.143.14
5.005.00
【样例 2 输出】
2
2
3
【样例 3 输入】
1
100
7.166.28
2.020.38
8.337.78
7.682.09
7.467.86
5.777.44
8.246.72
4.425.11
5.427.79
8.154.99
【样例 3 输出】
6
状态压缩动态规划。首先用18位二进制数表示，每一个是否被打了。
因为一直一定过原点，所以再有两个点就可以确定。
设另外的两个点为A(x1,y1),B(x2,y2)；设抛物线的方程为y=ax2+bx
带入方程：y1=ax12+bx1；y2=ax22+bx2
上面乘x2，下面乘x1：y1x2=ax12x2+bx1x2；y2x1=ax22x1+bx1x2
上式减下式：y1x2−y2x1=a(x12x2−x22x1)
解得：a=(y1x2−y2x1)/(x12x2−x22x1)；b=(y1−ax12)/x1；应该满足的条件是：a<0
然后就可以预处理出num[i][j]表示以i为第一个点的第j种方案。
然后就是动态规划了，设dp[i]表示现在的攻击状态二进制表示为i的最小次数。
dp[i|num[now][j]]=min(dp[i|num[now][j]],dp[i]+1)
dp[i|(1<<(now−1))]=min(dp[i|(1<<(now−1))],dp[i]+1)
其中，now是i这个状态中没有被攻击的最低的一位，因为考虑到在最优的答案中，这个位上一定会被攻击，所以只需要枚举攻击经过第now位的即可，此时做多有n种可能。
对于选定的第now位来说，也可以选择只打这一个，即为第二个方程。时间复杂度：O(Tn2n)
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using name space std;
const double eps = 0.000000001;
struct point{
double x, y;
};
int T, n, m, ans = 1e9;
point p[25];
int num[25][25], dp[300010];
int calc(double a, double b){
int res = 0, now = 1;
for(int i = 1; i <= n; i ++, now<<= 1){
double t = a*p[i].x*p[i].x+b*p[i].y;
if(abs(a*p[i].x*p[i].x+b*p[i].x-p[i].y)< eps){
res |= now;
}
}
return res;
}
int bits(int x){
int res = 0;
for(int i = 1; i <= n; i ++, x >>=1) if((x&1) == 0) res ++;
return res;
}
int main(){
scanf("%d", &T);
while(T--){
scanf("%d%d", &n,&m);
for(int i = 1; i <= n; i ++){
scanf("%lf%lf",&p[i].x, &p[i].y);
}
memset(dp, 63, sizeof(dp));
memset(num, 0, sizeof(num));
ans = 1e9;
for(int i = 1; i <= n; i ++){
for(int j = i+1; j <= n; j ++){
if(i == j) continue;
if(abs(p[i].x-p[j].x) < eps)continue;
double a =(p[i].y*p[j].x-p[j].y*p[i].x)/(p[i].x*p[i].x*p[j].x-p[j].x*p[j].x*p[i].x);
if(a >= 0) continue;
double b =(p[i].y-a*p[i].x*p[i].x)/p[i].x;
num[i][++num[i][0]] =calc(a,b);
}
}
int MAX = (1<<n)-1;
dp[0] = 0;
for(int i = 0; i <= MAX; i ++){
int now = 0;
for(int j = 1, w = 1; j <= n; j++, w <<= 1){
if((w&i) == 0){now =j;break;}
}
if(now == 0) continue;
dp[i|(1<<(now-1))] =min(dp[i|(1<<(now-1))], dp[i] + 1);
for(int j = 1; j <= num[now][0];j ++){
dp[i|num[now][j]] =min(dp[i|num[now][j]], dp[i] + 1);
}
}
printf("%d\n", dp[MAX]);
}
return 0;
}
猛戳下面文章，一起去冲刺NOIP复赛吧！
家长进微信交流总群，请加江哥微信：zzijiang
OIer投稿，请加江哥微信：zzijiang
信息学竞赛家长交流QQ群：532193136
信息学竞赛选手交流QQ群：465537784
WELCOME