2018 Multi-University Training Contest 3 – WNJXYKのBlog
WNJXYK
Thanks to the cruel world.
WNJXYKのBlog
2018 Multi-University Training Contest 3
2018 Multi-University Training Contest 3

HDU 6319 Problem A. Ascending Rating

给定一个长度为n(n\leq 10^{7})的序列,问所有长度为m的子区间内,最大值与扫描最大值中的更新次数。

反向维护一个单调队列就可以了,然而我正向做了。

正向同样可以维护一个当前区间内的上升序列,但是从队列头删除元素的时候可能会出现删除一个靠前较大的元素,需要引入若干个靠后较小的递增元素。
但是可以发现,无论怎么维护,所有元素都只会入队一次,所以复杂度还是O(n)的。
我们只需要预处理出每一个元素之后比它大的元素的位置即可,使用一个单调队列,即可处理出这个东西。

/**
* Author : WNJXYK
* Date : 20180730
* Problem : A
**/

#include <bits/stdc++.h>

using namespace std;

#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
typedef vector<int> VI;
typedef long long LL;
typedef pair<int,int> PII;

const int MAXN=1e7+50;

int n, m, k, p, q, r;
LL MOD;
int rate[MAXN], nxt[MAXN];
bool inQue[MAXN];

deque<int> que;
deque<int> que0;
stack<int> S;


inline void solve(int T){
    while(!que.empty()) que.pop_back(); while(!que0.empty()) que0.pop_back(); while(!S.empty()) S.pop();

    scanf("%d%d%d%d%d%d%lld", &n, &m, &k, &p, &q, &r, &MOD);
    for (int i=1; i<=k; i++) scanf("%d", rate+i);
    for (int i=k+1; i<=n; i++) rate[i]=(1LL*rate[i-1]*p+1LL*q*i+1LL*r)%MOD;
    for (int i=1; i<=n; i++) inQue[i]=false, nxt[i]=-1;

    for (int i=1; i<=n; i++){
        while(!que0.empty() && rate[i]>rate[que0.back()]) nxt[que0.back()]=i, que0.pop_back();
        que0.push_back(i);
    }


    LL A=0, B=0;
    for (int i=1; i<=n; i++){

        // Pop
        while(!que.empty() && que.front()<i-m+1) que.pop_front();

        // Save
        int now=i-m+1;
        while(0<now && now<i && !inQue[now]) S.push(now), now=nxt[now];
        while(!S.empty()) que.push_front(S.top()), inQue[S.top()]=true, S.pop();

        // Push
        if (que.empty() || rate[i]>rate[que.back()]) que.push_back(i), inQue[i]=true;
        //for (int i=0; i<que.size(); i++) printf("%d ", que[i]); printf("\n");
        if (i>=m){
            //printf("MAX=%d Count=%d\n", rate[que.back()], que.size());
            // Solve
            A=A+(rate[que.back()]^(i-m+1));
            B=B+(que.size()^(i-m+1));
        }
    }

    printf("%lld %lld\n", A, B);
}

int main(){
    freopen("A.in" ,"r", stdin);
    freopen("out.txt", "w", stdout);
    int T=0; scanf("%d", &T);
    for (int i=1; i<=T; i++) solve(i);
    return 0;
}

HDU 6321 Problem C. Dynamic Graph Matching

一个只有10个点的图,支持动态加边&删边,问每次操作之后图内边的K匹配数量。

边匹配是的条件是点不能重复使用,所以我们只需要记录点的使用情况即可。状态压缩10个点的匹配情况,那么增加一条边$<x, y>$,对答案的贡献是从状态S, (x, y\notin S)向状态S^1 (S^1 = S \bigcup x \bigcup y)贡献答案,反之,删边也是如此减少答案。
所以令dp[k][S]表示k匹配时点使用情况为S的方案数,转移为:
增加一条边(x, y),即为dp[k][S+x+y]+=dp[k-1][S], (x, y\notin S)
删除一条边(x, y),即为dp[k][S+x+y]-=dp[k-1][S], (x, y\notin S)

/**
* Author : WNJXYK
* Date : 20180730
* Problem : C
**/

