2019-2020 ICPC Latin American Regional

A - Algorithm Teaching

\(n\ (1\le n\le 10^3)\) 个老师，第 \(i\) 个老师会 \(m_i\ (1\le m_i\le 10)\) 个科目：\(s_{i,1},s_{i,2},\cdots,s_{i,m_i}\)。

每个学生只可以从一个老师那里学会老师会的科目的一个子集，两个学生可以合作当且仅当会的集合互不包含。

问最多能找出来多少个学生，使得两两都可以合作。

求包含关系的最长反链，由 dilworth 定理就是求最小链覆盖。

每个老师对应 \(2^{m_i}-1\) 个集合，\(3^{m_i}\) 个包含关系。最多一共 \(102300\) 个不同的集合，\(5904900\) 条边。

包含关系天然的是传递闭包，因此直接跑最小路径覆盖复杂度 \(\mathcal{O}(m\sqrt n)\) 约 \(10^9\) ，Hopcroft 常数很小（只跑了217ms）。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

#define fr            first
#define sc            second
#define pb            push_back
#define mp            make_pair
#define mt            make_tuple
#define pii           pair<int, int>
#define tiii          tuple<long, long, long>
#define all(s)        (s).begin(), (s).end()
#define lowbit(x)     ((x) & -(x))
#define rep(i, x, y)  for (int (i) = (x); (i) <= (y); ++(i))
#define per(i, x, y)  for (int (i) = (x); (i) >= (y); --(i))

inline bool getmin(int &a, int b) {return (a > b ? (a = b, true) : false);}
inline bool getmax(int &a, int b) {return (a < b ? (a = b, true) : false);}

const int N   = 110007;
const int inf = 1000000000;

namespace Hopcroft_Karp {

    bool vis[N];
    vector<int> e[N];
    int nl, nr, ml[N], mr[N], dl[N], dr[N]; // m for match, d for distance
    
    inline bool bfs() {
        static int q[N], hd, tl; hd = 1; tl = 0;
        memset(dl, -1, sizeof(int) * (nl + 1));
        memset(dr, -1, sizeof(int) * (nr + 1));
        for (int i = 1; i <= nl; ++i) if (!ml[i]) {dl[i] = 0; q[++tl] = i;}
        int dT = inf;
        while (hd <= tl) {
            int u = q[hd++];
            if (dl[u] >= dT) break;
            for (auto v : e[u])
                if (dr[v] == -1) {
                    dr[v] = dl[u] + 1;
                    if (!mr[v]) getmin(dT, dr[v] + 1);
                    else {dl[mr[v]] = dr[v] + 1; q[++tl] = mr[v];}
                }
        }
        return dT != inf;
    }

    bool dfs(int u) {
        for (auto v : e[u]) {
            if (vis[v] || dl[u] + 1 != dr[v]) continue;
            vis[v] = true;
            if (!mr[v] || dfs(mr[v])) {mr[v] = u; ml[u] = v; return true;}
        }
        return false;
    }

    inline void add(int u, int v) {e[u].push_back(v);}

    inline int max_matching() {
        int ans = 0;
        while(bfs()) {
            memset(vis, 0, sizeof(bool) * (nr + 1));
            for (int i = 1; i <= nl; ++i) if (!ml[i]) ans += dfs(i);
        }
        return ans;
    }
}

int tot, cnts;

bool vis[N];

unordered_map<string, int> tr;

map<vector<int>, int> id;

int main() {
    int n; cin >> n;
    for (int i = 1; i <= n; ++i) { 
        int k; cin >> k;
        vector<int> course(k);
        for (int j = 0; j < k; ++j) {
            string str;
            cin >> str;
            if (!tr[str]) tr[str] = ++cnts;
            course[j] = tr[str];
        }
        sort(all(course));
        vector<int> subset(1 << k);
        for (int S = 1; S < (1 << k); ++S) {
            vector<int> tmp(__builtin_popcount(S));
            for (int j = 0, tmpcnt = 0; j < k; ++j)
                if (S & (1 << j)) tmp[tmpcnt++] = course[j];
            if (!id[tmp]) id[tmp] = ++tot;
            subset[S] = id[tmp];
        }
        for (int S = 1; S < (1 << k); ++S) {
            int nwid = subset[S];
            if (vis[nwid]) continue;
            vis[nwid] = true;
            for (int s = (S & (S - 1)); s; s = (S & (s - 1))) Hopcroft_Karp::add(nwid, subset[s]);
        }  
    }
    Hopcroft_Karp::nl = Hopcroft_Karp::nr = tot;
    printf("%d\n", tot - Hopcroft_Karp::max_matching());
    return 0;
}

