CSU-OJ补完计划(一,10xx)

20170209

虽然好几年来一直是CSU-OJ的super admin,但是退役后就没怎么管OJ了,都是每年的在役队员在加题。不同人对学校OJ的理解不同,有的当对外交流的窗口,有的只是当一个内部的训练工具,导致部分题目残缺、题号不连续等许多问题。多年不做题也怕手生了挺可惜的,打算业余时间偶尔刷几题,把OJ题目重新整理下,调调字体,补补图之类的,顺便做个完整题解。不知道能不能坚持下去,先挖坑吧。

20170222

OJ丑得看不下去了……重做了一个,近期上线吧。


20170307

OJ、主页、报名系统三个网站合并到一起做了个新网站,已上线。 日志留念 CSU-ACM Home Page


1015: 机器人训练

20170316

把每两个点之间的移动,都分解成一横一竖两个移动,两个移动相互独立,只需要关心移动前后面对的方向,这样思路会清晰许多。

每一步从一个箭头末端去下一个箭头始端,无非都是走一个“L”,只有一个决策不同,先横着还是先竖着,受前后两个箭头方向的影响会有不同的转弯次数。但是不必分类讨论,都走一走试试就好了,只需要调一下分解后的横竖移动的顺序,纯粹模拟即可,稍注意下点重合的情况。

1014: 西湖三人行

20170316

先想到的思路是直接DP,dp[cost][status][site],当前花费、状态(行走、在哪个公交上、在出租上且走了几公里,超过3公里按3公里算)、当前站点,优化的是走的时间。 这个思路的问题是,虽然dp的状态空间是 101*204*100,但是每次更新状态还有100数量级的边遍历,这样就行不通了。然而这个方法却水过去了。

更好的方法状态空间是dp[cost][site],省去status这一维,需要预处理建图。根据三种交通方式,统一地建成一个点到点的距离+花费的无差别图。

首先是bus,因为公交不会抄近道,如果路线是3->4->5,它不会因为3->6->5更近就绕道,对bus线路上所有能一次性到达的两点都建一条边。

bus之后,就可以Floyd了,因为走路和出租车都是选最短路走的。Floyd之后对任意两点按直达建边。

这样建图在DP时候不需要考虑“当前状态”,比如出租车,都 只考虑起点发车 ,如果不是起点发车, 自然有其他的点建了直达边

如此得到了一个有重边的,每条边有距离、花费两个边权的链式图。接下来就可以DP了。最短路做DP也可以,不过多此一举,干净的DP就好。

#include<stdio.h>
#include<string.h>
#include<algorithm>
const int maxn = 111;
const int maxm = 30011;
const int MAXNUM = 0x3f3f3f3f;
int L, N, M, S, T, B;
int hz[maxn][maxn];
int bus[maxn];
int fst[maxn], nex[maxm], v[maxm], w[maxm], cost[maxm];
int ntp;
int dp[105][maxn];
inline void AddEdge(int s, int t, int len, int c)
{
    nex[ntp] = fst[s];
    v[ntp] = t;
    w[ntp] = len;
    cost[ntp] = c;
    fst[s] = ntp ++;
}
void Floyd()
{
    for(int i = 1; i <= N; i ++)
        for(int j = 1; j <= N; j ++)
            for(int k = 1; k <= N; k ++)
                hz[i][j] = std::min(hz[i][k] + hz[k][j], hz[i][j]);
}
int DPS(int costNow, int siteNow)
{
    if(costNow > L) return MAXNUM;
    int &ans = dp[costNow][siteNow];
    if(ans != -1) return ans;
    if(siteNow == T) return ans = 0;
    ans = MAXNUM;
    for(int i = fst[siteNow]; i != -1; i = nex[i])
    {
        ans = std::min(ans, DPS(costNow + cost[i], v[i]) + w[i]);
    }
    return ans;
}
int main()
{
    int t, s, e, len, ans;
    int K;
    for(scanf("%d", &t); t --; )
    {
        memset(fst, -1, sizeof(fst));
        memset(hz, 0x3f, sizeof(hz));
        memset(dp, -1, sizeof(dp));
        ntp = 0;
        scanf("%d%d%d%d%d%d", &L, &N, &M, &S, &T, &B);
        for(int i = 0; i < M; i ++)
        {
            scanf("%d%d%d", &s, &e, &len);
            hz[s][e] = hz[e][s] = len;
        }
        for(int i = 1; i <= B; i ++)
        {
            scanf("%d", &K);
            for(int j = 0; j < K; j ++)
            {
                scanf("%d", &bus[j]);
                int last = j, tmpLen = 0;
                for(int k = j - 1; k >= 0; last = k --)
                {
                    tmpLen += hz[bus[last]][bus[k]];
                    AddEdge(bus[k], bus[j], tmpLen * 250, 6);
                }
            }
        }
        Floyd();
        for(int i = 1; i <= N; i ++)
            for(int j = 1; j <= N; j ++)
            {
                if(hz[i][j] != MAXNUM)
                {
                    AddEdge(i, j, hz[i][j] * 1000, hz[i][j] * 3);
                    AddEdge(i, j, hz[i][j] * 125, 10 + (hz[i][j] > 3 ? (hz[i][j] - 3) * 2 : 0));
                }
            }
        ans = DPS(0, S);
        if(ans == MAXNUM)
            printf("no\n");
        else
            printf("%d\n", ans);
    }
    return 0;
}

