显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

灰然如此

Where there is a will, there is a way.

 
 
 
 
 
 

停止更新

2014-7-18 21:48:01 阅读300 评论0 182014/07 July18

  这一博客建立了约有三年,是我高中竞赛生涯所处的地方。日志中RQNOJ的题解占了大多数,POJ分类下也都是些水题,大致概括了我的水平。多数题解不甚完善,入目皆是疮痍,和我竞赛最终的结果相当。如今我已高中毕业,也就不再更新。大学四年里也许会参加ACM,只是居于别处。

作者  | 2014-7-18 21:48:01 | 阅读(300) |评论(0) | 阅读全文>>

素数的求法

2013-1-11 23:44:13 阅读131 评论2 112013/01 Jan11

我在竞赛中求素数一般使用初步优化过的筛法,也就是下面这个:

/*

ID: Sfiction

PROB: prime.3

*/

#include <cstdio>

#include <cmath>

#include <cstdlib>

const long long maxn=20000000;

unsigned char p[maxn/8+10];

int read(long long a)

{

    return p[a/8]&(1<<(a%8));

}

void write(long long a)

{

    p[a/8]|=1<<(a%8);

}

int main()

{

    FILE *red;

    long long t,i,j;

    t=sqrt(maxn);

    red=fopen("prime3.txt","w");

    for (i=2;i<=t;++i)

        if (!read(i))

        {

            fprintf(red,"%I64d\n",i);

            for (j=i*i;j<=maxn;j+=i) write(j);

作者  | 2013-1-11 23:44:13 | 阅读(131) |评论(2) | 阅读全文>>

RQNOJP519 Hankson的趣味题

2012-10-6 16:09:36 阅读306 评论0 62012/10 Oct6

Hanks 博士是BT (Bio-Tech,生物技术) 领域的知名专家,他的儿子名叫Hankson。现在,刚刚放学回家的Hankson 正在思考一个有趣的问题。

今 天在课堂上,老师讲解了如何求两个正整数c1 和c2 的最大公约数和最小公倍数。现在Hankson 认为自己已经熟练地掌握了这些知识,他开始思考一个“求公约数”和“求公倍数”之类问题的“逆问题”,这个问题是这样的:已知正整数 a0,a1,b0,b1,设某未知正整数x 满足:

1. x 和a0 的最大公约数是a1;

2. x 和b0 的最小公倍数是b1。

Hankson 的“逆问题”就是求出满足条件的正整数x。但稍加思索之后,他发现这样的x 并不唯一,甚至可能不存在。因此他转而开始考虑如何求解满足条件的x 的个数。请你帮助他编程求解这个问题。

数学太差了,想了好久才理清楚。

设a0[k]为a0中素因数k的个数。

有a0[k]>=a1[k],b0[k]<=b1[k]。

若a0[k]>a1[k],必有x[k]=a1[k]。

若b0[k]<b1[k],必有x[k]=b1[k]。

若a0[k]==a1[k],必有x>=a1[k]。

若b0[k]==b1[k],必有x[k]<=b1[k]。

具体的各位还是到这儿看看吧,纯数学推导看起来很霸气的样子。

作者  | 2012-10-6 16:09:36 | 阅读(306) |评论(0) | 阅读全文>>

RQNOJP689 拯救海文星

2012-9-4 21:00:03 阅读96 评论0 42012/09 Sept4

海文星(The Heaven Planet)遇到了前所未有的危机!

由于未知宇宙射线的原因,海文星的生态系统开始发生一系列的连锁崩坏,幸 好,科学家们研究出了一台机器,它放出的能量可以中和掉射线的干扰,不过这个机器耗能非常大,而且,据精细测算,这个机器的耗能,与使用时所在位置的海拔 高度成一个(2*N-1)次函数关系,设耗能为关于海拔x的一个函数f(x):

f(x) = a0 + a1 * x + a2 * x^3 + a3 * x^5 + … + an * x^(2*n-1) (a^b表示a的b次方)

其中所有的ai都是非负整数。

不难发现存在一些x,使得f(x)为0,而这些位置正是科学家们所要找到的,现在这个任务交给了你,给定a0..an,求出f(x)所有的零点。

时间限制:1S

空间限制:256MB

【数据范围】

对于20%:N<=1

对于40%:N<=2

对于100%的数据,N<=10000,|ai| <= 10000。保证多项式系数不全是0。

这是RQNOJ2012八月月赛的第一题,我只做出来这一题。

ai都为非负整数,那么除a0之外所有的项都是在R上单调递增的,可以用二分法找到令f(x)=0的x,即令除a0之外所有项之和为-a0。

计算过程需要作一些优化,即使用秦九韶算法将O(n^2)的时间复杂度优化到O(n)。或者直观一些,保存并持续更新x^i的值。

作者  | 2012-9-4 21:00:03 | 阅读(96) |评论(0) | 阅读全文>>

RQNOJP456 低价购买

2012-9-4 20:51:02 阅读222 评论0 42012/09 Sept4

“低价购买”这条建议是在奶牛股票市场取得成功的一半规则。要想被认为是伟大的投资者,你必须遵循以下的问题建议:“低价购买;再低价购买”。每次你购买 一支股票,你必须用低于你上次购买它的价格购买它。买的次数越多越好!你的目标是在遵循以上建议的前提下,求你最多能购买股票的次数。你将被给出一段时间 内一支股票每天的出售价(2^16范围内的正整数),你可以选择在哪些天购买这支股票。每次购买都必须遵循“低价购买;再低价购买”的原则。写一个程序计算最大购买次数

这里是某支股票的价格清单:

日期 1 2 3 4 5 6 7 8 9 10 11 12

价格 68 69 54 64 68 64 70 67 78 62 98 87

最优秀的投资者可以购买最多4次股票,可行方案中的一种是:

日期 2 5 6 10

价格 69 68 64 62

数据规模

对于100%的数据,1 <= N <= 5000。

原题为USACO 4.3.1 buy low,buy lower

核心的最长下降子序列应该没有问题,难点在于方案数的统计。

在扫描[1,i-1]寻找最优解时,如果当前解与已知最优解相同,就进行累加;如果更大,就覆盖之前的结果。对于重复方案的判断,可以比较已知最优解的末尾和和当前解的末尾,两个价格如果相同,那么就不能进行累加,而应该选取更靠后的一个。显然靠后的价格会有不少于靠前价格的方案数,例如序列3,2,3,2,1:

作者  | 2012-9-4 20:51:02 | 阅读(222) |评论(0) | 阅读全文>>

RQNOJP484 扫雷

2012-7-22 12:35:01 阅读261 评论0 222012/07 July22

你玩过扫雷游戏吗?这个有趣的小游戏来自于某个被人们遗忘的操作系统.游戏的目标是找出一个n×m矩阵内的所有地雷.在本题中,你需要为每个单元格统计出 他周围的地雷个数.每个单元格最多有8个相邻的单元格.下图的4×4矩阵中有两个地雷,用'*'表示.计算结果为右边的矩阵:

水题无节操。

第三页了~

/*

ID: Sfiction

OJ: RQNOJ

PROB: 484

*/

#include <cstdio>

#include <cstring>

int N,M,t;

void Work()

{

    char m[102][102];

    int i,j;

    if (t) printf("\n\n");

    printf("Field #%d:",++t);

    for (i=1;i<=N;++i)

        for (getchar(),j=1;j<=M;++j)

        {

作者  | 2012-7-22 12:35:01 | 阅读(261) |评论(0) | 阅读全文>>

RQNOJP199 门票系统

2012-7-22 12:03:46 阅读66 评论0 222012/07 July22

2008年,第31届魁地奇世界杯即将举行。全世界巫师热情高涨,争相订购魁地奇世界杯门票。但门票的总数是有限的,所以魁地奇世界杯举办方将不得不拒绝一部分人的订票请求。为了公平,魁地奇世界杯举办方决定,每个订票者最多只能获得1张门票。而很多人不只订了1张门票,

假设每个人在比赛中预订了1张门票。现在你要做的就是替魁地奇世界杯举办方开发一个订票处理系统,以满足可能多的订票请求。(只要获取1张门票就视为满足请求,每场比赛只有一张票)

标准的最大二分匹配模型,数据不大,用网络流和匈牙利算法均可。

第一次独立写Hungary~

学习匈牙利算法可以去这里:http://www.byvoid.com/blog/hungary/

/*

ID: Sfiction

OJ: RQNOJ

PROB: 199

*/

#include <cstdio>

#include <cstring>

int E[101][301];

int vis[301],mat[301];

int N;

void Init()

{

    int i,j;

    scanf("%d%d",&N,&i);

作者  | 2012-7-22 12:03:46 | 阅读(66) |评论(0) | 阅读全文>>

RQNOJP618 最大正方形面积

2012-7-18 21:00:05 阅读369 评论0 182012/07 July18

给定一个R行C列的01矩阵,求一个最大的正方形全为1的子矩阵,并输出该最大正方形子矩阵的面积。

n,m<=1000

似乎见到过很多次了。通过预处理来减少运算量。f[i][j]表示区间(1,1)-(i,j)中所有格子权值之和。

应该可以通过二分加速。

#include <stdio.h>

int f[1001][1001];

int R,C;

int Find(int k)

{

    int i,j,N;

    N=k*k;

    for (i=k;i<=R;++i)

        for (j=k;j<=C;++j)

            if (f[i][j]+f[i-k][j-k]-f[i][j-k]-f[i-k][j]==N) return 1;

    return 0;

}

int main()

{

    int i,j,k,N;

    scanf("%d%d",&R,&C);

    for (i=1;i<=R;++i)

    {

        for (j=1;j<=C;++j)

        {

            scanf("%d",&f[i][j]);

作者  | 2012-7-18 21:00:05 | 阅读(369) |评论(0) | 阅读全文>>

RQNOJP370 局域网(net)

2012-7-4 1:03:51 阅读116 评论0 42012/07 July4

某个局域网内有n(n<=100)台计算机,由于搭建局域网时工作人员的疏忽,现在局域网内的连接形成了回路,我们知道如果局域网形成回路那么数据 将不停的在回路内传输,造成网络卡的现象。因为连接计算机的网线本身不同,所以有一些连线不是很畅通,我们用f(i,j)表示i,j之间连接的畅通程度 (f(i,j)<=1000),f(i,j)值越小表示i,j之间连接越通畅,f(i,j)为0表示i,j之间无网线连接。现在我们需要解决回路问 题,我们将除去一些连线,使得网络中没有回路,并且被除去网线的Σf(i,j)最大,请求出这个最大值。

很水的一道题,几乎和裸模板题一样了。

目标网络中无回路,那么这应该是一棵有N-1条边的树了。出去网线的权值和最大,说明剩下树的权值之和应当尽可能小。用一般的最小生成树算法即可解决。

虽然程序提交后没有出错,但是题目中并未指出原网络是连通图,算是一个疏漏。

/*

ID: Sfiction

OJ: RQNOJ

PROB: 370

*/

#include <stdio.h>

int main()

{

    int E[101][101],V[101],P[101]={0};

    int i,j,t,N,K,f=1<<26,S=0;

    scanf("%d%d",&N,&K);

作者  | 2012-7-4 1:03:51 | 阅读(116) |评论(0) | 阅读全文>>

RQNOJP216 Car的旅行路线

2012-6-22 18:25:24 阅读204 评论0 222012/06 June22

又到暑假了,住在城市A的Car想和朋友一起去城市B旅游。她知道每个城市都有四个飞机场,分别位于一个矩形的四个顶点上,同一个城市中两个机场之间有一 条笔直的高速铁路,第I个城市中高速铁路了的单位里程价格为Ti,任意两个不同城市的机场之间均有航线,所有航线单位里程的价格均为t。

那么Car应如何安排到城市B的路线才能尽可能的节省花费呢?她发现这并不是一个简单的问题,于是她来向你请教。

找出一条从城市A到B的旅游路线,出发和到达城市中的机场可以任意选取,要求总的花费最少。

NOIP2001TG4。

最短路问题。我用了Floyd,比较冒险。另外一种方法是做4遍单源最短路。还有一种神法……起点城市四个机场之间路径权值全置为0,一遍单源最短路即可。

确定矩形第三个点的位置:找到距离最大的一对点,这对点应当是一条对角线的端点,它们的中点就是矩形两对角线的交点了。

/*

ID: Sfiction

OJ: RQNOJ

PROB: 216

*/

#include <stdio.h>

#include <math.h>

double E[400][400],x[400],y[400],t,w;

int k;

void Init()

{

    double u[4],v[4],r=0;

作者  | 2012-6-22 18:25:24 | 阅读(204) |评论(0) | 阅读全文>>

查看所有日志>>

 
 
 
 
 
 
 
 

四川省 德阳市

 发消息  写留言

 
Dormancy
 
近期心愿在OI的道路上前进。
博客等级加载中...
今日访问加载中...
总访问量加载中...
最后登录加载中...
 
 
 
 
 
 
 
心情随笔列表加载中...
 
 
 
 
 
 
 
模块内容加载中...
 
 
 
 
 

日志分类

 
 
日志分类列表加载中...
 
 
 
 
 

归档

 
 
数据加载中...
 
 
 
 
 

标签

 
 
数据加载中...
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018

注册 登录  
 加关注