@Falsyta 2016-02-12T14:45:17.000000Z 字数 46614 阅读 2165

颓废实录

OI

难度说明

[0-] 一眼题
[0-+] 唯一难度是代码的题目
[0] 极其显然的题目
[0+] 或许不是很简单但个人认为没有太大价值的题目
[0++] 或许有些难度但总觉得思路过于模板/陈旧的题目
[1-] 稍微想想就显然的题目
[1] 需要一会思考然后显然的题目
[1+] 需要好好想想的题目
[1++] 好好想想后依然难度不小的题目
<1++的是大部分自己独立想出来的题目
[2--] 为什么我这都不会啊啊（傲娇（才不是呢！
[2-] 思路似乎不那么显然的题目（其实是因为我太弱了）
[2-+] 思路有点厉害还难写的题目
[2] 思路有点优美的题目
[2+] 思路优美的题目
[2++] 思路优美还难写的题目
[3] 吓人的题目

进度

ASC01: 6/8
ASC02: 5/8
ASC30: 4/10
PA2011: 15/25 https://zybuluo.com/Falsyta/note/202488
AMPPZ2014: 6/11 https://zybuluo.com/Falsyta/note/202187
2014年国家集训队作业: 16/158
TCO 2012 L3: 5/12
TCO 2013 L3: 12/12 https://zybuluo.com/Falsyta/note/182557

尚未填坑

BOI2014 portals 传送门只用来横着从一堵墙到另外一堵墙吧……似乎BFS就好了。
BOI2014 postman 欧拉回路可以一遍DFS求吧。
ONTAK2015 bad 感觉在next树上做个DP就好了？（雾……
ONTAK2015 baj 似乎直接线段树做过去就好了吧……
ONTAK2015 cie 暴力枚举一个断点，剩下一个预处理什么的似乎就好了
ONTAK2015 stu 似乎是裸线段树……？

[0]CF256D Liars and Serge
[2-]CF325E The Red Button
[0-+]CF335D Rectangles and Square
[1-]TCO2012 Round 1A EllysLights
[0]CF305E Playing with String
[2-]CF235E Number Challenge
[2-]CF238E Meeting Her
[0-]CF582A GCD Table
[0]CF582B Once Again...
[2-+]CF317E Princess and Her Shadow
[2-]PA2011 pec
[1-]PA2011 pod
[0]CF263E Rhombus
[1-]CF360D Levko and Sets
[2-]PA2011 prz
[2-]TCO2012 Round 1B FoxAndPhotography
[0+]BZOJ2393
[2-+]TCO2012 Round 2A EvenPaths
[0]TCO2012 Round 1C PasswordXPalindrome
[1-]PA2011 pie
[0-]CF585B Phillip and Trains
[1]CF585C Alice, Bob, Oranges and Apples
[0]CF585D Lizard Era: Beginning
[1]ASC02 A Non Absorbing DFA
[2++]PA2009 sza
[1+]CC AUTHEN
[1]CC SKIRES
[2]CC E5
[3-]CEOI2015 indcyc
[1]AMPPZ2014 ben
[0+]AMPPZ2014 cen
[1]AMPPZ2014 glo
[0]AMPPZ2014 fil
[1]AMPPZ2014 ins
[2]BOI2014 sequence
[2]AMPPZ2014 hit
[1]PA2011 bwp
[1+]PA2011 kan
[1]PA2011 aut
[0]CF590A Median Smoothing
[0]CF590C Three States
[0]CF590D Top Secret Task
[1]PA2011 cia
[1]USACO JAN09 Safe Travel
[0+]PA2011 wyb
[1]SRM533 L3 Pikachu
[2-]USACO DEC05 Cow Patterns
[2--]USACO NOV07 Best Cow Line
[0]ASC30 F Sqrt Nim
[0]ASC30 D Currency Exchange
[0]ASC30 B Signed Derangements
[1]ASC30 I Segment Transformation
[1-]PA2011 bio
[2-]PA2011 wyz

10.1 木曜日

CF256D Liars and Serge

傻逼打表题……（不过其实似乎迭代的话不打也是能过的……

CF325E The Red Button

把 $2i$ 和 $2i+1$ 缩成一个点后问题变成了求欧拉回路。
注意到如果 $2i$ 和 $2i+1$ 在不同的回路里，我们只需要交换它们的后继就可以合并两个回路了。

# include <cstdio>
# include <cstring>
# define NR 100100
int p[NR], n;
void dfs (int x)
{
    if (p[x] != -1) return ;
    int y = (x + n / 2) % n;
    if (p[y] != -1) dfs (p[x] = (2 * x + (p[y] == 2 * x % n)) % n);
    else 
    {
        dfs (p[x] = 2 * x % n);
        if (p[y] == -1) p[y] = p[x], dfs (p[x] = (2 * x + 1) % n);
    }
}
int main ()
{
    scanf ("%d", &n);
    if (n % 2) return puts ("-1"), 0;
    memset (p, -1, sizeof (p));
    dfs (0), printf ("0 ");
    for (int i = p[0]; i; i = p[i]) printf ("%d ", i);
    printf ("0\n");
    return 0;
}

CF335D Rectangles and Square

考虑暴力枚举正方形的左边界，以此可以很容易地判定上下右边界是否合法以及正方形是否被填满。
时间复杂度 $O(N+W^2)$ 。

# include <cstdio>
# include <cstring>
# include <algorithm>
# include <vector>
# include <iostream>
using namespace std;
# define REP(i, n) for (int i = 1; i <= n; i ++)
# define REP_0(i, n) for (int i = 0; i < n; i ++)
# define REP_0N(i, n) for (int i = 0; i <= n; i ++)
# define FOR(i, a, b) for (int i = a; i <= b; i ++)
# define W 3000
# define NR 401000
int su[W + 2][W + 2], xsz, ysz, belX[W + 2][W + 2], belY[W + 2][W + 2], li[NR], len, n;
struct Rect
{
    int xl, xr, yl, yr;
    void init ()
    {
        scanf ("%d%d%d%d", &xl, &yl, &xr, &yr);
        FOR (i, xl + 1, xr) FOR (j, yl + 1, yr) ++ su[i][j];
    }   
} a[NR];
struct Seg
{
    int l, r, t;
    Seg () {l = r = t = 0;}
    Seg (int _l, int _r, int _t) {l = _l, r = _r, t = _t;}  
} sX[NR], sY[NR];
vector <int> xP[W + 2];
inline bool cmp (Seg a, Seg b) 
{
    if (a.t != b.t) return a.t < b.t; 
    if (a.l != b.l) return a.l < b.l;
    return a.r > b.r;
}
inline int sum (int xl, int xr, int yl, int yr) {return su[xr][yr] - su[xl - 1][yr] - su[xr][yl - 1] + su[xl - 1][yl - 1];}
int main ()
{
    scanf ("%d", &n);
    REP (i, n)
    {
        a[i].init ();
        sX[2 * i - 1] = Seg (a[i].xl, a[i].xr, a[i].yl);
        sX[2 * i]     = Seg (a[i].xl, a[i].xr, a[i].yr);
        sY[2 * i - 1] = Seg (a[i].yl, a[i].yr, a[i].xl);
        sY[2 * i]     = Seg (a[i].yl, a[i].yr, a[i].xr);
    }
    REP (i, W) REP (j, W) su[i][j] += su[i - 1][j] + su[i][j - 1] - su[i - 1][j - 1];
    sort (sX + 1, sX + 2 * n + 1, cmp);
    sort (sY + 1, sY + 2 * n + 1, cmp);
    sX[2 * n + 1].t = sY[2 * n + 1].t = -1;
    REP (i, 2 * n)
    {
        belX[sX[i].l][sX[i].t] = belX[sX[i].r][sX[i].t] = ++ xsz;
        while (sX[i].t == sX[i + 1].t && sX[i + 1].l <= sX[i].r)
            ++ i, belX[sX[i].l][sX[i].t] = belX[sX[i].r][sX[i].t] = xsz;
    }
    REP (i, 2 * n)
    {
        belY[sY[i].t][sY[i].l] = belY[sY[i].t][sY[i].r] = ++ ysz; int t = i, R = sY[i].r;
        while (sY[i].t == sY[i + 1].t && sY[i + 1].l <= R)
            R = max (R, sY[++ i].r), belY[sY[i].t][sY[i].l] = belY[sY[i].t][sY[i].r] = ysz;
        FOR (j, t, i) xP[sY[j].t].push_back (sY[j].l), xP[sY[j].t].push_back (sY[j].r);
    }
    REP_0N (x, W)
    {
        sort (xP[x].begin (), xP[x].end ());
        xP[x].erase (unique (xP[x].begin (), xP[x].end ()), xP[x].end ());
        int tl = xP[x].size ();
        REP_0 (i, tl)
            FOR (j, i + 1, tl - 1)
            {
                int yi = xP[x][i], yj = xP[x][j], z = yj - yi;
                if (belY[x][yi] != belY[x][yj]) break;
                if (belX[x][yi] != belX[x + z][yi] || belX[x][yj] != belX[x + z][yj] || belY[x + z][yi] != belY[x + z][yj]) 
                    continue;
                if (sum (x + 1, x + z, yi + 1, yj) == z * z)
                {
                    REP (id, n)
                        if (x <= a[id].xl && a[id].xr <= x + z && yi <= a[id].yl && a[id].yr <= yj)
                            li[++ len] = id;
                    printf ("YES %d\n", len);
                    REP (t, len) printf ("%d ", li[t]);
                    return 0;
                }
            }
    }
    puts ("NO");
    return 0;
}

TCO2012 Round 1A EllysLights

# include <cstdio>
# include <cstring>
# include <string>
# include <vector>
using namespace std;
# define REP(i, n) for (int i = 1; i <= n; i ++)
# define REP_0(i, n) for (int i = 0; i < n; i ++)
# define REP_G(i, x) for (int i = pos[x]; i; i = g[i].frt)
# define ER 10000
# define PR 200
# define v g[i].y
struct Edge {int y, frt, val; void set (int yr, int fr, int vl) {y = yr, frt = fr, val = vl;}} g[ER];
int pos[PR], gsz;
inline void AE (int x, int y, int z) {g[++ gsz].set (y, pos[x], z), pos[x] = gsz;}
class EllysLights
{
private:
    int __cnt[2], q[PR];
    bool vis[PR], state[PR], failed, col[PR];
    vector <int> ctrled[PR], ctrl[PR];
    void dfs (int x, bool c) 
    {
        if (vis[x]) {if (c != col[x]) failed = true; return ;}
        vis[x] = true, ++ __cnt[col[x] = c]; 
        REP_G (i, x) dfs (v, c ^ g[i].val);
    }
public:
    int getMinimum (string init, vector <string> trans)
    {
        int n = init.length (), m = trans.size ();
        REP_0 (i, m)
            REP_0 (j, n)
                if (trans[i][j] == 'Y') 
                    ctrled[j + 1].push_back (i + 1), 
                    ctrl[i + 1].push_back (j + 1);
        int ans = 0, head = 1, tail = 0;
        REP (i, n) state[i] = init[i - 1] == 'Y';
        REP (i, n)
        {
            if (state[i])
            {
                if (!ctrled[i].size ()) return -1;
                if (ctrled[i].size () == 1) q[++ tail] = i;
            }
            else
            {
                if (!ctrled[i].size ()) vis[m + i] = true;
                if (ctrled[i].size () == 1) q[++ tail] = i;
            }
        }
        while (head <= tail)
        {
            int x = q[head ++]; vis[m + x] = true;
            int y = ctrled[x][0];
            if (vis[y]) continue;
            REP_0 (i, ctrl[y].size ())
                if (ctrl[y][i] != x)
                {
                    int z = ctrl[y][i]; state[z] ^= state[x];
                    REP_0 (j, ctrled[z].size ()) if (ctrled[z][j] == y) ctrled[z].erase (ctrled[z].begin () + j);
                    if (state[z])
                    {
                        if (!ctrled[z].size ()) return -1;
                        if (ctrled[z].size () == 1) q[++ tail] = z;
                    }
                    else
                    {
                        if (!ctrled[z].size ()) vis[m + z] = true;
                        if (ctrled[z].size () == 1) q[++ tail] = z;
                    }
                }
            vis[y] = true, ans += state[x];
        }
        head = 1, tail = 0;
        REP (i, n) if (!vis[m + i]) AE (ctrled[i][0], ctrled[i][1], state[i]), AE (ctrled[i][1], ctrled[i][0], state[i]);
        REP (i, m) if (!vis[i]) __cnt[0] = __cnt[1] = 0, dfs (i, 0), ans += min (__cnt[0], __cnt[1]);
        if (failed) return -1;
        return ans;
    }
};

