UOJ Logo Gromah的博客

博客

NOIP day1 扯淡

2015-11-07 19:01:20 By Gromah

第一题是题?

第二题的话,找最小环应该就可以了吧。这个感觉是比较经典的。

第三题的话:

首先,我们考虑出牌顺序是否会对出牌次数产生影响。显然不会。

既然这样,我们不妨先出顺子,包括单顺,双顺,三顺。具体就是直接暴力枚举每一个顺子,然后出掉,再枚举顺子,再出掉$\dots\dots$这样会不会很耗时间呀?事实是不会的。因为一个顺子至少也有 5 张牌,所以最多出 4 次顺子,递归层数是很小的。然后在一组牌内可以产生 $O(K^2)$ 个顺子,其中 $K$ 表示能成为顺子组成部分的牌的种数,在这里 $K = 12$,然后这里的复杂度就是 $O(K^8)$,然而常数是极小无比的,可以很快地运作。

然后我们就可以不考虑顺子了,那么对于剩下的牌,我们就只能一个一个或者一对一对或者一带一带地出了。总而言之,出牌的次数与牌的点数无关了。那么我们可以预处理一个 $Time[a][b][c][d][e]$,表示手牌有 $a$ 张单牌,$b$ 个对子,$c$ 个三张,$d$ 个炸弹,$e$ 张王时,把牌出完的最小次数。这个东西可以通过动态规划求解。

时间复杂度:$O(n^4 + T\times K^8)$。

尽管我是这么 BB 的,然而考场上各种浪,后边这一部分是各种贪心各种分类讨论。。。还好据说数据随机,被卡的几率应该比较小吧。。。。。。

毕竟 Gromah 果弱嘛,只会这么 BB。

OI 回忆录

2015-07-21 17:49:08 By Gromah

时间过得好快,一下子就高三了,一下子就退役了,两年的时间仿佛就在一眨眼的功夫内度过了。不过还是想回忆回忆这两年的雨雪风霜,也就当做个总结吧。

高一其实并没有什么好说的,反正就这么颓到了高二。

高二上学期,我莫名其妙知道了一个叫做 UOJ 的东西,然后就开始打 UOJ 咯。同时也还通过 UOJ 认识了一些朋友。比如 PoPoQQQ 呀,TKD 呀,ysy 呀……然后还时不时抱一下VFleaKing的大腿呀(不要打我QAQ)……反正就是有一些朋友啦,一下子也写(记)不(不)完(请)。然后就混日子到了冬令营,然后冬令营大概就是面基会的样子……还被学长拉去唱歌献丑……这个学长现在秀恩爱秀的比较厉害,我就祝一句百(he)年(he)好(he)合(he)啦……

然后到了高二下学期,开始有各种各样的大型比赛了。首先是省选,省选真的是跪傻了。该写暴力的作死写正解类似物结果血崩了爆零,Sb题写暴力去了结果暴力都还写了半天,然后就这么滚粗了。然后就被班主任“护送”到了传说中的“高考尖子班”,在班上的那段时间感觉整个人都不好了。还好我们教练给了我一个D类名额,于是我又继续我的OI被虐之旅。然后是CTSC和APIO吧。CTSC的day1滚粗了,好像是45分的样子,那天晚上我就在想我是不是应该放弃了,什么都跪,应该没戏了,感觉很忧伤很失落。然后接着day2,T1好像会做的样子,然后大概就整场比赛都在做T1,T2写了个暴力,T3什么鬼管都没管,于是就85分了,于是就翻成Ag了。然后感觉好开心呀,心情顿时好了一些。然后是APIO,考得也还不错的样子,222 Au,然而感觉好像并没有什么卵用的样子。中间还去浙江打了day2,结果80分滚粗,还是题答拿了40分……然后THUSC被拒了,又忘记报PKUSC了,于是很悲剧。然后继续在搞学考,感觉人都搞蠢了……最后就是NOI了,笔试100分没什么压力,然后说说day1,T1直接切了,感觉不虚,T2并不会,试后才发现这就是优先重儿子dfs序版树链剖分然后就没了的样子,脑子可能在考场上炸掉了吧,T3就更不用说了……于是day1就100+40+40=180滚粗了。day2一上来就是搞了3个小时的T2,T1并不会就随便骗骗分了,写T3的时候只剩1个小时了,结果暴力都没调出来样例都没过。结果就是35+90+8=133滚粗了,总成绩100+180+133=413,光荣Cu。

