2015.9月作战

OI

---

说是9月作战，其实也只有18后的不到两周而已……
然而状态仍然是起起落落的呢……
27题收尾，希望下一个月状态可以好一点吧……

目录

[0]TCO13 Round 1B 1000 EllysReversals
[1-]TCO13 Round 1A 1000 DirectionBoard
[0+]hdu 5451 Best Solver
[0-]hdu 5456 Matches Puzzle Game
[0+]hdu 5458 Stability
[0-]hdu 5459 Jesus Is Here
[0]ACM-ICPC 2015 Beijing Online F Couple Trees
[0++]ASC02 F Roads
[1+]TCO13 Round 2A 1000 ThePowers
[2-]TCO12 Wildcard 1000 StringSequence
[0-]TCO13 Round 2C 1000 WellTimedSearch
[0+]ASC02 H Tickets
[1]TCO 2013 Round 2B LitPanels
[3]TCO 2013 Round 3A TrickyInequality
[1+]TCO 2013 Semifinal 1 GameWithTree
[1-]TCO 2013 Semifinal 2 OneBlack
[2-]TCO 2013 Round 3B ToastJumping
[2-]TCO 2013 Finals TBlocks
[2]TCO 2013 Wildcard SemiMultiple
[0-+]hdu 5469 Antonidas
[0]hdu 5478 Can you find it
[0-]hdu 5489 Removed Interval
[0-]hdu 5493 Queue
[0]CF240F TorCoder
[2-]CF241D Numbers
[0]CF249E Endless Matrix
[1]CF241B Friends

9.18 金曜日

TCO13 Round 1B 1000 EllysReversals

【脱出战 Scene 3】

Infan: …………前方……或许……或许还有村庄呢…………
Fiya: 已经到了这种地步了么……
Infan: 咦？…………我还记得最后一条路…………不过…………算了。与其死在这里……不如拼命吧。
Fiya: 那就走吧。

TCO13 Round 1A 1000 DirectionBoard

9.19 土曜日

正名之战。
不过…………还是打输了啊………………

hdu 5451 Best Solver

原题BZOJ 4002
明明找个循环节的事情……我为什么找完以后还要矩阵快速幂啊………………
都是自己拖了队友的后腿…………

# include <cstdio>
# include <algorithm>
# include <iostream>
# include <string>
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 ++)
typedef long long ll;
int f[1001000];
int Force (int P)
{
    f[0] = 2 % P, f[1] = 10 % P;
    FOR (i, 2, 500000)
    {
        f[i] = (10 * f[i - 1] - f[i - 2] + P) % P;
        if (f[i] == f[1] && f[i - 1] == f[0]) return i - 1;
    }
    return -1;
}
int Pow2 (ll z, int P)
{
    int res = 1, a = 2;
    do {if (z & 1) res = res * a % P; a = a * a % P;} while (z >>= 1);
    return res;
}
int q0;
int main ()
{
    scanf ("%d", &q0);
    ll n; int P;
    REP (id, q0)
    {
        scanf ("%lld%d", &n, &P);
        printf ("Case #%d: %d\n", id, (f[Pow2 (n, Force (P)) + 1] + P - 1) % P);
    }
    return 0;
}

hdu 5456 Matches Puzzle Game

傻逼数位DP………………
一个10写成9调了半个小时…………