10.2 金曜日

机房好吵>_<

CF305E Playing with String

一开始读错题了QAQ

显然只需要满足 $s[i-1]=s[i+1]$ 就是可选的。
把连续可选的一段缩在一起，显然段与段之间是相互独立的。
$SG$ 函数一算就没了。

# include <cstdio>
# include <cstring>
# include <algorithm>
using namespace std;
# define REP(i, n) for (int i = 1; i <= n; ++ i)
# define FOR(i, a, b) for (int i = a; i <= b; ++ i)
# define RST(a) memset (a, 0, sizeof (a))
# define NR 20000
char s[NR];
bool vis[NR];
int sg[NR], cov[NR], last[NR];
int main ()
{
    scanf ("%s", s + 1); int n = strlen (s + 1);
    sg[0] = 0, sg[1] = 1;
    FOR (i, 2, n)
    {
        RST (vis);
        REP (j, i) vis[sg[max (0, j - 2)] ^ sg[max (0, i - j - 1)]] = true;
        while (vis[sg[i]]) ++ sg[i];
    }
    int lst = -1, ans = 0;
    FOR (i, 2, n - 1)
    {
        if (s[i - 1] == s[i + 1]) {if (lst == -1) lst = i;}
        else if (lst != -1) 
        {
            FOR (j, lst, i - 1) cov[j] = i - lst;
            ans ^= sg[i - lst], lst = -1;
        }
        last[i] = lst;
    }
    if (lst != -1) 
    {
        FOR (i, lst, n - 1) cov[i] = n - lst;
        ans ^= sg[n - lst];
    }
    if (!ans) return puts ("Second"), 0;
    FOR (i, 2, n - 1)
    {
        if (s[i - 1] != s[i + 1]) continue;
        int j = i - last[i] + 1;
        if (!(ans ^ sg[cov[i]] ^ sg[max (0, j - 2)] ^ sg[max (0, cov[i] - j - 1)]))
            return printf ("First\n%d\n", i), 0;
    }
    return 0;
}

10.3 土曜日

CF235E Number Challenge

自己为什么这种傻逼题都不会做啊QAQ

# include <cstdio>
# define REP(i, n) for (int i = 1; i <= n; i ++)
# define FOR(i, a, b) for (int i = a; i <= b; i ++)
# define NR 2010
# define QR 4010000
int A, B, C, f[QR], g[QR], pr[NR], psz, mu[NR];
bool vis[NR];
int main ()
{
    scanf ("%d%d%d", &A, &B, &C); int AB = A * B;
    REP (i, A) REP (j, B) f[i * j] ++;
    mu[1] = 1;
    REP (i, C)
    {
        int t = 0;
        for (int j = 1; i * j <= C; j ++) t += C / (i * j);
        if (i != 1) 
        {
            if (!vis[i]) pr[++ psz] = i, mu[i] = -1;
            for (int j = 1; j <= psz && i * pr[j] <= C; j ++)
            {
                vis[i * pr[j]] = true;
                if (i % pr[j] == 0) {mu[i * pr[j]] = 0; break;}
                else mu[i * pr[j]] = - mu[i];
            }
        }
        t *= mu[i]; int tl = AB / i;
        REP (j, tl) g[i * j] += t;
    }
    int ans = 0;
    REP (i, AB) 
    {
        int h = 0, tl = AB / i;
        REP (j, tl) h += f[i * j];
        ans += g[i] * h;
    }
    printf ("%u\n", (unsigned) ans & ((1 << 30) - 1));
    return 0;
}

CF238E Meeting Her

自己为什么这种傻逼题都不会做啊QAQ

对于每个公交线路建出最短路图。

考虑最坏 $k$ 步可以到达 $b$ 的点。
若一个在公交线路 $i$ 的割点 $x$ ，满足从 $x$ 到 $t_i$ 的所有路径上都至少有一个最坏 $k-1$ 步可以到达 $b$ 的点，则 $x$ 最坏 $k$ 步可以到达 $b$ 。
然后就暴力。
话说DAG中判割点有什么不用算方案数的好方法啊……

# include <cstdio>
# define REP(i, n) for (int i = 1; i <= n; ++ i)
# define NR 300
template <class T0, class T1> inline bool RlxN (T0 &x, const T1 &y) {if (x > y) return x = y, true; return false;}
const int inf = (1 << 30) - 2;
int n, m, S, T, K, cur, g[NR][NR], d[NR][NR], fv[NR], sR[NR], tR[NR];
bool e[NR][NR], reach[NR], newr[NR];
bool dfs (int x)
{
    if (x == tR[cur]) return reach[x];
    if (fv[x] != -1) return fv[x];
    bool res = true;
    REP (v, n) if (e[x][v] && g[sR[cur]][x] + 1 + g[v][tR[cur]] == g[sR[cur]][tR[cur]]) res &= dfs (v);
    res |= reach[x];
    if (res && d[sR[cur]][x] * d[x][tR[cur]] == d[sR[cur]][tR[cur]]) newr[x] = true;
    return fv[x] = res;
}
int main ()
{
    scanf ("%d%d%d%d", &n, &m, &S, &T);
    if (S == T) return puts ("0"), 0;
    int t1, t2;
    REP (i, n) REP (j, n) g[i][j] = inf;
    REP (i, m) scanf ("%d%d", &t1, &t2), g[t1][t2] = d[t1][t2] = 1, e[t1][t2] = true;
    REP (k, n) 
        REP (i, n) 
            REP (j, n) 
            {
                if (g[i][j] > g[i][k] + g[k][j]) g[i][j] = g[i][k] + g[k][j], d[i][j] = d[i][k] * d[k][j];
                else if (g[i][j] == g[i][k] + g[k][j]) d[i][j] += d[i][k] * d[k][j];
            }
    REP (i, n) g[i][i] = 0, d[i][i] = 1;
    scanf ("%d", &K);
    REP (i, K) scanf ("%d%d", &sR[i], &tR[i]);
    reach[T] = true;
    REP (i, n)
    {
        for (cur = 1; cur <= K; ++ cur) 
        {
            if (d[sR[cur]][tR[cur]] == 0) continue;
            REP (j, n) fv[j] = -1; dfs (sR[cur]);
        }
        REP (j, n) reach[j] = newr[j];
        if (reach[S]) return printf ("%d\n", i), 0;
    }
    puts ("-1");
    return 0;
}

CF582A GCD Table

当时想都没想就一个map上去……
后来发现似乎是统计出现奇数次的数就好了……

# include <cstdio>
# include <cassert>
# include <map>
# define REP(i, n) for (int i = 1; i <= n; i ++)
using namespace std;
map <int, int> vis;
int li[1000010], len, n;
int gcx (int a, int b) {return !b ? a : gcx (b, a % b);}
int main ()
{
    scanf ("%d", &n); int N = n * n, ta;
    REP (i, N) scanf ("%d", &ta), ++ vis[ta];
    for (map <int, int>::reverse_iterator it = vis.rbegin (); it != vis.rend ();)
    {
        if (!it->second) {++ it; continue;}
        it->second --;
        printf ("%d ", li[++ len] = it->first);
        REP (i, len - 1) vis[gcx (li[len], li[i])] -= 2;
    }
    puts ("");
    return 0;
}

CF582B Once Again...

也不知道这种一眼大暴力为什么自己1h才A。

# include <cstdio>
# include <algorithm>
using namespace std;
# define REP(i, n) for (int i = 1; i <= n; ++ i)
# define REP_0(i, n) for (int i = 0; i < n; ++ i)
# define REP_D(i, n) for (int i = n; i >= 1; -- i)
# define REP_0N(i, n) for (int i = 0; i <= n; ++ i)
# define FOR(i, a, b) for (int i = a; i <= b; ++ i)
# define W 300
int n, T, cnt[400], f[400], fv[400], a[400];
int main ()
{
    scanf ("%d%d", &n, &T);
    int N = n * n;
    if (N * 3 > T * n) N = T * n;
    REP (i, n) scanf ("%d", &a[i]), ++ cnt[a[i]];
    REP (i, N)
    {
        int w = a[(i - 1) % n + 1];
        ++ f[w];
        REP_0 (j, w) f[w] = max (f[w], f[j] + 1);
    }
    if (N == T * n)
    {
        int ans = 0;
        REP_0N (i, W) ans = max (ans, f[i]);
        return printf ("%d\n", ans), 0;
    }
    REP_D (i, N)
    {
        int w = a[(i - 1) % n + 1];
        ++ fv[w];
        FOR (j, w + 1, W) fv[w] = max (fv[w], fv[j] + 1);
    }
    int ans = 0;
    REP (i, W)
    {
        int f0 = 0, f1 = 0;
        REP_0N (j, i) f0 = max (f0, f[j]);
        FOR (j, i, W) f1 = max (f1, fv[j]);
        ans = max (ans, f0 + f1 + cnt[i] * (T - n * 2));
    }
    printf ("%d\n", ans);
    return 0;
}

10.4 日曜日

CF317E Princess and Her Shadow

写之前：哎他们写的为什么这么长呀0.0
写之后：我写的为毛这么长T T

结合昨天晚上爆炸的CF，得出了自己应该退役的好消息。

一直想怎么才能在树林里绕……却连可以走出树林这种事都不知道……
追影子走追出树林。
然后乱撞就行了……

