nbhkdz.com冰点文库

2011noip提高组复赛题解


Noip 2011 提高组 (Day 1) 解题报告及程序 一、铺地毯 正着扫一遍 判断每个矩形是否覆盖询问的点,覆盖则更新结果 或者倒着扫一遍,找到第一个覆盖询问点的矩形,输出即可,时间复杂度 O(n) Procedure: #include <cstdio> #define MaxLength 10000 inline int Getint() { char c

= getchar(); while (c<'0' || c>'9') c = getchar(); int ret = 0; while (c>='0' && c<='9') { ret = ret*10 + (c-'0'); c = getchar(); } return ret; } int sx[MaxLength+5], sy[MaxLength+5], ex[MaxLength+5], ey[MaxLength+5], n; void Init() { n = Getint(); for (int i=1; i<=n; i++) { sx[i] = Getint(), sy[i] = Getint(), ex[i] = Getint(), ey[i] = Getint(); ex[i] += sx[i], ey[i] += sy[i]; } return ; } int x0, y0, ans = -1; void Solve() { x0 = Getint(), y0 = Getint(); for (int i=n; i;i--) if(x0>=sx[i] && x0<=ex[i] && y0>=sy[i] && y0<=ey[i]) { ans = i; break; } printf("%d", ans); return ; } int main() { Init(); Solve(); getchar(); getchar(); return 0;

} 二、选择客栈 f [i][j]表示前 i 个客栈以第 j 种颜色的方案数,先以客栈划分第一阶段,以颜色划分第二 阶段,如果颜色相同的客栈,则以前一客栈相同颜色的方案数+1,否则同其一样;计算答案 时记一下前一个比最高消费限制低的客栈编号 pos[i],路径压缩,时间复杂度 O(nm) Procedure: #include <cstdio> #define MaxNode 200000 #define MaxType 50 inline int Getint() { char c = getchar(); while (c<'0' || c>'9') c = getchar(); int ret = 0; while (c>='0' && c<='9') { ret = ret*10 + (c-'0'); c = getchar(); } return ret; } int color[MaxNode+5], price[MaxNode+5], n, m, low; void Init() { n = Getint(), m = Getint(), low = Getint(); for (int i=1; i<=n; i++) color[i] = Getint(), price[i] = Getint(); return ; } int f[MaxNode+5][MaxType+5], pos[MaxNode+5], ans = 0; void Dp() { for (int i=1; i<=n; i++) for (int j=0; j<m; j++) if (color[i]==j) f[i][j] = f[i-1][j]+1; else f[i][j] = f[i-1][j]; for (int i=1; i<=n; i++) if (price[i]<=low) { pos[i] = i; ans += f[i-1][color[i]]; } else { pos[i] = pos[i-1]; ans += f[pos[i]][color[i]]; } printf("%d", ans); return ; }

