题号	标题	已通过代码	题解/讨论	通过率	团队的状态
A	All-one Matrices	点击查看	单调栈+前缀和	326/2017	通过
B	Beauty Values	点击查看	进入讨论	827/1995	通过
C	CDMA	点击查看	进入讨论	669/1115	通过
D	Distance	点击查看	理性暴力	37/554	OK
E	Explorer	点击查看	可修改并查集，LCT	83/920	OK
F	Flower Dance	点击查看	进入讨论	13/121	未通过
G	Gemstones	点击查看	进入讨论	883/2062	通过
H	How Many Schemes	点击查看	进入讨论	3/61	未通过
I	Inner World	点击查看	dfs序，矩形面积	17/94	OK
J	Just Jump	点击查看	DP，容斥	85/532	OK

A - All-one Matrices

题意：

给定一个n × m的 01矩阵，输出极大全1子矩阵的个数。

思路：

先搞出每个点向下能走的距离。

利用单调栈维护每个点最左能到达的值，由于有相同的情况，所以要跑两次单调栈，

第一次求出每个点最左能到的地方。

第二次要弹栈的，判断是否能作为子矩阵的最上层，计入答案。

// #pragma GCC optimize(2)

// #pragma GCC optimize(3)

// #pragma GCC optimize(4)

#include <algorithm>

#include  <iterator>

#include  <iostream>

#include   <cstring>

#include   <cstdlib>

#include   <iomanip>

#include    <bitset>

#include    <cctype>

#include    <cstdio>

#include    <string>

#include    <vector>

#include     <stack>

#include     <cmath>

#include     <queue>

#include      <list>

#include       <map>

#include       <set>

#include   <cassert>

// #include<bits/extc++.h>

// using namespace __gnu_pbds;

using namespace std;

#define pb push_back

#define fi first

#define se second

#define debug(x) cerr<<#x << " := " << x << endl;

#define bug cerr<<"-----------------------"<<endl;

#define FOR(a, b, c) for(int a = b; a <= c; ++ a)

typedef long long ll;

typedef long double ld;

typedef pair<int, int> pii;

typedef pair<ll, ll> pll;

const int inf = 0x3f3f3f3f;

const ll inff = 0x3f3f3f3f3f3f3f3f;

const int mod = 1e9+;

template<typename T>

inline T read(T&x){

    x=;int f=;char ch=getchar();

    while (ch<''||ch>'') f|=(ch=='-'),ch=getchar();

    while (ch>=''&&ch<='') x=x*+ch-'',ch=getchar();

    return x=f?-x:x;

}

/**********showtime************/

            const int maxn = ;

            char str[maxn][maxn];

            int sum[maxn][maxn];

            int dp[maxn][maxn];

            int ls[maxn];

            stack<pii>st;

int main(){

            int n,m;

            scanf("%d%d", &n, &m);

            for(int i=; i<=n; i++) scanf("%s", str[i] + );

            for(int i=; i<=n; i++) {

                for(int j=; j<=m; j++) {

                    sum[i][j] = sum[i][j-];

                    if(str[i][j] == '') sum[i][j] ++;

                }

            }

            for(int i=n; i>=; i--) {

                for(int j=; j<=m; j++) {

                    if(str[i][j] == '') dp[i][j] = dp[i+][j] + ;

                    else dp[i][j] = ;

                }

            }

            int ans = ;

            for(int i=; i<=n; i++) {

//                debug(i);

                while(!st.empty()) st.pop();

                st.push(pii(-, ));

                for(int j=; j<=m; j++) {

                        while(!st.empty() && st.top().fi >= dp[i][j]) {

                            st.pop();

                        }

                        ls[j] = st.top().se + ;

                        st.push(pii(dp[i][j], j));

                }

                while(!st.empty()) st.pop();

                 for(int j=; j<=m + ; j++) {

                    while(!st.empty() && st.top().fi > dp[i][j]) {

                        int le = ls[st.top().se], ri = j - ;

                        st.pop();

                        if(sum[i-][ri] - sum[i-][le-] == ri - le + ) continue;

                        ans++;

                    }

                    if(j < m +  && (st.empty() || dp[i][j] > st.top().fi) )st.push(pii(dp[i][j], j));

                }

            }

            printf("%d\n", ans);

            return ;

}

/*

5 5

11111

11110

11100

11100

10000

3 6

001000

011011

010011

*/

D-Distance

思路

考虑非情况，如果点数不多，就枚举点数，如果点数很多，就把这么多点的影响通过bfs记录下来。