# include <cstdio>
# include <cstring>
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 CLR(a, x) memset (a, x, sizeof (a))
unsigned f[510][2][2][2];
int w[2][10] = 
{ 
    {0, 2, 5, 5, 4, 5, 6, 3, 7, 6}, 
    {6, 2, 5, 5, 4, 5, 6, 3, 7, 6}
};
int q0, n, P;
unsigned DFS (int rem, bool bS, bool cS, bool car)
{
    if (rem < 0) return 0;
    if (!rem) return bS && cS && !car;
    unsigned &s = f[rem][bS][cS][car];
    if (s != -1) return s;
    s = 0;
    REP_0 (i, 10)
        REP_0 (j, 10)
        {
            int d = i - j + car * 10;
            if (0 <= d && d < 10) s += DFS (rem - w[1][i] - w[bS][j] - w[cS][d], bS || j, cS || d, false);
            if (s >= P) s -= P;
            d --;
            if (0 <= d && d < 10) s += DFS (rem - w[1][i] - w[bS][j] - w[cS][d], bS || j, cS || d, true);
            if (s >= P) s -= P;
        }
    return s;
}
int main ()
{
    scanf ("%d", &q0);
    REP (id, q0)
    {
        scanf ("%d%d", &n, &P), n -= 3;
        CLR (f, -1);
        unsigned ans = 0;
        REP (fA, 9)
            REP_0 (fB, 10)
            {
                int d = fA - fB;
                if (0 <= d && d < 10) ans += DFS (n - w[1][fA] - w[0][fB] - w[0][d], fB, d, false);
                if (ans >= P) ans -= P;
                d --;
                if (0 <= d && d < 10) ans += DFS (n - w[1][fA] - w[0][fB] - w[0][d], fB, d, true);
                if (ans >= P) ans -= P;
            }
        printf ("Case #%d: %u\n", id, ans);
    }
    return 0;
}

hdu 5458 Stability

倒过来跑一遍LCT 大暴力…………
时间复杂度$O(N\log N)$

/* Template the Final Chapter Light --- Fimbulvetr version 0.1 */
/* In this blizzard, I will find peace. */
# define LOCAL
# include <cstring>
# include <cstdio>
# include <algorithm>
# include <vector>
# include <string>
# include <set>
# include <map>
# include <iostream>
# include <cmath>
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 REP_D(i, n) for (int i = n; i >= 1; i --)
# define REP_S( i, ss ) for ( char *i = ss; *i; i ++ )
# define REP_G( i, u ) for ( int i = pos[ u ]; 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 ) )
# define CPY( a, b ) memcpy ( a, b, sizeof ( a ) )
typedef long long LL;
const int inf = 1 << 30;
# define NR 101000
# define lc ch[ 0 ]
# define rc ch[ 1 ]
struct lctnode 
{ 
    int ch[ 2 ], sum, par, val; bool rev, cov; 
    inline void Rev () {rev ^= 1, swap (lc, rc);} 
    inline void Cov () {val = sum = 0, cov = 1;}
    inline void Rst ( bool ty ) {lc = rc = par = rev = cov = 0, val = sum = ty;}
} lct[NR];
int n, m, q0;
# define u lct[ x ]
# define ulfc lct[ u.lc ]
# define urtc lct[ u.rc ]
# define r lct[ y ]
# define up lct[ u.par ]
# define vc ch[ !ty ]
# define tc ch[ ty ]
inline void Upd ( int x ) { u.sum = ulfc.sum + urtc.sum + u.val; }
inline void PD ( int x ) 
{ 
    if ( u.rev ) { u.rev = false; if ( u.lc ) ulfc.Rev (); if ( u.rc ) urtc.Rev (); }
    if ( u.cov ) { u.cov = false; if ( u.lc ) ulfc.Cov (); if ( u.rc ) urtc.Cov (); }
}
inline int sgn ( int x ) { return up.lc == x ? 0 : up.rc == x ? 1 : -1; }
inline void sc ( int x, int y, bool ty ) { u.tc = y, r.par = x; }
inline void fix ( int x ) { if ( ~sgn ( x ) ) fix ( u.par ); PD ( x ); }
inline void Rot ( int x, bool ty )
{
    int y = u.par, z = r.par; if ( ~sgn ( y ) ) sc ( z, x, sgn ( y ) ); else u.par = z;
    sc ( y, u.vc, ty ), sc ( x, y, !ty ), Upd ( y );
}
inline int Splay ( int x )
{
    fix ( x ); int t0, t1, y;
    while ( ~( t0 = sgn ( x ) ) )
    {
        if ( ~( t1 = sgn ( y = u.par ) ) ) Rot ( t0 ^ t1 ? x : y, t0 ), Rot ( x, t1 );
        else Rot ( x, t0 );
    }
    Upd ( x ); 
    return x;
}
inline int Acs ( int tx )
{
    for ( int x = tx, y = 0; x; Upd ( y = x ), x = u.par ) Splay ( x ), u.rc = y;
    return Splay ( tx );
}
# define us lct[ Acs ( x ) ]
inline int rt ( int x ) { for ( x = Acs ( x ); PD ( x ), u.lc; x = u.lc ) ; return Splay ( x ); }
inline int Evt ( int x ) { us.Rev (); return x; }
inline void Link ( int x, int y ) { Evt ( x ), u.par = y; }
inline int Qry (int x, int y) { Evt ( x ); return lct[ Acs ( y ) ].sum; }
inline void Mfy (int x, int y) { Evt ( x ); lct[ Acs ( y ) ].Cov (); }
int psz, q;
inline void Add (int x, int y) 
{
    if (rt (x) != rt (y)) psz ++, Link (x, psz), Link (y, psz);
    else Mfy (x, y);
}
typedef pair <int, int> pii;
int ans[NR], op[NR], _x[NR], _y[NR];
map <pii, int> g;
inline pii gp (int a, int b) {return a < b ? make_pair (a, b) : make_pair (b, a);}
int main ()
{
    scanf ("%d", &q0);
    REP (id, q0)
    {
        printf ("Case #%d:\n", id);
        scanf ("%d%d%d", &n, &m, &q);
        REP (x, (n << 1) - 1) u.Rst (x > n);
        g.clear ();
        psz = n; int t1, t2;
        REP (i, m) scanf ("%d%d", &t1, &t2), g[gp (t1, t2)] ++;
        REP (i, q)
        {
            scanf ("%d%d%d", &op[i], &_x[i], &_y[i]);
            if (op[i] == 1) g[gp (_x[i], _y[i])] --;
        }
        for (map <pii, int>::iterator it = g.begin (); it != g.end (); it ++)
            if (it->second)
                Add ((it->first).first, (it->first).second);
        REP_D (i, q)
        {
            if (op[i] == 2) ans[i] = Qry (_x[i], _y[i]);
            else Add (_x[i], _y[i]);
        }
        REP (i, q) if (op[i] == 2) printf ("%d\n", ans[i]);
    }
    return 0;
}