NOI考完之后就是高校招生了。我去了浙大、北航、浙大的招生处。首先是浙大面试,感觉并不好的样子,就滚出来了。然后是北航,一下来就发了一套数学题,有6个题,只给10分钟的样子,我做了5个,感觉还可以,然而面试真的是把我搞蠢了,问的都是一些奇奇怪怪的问题,我并不会,感觉就一般般了。然后来到了复旦招生处,大概当时进去的都是440分左右的同学,然而我只有413分,并且感觉就是出来一个就签了一个,名额又只有30个,所以感觉好虚啊,会不会没大学读了……就莫名开始盘算去武大的计划,真是欲哭无泪的感觉。然后就在门口等了不知道多久,终于轮到我了,居然轮到我了。结果一进去,老师们都在休息,吃东西的吃东西,喝水的喝水,聊天的聊天。于是又等了好久,终于轮到我面试了,然后开始神级扯淡模式,结果感觉扯崩了,就开始有点发虚了,当时就不是紧张了,而是一种莫名的麻木,莫名的淡然了,心跳都感觉要停止了一样。面试完之后就在坐在其他地方结果,然后老师们在那里讨论了好久,最后好像是看中了我的CTSC和APIO的成绩才把我从边缘拉进来的。当时心里真是好开心呀,背上的石头都垮啦垮啦的落下地了。怎么感觉人品都用在这上面了……

总而言之,搞OI既要看实力,有时候也要看看运气和发挥。我感觉我有时候就是沉不住气,考试的时候如果做得不顺利心里就总是会发虚。平时的时候就是随便玩玩,也就没有什么心理压力,然而真正踏上战场的时候却总是会患得患失,脑子就不太好使,然后实力也不是特别强,可能这些就是导致我总是失利的主要原因吧。我也不知道自己算不算尽力了,有没有什么遗憾,不过结果已经是这样了,也就没有太多好说的了。

最后祝各位Au爷进队快乐,也祝和我一样失利的同学们高考加油吧。(^_^)

最小割计数个人心得

2015-03-23 21:32:36 By Gromah

前面的点我直接拿 K 小割跑的。。。

中间有些点是一些串并联图,

直接把那些串并联图弄出来单独 K 小割,

然后再带回原图弄一弄就好了。。。

8、9、10 就是对偶图的最短路计数嘛。。。

然后就做完了。。。

Orz PoPoQQQ

大作死

2015-03-12 20:08:57 By Gromah

$----------------------------$

$No$ $zuo$ $no$ $die$ $why$ $you$ $try$ $?$

$I$ $try$ $I$ $die$ $I$ $only$ $sigh$ $.$

$----------------------------$

$I$ $cry$

$----------------------------$

$I$ $cover$ $my$ $face$

捂脸熊

$----------------------------$

$I$ $hold$ $the$ $bomb$ $and$ $go$ $to$ $die$

炸弹熊

$----------------------------$

POI 2014 Solar Lamps (只是试一下Markdown)

2015-03-04 20:48:10 By Gromah

如题所述,只是试一下Markdown

所以我就不发题面了=_=

不如当一个萌萌哒链接菌吧=_=

毕竟我懒=_=

题目传送门

Solution

卧槽。【总领全文,奠定感情基调】

首先我们可以进行坐标变换。

如果两个向量构成一组基底,

我们可以把平面内每个的坐标 $(x_i,y_i)$ 变换成 $(a_i,b_i)$,

使得:

$$a_i \times x_1 + b_i \times x_2 = x_i$$

$$a_i \times y_1 + b_i \times y_2 = y_i$$

于是我们可以求得 $a_i$ 和 $b_i$:

$$a_i = \frac{x_i \times y_2 - y_i \times x_2}{x_1 \times y_2 - x_2 \times y_1}$$

$$b_i = \frac{x_i \times y_1 - y_i \times x_1}{x_1 \times y_2 - x_2 \times y_1}$$

然后我们发现这些坐标都是分数,

而且最重要的是:分母都是一样的。

于是我们可以令所有的坐标都乘以这个分母(要保证乘的是正的数字)。

于是我们就可以离散化这些点的坐标,使得坐标范围变成一个$ (1, 1) - (n, m) $的矩阵。

于是再给点以 $b_i$ 为第一关键字,$a_i$ 为第二关键字排序,

并按照这个顺序处理那些点。

这样我们后面的点的 $b$ 坐标就一定大于等于前面的点的 $b$ 坐标,

就可以不用管这一维了,只用管 $a$ 坐标了。

于是我们假设处理到第 $i$ 个灯泡,

令 $t$ 为以 $(1, 1)$ 为左下角,$(a_i, b_i)$ 为右上角的矩阵中 $Ans[]$ 第 $K[i]$ 小的值。