/*

* @Author: chenkexing

* @Date:   2019-08-11 21:48:52

* @Last Modified by:   chenkexing

* @Last Modified time: 2019-08-11 23:23:57

*/

// #pragma GCC optimize(2)

// #pragma GCC optimize(3)

// #pragma GCC optimize(4)

#include <algorithm>

#include  <iterator>

#include  <iostream>

#include   <cstring>

#include   <cstdlib>

#include   <iomanip>

#include    <bitset>

#include    <cctype>

#include    <cstdio>

#include    <string>

#include    <vector>

#include     <stack>

#include     <cmath>

#include     <queue>

#include      <list>

#include       <map>

#include       <set>

#include   <cassert>

// #include<bits/extc++.h>

// using namespace __gnu_pbds;

using namespace std;

#define pb push_back

#define fi first

#define se second

#define debug(x) cerr<<#x << " := " << x << endl;

#define bug cerr<<"-----------------------"<<endl;

#define FOR(a, b, c) for(int a = b; a <= c; ++ a)

typedef long long ll;

typedef long double ld;

typedef pair<int, int> pii;

typedef pair<int, pii> p3;

typedef pair<ll, ll> pll;

const int inf = 0x3f3f3f3f;

const ll inff = 0x3f3f3f3f3f3f3f3f;

const int mod = 1e9+;

template<typename T>

inline T read(T&x){

    x=;int f=;char ch=getchar();

    while (ch<''||ch>'') f|=(ch=='-'),ch=getchar();

    while (ch>=''&&ch<='') x=x*+ch-'',ch=getchar();

    return x=f?-x:x;

}

/**********showtime************/

            const int maxn = 1e5+;

            int n,m,h,q;

            int getid(int x, int y, int z) {

                return (z - )* (n * m) + (x-)*m + y;

            }

            vector<int>vx,vy,vz;

            int dis[maxn];

            int xia[][] = {{,,},{,,},{,,}, {-,  , }, {, - , }, {,  ,- }};

            void rebuild(){

                queue< p3>que;

                for(int i=; i<vx.size(); i++) {

                        int nx = vx[i];

                        int ny = vy[i];

                        int nz = vz[i];

                        dis[getid(nx, ny, nz)] = ;

                        que.push(p3(nx, pii(ny, nz)));

                }

                vx.clear();

                vy.clear();

                vz.clear();

                while(!que.empty()) {

                    p3 tmp = que.front(); que.pop();

                    int x = tmp.fi;

                    int y = tmp.se.fi;

                    int z = tmp.se.se;

                    for(int i=; i<; i++) {

                        int nx = x + xia[i][];

                        int ny = y + xia[i][];

                        int nz = z + xia[i][];

                        if(nx <=  || nx > n || ny <= || ny > m || nz <=  || nz > h) continue;

                        if(dis[getid(nx, ny, nz)] > dis[getid(x, y, z)] + ) {

                            dis[getid(nx, ny, nz)] = dis[getid(x, y, z)] + ;

                            que.push(p3(nx, pii(ny, nz)));

                        }

                    }

                }

            }

int main(){

            scanf("%d%d%d%d", &n, &m, &h, &q);

            int E = sqrt(n * m * h) + ;

            memset(dis, inf, sizeof(dis));

            while(q--) {

                int op, x, y, z;

                scanf("%d%d%d%d", &op, &x, &y, &z);

                if(op == ) {

                    vx.pb(x);

                    vy.pb(y);

                    vz.pb(z);

                }

                else {

                    int ans = dis[getid(x, y, z)];

                    for(int i=; i<vx.size(); i++) {

                        int nx = vx[i];

                        int ny = vy[i];

                        int nz = vz[i];

                        ans = min(ans, abs(nx - x) + abs(ny - y) + abs(nz - z));

                    }

                    printf("%d\n", ans);

                }

                if(vx.size() >= E) rebuild();

            }

            return ;

}

E - Explorer

可撤回的并查集

利用线段树优化

注意每次从左子树或者右子树回来的时候，都要进行清空。

// #pragma GCC optimize(2)

// #pragma GCC optimize(3)

// #pragma GCC optimize(4)

#include <algorithm>

#include  <iterator>

#include  <iostream>

#include   <cstring>

#include   <cstdlib>

#include   <iomanip>

#include    <bitset>

#include    <cctype>

#include    <cstdio>

#include    <string>

#include    <vector>

#include     <stack>

#include     <cmath>

#include     <queue>

#include      <list>

#include       <map>

#include       <set>

#include   <cassert>

// #include<bits/extc++.h>

// using namespace __gnu_pbds;

using namespace std;

#define pb push_back

#define fi first

#define se second