hdu 5459 Jesus Is Here

…………拼接处不会产生新的cff……

# include <cstdio>
# include <algorithm>
# include <iostream>
# include <string>
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 ++)
typedef long long ll;
const int P = 530600414;
struct Arr
{
    int len, sum, ans, cnt;
    Arr () {len = sum = ans = cnt = 0;}
    Arr (int _len, int _cnt, int _sum, int _ans) {len = _len, cnt = _cnt, sum = _sum, ans = _ans;}
} f[202000];
Arr operator + (Arr a, Arr b)
{
    return Arr (
        (a.len + b.len) % P, 
        (a.cnt + b.cnt) % P, 
        (a.sum + b.sum + 1ll * b.cnt * a.len) % P,
        (a.ans + b.ans + (b.sum + 1ll * b.cnt * a.len) % P * a.cnt - 1ll * a.sum * b.cnt % P + P) % P);
}
int Solve (int n)
{
    if (n <= 4) return 0;
    return f[n].ans;
}
void Init ()
{
    f[3] = Arr (3, 1, 0, 0);
    f[4] = Arr (5, 1, 2, 0);
    FOR (i, 5, 201314) f[i] = f[i - 2] + f[i - 1];
}
int q0, n;
int main ()
{
    Init ();
    scanf ("%d", &q0);
    REP (id, q0) scanf ("%d", &n), printf ("Case #%d: %d\n", id, Solve (n));
    return 0;
}

9.20 日曜日

ACM-ICPC 2015 Beijing Online Couple Trees

…………可持久化线段树显然……
$O(N\log N)$

