都是雅礼2017集训的题

Day1

T1 决斗

有结论：存在至少一个位置 $k$ 满足对于任意的顺序都满足没有精灵从第 $k$ 个精灵旁走到第 $k+1$ 个精灵旁。

证明：定义 $R_i$ 为一开始分配的侏儒对手编号小于或等于 $i$ 的精灵个数,并定义 $P_i =R_i-i$ 。 $P_n =0$
永远成立。不妨设位置 $m$ 满足 $P_m$ 是所有 $P_i$ 里面最小的,可以证明永远不会有精灵从位置 $m$ 走到位置 $m+1$ 。假设存在一个精灵从位置 $m$ 走到位置 $m+1$ ,意味着存在一个序列 $a, a+1,a+2,...,m-1,m$ 满足初始侏儒对手在这个区间的精灵数大于这些位置的数量。而初始侏儒对手在这个区间的精灵数减去这些位置的数量的差等于 $P_m -P_a$ 。而由于 $P_ m$ 是所有 $P_i$ 中最小的,所有 $P_m -P_a >0$ 永远无法成立,推出矛盾。

所以只需要从位置 $k$ 处把环断开，接下来就可以贪心地处理，每次从集合中选择力量值刚好大于当前侏儒的精灵，不存在则选择最小的。

需要一个支持插入一个数、删除一个数、查询集合内比 x 大的最小的数的数据结构，std::set 即可。

//#pragma GCC diagnostic error "-std=c++11"
//#pragma Gcc optimize(2)
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cstdarg>
#include<typeinfo>
#include<vector>
#include<set>
#define debug(x) cerr << #x << " = " << x << endl
#define debugf(...) fprintf(stderr, __VA_ARGS__)
using namespace std;
template <class T> bool mvmax(T &a, T b) {return b > a ? (a = b, 1) : 0;}
template <class T> bool mvmin(T &a, T b) {return b < a ? (a = b, 1) : 0;}
void read(char *s) {scanf("%s", s);} void read(char &c) {scanf("%c", &c);}
template <class T> void read(T &a) {
    a = 0; char c = getchar(); int f = 0;
    while (!isdigit(c)) { f ^= c == '-',  c = getchar(); }
    while (isdigit(c)) { a = a * 10 + (c ^ 48),  c = getchar(); }
    a *= f ? -1 : 1;
}
struct Fastin {
    template <class T> Fastin& operator >> (T &x) {read(x); return *this;}
} fastin;

const int MAXN = 1e5 + 10;

vector <int> input[MAXN];
set <int> buf;

int n;
int a[MAXN], p[MAXN], v[MAXN], cnt[MAXN];
int f[MAXN], g[MAXN], ming, m, ans;

int main() {
    debugf("compiled on [%s]\n", __TIME__);
    fastin >> n;
    for (int i = 1; i <= n; i++) {
        fastin >> a[i];
        input[a[i]].push_back(i);
    }
    for (int i = 1; i <= n; i++) {
        fastin >> p[i];
    }
    for (int i = 1; i <= n; i++) {
        fastin >> v[i];
    }
    for (int i = 1; i <= n; i++) {
        f[i] = f[i - 1] + input[i].size();
        g[i] = f[i] - i;
        if (mvmin(ming, g[i])) {
            m = i;
        }
    }
    for (int k = m + 1; k <= n + m; k++) {
        int i = (k - 1) % n + 1;
        for (int j = 0, siz = input[i].size(); j < siz; j++) {
            buf.insert(v[input[i][j]]);
        }
        set <int> :: iterator it = buf.lower_bound(p[i]);
        ans++;
        if (it == buf.end()) {
            it = buf.lower_bound(0);
            ans--;
        }
        buf.erase(it);
    }
    printf("%d\n", ans);
    return 0;
}

T2 数列

要计算题目所述的最长严格上升子序列,我们必须对于所有位置 $X$ 计算以 $X$ 起始的最长上升子序列和以 $X$ 起始的最长下降子序列,以及各自所对应的方案数。用树状数组可以在 $O(NlogN)$ 的时间复杂度内计算上述的最长上升/下降子序列的长度以及方案数。
可以注意到,最终的答案是由原来的一个严格上升子序列和一个严格下降子序列共同组成的结果。假设 $A$ 是以 $X$ (包含 $X$ )起始的最长严格上升子序列的长度, $B$ 是以 $X$ 为(包含 $X$ )起始的最长下降子序列的长度,且方案数分别为 $num_A$ 和 $num_b$ 。可以得到用 $X$ 右边的数(包含 $X$ )组合出来的数列的最长严格上升子序列长度为 $A+B-1$ ,且方案数为 $num_A\times num_b$ 。最终要求的最长严格上升子序列的长度只需要在所有位置求出的最长上升子序列长度中取一个最大值,不妨设其为 $R$ 。不难想到,对于每个位置计算出来的方案数,还需要乘 $2^{(N-R)}$ 。因为在最长严格上升子序列中的 $R$ 个元素以外的元素可以任意放在左边或右边。
总的时间复杂度为 $O(NlogN)$ 。

