UOJ Logo vfleaking的博客

博客

UOJ Test Round #2

2017-01-01 21:33:07 By vfleaking

UOJ Test Round #2 将于 1 月 8 日星期日晚上 19:00 举行!比赛将进行 3 个小时,共三道题。

话说 vfk 开学之后对于 UOJ 甩锅已久,很久没有比赛了,投到 UOJ 的题目又频频被管理员们秒掉……

捂脸熊

这可怎么办呢?

看了看最近的 UER/UR 的难度,UR 赛制只有 3 小时,题目太难大家不肯捉 —— 于是我们决定降低下题目的难度,嗯……然后我们瞬间就有三道题出了!

这次 Test Round 一方面是为了测试降低难度的 round 大家捉起来感觉怎么样,另一方面是为了测试即将上线的比赛问答系统。

(咳咳大家这次在切题的时候一定要记得调戏下比赛问答系统,可以对题意不清的地方提问,出题人会进行回答哒)

本次比赛将以“出题”为主题。

出题人:jiry_2, jiry_2, jiry_2

如果新功能没出问题的话,这场成绩将计入rating。

参加本次比赛将有机会获得 UOJ 抱枕!5d1ee77c1c495a6303e781cbe002b61b 是获奖条件的 md5 码。比赛结束后将公布条件。(你猜抱枕跟比赛问答系统有没有关系呀?)

再次提醒大家比赛中途只测样例,最后会进行最终测试,把所有提交记录重测。

(其实感觉这次难度确实好水好水,大家捉得开心就好)

UPD: 比赛已经结束!

echo -n 比赛中最后一个提问的 | md5sum
5d1ee77c1c495a6303e781cbe002b61b

恭喜获得前 5 名的选手!

  1. Rui
  2. owaski
  3. xumingkuan
  4. 613
  5. philipsweng

恭喜 sqc 获得 UOJ 抱枕一个!

UOJ 开……开……开源了!

2016-10-03 00:59:02 By vfleaking

很久很久以前,vfk 说:“UOJ 要开源”

然后……vfk 打开了 UOJ 的代码……发现好大一口锅

于是 vfk 开始整代码整代码,配环境配环境……终于!今天 UOJ 开源了!

超人熊

丢链接跑:

https://github.com/vfleaking/uoj

搞下来然后根据安装小教程搞一发就行了。封在 docker 里的,linux 和 mac 上应该挺好装的,不过 windows 用户得难受一下了hhh……

由于之前基本上是我一个人开发,当然还有 cyb 和 ljc 帮忙……但是……

什么没有文档?传题的文档还是有的。

什么没有注释?被注释掉的代码还是有的。

什么时候更新一波文档啊?看大家开发热情!这次发布之后我会写一波嗯。

鼓掌熊

这次开源的目的是为了 UOJ 的代码能够继续发展下去,把一些锅比如 “博客的个人主页” 通过大家的力量给填上。当然对于大家来说,又多了一个 hustoj 一样的存在,可以在学校的服务器上轻松搭一个校内的 UOJ。想用 ptrace 写沙箱的码农们,UOJ 的沙箱也是一个很好的参考。

以及!!!如果发现了任何 bug 求不要 hack 线上的 UOJ……QAQ……UOJ 的题目数据其实是公开的,写程序弃疗了可以伸手找找管理员要一份,除此之外 hack 网站也没啥吸引力对不……QAQ……发现了 bug 请尽快通知我们,非常感谢。

联系方式:uojmanagers@groups.163.com 或 vfleaking@163.com。

最后丢群跑:Universal OJ 开源群,590822951。想研究源码以及安装有困难的各位,在群里多交流哈~

嗯最后,祝大家 UOJ 使用愉快!愿 UOJ 开源能带来更多的便利,愿能帮到更多还在路上的 OIer 们。

(咳咳 UOJ 用户群里的某些人应该改群名片了)

UOJ Round #15 题解

2016-08-13 22:08:14 By vfleaking

奥林匹克五子棋

from qmqmqm

算法一

答案只与最后的棋盘有关。暴力枚举所有的棋盘然后判断是不是符合条件。

最终复杂度是 $O(nm2^{nm})$。可以获得 30 分。

算法二