# include <cstdio>
# include <cstring>
# include <cassert>
# include <algorithm>
# 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_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))
# define CPY(a, b) memcpy (a, b, sizeof (a))
# define NR 201000
struct Edge {int y, frt; void Set (int _y, int _frt) {y = _y, frt = _frt;}} g[NR << 1];
int pos[NR], gsz, dsz, bg[NR], ed[NR], ro[NR], tsz, dep[NR], fa[NR], n, m, q0, __depb[NR];
inline void AE (int x, int y) {g[++ gsz].Set (y, pos[x]), pos[x] = gsz;}
inline int depMax (int a, int b) {return dep[a] < dep[b] ? b : a;}
# define u t[x]
# define o t[y]
# define lc ch[0]
# define rc ch[1]
# define ulfc t[u.lc]
# define urtc t[u.rc]
struct Seg
{
    int ch[2], tag;
    inline void Max (int w) {tag = depMax (tag, w);}
    inline void clean () {lc = rc = tag = 0;}
} t[8001000];
void segMfyMax (int &x, int l, int r, int ml, int mr, int w, int y)
{
    x = ++ tsz; u = o;
    if (ml <= l && r <= mr) {u.Max (w); return ;}
    int mid = (l + r) >> 1;
    if (ml <= mid) segMfyMax (u.lc, l, mid, ml, mr, w, o.lc);
    if (mr > mid) segMfyMax (u.rc, mid + 1, r, ml, mr, w, o.rc);
}
int segQuery (int x, int l, int r, int p, int cur)
{
    if (!x) return cur;
    cur = depMax (cur, u.tag);
    if (l == r) return cur;
    int mid = (l + r) >> 1;
    if (p <= mid) return segQuery (u.lc, l, mid, p, cur);
    return segQuery (u.rc, mid + 1, r, p, cur);
}
# define v g[i].y
void dfsSeq (int x)
{
    bg[x] = ++ dsz;
    REP_G (i, x) if (v != fa[x]) dep[v] = dep[x] + 1, fa[v] = x, dfsSeq (v);
    ed[x] = dsz;
}
void dfsPre (int x, int fa)
{
    segMfyMax (ro[x], 1, n, bg[x], ed[x], x, ro[fa]);
    REP_G (i, x) if (v != fa) __depb[v] = __depb[x] + 1, dfsPre (v, x);
}
int main ()
{
    dep[0] = -1;
    while (scanf ("%d%d", &n, &m) != EOF)
    {
        dsz = tsz = 0; int t1, t2, lst = 0;
        RST (pos), gsz = 0;
        FOR (i, 2, n) scanf ("%d", &t1), AE (t1, i);
        dfsSeq (1);
        RST (pos), gsz = 0;
        FOR (i, 2, n) scanf ("%d", &t1), AE (t1, i);
        dfsPre (1, 0);
        REP (i, m) 
        {
            scanf ("%d%d", &t1, &t2), t1 = (t1 + lst) % n + 1, t2 = (t2 + lst) % n + 1;
            lst = segQuery (ro[t2], 1, n, bg[t1], 0), printf ("%d %d %d\n", lst, dep[t1] - dep[lst] + 1, __depb[t2] - __depb[lst] + 1);
        }
        REP (x, tsz) u.clean ();
    }
    return 0;
}

ASC02 F Roads