# include <cstdio>
# include <cstring>
# include <algorithm>
using namespace std;
# define REP(i, n) for (int i = 1; i <= n; i ++)
# define REP_0(i, n) for (int i = 0; i < n; i ++)
# define NR 500
# define SR 200000
struct Poi {int x, y; Poi () {x = y = 0;} Poi (int _x, int _y) : x(_x), y(_y) {}} q[SR], po[NR];
int n, vX, vY, sX, sY, cX, cY, minX, minY, maxX, maxY, up, dw, lf, rt; 
int pre[NR][NR], li[SR], len, qi[SR];
bool tree[NR][NR];
int dx[] = {0, 0, -1, 1};
int dy[] = {-1, 1, 0, 0};
char dirc[] = "DULR";
# define W 400
inline int sgn (int x) {return x > 0 ? 1 : x < 0 ? -1 : 0;}
inline bool existTree (int x, int y) {if (x < minX || y < minY || x > maxX || y > maxY) return false; return tree[x][y];}
void bfs ()
{
    int head = 1, tail = 1; q[1] = Poi (vX, vY), pre[vX][vY] = -1;
    while (head <= tail)
    {
        Poi u = q[head ++];
        REP_0 (d, 4)
        {
            int _x = u.x + dx[d], _y = u.y + dy[d];
            if (!existTree (_x, _y) && !pre[_x][_y] && 0 <= _x && _x <= W && 0 <= _y && _y <= W) 
                q[++ tail] = Poi (_x, _y), pre[_x][_y] = d + 1;
        }
    }
}
# define pc putchar
inline int area (int x, int y) {return (x < minX ? -3 : x > maxX ? 3 : 0) + (y < minY ? -1 : y > maxY ? 1 : 0);}
inline int dLf () {vY --, sY --, pc (dirc[0]);}
inline int dRt () {vY ++, sY ++, pc (dirc[1]);}
inline int dUp () {vX --, sX --, pc (dirc[2]);}
inline int dDw () {vX ++, sX ++, pc (dirc[3]);}
void towardsX (int Sj, int Tj) {while ((area (sX, sY) + 4) / 3 != Tj || (area (vX, vY) + 4) / 3 != Tj) Sj < Tj ? dDw () : dUp ();}
void towardsY (int Si, int Ti) {while ((area (sX, sY) + 4) % 3 != Ti || (area (vX, vY) + 4) % 3 != Ti) Si < Ti ? dRt () : dLf ();}
void moveTo (int S, int T)
{
    if (S == T) return ;
    if (S * T == -1)
    {
        while (area (sX, sY) > -2 || area (vX, vY) > -2) dUp ();
        if (S == -1) while (area (sX, sY) != -2 || area (vX, vY) != -2) dRt ();
        else while (area (sX, sY) != -4 || area (vX, vY) != -4) dLf ();
    }
    else if (S * T == -9)
    {
        while ((area (sX, sY) + 1) % 3 || (area (vX, vY) + 1) % 3) dLf ();
        if (S == -3) while (area (sX, sY) != 2 || area (vX, vY) != 2) dDw ();
        else while (area (sX, sY) != -4 || area (vX, vY) != -4) dUp ();
    }
    else
    {
        int Si = (S + 4) % 3, Sj = (S + 4) / 3, Ti = (T + 4) % 3, Tj = (T + 4) / 3;
        bool bS = S % 3 == 0 || abs (S) < 2, bT = T % 3 == 0 || abs (T) < 2, ord = 0;
        if (!bS && !bT) ord = 0;
        else if (!bS) ord = T % 3 != 0;
        else ord = S % 3 == 0;  
        ord ? (towardsY (Si, Ti), towardsX (Sj, Tj)) : (towardsX (Sj, Tj), towardsY (Si, Ti));
    }
}
void move ()
{
    if (!pre[sX][sY]) {puts ("-1"); return ;}
    for (int x = sX, y = sY; pre[x][y] != -1;) 
    li[++ len] = pre[x][y] - 1, x -= dx[li[len]], y -= dy[li[len]];
    int hi = 1, ti = 0;
    vX = sX, vY = sY;
    REP (i, len) 
    {
        if (i < len - i + 1) swap (li[i], li[len - i + 1]);
        int _x = sX + dx[li[i]], _y = sY + dy[li[i]];
        if (!existTree (_x, _y)) sX = _x, sY = _y, qi[++ ti] = li[i];
    }
    while ((vX != sX || vY != sY) && (area (sX, sY) != area (vX, vY) || area (sX, sY) == 0) && hi <= ti)
    {
        int d = qi[hi ++], _x = sX + dx[d], _y = sY + dy[d];
        vX += dx[d], vY += dy[d];
        if (!existTree (_x, _y)) sX = _x, sY = _y, qi[++ ti] = d;
    }
    if (hi > ti) 
    {
        if (sX != vX || sY != vY) puts ("-1");
        else
        {
            REP (i, len) printf ("%c", dirc[li[i]]);
            REP (i, hi - 1) printf ("%c", dirc[qi[i]]);
        }
        return ;
    }
    REP (i, len) printf ("%c", dirc[li[i]]);
    REP (i, hi - 1) printf ("%c", dirc[qi[i]]);
    moveTo (area (sX, sY), sgn (vX - sX) * 3 + sgn (vY - sY));
    if (vX != sX)
    {
        int t = vX < sX ? up : dw;
        while (sY < po[t].y) dRt ();
        while (sY > po[t].y) dLf ();
        if (vX < sX) {while (sX + 1 < po[t].x) dDw (); while (vX < sX) pc (dirc[3]), vX ++;}
        else {while (sX - 1 > po[t].x) dUp (); while (vX > sX) pc (dirc[2]), vX --;}
    }
    if (vY != sY)
    {
        int t = vY < sY ? lf : rt;
        while (sY < po[t].y) dRt ();
        while (sY > po[t].y) dLf ();
        vY < sY ? dLf () : dRt ();
        while (sX < po[t].x) dDw ();
        while (sX > po[t].x) dUp ();
        if (vY < sY) while (vY < sY) pc (dirc[1]), vY ++;
        else while (vY > sY) pc (dirc[0]), vY --;
    }
}
inline void proc (int &x, int &y) {x -= cX, y -= cY;}
int main ()
{
    scanf ("%d%d%d%d%d", &vX, &vY, &sX, &sY, &n);   
    if (!n) {if (vX != sX || vY != sY) puts ("-1"); return 0;}
    up = dw = lf = rt = -1, minX = minY = 200, maxX = maxY = -200;
    REP (i, n)
    {
        scanf ("%d%d", &po[i].x, &po[i].y);
        minX = min (minX, po[i].x), minY = min (minY, po[i].y);
        maxX = max (maxX, po[i].x), maxY = max (maxY, po[i].y);
        if (up == -1 || po[up].x > po[i].x) up = i;
        if (dw == -1 || po[dw].x < po[i].x) dw = i;
        if (lf == -1 || po[lf].y > po[i].y) lf = i;
        if (rt == -1 || po[rt].y < po[i].y) rt = i;
    }
    cX = min (minX, min (sX, vX)) - 10, cY = min (minY, min (sY, vY)) - 10;
    REP (i, n) proc (po[i].x, po[i].y), tree[po[i].x][po[i].y] = true;
    proc (vX, vY), proc (sX, sY), proc (minX, minY), proc (maxX, maxY);
    bfs (), move ();
    return 0;
}

PA2011 pec

PA2011 pod

CF263E Rhombus

维护几个和就完了……

# include <cstdio>
# include <cmath>
# include <algorithm>
using namespace std;
# define REP(i, n) for (int i = 1; i <= n; ++ i)
# define FOR(i, a, b) for (int i = a; i <= b; ++ i)
# define NR 1010
typedef long long ll;
int b[NR][NR], n, m, K;
ll a[NR][NR], xS[NR][NR], xT[NR][NR], yS[NR][NR], yT[NR][NR], zS[NR][NR];
ll sum[NR][NR], w[NR][NR], pl[NR][NR];
void calc (ll res[NR][NR], bool ty)
{
    res[K][K] = pl[K][K] = 0;
    REP (i, K) REP (j, K) res[K][K] += a[i][j] * max (0, K - abs (i - K) - abs (j - K)), pl[K][K] += a[i][j] * (K - abs (i - K) - abs (j - K) > 0);
    REP (i, n)
    {
        REP (j, m)
        {
            xS[i][j] = xS[i][j - 1] + a[i][j];
            xT[i][j] = xT[i][j - 1] + a[i][j] * j;
            yS[i][j] = yS[i - 1][j] + a[i][j];
            yT[i][j] = yT[i - 1][j] + a[i][j] * i;
            zS[i][j] = zS[i - 1][j + 1] + a[i][j];
            if (K <= i && i <= n - K + 1 && K <= j && j <= m - K + 1)
            {
                if (j == K)
                {
                    if (i != K)
                    {
                        pl[i][K] = pl[i - 1][K] - (zS[i - 1][1] - zS[i - 1 - K][1 + K]) + xS[i][K];
                        res[i][K] = res[i - 1][K] - pl[i - 1][K] + xT[i][K];
                    }
                }
                else
                {
                    pl[i][j] = pl[i][j - 1] - (zS[i][j - K] - zS[i - K][j]) + (yS[i][j] - yS[i - K][j]);
                    res[i][j] = res[i][j - 1] - pl[i][j - 1] + (yT[i][j] - yT[i - K][j] - (i - K) * (yS[i][j] - yS[i - K][j]));
                }
            }
        }
    }
    if (ty)
        FOR (i, K, n - K + 1) 
            FOR (j, K, m - K + 1) 
                res[i][j] -= yT[i][j] - yT[i - K][j] - (i - K) * (yS[i][j] - yS[i - K][j]) + 
                xT[i][j] - xT[i][j - K] - (j - K) * (xS[i][j] - xS[i][j - K]);
}
int main ()
{
    scanf ("%d%d%d", &n, &m, &K);
    REP (i, n) REP (j, m) scanf ("%d", &b[i][j]);
    REP (i, n) REP (j, m) a[i][j] = b[i][j]; calc (sum, 1); REP (i, n) REP (j, m) w[i][j] += sum[i][j];
    REP (i, n) REP (j, m) a[n - i + 1][j] = b[i][j]; calc (sum, 0); REP (i, n) REP (j, m) w[i][j] += sum[n - i + 1][j];
    REP (i, n) REP (j, m) a[i][m - j + 1] = b[i][j]; calc (sum, 0); REP (i, n) REP (j, m) w[i][j] += sum[i][m - j + 1];
    REP (i, n) REP (j, m) a[n - i + 1][m - j + 1] = b[i][j]; calc (sum, 1);  REP (i, n) REP (j, m) w[i][j] += sum[n - i + 1][m - j + 1];
    int _x = 0, _y = 0;
    FOR (i, K, n - K + 1) 
    {
        FOR (j, K, m - K + 1) 
        {
            w[i][j] += K * b[i][j];
            if (w[i][j] >= w[_x][_y]) _x = i, _y = j;
        }
    }
    printf ("%d %d\n", _x, _y);
    return 0;
}

10.5 月曜日

CF360D Levko and Sets

随手用原根算两把再容斥就完了……
想到了自己本来想出的傻逼题……

# include <cstdio>
# include <algorithm>
# include <cassert>
# define REP(i, n) for (int i = 1; i <= n; ++ i)
# define REP_0(i, n) for (int i = 0; i < n; ++ i)
# define REP_D(i, n) for (int i = n; i >= 1; -- i)
# define MOD 1000007
# define T 5000000
# define TR 210
using namespace std;
typedef long long ll;
struct Hash {int p, w, f; inline void set (int _p, int _w, int _f) {p = _p, w = _w, f = _f;}};
struct HashMap
{
    Hash h[T + 10];
    int hp[MOD], sz;
    inline void ins (int p, int w) {h[++ sz].set (p, w, hp[p % MOD]), hp[p % MOD] = sz;}
    inline int find (int p) {for (int i = hp[p % MOD]; i; i = h[i].f) if (h[i].p == p) return h[i].w; return -1;}
} ph, fid;
int li[20000], len, n, m, P, g, a[10100], inv_pow;
ll f[20000];
bool vis[20000];
inline int pr (int a, int z) {int s = 1; do {if (z & 1) s = 1ll * s * a % P; a = 1ll * a * a % P;} while (z >>= 1); return s;}
inline bool check () {REP (i, len) if (li[i] < P - 1 && pr (g, li[i]) == 1) return false; return true;}
inline int findG () {for (g = 2; !check (); ++ g) ; return g;}
template <class Z> Z gcx (Z a, Z b) {return !b ? a : gcx (b, a % b);}
inline int logg (int x)
{
    int t; if ((t = ph.find (x)) != -1) return t;
    REP (i, TR) {x = 1ll * x * inv_pow % P; if ((t = ph.find (x)) != -1) return i * T + t;}
}
void getFac (int n)
{
    for (int i = 1; i * i <= n; ++ i)
    {
        if (n % i) continue;
        li[++ len] = i;
        if (i * i != n) li[++ len] = n / i;
    }
    sort (li + 1, li + len + 1);
    REP (i, len) fid.ins (li[i], i);
}
inline void init ()
{
    getFac (P - 1), findG (); int tp = 1;
    REP_0 (i, T) ph.ins (tp, i), tp = 1ll * tp * g % P;
    inv_pow = pr (tp, P - 2);
}
int calc ()
{
    f[1] = -1;
    REP (i, len)
    {
        if (!vis[i]) continue;
        REP_D (j, len) f[fid.find (1ll * li[i] * li[j] / gcx (li[i], li[j]))] -= f[j];
    }
    f[1] ++;
    int res = 0;
    REP (i, len) res += f[i] * (P - 1) / li[i];
    return res;
}
int main ()
{
    scanf ("%d%d%d", &n, &m, &P), init (); int b, tb;
    REP (i, n) scanf ("%d", &a[i]), a[i] = logg (a[i]);
    scanf ("%d", &b);
    REP (i, m - 1) scanf ("%d", &tb), b = gcx (tb, b);
    REP (i, n) vis[fid.find (gcx (1ll * a[i] * b, P - 1ll))] = true;
    printf ("%d\n", calc ());
    return 0;
}

PA2011 prz

