`

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

阅读更多
KIDx 的解题报告



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

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


#include <iostream>
#include <algorithm>
using namespace std;
#define L __int64
#define M 1005

struct 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[i].a, &x[i].b, &x[i].c, &x[i].d);
            if (x[i].a < x[i].b)
                x[i].a ^= x[i].b, x[i].b ^= x[i].a, x[i].a ^= x[i].b;
        }
        sort (x, x+n, cmp);
        for (i = 0; i < n; i++)
            dp[i] = x[i].c;
        for (i = 0; i < n; i++)
        {
            for (j = i + 1; j < n; j++)
            {
                if (x[j].d == 0 && x[j].a >= x[i].a && x[j].b >= x[i].b ||
                    x[j].d == 1 && x[j].a >= x[i].a && x[j].b >= x[i].b && 
x[j].a*x[j].b > x[i].a*x[i].b ||
                    x[j].d == 2 && x[j].a > x[i].a && x[j].b > x[i].b)
                    if (dp[j] < dp[i]+x[j].c)
                        dp[j] = dp[i]+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[i] = 1;
        k = 0;
        for (i = 2; i < 242; i++)
        {
            if (hash[i] == 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[i] = prime[i].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[i]) == -1)
                    break;
            System.out.println(prime[i-1]);
        }
    }
}


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


#include <iostream>
#include <algorithm>
using namespace std;
#define M 500005

int 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[i] - 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[i] > mid)
					num++, tp = v[i];
				else tp += v[i];
			}
			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 1005

struct 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[i].x, &p[i].y);
        sort (p, p+n, cmp);
        maxs = 0;
        for (i = 0; i < n; i++)
        {
            rx = p[i].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;
}
  • 大小: 10.9 KB
  • 大小: 4.5 KB
  • 大小: 6.2 KB
  • 大小: 5.9 KB
  • 大小: 6 KB
  • 大小: 6 KB
  • 大小: 6 KB
4
2
分享到:
评论
1 楼 gzhu_101majia 2011-09-07  
  

相关推荐

    2011ACM黑龙江大学校赛

    2011ACM黑龙江大学校赛2011ACM黑龙江大学校赛2011ACM黑龙江大学校赛2011ACM黑龙江大学校赛2011ACM黑龙江大学校赛2011ACM黑龙江大学校赛

    2009ACM合肥赛区网络赛试题

    知识点:2009ACM合肥赛区网络赛试题——Another Door Repairing Problem 在深入解析这一问题之前,我们首先理解一下ACM/ICPC(Association for Computing Machinery / International Collegiate Programming ...

    沈阳2015acm区域赛B题

    2015年沈阳acm-icpc区域赛B题代码,自己练手,神牛勿喷

    ACM练习题ACM各种练习题ACM各种练习题ACM各种练习题

    ACM各种练习题ACM各种练习题ACM各种练习题ACM各种练习题ACM各种练习题ACM各种练习题ACM各种练习题ACM各种练习题ACM各种练习题ACM各种练习题ACM各种练习题ACM各种练习题ACM各种练习题ACM各种练习题ACM各种练习题ACM...

    2020ZJCPC_2020年_2020浙江acm省赛_省赛题目_浙江ACM_

    这个PDF文件很可能是2020年浙江省ACM省赛的试题集,包括题目描述、输入输出格式、样例测试用例等详细信息。参赛者和学习者可以通过阅读这些题目,了解当年比赛的难度水平,同时也能作为训练材料,提高自己的算法...

    09年ACM武汉大学网络赛试题

    【标题】"09年ACM武汉大学网络赛试题"涉及的是ACM(国际大学生程序设计竞赛,简称ICPC)的网络赛部分,这是一场由武汉大学主办的编程竞赛。ACM比赛是全球范围内影响力极大的编程竞赛,旨在锻炼大学生的算法设计、...

    第33届ACM亚洲区预选赛(杭州赛区)_网络选拔赛.rar

    【标题】"第33届ACM亚洲区预选赛(杭州赛区)_网络选拔赛"是针对ACM(国际大学生程序设计竞赛)的一次重要赛事,该赛事在亚洲区的预选赛中设定了杭州赛区的网络选拔环节。ACM比赛是全球范围内极具影响力的编程竞赛,...

    ACM考试题 ACM程序设计

    ### ACM程序设计基础知识点 #### 一、ACM竞赛概览 - **组织机构与活动**: 本课程由东北林业大学陈宇老师负责,通过邮箱Lg_chenyu@yahoo.com.cn进行联系。课程的主要目的是介绍ACM程序设计的基础概念及入门技巧。 - ...

    ACM程序设计培训教程

     15.6 应用…………………………………………………………………………………………………………227  〖案例l〗果园篱笆………………………………………………………………227  〖案例2〗巨人和鬼………………...

    北大ACM题库(3000多道题)

    北京大学ACM题库是编程竞赛领域的一份宝贵资源,包含了超过3000道精心设计的编程题目。这些题目旨在帮助参赛者提升算法设计、逻辑思维以及问题解决能力,尤其对于那些希望在ACM(国际大学生程序设计竞赛,...

    2010ACM选拔赛2010ACM选拔赛

    【标题解析】:“2010ACM选拔赛2010ACM选拔赛” 这个标题显然是指2010年举办的一场ACM(国际大学生程序设计竞赛,International Collegiate Programming Contest,简称ICPC或ACM/ICPC)的选拔赛,可能是一个地区性的...

    zjp2018_problems_ACM省赛题目_浙江2018年_

    《2018年浙江省ACM省赛题目解析与探讨》 2018年浙江省ACM省赛作为第十五届此类竞赛,吸引了众多编程爱好者和学子参与。ACM(国际大学生程序设计竞赛,International Collegiate Programming Contest)是全球极具...

    2008 ACM 内蒙古试题

    2008年的内蒙古赛区ACM赛事提供了丰富的编程挑战,共计十题,涵盖了算法、数据结构和逻辑推理等多个领域。 在这样的比赛中,参赛者需要快速理解问题描述,设计并实现高效算法,通常使用C、C++或Java等编程语言。...

    2008ACM浙江省赛解题报告

    【2008 ACM浙江省赛解题报告】涵盖了两道ACM竞赛中的编程问题,分别是“Accurately Say”Cocacola”!”和“Build The Electric System”。 第一题:“Accurately Say”Cocacola”!” 这是一道简单的预处理题目。...

    ACM_竞赛试题

    在 ACM 竞赛试题中,对于参加各种比赛,特别是 ACM 大赛的人会有很大帮助。以下是关于 ACM 竞赛试题和算法原理的知识点概述: 一、ACM 竞赛试题简介 ACM 竞赛试题是 ACM 大赛的主要组成部分,对于参加各种比赛,...

    ACM-ICPC 历年竞赛 真题,各大赛区真题详解

    同时,这份详解可能还包含了对历年题目的分类、解析以及解题技巧的总结,对于准备参加ACM-ICPC或者提升编程技能的人来说,是一份不可或缺的学习材料。 **真题解析的价值** 学习和研究ACM-ICPC的历年真题不仅可以...

    2009年ACM程序设计竞赛选拔赛试题

    【ACM程序设计竞赛选拔赛试题】是一类旨在考察参赛者编程能力的比赛,涉及的知识点广泛,主要包括: 1. **程序设计语言基础** - 试题规定必须使用C或C++语言,强调了对这两种语言的基本语法和编程技巧的掌握。 2. ...

    蓝桥杯ACM算法比赛模拟题30天每日训练.zip

    "蓝桥杯ACM算法比赛模拟题30天每日训练.zip"这个压缩包文件是针对蓝桥杯ACM算法比赛的训练资源,旨在帮助参赛者进行为期30天的日常练习,以提升他们的编程和算法解决能力。蓝桥杯是一项国内知名的编程竞赛,主要考察...

    中山大学acm比赛试题

    中山大学ACM比赛试题是计算机科学领域中一项重要的学习资源,尤其对于那些热衷于算法设计、编程竞赛和计算机科学教育的学生来说。ACM(国际大学生程序设计竞赛,International Collegiate Programming Contest)是一...

Global site tag (gtag.js) - Google Analytics