int main() { Init(); Dp(); getchar(); getchar(); return 0; } 三、 Mayan 纯暴力 DFS,加可行性剪枝,如同一种颜色小于 3 块无法消除,同一颜色交换无意义,下落 无法完成左右移动,再加模拟其过程 时间复杂度 O( n^(?) ) Procedure: #include <cstdio> #include <memory> inline int Getint() { char c = getchar(); while (c<'0' || c>'9') 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 map[10][10], point[10], color[15], n, type = 0; void Init() { n = Getint(); for (int i=0; i<5; i++) { map[i][0] = Getint(); if (type<map[i][point[i]]) type = map[i][point[i]]; color[ map[i][point[i]] ]++; while (map[i][point[i]]) { map[i][++point[i]] = Getint(); if (type<map[i][point[i]]) type = map[i][point[i]]; color[ map[i][point[i]] ]++; } point[i]--; } return ;

} bool Fall(int k) { int top = -1; for (int i=0; i<=point[k]; i++) if (map[k][i]) map[k][++top] = map[k][i]; if (top!=point[k]) { for (int i=top+1; i<=point[k]; i++) map[k][i] = 0; point[k] = top; return true; } return false; } bool Check_Fall() { bool flag = false; for (int i=0; i<5; i++) if (Fall(i)) flag = true; return flag; } bool sign[10][10]; void Clear() { int pmax = 0; for (int i=0; i<5; i++) if (point[i]>pmax) pmax = point[i]; for (int i=0; i<5; i++) if (point[i]>=2) { int k = point[i], j = k-1; for (; j>=0; j--) if (map[i][j]!=map[i][k]) { if (k-j>=3) for (; k>j; k--) sign[i][k] = true; else k = j; } if (k-j>=3) for (; k>j; k--) sign[i][k] = true; } for (int i=0; i<=pmax; i++) { int k = 0, j = 1; for (; j<5; j++) if (map[j][i]!=map[k][i]) { if (j-k>=3) for (; k<j; k++) sign[k][i] = true; else k = j;

} if (j-k>=3) for (; k<j; k++) sign[k][i] = true; } for (int i=0; i<5; i++) for (int j=pmax; j>=0; j--) if (sign[i][j]) { sign[i][j] = false; color[map[i][j]]--; map[i][j] = 0; } return ; } void Solve(int x, int y) { Fall(x), Fall(y); Clear(); while (Check_Fall()) Clear(); return ; } bool Check_Point() { for (int i=0; i<5; i++) if (point[i]>=0) return false; return true; } bool Check_Color() { for (int i=1; i<=type; i++) if (color[i]==1 || color[i]==2) return false; return true; } struct Ac{int m[10][10], p[10], c[15];}a[10]; inline void Copy(int k) { memcpy(a[k].m, map, sizeof(map)); memcpy(a[k].p, point, sizeof(point)); memcpy(a[k].c, color, sizeof(color)); return ; } inline void Turn_Copy(int k) { memcpy(map, a[k].m, sizeof(a[k].m)); memcpy(point, a[k].p, sizeof(a[k].p)); memcpy(color, a[k].c, sizeof(a[k].c)); return ; } int ans[10][10]; bool Dfs(int deep)

{ if (!Check_Color()) return false; Copy(deep); for (int i=0; i<5; i++) for (int j=0; j<=point[i]; j++) { ans[deep][0] = i, ans[deep][1] = j; if (i<4) { ans[deep][2] = 1; Swap(map[i][j], map[i+1][j]); if (point[i+1]<j) point[i+1] = j; Solve(i, i+1); if (deep==n && Check_Point()) return true; if (deep<n && Dfs(deep+1)) return true; Turn_Copy(deep); } if (i && point[i-1]<j) { ans[deep][2] = -1; Swap(map[i][j], map[i-1][j]); point[i-1] = j; Solve(i, i-1); if (deep==n && Check_Point()) return true; if (deep<n && Dfs(deep+1)) return true; Turn_Copy(deep); } } return false; } int main() { Init(); if (!Dfs(1)) printf("-1"); else for (int i=1; i<=n; i++) printf("%d %d %d\n", ans[i][0], ans[i][1], ans[i][2]); getchar(); getchar(); return 0; }

Noip 2011 提高组 (Day 2) 解题报告及程序 一、计算系数 二项式定理,杨辉三角,注意 Mod 就可以了,时间复杂度 O(k^2) Procedure: #include <cstdio> #define MaxNode 1000 #define Mod 10007 int f[MaxNode+5][MaxNode+5], a, b, k, n, m; void Init() { scanf("%d %d %d %d %d", &a, &b, &k, &n, &m); a %= Mod, b %= Mod, k++; for (int i=1; i<=k; i++) f[i][1] = f[i][i] = 1; for (int i=2; i<=k; i++) for (int j=2; j<i; j++) f[i][j] = (f[i-1][j-1] + f[i-1][j])%Mod; return ; } void Solve() { int x = k, y = k-n; for (int i=1; i<=n; i++) f[x][y] = (f[x][y] * a)%Mod; for (int j=1; j<=m; j++) f[x][y] = (f[x][y] * b)%Mod; printf("%d", f[x][y]%Mod); return ; } int main() { Init(); Solve(); getchar(); getchar(); return 0; }