调了一天发现是LCA写错了…………
考虑$c_i$是花在第$i$条边上的代价。
显然有$w_i-c_i\leq w_j+c_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_D0(i, n) for (int i = n - 1; i >= 0; i --)
# define FOR(i, a, b) for (int i = a; i <= b; i ++)
# define RST(a) memset (a, 0, sizeof (a))
# define CLR(a, x) memset (a, x, sizeof (a))
# define NR 410
struct Edge {int y, frt, w; void Set (int _y, int _frt, int _w) {y = _y, frt = _frt, w = _w;}} __g[NR << 1];
int pos[NR], gsz, g[NR][NR], lx[NR], __tw[NR], ly[NR], match[NR], lack, N, dep[NR], f[NR][10], fa[NR], fi[NR], n, m;
bool visx[NR], visy[NR];
const int inf = 1 << 30;
inline void AE (int x, int y, int z) {__g[++ gsz].Set (y, pos[x], z), pos[x] = gsz;}
template <class T0, class T1> inline bool RlxN (T0 &a, T1 b) {if (a > b) return a = b, true; return false;}
template <class T0, class T1> inline bool RlxX (T0 &a, T1 b) {if (a < b) return a = b, true; return false;}
# define v __g[i].y
void DFS (int x)
{
    f[x][0] = fa[x];
    for (int i = 1; (1 << i) <= dep[x]; i ++)
        f[x][i] = f[f[x][i - 1]][i - 1];
    for (int i = pos[x]; i; i = __g[i].frt) if (v != fa[x]) fa[v] = x, fi[v] = i >> 1, dep[v] = dep[x] + 1, DFS (v);
}
inline int LCA (int x, int y)
{
    if (dep[x] < dep[y]) swap (x, y);
    REP_D0 (i, 10) if (dep[f[x][i]] >= dep[y]) x = f[x][i];
    if (x == y) return x;
    REP_D0 (i, 10) if (f[x][i] != f[y][i]) x = f[x][i], y = f[y][i];
    return f[x][0];
}
bool Find (int x)
{
    visx[x] = true; int t;
    REP (y, N)
    {
        if (visy[y]) continue;
        t = lx[x] + ly[y] - g[x][y];
        if (t == 0)
        {
            visy[y] = true;
            if (match[y] == -1 || Find (match[y])) return match[y] = x, true;
        }
        else RlxN (lack, t);
    }
    return false;
}
void KM ()
{
    RST (lx), RST (ly), CLR (match, -1);
    REP (i, N) REP (j, N) RlxX (lx[i], g[i][j]);
    REP (x, N)
    {
        while (true)
        {
            RST (visx), RST (visy), lack = inf;
            if (Find (x)) break;
            REP (i, N) 
            {
                if (visx[i]) lx[i] -= lack; 
                if (visy[i]) ly[i] += lack;
            }
        }
    }
}
int main ()
{
    scanf ("%d%d", &n, &m), gsz = 1, dep[0] = -1;
    int t1, t2, t3;
    REP (i, n - 1) scanf ("%d%d%d", &t1, &t2, &t3), AE (t1, t2, t3), AE (t2, t1, t3);
    DFS (1);
    FOR (i, n, m)
    {
        scanf ("%d%d%d", &t1, &t2, &t3), __tw[i] = t3;
        int z = LCA (t1, t2);
        for (int x = t1; x != z; x = fa[x]) RlxX (g[fi[x]][i], __g[fi[x] << 1].w - t3);
        for (int x = t2; x != z; x = fa[x]) RlxX (g[fi[x]][i], __g[fi[x] << 1].w - t3);
    }
    N = m, KM ();
    REP (i, n - 1) printf ("%d\n", __g[i << 1].w - lx[i]);
    FOR (i, n, m) printf ("%d\n", __tw[i] + ly[i]);
    return 0;
}

9.21 月曜日

TCO13 Round 2A 1000 ThePowers

TCO12 Wildcard 1000 StringSequence

DP题对着题解写代码有毛用…………
…………先考虑$A$为空串的情形。
令插入$B[i,j)$的方案数为$F(i,j)$。
将串$S$中相同的连续的字母缩成一段，显然在某一段的任意位置插入该段的字母都是等价的。
为了避免重复我们强制只能在段末尾插入。
则

$$F(i,j)=\sum_{i\leq k<j, B_k\neq B_j}F(i,k)F(k+1,j)\binom{j-i-1}{k-i}$$
考虑串$A$不为空的情形时，我们令$g[i][j]$为串$A$匹配到$i$，串$B$匹配到$j$时的方案数。
则
$$g[i+1][k]+=\binom{k-i-1}{j-i}F(j+1,k)g[i][j]$$

# include <cstdio>
# include <cstring>
# include <string>
# include <cassert>
# include <algorithm>
# 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 FOR(i, a, b) for (int i = a; i <= b; i ++)
# define CLR(a, x) memset (a, x, sizeof (a))
const int P = 1000000007;
# define NR 60
class StringSequences
{
private:
    int f[NR][NR], g[NR][NR], bi[NR][NR], n, m;
    char Sa[NR], Sb[NR];
    int F (int i, int j)
    {
        if (i == j) return 1;
        int &s = f[i][j];
        if (s != -1) return s;
        s = 0;
        FOR (k, i, j - 1) if (Sb[k] != Sb[j]) s = (s + 1ll * F (i, k) * F (k + 1, j) % P * bi[j - i - 1][k - i]) % P;
        return s;
    }
public:
    int countSequences (string _A, string _B)
    {
        m = _A.length ();
        n = _B.length ();
        CLR (f, -1);
        REP (i, m) Sa[i] = _A[i - 1];
        REP (i, n) Sb[i] = _B[i - 1];
        bi[0][0] = 1;
        REP (i, n)
        {
            bi[i][0] = 1;
            REP (j, i) 
            {
                bi[i][j] = bi[i - 1][j - 1] + bi[i - 1][j];
                if (bi[i][j] >= P) bi[i][j] -= P;
            }
        }
        m ++;
        n ++;
        g[0][0] = 1;
        REP_0 (i, m)
            FOR (j, i, n)
                FOR (k, j + 1, n)
                {
                    if (Sa[i + 1] != Sb[k]) continue;
                    g[i + 1][k] = (g[i + 1][k] + 1ll * g[i][j] * F (j + 1, k) % P * bi[k - i - 1][j - i]) % P;
                }
        return g[m][n];
    }
};

