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

20170209

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

20170222

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


20170307

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


1015: 机器人训练

20170316

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

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

#include<stdio.h>
#include<stdlib.h>
#include<algorithm>
const int TURN_NUM[4][4] =
        {
                {0, 2, 1, 1},
                {2, 0, 1, 1},
                {1, 1, 0, 2},
                {1, 1, 2, 0}
        };
//方向压缩到 0:x正,1:x负,2:y正,3:y负
inline int Dir(int s, int e, int is_y){return (e > s) + (is_y << 1);}
inline int ArrowDir(int * a){return a[0] != a[2] ? Dir(a[0], a[2], 0) : Dir(a[1], a[3], 1);}
void OneStep(int s, int e, int is_y, int &turn, int &dir)
{
    if(s == e) return;
    int nex_dir = Dir(s, e, is_y);
    turn += TURN_NUM[dir][nex_dir];
    dir = nex_dir;
}
int TryOneDir(int is_y, int dir, int *now, int *nex)
{
    int turn = 0;
    OneStep(now[is_y + 2 ], nex[is_y], is_y, turn, dir);
    OneStep(now[!is_y + 2 ], nex[!is_y], !is_y, turn, dir);
    OneStep(nex[0], nex[2], 0, turn, dir);
    OneStep(nex[1], nex[3], 1, turn, dir);
    return turn;
}
int main()
{
    int t, n, aw[2][4];
    for(scanf("%d", &t); t --; )
    {
        scanf("%d", &n);
        for(int i = 0; i < 4; i ++) scanf("%d", &aw[0][i]);
        int now_dir = ArrowDir(aw[0]), totalTurn = 0, totalDis = abs(aw[0][0] - aw[0][2]) + abs(aw[0][1] - aw[0][3]);
        for(int i = 0; -- n; i ^= 1)
        {
            for(int j = 0; j < 4; j ++) scanf("%d", &aw[!i][j]);
            totalTurn += std::min(TryOneDir(0, now_dir, aw[i], aw[!i]),
                                  TryOneDir(1, now_dir, aw[i], aw[!i]));
            now_dir = ArrowDir(aw[!i]);
            totalDis += abs(aw[i][2] - aw[!i][0]) + abs(aw[i][3] - aw[!i][1]) +
                    abs(aw[!i][0] - aw[!i][2]) + abs(aw[!i][1] - aw[!i][3]);
        }
        printf("%d %d\n", totalDis, totalTurn);
    }
    return 0;
}

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,用一个优先级队列。

#include<stdio.h>
#include<queue>
#include<algorithm>
using namespace std;
typedef pair<int, int> pii;
struct cmp { ;
    bool operator()(const pii &a, const pii &b) const {
        return a.first != b.first ? a.first > b.first : a.second < b.second;
    }
};
int main()
{
    int t, n, l, h;
    char start[10];
    for(scanf("%d", &t); t --; )
    {
        priority_queue<pii, vector<pii>, cmp> H;
        int ansl = 0, ansh = 0;
        vector<pii> L;
        scanf("%d%s", &n, start);
        for(int i = 0; i < n; i ++)
        {
            scanf("%d%d", &l, &h);
            L.push_back(pii(l, h));
        }
        sort(L.begin(), L.end(), cmp());
        if(start[0] == 'L')
            ansl += L[0].first;
        for(int isH = 1, i = start[0] == 'L'; i < L.size(); isH ^= 1, i ++)
        {
            pii &now = L[i];
            if(isH)
            {
                ansh += now.second;
                H.push(pii(now.second, now.first));
            }
            else
            {
                if(!cmp()(pii(now.second, now.first), H.top()))
                    ansl += now.first;
                else
                {
                    ansl += H.top().second;
                    ansh -= H.top().first;
                    ansh += now.second;
                    H.pop();
                    H.push(pii(now.second, now.first));
                }
            }
        }
        printf("%d %d\n", ansl, ansh);
    }
    return 0;
}

1011: Counting Pixels

20170313

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

#include<stdio.h>
#include<math.h>
int main()
{
    long long x, y, r;
    while(scanf("%lld%lld%lld", &x, &y, &r) && (x || y || r))
    {
        long long ans = 0;
        for(long long i = 0; i < r; i ++)
        {
            ans += (long long)(ceil(sqrt(r * r - i * i)) + 1e-8);
        }
        printf("%lld\n", ans * 4);
    }
    return 0;
}

1010: Water Drinking

20170222

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

#include<stdio.h>
int p[100011];
int dis[100011];
bool s[100011];
int fa(int x)
{
    if(x == p[x]) return x;
    fa(p[x]);
    dis[x] += dis[p[x]];
    p[x] = fa(p[x]);
    return p[x];
}
int main()
{
    int n, a, b;
    while(scanf("%d", &n) != EOF)
    {
        for(int i = 0; i <= n; i ++)
            p[i] = i, dis[i] = 0, s[i] = false;
        for(int i = 0; i < n; i ++)
        {
            scanf("%d%d", &a, &b);
            s[a] = true;
            p[b] = a;
            dis[b] = 1;
            fa(b);
        }
        int ans = -1;
        for(int i = 1; i <= n; i ++)
        {
            fa(i);
            if (!s[i] && (ans == -1 || dis[i] < dis[ans]))
                ans = i;
        }
        printf("%d\n", ans);
    }
    return 0;
}

1009: 抛硬币

20170222

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

