头像

心里没有一点AC数

兰州大学 - 网易浚源工作室 - 西山居 - <https://www.fogsail.net/>




离线:2小时前


新鲜事 原文

字符串相关的,乱七八糟的搜索 debug太难了啊啊啊啊
图片 图片


活动打卡代码 AcWing 2523. 历史研究

BZOJ4241-01.jpg
BZOJ4241-02.jpg

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <queue>
#include <vector>
#include <stack>
#include <map>
#include <set>
#include <sstream>
#include <iomanip>
#include <cmath>
#include <bitset>
#include <assert.h>

using namespace std;
typedef long long llong;
typedef set<int>::iterator ssii;

#define Cmp(a, b) memcmp(a, b, sizeof(b))
#define Cpy(a, b) memcpy(a, b, sizeof(a))
#define Set(a, v) memset(a, v, sizeof(a))
#define debug(x) cout << #x << ": " << x << endl
#define _forS(i, l, r) for(set<int>::iterator i = (l); i != (r); i++)
#define _rep(i, l, r) for(int i = (l); i <= (r); i++)
#define _for(i, l, r) for(int i = (l); i < (r); i++)
#define _forDown(i, l, r) for(int i = (l); i >= r; i--)
#define debug_(ch, i) printf(#ch"[%d]: %d\n", i, ch[i])
#define debug_m(mp, p) printf(#mp"[%d]: %d\n", p->first, p->second)
#define debugS(str) cout << "dbg: " << str << endl;
#define debugArr(arr, x, y) _for(i, 0, x) { _for(j, 0, y) printf("%c", arr[i][j]); printf("\n"); }
#define _forPlus(i, l, d, r) for(int i = (l); i + d < (r); i++)
#define lowbit(i) (i & (-i))
#define MPR(a, b) make_pair(a, b)

const int maxn = 100000 + 10;
const int maxb = 5000;
int n, m, N;

int a[maxn], typ[maxn], inp[maxn];

class Qry {
public:
    int l, r, id;
};
Qry qry[maxn];

// == discrete ==
void discrete() {
    sort(inp + 1, inp + 1 + n);
    N = unique(inp + 1, inp + 1 + n) - inp - 1;
    _rep(i, 1, n) typ[i] = lower_bound(inp + 1, inp + 1 + N, a[i]) - inp;
}
// == discrete finished ==

// == block ==
int bl[maxn], br[maxn];
int belong[maxn];
int sz, t;

void block() {
    sz = sqrt(n);
    t = n / sz;
    _rep(i, 1, t) {
        bl[i] = (i - 1) * sz + 1;
        br[i] = i * sz;

        _rep(k, bl[i], br[i]) belong[k] = i;
    }

    if(t * sz < n) {
        t++;
        bl[t] = (t - 1) * sz + 1;
        br[t] = n;

        _rep(k, bl[t], br[t]) belong[k] = t;
    }
}

bool cmp(const Qry& a, const Qry& b) {
    if(belong[a.l] ^ belong[b.l]) return belong[a.l] < belong[b.l];
    return a.r < b.r;
}
// == block finsihed ==
int cnt[maxn];
llong ANS[maxn];

void initMo() {
    Set(ANS, 0);
    Set(cnt, 0);
}

llong force(int ql, int qr) {
    llong res = 0;
    int tcnt[maxn];

    _rep(i, ql, qr) tcnt[typ[i]] = 0;
    _rep(i, ql, qr) {
        tcnt[typ[i]]++;
        res = max(res, (llong)1 * tcnt[typ[i]] * a[i]);
        //debug(res);
    }
    return res;
}

