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;
}

Goodbye Yiwei 题解

2016-02-05 22:06:29 By vfleaking

新年的破栈

from wyx528

算法一

容易发现,每次可能的操作不会超过 3 种,因此只要在需要决策的时候暴力枚举其中的一种即可,指数级复杂度,可以得到 20 分。

算法二

由于要求字典序最小,所以必然要把尽可能小的数提前出栈,更特殊地,一定会把最小的数最先出栈。

当最小的元素出栈时,记栈底元素为 $x$,栈顶元素为 $y$,未进栈的元素中最小值为 $z$,则下一个要出栈的元素必为 $\min\{x,y,z\}$。由于题目保证给定的元素互不相等,所以这一步是没有歧义的,也就是说 $x,y,z$ 中任意两个都不会相等。这样,我们便得到了输出序列的第二个数。

可以发现,只要重复这个贪心过程即可取得最优解。使用朴素算法,选取未进栈元素最小值的时间复杂度为 $O(n)$,因此完成一组数据的时间复杂度为 $O(n^2)$,可以得到 60 分。

算法三

使用堆或者平衡树来优化算法二中选取未进栈元素最小值的时间复杂度,使之降为 $O(\log n)$,这样完成一组数据的时间复杂度变为 $O(n \log n)$,可以得到 100 分。(比赛时还真有人这么干……)

阅读更多……

Goodbye Yiwei

2016-02-02 17:00:27 By vfleaking

再见,乙未!

转眼间,乙未年已经过去。过去的这一年,羊族守护着中华大地。除夕夜,羊族完成了一年的使命。零点钟声敲响,猴族首领接过了羊族首领的生肖旗,开启了新的一年。

猴族的首领名叫猴腮雷,因两腮上各长了一个腮雷而闻名于世。他有一句名言:没有什么是一颗腮雷解决不了的,如果有,那就两颗。

在新的一年里,祝大家一帆风顺万事如意,即使遇到困难也要迎难而上,在最艰难的时候也要坚信 —— 没有什么是猴腮雷解决不了的。

我们将于除夕前一天下午 13:00 到 18:00 举办一场盛大的 Goodbye Yiwei 赛。

即:2月6日下午 13:00 到 18:00。注意此次比赛时间为 5 小时,共 5 道题 ABCDE 来给大家贺岁~

赛制仍然是OI赛制,但是题目难度嘛,水题和省选难度题兼有。欢迎所有人包括萌萌哒NOIP选手来玩!

出题人:wyx528, sevenkplus, Rating_Jia_Su_Qi, saffah, ppfdd

猴腮雷

这场成绩将计入rating。

参加本次比赛将有机会获得 UOJ 纪念品!你可以选择 UOJ 抱枕或 UOJ 充电宝!8e2519a93491ea3651f808eb830fe26c 是获奖条件的 md5 码。比赛结束后将公布条件。

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

UPD:比赛已经结束!

echo -n ABCDE都得分的人中成绩顺序对数最多的(顺序对是逆序对的反义词),有多个人取排名最靠前的 | md5sum
8e2519a93491ea3651f808eb830fe26c

恭喜获得前 5 名的选手!

  1. hzt1
  2. BillXu2000
  3. xuhaike
  4. Yemengmeng
  5. function843

恭喜 heheda 获得 UOJ 抱枕一个!

UOJ精神之源流

2015-11-02 01:19:14 By vfleaking

不得不说今天是个伤感的夜晚。我们此时站在这里,连接过去和未来。曾以为我们的计划会成为我们的未来,却不知道大浪拍击沙滩的力量比飓风更有力。

UOJ从哪里来?今晚的UOJ还是一年前发布时的那个UOJ吗?

为什么我们慢慢忘了那最虔诚的最初,渐行渐远……

于是我意识到,我们应该回去,回头看看那最初的原点。

最初我是怀着对OI界题目的不满,最初我和业界毒瘤有很多比较难的脑洞想出给大家玩,最初的最初是那场引发我对OI比赛的思考的NOI2013……

我们想建立的是,一个能自由评测各种类型题目的OJ,一个题题高质量的OJ,一个定期举办高质量的比赛的OJ —— 一个能带给OIer思考与收获的OJ。