#include <bits/stdc++.h>

using namespace std;

#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
typedef vector<int> VI;
typedef long long LL;
typedef pair<int,int> PII;

const int MOD=1e9+7;
const int MAXN=1e5+50;

LL powmod(LL a, LL b) {LL res=1;a%=MOD; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%MOD;a=a*a%MOD;}return res;}
LL gcd(LL a, LL b) { return b?gcd(b,a%b):a;}

int n, m;
char op[5];

int dp[15][1<<10];
int _s[1<<10], tot;

inline void solve(int T){
    memset(dp, 0, sizeof(dp));
    scanf("%d%d", &n, &m);
    int lim=1<<n;

    tot=0;
    for (int i=0; i<lim; i++)
        if (__builtin_parity(i)==0) _s[++tot]=i, dp[0][i]=1;

    for (int i=1, x, y; i<=m; i++){
        scanf("%s %d %d", op, &x, &y);
        --x; --y;
        for (int now=1, l=n/2; now<=l; now++){
            // DP
            for (int _=1; _<=tot; _++){
                int s=_s[_];
                if (((s>>x)&1) || ((s>>y)&1) || dp[now-1][s]==0) continue;
                int ns=s|(1<<x)|(1<<y);
                if (op[0]=='-') dp[now][ns]=dp[now][ns]+MOD-dp[now-1][s]; else dp[now][ns]=dp[now][ns]+dp[now-1][s];
                if (dp[now][ns]>=MOD) dp[now][ns]-=MOD;
            }
            printf("%d%c", dp[now][lim-1], (now==l?'\n':' '));
        }
    }
}

int main(){
    //freopen("in.txt" ,"r", stdin);
    //freopen("out.txt", "w", stdout);
    int T=0; scanf("%d", &T);
    for (int i=1; i<=T; i++) solve(i);
    return 0;
}

HDU 6322 Problem D. Euler Function

给定k,求第k小的数 n,满足\phi(n)是合数。

经过证明与观察可以发现,当n=1, 2, 3, 4, 6时,\phi(n)为质数,其他都为合数。

#include<bits/stdc++.h>
using namespace std;
#define LL long long

int main() {
    int t, k;
    scanf("%d", &t);
    for(int i = 1; i <= t; ++i) {
        scanf("%d", &k);
        if(k == 1) {
            printf("5\n");
            continue;
        }
        if(k == 2) {
            printf("7\n");
            continue;
        }
        printf("%d\n", k + 5);
    }
    return 0;
}

HDU 6324 Problem F. Grab The Tree

给定一棵n个点的树,每个点有权值。两个人玩游戏,先手需要占领若干不相邻的点,然后后手占领剩下所有点。
每个人的得分为占领的点权异或和,分高的获胜。问最优策略下游戏的结果。

如果这个树上所有节点异或和为0,那么一定会平局,否则先手只需要取包含异或和最高位为1的那个节点就一定能保证胜利。

#include <iostream>
#include <cstdio>
#include <queue>
#include <cstring>

using namespace std;

const int MAXN = 100010;
int tot;
int w[MAXN], to[MAXN<<1], _next[MAXN<<1], head[MAXN], col[MAXN];

void addEdge(int u, int v) {
    to[++tot] = v, _next[tot] = head[u], head[u] = tot;
}

void bfs() {
    queue<int>q; q.push(1);
    col[1] = 2;
    while(!q.empty()) {
        int u = q.front(); q.pop();
        for(int i = head[u]; i; i = _next[i]) {
            int v = to[i];
            if(col[v]) continue;
            col[v] = (col[u]^1); q.push(v);
        }
    }
}

int main() {
    //freopen("in.txt", "r", stdin);
    int T;
    scanf("%d", &T);
    while(T--) {
        tot = 0; memset(head, 0, sizeof(head)); memset(col, 0, sizeof(col));
        int n;
        scanf("%d", &n);
        for(int i = 1; i <= n; i++) scanf("%d", &w[i]);
        int u, v;
        for(int i = 1; i < n; i++) {
            scanf("%d%d", &u, &v);
            addEdge(u, v); addEdge(v, u);
        }
        bfs();
        int a = 0, b = 0;
        for(int i = 1; i <= n; i++) {
            if(col[i] == 2) a ^= w[i];
            else b ^= w[i];
        }
        if(a == b) printf("D\n");
        else printf("Q\n");
    }
}