*C - Cut Inequality Down

一共 \(n\ (1\le n\le 10^5)\) 个月，第 \(i\) 个月的收入固定是 \(a_i\ (-10^6\le a_i\le 10^6)\) 元。

限制钱数任何时刻都必须在 \([L,R]\) 内，如果一个月收入之后超过了边界就把钱数改为对应边界。

\(Q\ (1\le Q\le 10^5)\) 次询问：如果从第 \(a\) 天开始的时候有 \(w\) 元钱，那么第 \(b\) 天的时候有多少钱？

如果没有碰过边界，答案就是 \(w+sum[b] - sum[a - 1]\) 。

如果碰过边界，答案就是 最后一次碰的边界值 + 剩下的一段收入和 。

如何求最后一次碰的边界的位置呢？

首先我们可以 \(O(1)\) 判断给定区间和初始钱数，区间内是否碰过边界：

预处理前缀和的区间 \(\max,\min\) 的 ST 表，查区间内收入最多/最低时刻，与边界比较即可。

那么可以用上述方法套一个二分 \(\mathcal{O}(\log n)\) 求出最近的触碰边界时刻。

就可以预处理倍增 nxt[i][t][0/1] 表示当前在 \(i\) ，当前钱数是上/下边界，往后 \(2^t\) 次触及边界的位置和对应是上/下边界。

每次询问先二分一次到边界，然后用倍增跳，最后一段直接用前缀和，总复杂度 \(\mathcal{O}(n\log n+ Q\log n)\)。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

inline int rd() {
    int x = 0; 
    bool f = 0; 
    char c = getchar();
    for (; !isdigit(c); c = getchar()) f |= (c == '-');
    for (; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);
    return f ? -x : x;
}

#define fr        first
#define sc        second
#define mp        make_pair
#define pb        push_back
#define pii       pair<int, int>
#define all(s)    (s).begin(), (s).end()
#define lowbit(x) ((x) & -(x))

#define N 100007

int n, L, R, a[N], lg[N];

ll mx[N][18], mn[N][18], pre[N];

inline ll qmx(int l, int r) {
    int t = lg[r - l + 1];
    return max(mx[l][t], mx[r - (1 << t) + 1][t]);
}

inline ll qmn(int l, int r) {
    int t = lg[r - l + 1];
    return min(mn[l][t], mn[r - (1 << t) + 1][t]);
}

pair<int, bool> nxt[N][18][2];

pair<int, bool> getnxt(int nw, int w) {
    auto check = [&](int p) {
        if (w + qmx(nw, p) - pre[nw - 1] > R) return true;
        if (w + qmn(nw, p) - pre[nw - 1] < L) return true;
        return false;
    };
    if (!check(n)) return mp(n + 1, 0);
    int l = nw, r = n;
    while (l < r) {
        int mid = (l + r) >> 1;
        check(mid) ? r = mid : l = mid + 1;
    }
    return mp(l, w + qmx(nw, l) - pre[nw - 1] > R);
}