//Author: ycp
//#pragma GCC diagnostic error "-std=c++11"
//#pragma Gcc optimize(2)
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cstdarg>
#include<typeinfo>
#include<utility>
#define debug(x) cerr << #x << " = " << x << endl
//#define debugf(...) fprintf(stderr, __VA_ARGS__)
#define debugf(...)
using namespace std;
template <class T> bool mvmax(T &a, T b) {return b > a ? (a = b, 1) : 0;}
template <class T> bool mvmin(T &a, T b) {return b < a ? (a = b, 1) : 0;}
void read(char *s) {scanf("%s", s);} void read(char &c) {scanf("%c", &c);}
template <class T> void read(T &a) {
    a = 0; char c = getchar(); int f = 0;
    while (!isdigit(c)) { f ^= c == '-',  c = getchar(); }
    while (isdigit(c)) { a = a * 10 + (c ^ 48),  c = getchar(); }
    a *= f ? -1 : 1;
}
struct Fastin {
    template <class T> Fastin& operator >> (T &x) {read(x); return *this;}
} fastin;

#define int long long

const int MAXN = 2e5 + 10;
const int mod = 1e9 + 7;

int pow2[MAXN], a[MAXN], b[MAXN], tot;
int n;

class Binary_indexed_tree {
    int cnt[MAXN], val[MAXN];
    public:
    void insert(int pos, int upd_val, int upd_cnt) {
        for (int i = pos; i <= tot + 5; i += (i & (-i))) {
            if (val[i] < upd_val) {
                val[i] = upd_val;
                cnt[i] = upd_cnt;
            } else if (val[i] == upd_val) {
                (cnt[i] += upd_cnt) %= mod;
            }
        }
    }
    pair <int, int> query(int pos) {
        int res_val = 0, res_cnt = 1;
        for (int i = pos; i; i -= (i & (-i))) {
            if (val[i] > res_val) {
                res_val = val[i];
                res_cnt = cnt[i];
            } else if (val[i] == res_val) {
                (res_cnt += cnt[i]) %= mod;
            }
        }
        return make_pair(res_val, res_cnt);
    }
} t1, t2;

int ans_len, ans_cnt;

signed main() {
    debugf("compiled on [%s]\n", __TIME__);
    fastin >> n;
    for (int i = 1; i <= n; i++) {
        fastin >> a[i];
        b[i] = a[i];
    }
    sort(b + 1, b + n + 1);
    tot = unique(b + 1, b + n + 1) - b - 1;
    for (int i = 1; i <= n; i++) {
        a[i] = lower_bound(b + 1, b + tot + 1, a[i]) - b;
    }
    pow2[0] = 1;
    for (int i = 1; i <= n; i++) {
        pow2[i] = (pow2[i - 1] << 1) % mod;
    }
    for (int i = n; i >= 1; i--) {
        debugf("t1.query(%lld)\n", a[i] - 1);
        pair <int, int> res1 = t1.query(a[i] - 1);
        debugf("t2.query(%lld)\n", tot - a[i] + 1);
        pair <int, int> res2 = t2.query(tot - a[i] + 1);
        debugf("id = %lld, res1 = <%lld, %lld>, res2 = <%lld, %lld>\n", i, res1.first, res1.second, res2.first, res2.second);
        res1.first += 1, res2.first += 1;
        int len = res1.first + res2.first - 1;
        int cnt = res1.second * res2.second % mod;
        if (len == ans_len) {
            (ans_cnt += pow2[n - len] * cnt % mod) %= mod;
        } else if (len > ans_len) {
            ans_cnt = pow2[n - len] * cnt % mod;
            ans_len = len;
        }
        debugf("t1.insert(%lld, %lld, %lld)\n", a[i], res1.first, res1.second);
        t1.insert(a[i], res1.first, res1.second);
        debugf("t2.insert(%lld, %lld, %lld)\n", tot - a[i] + 2, res2.first, res2.second);
        t2.insert(tot - a[i] + 2, res2.first, res2.second);
    }
    cout << ans_len << " "<< ans_cnt << endl;
    return 0;
}