HDU 6325 Problem G. Interstellar Travel

给定n个点,选择一条途经点x_{p_i}递增且\sum_{i=2}^k (x_{i-1}y_i – y_{i-1}x_i)最小的路径,在此基础上保证p_1, p_2, \cdots, p_k的字典序最小。

如果给此图形加入(x_{p_k},-\infty), (x_{p_1}, -\infty)这两个点,那么求和相当于加入一个常数,但是我们要求和的内容变成了图形有向面积的相反数。所以我们就是要求再加入这个个点之后选出若干个点使得图形的有向面积最大。
所以,维护一个上凸壳即可。(比赛的时候随意贪心写了一发就过了,并没有仔细分析Orz

/**
* Author : WNJXYK
* Date : 20180730
* Problem : G
**/

#include <bits/stdc++.h>

using namespace std;

#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
typedef vector<int> VI;
typedef long long LL;
typedef pair<int,int> PII;

const LL MOD=998244353;
const int MAXN=2e5+50;

LL powmod(LL a, LL b) {LL res=1;a%=MOD; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%MOD;a=a*a%MOD;}return res;}
LL gcd(LL a, LL b) { return b?gcd(b,a%b):a;}

int n;
struct Point{int x, y, idx;} p[MAXN];
inline bool cmp(const Point &a, const Point &b){
    if (a.x!=b.x) return a.x<b.x;
    if (a.y==b.y) return a.idx<b.idx;
    return a.y>b.y;
}

Point S[MAXN];
int t;

inline LL cValue(const Point &a, const Point &b){return 1LL*a.x*b.y-1LL*a.y*b.x;}

inline void solve(int T){
    sort(p+2, p+n, cmp);

    S[1]=p[1]; S[2]=p[2]; t=2;
    for (int i=3; i<=n; i++){
        if (p[i].x==p[i-1].x && i!=n) continue;
        while(t>=2
              && (
                cValue(S[t], p[i]) + cValue(S[t-1], S[t]) > cValue(S[t-1], p[i]) ||
                (cValue(S[t], p[i]) + cValue(S[t-1], S[t]) == cValue(S[t-1], p[i]) && S[t].idx>p[i].idx) ) ) t--;
        S[++t]=p[i];
    }

    for (int i=1; i<=t; i++) printf("%d%c", S[i].idx, (i==t?'\n':' '));
}

int main(){
    //freopen("in.txt" ,"r", stdin);
    //freopen("out.txt", "w", stdout);
    int T=0; scanf("%d", &T);
    for (int r=1; r<=T; r++){
        scanf("%d", &n);
        for (int i=1; i<=n; i++) scanf("%d%d", &p[i].x, &p[i].y), p[i].idx=i;
        solve(r);
    }
    return 0;
}

HDU 6327 Problem I. Random Sequence

给定一个序列,求\prod_{i=4}^n v[gcd(a_{i-3},a_{i-2},a_{i-1},a_{i})]
但是其中有一些位置的数值不知道,等概率为[1, m]的一个整数,求积期望。

我们可以发现不知道的位置之间相互是影响的,所以我们需要在状态中表示出前三个数字。
于是令dp[i][a][b][c]表示当前最后一个数字为c = a_ib = gcd(a_i, a_{i-1}), a = gcd(a_i, a_{i-1}, a_{i-2})的积期望。
我们可以通过枚举a_{i+1}的值,然后动态转移到状态dp[i+1][gcd(b, a_{i+1})][gcd(c, a_{i+1})][a_{i+1}]
dp[i+1][gcd(b, a_{i+1})][gcd(c, a_{i+1})][a_{i+1}] += dp[i][a][b][c] \times v[gcd(a_{i+1}, a)]

最后除以总方案数即可求得期望。

/**
* Author : WNJXYK
* Date : 20180731
* Problem : I
**/

#include <bits/stdc++.h>

using namespace std;

#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
typedef vector<int> VI;
typedef long long LL;
typedef pair<int,int> PII;