我为什么这种题要看题解T_T 真是没救了……
显然放到模 $K$ 意义下一算就完了……

# include <cstdio>
# include <algorithm>
using namespace std;
const int inf = 1 << 30;
# define REP(i, n) for (int i = 1; i <= n; ++ i)
# define NR 250010
pair <int, int> seg[NR];
int q0, s, k, n, sl;
int main ()
{
    for (scanf ("%d", &q0); q0; -- q0)
    {
        scanf ("%d%d%d", &s, &k, &n); sl = 0;
        int p = 0, tL = -1, tR = k, len; bool succ = true;
        REP (i, n)
        {
            scanf ("%d", &len);
            if (i & 1)
            {
                if (len >= k) succ = false;
                int pl = p, pr = p + len - 1;
                if (pr < k) seg[++ sl] = make_pair (pl, pr);
                else tL = max (tL, pr % k), tR = min (tR, pl);
            }
            p = (p + len) % k;
        }
        if (!succ) {puts ("NIE"); continue;}
        if (tL != -1) seg[++ sl] = make_pair (0, tL);
        if (tR != k) seg[++ sl] = make_pair (tR, k - 1);
        sort (seg + 1, seg + sl + 1);
        int lst = 0; succ = false;
        REP (i, sl)
        {
            if (seg[i].first - lst >= s) {succ = true; break;}
            lst = max (lst, seg[i].second + 1);
        }
        if (k - lst >= s) succ = true;
        puts (succ ? "TAK" : "NIE");
    }
    return 0;
}

TCO2012 Round 1B FoxAndPhotography

显然的状压吧……
$f(S)$ 表示 $A$ 中当前取了状态为 $S$ 的元素来对应 $B$ 中前 $|S|$ 个元素。

# include <cstdio>
# include <algorithm>
# include <vector>
# include <cassert>
# define REP_0(i, n) for (int i = 0; i < n; ++ i)
const int inf = 1 << 30;
using namespace std;
class FoxAndPhotography
{
private:
    int f[1 << 16], n, M;
    vector <int> a, b;
    int search (int s)
    {
        if (f[s] != inf) return f[s];
        int cnt = 1;
        REP_0 (i, n) if (s >> i & 1) ++ cnt;
        int index = cnt - 1;
        REP_0 (i, n)
            if (!(s >> i & 1))
            {
                ++ index; 
                if (a[i] < b[cnt - 1]) f[s] = min (f[s], search (s | 1 << i) + abs (index - cnt));
            }
        if (f[s] == inf) f[s] -= 2;
        return f[s];
    }
public:
    int getMinimumSwaps (vector <int> _a, vector <int> _b)
    {
        a = _a, b = _b;
        n = a.size (), M = 1 << n;
        REP_0 (i, M - 1) f[i] = inf;
        sort (_a.begin (), _a.end ());
        sort (_b.begin (), _b.end ());
        REP_0 (i, n) if (_a[i] >= _b[i]) return -1;
        return search (0);
    }
};

10.6 火曜日

然而打NOIP摸你赛还是象傻逼一样秀智商下限。
被虐的要多惨有多惨。
写一道和BZOJ2393差不多的题发现玄不救非。

10.7 水曜日

前几天太浪了补作业T_T

10.8 木曜日

不想上学了T_T
又开始颓颓颓……

TCO2012 Round 2A EvenPaths

其实知道这题是分段FWT以后就显然的要死了T_T
考虑按照拓扑序把特殊格劈成两段。
为了方便计算强制起点为特殊格子。

暴力枚举前半段的特殊点状态，算出起点到每个前半段特殊点的方案数。
暴力枚举后半段的特殊点状态，算出终点走回每个前半段特殊点的方案数。（前半段的其他特殊点不能走）
（窝一开始居然不会暴力枚举还想着DP以后用子集和卷积……）

然后发现就是FWT了嘛……

乱写一通常数根本不管了T_T

# include <cstdio>
# include <cstring>
# include <vector>
# include <string>
# define REP(i, n) for (int i = 1; i <= n; ++ i)
# define REP_0(i, n) for (int i = 0; i < n; ++ i)
# define REP_D(i, n) for (int i = n; i >= 1; -- i)
# define REP_G(i, n) for (int i = pos[x]; i; i = g[i].frt)
# define RST(a) memset (a, 0, sizeof (a))
using namespace std;
typedef long long ll;
# define NR 100
# define ER 10000
# define MR (1 << 19)
struct Edge {int y, frt; void set (int yr, int fr) {y = yr, frt = fr;}};
# define v g[i].y
class EvenPaths
{
private:
    Edge g[ER];
    int pos[NR], in[NR], q[NR], un[NR], n, gsz, usz, fir, sec;
    ll cntA[MR], cntB[MR], ans;
    vector <int> e[NR];
    bool del[NR], f[NR];
    inline void AE (int x, int y) {g[++ gsz].set (y, pos[x]), pos[x] = gsz, ++ in[y];}
    void Topo ()
    {
        int head = 1, tail = 0, x;
        REP (i, n) if (!in[i]) q[++ tail] = i;
        while (head <= tail)
        {
            x = q[head ++];
            REP_G (i, x) if (!-- in[v]) q[++ tail] = v;
        }
    }
    int bfsFir (int s)
    {
        REP (i, n) f[i] = del[i] = 0;
        REP_0 (i, fir) del[un[i + 1]] = s >> i & 1;
        f[1] = 1;
        REP (t, n)
        {
            int x = q[t]; if (!f[x]) continue;
            REP_G (i, x) if (!del[v]) f[v] ^= 1;
        }
        int res = 0;
        REP_0 (i, fir) if (f[un[i + 1]]) res |= 1 << i;
        return res;
    }
    int bfsSec (int s)
    {
        REP (i, n) f[i] = del[i] = 0;
        REP (i, fir) del[un[i]] = true;
        REP_0 (i, sec) del[un[i + fir + 1]] = s >> i & 1;
        f[2] = 1;
        if (del[2]) return 0;
        REP_D (t, n)
        {
            int x = q[t]; if (!f[x]) continue;
            REP_G (i, x) if (!del[v]) f[v] ^= 1;
        }
        int res = 0;
        REP_0 (i, fir)
        {
            int x = un[i + 1]; bool z = 0;
            for (int y : e[x]) z ^= f[y];
            if (z) res |= 1 << i;
        }
        return res;
    }
    void fwt (ll *a, int l, int r, int ty)
    {
        if (l == r) return ;
        int mid = (l + r) >> 1;
        fwt (a, l, mid, ty); fwt (a, mid + 1, r, ty);
        REP_0 (i, mid - l + 1) a[l + i] += a[mid + 1 + i] * ty;
    }
public:
    ll theCount (vector <string> maze, string rooms)
    {
        n = rooms.length ();
        REP (i, n) REP (j, n) if (maze[i - 1][j - 1] == 'Y') AE (i, j), e[i].push_back (j);
        Topo ();
        int cu = 0; bool v1 = false;
        REP (i, n)
        {
            if (q[i] == 1) un[++ usz] = 1, v1 = true;
            else if (rooms[q[i] - 1] == '?') v1 ? un[++ usz] = q[i] : ++ cu;
        }
        if (rooms[0] == '?') ans += 1ll << (usz - 1);
        fir = (usz + 1) / 2, sec = usz - fir;
        int N = 1, Mf = 1 << (fir - 1), Ms = 1 << sec;
        REP_0 (s, Mf) ++ cntA[bfsFir (s << 1)];
        RST (pos), gsz = 0;
        REP (i, n) REP (j, n) if (maze[i - 1][j - 1] == 'Y') AE (j, i);
        REP_0 (s, Ms) ++ cntB[bfsSec (s)];
        for (; N <= (Mf << 1) || N <= Ms; N <<= 1) ;
        fwt (cntA, 0, N - 1, 1), fwt (cntB, 0, N - 1, 1);
        REP_0 (i, N) cntA[i] *= cntB[i];
        fwt (cntA, 0, N - 1, -1);
        REP_0 (s, N)
        {
            bool b = 0;
            REP_0 (i, fir) if (s >> i & 1) b ^= 1;
            if (!b) ans += cntA[s];
        }
        return ans << cu;
    }
};

TCO2012 Round 1C PasswordXPalindrome

一股想把自己骂死的冲动……
傻逼回家种田去……

# include <cstdio>
# include <string>
# include <algorithm>
using namespace std;
# define REP_0(i, n) for (int i = 0; i < n; ++ i)
class PasswordXPalindrome
{
private:
    int ap[30][2], apr[30], t[100], z[100], ans, len;
public:
    int minSwaps (string s)
    {
        ans = 0, len = s.length (); int si = -1;
        REP_0 (i, 26) ap[i][0] = -1;
        REP_0 (i, len) ++ apr[t[i] = s[i] - 'a'];
        REP_0 (i, len)
        {
            if (apr[t[i]] == 1)
            {
                if (len % 2 == 0) return -1;
                if (si == t[i]) return -1;
                else if (i != len / 2) swap (t[i], t[len / 2]), ++ ans, si = t[i], -- i;
            }
        }
        REP_0 (i, len)
            if (apr[t[i]] == 2)
            {
                if (ap[t[i]][0] == -1) ap[t[i]][0] = i, z[i] = 0;
                else ap[t[i]][1] = i, z[i] = 1;
            }
        REP_0 (i, len)
        {
            if (apr[t[i]] != 2) continue;
            while (ap[t[i]][z[i]] != len - ap[t[i]][!z[i]] - 1)
            {
                int j = len - ap[t[i]][!z[i]] - 1;
                swap (t[i], t[j]), swap (z[i], z[j]);
                ap[t[i]][z[i]] = i;
                ap[t[j]][z[j]] = j;
                ++ ans;
            }
        }
        return ans;
    }
};

10.9 金曜日

颓……

10.10 土曜日

颓……

10.11 日曜日

初赛啦……
瞎写写一个小时就就交了卷回家颓……

10.12 月曜日

deadline快要到了止颓止颓…………QAQ
晚上CF上黄啦www
不过啊……我已经高一了呢……

PA2011 pie

CF585B Phillip and Trains

暴力。

# include <cstdio>
# include <cstring>
# include <cmath>
# include <algorithm>
# include <cassert>
# include <iostream>
using namespace std;
# define REP(i, n) for (int i = 1; i <= n; ++ i)
# define REP_0(i, n) for (int i = 0; i < n; ++ i)
# define REP_G(i, x) for (int i = pos[x]; i; i = g[i].frt)
# define REP_D(i, n) for (int i = n; i >= 1; -- i)
# define FOR(i, a, b) for (int i = a; i <= b; ++ i)
# define DWN(i, a, b) for (int i = b; i >= a; -- i)
# define RST(a) memset (a, 0, sizeof (a))
# define CLR(a, x) memset (a, x, sizeof (a))
# define CPY(a, b) memcpy (a, b, sizeof (a))
typedef long long ll;
typedef long double ld;
const int inf = 1 << 30;
const ll lnf = 1ll << 60;
template <class T0, class T1> bool RlxX (T0 &a, T1 b) {if (a < b) return a = b, true; return false;}
template <class T0, class T1> bool RlxN (T0 &a, T1 b) {if (a > b) return a = b, true; return false;}
int f[4][200][2];
int n, m, q0, sX, sY;
char s[4][200];
bool train (int x, int y) {return s[x][y] <= 'Z' && s[x][y] >= 'A';}
bool dfs (int x, int y, int z)
{
    if (y > n) return true;
    if (train (x, y)) return false;
    if (f[x][y][z] != -1) return f[x][y][z];
    if (z)
    {
        if (train (x, y + 1) || train (x, y + 2)) return f[x][y][z] = false;
        return f[x][y][z] = dfs (x, y + 2, 0);
    }
    else
    {
        if (train (x, y + 1)) return f[x][y][z] = false;
        if (dfs (x, y + 1, 1)) return f[x][y][z] = true;
        if (x != 1 && dfs (x - 1, y + 1, 1)) return f[x][y][z] = true;
        if (x != 3 && dfs (x + 1, y + 1, 1)) return f[x][y][z] = true;  
    }
    return f[x][y][z] = false;
}
int main ()
{
    for (scanf ("%d", &q0); q0; -- q0)
    {
        scanf ("%d%d", &n, &m);
        CLR (f, -1), RST (s);
        REP (i, 3) 
        {
            scanf ("%s", s[i] + 1);
            REP (j, n) if (s[i][j] == 's') sX = i, sY = j;
        }
        printf ("%s\n", dfs (sX, sY, 0) ? "YES" : "NO");
    }
    return 0;
}