那么怎样的题才能被称为好题?我记得那年我造题,一造就是一周。没有别的,就是死磕。磕题面的简洁严谨,磕标程的运行效率,磕数据,写好几个暴力分别卡掉 —— 这一切都源于我对现行OI出题人的不满。出到比赛里的题,平时抛之脑后,考前紧急造题,最后端给选手的是一碗方便面。

一道好题应该被仔细推敲过。好题应该有很强的数据,好题应该又清晰的题面,好题的标程应该优美题解应该详尽。

一道好题不应该是两道题拼在一起,一道好题会有自己的idea —— 而它应该不加过多包装地突出这个idea。

一道好题应该新颖。真正的好题,应该是能让人脑洞出新的好题的好题。

一道好题应该具有它的选拔性质,具有足够的区分度。应该至少4档部分分,让新手可以拿到分,让高手能够展示自己的实力。

不得不说我认为我出过的题中最优美的还是两年前的那个嵌入了函数式线段树的网络流题 a+b problem。

嗯,这一切都是开端。接下来就是 UOJ Test Round #1,UOJ Easy Round #1,UOJ Round #1,UOJ Round #2,UOJ Round #3,这几场我都很满意。

等到UOJ Round #4及之后的时候我发现情况有些不对了,因为没有什么题可出了。 UOJ比赛的频率是两周一次,对于要造题的我来说是相当辛苦的。应该就是从这场比赛开始吧,由于没有好脑洞,我开始使用起自己特有的脑洞能力去改编出题人给我的不那么完美的题,死磕直到令人满意。

往后看去,UOJ Round #5的C题考验了大家对莫比乌斯反演的灵活运用,纯考智商的UOJ Round #6的C题是一个小小的巅峰,各种贪心得到简洁结论又需要用一些技巧优化复杂度的UOJ Round #7也相当有意思。

再往后看去,让人觉得有趣的又有多少呢?

后来UOJ搬运了集训队互测这头怪兽。

后来我CTSC滚粗,退役了。这之后其实我心态完全发生了变化 —— 因为OI已经几乎与我无关。

后来UOJ的比赛完全造好题目的时间离比赛开始的时间越来越近。

后来有出题人给我idea,我没有太多耐心跟他一起脑洞一起改编。

后来我为了“两周一次”这个承诺而造题,而不是为了最初的一场大梦,甚至连两周一次也做不到。

我渐渐意识到,自己都觉得没那么有趣的题目,别人凭什么觉得有趣?远远超过三小时的汗水,才值得几百人为一场比赛花上三小时。

我想起了我最初的一句“宁缺毋滥”,我想起了激励了我很长时间的洛克菲勒与协和医院的故事:我们要以最高标准建一所医院,成为中国医学界的一座标杆 —— 而我们清楚地知道,论题目的数量,世界上千万万OJ不缺我们UOJ一家,我们要做的就是聚集最优秀最热爱信息学的OIer,建立一个题目质量难以企及的OJ。

然而说好的题目质量呢?

今日的UOJ Easy Round #5,被点了好多差评。当然我一开始是吐槽那些“不会做题就直接点差评”党们,或是抱怨做题人不懂出题人的艰辛 —— 然而,做题人和出题人什么时候互相理解过?看到网上对葛军的一些言论,假若那些截图是真的,那么同为出题人我特别能体会到葛军的心情。但是我们能抱怨那些来做题的人吗?

回到最初最初的想法,从服务器到域名,从数据库到网页前端,从一句ptrace到一整个沙箱,从零散的idea到一整场比赛,我做这些到底是为了什么?就是想让大家一起享受算法的乐趣啊……就是想帮助大家实现自己的信息学梦想啊……

所以有什么好抱怨的呢?我想要帮助的人觉得自己在浪费时间,是他们的思想境界问题吗?其实,我自己也没有特别认真对待最近的这些UOJ比赛不是么?

我知道我在吃老本,一点点考验着在座的各位由于过去的比赛而产生的对UOJ的信任。然而这些终将过去,没有多少人还会记得UOJ Test Round #1的文件名排序,UOJ Easy Round #1的有趣的并查集,UOJ Round #1的仙人掌……重要的是当下,重要的是未来UOJ如何发展。