void solve() {
    sort(qry + 1, qry + 1 + m, cmp);

    int i = 1;
    _rep(k, 1, t) {
        int l = br[k] + 1, r = br[k];
        Set(cnt, 0);
        llong res = 0;

        // brute force for seg in block
        for( ; belong[qry[i].l] == k; i++) {
            int ql = qry[i].l, qr = qry[i].r;

            if(belong[ql] == belong[qr]) {
                llong ans = force(ql, qr);
                ANS[qry[i].id] = ans;
                continue;
            }

            llong fix = 0;
            while (r < qr) {
                r++;
                ++cnt[typ[r]];
                res = max(res, (llong)1 * cnt[typ[r]] * a[r]);
                //debug(res);
            }
            fix = res;

            while (l > ql) {
                l--;
                ++cnt[typ[l]];
                res = max(res, (llong)1 * cnt[typ[l]] * a[l]);
                //debug(res);
            }

            ANS[qry[i].id] = res;
            //debug(res);

            while (l < br[k] + 1) {
                --cnt[typ[l]];
                ++l;
            }

            res = fix;
        }
    }
}


int main() {
    //freopen("input.txt", "r", stdin);
    // == input ==
    scanf("%d%d", &n, &m);
    _rep(i, 1, n) {
        scanf("%d", &a[i]);
        inp[i] = a[i];
    }
    _rep(i, 1, m) {
        int _l, _r;
        scanf("%d%d", &_l, &_r);
        qry[i].l = _l;
        qry[i].r = _r;
        qry[i].id = i;
    }
    // == input finished ==

    // == discrete ==
    discrete();
    // == discrete finished ==

    // == block ==
    block();
    // == block finished ==

    // == Mo Algorithm ==
    initMo();
    solve();
    // == Mo Algo finished ==

    _rep(i, 1, m) printf("%lld\n", ANS[i]);
}



BZOJ4241-01.jpg
BZOJ4241-02.jpg

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <queue>
#include <vector>
#include <stack>
#include <map>
#include <set>
#include <sstream>
#include <iomanip>
#include <cmath>
#include <bitset>
#include <assert.h>

using namespace std;
typedef long long llong;
typedef set<int>::iterator ssii;

#define Cmp(a, b) memcmp(a, b, sizeof(b))
#define Cpy(a, b) memcpy(a, b, sizeof(a))
#define Set(a, v) memset(a, v, sizeof(a))
#define debug(x) cout << #x << ": " << x << endl
#define _forS(i, l, r) for(set<int>::iterator i = (l); i != (r); i++)
#define _rep(i, l, r) for(int i = (l); i <= (r); i++)
#define _for(i, l, r) for(int i = (l); i < (r); i++)
#define _forDown(i, l, r) for(int i = (l); i >= r; i--)
#define debug_(ch, i) printf(#ch"[%d]: %d\n", i, ch[i])
#define debug_m(mp, p) printf(#mp"[%d]: %d\n", p->first, p->second)
#define debugS(str) cout << "dbg: " << str << endl;
#define debugArr(arr, x, y) _for(i, 0, x) { _for(j, 0, y) printf("%c", arr[i][j]); printf("\n"); }
#define _forPlus(i, l, d, r) for(int i = (l); i + d < (r); i++)
#define lowbit(i) (i & (-i))
#define MPR(a, b) make_pair(a, b)

const int maxn = 100000 + 10;
const int maxb = 5000;
int n, m, N;

int a[maxn], typ[maxn], inp[maxn];

class Qry {
public:
    int l, r, id;
};
Qry qry[maxn];

// == discrete ==
void discrete() {
    sort(inp + 1, inp + 1 + n);
    N = unique(inp + 1, inp + 1 + n) - inp - 1;
    _rep(i, 1, n) typ[i] = lower_bound(inp + 1, inp + 1 + N, a[i]) - inp;
}
// == discrete finished ==

// == block ==
int bl[maxn], br[maxn];
int belong[maxn];
int sz, t;

void block() {
    sz = sqrt(n);
    t = n / sz;
    _rep(i, 1, t) {
        bl[i] = (i - 1) * sz + 1;
        br[i] = i * sz;

        _rep(k, bl[i], br[i]) belong[k] = i;
    }

    if(t * sz < n) {
        t++;
        bl[t] = (t - 1) * sz + 1;
        br[t] = n;

        _rep(k, bl[t], br[t]) belong[k] = t;
    }
}