CF585C Alice, Bob, Oranges and Apples

每次试图用向量 $A,B$ 表示出最终向量。
$A,B$ 改动的时候重新把最终向量正交分解。

# include <cstdio>
# include <cstring>
# include <cmath>
# include <algorithm>
# include <cassert>
# include <iostream>
using namespace std;
# define REP(i, n) for (int i = 1; i <= n; ++ i)
# define REP_0(i, n) for (int i = 0; i < n; ++ i)
# define REP_G(i, x) for (int i = pos[x]; i; i = g[i].frt)
# define REP_D(i, n) for (int i = n; i >= 1; -- i)
# define FOR(i, a, b) for (int i = a; i <= b; ++ i)
# define DWN(i, a, b) for (int i = b; i >= a; -- i)
# define RST(a) memset (a, 0, sizeof (a))
# define CLR(a, x) memset (a, x, sizeof (a))
# define CPY(a, b) memcpy (a, b, sizeof (a))
typedef long long ll;
typedef long double ld;
const int inf = 1 << 30;
const ll lnf = 1ll << 60;
char tmp[1001000];
string res;
ll a, b;
bool solve (ll a, ll b, char A, char B)
{
    if (!a && !b) return true;
    if (a == b) return false;
    if (a < b) return solve (b, a, B, A);
    sprintf (tmp, "%I64d%c", a / (b + 1), A);
    res.append (tmp);
    return solve (a % (b + 1), b, A, B);
}
int main ()
{
    scanf ("%I64d%I64d", &a, &b);
    if (solve (a - 1, b - 1, 'A', 'B')) cout << res << endl;
    else cout << "Impossible" << endl;
    return 0;
}

CF585D Lizard Era: Beginning

分段大暴力。

# include <cstdio>
# include <cstring>
# include <cmath>
# include <algorithm>
# include <cassert>
# include <iostream>
# include <map>
using namespace std;
# define REP(i, n) for (int i = 1; i <= n; ++ i)
# define REP_0(i, n) for (int i = 0; i < n; ++ i)
# define REP_G(i, x) for (int i = pos[x]; i; i = g[i].frt)
# define REP_D(i, n) for (int i = n; i >= 1; -- i)
# define FOR(i, a, b) for (int i = a; i <= b; ++ i)
# define DWN(i, a, b) for (int i = b; i >= a; -- i)
# define RST(a) memset (a, 0, sizeof (a))
# define CLR(a, x) memset (a, x, sizeof (a))
# define CPY(a, b) memcpy (a, b, sizeof (a))
typedef long long ll;
typedef long double ld;
const int inf = 1 << 30;
const ll lnf = 1ll << 60;
template <class T0, class T1> bool RlxX (T0 &a, T1 b) {if (a < b) return a = b, true; return false;}
template <class T0, class T1> bool RlxN (T0 &a, T1 b) {if (a > b) return a = b, true; return false;}
# define NR 50
typedef map <pair <int, int>, pair <int, int> >::iterator Mi;
int n0, n, dx[NR], dy[NR], dz[NR], rec[NR], ans, S0, S1;
map <pair <int, int>, pair <int, int> > vis;
void dfs0 (int i, int x, int y, int z, int mask)
{
    if (i > n0) 
    {
        Mi it = vis.find (make_pair (y, z));
        if (it == vis.end ()) vis.insert (make_pair (make_pair (y, z), make_pair (x, mask)));
        else it->second = max (it->second, make_pair (x, mask)); 
        return ;
    }
    dfs0 (i + 1, x, y + dy[i], z + dz[i], mask * 3);
    dfs0 (i + 1, x + dx[i], y - dx[i], z + dz[i] - dx[i], mask * 3 + 1);
    dfs0 (i + 1, x + dx[i], y + dy[i] - dx[i], z - dx[i], mask * 3 + 2);
}
void dfs1 (int i, int x, int y, int z, int mask)
{
    if (i > n) 
    {
        if (vis.find (make_pair (-y, -z)) == vis.end ()) return ;
        pair <int, int> t = vis[make_pair (-y, -z)];
        if (t.first + x > ans) ans = t.first + x, S0 = t.second, S1 = mask;
        return ;
    }
    dfs1 (i + 1, x, y + dy[i], z + dz[i], mask * 3);
    dfs1 (i + 1, x + dx[i], y - dx[i], z + dz[i] - dx[i], mask * 3 + 1);
    dfs1 (i + 1, x + dx[i], y + dy[i] - dx[i], z - dx[i], mask * 3 + 2);
}
char str[4][4] = {"MW", "LW", "LM"};
int main ()
{
    scanf ("%d", &n); n0 = n >> 1; ans = -inf;
    REP (i, n) scanf ("%d%d%d", &dx[i], &dy[i], &dz[i]);
    dfs0 (1, 0, 0, 0, 0), dfs1 (n0 + 1, 0, 0, 0, 0);
    if (ans != -inf)
    {
        REP_D (i, n0) rec[i] = S0 % 3, S0 /= 3;
        DWN (i, n0 + 1, n) rec[i] = S1 % 3, S1 /= 3;
        REP (i, n) puts (str[rec[i]]);
    }
    else puts ("Impossible");
    return 0;
}

10.13 火曜日

ASC02 A Non Absorbing DFA

坑了好久的题了……
早上看数据发现高精度输出错了2333

感觉自己使用coach mode的姿势不大对QAQ

把不需要删除字符的边连到从它出发走不需要删除的边遇到的第一条需要删除的边即可。

# include <cstdio>
# include <cstring>
# include <algorithm>
# include <iostream>
# include <vector>
# define REP(i, n) for (int i = 1; i <= n; i ++)
# define REP_0(i, n) for (int i = 0; i < n; i ++)
# define REP_D0(i, n) for (int i = n - 1; i >= 0; i --)
# define W 1000000000
using namespace std;
struct BigInteger
{
    vector <int> s;
    BigInteger () {s.clear ();}
    void operator += (BigInteger b)
    {
        REP_0 (i, b.s.size ())
        {
            if (i + 1 > s.size ()) s.push_back (b.s[i]);
            else s[i] = s[i] + b.s[i];
        }
        REP_0 (i, s.size ())
            if (s[i] >= W)
            {
                s[i] -= W;
                if (i + 2 > s.size ()) s.push_back (1);
                else s[i + 1] ++;
            }
    }
    void output ()
    {
        if (!s.size ()) {puts ("0"); return ;}
        char ts[20];
        REP_D0 (i, s.size ())
        {
            if (i + 1 == s.size ()) printf ("%d", s[i]);
            else
            {
                int tl = 0, tmp = s[i];
                REP_0 (i, 9) ts[i] = 0;
                while (tmp) ts[tl ++] = tmp % 10, tmp /= 10;
                REP_D0 (i, 9) printf ("%d", ts[i]);
            }
        }
        puts ("");
    }
};
int n, Z, S, K, g[1010][30], stk[1010], top;
bool h[1010][30], vis[1010][30], vT[1010];
BigInteger f[62][1010];
int main ()
{
    freopen ("dfa.in", "r", stdin);
    freopen ("dfa.out", "w", stdout);
    char rts[30]; int tt, lT;
    scanf ("%s", rts); Z = strlen (rts);
    scanf ("%d%d%d", &n, &S, &lT);
    REP (i, lT) scanf ("%d", &tt), vT[tt] = true;
    REP (i, n) REP (c, Z) scanf ("%d", &g[i][c]);
    REP (i, n) REP (c, Z) scanf ("%d", &h[i][c]);
    int abd = n + 1;
    REP (c, Z) g[n + 1][c] = n + 1;
    REP (i, n)
        REP (c, Z)
            if (h[i][c])
            {
                int vi;
                for (int u = i; 1; u = g[u][c])
                {
                    vis[stk[++ top] = u][c] = true;
                    if (!h[u][c]) {vi = g[u][c]; break;}
                    if (vis[g[u][c]][c]) {vi = abd; break;}
                }
                while (top) 
                {
                    g[stk[top]][c] = vi, h[stk[top]][c] = vis[stk[top]][c] = false; 
                    top --;
                }
            }
    n ++;
    scanf ("%d", &K);
    f[0][S].s.push_back (1);
    REP (k, K) REP (i, n) REP (c, Z) f[k][g[i][c]] += f[k - 1][i];
    BigInteger ans;
    REP (i, n) if (vT[i]) ans += f[K][i];
    ans.output ();
    return 0;
}

10.14 水曜日

PA2009 sza

…………简直了……
没有C++11的世界T_T（幸好自己用的一堆STL没T…………
写了好久好久好久T_T
考虑后缀树，唯一问题是匹配开头，匹配其他的可以用平衡树启发式合并。
考虑使用KMP。
考虑每个后缀树节点到其父亲节点的边上的每一个位置到根的路径组成的字符串，令我们当前考虑的边中的可行字符串是 $S[p\ldots l], S[p\ldots l+1],\ldots S[p\ldots r]$ ，其中 $p$ 是当前后缀树节点的笫一次出现位置。
那么该边的贡献为 $\sum_{i=l}^r [next_i\geq p - 1]$ 。
该条件的必要性显然，充分性的话，
因为若 $i-next_i+1<=p$ ，则显然 $p$ 不是该后缀节点的第一次出现位置，不可能。
所以写啊写就行了……
另外sort居然会自己和自己比大小T_T（我也不知道stable_sort会不会>_<