#define debug(x) cerr<<#x << " := " << x << endl;

#define bug cerr<<"-----------------------"<<endl;

#define FOR(a, b, c) for(int a = b; a <= c; ++ a)

typedef long long ll;

typedef long double ld;

typedef pair<int, int> pii;

typedef pair<ll, ll> pll;

const int inf = 0x3f3f3f3f;

const ll inff = 0x3f3f3f3f3f3f3f3f;

const int mod = 1e9+;

template<typename T>

inline T read(T&x){

    x=;int f=;char ch=getchar();

    while (ch<''||ch>'') f|=(ch=='-'),ch=getchar();

    while (ch>=''&&ch<='') x=x*+ch-'',ch=getchar();

    return x=f?-x:x;

}

const int N = 1e5+;

/// 可撤回并查集模板

struct UFS {

    stack<pair<int*, int>> stk;

    int fa[N], rnk[N];

    inline void init(int n) {

        for (int i = ; i <= n; ++i) fa[i] = i, rnk[i] = ;

    }

    inline int Find(int x) {

        while(x^fa[x]) x = fa[x];

        return x;

    }

    inline void Merge(int x, int y) {

        x = Find(x), y = Find(y);

        if(x == y) return ;

        if(rnk[x] <= rnk[y]) {

            stk.push({fa+x, fa[x]});

            fa[x] = y;

            if(rnk[x] == rnk[y]) {

                stk.push({rnk+y, rnk[y]});

                rnk[y]++;

            }

        }

        else {

            stk.push({fa+y, fa[y]});

            fa[y] = x;

        }

    }

    inline void Undo() {

        *stk.top().fi = stk.top().se;

        stk.pop();

    }

}T;

/**********showtime************/

            const int maxn = 1e5+;

            int n,m;

            struct E{

                int u, v, le, ri;

                void init(int U, int V, int Le, int Ri) {

                    u = U; v = V;

                    le = Le; ri = Ri;

                }

            } edge[maxn];

            vector<int>vec;

            int getid(int x) {

                return lower_bound(vec.begin(), vec.end(), x) - vec.begin() + ;

            }

            vector <int> node[maxn * ];

            int sz[maxn * ];

            void update(int L, int R, int id, int le, int ri, int rt) {

                if(le >= L && ri <= R) {

                    node[rt].pb(id);

                    return;

                }

                int mid = (le + ri) >> ;

                if(mid >= L) update(L, R, id, le, mid, rt<<);

                if(mid < R) update(L, R, id, mid+, ri, rt<<|);

            }

            ll ans = ;

            void dfs(int le, int ri, int rt) {

                for(int id : node[rt]) {

                    T.Merge(edge[id].u, edge[id].v);

                }

                int sz = T.stk.size();

                if(le == ri) {

                    if(T.Find() == T.Find(n)) {

//                        cout<<ri<<endl;

                        ans += vec[ri] - vec[le-];

                    }

                    return;

                }

                int mid = (le + ri) >> ;

                dfs(le, mid, rt<<);

                while(T.stk.size() > sz) {

                    T.Undo();

                }

                dfs(mid+, ri, rt<<|);

                while(T.stk.size() > sz) {

                    T.Undo();

                }

            }

int main(){

            scanf("%d%d", &n, &m);

            T.init(n);

            for(int i=; i<=m; i++) {

                int u,v,le,ri;

                scanf("%d%d%d%d", &u, &v, &le, &ri);

                edge[i].init(u, v, le, ri+);

                vec.pb(le);

                vec.pb(ri + );

            }

            sort(vec.begin(), vec.end());

            vec.erase(unique(vec.begin(), vec.end()), vec.end());

            int tot = vec.size();

            for(int i=; i<=m; i++) {

                int l = getid(edge[i].le);

                int r = getid(edge[i].ri) - ;

//                cout<<l<<" " << r << endl;

                update(l, r, i, , tot-, );

            }

            ans = ;

            dfs(, tot-, );

            printf("%lld\n", ans);

            return ;

}

I - Inner World

先把n个子树看成一颗树，相同的点合并到一起，附加一个区间信息就行了。

然后利用dfs序+前缀和的思想处理询问即可

// #pragma GCC optimize(2)

// #pragma GCC optimize(3)

// #pragma GCC optimize(4)

#include <algorithm>

#include  <iterator>

#include  <iostream>

#include   <cstring>

#include   <cstdlib>

#include   <iomanip>

#include    <bitset>

#include    <cctype>

#include    <cstdio>

#include    <string>

#include    <vector>

#include     <stack>

#include     <cmath>

#include     <queue>

#include      <list>

