SQYBI.com

Change is a part of life, and takes part in finding us who we are.

2008年08月22日
by sqybi
0 comments

UVa 102 -- Ecological Bin Packing

水题,枚举即可.
第一次提交WA,没有注意这道题并不是Special Judge,如果有多组顺序符合要求,需要输出字典序最靠前的一组.
虽然用了string,不过代码写的还是很垃圾.

/*
  UVa 102; Ecological Bin Packing
  - sqybi's code
*/
//for my winsty

#include
#include
using namespace std;

const int nn = 3;
int t, res, now;
int a[nn][nn];
bool u[nn];
char ch[nn] = {'B', 'G', 'C'};
string ress, nows;

void get(int i)
{
    if (i == 3)
    {
        if (now > res || (now == res && nows < ress))
        {
            res = now;
            ress = nows;
        }
        return;
    }
    for (int j = 0; j != 3; ++ j)
        if (! u[j])
        {
            u[j] = true;
            now = now + a[i][j];
            nows += ch[j];
            get(i+1);
            nows = nows.erase(i, 1);
            now = now - a[i][j];
            u[j] = false;
        }
}

int main()
{
    while (scanf("%d", &a[0][0]) != EOF)
    {
        t = a[0][0];
        for (int i = 0; i != 3; ++ i)
            for (int j = 0; j != 3; ++ j)
                if (i + j)
                {
                    scanf("%d", &a[i][j]);
                    t += a[i][j];
                }
        res = 0;
        now = 0;
        nows = "";
        memset(u, false, sizeof(u));
        get(0);
        cout << ress << ' ' << t - res << endl;
    }
}

2008年08月22日
by sqybi
5 Comments

UVa 100 -- The 3n + 1 problem

经典的3n+1,没有想到这道题调了一个晚上.
Project Euler上看过这道题,于是按照那道题写了个部分DP.然后诡异的WA了.
调啊,调啊,只找到了一个trick:输入的两个数不一定小数在前大数在后.
然后呢,我这个程序是search,可加了一个预处理,for i=1~10000 do dp[i]=f(i),然后调用f(i)的地方改成dp[i],就过不了,都鬼了...怀疑数据范围有问题.

search可以1s过掉.

/*
  UVa 100; The 3n + 1 problem
  - sqybi's code
*/
//for my winsty

//#define DEBUG
#include
using namespace std;

const int nn = 1000001, mm = 10001;
int l, r, ll, rr, maxa;

int f(int i)
{
    if (i == 1)
        return 1;
    else if (i % 2)
        return f(i*3+1)+1;
    else
        return f(i/2)+1;
}

int main()
{
    #ifdef DEBUG
    freopen("uva100.in", "r", stdin);
    freopen("uva100.out", "w", stdout);
    #endif

    while (scanf("%d%d", &ll, &rr) != EOF)
    {
        l = ll;
        r = rr;
        if (l > r) swap(l, r);
        maxa = 0;
        for (int i = l; i <= r; ++ i)
            if (f(i) > maxa) maxa = f(i);
        printf("%d %d %d\n", ll, rr, maxa);
    }
}

2008年08月17日
by sqybi
10 Comments

ZOJ Monthly August 2008 and SRM 414 and dd's Contest

今天做了两场比赛,ZOJ Monthly和SRM.
总体感觉还是不错,coding速度有待提高.思路准确性不够.coding准确性尚可.
ZOJ去晚了,做了几道弱智题,拿了rank 60.其实早去半小时,就能top 25了...
ZOJ月赛好多人组队参加...下次考虑和jl等人组个队.
SRM,基本发挥水平,250+500全部Pass,可惜250和500开始想的都有问题,加上我C++的coding速度很慢,最后加起来也不到500分.我那个room都是强人,六个red...于是cha人的时候,打开一个代码,就提示我这个已经被cha了,再打开一个,又提示...最后一个代码也没看完就都cha干净了...现在rating是1671,涨得不多...

对了,还有dd的一个模拟赛,那个我写了三道题的标程.交到TOI的时候,第三题又因为%lld和%I64d的问题挂掉了...我忘了TOI是Linux系统,直接交了%I64d...

ZOJ Monthly

中午去图书大厦,下午回到家,winsty告诉我有月赛...然后那时候人家都比了一半了.
这次月赛是ZOJ内部集训的题目,于是某道题我就得利了...可是重写的程序精度还是出了问题,最后2Y掉.就是1008题,这题AC率好低...传说中的万人坑.
然后1006,1002和1001都1Y掉了.

1008
这题注意精度,十分注意精度...没别的了.

1006
统计每个数在a和b中分别出现的次数,然后对每个数对应的两个次数取个最小值,最后把这些最小值都+起来.用了map和迭代器,STL果然好用.

1002
小学奥数题,竟然想了半天没想出来...后来MM群里有人提醒我(HL牛?),就是那个一个人牵着一匹马(一头驴也一样...)从A走到B途中要去河里喝水...问最短路径...后来又扯到Fermat原理...但不管怎么说,就是作(b, 0)关于三角形那条斜边的对称点...然后对称点和(0, a)连线,求出这条连线与斜边的交点,就是反射点...没有精度问题.

1001
写个暴力,跑,然后打表...dd的题目真恶搞...

SRM 414 Div 1

第一次做Div 1,题目还不是很难.