那么 $Ans[i] = min(i, t)$。

特别的,如果那个矩阵中没有$K[i]$多灯泡,$Ans[i] = i$。

于是怎么维护呢?

【插入操作】

我们以时间为 $Ans[]$ 第一关键字建立线段树,套上以 $a$ 坐标为第二关键字的平衡树。

每次插入都会在 $O(\log n)$ 个线段树结点所套的平衡树中进行时间为 $O(\log n)$ 的插入操作,

于是插入操作的时间复杂度是 $O(\log^2 n)$ 的。

【查询操作】

怎么查询以 $(1, 1)$ 为左下角,$(a_i, b_i)$ 为右上角的矩阵中 $Ans[]$ 第 $K[i]$ 小的值呢?

我们可以二分答案。

具体做法就是从线段树根结点开始,先看左儿子所套的平衡树里边 $a$ 坐标小于等于 $a_i$ 的结点个数。

设有 $u$ 个,那么就说明 $Ans[]$ 在 $[l, mid]$ 区间内的,

并且在以 $(1, 1)$ 为左下角,$(a_i, b_i)$ 为右上角的矩阵中的点有 $u$ 个。

如果 $u \ge K[i]$,说明答案应该在 $[l, mid]$ 之间,然后递归处理。

否则答案就应该在 $[mid + 1, r]$ 之间,然后递归处理。

直到 $l = r$ 的时候,便可确定 $Ans[i] = min(i, l)$。

然后我们可以加上一个小优化:

如果递归处理到 $[l, r]$ 的区间,并且有 $l \ge i$,

那么直接返回 $i$,

因为 $Ans[i] = min(i, l)$,

如果可能的最小值都不比 $i$ 小了,那么就没有做下去的必要了。

查询操作中,我们要访问 $O(\log n)$ 个线段树结点,在每个线段树节点中,都要 $O(\log n)$ 地查找相关点的个数。

所以查询操作的时间复杂度也是 $O(\log^2 n)$ 的。

然后有 $O(n)$ 个灯泡,所以总时间复杂度是 $O(n \log^2 n)$ 的。

每个灯泡的信息会被插入到 $O(\log n)$ 个线段树所套的平衡树里,

所以空间复杂度是 $O(n \log n)$ 的。

如果写矩形树(其实就是二维线段树TAT这只不过是我生造的名字)的话空间复杂度就是 $O(n \log^2 n)$ 的,承受不了。

所以才要写这种蛋疼的东西。。。

卧槽。【承上启下,推动情节发展】

等等。

我们好像忽略了一点:

如果灯的照射范围是一条线该怎么办。。。

啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊。。。

其实也比较好处理。

我们把另一个向量弄成垂直于当前的这条向量。

可以令 :$x_2 = -y_1$,$y_2 = x_1$

然后也可以求出点的 $a$ 坐标和 $b$ 坐标,

只不过在查询的时候,我们找的就不是矩阵中点的个数,

而是某一条线段里边的点的个数了。

稍微处理一下就可以了。。。=_=

具体实现可以看我的代码。

卧槽。【总结全文,升华文章主旨】

毕竟 $Gromah$ 太弱,只会做水题。

#include <cmath>
#include <cstdio>
#include <vector>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long LL;
#define N 200000 + 5
#define M 524288 + 5
#define SIZE 5000000 + 5
#define ls(x) x << 1
#define rs(x) x << 1 | 1

int n, tot, Ord[N], Root[M], Ans[N], K[N];
LL x_1, y_1, x_2, y_2, X[N], Y[N], _X[N], _Y[N];

struct Data
{
    int l, r, fa, size, num, fix;
}h[SIZE];

inline void update(int x)
{
    h[x].size = h[h[x].l].size + h[h[x].r].size + h[x].fix;
}

inline void zig(int x)
{
    int y = h[x].fa, z = h[y].fa;
    if (y == h[z].l) h[z].l = x;
    if (y == h[z].r) h[z].r = x;
    h[x].fa = z, h[y].fa = x;
    h[y].l = h[x].r, h[h[x].r].fa = y, h[x].r = y;
    update(y), update(x);
}

inline void zag(int x)
{
    int y = h[x].fa, z = h[y].fa;
    if (y == h[z].l) h[z].l = x;
    if (y == h[z].r) h[z].r = x;
    h[x].fa = z, h[y].fa = x;
    h[y].r = h[x].l, h[h[x].l].fa = y, h[x].l = y;
    update(y), update(x);
}