bool cmp(const Qry& a, const Qry& b) {
    if(belong[a.l] ^ belong[b.l]) return belong[a.l] < belong[b.l];
    return a.r < b.r;
}
// == block finsihed ==
int cnt[maxn];
llong ANS[maxn];

void initMo() {
    Set(ANS, 0);
    Set(cnt, 0);
}

llong force(int ql, int qr) {
    llong res = 0;
    int tcnt[maxn];

    _rep(i, ql, qr) tcnt[typ[i]] = 0;
    _rep(i, ql, qr) {
        tcnt[typ[i]]++;
        res = max(res, (llong)1 * tcnt[typ[i]] * a[i]);
        //debug(res);
    }
    return res;
}

void solve() {
    sort(qry + 1, qry + 1 + m, cmp);

    int i = 1;
    _rep(k, 1, t) {
        int l = br[k] + 1, r = br[k];
        Set(cnt, 0);
        llong res = 0;

        // brute force for seg in block
        for( ; belong[qry[i].l] == k; i++) {
            int ql = qry[i].l, qr = qry[i].r;

            if(belong[ql] == belong[qr]) {
                llong ans = force(ql, qr);
                ANS[qry[i].id] = ans;
                continue;
            }

            llong fix = 0;
            while (r < qr) {
                r++;
                ++cnt[typ[r]];
                res = max(res, (llong)1 * cnt[typ[r]] * a[r]);
                //debug(res);
            }
            fix = res;

            while (l > ql) {
                l--;
                ++cnt[typ[l]];
                res = max(res, (llong)1 * cnt[typ[l]] * a[l]);
                //debug(res);
            }

            ANS[qry[i].id] = res;
            //debug(res);

            while (l < br[k] + 1) {
                --cnt[typ[l]];
                ++l;
            }

            res = fix;
        }
    }
}


int main() {
    //freopen("input.txt", "r", stdin);
    // == input ==
    scanf("%d%d", &n, &m);
    _rep(i, 1, n) {
        scanf("%d", &a[i]);
        inp[i] = a[i];
    }
    _rep(i, 1, m) {
        int _l, _r;
        scanf("%d%d", &_l, &_r);
        qry[i].l = _l;
        qry[i].r = _r;
        qry[i].id = i;
    }
    // == input finished ==

    // == discrete ==
    discrete();
    // == discrete finished ==

    // == block ==
    block();
    // == block finished ==

    // == Mo Algorithm ==
    initMo();
    solve();
    // == Mo Algo finished ==

    _rep(i, 1, m) printf("%lld\n", ANS[i]);
}



计算几何+搜索

UVA10639

UVA10639.jpg

AC 代码如下

#include <bits/stdc++.h>
using namespace std;
#define _for(i, l, r) for(int i = (l); i < (r); i++)
const double eps = 1e-6;
const double inf = 0x3f3f3f3f;
const int maxn = 10;
int n, m;
int dcmp(double x) {
    if (fabs(x) < eps) return 0;
    else return x < 0 ? -1 : 1;
}
class Point {
public:
    double x, y;
    Point(double xx = 0, double yy = 0) : x(xx), y(yy) {}

    Point operator+ (const Point &rhs) const {
        return Point(x+rhs.x, y+rhs.y);
    }
    Point operator- (const Point &rhs) const {
        return Point(x-rhs.x, y-rhs.y);
    }
    bool operator== (const Point &rhs) const {
        return dcmp(x-rhs.x) == 0 && dcmp(y-rhs.y) == 0;
    }
};

typedef Point Vector;
double Dot(Vector A, Vector B) { return A.x*B.x + A.y*B.y; }
double Cross(Vector A, Vector B) { return A.x*B.y - A.y*B.x; }

bool onSegment(Point p, Point a1, Point a2) {
    bool fl = dcmp( Cross(a1-p, a2-p) ) == 0 && dcmp( Dot(a1-p, a2-p) ) < 0;
    return fl || (p == a1) || (p == a2);
}

const int RD = 2, LD = 3, RU = 4, LU = 5;
const int DOWN = 1, UP = 2, RIGHT = 3, LEFT = 4;