int main() {
    for (int t = 0; (1 << t) < N; ++t) lg[1 << t] = t;
    for (int i = 1; i < N; ++i) if (!lg[i]) lg[i] = lg[i - 1];
    n = rd(); L = rd(); R = rd();
    for (int i = 1; i <= n; ++i) {
        a[i] = rd(); 
        pre[i] = pre[i - 1] + a[i];
        mx[i][0] = mn[i][0] = pre[i];
    }
    for (int t = 1; t <= lg[n]; ++t)
        for (int i = 1; i <= n - (1 << t) + 1; ++i) {
            mx[i][t] = max(mx[i][t - 1], mx[i + (1 << (t - 1))][t - 1]);
            mn[i][t] = min(mn[i][t - 1], mn[i + (1 << (t - 1))][t - 1]);
        }
    memset(nxt, 0x3f, sizeof(nxt));
    for (int i = 1; i <= n; ++i) {
        nxt[i][0][0] = getnxt(i, L);
        nxt[i][0][1] = getnxt(i, R);
    }
    for (int t = 1; t <= lg[n]; ++t) 
        for (int i = 1; i <= n; ++i) {
            if (nxt[i][t - 1][0].fr <= n) nxt[i][t][0] = nxt[nxt[i][t - 1][0].fr + 1][t - 1][nxt[i][t - 1][0].sc];  
            if (nxt[i][t - 1][1].fr <= n) nxt[i][t][1] = nxt[nxt[i][t - 1][1].fr + 1][t - 1][nxt[i][t - 1][1].sc];
        }
    for (int q = rd(); q; --q) {
        int l = rd(), r = rd(), w = rd();
        auto [p, fl] = getnxt(l, w);
        if (p > r) {
            printf("%lld\n", w + pre[r] - pre[l - 1]);
            continue;
        }
        for (int i = lg[n]; ~i; --i)
            if (nxt[p][i][fl].fr <= r) {
                auto [nxp, nxfl] = nxt[p][i][fl];
                p = nxp + 1; fl = nxfl;
            }
        printf("%lld\n", (fl ? R : L) + pre[r] - pre[p - 1]);
    }
    return 0;
}

D - Dazzling Stars

给定二维平面上 \(n\ (1\le n\le 10^3)\) 个点的坐标 \((x_i,y_i)\) 和权值 \(w_i\) 。

问是否能将所有点整体旋转一个角度，使得：若 \(w_A>w_B\) ，那么 \(y_A\ge y_B\) 。

对于每一对不等关系，确定合法的角度区间，角度区间判交。

把角度区间控制在 \([0,2\pi]\) 内，如果越过就拆成两段，然后扫描线，先 \(+\) 后 \(-\) ，判断是否有一个位置覆盖次数 \(=\) 区间个数。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;

inline int rd() {
    int x = 0; 
    bool f = 0; 
    char c = getchar();
    for (; !isdigit(c); c = getchar()) f |= (c == '-');
    for (; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);
    return f ? -x : x;
}

#define fr        first
#define sc        second
#define mp        make_pair
#define pb        push_back
#define pii       pair<int, int>
#define all(s)    (s).begin(), (s).end()
#define lowbit(x) ((x) & -(x))

const ld PI = 3.1415926535897932384;
const ld a90 = atan(1) * 2;
const ld a180 = a90 * 2, a270 = a90 * 3, a360 = a90 * 4;
const ld dlt[2][2] = {0, a180, a360, a180};

#define N 1007

int w[N];

ld x[N], y[N];

inline ld angle(ld x, ld y) {
    if (fabs(x) < 1e-15) return a90 * (1 + 2 * (y < 0));
    else return atan(y / x) + dlt[y < 0][x < 0];
}

vector<pair<long double, bool>> s;

int main() {
    int n = rd();
    for (int i = 1; i <= n; ++i) {
        x[i] = rd(); y[i] = rd(); w[i] = rd();
    }
    int tot = 0, nw = 0;
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= n; ++j)
            if (w[i] > w[j]) {
                ++tot;
                ld alpha = angle(x[i] - x[j], y[i] - y[j]);
                ld l = -alpha, r = PI - alpha;
                while (l < 0) {l += 2 * PI; r += 2 * PI;}
                if (r >= 2 * PI) r -= 2 * PI;
                s.pb(mp(l, false)); s.pb(mp(r, true));
                if (l > r) ++nw;
            }
    sort(all(s));
    if (tot == 0) {puts("Y"); return 0;}
    for (auto [p, w] : s) {
        nw += (w ? -1 : 1);
        if (nw == tot) {puts("Y"); return 0;}
    }
    puts("N");
    return 0;
}