const LL MOD=1e9+7;
const int MAXN=1e2+50;

LL powmod(LL a, LL b) {LL res=1;a%=MOD; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%MOD;a=a*a%MOD;}return res;}
int ggcd(int a, int b) { return b?ggcd(b,a%b):a;}
int sgcd[MAXN][MAXN];
int gcd(int a, int b) { return sgcd[a][b];}

int n, m;
int num[MAXN], v[MAXN];
int dp[2][MAXN][MAXN][MAXN];
int tl[2][MAXN][MAXN][MAXN];

inline int get(int n, int x, int y, int z){
    if (tl[n&1][x][y][z]!=n) return 0;
    return dp[n&1][x][y][z];
}

inline void add(int n, int x, int y, int z, int v){
    if (tl[n&1][x][y][z]!=n) dp[n&1][x][y][z]=v, tl[n&1][x][y][z]=n; else{
        dp[n&1][x][y][z]+=v;
        if (dp[n&1][x][y][z]>=MOD) dp[n&1][x][y][z]-=MOD;
    }
}

vector<int> factors[MAXN];

inline void getFactors(int n){
    for (int i=1; i<=n; i++) factors[i].clear();
    for (int i=1; i<=n; i++) for (int j=i; j<=n; j+=i) factors[j].pb(i);
}

inline void solve(int T){
    memset(tl, 0, sizeof(tl));
    scanf("%d%d", &n, &m);
    for (int i=1; i<=n; i++) scanf("%d", num+i);
    for (int i=1; i<=m; i++) scanf("%d", v+i);

    for (int x=1; x<=m; x++){
        if (num[1]!=0 && x!=num[1]) continue;
        for (int y=1; y<=m; y++){
            if (num[2]!=0 && y!=num[2]) continue;
            for (int z=1; z<=m; z++){
                if (num[3]!=0 && z!=num[3]) continue;
                int c=z, b=gcd(c, y), a=gcd(b, x);
                add(3, a, b, c, 1);
            }
        }
    }

    for (int i=4; i<=n; i++) {
        int dLim=1, uLim=m; if (num[i]!=0) dLim=uLim=num[i];
        for (int c=1; c<=m; c++){
            if (num[i-1]&&c!=num[i-1]) continue;
            for (int _b=0, b=factors[c][_b]; _b<SZ(factors[c]); ++_b, b=factors[c][_b]){
                if (num[i-2] && gcd(num[i-2], c)!=b) continue;
                for (int _a=0, a=factors[b][_a]; _a<SZ(factors[b]); ++_a, a=factors[b][_a]){
                    if (num[i-3] && gcd(num[i-3], b)!=a) continue;
                    if (dp[(i-1)&1][a][b][c]==0) continue;
                    for (int now=dLim; now<=uLim; now++){
                        int z=now, y=gcd(z, c), x=gcd(y, b);
                        add(i, x, y, z, 1LL*get(i-1, a, b, c)*v[gcd(z, a)]%MOD);
                    }
                }
            }
        }
    }

    int ans=0;
    for (int c=1; c<=m; c++){
        if (num[n]&&c!=num[n]) continue;
        for (int _b=0, b=factors[c][_b]; _b<SZ(factors[c]); ++_b, b=factors[c][_b]){
            for (int _a=0, a=factors[b][_a]; _a<SZ(factors[b]); ++_a, a=factors[b][_a]){
                ans=ans+get(n, a, b, c);
                if (ans>=MOD) ans-=MOD;
            }
        }
    }

    int zCnt=0;
    for (int i=1; i<=n; i++) if (num[i]==0) zCnt++;
    ans=ans*powmod(powmod(m, zCnt), MOD-2)%MOD;

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

int main(){
    //freopen("in.txt" ,"r", stdin);
    //freopen("out.txt", "w", stdout);
    getFactors(100);
    for (int i=1; i<=100; i++)
        for (int j=1; j<=100; j++) sgcd[i][j]=ggcd(i, j);
    int T=0; scanf("%d", &T);
    for (int i=1; i<=T; i++) solve(i);
    return 0;
}

HDU 6330 Problem L. Visual Cube

绘制一个三维正方体的三视图

找一找规律,然后细心画一画即可。

/**
* Author : WNJXYK
* Date : 20180730
* Problem :
**/

#include <bits/stdc++.h>

using namespace std;

#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
typedef vector<int> VI;
typedef long long LL;
typedef pair<int,int> PII;

const LL MOD=998244353;
const int MAXN=1e3+50;

LL powmod(LL a, LL b) {LL res=1;a%=MOD; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%MOD;a=a*a%MOD;}return res;}
LL gcd(LL a, LL b) { return b?gcd(b,a%b):a;}