class Poly {
public:
    int K;
    Point a[105];
    int mat[maxn][maxn];

    int check(const Point &p) const {
        int wn = 0;
        _for(i, 0, K) {
            if ( onSegment(p, a[i], a[(i+1)%K]) ) return 2;
            int fl = dcmp( Cross(a[(i+1)%K]-a[i], p-a[i]) );
            int d1 = dcmp( a[i].y - p.y );
            int d2 = dcmp( a[(i+1)%K].y - p.y );
            if (fl > 0 && d1 <= 0 && d2 > 0) wn++;
            if (fl < 0 && d2 <= 0 && d1 > 0) wn--;
        }
        if (wn != 0) return 1;
        return 0;
    }

    void buildMap() {
        _for(i, 0, m) _for(j, 0, m) {
                Point mid( (double)(i) + 0.5, (double)(j) + 0.5 );
                Point lu( (double)(i) + 0.25, (double)(j) + 0.75 );
                Point ru( (double)(i) + 0.75, (double)(j) + 0.75 );
                Point ld( (double)(i) + 0.25, (double)(j) + 0.25 );
                Point rd( (double)(i) + 0.75, (double)(j) + 0.25 );

                if (check(mid) == 0) mat[i][j] = 0;
                else if (check(mid) == 1) mat[i][j] = 1;
                else if (check(ld) == 2 && check(ru) == 2 && check(rd) == 1) mat[i][j] = RD;
                else if (check(lu) == 2 && check(rd) == 2 && check(ld) == 1) mat[i][j] = LD;
                else if (check(lu) == 2 && check(rd) == 2 && check(ru) == 1) mat[i][j] = RU;
                else mat[i][j] = LU;
            }
    }

    double Area() {
        double ans = 0.0;
        _for(i, 0, m) _for(j, 0, m) {
                if (mat[i][j] == 1) ans += 1;
                else if (mat[i][j] != 0) ans += 0.5;
            }
        return ans;
    }
    void normalize() {
        double xmin = inf, ymin = inf;

        _for(i, 0, K) {
            xmin = min(xmin, a[i].x);
            ymin = min(ymin, a[i].y);
        }
        _for(i, 0, K) {
            a[i].x -= xmin;
            a[i].y -= ymin;
            assert(0 <= a[i].x && a[i].x <= m);
            assert(0 <= a[i].y && a[i].y <= m);
        }

        buildMap();
    }
    void rotate() {
        _for(i, 0, K) {
            a[i] = Point(a[i].y, -a[i].x);
        }
        normalize();
    }

    bool Move(int dir) {
        if (dir == DOWN) {
            _for(i, 0, m) if (mat[i][0] != 0) return false;
            _for(j, 0, m-1) {
                _for(i, 0, m) mat[i][j] = mat[i][j+1];
            }
            _for(i, 0, m) mat[i][m-1] = 0;
        }
        if (dir == UP) {
            _for(i, 0, m) if (mat[i][m-1] != 0) return false;
            for (int j = m-1; j > 0; j--) {
                _for(i, 0, m) mat[i][j] = mat[i][j-1];
            }
            _for(i, 0, m) mat[i][0] = 0;
        }
        if (dir == RIGHT) {
            _for(i, 0, m) if (mat[m-1][i] != 0) return false;
            for (int i = m-1; i > 0; i--) {
                _for(j, 0, m) mat[i][j] = mat[i-1][j];
            }
            _for(i, 0, m) mat[0][i] = 0;
        }
        if (dir == LEFT) {
            _for(i, 0, m) if (mat[0][i] != 0) return false;
            _for(i, 0, m-1) {
                _for(j, 0, m) mat[i][j] = mat[i+1][j];
            }
            _for(i, 0, m) mat[m-1][i] = 0;
        }

        return true;
    }


} poly[maxn];

vector<Poly> vec[maxn];
bool vis[maxn];