如果对于一组 $n,m,k$ 如果有解,那么对于 $n,m,k+1$ 也有解。

明显如果 $k=1$,那先手随便下一个子就赢了,所以无解。

当 $\min(n,m)=1$ 时,如果 $k=2$,那么双方只要棋子间隔分布,就是可行解。

最终复杂度是 $O(nm)$。可以获得 15 分。

算法三

当 $\min(n,m) \lt k$ 时,斜线方向是明显永远符合条件的。所以我们采取像黑白染色那样,这样在横竖方向上最长连续段都是 $1$,明显是符合条件的解。

最终复杂度是 $O(nm)$。可以获得 15 分。

算法四

当 $n,m \geq 2$ 时,可以证明如果 $k=2$ 是无解的。

具体来说考虑 $(1,1),(1,2),(2,2)$ 三个点,由抽屉原理得其中必定有两个点同色,那么他们就成了一个长为 $2$ 的同色连续段。

所以我们来考虑 $k=3$ 的情况。

可以想到,$k=3$ 一定不会在内部有一个 $2 \times 2$ 的同色块,否则这个块的下方三个位置就会形成一个长为 $3$ 的同色连续段。进而一个同色的 L 形也不能存在,因为其上方三个斜向位置都必须和它颜色不同,从而形成一个长为$3$的同色连续段。

这样一来,构造必须是一些 $1 \times 2$ 的条间隔分布。观察发现,这个构造符合题目中的所有条件。再根据上边的结论,$k \gt 3$ 的情况也解决了。

最终复杂度是 $O(nm)$。结合算法二可以获得 100 分。

奥林匹克环城马拉松

from ftiasch,题解 from C_SUNSHINE

算法一

首先我们判断掉无解的情况,即存在一个点度数为奇数,此时方案数为 $0$。

从 $1$ 号点开始搜索欧拉回路,只要记录当前在哪和 $u,v$ 之间还有几条边没有走就好了,状态数是所有 $t_i$ 的积乘以 $n$,每次枚举下一步往哪走,可以从将要走的路上选一条未走过的边来走,并乘以这条路上剩余的边数,这样转移复杂度是 $O(n)$ 的,可以得到 $20$ 分。

算法二

注意到树的每一条边数目都是偶数,且走过去和走回来的次数各占一半,令一个点的度数 $deg_x$ 为走入这个点的次数即这个点相邻边权和除以$2$。

首先先要确定每一条边的方向,这个其实就是在每一组重边中选一半向下,另一半向上,所以是 $\prod \binom{t_i}{t_i/2}$。

那么确定方向之后,欧拉回路如何计数呢?

我们有一个简单粗暴的方法,在每个点上对于每一条入边为它指定一个后继出边,这样边与边之间就连起来了,由于 $deg_x$ 条入边和出边的匹配方案数是 $deg_x!$,于是答案就是 $\prod deg_x!$。

妈呀我怎么过不了样例啊……

可以发现这样确定出来的不是欧拉回路,而是若干个环并在一起。

继续思考,我们可以使用一些类似“骨架”的东西来连接整个欧拉回路。而在连通图中,树是一个不错的选择。

我们令欧拉回路从 $1$ 号点开始走,把最后一次经过除 $1$ 号点以外的点时走的出边拿出来作为特殊边。那么除了 $1$ 号节点以外每个节点有一条出边,并且由于是最后一次,不会出现环。于是这些特殊边构成了一棵以 $1$ 为根的树。

怎么统计这棵树呢?只要从向上走的边上拉一条出来就好了,方案数是 $\prod t_i/2$

确定了最后一条出边之后找欧拉回路的过程其实也不难,对于一个点 $x(x>1)$,前 $deg_x-1$ 次可以非特殊出边中任意挑选,最后一次只能走特殊出边,方案数是 $(deg_x-1)!$。对于 $1$ 号点来说没有特殊边的限制方案数仍然是 $deg_1!$。

于是方案数变成了 $deg_1!\prod_{x>2} (deg_x-1)!$,再乘上其他系数……妈呀我怎么还是过不了样例啊。

注意题目要求循环同构算同一种方案,但是你强制起点是 $1$,而 $1$ 在欧拉序列中可能出现了多次,于是你就统计了多次。