9.22 火曜日

TCO13 Round 2C 1000 WellTimedSearch

ASC02 H Tickets

写道暴力Polya写的像傻逼一样…………

import java.util.*;
import java.io.*; 
import java.math.*;
public class Main
{
    public static void main (String[] args)
    {
        try
        {
            BufferedReader input = new BufferedReader (new FileReader ("tickets.in"));
            BufferedWriter output = new BufferedWriter (new FileWriter ("tickets.out"));
            String str = input.readLine ();
            int a = 0, b = 0;
            boolean aComplete = false;
            for (int i = 0; i < str.length (); i ++)
            {
                char c = str.charAt (i);
                if (c == ' ') aComplete = true;
                else if (Character.isDigit (c))
                {
                    if (aComplete) b = b * 10 + Character.digit (c, 10);
                    else a = a * 10 + Character.digit (c, 10);
                }
            }
            output.write ((new Solver ()).solve (a, b).toString ());
            output.flush ();
            input.close ();
            output.close ();
        }
        catch (IOException e)
        {
            System.out.println ("File not found!");
        }
    }
}
class Solver
{
    private int n, m;
    private static boolean[] vis = new boolean[420];
    private int poi (int x, int y) {return x * m + y;}
    private int count (int[] p)
    {
        int result = 0;
        Arrays.fill (vis, 0, p.length, false);
        for (int i = 0; i < n * m; i ++)
            if (!vis[i])
            {
                result ++;
                vis[i] = true;
                for (int j = p[i]; j != i; j = p[j])
                    vis[j] = true;
            }
        return result;
    }
    public BigInteger solve (int _n, int _m)
    {
        n = _n; 
        m = _m;
        BigInteger answer = BigInteger.valueOf (0);
        int[][] p;
        int cnt = 0;
        if (n == m) p = new int[4][n * m];
        else p = new int[2][n * m];
        for (int i = 0; i < n; i ++)
            for (int j = 0; j < m; j ++)
            {
                for (int x = 0; x < n; x ++)
                {
                    for (int y = 0; y < m; y ++)
                    {
                        int _x = (x + i) % n, _y = (y + j) % m;
                        p[0][poi (x, y)] = poi (_x, _y);
                        p[1][poi (x, y)] = poi (n - _x - 1, m - _y - 1);
                        if (n == m)
                        {
                            p[2][poi (x, y)] = poi (m - _y - 1, _x);
                            p[3][poi (x, y)] = poi (_y, n - _x - 1);
                        }
                    }
                }
                for (int _p[] : p)
                {
                    answer = answer.add (BigInteger.valueOf (1).shiftLeft (count (_p)));
                    cnt ++;
                }
            }
        return answer.divide (BigInteger.valueOf (cnt));
    }
}

TCO 2013 Round 2B LitPanels

【Battle of Mocosor Day 7 Scene 1】
Noranz: 长官！今天有没有新的作战计划啊？
Dasen: ……没有…………还是强攻……
Noranz: 这样呀……那就继续上吧！
Dasen: ……这小子倒是真有活力呢…………

Infan: 长官！……发现西侧一支敌军魔法连队！有近百人！……
Dasen: …………别急，我去请示。

Dasen: Sergan大人，我军阵地西侧发现敌军一支魔法连队，是否进行攻击？
Sergan: 那就去啊！
Dasen: 我方实力不足进攻，请求支援。
Sergan: 知道了，立刻去进攻吧！我会联系支援的！

9.23 水曜日

TCO 2013 Round 3A TrickyInequality