T3 拍苍蝇

问题可以被分解成两个较简单的问题:

对于给定的多边形,找到所有在多边形内部以及边上的整点。
对于每一个可能的多边形位置,判断是否有一个苍蝇所在位置等于多
边形内部一个整点的位置。

对于第一个问题，我们可以枚举横坐标 $x$ ，逐一判断不同的边与 $x$ 的交点，细节较多（比方说线段端点直接在 $x$ 上的问题），可以看代码

对于第二个问题，用 std::bitset 即可维护。

//author: ycp | https://ycpedef.github.io
//#pragma GCC diagnostic error "-std=c++11"
//#pragma Gcc optimize(2)
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cstdarg>
#include<bitset>
#include<vector>
#include<typeinfo>
#define debug(x) cerr << #x << " = " << x << endl
#define debugf(...) //fprintf(stderr, __VA_ARGS__)
using namespace std;
template <class T> bool cmax(T &a, T b) {return b > a ? (a = b, 1) : 0;}
template <class T> bool cmin(T &a, T b) {return b < a ? (a = b, 1) : 0;}
void read(char *s) {scanf("%s", s);} void read(char &c) {scanf("%c", &c);}
template <class T> void read(T &a) {
    a = 0; char c = getchar(); int f = 0;
    while (!isdigit(c)) { f ^= c == '-',  c = getchar(); }
    while (isdigit(c)) { a = a * 10 + (c ^ 48),  c = getchar(); }
    a *= f ? -1 : 1;
}
struct Fastin {
    template <class T> Fastin& operator >> (T &x) {read(x); return *this;}
} fastin;

const int MAXN = 510;
//const int MAXN = 10;

struct Point {
    int x, y;
} p[MAXN * 1000];

int n, m, k, q, maxx, maxy, minx, miny;
bitset <MAXN> graph[MAXN], fly[MAXN];
int ans[MAXN][MAXN];

int main() {
    fastin >> n >> m >> q;
    for (int i = 1, x, y; i <= q; i++) {
        fastin >> x >> y;
        fly[x][y] = 1;
    }
    fastin >> k;
    maxx = 0x80808080, maxy = 0x80808080, minx = 0x3f3f3f3f, miny = 0x3f3f3f3f;
    for (int i = 1; i <= k; i++) {
        fastin >> p[i].x >> p[i].y;
        cmax(maxx, p[i].x); cmin(minx, p[i].x);
        cmax(maxy, p[i].y); cmin(miny, p[i].y);
    }
    maxx -= minx, maxy -= miny;
    for (int i = 1; i <= k; i++) {
        p[i].x -= minx, p[i].y -= miny;
        graph[p[i].x][p[i].y] = 1;
        //debugf("p[%d] = <%d, %d>\n", i, p[i].x, p[i].y);
    }
    //for (int i = 0; i <= maxx; i++) {
        //debugf("graph[%d] = ", i);
        //cerr << graph[i] << endl;
    //}
    //debugf("----------------\n");
    for (int x = 0; x <= maxx; x++) {
        vector <double> bpt;
        for (int l = 1; l <= k; l++) {
            int a = l, b = l % k + 1;
            if (p[a].y > p[b].y) swap(a, b);
            if ((p[a].x < x && p[b].x < x) || (p[a].x > x && p[b].x > x)) continue;
            if ((p[a].x == x && p[b].x > x) || (p[a].x > x && p[b].x == x)) continue;
            if (p[a].x == x && p[b].x == x) {
                for (int y = p[a].y; y <= p[b].y; y++) {
                    graph[x][y] = 1;
                }
                continue;
            }
            double k = (double)(p[b].y - p[a].y) / (p[b].x - p[a].x);
            bpt.push_back(p[a].y + k * (x - p[a].x));
        }
        sort(bpt.begin(), bpt.end());
        int siz = bpt.size();
        for (int y = 0, i = 0, flag = 0; y <= maxy; y++) {
            while (i < siz && bpt[i] < y) i++, flag ^= 1;
            if (flag || (i < siz && bpt[i] == y)) {
                graph[x][y] = 1;
            }
        }
        //debugf("graph[%d] = ", x);
        //cerr << graph[x] << endl;
    }
    bitset <MAXN> cur;
    for (int i = 0; i <= n - maxx; i++) {
        for (int j = 0; j <= m - maxy; j++) {
            ans[i][j] = 1;
            for (int x = i; x <= i + maxx; x++) {
                cur = graph[x - i] << j;
                if ((cur & fly[x]).any()) {
                    ans[i][j] = 0;
                    break;
                }
            }
        }
    }
    int res = 0;
    for (int i = 0; i <= n - maxx; i++) {
        for (int j = 0; j <= m - maxy; j++) {
            res += ans[i][j];
        }
    }
    printf("%d\n", res);
    return 0;
}