解决办法也很简单,$1$ 在欧拉序列中出现的次数恰好是 $deg_1$,除掉即可,这样最后一部分方案数变成了 $\prod (deg_x-1)!$。

时间复杂度 $O(n)$,期望得分 $20$ 分,结合算法一可获得 $40$ 分。

算法三

观察树上的结论,我们会发现有向图的欧拉回路计数问题是有一个通用公式的:

$$T \cdot \prod (deg_x-1)!$$

其中 $T$ 是以某个节点为根的树形图数目。

于是问题就变成了给图定向。

考虑一个环的情况,由于 $t_i \leq 10^4$,我们可以直接枚举在环上转了几圈,那么每条边往两个方向走的次数都能计算出来。

接下来就是求环的树形图数目了。

对于 $n=m=3$ 的情况显然可以手算,其余的情况,注意到树只比环少一条边,那么枚举那条边断开就好了。

时间复杂度 $O(t_in)$,期望得分 $30$,结合算法一二可获得 $70$ 分。

算法四

环的问题解决之后,环套树问题就变得十分容易了。事实上,枚举任意一条环边正着走了多少次,根据有向图欧拉序列条件式 $indegree_x=outdegree_x$,就可以直接给无向边定向,定向的方案数直接用组合数计算就好了,例如 $t_i$ 条无向边有一侧是 $s_i$ 条,方案数就是 $\prod \binom{s_i}{t_i}$。

第二步就是树形图计数,这一步只要把环上的树形图计数和每个点的外向树树形图计数直接乘起来即可。

最后乘以 $\prod (deg_x-1)!$ 即可。

时间复杂度 $O(t_in)$,期望得分 $100$ 分。

奥林匹克数据结构

from ppfdd,题解 from matthew99

算法一

直接按照题意模拟,时间复杂度$O(n\sum{{m_i} ^ 2})$,加上一些小优化很容易做到$O(n\sum{m_i})$。

算法二

考虑KMP的过程,我们同样考虑对b串建出KMP中的fail数组。那么我们发现,只需要将KMP中判断两个数相等的操作改成判断只要最后一个数字在整个序列中的名次相同即可。

用主席树实现可能会有常数问题。我们发现,我们只需要用树状数组预处理出b串中每个位置在它前面的所有数中的名次。然后再用树状数组维护当前的border,由于在KMP中border是单调的,所以每次border变化的时候暴力修改即可。

时间复杂度$O((n + \sum{m_i})\log{n} + \sum{m_i\log{m_i}})$。

算法三

考虑多串匹配,显然就是将KMP改成AC自动机,转移就是考虑下一个数在当前点到根的路径上的所有数中的名次,现在由于没有类似KMP的border的单调性,我们必须用主席树维护了。注意实现的时候,每次失配时一定要顺着fail链走上去而不是直接将转移置为fail节点的对应转移,否则会由于字符集太大无法保证复杂度(注意如果是一棵普通的trie而且字符集很小,一定要将转移置为fail节点的对应转移,因为普通trie的叶子节点深度之和可能很大)。

接着将原串在AC自动机上走一遍,最后更新子树和。注意如果暴力更新子树和会由于复杂度不对而超时。

注意要用平衡树或者hash存储转移。

时间复杂度$O(n(\log{n} + \log{q}) + \sum{m_i\log{m_i}})$。($q$是因为AC自动机上每个点度数最多是$q$)

算法四

注意到如果$\max{m_i} \le 25$,我们可以对于长度小于$\max{m_i}$的串全部预处理一遍hash值并存下来,具体来说可以存在一个数组里面然后排序,然后询问的时候直接二分查询个数即可。

用树状数组加上异或哈希实现常数较小,可以通过四个$\max{m_i} \le 25$的点。

时间复杂度$O(n\max{m_i}\log{n} + q\log(n \max{m_i}))$。

算法五

我们考虑在线怎么做。对于普通的字符串,这个问题显然是用后缀三兄弟或后缀平衡树解决。那么在这个问题上是不是也可以如此呢?

后缀数组!

慢着……这玩意儿。。。后缀数组要求把后缀进行排序,很好,两个名次数组怎么比较顺序?

后缀自动机!

