大连2011ACM网络赛【5道水题总结】……很黄很暴力

基德KID.1412

KIDx 的解题报告



http://acm.hdu.edu.cn/listproblem.php?vol=31

4001：直接一个最长递增子序列模板，注意数据范围就可以了


#include <iostream>#include <algorithm>using namespace std;#define L __int64#define M 1005struct block{    L a, b, c, d;}x[M];L dp[M];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[j].d == 0 && x[j].a >= x.a && x[j].b >= x.b ||                    x[j].d == 1 && x[j].a >= x.a && x[j].b >= x.b && x[j].a*x[j].b > x.a*x.b ||                    x[j].d == 2 && x[j].a > x.a && x[j].b > x.b)                    if (dp[j] < dp+x[j].c)                        dp[j] = dp+x[j].c;            }        }        printf ("%I64d\n", *max_element (dp, dp+n));    }    return 0;}

4002：猥琐打表找规律+大数乘法，Java暴力水过


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[60], tp, n;        int hash[] = new int[300], 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[k] = BigInteger.valueOf(i);                k++;                for (j = i * 2; j < 242; j += i)                    hash[j] = 0;            }        }        for (i = 1; i < k; i++)            prime = prime.multiply(prime[i-1]);        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[i-1]);        }    }}

4004：二分枚举答案+暴力检验


#include <iostream>#include <algorithm>using namespace std;#define M 500005int x[M], v[M];int main(){int L, n, m, i, k, maxs, l, r, mid, num, tp;while (~scanf ("%d%d%d", &L, &n, &m)){x[0] = 0;for (i = 1; i <= n; i++)scanf ("%d", x+i);sort (x, x+n+1);x[n+1] = L;k = maxs = 0;for (i = 1; i < n + 2; i++){v[k++] = x - x[i-1];if (v[k-1] > maxs)maxs = v[k-1];}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：优先队列暴力水过


#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[3];    while (~scanf ("%d%d", &n, &k))    {        priority_queue<Int> q;        while (n--)        {            scanf ("%s", ch);            if (ch[0] == '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：最暴力的解法，相信没有人能够破我记录----史上最慢

先优先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[M], tp[M];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[j].x > rx)                    break;                if (p[j].x >= lx && p[j].x <= rx)                    tp[x++] = p[j];            }            sort (tp, tp+x, cmp2);            for (j = 0; j < x; j++)            {                ry = tp[j].y;                ly = ry - R;                tmp = 0;                for (k = 0; k < x; k++)                {                    if (tp[k].y > ry)                        break;                    if (tp[k].y >= ly && tp[k].y <= ry)                        tmp++;                }                if (tmp > maxs)                    maxs = tmp;            }        }        printf ("%d\n", maxs);    }    return 0;}