Day2

T1 市场

考虑势能分析，令区间 $[l,r]$ 的势能为 $max-min$ ，则每次修改操作 1 最多改变 $O(\log n)$ 个区间的势能，操作 2 会使势能变为原来的 $\lfloor1/2\rfloor$ ，不需要修改几次就可以变为区间加法或者区间赋值运算。

复杂度 $O(n\log^2n)$

//author: ycp | https://ycpedef.github.io
//#pragma GCC diagnostic error "-std=c++11"
//#pragma Gcc optimize(2)
#include <algorithm>
#include <cmath>
#include <cstdarg>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <typeinfo>
#define debug(x) cerr << #x << " = " << x << endl
#define debugf(...) fprintf(stderr, __VA_ARGS__)
template <class T>
bool cmax(T& a, T b) { return b > a ? (a = b, 1) : 0; }
template <class T>
bool cmin(T& a, T b) { return b < a ? (a = b, 1) : 0; }
void read(char* s) { scanf("%s", s); }
void read(char& c) { scanf("%c", &c); }
template <class T>
void read(T& a) {
    a = 0;
    char c = getchar();
    int f = 0;
    while (!isdigit(c)) { f ^= c == '-', c = getchar(); }
    while (isdigit(c)) { a = a * 10 + (c ^ 48), c = getchar(); }
    a *= f ? -1 : 1;
}
struct Fastin {
    template <class T>
    Fastin& operator>>(T& x) {
        read(x);
        return *this;
    }
} fastin;
using namespace std;

#define int long long
const int MAXN = 2e6 + 10;
const int inf = 0x3f3f3f3f3f3f3f3f;

struct Segment {
    int val;
    int minv;
    int maxv;
    int tag;
    int fil;
    Segment() {
        val = 0;
        minv = inf;
        maxv = -inf;
        tag = 0;
        fil = 0;
    }
} t[MAXN];

int a[MAXN], n, q;

#define ls ((p) << 1)
#define rs (((p) << 1) | 1)
#define mid ((l + r) >> 1)
#define val(p) t[p].val
#define tag(p) t[p].tag
#define minv(p) t[p].minv
#define maxv(p) t[p].maxv
#define fil(p) t[p].fil

void pushup(int p) {
    val(p) = val(ls) + val(rs);
    minv(p) = min(minv(ls), minv(rs));
    maxv(p) = max(maxv(ls), maxv(rs));
}

void fill(int p, int l, int r, int v) {
    //debugf("fill #%lld: [%lld, %lld] => %lld\n", p, l, r, v);
    minv(p) = maxv(p) = fil(p) = v;
    tag(p) = 0;
    val(p) = (r - l + 1) * v;
}

inline void add(int p, int l, int r, int v) {
    tag(p) += v;
    val(p) += v * (r - l + 1);
    minv(p) += v;
    maxv(p) += v;
}

void pushdown(int p, int l, int r) {
    if (fil(p) != inf) {
        fill(ls, l, mid, fil(p));
        fill(rs, mid + 1, r, fil(p));
        fil(p) = inf;
    }
    if (tag(p)) {
        //debugf("pushdown #%lld, @%lld, @%lld: fil = %lld, inf = %lld\n", p, l, r, fil(p), inf);
        add(ls, l, mid, tag(p));
        add(rs, mid + 1, r, tag(p));
        tag(p) = 0;
        //debugf("fuck pushdown #%lld, @%lld, @%lld: fil = %lld, inf = %lld\n", p, l, r, fil(p), inf);
    }
}

void build_tree(int p, int l, int r) {
    fil(p) = inf;
    if (l == r) {
        val(p) = a[l];
        minv(p) = a[l];
        maxv(p) = a[l];
    } else {
        build_tree(ls, l, mid);
        build_tree(rs, mid + 1, r);
        pushup(p);
    }
}