1013: 狐狸与小狗

20170314

一共32个位置,至多C(32, 5) * 5 * 2 = 2013760种状态,基本思路是状态DP,不难想,却难A。当年出题人或许是为了卡map,设置了1秒,我也不乱改时限了,不过还是用unordered_map先水过了一下。 要做到正常时限还是要自己写Hash,Hash写对了,状态随便压缩一下做记忆化搜索基本就能过了。不过还可以有一些“看起来”挺酷的“优化”。

把所有能放的格子编号,就是0~31,表达棋子位置就有三种模式:坐标(x, y),编号(0~31),位标记(0, 2, 4, 8 ... 2147483648),32个位置用位标记需要unsigned int。 棋子走动,其实就是按位左移或右移3~5个位,棋子能不能落下,就是单个棋子的新位置与所有棋子的旧位置按位与一下来判断。一些细节的分类讨论也可以用位运算减少代码量。

#include<stdio.h>
#include<string.h>
const unsigned LEFT_1357  = 0x01010101;
const unsigned RIGHT_2468 = 0x80808080;
const unsigned LINE_1357  = 0x0F0F0F0F;
const unsigned LINE_2468  = 0xF0F0F0F0;
const unsigned TOP_LINE   = 0x0000000F;
const int maxn = 2013761;
const int hashSize = 1000007;
const int pace[4] = {3, 4, 4, 3};
struct HashNode
{
    unsigned dogs, fox;
    int status, m, next;
    HashNode(){}
    HashNode(unsigned d, unsigned f, int m_, int s, int n)
    :dogs(d), fox(f), m(m_), status(s), next(n){}
    bool Vis(unsigned dogs_, unsigned fox_, int m_)
    {
        return dogs == dogs_ && fox == fox_ && m == m_;
    }
};
HashNode hashBuf[maxn];
int hashPointer[hashSize];
int htp = 0;
inline int GetHash(unsigned dogs, unsigned fox, int m)
{
    int hashNum = ((dogs | fox) % hashSize << 1 | m) % hashSize;
    for(int i = hashPointer[hashNum]; i != -1; i = hashBuf[i].next)
    {
        if(hashBuf[i].Vis(dogs, fox, m))
            return i;
    }
    hashBuf[htp] = HashNode(dogs, fox, m, -1, hashPointer[hashNum]);
    return hashPointer[hashNum] = htp ++;
}
int DPS(unsigned dogs, unsigned fox, int m)
{
    //status == 1表示Dog win, 0表示Fox win,2表示已入栈
    int &status = hashBuf[GetHash(dogs, fox, m)].status;
    if(status != -1)
        return status;
    status = 2;
    if(m == 1)
    {
        bool moveFlag = false;
        unsigned tmpdogs = dogs;
        while(tmpdogs > 0)
        {
            unsigned dog = tmpdogs & -tmpdogs;
            for(int mov = 0; mov < 2; mov ++)
            {
                if(dog & RIGHT_2468 && mov == 1 || dog & LEFT_1357 && mov == 0)
                    continue;
                unsigned nex = dog << pace[mov] + !(dog & LINE_1357);
                if (nex == 0 || dogs & nex || fox & nex)
                    continue;
                moveFlag = true;
                if(DPS(dogs ^ dog ^ nex, fox, !m) == 1)
                    return status = 1;
            }
            tmpdogs &= (tmpdogs - 1);
        }
        if(!moveFlag)
            return status = DPS(dogs, fox, !m);
        else
            return status = 0;
    }
    else
    {
        if(fox & TOP_LINE)
            return status = 0;
        for(int mov = 3; mov >= 0; mov --)
        {
            if(fox & RIGHT_2468 && mov & 1 || fox & LEFT_1357 && ~mov & 1)
                continue;
            unsigned nex;
            if(mov < 2) nex = fox << pace[mov] + !(fox & LINE_1357);
            else nex = fox >> pace[mov] + !(fox & LINE_2468);
            if (nex == 0 || dogs & nex)
                continue;
            if (DPS(dogs, nex, !m) == 0)
                return status = 0;
        }
        return status = 1;
    }
}
int main()
{
    int t, m, x, y;
    unsigned dogs, fox;
    memset(hashPointer, -1, sizeof(hashPointer));
    for(scanf("%d", &t); t --; )
    {
        scanf("%d", &m);
        scanf("%d%d", &x, &y);
        fox = 1u << ((x - 1) << 2 | (y - 1) >> 1);
        dogs = 0;
        for(int i = 0; i < 4; i ++)
        {
            scanf("%d%d", &x, &y);
            dogs |= 1u << ((x - 1) << 2 | (y - 1) >> 1);
        }
        printf("%s\n", DPS(dogs, fox, m) ? "Dog win" : "Fox win");
    }
    return 0;
}