void getPolys() {
    _for(i, 0, maxn)  vec[i].clear();
    memset(vis, 0, sizeof(vis));

    _for(i, 0, n) {
        Poly pp = poly[i];
        // enumerate posture
        _for(dir, 0, 4) {
            Poly plg = pp;

            while (true) {
                Poly plgp = plg;
                while (true) {
                    vec[i].push_back(plgp);
                    if (!plgp.Move(RIGHT)) break;
                }
                if (!plg.Move(UP)) break;
            }
            pp.rotate();
        }
    }
}

class Node {
public:
    int mat[maxn][maxn];
    void init() {
        memset(mat, 0, sizeof(mat));
    }

    bool add(const Poly &p) {
        _for(i, 0, m) _for(j, 0, m) {
                if (mat[i][j] == 0) mat[i][j] = p.mat[i][j];
                else {
                    if (p.mat[i][j] == 0) continue;
                    else if (mat[i][j] + p.mat[i][j] == 7) mat[i][j] = 1;
                    else return false;
                }
            }
        return true;
    }
} P;

bool dfs(int x, int y) {
    if (y == m) return true;
    bool ok = false;

    if (P.mat[x][y] == 1) {
        x++;
        if (x == m) {
            x = 0;
            y++;
        }
        return dfs(x, y);
    }
    for (int i = 0; i < n && !(ok); i++) {
        if (vis[i]) continue;

        for (auto u : vec[i]) {
            if (ok) break;
            Node P0 = P;

            // then try to insert
            if (P.mat[x][y] == 0 && u.mat[x][y] != 0 && P.add(u)) {
                vis[i] = true;
                if (u.mat[x][y] != 1) ok = dfs(x, y);
                else if (x == m-1) ok = dfs(0, y+1);
                else ok = dfs(x+1, y);
                vis[i] = false;
            }
            else if (P.mat[x][y] + u.mat[x][y] == 7 && P.add(u)) {
                vis[i] = true;
                if (x == m-1) ok = dfs(0, y+1);
                else ok = dfs(x+1, y);
                vis[i] = false;
            }

            P = P0;
        }
    }
    return ok;
}

int main() {
    int kase;
    scanf("%d", &kase);

    while (kase--) {
        scanf("%d%d", &n, &m);
        _for(i, 0, n) {
            scanf("%d", &poly[i].K);
            _for(j, 0, poly[i].K) {
                scanf("%lf%lf", &poly[i].a[j].x, &poly[i].a[j].y);
            }
        }

        double area = 0;
        _for(i, 0, n) {
            poly[i].normalize();
            area += poly[i].Area();
        }
        if (dcmp(area - (m * m))) {
            printf("no\n");
            continue;
        }

        P.init();
        getPolys();
        int res = dfs(0, 0);
        if (res) printf("yes\n");
        else printf("no\n");
    }
}

繁文缛节的搜索

Aizu1264

Aizu1264.jpg

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <queue>
#include <vector>
#include <stack>
#include <map>
#include <set>
#include <sstream>
#include <iomanip>
#include <cmath>
#include <bitset>
#include <assert.h>

using namespace std;
typedef long long ll;
typedef set<int>::iterator ssii;

#define Cmp(a, b) memcmp(a, b, sizeof(b))
#define Cpy(a, b) memcpy(a, b, sizeof(b))
#define Set(a, v) memset(a, v, sizeof(a))
#define debug(x) cout << #x << ": " << x << endl
#define _forS(i, l, r) for(set<int>::iterator i = (l); i != (r); i++)
#define _rep(i, l, r) for(int i = (l); i <= (r); i++)
#define _for(i, l, r) for(int i = (l); i < (r); i++)
#define _forDown(i, l, r) for(int i = (l); i >= r; i--)
#define debug_(ch, i) printf(#ch"[%d]: %d\n", i, ch[i])
#define debug_m(mp, p) printf(#mp"[%d]: %d\n", p->first, p->second)
#define debugS(str) cout << "dbg: " << str << endl;
#define debugArr(arr, x, y) _for(i, 0, x) { _for(j, 0, y) printf("%c", arr[i][j]); printf("\n"); }
#define _forPlus(i, l, d, r) for(int i = (l); i + d < (r); i++)
#define lowbit(i) (i & (-i))
#define MPR(a, b) make_pair(a, b)