250
这道题一开始想复杂了,一直在想怎么处理第一个表格从一天的什么时刻开始填的问题...后来发现一天最多有10^6个时刻,于是直接枚举...然后最后Pass掉.很囧...这道题白白掉了一大半的分数.

500
这道题开始想的就是正确的,贪心.可是细节处理出了问题.
算法是每个string记录当前取到了哪个字母,每次取字典序最小的一个字母.
细节上,当两个字符串当前字母一样的时候,需要比较剩余后缀的字典序.注意abc比abcd的字典序靠后,而不是一般我们认为的靠前.
一度以为时间复杂度太高会被cha,事实证明pass了.

dd_engi的NOIP模拟赛

题目难度适中.dd的题质量还是不错的.

生命游戏
纯模拟...没什么可说的,判断的时候注意边界.还有n和m的输入顺序,是先m后n.

正则表达式简化版
还是模拟...很恶心的题,这题我没写标程.

魔法塔防
这套题最有意思的一道题!很容易想到n^3的DP,其实只需要证明一点:红色的一定在最后.尝试反证法.

公司聚会
很裸的Tree DP.我写了多叉转二叉,不过dd的标程写法很独特.详情请期待dd的题解.

2008年08月15日
by sqybi
11 Comments

TopCoder SRM 413

Div 2果然是水题.第一次SRM,变黄.
yuhch不好好出题啊...
此文测试插件用 有爱者可以忽略

第一题,纯水.贴TC的标程:

double minTime(int length, int maxAcceleration, int maxVelocity) {
  double t1 = sqrt(length / double(maxAcceleration));
  if(maxAcceleration * t1 > maxVelocity) {
    double t2 = maxVelocity / double(maxAcceleration);
    return (length - maxAcceleration * t2 * t2) / maxVelocity + 2 * t2;
  } else
    return 2 * t1;
}

第二题,我的做法是求解一大堆不等式:
假设给出了a0,a1,a2,...其中a1,a2...分别等于[a1],[a2]...,那么
a1-a0<=d<a1-a0+1
a2-a0<=2*d<a2-a0+1
...
TC给出的代码如下:

double minCommonDifference(int a0, vector  seq) {
  // fraction representing 0/1 (minimum permissible value)
  pair  res(0, 1);
  // find d
  for(int i = 0; i < seq.size(); ++i)
    if(res.first * (i + 1) < (seq[i] - a0) * res.second) {
      res.first = seq[i] - a0;
      res.second = i + 1;
    }
  // check whether a solution is possible
  for(int i = 0; i < seq.size(); ++i)
    if(seq[i] != a0 + (i + 1) * res.first / res.second)
      return -1;
  return res.first / double(res.second);
}

出现问题了...先测试到这里

刚才看了一下,Zoundry瞎改HTML.没办法,以后只能到blog后台来写了...装个增强的WYSIWYG插件去...

update:WLW竟然可以用!没想到啊.
继续写完.

第三题看似范围很大,实际用到的状态并不多,所以开一个map做记忆化搜索就解决问题.继续贴TC的代码:

map  mem;
long long calc(long long n, int p, int q) {
  if(n == 0)
    return 1;
  if(mem.count(n))
    return mem[n];
  mem[n] = calc(n / p, p, q) + calc(n / q, p, q);
  return mem[n];
}

这次题目就这样,很水了...
WLW似乎也把line参数给吞了...泪奔...

关闭了可视化编辑器,希望这次能行...
以后就得这么发代码了...

2008年08月15日
by sqybi
0 comments

2008.08.14

此文使用Zoundry Raven发布.据巫山霏云牛说Zoundry Raven不错,于是尝试一下.

今天一天一直在搞这个blog.中午11点左右起床,看到昨天晚上一键安装的WP装好了,然后开始搞Logo和首页.找wh做了个flash,然后自己照猫画虎又做了一个.发现Flash也挺简单.
接下来就是装插件,装主题.一直到安装全部结束都很顺利.

不过调试的部分可就没那么容易了.

出现了种种的问题,比如windywinter所说的在Firefox下变形,本机测试却没有问题.后来发现是因为主题的CSS大部分用了em,于是调整默认字体大小之后,整个主题的各个地方大小就都改变了.更要命的是竟然还有部分地方写了pt,于是大脑崩溃...用了好长时间把所有非字体的em都改成px,终于测试通过.
另外首页的Flash弹出窗口被Firefox拦截的情况,至今不知如何处理.如果哪位大牛知道请留言.

然后评论插件又出现问题,reply的时候总是reply到最下方而不是被reply的评论的下一层(我的插件是可以分层评论的).实在调的恶心了只好关掉,这时才发现我开了两个评论的插件...泪奔...重新启用其中一个,问题解决.Ajax还很好用.

接下来改CSS,把链接的下划线去掉.依然是人工改,一个一个把underline改成none,问题解决.
另外有一些比如页面评论的问题,已经被我忽视掉了.

最后还剩下一个未解决的问题,那就是wp-syntax插件.下一篇文章是SRM 413的总结.由于Div 1的1000不会,250和500跟Div 2的500和1000如出一辙,所以只总结Div 2的三道水题.主要为了测试插件用,所以那篇文章基本可以忽略.
P.S.刚才下载了Semagic,一会儿用它试试.