#include       <map>

#include       <set>

#include   <cassert>

// #include<bits/extc++.h>

// using namespace __gnu_pbds;

using namespace std;

#define pb push_back

#define fi first

#define se second

#define debug(x) cerr<<#x << " := " << x << endl;

#define bug cerr<<"-----------------------"<<endl;

#define FOR(a, b, c) for(int a = b; a <= c; ++ a)

typedef long long ll;

typedef long double ld;

typedef pair<int, int> pii;

typedef pair<ll, ll> pll;

const int inf = 0x3f3f3f3f;

const ll inff = 0x3f3f3f3f3f3f3f3f;

const int mod = ;

template<typename T>

inline T read(T&x){

    x=;int f=;char ch=getchar();

    while (ch<''||ch>'') f|=(ch=='-'),ch=getchar();

    while (ch>=''&&ch<='') x=x*+ch-'',ch=getchar();

    return x=f?-x:x;

}

/**********showtime************/

            const int maxn = 3e5+;

            int le[maxn],ri[maxn];

            vector<int>mp[maxn];

            int id[maxn], dfn[maxn], tim = , sz[maxn];

            void dfs(int u) {

                dfn[u] = ++tim;

                id[tim] = u;

                sz[u] = ;

                for(int v : mp[u]) {

                    dfs(v);

                    sz[u] += sz[v];

                }

            }

            struct node{

                int le, ri, id, op;

                node(int Le, int Ri, int Id, int Op){

                    le = Le; ri = Ri; id = Id; op = Op;

                }

            };

            vector<node> g[maxn];

            ll ans[maxn];

            struct TT{

                ll sum[maxn<<], lazy[maxn<<];

                void pushdown(int le, int ri, int rt) {

                    lazy[rt<<] += lazy[rt];

                    lazy[rt<<|] += lazy[rt];

                    int mid = (le + ri) >> ;

                    sum[rt<<] += 1ll*lazy[rt] * (mid - le + );

                    sum[rt<<|] += 1ll*lazy[rt] * (ri - mid);

                    lazy[rt] = ;

                }

                void update(int L, int R, int c, int le, int ri, int rt) {

                    if(le >= L && ri <= R) {

                        sum[rt] += 1ll * c * (ri - le + );

                        lazy[rt] += 1ll * c;

                        return ;

                    }

                    int mid = (le + ri) >> ;

                    if(lazy[rt]) pushdown(le , ri, rt);

                    if(L <= mid) update(L, R, c, le, mid, rt<<);

                    if(mid < R) update(L, R, c, mid+, ri, rt<<|);

                    sum[rt] = sum[rt<<] + sum[rt<<|];

                }

                ll query(int L, int R, int le, int ri, int rt) {

                    if(le >= L && ri <= R) {

                        return sum[rt];

                    }

                    int mid = (le + ri) >> ;

                    if(lazy[rt]) pushdown(le, ri, rt);

                    ll res = ;

                    if(L <= mid) res += query(L, R, le, mid, rt<<);

                    if(mid < R) res += query(L, R, mid+, ri,rt<<|);

                    return res;

                }

            } tree;

int main(){

            int n,m;

            scanf("%d%d", &n, &m);

            le[] = , ri[] = n;

            for(int i=; i<=m; i++) {

                int u,v,l,r;

                scanf("%d%d%d%d", &u, &v, &l, &r);

                mp[u].pb(v);

                le[v] = l, ri[v] = r;

            }

            int N = m + ;

            ///dfs序，将一个点的子树表示成一个区间

            dfs();

            int q;  scanf("%d", &q);

            for(int i=; i<=q; i++) {

                int u, le, ri;

                scanf("%d%d%d", &u, &le, &ri);

                int t1 = dfn[u] - ;

                ///将一次询问拆成两次操作，类似于把区间和改为前缀和相减

                g[t1].pb(node(le, ri, i, -));

                g[t1 + sz[u]].pb(node{le, ri, i, });

            }

            for(int i=; i<=tim; i++) {

                int u = id[i];

                tree.update(le[u], ri[u], , , n, );

                ///因为是二维面积，所以要用线段树等数据结构维护前缀和

                for(node a : g[i]) {

                    ans[a.id] += 1ll * a.op * tree.query(a.le, a.ri, , n, );

                }

            }

            for(int i=; i<=q; i++) printf("%lld\n", ans[i]);

            return ;

}

/*

4 3

1 2 1 2

1 3 2 4

3 4 2 3

2

1 1 4

3 1 4

*/

J - Just Jump

由于有m个限制，我们就计算出m个对应点不合法方案的个数。

