大连2011ACM网络赛【5道水题总结】……很黄很暴力
KIDx 的解题报告http://dl.iteye.com/upload/attachment/549202/25e5a98b-f15a-3820-93b6-bb9278333409.png
http://acm.hdu.edu.cn/listproblem.php?vol=31
4001：直接一个最长递增子序列模板，注意数据范围就可以了
http://dl.iteye.com/upload/attachment/591362/5864fbcb-5570-3b6d-bf92-2069bd4f2cba.png
#include <iostream>#include <algorithm>using namespace std;#define L __int64#define M 1005struct block{ L a, b, c, d;}x;L dp;bool cmp (block x, block y){ if (x.a == y.a) { if (x.b == y.b) return x.d > y.d; return x.b < y.b; } return x.a < y.a;}int main(){ int n, i, j; while (scanf ("%d", &n), n) { for (i = 0; i < n; i++) { scanf ("%I64d%I64d%I64d%I64d", &x.a, &x.b, &x.c, &x.d); if (x.a < x.b) x.a ^= x.b, x.b ^= x.a, x.a ^= x.b; } sort (x, x+n, cmp); for (i = 0; i < n; i++) dp = x.c; for (i = 0; i < n; i++) { for (j = i + 1; j < n; j++) { if (x.d == 0 && x.a >= x.a && x.b >= x.b || x.d == 1 && x.a >= x.a && x.b >= x.b && x.a*x.b > x.a*x.b || x.d == 2 && x.a > x.a && x.b > x.b) if (dp < dp+x.c) dp = dp+x.c; } } printf ("%I64d\n", *max_element (dp, dp+n)); } return 0;}
4002：猥琐打表找规律+大数乘法，Java暴力水过
http://dl.iteye.com/upload/attachment/591364/ac5b9275-7a77-3c93-b1e7-09dfdb3877a4.png
import java.util.*;import java.io.*;import java.math.*;public class Main{ static public void main(String[] args) throws IOException { Scanner cin = new Scanner(new BufferedInputStream(System.in)); BigInteger prime[] = new BigInteger, tp, n; int hash[] = new int, k, i, j, num, t; for (i = 0; i < 300; i++) hash = 1; k = 0; for (i = 2; i < 242; i++) { if (hash == 1) { prime = BigInteger.valueOf(i); k++; for (j = i * 2; j < 242; j += i) hash = 0; } } for (i = 1; i < k; i++) prime = prime.multiply(prime); t = cin.nextInt(); while (true) { if (t == 0) break; t--; n = cin.nextBigInteger(); for (i = 0; i < k; i++) if (n.compareTo(prime) == -1) break; System.out.println(prime); } }}
4004：二分枚举答案+暴力检验
http://dl.iteye.com/upload/attachment/591366/57e9d60f-f075-34e3-b436-d6e6538d00d8.png
#include <iostream>#include <algorithm>using namespace std;#define M 500005int x, v;int main(){int L, n, m, i, k, maxs, l, r, mid, num, tp;while (~scanf ("%d%d%d", &L, &n, &m)){x = 0;for (i = 1; i <= n; i++)scanf ("%d", x+i);sort (x, x+n+1);x = L;k = maxs = 0;for (i = 1; i < n + 2; i++){v = x - x;if (v > maxs)maxs = v;}l = maxs, r = L;while (l < r){tp = num = 0;mid = (l + r) / 2;for (i = 0; i < k; i++){if (tp + v > mid)num++, tp = v;else tp += v;}num++;if (num <= m)r = mid;else l = mid + 1;}printf ("%d\n", r);} return 0;}
4006：优先队列暴力水过
http://dl.iteye.com/upload/attachment/591360/7a35027c-acc9-3d5a-a316-ee8cfaf07778.png
#include <iostream>#include <queue>using namespace std;struct Int{ int v; friend bool operator < (Int a, Int b) { return a.v > b.v; }};int main(){ Int tp; int n, x, k; char ch; while (~scanf ("%d%d", &n, &k)) { priority_queue<Int> q; while (n--) { scanf ("%s", ch); if (ch == 'Q') { while (q.size() > k) q.pop(); printf ("%d\n", q.top().v); } else { scanf ("%d", &x); tp.v = x; q.push (tp); } } } return 0;}
4007：最暴力的解法，相信没有人能够破我记录----史上最慢http://dl.iteye.com/upload/attachment/549230/2551a8b6-cdbd-3bc2-b680-5a2597cc3030.gif
http://dl.iteye.com/upload/attachment/591358/f1dde3c2-5716-3124-b737-cc5f68443616.png
先优先sort-x坐标，再枚举2条垂直于x轴的扫描线，再从p数组中筛选出在这2条扫描线中的x个点入tp数组，然后优先sort-y坐标，再枚举2条垂直于y轴的扫描线，再从tp数组中筛选出在这2条扫描线中的tmp个点，就是4条扫描线所围成的正方形里的点的个数
#include <iostream>#include <algorithm>using namespace std;#define M 1005struct point{ int x, y;}p, tp;bool cmp (point a, point b){ if (a.x == b.x) return a.y < b.y; return a.x < b.x;}bool cmp2 (point a, point b){ if (a.y == b.y) return a.x < b.x; return a.y < b.y;}int main(){ int n, R, i, j, k, lx, rx, ly, ry, x, maxs, tmp; while (~scanf ("%d%d", &n, &R)) { for (i = 0; i < n; i++) scanf ("%d%d", &p.x, &p.y); sort (p, p+n, cmp); maxs = 0; for (i = 0; i < n; i++) { rx = p.x; lx = rx - R; x = 0; for (j = 0; j < n; j++) { if (p.x > rx) break; if (p.x >= lx && p.x <= rx) tp = p; } sort (tp, tp+x, cmp2); for (j = 0; j < x; j++) { ry = tp.y; ly = ry - R; tmp = 0; for (k = 0; k < x; k++) { if (tp.y > ry) break; if (tp.y >= ly && tp.y <= ry) tmp++; } if (tmp > maxs) maxs = tmp; } } printf ("%d\n", maxs); } return 0;}
页:
[1]