inline void Splay(int &root, int x)
{
    while (h[x].fa)
    {
        int y = h[x].fa, z = h[y].fa;
        if (x == h[y].l)
        {
            if (y == h[z].l) zig(y);
            zig(x);
        }
        else
        {
            if (y == h[z].r) zag(y);
            zag(x);
        }
    }
    root = x;
}

inline void Insert(int &root, int u)
{
    if (!root)
    {
        root = ++ tot;
        h[tot].size = h[tot].fix = 1, h[tot].num = u;
        return ;
    }
    int z, p = root;
    while (p)
    {
        z = p;
        h[z].size ++;
        if (u == h[z].num)
        {
            h[z].fix ++;
            return ;
        }
        if (u > h[z].num)
            p = h[z].r;
        else p = h[z].l;
    }
    h[++ tot].fix = 1;
    h[tot].size = 1;
    h[tot].num = u;
    h[tot].fa = z;
    if (u > h[z].num)
        h[z].r = tot;
    else h[z].l = tot;
    Splay(root, tot);
}

inline int Find(int x, int k, bool op)
{
    int res = 0;
    while (1)
    {
        if (!x)
        {
            if (op) return 0;
            break ;
        }
        if (k == h[x].num)
        {
            if (op) return h[x].fix;
            res += h[h[x].l].size + h[x].fix;
            break ;
        }
        else if (k > h[x].num)
        {
            res += h[h[x].l].size + h[x].fix;
            x = h[x].r;
        }
        else x = h[x].l;
    }
    return res;
}

inline int Query(int x, int l, int r, int k, int lim, int Lim, bool op)
{
    if (l >= Lim) return Lim;
    if (l == r) return l;
    int mid = l + r >> 1;
    int t = Find(Root[ls(x)], lim, op);
    if (k <= t)
        return Query(ls(x), l, mid, k, lim, Lim, op);
    else return Query(rs(x), mid + 1, r, k - t, lim, Lim, op);
}

inline void Modify(int x, int l, int r, int t, int k)
{
    Insert(Root[x], k);
    if (l == r) return ;
    int mid = l + r >> 1;
    if (t <= mid)
        Modify(ls(x), l, mid, t, k);
    else Modify(rs(x), mid + 1, r, t, k);
}

inline int getint()
{
    char ch = '\n';
    for (; ch != '-' && (ch > '9' || ch < '0'); ch = getchar()) ;
    int f = ch == '-' ? -1 : 1;
    int res = ch == '-' ? 0 : ch - '0';
    for (ch = getchar(); ch >= '0' && ch <= '9'; ch = getchar())
        res = (res << 3) + (res << 1) + ch - '0';
    return res * f;
}

inline bool cmp(int u, int v)
{
    return X[u] < X[v] || (X[u] == X[v] && Y[u] < Y[v]);
}

inline void Solve(bool op)
{
    if (op) x_2 = -y_1, y_2 = x_1;
    int f = (x_2 * y_1 - x_1 * y_2 > 0) ? 1 : -1;
    for (int i = 1; i <= n; i ++)
    {
        LL u = getint(), v = getint();
        _X[i] = X[i] = (x_2 * v - y_2 * u) * f;
        _Y[i] = Y[i] = (y_1 * u - x_1 * v) * f;
    }
    sort(_X + 1, _X + n + 1);
    sort(_Y + 1, _Y + n + 1);
    int sx = unique(_X + 1, _X + n + 1) - _X;
    int sy = unique(_Y + 1, _Y + n + 1) - _Y;
    for (int i = 1; i <= n; i ++)
    {
        int u = lower_bound(_X + 1, _X + sx, X[i]) - _X;
        int v = lower_bound(_Y + 1, _Y + sy, Y[i]) - _Y;
        X[i] = u, Y[i] = v;
        Ord[i] = i, K[i] = getint();
    }
    sort(Ord + 1, Ord + n + 1, cmp);
    for (int i = 1; i <= n; i ++)
    {
        int _i = Ord[i];
        if (Find(Root[1], Y[_i], op) < K[_i]) Ans[_i] = _i;
            else Ans[_i] = Query(1, 1, n, K[_i], Y[_i], _i, op);
        Modify(1, 1, n, Ans[_i], Y[_i]);
    }
}

int main()
{
    #ifndef ONLINE_JUDGE
        freopen("3833.in", "r", stdin);
        freopen("3833.out", "w", stdout);
    #endif

    n = getint();
    x_1 = getint(), y_1 = getint();
    x_2 = getint(), y_2 = getint();
    Solve(x_1 * y_2 == x_2 * y_1);
    for (int i = 1; i <= n; i ++)
        printf("%d%c", Ans[i], " \n"[i == n]);

    return 0;
}
Gromah Avatar