pair<int, int> crack(int n) {
    int st = sqrt(n);
    int fac = n / st;
    while (n % st) {
        st += 1;
        fac = n / st;
    }

    return make_pair(st, fac);
}

inline ll qpow(ll a, int n) {
    ll ans = 1;
    for(; n; n >>= 1) {
        if(n & 1) ans *= 1ll * a;
        a *= a;
    }
    return ans;
}

template <class T>
inline bool chmax(T& a, T b) {
    if(a < b) {
        a = b;
        return true;
    }
    return false;
}

ll gcd(ll a, ll b) {
    return b == 0 ? a : gcd(b, a % b);
}

ll ksc(ll a, ll b, ll mod) {
    ll ans = 0;
    for(; b; b >>= 1) {
        if (b & 1) ans = (ans + a) % mod;
        a = (a * 2) % mod;
    }
    return ans;
}

ll ksm(ll a, ll b, ll mod) {
    ll ans = 1 % mod;
    a %= mod;

    for(; b; b >>= 1) {
        if (b & 1) ans = ksc(ans, a, mod);
        a = ksc(a, a, mod);
    }

    return ans;
}

template <class T>
inline bool chmin(T& a, T b) {
    if(a > b) {
        a = b;
        return true;
    }
    return false;
}

bool _check(int x) {
    //
    return true;
}

int bsearch1(int l, int r) {
    while (l < r) {
        int mid = (l + r) >> 1;
        if(_check(mid)) r = mid;
        else l = mid + 1;
    }
    return l;
}

int bsearch2(int l, int r) {
    while (l < r) {
        int mid = (l + r + 1) >> 1;
        if(_check(mid)) l = mid;
        else r = mid - 1;
    }
    return l;
}

template<class T>
bool lexSmaller(vector<T> a, vector<T> b) {
    int n = a.size(), m = b.size();
    int i;
    for(i = 0; i < n && i < m; i++) {
        if (a[i] < b[i]) return true;
        else if (b[i] < a[i]) return false;
    }
    return (i == n && i < m);
}

// ============================================================== //

const int inf = 100;
const int maxn = 5;
const int maxl = 15;
int mat[maxn][maxn][maxn];
int a[maxn][maxl][maxn];
int n, m, K;

void prework(int p) {
    K = 0;
    _for(x, 0, m) {
        _for(y, 0, m) a[p][K][y] = mat[p][x][y];
        K++;
    }
    _for(y, 0, m) {
        _for(x, 0, m) a[p][K][x] = mat[p][x][y];
        K++;
    }

    _for(x, 0, m) {
        a[p][K][x] = mat[p][x][x];
    }
    K++;

    _for(x, 0, m) {
        a[p][K][x] = mat[p][x][m-1-x];
    }
    K++;

    assert(K == 2*m + 2);
}

int tim[inf + 5];
bool isChose[inf + 5];
bool mark[inf << 1];

bool isBingo(int p) {
    // check card p is bingo

    // check horizontal
    _for(x, 0, m) {
        bool ok = true;
        _for(y, 0, m) if (!mark[ mat[p][x][y] ]) { ok = false; break; }
        if (ok) return true;
    }
    // check vertical
    _for(y, 0, m) {
        bool ok = true;
        _for(x, 0, m) if (!mark[ mat[p][x][y] ]) { ok = false; break; }
        if (ok) return true;
    }

    // check slash 1
    bool ok = true;
    _for(x, 0, m) if (!mark[ mat[p][x][x] ]) { ok = false; break; }
    if (ok) return true;

    // check slash 2
    ok = true;
    _for(x, 0, m) if (!mark[ mat[p][x][m-1-x] ]) { ok = false; break; }
    if (ok) return true;

    return false;
}

bool isComplete() {
    _for(i, 0, n-1) if (!isBingo(i)) return false;
    return true;
}