E - Eggfruit Cake

给一个 \(01\) 环，问有多少个环上的的区间符合长度不超过 \(s\) 并且至少有一个 \(1\) 。

枚举左端点，复制一遍预处理后面第一个 \(1\) 的位置，答案就是 \(\sum s-dis(pos[i]-i)\)

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

int rd() {
    int x = 0; 
    bool f = 0; 
    char c = getchar();
    for (; !isdigit(c); c = getchar()) f |= (c == '-');
    for (; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);
    return f ? -x : x;
}

#define fr        first
#define sc        second
#define mp        make_pair
#define pb        push_back
#define pii       pair<int, int>
#define all(s)    (s).begin(), (s).end()
#define lowbit(x) ((x) & -(x))

string s;

#define N 100007

bool fl = false;

int nxt[N << 1];

int main() {
    cin >> s; 
    for (auto x : s) 
        if (x == 'E') {fl = true; break;}
    if (!fl) {puts("0"); return 0;}
    int n = s.length();
    s = " " + s + s;
    for (int i = (n << 1), lst = n; i; --i) {
        if (s[i] == 'E') lst = i;
        nxt[i] = lst;
    }
    int mx; cin >> mx;
    ll ans = 0;
    for (int i = 1; i <= n; ++i) {
        ans += max(0, mx - (nxt[i] - i));
    }
    printf("%lld\n", ans);
    return 0;
}

*F - Fabricating Sculptures

一些砖块堆起来，计数恰好用 \(B\) 块砖，最下面一层恰好 \(S\ (1\le S\le B\le 10^3)\) 块砖，并且不会积水的堆砌方案数。

需要横着想，一层一层放，约束变成：最下面一层 \(S\) 个，每一层不能比下一层多的方案数。

发现我们并不关心当前放了多少层，因此状态可以设计为 \(f[x][j]\) 表示已经用了 \(x\) 个，当前最上面一层放了 \(j\) 个的方案数。

转移：\(f[x][j] = \sum_{k=j}^Sf[x - j][k]\times (k - j + 1) = \sum_{k=j}^S f[x-j][k]\times k - (j-1)\sum_{k=j}^S f[x-j][k]\)

维护 \(f[\ast][k]\times k\) 的后缀和、\(f[\ast][k]\) 的后缀和即可实现 \(\mathcal{O}(1)\) 转移。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

int rd() {
    int x = 0; 
    bool f = 0; 
    char c = getchar();
    for (; !isdigit(c); c = getchar()) f |= (c == '-');
    for (; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);
    return f ? -x : x;
}

#define fr        first
#define sc        second
#define mp        make_pair
#define pb        push_back
#define pii       pair<int, int>
#define all(s)    (s).begin(), (s).end()
#define lowbit(x) ((x) & -(x))

#define N   5007
#define mod 1000000007

int f[N][N], sum[N][N], sumk[N][N];

int main() {
    int m = rd(), n = rd();
    f[m][m] = 1;
    for (int j = m; j; --j) {
        sum[m][j] = (sum[m][j + 1] + f[m][j]) % mod;
        sumk[m][j] = (sumk[m][j + 1] + 1ll * j * f[m][j]) % mod;    
    }
    for (int use = m + 1; use <= n; ++use) {
        for (int j = min(m, use); j; --j) {
            f[use][j] = (sumk[use - j][j] + 1ll * sum[use - j][j] * (1 - j + mod)) % mod;
            sum[use][j] = (sum[use][j + 1] + f[use][j]) % mod;
            sumk[use][j] = (sumk[use][j + 1] + 1ll * j * f[use][j]) % mod;
        }
    }
    printf("%d\n", sum[n][1]);
    return 0;
}

G - Gluing Pictures

给定一个模版串，多次询问，把一个串最少拆成多少个模版串的子串拼接起来。

容易发现贪心拿更长的子串是正确的，所以直接在 SAM 上匹配就好了，失败就回到根，答案就是匹配次数。

#include<cstdio>
using namespace std;
const int maxn=200000,maxt=maxn<<1,maxi=26;

