SQYBI.com

前几天 blog 挂掉了, 当时就想到了可能是 sql 数据库地址的问题. 但是 ftp 一直登不上, 我这儿上网又不是很方便, 昨天才把两个问题一并提交到客服, 然后虽然 ftp 的问题还没解决, 但是第一个问题确定了是 sql 数据库地址有问题, 客服也帮我在他那边改过了. 然后今天用速度有点慢的 webftp 装了个新的 wordpress 2.8, 折腾了一下午总算弄完了.

最近训练还好, 具体就不多说了. 然后已经得到了通知, 要 8 月 10 号左右才能回去, 到时候不知道还有多少人没玩腻…
过几天事情很多, ACM 班的面试, 提前入校的期末考试, ACM 队的训练, 加上现在还不知道要搬到哪个宿舍, 于是能预计到过几天的忙乱. 而原先定的 7 月回去一趟的目标, 估计是实现不了了.

这几天上海突然热起来了, 貌似 N 多人都是半夜两三点睡不着觉… 我今天也是凌晨 3 点才睡着的. 还好的是, 白天一直有 ACM 机房可以泡. 貌似大多数人都在泡图书馆, 不过 ACM 机房里有空调, 加上人比图书馆少, 所以还是这里好. 某人语: 早知道我就去考 ACM 队了…
电脑前几天显卡挂掉了, 跑到徐家汇去修. 然后第一天送过去修, 回来的时候淋了一身的雨, 第一次知道了啥叫落汤鸡= =||. 第二天去取, 中午去的, 然后第一次知道了啥叫热的要死… 回到宿舍之后喝了三四瓶水跟没喝一样… 不过还好电脑现在正常了, 花了 600 多块钱啊, 我电脑现在卖都不一定能卖这个价…

然后今天做了做 UVa, 换了个新 ID. 把那个推荐列表里整百的题都做了, 结果发现没有一道题不是水题, 晕死…

别的也没啥了, 最近貌似比较多愁善感, 不管怎样还是像我所说的, 你们真的不会明白我有多想你们的, 我也不会明白.
回去的时候还能不能去以前的教室看看呢…

水题,枚举即可.
第一次提交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;
    }
}

经典的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);
    }
}

本来一直就没关注过UVa,甚至连用户都没有注册过.昨天在sjtu的网站上到处瞎逛,偶然看到了一个做题计划.分为两档,一个是初学者,一个是进阶.初学者那个推荐了USACO,被我直接忽略掉.不过那个进阶吸引了我,那里面推荐了UVa的200道题.

想想以后进入sjtu说不定也要做题,于是干脆这段时间就刷UVa这些题算了.
决定启动UVa Plan.

SGU的刷题计划已然结束,50多题显然不是我想要的.希望这次能坚持的更长(我不奢望我能完成这200道题的计划).
语言用C++.
每道题都会在这里发布题解,订阅Feed的童鞋们会比较痛苦,请原谅我…

sjtu推荐的200道题及我的完成情况(随时更新):
http://sqybi.com/blog/plan