char matrix[MAXN][MAXN];

inline void solve(int T){
    int a, b, c; scanf("%d%d%d", &a, &b, &c);

    int n=2*b+(c*2+1), m=(a*2+1)+2*b;
    //printf("%d %d\n", n, m);

    // Head
    for (int i=1; i<=2*b; i++){
        for (int j=1; j<=2*b-i+1; j++) matrix[i][j]='.';
        if (i&1){
            int now=2*b-i+1;
            for (int j=1; j<=a; j++){
                matrix[i][++now]='+';
                matrix[i][++now]='-';
            }
            matrix[i][++now]='+';
        }else{
            int now=2*b-i+1;
            for (int j=1; j<=a; j++){
                matrix[i][++now]='/';
                matrix[i][++now]='.';
            }
            matrix[i][++now]='/';
        }
    }

    // Right
    for (int i=1; i<=2*b; i++){
        int now=i-1;
        if (i&1){
            for (int j=1; j<=c; j++){
                matrix[++now][m-i+1]='+';
                matrix[++now][m-i+1]='|';
            }
            matrix[++now][m-i+1]='+';
        }else{
            for (int j=1; j<=c; j++){
                matrix[++now][m-i+1]='/';
                matrix[++now][m-i+1]='.';
            }
            matrix[++now][m-i+1]='/';
        }
        for (int j=now+1; j<=n; j++) matrix[j][m-i+1]='.';
    }

    // Front
    for (int i=0; i<c; i++){
        for (int j=0; j<a; j++){
            matrix[2*b+i*2+1][j*2+1]='+';
            matrix[2*b+i*2+1][j*2+2]='-';
        }
        matrix[2*b+i*2+1][a*2+1]='+';
        for (int j=0; j<a; j++){
            matrix[2*b+i*2+2][j*2+1]='|';
            matrix[2*b+i*2+2][j*2+2]='.';
        }
        matrix[2*b+i*2+2][a*2+1]='|';
    }
    for (int j=0; j<a; j++) matrix[n][j*2+1]='+', matrix[n][j*2+2]='-';
    matrix[n][a*2+1]='+';

    for (int i=1; i<=n; i++){
        for (int j=1; j<=m; j++){
            printf("%c", matrix[i][j]);
        }
        printf("\n");
    }
}

int main(){
    //freopen("in.txt" ,"r", stdin);
    //freopen("out.txt", "w", stdout);
    int T=0; scanf("%d", &T);
    for (int i=1; i<=T; i++) solve(i);
    return 0;
}

HDU 6331 Problem M. Walking Plan

给定一个n, n\leq 50的图,q个询问问s \rightarrow t至少经过k条边的最短路是多少。

因为k=10000并不大,我们可以对k进行分块,然后预处理处这两部分答案:
1. 刚好经过p\cdot 100, (q \leq 100)步,任意两点之间的最短路F[p][i][j]
2. 至少经过q, (q\leq 100)步,任意两点之间的最短路G[q][i][j]

然后对于每一个询问,我们只需要枚举中间点u,然后求得\min\{F[k/100][s][u]+G[k\%100][u][t]\}即可。

/**
* Author : WNJXYK
* Date : 20180730
* Problem : M
**/

#include <bits/stdc++.h>

using namespace std;

#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
typedef vector<int> VI;
typedef long long LL;
typedef pair<int,int> PII;

const LL MOD=998244353;
const int MAXN=55;

LL powmod(LL a, LL b) {LL res=1;a%=MOD; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%MOD;a=a*a%MOD;}return res;}
LL gcd(LL a, LL b) { return b?gcd(b,a%b):a;}