慢着……这玩意儿。。。一个结点能识别的子串的长度都不固定,怎么玩?

后缀平衡树!

慢着……这玩意儿。。。还是不知怎么比较两个名次数组的顺序啊。

后缀树!

慢着……这玩意儿。。。诶不慢,好像可以。

考虑用Ukkonen算法构造后缀树的过程,显然每一步也很容易用主席树推广到这题上。

然而直接用 Ukkonen 算法会被卡复杂度。我们把孩子数不等于 $1$ 的非根节点称为特殊节点,原因是在普通串上,一个特殊节点的后缀链接显然会指向一个特殊节点,因为特殊节点已经有两个不同的字母作为转移,那么它的后缀链接肯定也有这两种字母,而在本题中不然,由于后缀链接指向了一个更浅的点,因此两种转移可能会合并为一个。

解决方法很简单,在找后缀链接的时候,如果它的父亲不是特殊节点,那就找它父亲的父亲,直到找到一个特殊节点,再从那个特殊节点开始求出当前点的后缀链接,可以证明这样的复杂度是正确的。

构造完后缀树之后求一遍子树和,每次在后缀树上跑一边查询即可。

时间复杂度 $O(n \log n + \sum{m_i(\log{m_i} + \log{n})})$。

有人说,有后缀数组和后缀自动机了,还要后缀树干嘛?从这题可以看出,每个数据结构都有自己的特性。后缀树在这题上能够成功的原因,也许是因为他其实是某种后缀 Trie 的 AC 自动机吧。而 AC 自动机能够解决离线问题的原因,也许是因为他其实是推广后的 KMP 吧。这一切,也许正是奥林匹克数据结构的魅力所在。

C/C++ 编译器更新到 4.8.4

2016-08-08 03:35:28 By vfleaking

光阴似箭,日月如梭,软件在更新,时代在进步!(喂喂)

现在 UOJ 的 C/C++ 编译器闷声从 gcc-4.8.2 和 g++-4.8.2 升级到 gcc-4.8.4 和 g++-4.8.4 了!不过其实都第三位版本号了,没多大差别了……

(其实之前用在清华集训、清华校赛、清华夏令营的那版校内 UOJ 的编译器就是 4.8.4 的,不知大家注意到没有)

咳咳,因此测评时间在2016年8月8日以前的为旧编译器的测评结果,2016年8月8日及之后的为新编译器的测评结果。

最后播送一则谣言:坊间传说几年内 OI 系列比赛将取消 Pascal,嗯……画面真美不敢想象……那时候出交互题就可以少写一种交互库了哈哈哈……(别问我是不是真的)

好,今天的 UOJ 新闻联播就到这里!

旷野大标程

2016-07-29 14:02:04 By vfleaking

标程大放送!

话说我监考时看到大部分人是手动 printf 和手算节点编号。。。好麻烦呀。。。

其实可以封装一下,重载下运算符,会爽很多,代码也更可读。

最后一个点, modmul 是可以获得满分的快速加,fastmodmul 是那个鬼畜的泰勒展开大法。注意用 modmul 已经能获得满分了,泰勒展开只是用来猎奇的。

说不定大家仔细研究标程然后发现标程错了,vfk你还我血汗分,还我血汗分!

#include "testlib.h"
#include <iostream>
#include <iomanip>
#include <vector>
#include <cassert>
using namespace std;

typedef long long int64;

int n = 0;

int opadd(int i, int j)
{
    printf("+ %d %d\n", i, j);
    return ++n;
}
int opneg(int i)
{
    printf("- %d\n", i);
    return ++n;
}
int opaddc(int i, string c)
{
    printf("C %d %s\n", i, c.c_str());
    return ++n;
}
int opshl(int i, int k)
{
    printf("< %d %d\n", i, k);
    return ++n;
}
int opshr(int i, int k)
{
    printf("> %d %d\n", i, k);
    return ++n;
}
int opsig(int i)
{
    printf("S %d\n", i);
    return ++n;
}

int n_in = 0;
int opin()
{
    printf("I\n");
    return ++n;
}
int opout(int i)
{
    printf("O %d\n", i);
    return ++n;
}

struct xvar
{
    int id;