bool valid() {
    bool ok = true;
    for (int i = 0; i < n; i++) {
        if (isBingo(i)) {
            if (!ok) return false;
        }
        else ok = false;
    }
    return true;
}

bool vis[1<<16];
int res = inf;
inline int cal() {
    // calculate the last card
    int ans = m+1;
    _for(i, 0, K) {
        int cnt = 0;
        _for(j, 0, m) if (!mark[ a[n-1][i][j] ]) cnt++;
        chmin(ans, cnt);
    }
    return ans;
}
void dfs2(const vector<int>& arr, int cnt, int sta) {
    if (vis[sta]) return;
    vis[sta] = true;

    if (!valid()) return;
    if (isComplete()) {
        res = min(res, cnt + cal());
        //debug(res);
        return;
    }

    // then enumerate permutation of arr
    for (int i = 0; i < arr.size(); i++) {
        int x = arr[i];
        if (mark[x]) continue;

        mark[x] = true;
        dfs2(arr, cnt + 1, sta | (1<<i));
        mark[x] = false;
    }
}

void dfs(int x) {
    if (x == n-1) {
        vector<int> arr;
        for (int i = 0; i < inf; i++) {
            if (isChose[i]) { arr.push_back(i); mark[i] = false; }
        }
        _for(i, 0, 1<<(arr.size())) vis[i] = 0;
        dfs2(arr, 0, 0);
        return;
    }

    for (int i = 0; i < K; i++) {
        // enumerate bingo posture i for card x
        _for(j, 0, m) {
            int val = a[x][i][j];
            if (tim[val] == -1) {
                tim[val] = x;
                isChose[val] = true;
            }
        }

        dfs(x+1);

        _for(j, 0, m) {
            int val = a[x][i][j];
            if (tim[val] == x) {
                tim[val] = -1;
                isChose[val] = false;
            }
        }
    }
}

void init() {
    memset(a, 0, sizeof(a));
    memset(tim, -1, sizeof(tim));
    memset(isChose, 0, sizeof(isChose));
    memset(mark, 0, sizeof(mark));
    memset(vis, 0, sizeof(vis));
    K = 0;
    res = inf;
}

int main() {
    freopen("input.txt", "r", stdin);
    while (scanf("%d%d", &n, &m) == 2 && n) {
        init();

        // get data
        _for(i, 0, n) {
            _for(x, 0, m) _for(y, 0, m) scanf("%d", &mat[i][x][y]);
        }

        // prework and normalize
        _for(i, 0, n) prework(i);

        // then solve
        dfs(0);
        if (res == inf) printf("0\n");
        else printf("%d\n", res);
    }
}


新鲜事 原文

别人一天 AC 的,我花一周


新鲜事 原文

经过检验,使用这定制卷的龙猫AC杯,智商很容易爆表。之前想了好久的计算几何。后来用这个杯子冲了杯咖啡,就想到可以,格点拆分,转成矩阵运算,然后有优化的话就是线段树搞矩阵乘法。我之前想了好久都没想出来,我智商是不是变高了?
图片 图片


新鲜事 原文

用这个水杯写代码,是不是感觉智商变高了?~
图片


新鲜事 原文

如果我智商高一点,会不会 AC 得更轻松,更快?
图片 图片


新鲜事 原文

我发现我好菜



Acwing06-01.jpg
Acwing06-02.jpg

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <queue>
#include <vector>
#include <stack>
#include <map>
#include <set>
#include <sstream>
#include <iomanip>
#include <cmath>
#include <bitset>
#include <assert.h>

using namespace std;
typedef long long ll;
typedef set<int>::iterator ssii;