二、聪明的质检员 由观察得随着参数 W 的上升检验值 temp 会减小,据函数 Abs(标准值-temp)有最小值,故 可二分查找得出答案 其中每次调整参数 W 时扫描一次矿石中大于 W 的, num[]表示其数量前缀和, val[]表示其价 值前缀和,故可在一个区间的检验值计算中以 O(1)的时间得出答案 时间复杂度 O(log(w)*(n+m)) Procedure: #include <cstdio> #define MaxNode 200000 #define INF ((0x7fffffffffffffffll)>>1) inline int Getint() { char c = getchar(); while (c<'0' || c>'9') c = getchar();

int ret = 0; while (c>='0' && c<='9') { ret = ret*10 + (c-'0'); c = getchar(); } return ret; } long long Abs(long long a) { if (a>0) return a; return -a; } int w[MaxNode+5], val[MaxNode+5], l[MaxNode+5], r[MaxNode+5], n, m, lw, rw; long long standard; void Init() { n = Getint(), m = Getint(), scanf("%I64d", &standard); for (int i=1; i<=n; i++) { w[i] = Getint(), val[i] = Getint(); if (rw<w[i]) rw = w[i]+1; } for (int i=1; i<=m; i++) l[i] = Getint(), r[i] = Getint(); return ; } int num[MaxNode+5]; long long sum[MaxNode+5]; long long Calc(int left, int right) { return (sum[right]-sum[left]) * (num[right]-num[left]); } long long Sieve(int Limit) { long long ret = 0; sum[0] = num[0] = 0; for (int i=1; i<=n; i++) { num[i] = num[i-1]; sum[i] = sum[i-1]; if (w[i]>=Limit) { num[i]++; sum[i] += val[i]; } } for (int i=1; i<=m; i++) ret += Calc(l[i]-1, r[i]); return ret; } long long ans = INF; void Binary_Search()

{ while (lw<rw) { int mid = (lw+rw)>>1; long long temp = Sieve(mid); long long value = Abs(standard - temp); if (temp<standard) rw = mid; else lw = mid+1; if (ans>value) ans = value; } printf("%I64d", ans); return ; } int main() { Init(); Binary_Search(); getchar(); getchar(); return 0; } 三、观光公交 贪心 令 t[i]表示当前到达第 i 个站的时间,sumoff[i]表示目的地为 i 的乘客数,arrtime[i]表 示第 i 个乘客到站等车的时刻 题目给定加速器的作用 就是可以把某个 t[i]减去 1 并把与其相关联的 t[i]全部减小 1。设 减小 t[i]后相关会改变的 t[i]区间为[i..end],则减小 t[i]对总结果的影响量就等于 sum{sumoff[j]}(j = i..end)。 那么我们每次应用加速器的时候,都选择对结果影响量最大的那个 t[i]去作用即可。 这样每次找最小需要 O(N)时间 共 K 个加速器 时间复杂度 O(nk) 还有一个小小的优化就是每次不一定只减 1,求一下对于最大的那个区间最大影响多少然后 减掉即可。(这样做时间复杂度降到 O(n^2)) 计算 ans 时 ans =sum{ t[i] * sumoff[i]}- sum{arrtime[i]} (i = 1..m) (传说中更快的算法 请参照 CLJ 的题解, 如果用堆维护当前可能的[i..end]区间的话 时间 复杂度可以降到 O(n log n)) Procedure: #include <cstdio> #define MaxView 1000 inline int Getint() { char c = getchar(); while (c<'0' || c>'9') c = getchar(); int ret = 0; while (c>='0' && c<='9') { ret = ret*10 + (c-'0'); c = getchar(); } return ret;

} int cost[MaxView+5], lateup[MaxView+5], sumoff[MaxView+5], n, m, k, sum = 0; void Init() { n = Getint(), m = Getint(), k = Getint(); for (int i=1; i<n; i++) cost[i] = Getint(); for (int i=1; i<=m; i++) { int arrtime = Getint(), start = Getint(), end = Getint(); sum += arrtime; if (lateup[start]<arrtime) lateup[start] = arrtime; sumoff[end]++; } return ; } int t[MaxView+5]; void Dp() { t[1] = 0; for (int i=2; i<=n; i++) if (t[i-1]>lateup[i-1]) t[i] = t[i-1] + cost[i-1]; else t[i] = lateup[i-1] + cost[i-1]; return ; } int ans = 0; void Greed() { while (k) { int i = 1, start; for (int maxn=0, sumleave; i<=n; i++) if (t[i]>t[i-1] && t[i]>lateup[i-1]) { sumleave = sumoff[i]; int temp = i; for (; i<=n && t[i]>lateup[i]; i++) sumleave += sumoff[i+1]; if (maxn<sumleave) maxn = sumleave, start = temp; } if (!start) break; i = start; int dele = t[i] - lateup[i-1]; if (dele>t[i]-t[i-1]) dele = t[i] - t[i-1]; if (dele>k) dele = k; for (i=start; i<=n && t[i]>lateup[i]; i++) if (dele>t[i]-lateup[i]) dele = t[i] - lateup[i]; int end = i; for (i=start; i<=end; i++) t[i] -= dele; k -= dele; }

for (int i=1; i<=n; i++) ans += t[i] * sumoff[i]; ans -= sum; printf("%d", ans); return ; } int main() { Init(); Dp(); Greed(); getchar(); getchar(); return 0; }