看到比赛前热情洋溢的报名人数,看看最后点赞寥寥差评者众的局面,我想,其实这一切都是因为我变懒了吧。虽说经历了这么多,让我跟最初的那个理想的我相比更加现实了一些,更加能理解作为一个出题人他所面临的窘境,但是当我今天回忆起我们最初究竟是要干什么的时候,我还是清晰地意识到:不能再迷失了,虽然我没时间负责具体的造题,但是,是时候回去了 ——

回到那场大梦,坚持UOJ的精神。

因为不忘初心,方得始终。

暂别

2015-10-19 22:09:32 By vfleaking

众所周知 vfk 一夜间变成了大学生。

然后大学全新的环境我自己都还没把自己玩清楚,忙了一段时间后发现果然 UOJ 就这么坑着了。

其实出发去大学之前还想着可以咬牙硬撑。还记得 UER #3 吗?在大家激战正酣的时候,vfk 正在整理内务、把被子叠成豆腐块。就这样我在军训期间成功办了比赛。

然而,我那次完全没有以前认真,有些题自己并没有仔细检查,慌慌忙忙就出了。

有这样一件事非常激励我:当年洛克菲勒想做慈善,提升中国的医疗卫生水平。他派出的调查团给出了两个方案:

  1. 在全国各地撒下大大小小的医院
  2. 建一所医院,以最高标准来建

洛克菲勒选择了方案2,他建了一所从硬件设施到专业水平都世界一流的医院,那就是协和医院。据说第一届只招了 7 个学生,最终有 3 个人成功毕业。协和的严谨认真的精神传承至今,成为中国近代医学史上的一座丰碑,被千百万医学后辈仰望。

我在创办 UOJ 之初就想到:论题目数量,天下 OJ 不缺 UOJ 这一个。我跟洛克菲勒的选择一样:我们要的不是数量,而是质量。

也许你有所耳闻,UOJ 的比赛的题目的审核较为严格。当题目不有趣时我会和出题人一起讨论,不断地改进、加强。所以,一场 UOJ 比赛要耗费我大量的时间和精力 —— 这对于我来说有点奢侈。

抱歉我就这样把 UOJ 比赛拖欠了 2 个月。我很感动的是 jiry_2C_SUNSHINE 愿意来帮忙给 UOJ 的比赛找题、审题,嗯,是时候让现役选手出点有趣的题目给大家了。

这周的 UER #4 由 jiry_2C_SUNSHINE 和我共同负责,欢迎各位!

虽说博客题目是暂别,但是也不是暂别吧,因为 vfk 一直就在这里,UOJ 的团队一直在这里。我们会忙活 UOJ 的事,只是花的时间比以前少多了。

我很喜欢 UOJ,即使从 OI 退役了也如此,高三折腾 UOJ 的日子是最难忘的回忆,愿 UOJ 有更加美好的未来。

UOJ Easy Round #3 题解

2015-08-23 20:43:39 By vfleaking

开学前的作文

by Starzxy

首先,光标移动范围不可能超出 $(1,1)-(n,m)$ 的方格。其次,只有 Fn 是有效的按键。(很显然吧……

算法一

枚举每一种不同的操作,时间复杂度$O(3^{n+m})$。可以获得10分。

算法二

设 $N[x],x\in${ , }表示按下 $x$ 键后光标行位置的变化。

设 $M[x],x\in${ , }表示按下 $x$ 键后光标列位置的变化。

用 $F[n][m][k_1][k_2]$ 表示光标移动到第 $n$ 行第 $m$ 列最后分别按下的 或未进行按键操作是 $k_1$ 与 $k_2$,则 $F[n][m][k_1][k_2]=min(F[n-N[k_2]][m-M[k_2]][k_x][k_1],F[n-N[k_1]-N[k_2]][m-M[k_1]-M[k_2]][k_1][k_2])+1$,$k_x$ 为任意操作,$\mathrm{DP}$ 可以做到 $O(nm)$ 的复杂度。可以获得50分。

算法三

对于只有一行或者一列的情况,多枚举一些就能找到规律。(啊啊啊就在右(下)边我要拼命按右(下)按Fn!

可以获得20分,结合算法二可以获得70分。

阅读更多……

共 50 篇博客