# include <cstdio>
# include <cstring>
# include <map>
# include <set>
# include <vector>
using namespace std;
# define REP(i, n) for (int i = 1; i <= n; ++ i)
# define REP_D(i, n) for (int i = n; i >= 1; -- i)
# define REP_G(i, x) for (int i = pos[x]; i; i = g[i].frt)
# define FOR(i, a, b) for (int i = a; i <= b; ++ i)
# define DWN(i, a, b) for (int i = b; i >= a; -- i)
# define RST(a) memset (a, 0, sizeof (a))
# define CLR(a, x) memset (a, x, sizeof (a))
typedef set <int>::iterator Si;
typedef map <int, int>::iterator Mi;
typedef long long ll;
const int inf = 1 << 30;
# define u t[x]
# define o t[y]
# define ulfc t[u.lc]
# define urtc t[u.rc]
# define NR 201000
# define SR 401000
struct Seg {int lc, rc, cnt;} t[5010000];
vector <int> e[SR], tp[NR];
struct Sam {int trans[26], par, l, p; bool ed; Sam () {CLR (trans, -1);}} sam[SR];
int next[NR], ro[NR];
int lst, ssz, tsz, n, finL, finE;
ll ans;
map <int, int> al[SR];
set <int> ap[SR];
char s[NR];
int segModi (int l, int r, int p, int y)
{
    int x = ++ tsz, mid = (l + r) >> 1; u = o; ++ u.cnt;
    if (l == r) return x;
    if (p <= mid) u.lc = segModi (l, mid, p, o.lc);
    else u.rc = segModi (mid + 1, r, p, o.rc);
    return x;
}
int segQry (int x, int l, int r, int ql, int qr)
{
    if (!x || l > r) return 0;
    if (ql <= l && r <= qr) return u.cnt;
    int mid = (l + r) >> 1, ret = 0;
    if (ql <= mid) ret += segQry (u.lc, l, mid, ql, qr);
    if (qr > mid) ret += segQry (u.rc, mid + 1, r, ql, qr);
    return ret;
}
int segMin (int x, int l, int r, int ml, int mr, int y)
{
    int mid = (l + r) >> 1;
    if (ml <= l && r <= mr)
    {
        if (u.cnt == o.cnt) return inf;
        if (l == r) return l;
        if (ulfc.cnt - t[o.lc].cnt) return segMin (u.lc, l, mid, ml, mr, o.lc);
        return segMin (u.rc, mid + 1, r, ml, mr, o.rc);
    }
    int tmp;
    if (ml <= mid && (tmp = segMin (u.lc, l, mid, ml, mr, o.lc)) != inf) return tmp;
    if (mr > mid && (tmp = segMin (u.rc, mid + 1, r, ml, mr, o.rc)) != inf) return tmp;
    return inf;
}
# undef u
# undef o
# define u sam[x]
# define o sam[y]
# define w sam[z]
# define v sam[x].trans[c]
# define vn sam[v]
void extend (int c, int ti)
{
    int x = lst, z = ++ ssz; lst = z, w.l = u.l + 1, w.p = ti, w.ed = true;
    for (; x != -1 && v == -1; x = u.par) v = z;
    if (x == -1) w.par = 1;
    else if (u.l + 1 == vn.l) w.par = v;
    else
    {
        int y = ++ ssz, tv = v;
        o = vn, o.l = u.l + 1, o.ed = false, vn.par = w.par = y;
        for (; x != -1 && v == tv; x = u.par) v = y;
    }
}
bool cmpS (int x, int y) 
{
    int cX = s[u.p + sam[u.par].l], cY = s[o.p + sam[o.par].l];
    return cX < cY;
}
# undef v
void calcNext ()
{
    int j = 0;
    FOR (i, 2, n)
    {
        while (j > 0 && s[j + 1] != s[i]) j = next[j];
        if (s[j + 1] == s[i]) ++ j;
        tp[next[i] = j].push_back (i);
    }
    REP (i, n)
    {
        ro[i] = ro[i - 1];
        for (vector <int>::iterator it = tp[i - 1].begin (); it != tp[i - 1].end (); ++ it)
            ro[i] = segModi (1, n, *it, ro[i]);
    }
}
void merge (int x, int y)
{
    if (ap[x].size () < ap[y].size ()) ap[x].swap (ap[y]), al[x].swap (al[y]);
    for (Si it = ap[y].begin (); it != ap[y].end (); ++ it)
    {
        if (ap[x].find (*it) != ap[x].end ()) continue;
        Si p = ap[x].insert (*it).first, prev = p, succ = p;
        ++ succ;
        if (succ == ap[x].end ())
        {
            ++ al[x][*it - *(-- prev)];
            continue;
        }
        ++ al[x][*succ - *it];
        if (p != ap[x].begin ())
        {
            -- prev;
            Mi t = al[x].find (*succ - *prev);
            if (!-- t->second) al[x].erase (t);
            ++ al[x][*it - *prev];
        }
    }
    al[y].clear (), ap[y].clear ();
}
# define v *it
int maxL, end;
Mi __it;
void dfsSuf (int x, int el)
{
    ap[x].insert (el);
    if (u.ed) ap[x].insert (n - u.l + 1), ++ al[x][el - (n - u.l + 1)], el = n - u.l + 1;
    for (vector <int>::iterator it = e[x].begin (); it != e[x].end (); ++ it)
        dfsSuf (v, el), merge (x, v), u.p = min (u.p, vn.p);
    __it = al[x].end (); -- __it;
    maxL = __it->first, end = *ap[x].begin () - 1;
    if (maxL > u.l) return ;
    if (!end)
    {
        if (maxL < finL) finL = max (maxL, sam[u.par].l + 1), finE = u.p;
        ans += u.l - max (maxL, sam[u.par].l + 1) + 1;
        return ;
    }
    else
    {
        int tl = u.p + max (max (end, maxL), sam[u.par].l + 1) - 1, tr = u.p + u.l - 1, tmp = segMin (ro[n], 1, n, tl, tr, ro[u.p - 1]);    
        ans += segQry (ro[n], 1, n, tl, tr) - segQry (ro[u.p - 1], 1, n, tl, tr);
        if (tmp - u.p + 1 < finL) finL = tmp - u.p + 1, finE = u.p;
    }
}
int main ()
{
    scanf ("%s", s + 1);
    sam[lst = ssz = 1].par = -1, finL = inf;
    n = strlen (s + 1);
    REP_D (i, n) extend (s[i] - 'a', i);
    calcNext ();
    DWN (x, 2, ssz) e[sam[x].par].push_back (x);
    REP (i, ssz) if (e[i].size () > 1) stable_sort (e[i].begin (), e[i].end (), cmpS);
    dfsSuf (1, n + 1);
    printf ("%lld\n", ans);
    REP (i, finL) putchar (s[finE + i - 1]); putchar ('\n');
    return 0;
}

CC AUTHEN

…………啊啊啊自己好蠢T_T

考虑 $F(i,j)$ 为长度为 $i$ 有 $j$ 个多余字符的方案数。
为了不重复算算到前一个相同字符就停。

# include <cstdio>
# include <cstring>
# include <algorithm>
using namespace std;
# define REP(i, n) for (int i = 1; i <= n; ++ i)
# define REP_0N(i, n) for (int i = 0; i <= n; ++ i)
# define RST(a) memset (a, 0, sizeof (a))
# define P 1009419529
# define NR 11000
int n, K, q0;
char s[NR];
int f[NR][120], sum[NR][120];
int main ()
{
    for (scanf ("%d", &q0); q0; -- q0)
    {
        scanf ("%d%d%s", &n, &K, s + 1);
        if (!K) {puts ("0"); continue;}
        RST (f), RST (sum);
        f[0][0] = sum[0][0] = 1;
        REP (i, n + K)
        {
            int k = 1;
            for (; i - k > 0 && s[i - k] != s[i]; ++ k) ;
            f[i][0] = sum[i][0] = 1;
            int jr = min (i - 1, K);
            REP (j, jr)
            {
                int tl = min (j + 1, k);    
                f[i][j] = sum[i - 1][j];
                if (j - tl >= 0) f[i][j] -= sum[i - tl - 1][j - tl];
                if (f[i][j] >= P) f[i][j] -= P;
                if (f[i][j] < 0) f[i][j] += P;
            }
            REP (j, K)
            {
                sum[i][j] = f[i][j] + sum[i - 1][j - 1];
                if (sum[i][j] >= P) sum[i][j] -= P;
            }
        }
        int ans = 0;
        REP_0N (i, K)
        {
            ans += f[n + K - i][K - i];
            if (ans >= P) ans -= P;
        }
        printf ("%d\n", (ans + P - 1) % P);
    }
    return 0;
}

CC SKIRES

自己状态好差T_T
考虑把一个点高度可能的取值，拆点建图即可。

# include <cstdio>
# include <cstring>
# include <algorithm>
using namespace std;
# define REP(i, n) for (int i = 1; i <= n; ++ i)
# define REP_G(i, x) for (int i = pos[x]; i; i = g[i].frt)
# define RST(a) memset (a, 0, sizeof (a))
# define CLR(a, x) memset (a, x, sizeof (a))
# define v g[i].y
# define fl g[i].f
# define vfl g[i ^ 1].f
# define NR 60
# define PR 15000
# define ER 200000
template <class T> T abs (T a) {return a >= 0 ? a : -a;}
int dx[] = {0, 0, 0, -1, 1};
int dy[] = {0, -1, 1, 0, 0};
const int inf = 1 << 30;
struct Edge {int y, frt, f; void set (int yr, int fr, int ff) {y = yr, frt = fr, f = ff;}} g[ER];
struct Arr {int x, y; Arr () {x = y = 0;} Arr (int _x, int _y):x(_x), y(_y) {}} li[10];
int q0, n, m, Sx, Sy, Tx, Ty, h[NR][NR], pos[PR], gsz, den[NR][NR][5], S, T, hl[NR][NR], dsz;
int q[PR], lv[PR];
inline bool cmpH (Arr a, Arr b) {return h[a.x][a.y] > h[b.x][b.y];}
bool denote ()
{
    int h, t, x;
    CLR (lv, -1), lv[q[h = t = 1] = S] = 0;
    while (h <= t) {x = q[h ++]; REP_G (i, x) if (fl && lv[v] < 0) lv[q[++ t] = v] = lv[x] + 1;}
    return lv[T] > 0;
}
int augment (int x, int f)
{
    if (x == T) return f;
    int s = 0, ff;
    REP_G (i, x) if (fl && f && lv[v] == lv[x] + 1 && (ff = augment (v, min (f, fl))))
        fl -= ff, vfl += ff, f -= ff, s += ff;
    if (!s) lv[x] = -1;
    return s;
}
int maxFlow () {int s = 0; for (; denote (); s += augment (S, inf)) ; return s;}
void AE (int x, int y, int z) 
{
    g[++ gsz].set (y, pos[x], z), pos[x] = gsz;
    g[++ gsz].set (x, pos[y], 0), pos[y] = gsz;
}
int main ()
{
    for (scanf ("%d", &q0); q0; -- q0)
    {
        scanf ("%d%d%d%d%d%d", &n, &m, &Sx, &Sy, &Tx, &Ty);
        REP (i, n) REP (j, m) {scanf ("%d", &h[i][j]); hl[i][j] = 0;}
        RST (den);
        if (h[Sx][Sy] < h[Tx][Ty]) {puts ("0"); continue;}
        if (abs (Sx - Tx) + abs (Sy - Ty) == 1) {puts ("-1"); continue;}
        dsz = 0, gsz = 1; RST (pos);
        REP (i, n) REP (j, m) den[i][j][0] = ++ dsz;
        REP (i, n)
            REP (j, m)
            {
                if (i == Tx && j == Ty)
                {
                    REP (d, 4)
                    {
                        int _i = i + dx[d], _j = j + dy[d];
                        if (1 <= _i && _i <= n && 1 <= _j && _j <= m && h[_i][_j] >= h[i][j])
                            AE (den[_i][_j][0], den[i][j][0], inf);
                    }
                    continue;
                }
                REP (d, 4)
                {
                    int _i = i + dx[d], _j = j + dy[d];
                    if (1 <= _i && _i <= n && 1 <= _j && _j <= m && h[_i][_j] >= h[i][j])
                        li[++ hl[i][j]] = Arr (_i, _j);
                }
                if (!hl[i][j]) continue;
                sort (li + 1, li + hl[i][j] + 1, cmpH);
                REP (k, hl[i][j])
                {
                    den[i][j][k] = ++ dsz;
                    AE (den[i][j][k], den[i][j][k - 1], h[li[k].x][li[k].y] + 1 - h[i][j]);
                    AE (den[li[k].x][li[k].y][0], den[i][j][k], inf);
                }
            }
        S = den[Sx][Sy][0], T = den[Tx][Ty][0];
        printf ("%d\n", maxFlow ());
    }
    return 0;
}

10.15 木曜日

CC E5

啊啊啊感觉自己好弱啊T_T
首先重要结论是若最终序列中有长度不小于3的下降子序列则无解。
原因是注意到 $p_i-i=(p_i-1)-(i-1)$ ，即该式子算的是假若 $p_i-1\geq i-1$ ，则对于 $j<i$ 有 $p_j<p_i$ ，否则对于 $p_j<p_i$ 有 $j<i$ 这样的排列 $p$ 。
则可以发现可以把数分成两类，存在 $i<j, p_i>p_j$ 的 $i$ 和不存在的 $i$ ，两类数各自形成一个上升序列。
我们填第二类数，把第一类数的空预留出来。
我们先忽略要求前 $M$ 个数的限制。
令 $F(i,j,k)$ 为填了 $i$ 个数预留 $j$ 个空， $\sum_{t=1}^imax(0,p_t-t)-逆序对数=k$ 的排列数量。

则转移显然有三种，经过计算可得
$F(i,j,k)=\sum_{t=-1}^{n}F(i-1,j-t,k+t)$

考虑前 $M$ 个数的话直接按照这么填就好了。
$k$ 的那一维可以省略。
大概还可以用前缀和优化转移吧，懒得写了。