    xvar() {}
    xvar(const int &_id)
        : id(_id) {}

    friend inline xvar operator+(const xvar &lhs, const string &rhs)
    {
        return opaddc(lhs.id, rhs);
    }
    friend inline xvar operator+(const xvar &lhs, const xvar &rhs)
    {
        return opadd(lhs.id, rhs.id);
    }
    friend inline xvar operator<<(const xvar &lhs, const int &rhs)
    {
        return opshl(lhs.id, rhs);
    }
    friend inline xvar operator>>(const xvar &lhs, const int &rhs)
    {
        return opshr(lhs.id, rhs);
    }
    inline xvar operator-() const
    {
        return opneg(id);
    }
};

inline xvar sig(xvar x)
{
    return opsig(x.id);
}
inline xvar opout(xvar x)
{
    opout(x.id);
    return x;
}

inline string zeros(int n)
{
    string s;
    for (int i = 1; i <= n; i++)
        s += '0';
    return s;
}
inline string nines(int n)
{
    string s;
    for (int i = 1; i <= n; i++)
        s += '9';
    return s;
}

xvar psgn(xvar x)
{
    return sig(x << 500);
}
xvar ge0(xvar x)
{
    return psgn(x + ("0." + zeros(29) + "1"));
}
xvar ge1(xvar x)
{
    return psgn(x + ("-0." + nines(30)));
}
xvar gt1(xvar x)
{
    return psgn(x + ("-1." + zeros(29) + "1"));
}

xvar ncondx(xvar p, xvar x)
{
    const int VL = 150;
    p = p << (VL + 1);
    xvar y = sig((x >> VL) + p);
    return ((y + "-0.5") << (VL + 2)) + (-p);
}
xvar condx(xvar p, xvar x)
{
    return ncondx(-p + "1", x);
}
xvar minx0(xvar x)
{
    return ncondx(ge0(x), x);
}
xvar abs(xvar x)
{
    const int VL = 150;
    xvar p = ge0(x) << (VL + 2);
    xvar y = sig((x >> VL) + p);
    return x + ((-y + "0.5") << (VL + 3)) + p;
}

xvar land(xvar x, xvar y)
{
    return gt1(x + y);
}
xvar lor(xvar x, xvar y)
{
    return ge1(x + y);
}

xvar bits_to_x(xvar *bits)
{
    xvar x = bits[0];
    for (int i = 1; i < 32; i++)
        x = (x << 1) + bits[i];
    return x;
}
void x_to_bits(xvar x, xvar *bits)
{
    x = x << 500;

    long long t = 702955280397374434ll;
    char ts[100];
    for (int i = 31; i >= 1; i--)
    {
        sprintf(ts, "-%lld", t);
        bits[i] = sig(x + (ts + zeros(142)));
        x = x + -(bits[i] << (500 + i));
        t /= 2;
    }
    bits[0] = x >> 500;
}

xvar sqr(xvar x)
{
    const int UL = 130;
    xvar dx = x >> UL;
    xvar y = sig(dx + "-1.098612288668109691395245236922525704647490557822749451734694333637494293218608966873615754");
    y = y + -((dx >> 4) + (dx >> 3));

    //   1.31695789692481670862504634730796844402698197146751647976847225692046018541644397607421903
    // - 0.25
    // = 1.06695789692481670862504634730796844402698197146751647976847225692046018541644397607421903

    return (sig(y + "1.06695789692481670862504634730796844402698197146751647976847225692046018541644397607421903") + "-0.788675134594812882254574390250978727823800875635063438009301163241988836151466672846857700") << (UL * 2 + 7);
}