#define Cmp(a, b) memcmp(a, b, sizeof(b))
#define Cpy(a, b) memcpy(a, b, sizeof(b))
#define Set(a, v) memset(a, v, sizeof(a))
#define debug(x) cout << #x << ": " << x << endl
#define _forS(i, l, r) for(set<int>::iterator i = (l); i != (r); i++)
#define _rep(i, l, r) for(int i = (l); i <= (r); i++)
#define _for(i, l, r) for(int i = (l); i < (r); i++)
#define _forDown(i, l, r) for(int i = (l); i >= r; i--)
#define debug_(ch, i) printf(#ch"[%d]: %d\n", i, ch[i])
#define debug_m(mp, p) printf(#mp"[%d]: %d\n", p->first, p->second)
#define debugS(str) cout << "dbg: " << str << endl;
#define debugArr(arr, x, y) _for(i, 0, x) { _for(j, 0, y) printf("%c", arr[i][j]); printf("\n"); }
#define _forPlus(i, l, d, r) for(int i = (l); i + d < (r); i++)
#define lowbit(i) (i & (-i))
#define MPR(a, b) make_pair(a, b)

pair<int, int> crack(int n) {
    int st = sqrt(n);
    int fac = n / st;
    while (n % st) {
        st += 1;
        fac = n / st;
    }

    return make_pair(st, fac);
}

inline ll qpow(ll a, int n) {
    ll ans = 1;
    for(; n; n >>= 1) {
        if(n & 1) ans *= 1ll * a;
        a *= a;
    }
    return ans;
}

template <class T>
inline bool chmax(T& a, T b) {
    if(a < b) {
        a = b;
        return true;
    }
    return false;
}

ll gcd(ll a, ll b) {
    return b == 0 ? a : gcd(b, a % b);
}

ll ksc(ll a, ll b, ll mod) {
    ll ans = 0;
    for(; b; b >>= 1) {
        if (b & 1) ans = (ans + a) % mod;
        a = (a * 2) % mod;
    }
    return ans;
}

ll ksm(ll a, ll b, ll mod) {
    ll ans = 1 % mod;
    a %= mod;

    for(; b; b >>= 1) {
        if (b & 1) ans = ksc(ans, a, mod);
        a = ksc(a, a, mod);
    }

    return ans;
}

template <class T>
inline bool chmin(T& a, T b) {
    if(a > b) {
        a = b;
        return true;
    }
    return false;
}

bool _check(int x) {
    //
    return true;
}

int bsearch1(int l, int r) {
    while (l < r) {
        int mid = (l + r) >> 1;
        if(_check(mid)) r = mid;
        else l = mid + 1;
    }
    return l;
}

int bsearch2(int l, int r) {
    while (l < r) {
        int mid = (l + r + 1) >> 1;
        if(_check(mid)) l = mid;
        else r = mid - 1;
    }
    return l;
}

template<class T>
bool lexSmaller(vector<T> a, vector<T> b) {
    int n = a.size(), m = b.size();
    int i;
    for(i = 0; i < n && i < m; i++) {
        if (a[i] < b[i]) return true;
        else if (b[i] < a[i]) return false;
    }
    return (i == n && i < m);
}

// ============================================================== //

const int maxn = 20000 + 10;
int f[maxn], g[maxn], que[maxn];
int v[maxn], w[maxn], s[maxn];
int n, V;

void init() {
    memset(f, 0, sizeof(f));
    memset(g, 0, sizeof(g));
    memset(que, 0, sizeof(que));
}

void dp() {
    _for(i, 0, n) {
        memcpy(g, f, sizeof(f));
        _for(u, 0, v[i]) {
            int hh = 1, tt = 0;
            for (int k = u; k <= V; k += v[i]) {
                while (hh <= tt && que[hh] < k - s[i]*v[i]) hh++;
                if (hh <= tt) f[k] = max(g[k], g[que[hh]] + (k - que[hh]) / v[i] * w[i]);
                while (hh <= tt && g[k] >= g[que[tt]] + (k - que[tt]) / v[i] * w[i]) tt--;
                que[++tt] = k;
            }
        }
    }
    printf("%d\n", f[V]);
}

int main() {
    freopen("input.txt", "r", stdin);
    scanf("%d%d", &n, &V);
    init();

    // get data
    _for (i, 0, n) scanf("%d%d%d", &v[i], &w[i], &s[i]);

    // dp
    dp();
}