noip2011 提高组 day2 题解 第一题 数值计算 考察二项式定理 (a*x+b*y)^k 展开后 x^n*y^m(n+m=k)项系数为 a^n*b^m*C(k,n) C 为组合数 求解组合数用杨辉三角 即 C(a, b) = C(a-1, b-1) + C(a-1, b) 时间复杂度 O(k^2) 第二题 二分 取的 w 值越大 可以选择的零件就越少 所以按要求计算出的数值 s 就越小 所以二分找到两个距离给定的值 k 最近的两个 s 即可 每次求解 s 时 用部分和的方法 即先用 O(n)的时间算出从最开始到中间某一处总的可以取的零件数和其 v 值之和 之后对于每一个区间 可以用 O(1)的时间算出该范围内可以取的零件数和其 v 值之和 不需要高精度 因为当 w 取最大时 s 为 0 此时 abs(k-s)=s 优于所有 s 爆精度的情况 所以计算时若 s 超过 64 位整型的范围时令其等于一个特别大的值即可 时间复杂度 二分 O(logMaxW) * 二分时每次的求解 O(n) 即 O(nlogMaxW) 第三题 贪心 这道题使用贪心的方法 每次选择一条能获得最大收益的路修改 直到不能修改为止 具体做 法和解释如下 每个人在车上的时间 等于 车到达目的站的时间 减去 这个人到达起始站的时间 由于人到达起始站的时间题目给出不会变化 所以求解一个最优的车到达目的站的时间即可 假设到达第 i+1 站的时间是 time[i] 从前往后逐个求解到站时间 可以得出 time[i] = max{time[i-1], last[i]} + d[i] 其中 last[i]为从第 i 站上车的旅客中最后到达的一个到达的时间 可以用 O(n+m)的时间预 处理得出 d[i]为从 i 走到 i+1 所用的时间 很明显的 我们可以利用这个递推关系式用 O(n)的时间求解 time[i] 当我们令 d[i]减少 1 时 time[1..i-1]不会变化 time[i]会减少 1 考虑 time[i+1] 由前面的式子得出 time[i+1] = max{time[i], last[i+1]} + d[i+1] 若我们令 d[i]减少之前 存在 time[i] > last[i+1]则 time[i+1]会减少 1 否则 time[i+1] 就会不变 若 time[i+1]减少了 1 我们可以用同样的方法判断 time[i+2]直到最后是否变化 若 time[i+1]不变 则 time[i+2]及之后的 time 值都不会变化 **所以 当我们令某个 d[i]减少 1 时 从 time[i]开始会有一段区间的 time 值均减少 1