int n,te;char s[maxn+5],t[maxn+5];
int pl,ro,son[maxt+5][maxi],fai[maxt+5],MAX[maxt+5];

inline int newnode() {pl++;return pl;}
int Extend(int p,int c){
	int np=newnode();MAX[np]=MAX[p]+1;
	while (p && !son[p][c]) son[p][c]=np,p=fai[p];
	if (!p) {fai[np]=ro;return np;}
	int q=son[p][c];if (MAX[p]+1==MAX[q]) {fai[np]=q;return np;}
	int nq=newnode();MAX[nq]=MAX[p]+1;
	for (int i=0;i<maxi;i++) son[nq][i]=son[q][i];
	fai[nq]=fai[q];fai[q]=fai[np]=nq;
	while (p && son[p][c]==q) son[p][c]=nq,p=fai[p];
	return np;
}
int main(){
	scanf("%s",s+1);ro=newnode();
	for (int i=1,p=ro;s[i];i++) p=Extend(p,s[i]-'A');
	for (scanf("%d",&te);te;te--){
		scanf("%s",t+1);
		int ans=0;
		for (int i=1,p=ro;t[i];i++){
			p=son[p][t[i]-'A'];
			if (!p){
				p=son[ro][t[i]-'A'];ans++;
				if (!p) {ans=-2;break;}
			}
		}
		printf("%d\n",ans+1);
	}
	return 0;
}

I - Improve SPAM

注意题目保证是个DAG，BFS 去掉无用点，统计出正确点度，然后拓扑排序路径计数即可。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

int rd() {
    int x = 0; 
    bool f = 0; 
    char c = getchar();
    for (; !isdigit(c); c = getchar()) f |= (c == '-');
    for (; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);
    return f ? -x : x;
}

#define fr        first
#define sc        second
#define mp        make_pair
#define pb        push_back
#define pii       pair<int, int>
#define all(s)    (s).begin(), (s).end()
#define lowbit(x) ((x) & -(x))

#define N   2007
#define mod 1000000007

int deg[N], f[N];

vector<int> e[N];

queue<int> q;

int main() {
    int n = rd(), m = rd();
    for (int i = 1; i <= m; ++i) 
        for (int k = rd(); k; --k) e[i].pb(rd());
    q.push(1);
    while (!q.empty()) {
        int u = q.front(); q.pop();
        for (auto v : e[u]) {
            if (!deg[v]) q.push(v);
            ++deg[v];
        }
    }
    int ans2 = 0;
    for (int i = m + 1; i <= n; ++i) ans2 += (deg[i] > 0);
    q.push(1); f[1] = 1;
    while (!q.empty()) {
        int u = q.front(); q.pop();
        for (auto v : e[u]) {
            f[v] = (f[v] + f[u]) % mod;
            --deg[v]; if (!deg[v]) q.push(v);
        }
    }
    int ans1 = 0;
    for (int i = m + 1; i <= n; ++i) ans1 = (ans1 + f[i]) % mod;
    printf("%d %d\n", ans1, ans2);
    return 0;
}

**J - Jumping Grasshopper

给定长度为 \(n\) 的数列，规定一个起点和方向（左/右），每次会跳到该方向的第一个比当前高的位置，然后转向。

保证初始数列两两不同，支持 \(m\) 次：1. 把某个数改大（依旧两两不同）；2. 给定起始位置和方向，问最后停在的位置。

数据范围：\(1\le n,m\le 2\times 10^5,1\le h_i\le 10^9\)

如果两侧都存在比当前位置大的，跳跃不会停止，最终会先跳到左右最大值较小的那个，然后再往对面跳一步 。

注意不是跳到最大的，因为最大值较小的一侧回头之后第一个比他大的，有可能不是那一侧最大的。

所以线段树维护区间 \(\max\) + 线段树上二分找上一个/下一个比给定值大的位置，复杂度 \(\mathcal{O}(n\log n)\) 。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

inline int rd() {
    int x = 0; 
    bool f = 0; 
    char c = getchar();
    for (; !isdigit(c); c = getchar()) f |= (c == '-');
    for (; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);
    return f ? -x : x;
}