void modify(int, int, int, int, int, int);

void div(int p, int l, int r, int x, int y, int c) {
    //debugf("div in (#%lld, @%lld, @%lld)\n", p, l, r);
    //if (l == r) {
    //    val(p) = (int)floor(1.0 * val(p) / c);
    //    minv(p) = val(p);
    //    maxv(p) = val(p);
    //    return;
    //}
    if (x <= l && r <= y) {
        int delta_min = (int)(floor(1.0 * minv(p) / c)) - minv(p);
        int delta_max = (int)(floor(1.0 * maxv(p) / c)) - maxv(p);
        if (delta_min == delta_max) {
//            debugf("shit c = %lld, %lld/%lld, %lld/%lld\n", c, minv(p), maxv(p), delta_min, delta_max);
            modify(p, l, r, l, r, delta_min);
            //debugf("delta $maxv = %lld, $minv = %lld, $delta = %lld\n", maxv(p), minv(p), delta_min);
            return;
        }
        if (minv(p) + delta_min == maxv(p) + delta_max) {
            //debugf("value skiped $val = %lld\n", minv(p) + delta_min);
            //        if (delta_min == 0);
            //            debugf("fuck c = %lld, %lld/%lld, %lld/%lld\n", c, minv(p), maxv(p), delta_min, delta_max);
            fill(p, l, r, minv(p) + delta_min);
            //debugf("FUCK fil(%lld)\n", fil(p));
            return;
        }
    }
    pushdown(p, l, r);
    if (mid >= x)
        div(ls, l, mid, x, y, c);
    if (mid < y)
        div(rs, mid + 1, r, x, y, c);
    pushup(p);
}

void modify(int p, int l, int r, int x, int y, int c) {
    if (x <= l && r <= y) {
        add(p, l, r, c);
        return;
    }
    pushdown(p, l, r);
    if (mid >= x)
        modify(ls, l, mid, x, y, c);
    if (mid < y)
        modify(rs, mid + 1, r, x, y, c);
    pushup(p);
}

int query_sum(int p, int l, int r, int x, int y) {
    pushdown(p, l, r);
    if (x <= l && r <= y) {
        return val(p);
    }
    int res = 0;
    if (mid >= x)
        res += query_sum(ls, l, mid, x, y);
    if (mid < y)
        res += query_sum(rs, mid + 1, r, x, y);
    return res;
}

int query_min(int p, int l, int r, int x, int y) {
    pushdown(p, l, r);
    if (x <= l && r <= y) {
        return minv(p);
    }
    int res = inf;
    if (mid >= x)
        cmin(res, query_min(ls, l, mid, x, y));
    if (mid < y)
        cmin(res, query_min(rs, mid + 1, r, x, y));
    return res;
}

void print_tree(int p, int l, int r) {
    debugf("#%lld\t[%lld, %lld]: ", p, l, r);
    debugf("%lld / %lld, sum %lld, tag %lld, fil %s\n", minv(p), maxv(p), val(p), tag(p), fil(p) == inf ? "inf" : to_string(fil(p)).c_str());
    //pushdown(p, l, r);
    if (l != r)
        print_tree(ls, l, mid), print_tree(rs, mid + 1, r);
}

void print_array(int p, int l, int r) {
    if (l == r) return;
    pushdown(p, l, r);
    print_array(ls, l, mid);
    print_array(rs, mid + 1, r);
}

#undef ls
#undef rs
#undef mid
#undef val
#undef tag
#undef minv

signed main() {
    fastin >> n >> q;
    for (int i = 1; i <= n; i++) {
        fastin >> a[i];
    }
    build_tree(1, 1, n);
    for (int i = 1, op, x, y, c; i <= q; i++) {
        fastin >> op;
        switch (op) {
            case 1:
                fastin >> x >> y >> c;
                x++, y++;
                debugf("---- modifing (%lld, %lld, +%lld) ----\n", x, y, c);
                modify(1, 1, n, x, y, c);
                print_tree(1, 1, n);
                //print_array(1, 1, n); //debugf("\n");
                //                debugf("%lld\n", query_sum(1, 1, n, 655, 659));
                break;
            case 2:
                fastin >> x >> y >> c;
                x++, y++;
                debugf("---- diving (%lld, %lld, %lld) ----\n", x, y, c);
                div(1, 1, n, x, y, c);
                print_tree(1, 1, n);
                //print_array(1, 1, n), //debugf("\n");
                //                debugf("%lld\n", query_sum(1, 1, n, 655, 659));
                break;
            case 3:
                fastin >> x >> y;
                x++, y++;
                debugf("---- min (%lld, %lld) ----\n", x, y);
                printf("%lld\n", query_min(1, 1, n, x, y));
                print_tree(1, 1, n);
                break;
            case 4:
                fastin >> x >> y;
                x++, y++;
                debugf("---- sum (%lld, %lld) ----\n", x, y);
                printf("%lld\n", query_sum(1, 1, n, x, y));
                print_tree(1, 1, n);
                break;
        }
    }
    return 0;
}