这里要利用容斥，第i个点不合法的方案要减去之前就不合法的点转移过来的方案。

然后dp转移。

O($m ^ 2 + n$)的复杂度

从一个点x转移到y，走p步，每步长度要大于t,的方案数。可以转化为小球放入盒子中的问题。

设x到y之间有n个点，

就可以转化为有n个小球，分到p个盒子中，每个盒子至少要有t个小球。

那么我们先安排每个盒子t个小球。

那么剩下的$ n - t \times p$个小球放入盒子中，盒子可以为空。

这个怎么做呢，我们利用隔板法，多放入$ n - t \times p$个盒子，选出 p - 1个盒子作为隔板即可。

即

$\dbinom{n - p \times t + p - 1}{p-1}$

// #pragma GCC optimize(2)

// #pragma GCC optimize(3)

// #pragma GCC optimize(4)

#include <algorithm>

#include  <iterator>

#include  <iostream>

#include   <cstring>

#include   <cstdlib>

#include   <iomanip>

#include    <bitset>

#include    <cctype>

#include    <cstdio>

#include    <string>

#include    <vector>

#include     <stack>

#include     <cmath>

#include     <queue>

#include      <list>

#include       <map>

#include       <set>

#include   <cassert>

// #include<bits/extc++.h>

// using namespace __gnu_pbds;

using namespace std;

#define pb push_back

#define fi first

#define se second

#define debug(x) cerr<<#x << " := " << x << endl;

#define bug cerr<<"-----------------------"<<endl;

#define FOR(a, b, c) for(int a = b; a <= c; ++ a)

typedef long long ll;

typedef long double ld;

typedef pair<int, int> pii;

typedef pair<ll, ll> pll;

const int inf = 0x3f3f3f3f;

const ll inff = 0x3f3f3f3f3f3f3f3f;

const int mod = ;

template<typename T>

inline T read(T&x){

    x=;int f=;char ch=getchar();

    while (ch<''||ch>'') f|=(ch=='-'),ch=getchar();

    while (ch>=''&&ch<='') x=x*+ch-'',ch=getchar();

    return x=f?-x:x;

}

/**********showtime************/

            const int maxn=1e7+;

            ll A[maxn];

            ll B[maxn];

            ll quick(int x,int n){

                ll ans=;

                while(n){

                    if(n&) ans=1ll*ans*x%mod;

                    x=1ll*x*x%mod;

                    n=n/;

                }

                return ans;

            }

            void init(){

                int n=maxn-;

                A[]=; B[]=;

                for(int i=;i<=n;i++) A[i]=1ll*A[i-]*i%mod;

                B[n]=quick(A[n],mod-);

                for(int i=n-;i>=;i--) B[i]=1ll*B[i+]*(i+)%mod;

            }

            ll CC(ll n,ll x){

                if(x>n) return ;

                return 1ll*A[n]*B[n-x]%mod*B[x]%mod;

            }

            ll dp[maxn];

            ll s[], sum[maxn];

            pii a[];

int main(){

            init();

//            debug(CC(500, 1));

            int L,d,m;

            scanf("%d%d%d", &L, &d, &m);

            for(int i=; i<=m; i++) {

                scanf("%d%d", &a[i].se, &a[i].fi);

            }

            sort(a + , a +  + m);

            for(int i=; i<=m; i++) {

                ll pos = a[i].fi, t = a[i].se;

                s[i] = CC(pos - t * d + t - , t - );

//                cout<<s[i]<<" ";

                for(int j=; j<i; j++){

                    if(a[j].fi < a[i].fi && a[j].se < a[i].se) {

                        ll prepos = a[j].fi, pret = a[j].se;

                        ll n = pos - prepos, tt = t - pret;

                        s[i] = (s[i] - 1ll*s[j] * CC(n - tt * d + tt - , tt - )%mod + mod) % mod;

                    }

                }

                dp[pos] =((dp[pos] - s[i])% mod + mod) % mod;

            }

//            cout<<endl;

            dp[] = ;

            sum[] = ;

            for(int i=; i<=L; i++) {

                if(i-d >= ) dp[i] += sum[i-d];

                dp[i] = dp[i] % mod;

                sum[i] = (sum[i-] + dp[i]) % mod;

//                cout<<dp[i]<<" ";

            }

//            cout<<endl;

            printf("%lld\n", dp[L]);

            return ;

}

/*

5 2 4

1 2

2 5

2 8

2 9

*/

巴特西

2019NC#8

A - All-one Matrices

题意：

思路：

D-Distance

思路

E - Explorer

I - Inner World

J - Just Jump

最新文章

热门文章