这个区间的左端为 i 我们令右端为 range[i] 对于 j 属于从 i+1 到 range[i] 均存在 time[j-1] > last[j] 且对于 range[i]+1 不存在 time[j-1] > last[j] 说到这里 大家应该发现求解 range[i]的方法了 若 range[i+1] = t 则对于从 i+2 到 t 前不等式均成立且对于 t+1 不成立 所以我们求解 range[i]只需判断对于 i+1 前不等式是否成立即可 若成立则 range[i] = range[i+1] 不成立则 range[i] = i 若我们修改每个值所减少的时间为 reduce[i] 则 reduce[i] = v[i] + v[i+1] + ... + v[range[i]] v[i]表示到达第 i+1 个车站的人的数量 很明显的 reduce[i] = v[i] + reduce[i+1] 或 v[i] 现在 我们可以用 O(n)的时间求解 reduce 了 然后每次选择一个令 reduce[i]最大的 i 令 d[i]减少即可 注意每次修改 d[i]之后 要重新计算新的 time[i] 时间复杂度 O(kn) 若 d[i] = 0 时则不能再减少 但计算 reduce 和 range 时还要考虑它 这一点要注意


2011noip提高组复赛题解

2011noip提高组复赛题解_学科竞赛_高中教育_教育专区。Noip 2011 提高组 (Day 1) 解题报告及程序 一、铺地毯 正着扫一遍 判断每个矩形是否覆盖询问的点,覆盖则...

NOIP2011提高组复赛试题与简解(转载)

NOIP2011提高组复赛试题与简解(转载)_中考_初中教育_教育专区。NOIP2011提高组...威锋上果然有完全题解啊,第 14 关果然是样例啊有木有!!!人类智力威武, Orz...

NOIP2011提高组解题报告day2

NOIP2011提高组解题报告day2_理学_高等教育_教育专区。noip历届复赛试题及解析 ...NOIP2007提高组解题报告 NOIP2008提高组复赛试题... NOIP2009提高组复赛题解 NOIP...

NOIP2011提高组解题报告day1

NOIP2011提高组解题报告day1_学科竞赛_高中教育_教育...后往前扫,找到第一个覆盖这个点的就输出,否则无解...下面附加几个剪枝 左右交换是等价的,根据题中的顺序...

NOIP2011提高组复赛试题Day1

第 3 页共 6 页 全国信息学奥林匹克联赛(NOIP2011)复赛 提高组 day1 输出只有一行,一个整数,表示可选的住宿方案的总数。 【输入输出样例 1】 hotel.in 5 ...

2008noip提高组复赛题解

2008noip提高组复赛题解_学科竞赛_高中教育_教育专区 暂无评价|0人阅读|0次下载|举报文档2008noip提高组复赛题解_学科竞赛_高中教育_教育专区。NOIP2008 提高组...

2009noip提高组复赛题解

2009noip提高组复赛题解_企业管理_经管营销_专业资料。NOIP2009 提高組複賽試題解題報告 NOIP2009 提高組複賽試題解題報告 一、潛伏者(spy) 問題描述: 給出密文及...

NOIP2011复赛题解

NOIP2011复赛题解_计算机软件及应用_IT/计算机_专业资料。noip2011 普及组解题报告 NOIP2011 普及组解题报告 ——ahbbzeq 2011.11.25 转载请注明来源 一、数字反转...

NOIP 2011 提高组 day1 题解

NOIP 2011 提高组 day1 题解_其它考试_资格考试/认证_教育专区。NOIP2011 题解 铺地毯: 顺序处理每一个长方形, 并判断当前的点是否在长方形内, 并记录尽可能...

NOIP2015提高组解题报告

NOIP2015 提高组解题报告 T1 神奇的幻方【题目大意】 告诉你幻方的构造方法,给...NOIP2011提高组解题报告... 9页 2下载券 NOIP2015复赛提高组day2 6页 1...