#define fr        first
#define sc        second
#define mp        make_pair
#define pb        push_back
#define pii       pair<int, int>
#define all(s)    (s).begin(), (s).end()
#define lowbit(x) ((x) & -(x))

#define N  200007
#define ls (rt << 1)
#define rs (rt << 1 | 1)
#define mid ((l + r) >> 1)

int n, m, h[N], mx[N << 2];

inline void pushup(int rt) {
    mx[rt] = mx[ls] > mx[rs] ? mx[ls] : mx[rs];
}

void build(int rt, int l, int r) {
    if (l == r) {mx[rt] = h[l]; return;}
    build(ls, l, mid); build(rs, mid + 1, r);
    pushup(rt);
}

void upd(int rt, int l, int r, int p, int x) {
    if (l == r) {mx[rt] = x; return;}
    p <= mid ? upd(ls, l, mid, p, x) : upd(rs, mid + 1, r, p, x);
    pushup(rt);
}

int qmax(int rt, int l, int r, int L, int R) {
    if (L <= l && r <= R) return mx[rt];
    int ans = 0;
    if (L <= mid) ans = max(ans, qmax(ls, l, mid, L, R));
    if (R > mid) ans = max(ans, qmax(rs, mid + 1, r, L, R));
    return ans;
}

int nxtr(int rt, int l, int r, int L, int w) {
    if (l == r) return l;
    if (L <= mid && mx[ls] > w) {
        int res = nxtr(ls, l, mid, L, w);
        if (res > 0) return res;
    }
    if (mx[rs] <= w) return -1;
    return nxtr(rs, mid + 1, r, L, w);
}

int nxtl(int rt, int l, int r, int L, int w) {
    if (l == r) return l;
    if (L > mid && mx[rs] > w) {
        int res = nxtl(rs, mid + 1, r, L, w);
        if (res > 0) return res;
    }
    if (mx[ls] <= w) return -1;
    return nxtl(ls, l, mid, L, w);
}

unordered_map<int, int> pos;

int main() {
    int n = rd(), m = rd(), mxpos = 1;
    for (int i = 1; i <= n; ++i) {
        h[i] = rd(); pos[h[i]] = i;
    }
    build(1, 1, n);
    for (int i = 1; i <= m; ++i) {
        char c = getchar();
        while (!isalpha(c)) c = getchar();
        if (c == 'U') {
            int p = rd(); 
            pos[h[p] = rd()] = p;
            upd(1, 1, n, p, h[p]);
        } else {
            int p = rd();
            int lmx = qmax(1, 1, n, 1, p);
            if (c == 'L' && lmx == h[p]) {printf("%d\n", p); continue;}
            int rmx = qmax(1, 1, n, p, n);
            if (c == 'R' && rmx == h[p]) {printf("%d\n", p); continue;}
            if (lmx < rmx) printf("%d\n", nxtr(1, 1, n, pos[lmx], lmx));
            else printf("%d\n", nxtl(1, 1, n, pos[rmx], rmx));
        }
    }
    return 0;
}

K - Know your Aliens

构造多项式 \(P\) ，对于 \(i=2,4,\dots,2n\) ，符合给定的条件 \(P(i)>0\) 或 \(P(i)<0\) 。

对于相邻的符号变化的位置，中位数一定是个奇数（并且是整数），可以假定他是多项式的根。

因此就是求 \(\prod (x-w_i)\) 的各系数，然后根据第一个的正负调整一下符号即可。

有一个 \(O(n^2)\) 的递推方法求系数（直接多项式乘法复杂度也对）：

设 \(f[i][j]\) 表示前 \(i\) 个系数里所有的选 \(j\) 个的方案对应的乘积和，转移 \(f[i][j] = f[i - 1][j] + f[i - 1][j - 1] * w_i\) 。

（不过这个题题面里说保证存在系数不超过 \(2^{63}\) 的多项式符合要求，理解起来有点奇怪）

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

int rd() {
    int x = 0; 
    bool f = 0; 
    char c = getchar();
    for (; !isdigit(c); c = getchar()) f |= (c == '-');
    for (; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);
    return f ? -x : x;
}

