《2011noip提高组复赛题解资料》由会员分享，可在线阅读，更多相关《2011noip提高组复赛题解资料（13页珍藏版）》请在金锄头文库上搜索。
1、Noip 2011 提高组 （Day 1） 解题报告及程序一、铺地毯正着扫一遍 判断每个矩形是否覆盖询问的点，覆盖则更新结果或者倒着扫一遍，找到第一个覆盖询问点的矩形，输出即可，时间复杂度O（n）Procedure:#include #define MaxLength 10000inline int Getint() char c = getchar(); while (c9) c = getchar(); int ret = 0; while (c=0 & c=9) ret = ret*10 + (c-0); c = getchar(); return ret;int sxMaxLength
2、+5, syMaxLength+5, exMaxLength+5, eyMaxLength+5, n;void Init() n = Getint(); for (int i=1; i=sxi & x0=syi & y0=eyi) ans = i; break; printf(%d, ans); return ;int main() Init(); Solve(); getchar(); getchar(); return 0;二、选择客栈f ij表示前i个客栈以第j种颜色的方案数，先以客栈划分第一阶段，以颜色划分第二阶段，如果颜色相同的客栈，则以前一客栈相同颜色的方案数+1，否则同其一样；计
3、算答案时记一下前一个比最高消费限制低的客栈编号posi，路径压缩，时间复杂度O（nm）Procedure:#include #define MaxNode 200000#define MaxType 50inline int Getint() char c = getchar(); while (c9) c = getchar(); int ret = 0; while (c=0 & c=9) ret = ret*10 + (c-0); c = getchar(); return ret;int colorMaxNode+5, priceMaxNode+5, n, m, low;void In
4、it() n = Getint(), m = Getint(), low = Getint(); for (int i=1; i=n; i+) colori = Getint(), pricei = Getint(); return ;int fMaxNode+5MaxType+5, posMaxNode+5, ans = 0;void Dp() for (int i=1; i=n; i+) for (int j=0; jm; j+) if (colori=j) fij = fi-1j+1; else fij = fi-1j; for (int i=1; i=n; i+) if (pricei
5、=low) posi = i; ans += fi-1colori; else posi = posi-1; ans += fposicolori; printf(%d, ans); return ;int main() Init(); Dp(); getchar(); getchar(); return 0;三、Mayan纯暴力DFS，加可行性剪枝，如同一种颜色小于3块无法消除，同一颜色交换无意义，下落无法完成左右移动，再加模拟其过程时间复杂度O（ n(?) ）Procedure：#include #include inline int Getint() char c = getchar()
6、; while (c9) c = getchar(); int ret = 0; while (c=0 & c=9) ret = ret*10 + (c-0); c = getchar(); return ret;inline void Swap(int &a, int &b) int temp = a; a = b; b = temp; return ;int map1010, point10, color15, n, type = 0;void Init() n = Getint(); for (int i=0; i5; i+) mapi0 = Getint(); if (typemapi
7、pointi) type = mapipointi; color mapipointi +; while (mapipointi) mapi+pointi = Getint(); if (typemapipointi) type = mapipointi; color mapipointi +; pointi-; return ;bool Fall(int k) int top = -1; for (int i=0; i=pointk; i+) if (mapki) mapk+top = mapki; if (top!=pointk) for (int i=top+1; i=pointk; i
8、+) mapki = 0; pointk = top; return true; return false;bool Check_Fall() bool flag = false; for (int i=0; i5; i+) if (Fall(i) flag = true; return flag;bool sign1010;void Clear() int pmax = 0; for (int i=0; ipmax) pmax = pointi; for (int i=0; i=2) int k = pointi, j = k-1; for (; j=0; j-) if (mapij!=mapik) if (k-j=3) for (; kj; k-) signik = true; else k = j; if (k-j=3) for (; kj; k-) signik = true; for (int i=0; i=pmax; i+) int k = 0, j = 1; for (; j=3) for (; k=3) for (; kj; k+) signki = true; for (int i=0; i=0; j-) if (signij) signij = false; colormapij-; m