void solve1()
{
    xvar x1 = opin();
    xvar x2 = opin();
    opout(-((x1 + x2) << 1));
}
void solve2()
{
    xvar x = opin();
    opout(sig(-(x + (x << 4))));
}
void solve3()
{
    opout((psgn(opin()) << 1) + "-1");
}
void solve4()
{
    xvar x = opin();
    opout(abs(x));
}
void solve5()
{
    static xvar bits[32];
    for (int i = 0; i < 32; i++)
        bits[i] = opin();
    opout(bits_to_x(bits));
}
void solve6()
{
    xvar x = opin();
    static xvar bits[32];
    x_to_bits(x, bits);
    for (int i = 31; i >= 0; i--)
        opout(bits[i]);
}
void solve7()
{
    xvar x = opin();
    xvar y = opin();
    xvar xbits[32], ybits[32];
    x_to_bits(x, xbits);
    x_to_bits(y, ybits);

    xvar zbits[32];
    for (int i = 0; i < 32; i++)
    {
        xvar s = xbits[i] + ybits[i];
        zbits[31 - i] = s + -(psgn(s + "-1.5") << 1);
    }
    opout(bits_to_x(zbits));
}
void solve8()
{
    xvar x = opin();
    string alpha = "2.06343706889556054705";
    string sigalpha = "0.887298334620741688550198422716226773933599412474263948504833186119911079463425709202638465";
    opout((sig((x >> 200) + alpha) + ("-" + sigalpha)) << 200);
}

void solve9()
{
    xvar x[17];
    for (int i = 1; i <= 16; i++)
        x[i] = opin();
    for (int i = 1; i <= 16; i++)
        for (int j = i + 1; j <= 16; j++)
        {
            xvar s = x[i] + x[j];
            x[i] = x[i] + minx0(-x[i] + x[j]);
            x[j] = s + -x[i];
        }
    for (int i = 1; i <= 16; i++)
        opout(x[i]);
}

xvar modadd(xvar a, xvar b, xvar ma, xvar negm)
{
    xvar s = a + b;
    return s + ncondx(psgn(-s + ma), negm);
}
xvar modmul(xvar a, xvar b, xvar m, xvar negm)
{
    xvar ta[32];
    xvar tb[32];
    x_to_bits(a, ta);
    x_to_bits(b, tb);

    xvar zero = a >> 1000;
    xvar ma = m + "-0.1";
    a = ta[31];
    a = a + ncondx(psgn(-a + ma), negm);
    for (int i = 30; i >= 0; i--)
    {
        a = a + a + ta[i];
        a = a + ncondx(psgn(-a + ma), negm);
    }

    xvar res = zero;
    res = condx(tb[0], a);
    res = res + ncondx(psgn(-res + ma), negm);

    a = a + a;
    a = a + ncondx(psgn(-a + ma), negm);
    for (int i = 1; i < 32; i++)
    {
        res = res + condx(tb[i], a);
        res = res + ncondx(psgn(-res + ma), negm);

        if (i < 31)
        {
            a = a + a;
            a = a + ncondx(psgn(-a + ma), negm);
        }
    }
    return res;
}

xvar fastmodmul(xvar a, xvar b, xvar m)
{
    xvar ab = sqr(a + b);
    ab = ab + -sqr(a);
    ab = ab + -sqr(b);
    ab = ab + "0.2";
    ab = -ab;
    ab = ab << 149;
    for (int i = 63; i >= 0; i--)
    {
        const int VL = 300;

        xvar mi = m << (150 + i);
        xvar p = sig(mi + ab) << (VL + 1);
        xvar y = sig((mi >> VL) + p);
        ab = ab + ((y + "-0.5") << (VL + 2)) + -p;
    }
    ab = ab >> 150;
    ab = -ab + "-0.1";
    return ab;
}

void solve10()
{
    xvar a = opin(), b = opin(), m = opin();
    //opout(modmul(a, b, m, -m));
    opout(fastmodmul(a, b, m));
}

int main(int argc, char **argv)
{
    freopen("nodes1.out", "w", stdout);
    n = 0, solve1();
    freopen("nodes2.out", "w", stdout);
    n = 0, solve2();
    freopen("nodes3.out", "w", stdout);
    n = 0, solve3();
    freopen("nodes4.out", "w", stdout);
    n = 0, solve4();
    freopen("nodes5.out", "w", stdout);
    n = 0, solve5();
    freopen("nodes6.out", "w", stdout);
    n = 0, solve6();
    freopen("nodes7.out", "w", stdout);
    n = 0, solve7();
    freopen("nodes8.out", "w", stdout);
    n = 0, solve8();
    freopen("nodes9.out", "w", stdout);
    n = 0, solve9();
    freopen("nodes10.out", "w", stdout);
    n = 0, solve10();

    return 0;
}
vfleaking Avatar