#include<stdio.h>
#include<algorithm>
double p[11][111];
int main()
{
    int n, m;
    while(scanf("%d%d", &n, &m) && n && m)
    {
        for(int i = 0; i < n; i ++)
            for(int j = 0; j < m; j ++)
                scanf("%lf", &p[j][i]);
        for(int j = 0; j < m; j ++)
            std::sort(p[j], p[j] + n);
        double ret = 0, tmp;
        for(int i = 0; i < n; i ++)
        {
            tmp = 1;
            for(int j = 0; j < m; j ++)
                tmp *= p[j][i];
            ret += tmp;
        }
        printf("%.4f\n", ret);
    }
    return 0;
}

1008: Horcrux

20170222

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

#include<stdio.h>
#include<stack>
int main()
{
    int n, horcrux, nowcolor;
    std::stack<int> s;
    while(scanf("%d", &n) != EOF)
    {
        nowcolor = -1;
        for(int i = 1; i <= n; i ++)
        {
            scanf("%d", &horcrux);
            if(s.empty() || horcrux != nowcolor && (i & 1))
            {
                s.push(i);
                nowcolor = horcrux;
            }
            else if(horcrux != nowcolor)
            {
                nowcolor = horcrux;
                if(s.size() > 1) s.pop();
            }
        }
        int ans = 0, right = n + 1;
        while(!s.empty())
        {
            ans += (!nowcolor) * (right - s.top());
            nowcolor = !nowcolor;
            right = s.top();
            s.pop();
        }
        printf("%d\n", ans);
    }
    return 0;
}

1007: 矩形着色

20170222

把情况想清楚就好。

#include<stdio.h>
int main()
{
    int t;
    int px, py, ax, ay, bx, by;
    for(scanf("%d", &t); t --; )
    {
        scanf("%d%d%d%d%d%d", &px, &py, &ax, &ay, &bx, &by);
        if(px < ax || px > bx || py < ay || py > by)
            printf("Outside\n");
        else if(px == ax || px == bx || py == ay || py == by)
            printf("On\n");
        else
            printf("Inside\n");
    }
    return 0;
}

1006: SAW

20170222

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

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

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

#include<stdio.h>
int main()
{
    printf("A");
    return 0;
}

1005: Binary Search Tree analog

20170222

二叉搜索树基础

#include<stdio.h>
struct Node
{
    int num;
    int left;
    int right;
    Node(){left = right = num = -1;}
};
Node nd[1111];
int ltp;
void Insert(int x, int now)
{
    if(nd[now].num == -1)
        nd[now].num = x;
    else if(nd[now].num > x)
    {
        if(nd[now].left == -1)
            nd[ltp] = Node(), nd[now].left = ltp ++;
        Insert(x, nd[now].left);
    }
    else
    {
        if(nd[now].right == -1)
            nd[ltp] = Node(), nd[now].right = ltp ++;
        Insert(x, nd[now].right);
    }
}
bool printed;
void PrintTree(int now, int order)
{
    if(order == 1)
        printf(printed ? " %d" : "%d", nd[now].num), printed = true;
    if(nd[now].left != -1)
        PrintTree(nd[now].left, order);
    if(order == 2)
        printf(printed ? " %d" : "%d", nd[now].num), printed = true;
    if(nd[now].right != -1)
        PrintTree(nd[now].right, order);
    if(order == 3)
        printf(printed ? " %d" : "%d", nd[now].num), printed = true;
}
int main()
{
    int t, n;
    for(scanf("%d", &t); t --; )
    {
        scanf("%d", &n);
        ltp = 0;
        nd[ltp ++] = Node();
        int x;
        while(n --)
        {
            scanf("%d", &x);
            Insert(x, 0);
        }
        printed = false; PrintTree(0, 1); printf("\n");
        printed = false; PrintTree(0, 2); printf("\n");
        printed = false; PrintTree(0, 3); printf("\n");
        printf("\n");
    }
    return 0;
}

1004: Xi and Bo

20170222

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

#include<stdio.h>
int p[111];
int fa(int x)
{
    return x == p[x] ? x : (p[x] = fa(p[x]));
}
int main()
{
    int t, n, m, start, end;
    for(scanf("%d", &t); t --; )
    {
        scanf("%d%d", &start, &end);
        scanf("%d", &n);
        for(int i = 0; i <= 100; i ++)
            p[i] = i;
        for(int i = 0; i < n; i ++)
        {
            scanf("%d", &m);
            int first = -1, connected;
            while(m --)
            {
                scanf("%d", &connected);
                if(first == -1)
                    first = connected;
                else
                    p[fa(connected)] = fa(first);
            }
        }
        printf("%s\n", fa(start) == fa(end) ? "Yes" : "No");
    }
    return 0;
}

1003: UC Browser

20170222

按题意做。

#include<stdio.h>
int main()
{
    int t, n;
    char buf[111];
    for(scanf("%d", &t); t --; )
    {
        int score = 0, tmpscore = 0;
        scanf("%d%s", &n, buf);
        for(int i = 0; i <= n; i ++)
        {
            buf[i] == '1' ? tmpscore ++ : (tmpscore = 0);
            score += 10 * ((tmpscore - 1) % 5 + 1);
        }
        int level = (score + 50) / 100;
        printf("%d\n", level > 8 ? 8 : level);
    }
    return 0;
}

1002: A+B (III)

20170209

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

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
int main()
{
    long long a, b;
    while(scanf("%lld%lld", &a, &b) && a && b)
    {
        printf("%lld\n", a + b);
    }
    return 0;
}

1001: A+B (II)

20170209

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
int main()
{
    double a, b;
    while(scanf("%lf%lf", &a, &b) != EOF)
    {
        printf("%.4f\n", a + b);
    }
    return 0;
}

1000: A+B (I)

20170209

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
int main()
{
    int a, b;
    while(scanf("%d%d", &a, &b) != EOF)
    {
        printf("%d\n", a + b);
    }
    return 0;
}