int n, m, Q;
int dis[MAXN][MAXN];
int tmp[MAXN][MAXN], mat[MAXN][MAXN];

inline void multi(int A[MAXN][MAXN], int B[MAXN][MAXN], int C[MAXN][MAXN]){
    for (int i=1; i<=n; i++){
        for (int j=1; j<=n; j++){
            tmp[i][j]=-1;
            for (int k=1; k<=n; k++){
                if (A[i][k]==-1 || B[k][j]==-1) continue;
                if (tmp[i][j]==-1 || tmp[i][j]>A[i][k]+B[k][j]) tmp[i][j]=A[i][k]+B[k][j];
            }
        }
    }

    for (int i=1; i<=n; i++) for (int j=1; j<=n; j++) C[i][j]=tmp[i][j];
}

int f[155][MAXN][MAXN], g[155][MAXN][MAXN];

inline void presolve(){
    for (int i=1; i<=n; i++) for (int j=1; j<=n; j++) f[1][i][j]=f[0][i][j]=-1, mat[i][j]=dis[i][j];
    for (int i=1; i<=n; i++) f[0][i][i]=0, f[1][i][i]=0;
    int p=100;
    while(p){
        if (p&1) multi(f[1], mat, f[1]);
        multi(mat, mat, mat), p/=2;
    }
    //for (int i=1; i<=n; i++){ for (int j=1; j<=n; j++) printf("%d ",f[1][i][j]); printf("\n");}
    for (int k=2; k<=100; k++) multi(f[k-1], f[1], f[k]);

    for (int i=1; i<=n; i++) for (int j=1; j<=n; j++) g[0][i][j]=-1;
    for (int i=1; i<=n; i++) g[0][i][i]=0;
    for (int k=1; k<=150; k++) multi(g[k-1], dis, g[k]);
    for (int k=150; k>=1; k--){
        for (int i=1; i<=n; i++){
            for (int j=1; j<=n; j++){
                if (g[k][i][j]==-1) continue;
                if (g[k-1][i][j]==-1 || g[k-1][i][j]>g[k][i][j]) g[k-1][i][j]=g[k][i][j];
            }
        }
    }
    //for (int i=1; i<=n; i++){ for (int j=1; j<=n; j++) printf("%d ",g[0][i][j]); printf("\n");}
}

inline void solve(int T){
    scanf("%d%d", &n, &m);
    for (int i=1; i<=n; i++) for (int j=1; j<=n; j++) dis[i][j]=-1;
    for (int i=1; i<=m; i++){
        int x, y, w; scanf("%d%d%d", &x, &y, &w);
        if (dis[x][y]==-1 || dis[x][y]>w) dis[x][y]=w;
    }

    presolve();

    scanf("%d", &Q);
    for (int i=1; i<=Q; i++){
        int s, t, k; scanf("%d%d%d", &s, &t, &k);
        int pk=k/100, yk=k%100, ans=-1;
        for (int u=1; u<=n; u++){
            if (f[pk][s][u]==-1 || g[yk][u][t]==-1) continue;
            if (ans==-1 || ans>f[pk][s][u]+g[yk][u][t]) ans=f[pk][s][u]+g[yk][u][t];
        }
        printf("%d\n", ans);
    }
}

int main(){
    //freopen("M.in" ,"r", stdin);
    //freopen("M.out", "w", stdout);
    int T=0; scanf("%d", &T);
    for (int i=1; i<=T; i++) solve(i);
    return 0;
}

赞赏
https://secure.gravatar.com/avatar/f83b57c055136369e9feba5d6671d6b5?s=256&r=g

WNJXYK

文章作者

一个蒟蒻

推荐文章

发表评论

textsms
account_circle
email

WNJXYKのBlog

2018 Multi-University Training Contest 3
HDU 6319 Problem A. Ascending Rating 给定一个长度为$$n(n\leq 10^{7})$$的序列,问所有长度为$$m$$的子区间内,最大值与扫描最大值中的更新次数。 反向维护一个单调队列就可以了,然…
扫描二维码继续阅读
2018-07-31
<--! http2https -->