T2 matrix

设初始状态含有白格子的列的数量为 $c$ ,设 $k$ 表示最少的操作次数使得某一行的所有格子变成黑色,那么在 $k$ 次操作之前,每一行都是不全为黑的,所以每次操作不会减少 $c$ ,而且为了步数最少, $c$ 肯定也不会增加,因此我们只要找到 $k$ ,那么答案就是 $k + c$ 。
考虑枚举全黑的那一行 $r$ , 设 $x$ 表示这一行白格子数量:

如果列 $r$ 有黑格子,那么最少次数为 $x$ ,只要把列 $r$ 有黑格子的那一行对每个白格子
所在列进行操作即可。
如果没有,我们需要用一次操作来让这一列含有黑格子,所以要 $x + 1$ 步。

复杂度 $O(n^2)$

//author: ycp | https://ycpedef.github.io
//#pragma GCC diagnostic error "-std=c++11"
//#pragma Gcc optimize(2)
#include <algorithm>
#include <cstdarg>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <typeinfo>
#define debug(x) cerr << #x << " = " << x << endl
#define debugf(...)  //fprintf(stderr, __VA_ARGS__)
using namespace std;
template <class T>
bool cmax(T& a, T b) { return b > a ? (a = b, 1) : 0; }
template <class T>
bool cmin(T& a, T b) { return b < a ? (a = b, 1) : 0; }
void read(char* s) { scanf("%s", s); }
void read(char& c) { scanf("%c", &c); }
template <class T>
void read(T& a) {
    a = 0;
    char c = getchar();
    int f = 0;
    while (!isdigit(c)) { f ^= c == '-', c = getchar(); }
    while (isdigit(c)) { a = a * 10 + (c ^ 48), c = getchar(); }
    a *= f ? -1 : 1;
}
struct Fastin {
    template <class T>
    Fastin& operator>>(T& x) {
        read(x);
        return *this;
    }
    template <class T>
    Fastin& operator>>(T* x) {
        read(x);
        return *this;
    }
} fastin;

const int MAXN = 1010;
const int inf = 0x3f3f3f3f;
int n, c, _flag;
char s[MAXN][MAXN];

int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        scanf("%s", s[i]);
        int f = 1;
        for (int j = 0, v; v = (s[i][j] == '#'), j < n; j++) _flag |= v, f &= v;
        if (!f) c++;
    }
    if (!_flag) {
        return puts("-1"), 0;
    }
    debugf("c = %d\n", c);
    int ans = inf;
    for (int i = 0; i < n; i++) {
        int k = 0;
        for (int j = 0; j < n; j++) k += (s[i][j] == '.');
        debugf("i = %d, k = %d\n", i, k);
        if (s[i][i] == '#')
            cmin(ans, c + k);
        else {
            debugf("failed\n");
            int flag = 0;
            for (int j = 0; j < n; j++) {
                if (s[j][i] == '#') {
                    flag = 1;
                }
            }
            if (flag)
                cmin(ans, c + k);
            else
                cmin(ans, c + k + 1);
        }
    }
    //    printf("%d\n", ans);
    printf("%d\n", ans);
    return 0;
}

T3 string

考虑当 $k > \sqrt m$ 时, $q \le\sqrt m$ ,因此每个询问我们对 $i \in [a, b]$ 查询 $w[l_i , r_i ]$ 在 $s$ 中出现次数, 用 SAM 可以做到单次 $O(k + m \cdot \log n)$ 。

考虑当 $k \le \sqrt m$ 时, $\sum k^2 \le m^{3/2}$ ,因此 $O(k^2)$ 枚举 $w$ 的所有子串,对每个子串 $w[l, r]$ 查询

出现次数以及询问次数,乘起来即可,单次 $O(k^2\log n)$ 。

总复杂度O(m\sqrt m \log n)。

Cauphenuny's blog

20210109~10 考试总结