# include <cstdio>
# include <cstring>
# include <algorithm>
# define REP(i, n) for (int i = 1; i <= n; ++ i)
# define REP_0N(i, n) for (int i = 0; i <= n; ++ i)
# define FOR(i, a, b) for (int i = a; i <= b; ++ i)
# define CLR(a, x) memset (a, x, sizeof (a))
# define NR 50
using namespace std;
typedef long long ll;
int n, m, q0, a[NR], p[NR], M;
ll f[NR][NR];
ll dfs (int i, int j)
{
    if (j < 0 || j > n) return 0;
    if (i > n) return !j;
    if (f[i][j] != -1) return f[i][j];
    if (p[i] == -1)
    {
        if (i + j <= m)
        {
            f[i][j] = 0;
            FOR (t, m - (i + j - 1), n) f[i][j] += dfs (i + 1, j + t);
        }
        else
        {
            f[i][j] = dfs (i + 1, j);
            REP (t, n) f[i][j] += dfs (i + 1, j + t);
            if (i > M) f[i][j] += dfs (i + 1, j - 1);
        }
    }
    else
    {
        if (p[i] == i + j) f[i][j] = dfs (i + 1, j);
        else if (p[i] < i + j) f[i][j] = dfs (i + 1, j - 1);
        else f[i][j] = dfs (i + 1, j + p[i] - (i + j));
    }
    return f[i][j];
}
int main ()
{
    for (scanf ("%d", &q0); q0; -- q0)
    {
        scanf ("%d%d", &n, &m), M = 0;
        int lst = 0; CLR (f, -1);
        int ci = 1; bool valid = true;
        REP (i, n) p[i] = -1;
        REP (i, m) 
        {
            scanf ("%d", &a[i]), p[a[i]] = i;
            if (a[i] == ci) for (++ ci; p[ci] != -1 && ci <= n; ++ ci) ;
            else if (a[i] < lst) valid = false;
            else lst = a[i];
            M = max (a[i], M);
        }
        if (!valid) {puts ("0"); continue;}
        printf ("%lld\n", dfs (1, 0));
    }
    return 0;
}

10.16 金曜日

啊啊啊颓课件QAQ

10.17 土曜日

啊啊啊学妹好不容易来一次嘛>_<

下午的CF毫无输出，感觉药丸啊……

10.18 日曜日

讲课日……QAQ
被hzt1爷虐飞（意料之中吧。
又感受到了许多完爆标解的做法……
感觉hzt1爷早晚国家队。

10.19 月曜日

CEOI2015 indcyc

太吓人了……
标解400lines什么鬼啊……
题解休息的时候再写好了……

# include <cstdio>
# include <cstring>
# include <algorithm>
# include <vector>
using namespace std;
# define REP(i, n) for (int i = 1; i <= n; ++ i)
# define REP_0(i, n) for (int i = 0; i < n; ++ i)
# define FOR(i, a, b) for (int i = a; i <= b; ++ i)
# define REP_G(i, x) for (int i = p[x].pos; i; i = g[i].frt)
# define NR 1010
const int inf = 1 << 30;
struct Edge {int y, frt; Edge () {y = 0, frt = -1;} Edge (int _y, int _frt): y(_y), frt(_frt) {}};
struct Poi
{
    int pos, id, org; bool c;
    Poi () {pos = id = org = c = 0;}
    Poi (int _pos, int _id, int _org, bool _c): pos(_pos), id(_id), org(_org), c(_c) {}
};
bool e[NR][NR];
int n, m, lo, ln, al, aX, aY, len;
int op[NR], np[NR], dt[NR], pre[NR], ans[NR], match[NR], q[NR], li[NR];
void bfs (int f)
{
    int head = 1, tail = 1, u; 
    REP_0 (i, n) dt[i] = inf;
    q[1] = aX, dt[aX] = 1, pre[aX] = -1, dt[f] = -1;
    REP_0 (v, n) if (e[f][v] && v != aX && v != aY) dt[v] = -1;
    while (head <= tail)
    {
        u = q[head ++];
        REP_0 (v, n) if (e[u][v] && dt[u] + 1 < dt[v]) dt[q[++ tail] = v] = dt[u] + 1, pre[v] = u;
    }
    for (u = aY; u != -1; u = pre[u]) ans[++ al] = u;
}
# define v g[i].y
class Solver
{
public:
    vector <Edge> g;
    vector <Poi> p;
    int gsz, csz, n;
    void AE (int x, int y) {g.push_back (Edge (y, p[x].pos)), p[x].pos = ++ gsz;}
    Solver () {gsz = csz = 0, g.clear (), p.clear (), g.push_back (Edge (0, 0));}
    Solver (Solver* b, int cid)
    {
        gsz = csz = n = 0, g.clear (), p.clear (), g.push_back (Edge (0, 0));
        REP_0 (i, b->n) if (abs (b->p[i].id) == cid) p.push_back (Poi (0, 0, b->p[i].org, b->p[i].id < 0)), match[i] = n ++;
        REP_0 (x, b->n) 
            if (abs (b->p[x].id) == cid) 
                for (int i = b->p[x].pos; i; i = b->g[i].frt)
                    if (abs (b->p[b->g[i].y].id) == cid)
                        AE (match[x], match[b->g[i].y]);
    }
    bool solve ()
    {
        if (n < 4) return false;
        int u = 0;
        REP_0 (i, n) if (p[i].c) {u = i; break;}
        p[u].id = -inf;
        REP_G (i, u) p[v].id = -(n + 3);
        REP_0 (i, n) 
            if (!p[i].id) 
            {
                len = 0, color (i, ++ csz);
                if (len > 1 && clique (csz)) return bfs (p[u].org), ans[++ al] = p[u].org, true;
                if ((new Solver (this, csz))->solve ()) return true;
            }
        REP_0 (i, n) p[i].id = p[i].id < 0 && p[i].id != -inf;
        return (new Solver (this, 1))->solve ();
    }
private:
    inline bool clique (int c)
    {
        lo = ln = 0;
        REP (i, len) if (p[li[i]].id == -c) p[li[i]].c ? op[++ lo] = p[li[i]].org : np[++ ln] = p[li[i]].org;
        REP (i, lo) REP (j, ln) if (!e[op[i]][np[j]]) return aX = op[i], aY = np[j], true;
        REP (i, ln) FOR (j, i + 1, ln) if (!e[np[i]][np[j]]) return aX = np[i], aY = np[j], true;
        return false;
    }
    void color (int x, int c)
    {
        p[x].id = c;
        REP_G (i, x)
        {
            if (!p[v].id) color (v, c);
            else if (p[v].id < 0 && p[v].id != -inf && p[v].id != -c) p[li[++ len] = v].id = -c;
        }
    }
} root;
int main ()
{
    scanf ("%d%d", &n, &m); int t1, t2;
    REP_0 (i, n) root.p.push_back (Poi (0, 0, i, 0)), ++ root.n;
    REP (i, m)
    {
        scanf ("%d%d", &t1, &t2), -- t1, -- t2; 
        e[t1][t2] = e[t2][t1] = true, root.AE (t1, t2), root.AE (t2, t1);
    }
    if (root.solve ()) {REP (i, al) printf ("%d ", ans[i] + 1); puts ("");}
    else puts ("no");
    return 0;
}

AMPPZ2014 ben

10.20 火曜日

AMPPZ2014 cen

AMMPPZ2014 glo

10.21 水曜日

把前两天做的题当成NOIP摸你赛出了。
说难是什么鬼啊……

AMPPZ2014 fil

AMPPZ2014 ins

10.22 木曜日

BOI2014 sequence

QAQ自己好笨
考虑最后一位，令 $L_i$ 为当前第 $i$ 个数需要包含的数字的集合。
去掉最后一位后序列是形如 $X,X,\ldots X+1,X+1\ldots X+2\ldots$
缩起来递归下去。

# include <cstdio>
# include <cstring>
# include <cstdlib>
# include <cassert>
# include <iostream>
# include <algorithm>
# define REP(i, n) for (int i = 1; i <= n; ++ i)
# define REP_0(i, n) for (int i = 0; i < n; ++ i)
# define NR 101000
using namespace std;
typedef long long ll;
const ll lnf = 1ll << 61;
int a[NR];
# define e(s, i) ((s) >> (i) & 1)
ll c1 (int s)
{
    if (s == 1) return 10;
    ll f = 0; bool ze = e (s, 0);
    REP (i, 9) if (e (s, i)) {f = f * 10 + i; if (ze) f *= 10, ze = false;}
    return f;
}
ll c2 (int s0, int s1, bool ty)
{
    int _s0 = s0, _s1 = s1; ll f = lnf;
    if (s0 == 1 && s1 == 1) return 100;
    if (s0 == 1 && !s1) return 10;
    if (!s0 && s1 == 0) return 9;
    REP_0 (t, 9)
    {
        if (e (s0, t)) s0 ^= 1 << t;
        if (e (s1, t + 1)) s1 ^= 1 << (t + 1);
        f = min (f, c1 (s0 | s1) * 10 + t); 
        s0 = _s0, s1 = _s1;
    } 
    if (ty) 
    {
        if (e (s0, 9)) s0 ^= 1 << 9;
        if (e (s1, 0)) s1 ^= 1;
        f = min (f, c2 (s0, s1, false) * 10 + 9);
    }
    return f;
}
struct Solver
{
    int *d, n;
    Solver () {n = 0, d = NULL;}
    Solver (int _n)
    {
        n = _n;
        d = (int*) malloc (n * sizeof (int));
        REP_0 (i, n) d[i] = 0;
    }
# define w(t, i) (d[t] >> (i) & 1)
    ll solve ()
    {
        if (n == 1) return c1 (d[0]);
        if (n == 2) return c2 (d[0], d[1], true);
        bool succ = true;
        REP_0 (i, n) if (d[i]) succ = false;
        if (succ) return 0;
        ll res = lnf;
        REP_0 (f, 10)
        {
            int cur = f, sz = 0;
            Solver *next = new Solver ((n + f + 9) / 10);
            REP_0 (i, n)
            {
                if (w (i, cur)) next->d[sz] |= d[i] ^ 1 << cur;
                else next->d[sz] |= d[i]; 
                ++ cur;
                if (cur == 10 && i + 1 != n) cur = 0, ++ sz;
            }
            res = min (res, next->solve () * 10 + f); delete next;
        }
        return res;
    }
};
int main ()
{
    int n, t1; scanf ("%d", &n);
    Solver *sol = new Solver (n);
    REP_0 (i, n) scanf ("%d", &t1), sol->d[i] |= 1 << t1;
    printf ("%lld\n", sol->solve ());
    return 0;
}

10.23 金曜日

AMPPZ2014 hit

10.24 土曜日

PA2011 bwp

PA2011 kan

10.25 日曜日

这场CF好逗啊……
可惜还是打错一个减号没A掉D T_T
不过想来自己只是想和BF打CF呢。结果什么的嘛。

PA2011 aut

CF590A Median Smoothing

直接模拟。

# include <cstdio>
# include <cstring>
# include <algorithm>
using namespace std;
# define REP(i, n) for (int i = 1; i <= n; ++ i)
# define REP_0(i, n) for (int i = 0; i < n; ++ i)
# define REP_D(i, n) for (int i = n; i >= 1; -- i)
# define FOR(i, a, b) for (int i = a; i <= b; ++ i)
# define DWN(i, a, b) for (int i = b; i >= a; -- i)
# define RST(a) memset (a, 0, sizeof (a))
# define CLR(a, x) memset (a, x, sizeof (a))
# define NR 501000
# define w0 first
# define w1 second
int n, a[NR], len, ans;
pair <int, int> li[NR];
int main ()
{
    scanf ("%d", &n);
    REP (i, n) scanf ("%d", &a[i]);
    a[0] = a[1], a[n + 1] = a[n];
    int last = a[1], ti = 2;
    li[++ len] = make_pair (1, 1);
    FOR (i, 2, n + 1)
    {
        if (a[i] == last) 
        {
            ++ ti;
            if (li[len].w1 != i - 1 && ti >= 2)
                li[++ len] = make_pair (i - ti + 1, i);
            else if (ti > 2) li[len].w1 ++;
        }
        else ti = 1, last = a[i];
    }
    REP (i, len - 1)
    {
        if (a[li[i].w0] == a[li[i + 1].w0])
        {
            FOR (j, li[i].w1 + 1, li[i + 1].w0 - 1) a[j] = a[li[i].w0];
            ans = max (ans, (li[i + 1].w0 - li[i].w1) >> 1);
        }
        else
        {
            int t = (li[i + 1].w0 - li[i].w1 - 1) >> 1;
            FOR (j, li[i].w1 + 1, li[i + 1].w0 - 1)
            {
                if (j - li[i].w1 > t) a[j] = a[li[i + 1].w0];
                else a[j] = a[li[i].w0];
            }
            ans = max (ans, t);
        }
    }
    printf ("%d\n", ans);
    REP (i, n) printf ("%d ", a[i]); puts ("");
    return 0;
}