1012: Prestige

20170313

首先理解题意是两个人都要争取自己拿到的多,在这个前提下让对方也拿到的多。优先拿对自己价值高的,等价情况下优先拿走对对方价值低的(把等价情况下对对方价值高的留给对方),这个思路是对的,也即Han也会用这个思路拿,但需要一个全局策略,即求一个全局的尽可能按上面思路拿的策略。

题目数据规模不允许进行全局状态的DP(比如位运算什么的),那么只能用一个调整的策略。

Li的策略比较直白,所以先按Li取的优先级排序,然后游戏开始。

考虑第i个物品,轮到Han,则假设直接取,但做记录,轮到Li,则看物品i对于已假设Han取了的物品集合而言,是否比这个集合中对Han价值最差的(对Han价值尽可能低,对Li价值尽可能高)物品x,要价值更好,如果更好,那么“时光倒流”,当Han面对物品x的时候,取i,因为已经排序,所以“当时”如果取了i,Li肯定会取x

不断这样进行下去,这个假设的集合最终就是Han的策略会取的物品集合。

需要Log(n)来找到这个x,用一个优先级队列。

1011: Counting Pixels

20170313

只与半径有关,考虑右上的四分之一圆最后乘 4 即可。半径是整数,把这四分之一圆圈住的像素看作一列一列,圆与每列左边界的交点向上取整就是这一列的像素数,加起来。

1010: Water Drinking

20170222

很稀疏的图,记录父子节点关系最后枚举迭代一下就好。不过其实是个食物链并查集模型,比基本并查集多维护一个与父节点的距离。 已经忘了食物链怎么写了,于是复习一下。。。其实还是瞎写的。

1009: 抛硬币

20170222

对每列排序,大的跟大的乘,小的很小的乘,最后加起来总期望最高。 证明: 设a>c, b>d, (ab+cd) - (ad + bc) = (a - c)*(b - d) > 0,即假设已排好序,这时调换任意两个数的位置,得到的结果会小于先前。

1008: Horcrux

20170222

用栈的结构,每段连续相同颜色的第一个的位置为栈元素,每次变色,相当于最后一段连续颜色的起点变成了当前起点的上一个,也即出栈操作。过程中控制好颜色标记。

1007: 矩形着色

20170222

把情况想清楚就好。

1006: SAW

20170222

当年校队的大大们给新人开的一个小玩笑。当时还没看过《电锯惊魂》,都没理解标题的SAW是什么意思。 题目就是随机一个大写的26个英文字母之一,随机也好固定一个字母押宝也好,过的概率是一样的。

但是前些天看到有个代码100% AC,还以为spj坏了,看了一下spj的代码,原来是当年随机字母就用的srand(time(0))做种子,提交的代码也这样,而提交代码与spj代码运行时间很近,两个种子就一样了。

于是我邪恶地把spj的随机过程搞得更乱了 😂。

1005: Binary Search Tree analog

20170222

二叉搜索树基础

1004: Xi and Bo

20170222

用并查集合并相连的站点。

1003: UC Browser

20170222

按题意做。

1002: A+B (III)

20170209

int64基础知识。CSU-OJ是Linux编译器,用long long

1001: A+B (II)

20170209

1000: A+B (I)

20170209