#define fr        first
#define sc        second
#define mp        make_pair
#define pb        push_back
#define pii       pair<int, int>
#define all(s)    (s).begin(), (s).end()
#define lowbit(x) ((x) & -(x))

#define N 10007

char s[N];

ll cnt, f[N][N], w[N];

int main() {
    scanf("%s", s + 1);
    int n = strlen(s + 1);
    for (int i = 1; i < n; ++i) 
        if (s[i] != s[i + 1]) w[++cnt] = - 2 * i - 1;
    f[0][0] = 1;
    for (int i = 1; i <= cnt; ++i) {
        f[i][0] = 1;
        for (int j = 1; j <= i; ++j)
            f[i][j] = f[i - 1][j - 1] * w[i] + f[i - 1][j];
    }
    int fl = ((f[cnt][cnt] > 0) == (s[1] == 'H') ? 1 : -1);
    printf("%lld\n", cnt);
    for (int i = 0; i <= cnt; ++i) printf("%lld ", fl * f[cnt][i]);
    return 0;
}

L - Leverage MDT

给一个 \(01\) 矩阵，对于每行你都可以选择全部 \(01\) 翻转/不翻转，然后求最大子正方形。

按列去看，枚举答案的右边界，对于每行约束就变成了向左找和当前位置相同的最长长度。

然后做一个单调栈就可以了，因为是正方形，更新答案使用当前的高度和宽度的较小值。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

int rd() {
    int x = 0; 
    bool f = 0; 
    char c = getchar();
    for (; !isdigit(c); c = getchar()) f |= (c == '-');
    for (; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);
    return f ? -x : x;
}

#define fr        first
#define sc        second
#define mp        make_pair
#define pb        push_back
#define pii       pair<int, int>
#define all(s)    (s).begin(), (s).end()
#define lowbit(x) ((x) & -(x))

#define N 1007

bool a[N][N];

int f[N][N];

stack<pii> s;

int main() {
    int n = rd(), m = rd();
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= m; ++j) {
            char c = getchar();
            while (!isalpha(c)) c = getchar();
            a[i][j] = (c == 'G');
            f[i][j] = (a[i][j] == a[i][j - 1] ? f[i][j - 1] + 1 : 1);
        }
    int ans = 0;
    for (int j = 1; j <= m; ++j) {
        for (int i = 1; i <= n; ++i) {
            int len = 0;
            while (!s.empty() && f[s.top().fr][j] >= f[i][j]) {
                len += s.top().sc;
                ans = max(ans, min(f[s.top().fr][j], len));
                s.pop();
            }
            s.push(mp(i, len + 1));
        }
        int len = 0;
        while (!s.empty()) {
            len += s.top().sc;
            ans = max(ans, min(f[s.top().fr][j], len));
            s.pop();
        }
    }
    printf("%d\n", ans * ans);
    return 0;
}

M - Mountain Ranges

给定数列，求最长的区间，区间内相邻的两个数差值不超过 \(x\) 。直接扫一遍。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

int rd() {
    int x = 0; 
    bool f = 0; 
    char c = getchar();
    for (; !isdigit(c); c = getchar()) f |= (c == '-');
    for (; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);
    return f ? -x : x;
}

#define fr        first
#define sc        second
#define mp        make_pair
#define pb        push_back
#define pii       pair<int, int>
#define all(s)    (s).begin(), (s).end()
#define lowbit(x) ((x) & -(x))

#define N 1007

int a[N];

int main() {
    int n = rd(), k = rd(), ans = 0;
    for (int i = 1; i <= n; ++i) a[i] = rd();
    for (int i = n, cnt = 0; i; --i) {
        if (a[i + 1] - a[i] > k) cnt = 0;
        ++cnt; ans = max(ans, cnt);
    }
    printf("%d\n", ans);
    return 0;
}

Official Contests

Binary Search Graphs Segment Tree Binary Lifting Sparse Table Stack

本博客所有文章除特别声明外，均采用 CC BY-SA 4.0 协议，转载请注明出处！

2018 CCPC Finals Previous

Prefix Function and Z Function Next