【Battle of Mocosor Night 7】
浑浊的雨不停地冲击着地面……洗刷着地面上的斑斑血迹。
Dasen: 还没有攻下来呢……Sergan大人……
Sergan: 敌人已经在崩溃的边缘了。
Dasen: 长官，恕我直言……我们几次进攻都被毫不费力地挡下来了……
Sergan: 我知道。Dasen，这一仗至关重要，一定可以胜利的。
Dasen: 长官……伤亡已经……
Sergan: ……我知道了，你先回去吧。
Dasen: ……

Sergan: 今日停止夜战，大家回去休整吧。

Infan: Fiya！我在这里！…………伤势怎么样…………
Fiya: 没事的。
Infan: 去找过军医了？
Fiya: 没有。
Infan: 你怎么老是这样啦……来，我带你去找军医，不然伤口要感染的。
Fiya: ……

Infan: 喂，Fiya，军医在那里啊！喂，你要去哪？
Fiya: ……有人来了呢……
Fiya: ……咦……

TCO 2013 Semifinal 1 GameWithTree

9.24 木曜日

TCO 2013 Semifinal 2 OneBlack

TCO 2013 Round 3B ToastJumping

【Battle of Mocosor Night 8】

Falsytza: 战斗怎么样了啊。
Dasen: 先生，谢谢您！…………已经基本解决了……那个，我们的长官希望能认识您……
Falsytza: ……这种指挥的话还是免了吧。
Dasen: …………那个………………哎！…………Sergan长官！……
Falsytza: ……
Sergan: 十分感谢您对我们的帮助，很高兴认识您，请问您贵姓？
Falsytza: …………有事先告辞了。
Sergan: ……

Sergan: 去休息吧……
Dasen: 是……

Fiya: 你要去哪。
Falsytza: …………不知道。
Fiya: 留下来吧。
Falsytza: 为什么要留下我？
Fiya: 看着我。
Falsytza: ……为什么我要留下？
Fiya: 因为你无处可去。
Falsytza: ……你在哪个连队？
Fiya: 他的。

Falsytza: 听着，如果你的部队还想活下来，趁早离开那个家伙。
Dazen: ……可是离开他我们又能去哪里呢…………
Falsytza: 跟我走。
Dazen: ……可是…………
Falsytza: ……你还不知道你们附近有多少敌人？
Dazen: …………Seral，过来……附近有多少敌人…………说实话…………什么？！
Falsytza: 所以你们还觉得那家伙能带着你们活着出去？
Dazen: ……走！…………我走…………

TCO 2013 Finals TBlocks

9.25 金曜日

TCO 2013 Wildcard SemiMultiple

金曜日的早安~
完结撒花啦w 赶上了太太改二的日子呢哟~www
被虐的神志不清啦……要去休息休息啦……

9.26 土曜日

9.27 日曜日

9.28 月曜日

CF240F TorCoder

显然用一个线段树维护区间出现次数就好……