CF590C Three States

BFS一遍。

# include <cstdio>
# include <cstring>
# include <algorithm>
using namespace std;
# define REP(i, n) for (int i = 1; i <= n; ++ i)
# define REP_0(i, n) for (int i = 0; i < n; ++ i)
# define REP_D(i, n) for (int i = n; i >= 1; -- i)
# define FOR(i, a, b) for (int i = a; i <= b; ++ i)
# define DWN(i, a, b) for (int i = b; i >= a; -- i)
# define RST(a) memset (a, 0, sizeof (a))
# define CLR(a, x) memset (a, x, sizeof (a))
const int inf = 1 << 28;
# define NR 1010
# define SR 1010000
struct pii {int x, y; pii () {x = y = 0;} pii (int _x, int _y): x(_x), y(_y) {}} q[SR];
char s[NR][NR];
int dc[NR][NR], dt[4][NR][NR], n, m;
int dx[] = {0, 0, -1, 1};
int dy[] = {-1, 1, 0, 0};
bool valid (int x, int y) {return x >= 1 && x <= n && y >= 1 && y <= m && s[x][y] != '#';}
int main ()
{
    scanf ("%d%d", &n, &m); int ans;
    REP (i, n) scanf ("%s", s[i] + 1);
    REP (i, 3) REP (j, 3) if (i != j) dc[i][j] = inf;
    REP (id, 3)
    {
        int head = 1, tail = 0;
        REP (i, n) REP (j, m) if (s[i][j] == '0' + id) q[++ tail] = pii (i, j); else dt[id][i][j] = inf;
        while (head <= tail)
        {
            pii u = q[head ++];
            if (s[u.x][u.y] >= '0' && s[u.x][u.y] <= '9') 
            {
                int td = s[u.x][u.y] - '0';
                dc[id][td] = min (dc[id][td], dt[id][u.x][u.y]);
            }
            REP_0 (d, 4)
            {
                int _x = u.x + dx[d], _y = u.y + dy[d];
                if (valid (_x, _y) && dt[id][_x][_y] == inf) q[++ tail] = pii (_x, _y), dt[id][_x][_y] = dt[id][u.x][u.y] + 1;
            }
        }
    }
    ans = min (dc[1][2] + dc[1][3], min (dc[2][1] + dc[2][3], dc[3][1] + dc[3][2])) - 2;
    REP (i, n) REP (j, m) ans = min (ans, dt[1][i][j] + dt[2][i][j] + dt[3][i][j] - 2);
    printf ("%d\n", ans > n * m ? -1 : ans);
    return 0;
}

CF590D Top Secret Task

显然是选前K个中的某些数和后面的某些数交换。
确定了交换哪些数以后交换策略是每次交换最里面的一对。
$F(i,j,k)$ 为前K个中选到第 $i$ 个，后面的选到第 $j$ 个剩余交换次数为 $k$ 的答案。

# include <cstdio>
# include <cstring>
# include <algorithm>
using namespace std;
# define REP(i, n) for (int i = 1; i <= n; ++ i)
# define REP_0(i, n) for (int i = 0; i < n; ++ i)
# define REP_D(i, n) for (int i = n; i >= 1; -- i)
# define FOR(i, a, b) for (int i = a; i <= b; ++ i)
# define DWN(i, a, b) for (int i = b; i >= a; -- i)
# define RST(a) memset (a, 0, sizeof (a))
# define CLR(a, x) memset (a, x, sizeof (a))
int f[2][180][25000], n, K, T, a[200];
const int inf = 1 << 30;
inline void RlxN (int &x, int y) {if (x > y) x = y;}
int main ()
{
    scanf ("%d%d%d", &n, &K, &T);
    REP (i, n) scanf ("%d", &a[i]);
    if (T >= n * n / 2)
    {
        sort (a + 1, a + n + 1);
        int sum = 0;
        REP (i, K) sum += a[i];
        printf ("%d\n", sum);
        return 0;
    }
    int ans = inf;
    CLR (f[0], 60);
    FOR (j, K, n) f[0][j][T] = 0;
    REP (i, K)
    {
        bool d = i % 2; CLR (f[d], 60);
        FOR (j, K, n)
        {
            REP_0 (k, T + 1)
            {
                RlxN (f[d][j][k], f[!d][j][k] + a[i]);
                if (k < T) RlxN (f[d][j][k], f[d][j][k + 1]);
                if (j > K) RlxN (f[d][j][k], f[d][j - 1][k]);
                if (j != K && k + j - i <= T) RlxN (f[d][j][k], f[!d][j - 1][k + j - i] + a[j]);
                if (i == K) RlxN (ans, f[d][j][k]);
            }
        }
    }
    printf ("%d\n", ans);
    return 0;
}

10.26 水曜日

最近越来越喜欢爆OJ了T_T
完全不在状态要拯救一下才行呢……

PA2011 cia

10.17 火曜日

USACO JAN09 Safe Travel

……有并查集做法。挺显然的也。
写的是带标记可并堆，记录子树中的点连出去的边到达的点。

# include <cstdio>
# include <algorithm>
# include <vector>
# include <iostream>
# include <queue>
using namespace std;
# define REP(i, n) for (int i = 1; i <= n; ++ i)
# define REP_G(i, x) for (int i = pos[x]; i; i = g[i].frt)
# define FOR(i, a, b) for (int i = a; i <= b; ++ i)
# define NR 101000
# define ER 401000
const int inf = 1 << 30;
typedef pair <int, int> pii;
struct Heap {int ch[2], tag, w, id; inline void add (int d) {w += d, tag += d;}} t[ER];
struct Edge {int y, frt, w; void set (int yr, int fr, int wr) {y = yr, frt = fr, w = wr;}} g[ER];
int n, m, gsz, dsz, tsz, pos[NR], dt[NR], ro[NR], pre[NR], bg[NR], ed[NR], ans[NR], pw[NR];
bool vis[NR];
vector <pii> e[NR];
priority_queue <pii> Q;
# define u t[x]
# define lc ch[0]
# define rc ch[1]
# define v g[i].y
inline void AE (int x, int y, int z) {g[++ gsz].set (y, pos[x], z), pos[x] = gsz;}
inline void PD (int x) {if (!u.tag) return ; t[u.lc].add (u.tag), t[u.rc].add (u.tag), u.tag = 0;}
inline int merge (int x, int y)
{
    if (!x || !y) return x + y;
    if (u.w > t[y].w) swap (x, y);
    bool z = rand () & 1; return PD (x), u.ch[z] = merge (u.ch[z], y), x;
}
void dijkstra ()
{
    Q.push (pii (0, 1));
    FOR (i, 2, n) dt[i] = inf;
    while (!Q.empty ())
    {
        int x = Q.top ().second; Q.pop ();
        if (vis[x]) continue; vis[x] = true;
        REP_G (i, x)
            if (dt[v] > dt[x] + g[i].w)
            {
                pre[v] = x, pw[v] = g[i].w;
                Q.push (pii (-(dt[v] = dt[x] + g[i].w), v));
            }
    }
}
inline bool in (int y, int x) {return bg[y] && bg[x] <= bg[y] && bg[y] <= ed[x];}
void dfs (int x)
{
    bg[x] = ++ dsz;
    REP_G (i, x) dfs (v), t[ro[v]].add (g[i].w), ro[x] = merge (ro[x], ro[v]);
    ed[x] = dsz;
    for (vector <pii>::iterator it = e[x].begin (); it != e[x].end (); ++ it)
        if (!in (it->first, x) && it->first != pre[x]) 
            t[++ tsz].w = it->second + dt[it->first], t[tsz].id = it->first, ro[x] = merge (ro[x], tsz);
    while (ro[x] && in (t[ro[x]].id, x)) PD (ro[x]), ro[x] = merge (t[ro[x]].lc, t[ro[x]].rc);
    ans[x] = ro[x] ? t[ro[x]].w : -1;
}
int main ()
{
    srand (1214), scanf ("%d%d", &n, &m); int t1, t2, t3;
    REP (i, m) scanf ("%d%d%d", &t1, &t2, &t3), AE (t1, t2, t3), AE (t2, t1, t3), e[t1].push_back (pii (t2, t3)), e[t2].push_back (pii (t1, t3));
    dijkstra (), gsz = 0; REP (i, n) pos[i] = 0;
    FOR (i, 2, n) {if (dt[i] == inf) ans[i] = -1; else AE (pre[i], i, pw[i]);}
    dfs (1);
    FOR (i, 2, n) printf ("%d\n", ans[i]);
    return 0;
}

PA2011 wyb

SRM533 L3 Pikachu

挺显然的DP吧……
一个类似哈夫曼树的结构，按照到根的长度分层考虑。
考虑 $F(cur,l0,l1,l2)$ 为还剩后 $cur$ 个数要填，最后三层的可用节点数分别是 $l0,l1,l2$ 的答案。
暴力枚举选多少个即可。

# include <cstdio>
# include <algorithm>
# include <vector>
using namespace std;
typedef pair <int, int> pii;
# define REP(i, n) for (int i = 1; i <= n; ++ i)
# define FOR(i, a, b) for (int i = a; i <= b; ++ i)
# define NR 33
# define TR 210
# define w0 first
# define w1 second
# define P 1000000009
const int inf = 1 << 30;
class Pikachu
{
private:
    int sum[NR], bi[TR][TR], fac[TR], pre[NR], suc[NR], n;
    pii f[NR][NR][NR][NR];
    inline void relax (pii &x, pii y)
    {
        if (y.w0 < x.w0) x.w0 = y.w0, x.w1 = y.w1;
        else if (y.w0 == x.w0) {x.w1 += y.w1; if (x.w1 >= P) x.w1 -= P;}
    }
    pii dfs (int cur, int l0, int l1, int l2)
    {
        int l3 = l0 + 2 * l1;
        if (l3 >= cur) return pii (sum[cur], 1ll * bi[l3][cur] * fac[cur] % P);
        pii &w = f[cur][l0][l1][l2];
        if (w.w0) return w;
        w.w0 = inf;
        pii z = dfs (cur, l1, l2, l3);
        z.w0 += sum[cur], w = z;
        REP (i, l3)
        {
            int p = cur - i + 1;
            pii t = dfs (cur - i, l1, l2, l3 - i);
            t.w0 += sum[cur], t.w1 = 1ll * t.w1 * bi[l3][i] % P * bi[min (suc[p], cur) - pre[p] + 1][min (suc[p], cur) - p + 1] % P * fac[i] % P;
            relax (w, t);
        }
        return w;
    }
public:
    vector <int> bestEncoding (vector <int> a)
    {
        n = a.size (), sort (a.begin (), a.end ());
        bi[0][0] = fac[0] = 1; a.push_back (-1);
        int N = 4 * n, last = 1;
        REP (i, N)
        {
            bi[i][0] = 1, fac[i] = 1ll * fac[i - 1] * i % P;
            REP (j, i)
            {
                bi[i][j] = bi[i - 1][j] + bi[i - 1][j - 1];
                if (bi[i][j] >= P) bi[i][j] -= P;
            }
        }
        REP (i, n) 
        {
            sum[i] = sum[i - 1] + a[i - 1], pre[i] = last;
            if (a[i - 1] != a[i]) {FOR (j, last, i) suc[j] = i; last = i + 1;}
        }
        pii res = dfs (n, 0, 0, 1);
        return {res.w0, res.w1};
    }
};