# include <cstdio>
# include <cstring>
# include <cassert>
# include <iostream>
# 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_D0(i, n) for (int i = n - 1; i >= 0; -- i)
# define max(a, b) ((a) > (b) ? (a) : (b))
# define NR 100100
int n, m, cur, sz, infol[NR], infor[NR], __root;
char s[NR];
inline int isc (int l0, int r0, int l1, int r1) {return max (0, min (r0, r1) - max (l0, l1) + 1);}
struct Info
{
    int cnt[26];
    void apply (Info tag, int l, int r, int _l, int _r)
    {
        int _m = (_l + _r - 1) >> 1, p = _l, s = -1;
        REP_0 (i, 26)
        {
            if (tag.cnt[i] % 2 == 1) s = i;
            tag.cnt[i] >>= 1;
            cnt[i] = isc (l, r, p, p + tag.cnt[i] - 1);
            p += tag.cnt[i];
        }
        if (s != -1) 
        {
            if (l <= p && p <= r) cnt[s] ++; 
            p ++;
        }
        REP_D0 (i, 26)
        {
            cnt[i] += isc (l, r, p, p + tag.cnt[i] - 1);
            p += tag.cnt[i];
        }
        assert (p == _r + 1);
    }
} info[NR];
# define u t[x]
# define lc ch[0]
# define rc ch[1]
# define ulfc t[u.lc]
# define urtc t[u.rc]
struct Seg 
{
    int ch[2], cov; Info w;
    inline void cover (int _v, int l, int r) {w.apply (info[_v], l, r, infol[_v], infor[_v]), cov = _v;}
} t[NR << 2];
inline void push (int x, int l, int r) {if (!u.cov) return ; int mid = (l + r) >> 1; ulfc.cover (u.cov, l, mid), urtc.cover (u.cov, mid + 1, r), u.cov = 0;}
inline void upd (int x) {REP_0 (i, 26) u.w.cnt[i] = ulfc.w.cnt[i] + urtc.w.cnt[i];}
inline void count (int x, int l, int r, int cl, int cr)
{
    if (cl <= l && r <= cr) {REP_0 (i, 26) info[cur].cnt[i] += u.w.cnt[i]; return ;}
    push (x, l, r); int mid = (l + r) >> 1;
    if (cl <= mid) count (u.lc, l, mid, cl, cr);
    if (cr > mid) count (u.rc, mid + 1, r, cl, cr);
}
bool check (int l, int r)
{
    count (__root, 1, n, l, r);
    bool odd = false;
    REP_0 (i, 26) if (info[cur].cnt[i] % 2 == 1) {if (!odd) odd = true; else return false;}
    return true;
}
void modify (int x, int l, int r, int ml, int mr)
{
    if (ml <= l && r <= mr) {u.cover (cur, l, r); return ;}
    push (x, l, r); int mid = (l + r) >> 1;
    if (ml <= mid) modify (u.lc, l, mid, ml, mr);
    if (mr > mid) modify (u.rc, mid + 1, r, ml, mr);
    upd (x);
}
int build (int l, int r)
{
    int x = ++ sz, mid = (l + r) >> 1;
    if (l == r) {++ u.w.cnt[s[l] - 'a']; return x;}
    return u.lc = build (l, mid), u.rc = build (mid + 1, r), upd (x), x;
}
void output (int x, int l, int r)
{
    if (l == r) {REP_0 (i, 26) if (u.w.cnt[i] > 0) putchar (i + 'a'); return ;}
    push (x, l, r); int mid = (l + r) >> 1; output (u.lc, l, mid), output (u.rc, mid + 1, r);
}
int main ()
{
    scanf ("%d%d%s", &n, &m, s + 1);
    int t1, t2; __root = build (1, n);
    REP (i, m)
    {
        scanf ("%d%d", &t1, &t2), ++ cur, infol[cur] = t1, infor[cur] = t2;
        if (check (t1, t2)) modify (__root, 1, n, t1, t2);
    }
    output (__root, 1, n);
    return 0;
}

CF241D Numbers

能不能不天天爆OJ啊哭……

可以发现它给的两个条件毫不相关。
我们把它给的两个条件看作两个函数，子序列异或和为$0$在只考虑大小在$O(\log n)$之内元素的时候就有远大于$p$种情况了。那么大概可以知道，直接暴力取大小在$O(\log n)$之内的元素就可以了。

# include <cstdio>
# define REP(i, n) for (int i = 1; i <= n; i ++)
# define REP_D(i, n) for (int i = n; i >= 1; i --)
bool vis[33][33][50010];
int n, m, P, li[100], len, a[100], id[50010], dig[100];
bool DFS (int i, int j, int k)
{
    if (i > n) return !j && !k;
    if (vis[i][j][k]) return false;
    vis[i][j][k] = true;
    if (DFS (i + 1, j, k)) return true;
    if (DFS (i + 1, j ^ a[i], (k * dig[a[i]] + a[i]) % P)) return li[++ len] = a[i], true;
    return false;
}
bool solve () {REP (i, n) if (DFS (i + 1, a[i], a[i] % P)) {li[++ len] = a[i]; return true;} return false;}
int main ()
{
    scanf ("%d%d", &m, &P); int t1;
    REP (i, 31) dig[i] = i < 10 ? 10 : 100;
    REP (i, m) {scanf ("%d", &t1); if (t1 < 32) id[a[++ n] = t1] = i;}
    if (solve ()) {printf ("Yes\n%d\n", len); REP_D (i, len) printf ("%d ", id[li[i]]);}
    else puts ("No");
    return 0;
}