【解题报告】ZJNU 个人赛一 (2021)

【解题报告】ZJNU 个人赛一 (2021暑假)

  • 尽可能把代码中的注释都保留了,虽然有些注释和正确代码的方向没什么关系,但是能保留出做题中的中间想法。

A

题意

  • 给定 n n n 的二进制表示和三进制表示。
    但这两个表示中,都有一位数字是错误的。
    求原来的 n n n
  • n ≤ 1 0 9 n\le 10^9 n≤109

思路

  • 分别枚举两个表示中,哪一位出错,以及修改后改成什么。
    然后判断修改后数字是否相同即可。可以 O ( 1 ) O(1) O(1) 去判。

代码

  • 时间复杂度: O ( log ⁡ 2 n × log ⁡ 3 2 n ) , 就 1.1 e 4 O(\log_2n\times \log_3^2n),就1.1e4 O(log2​n×log32​n),就1.1e4次运算。
#include <bits/stdc++.h>
#define IOS ios::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
using namespace std;
typedef long long ll;
void show(){std::cerr << endl;}template<typename T,typename... Args>void show(T x,Args... args){std::cerr << "[ " << x <<  " ] , ";show(args...);}

const int MAX = 60;
const int MOD = 1e9+7;
const int INF = 0x3f3f3f3f;
const ll LINF = 0x3f3f3f3f3f3f3f3f;
const double EPS = 1e-5;

int b2[MAX],b3[MAX];

int main()
{
    b2[0] = 1;b3[0] = 1;

    string ta,tb;
    int la,lb;
    cin >> ta >> tb;
    la = ta.size();lb=tb.size();

    int n1 = 0,n2 = 0;
    int st = 0;
    for(int i = la-1;i>=0;--i){
        n1 = n1 + b2[st] * (ta[i] - '0');
        st++;
        b2[st] = b2[st-1] * 2;
    }
    st = 0;
    for(int i = lb-1;i>=0;--i){
        n2 = n2 + b3[st] * (tb[i] - '0');
        st++;
        b3[st] = b3[st-1] * 3;
    }
//    show(n1,n2);
    int nn1=0,nn2=0;

    for(int i = la-1;i>=0;--i){
        nn1=n1;

        if(ta[i] == '1'){
            nn1 -= b2[la-1-i];
        }else{
            nn1 += b2[la-1-i];
        }

        for(int j = lb-1;j>=0;--j){
            for(int k = 0;k <= 2;++k){
                if(k != (tb[j]-'0')){
                    nn2 = n2-(tb[j]-'0')*b3[lb-1-j] + k*b3[lb-1-j];

                    if(nn1 == nn2){
                        cout << nn1;
                        return 0;
                    }
                }
            }
        }
    }
    return 0;
}

B

题意

  • 给你一个长度为 n n n 的序列 H H H
    给你一个 X X X
    问你其中有多少个连续区间,满足这个区间中所有数字排序后的中位数 ≥ X \ge X ≥X
  • 1 ≤ N ≤ 1 0 5 1\le N\le 10^5 1≤N≤105
    1 ≤ H i ≤ 1 0 9 1\le H_i\le 10^9 1≤Hi​≤109
    1 ≤ X ≤ 1 0 9 1\le X\le 10^9 1≤X≤109

思路

  • 首先容易得到,若 H i ≥ X H_i\ge X Hi​≥X,我们令 A i = 1 A_i=1 Ai​=1
    否则,我们令 A i = − 1 A_i=-1 Ai​=−1
    考虑区间右端点为 i i i,满足区间和 = x =x =x 的区间个数为 s h u [ i ] [ x ] shu[i][x] shu[i][x]
    我们答案容易得到为 ∑ s h u [ i ] [ j ≥ 0 ] \sum shu[i][j\ge0] ∑shu[i][j≥0]
  • 我们考虑转移。如果当前 A i = 1 A_i=1 Ai​=1 时:
    s h u [ i − 1 ] [ x ] shu[i-1][x] shu[i−1][x] 转移到 s h u [ i ] [ x + 1 ] shu[i][x+1] shu[i][x+1]
    然后 s h u [ i ] [ 1 ] shu[i][1] shu[i][1] 额外增加1,因为多了一个长度为1的区间 [ i , i ] [i,i] [i,i]
  • 如果当前 A i = − 1 A_i=-1 Ai​=−1 时:
    s h u [ i − 1 ] [ x ] shu[i-1][x] shu[i−1][x] 转移到 s h u [ i ] [ x − 1 ] shu[i][x-1] shu[i][x−1]
    然后 s h u [ i ] [ − 1 ] shu[i][-1] shu[i][−1] 额外增加1。
  • 每次都把 s h u [ ] [ ] shu[][] shu[][] 向左/右 移动肯定不好做,但是我们可以移动假想原点 o r i ori ori,原点移动就相当于 s h u [ ] [ ] shu[][] shu[][] 数组移动了。
  • 其他的就是每次单点更新 + 1 / − 1 +1/-1 +1/−1 ,还有求区间和 s h u [ i ] [ j ≥ 0 ] shu[i][j\ge0] shu[i][j≥0],用一个线段树即可。
    注意一下数组下标不能为负数,集体向右移动一段即可。

代码

  • 时间复杂度: O ( N log ⁡ N ) O(N\log N) O(NlogN)
#include <bits/stdc++.h>
#define IOS ios::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
using namespace std;
typedef long long ll;
void show(){std::cerr << endl;}template<typename T,typename... Args>void show(T x,Args... args){std::cerr << "[ " << x <<  " ] , ";show(args...);}

const int MAX = 1e5+50;
const int MOD = 1e9+7;
const int INF = 0x3f3f3f3f;
const ll LINF = 0x3f3f3f3f3f3f3f3f;
const double EPS = 1e-5;

#define ls (p<<1)
#define rs (p<<1|1)
#define md ((l+r)>>1)

const int YOU = 2e5+2;
int aa[MAX];

int tree[YOU*4];
void push_up(int p){
    tree[p] = tree[ls] + tree[rs];
}
void build(int p,int l,int r){
    if(l == r){
        tree[p] = 0;
        return;
    }
    build(p,l,md);
    build(p,md+1,r);
    push_up(p);
}
void update(int p,int l,int r,int u,ll k){
    if(l == r){
        tree[p] += k;
        return;
    }
    if(md >= u)update(ls,l,md,u,k);
    else update(rs,md+1,r,u,k);
    push_up(p);
}
ll query(int p,int l,int r,int qx,int qy){
    if(qx <= l && qy >= r){
        return tree[p];
    }
    ll res = 0;
    if(qx <= md)res += query(ls,l,md,qx,qy);
    if(qy >  md)res += query(rs,md+1,r,qx,qy);
    return res;
}


int main()
{
    int n,x;
    scanf("%d%d",&n,&x);
    for(int i = 1;i <= n;++i){
        int t;scanf("%d",&t);
        if(t >= x)aa[i] = 1;
        else aa[i] = -1;
    }
    build(1,1,YOU);
    int ori = 1e5+1;
    ll ans = 0;
    for(int i = 1;i <= n;++i){
        if(aa[i] == 1){
            ori--;
            update(1,1,YOU,ori+1,1);
            ans += query(1,1,YOU,ori,YOU);
        }else{
            ori++;
            update(1,1,YOU,ori-1,1);
            ans += query(1,1,YOU,ori,YOU);
        }
        //show(ans);
    }
    printf("%lld",ans);
    return 0;
}
/**
4 6
0 0 0 0
*/

C

  • 暴力

D

题意

  • n n n 个点,每个点有一个坐标 x i x_i xi​ 和种类 y i y_i yi​
    求最短的区间长度,其中覆盖了所有种类的点。
  • 1 ≤ n ≤ 5 e 4 1\le n\le 5e4 1≤n≤5e4

思路

  • 尺取即可。
    注意一下跳出条件。

代码

  • 时间复杂度: O ( n ) O(n) O(n)
#include <bits/stdc++.h>
#define IOS ios::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
using namespace std;
typedef long long ll;
void show(){std::cerr << endl;}template<typename T,typename... Args>void show(T x,Args... args){std::cerr << "[ " << x <<  " ] , ";show(args...);}

const int MAX = 5e4+50;
const int MOD = 1e9+7;
const int INF = 0x3f3f3f3f;
const ll LINF = 0x3f3f3f3f3f3f3f3f;
const double EPS = 1e-5;

struct node{
    int p;
    int id;
    bool operator <(const node &ND)const{
        return p < ND.p;
    }
}aa[MAX];
map<int,int>M;
int main()
{
    int n,cnt = 0;
    scanf("%d",&n);
    for(int i = 1;i <= n;++i){
        scanf("%d%d",&aa[i].p,&aa[i].id);
        M[aa[i].id]++;
        if(M[aa[i].id] == 1)cnt++;
    }
    sort(aa+1,aa+1+n);
//    for(int i = 1;i <= n;++i){
//        printf("%d %d\n",aa[i].p,aa[i].id);
//    }
    M.clear();
    int L = 1,R = 0;
    int ans = INF;
    int now = 0;
    while(1){
        while(R < n && now < cnt){
            R++;
            M[aa[R].id]++;
            if(M[aa[R].id] == 1)now++;
        }
        if(R == n){
            if(now == cnt)ans = min(ans,aa[R].p - aa[L].p);
            else break;
        }
        while(L <= R && now == cnt){
            //show(L,R);
            ans = min(ans,aa[R].p - aa[L].p);
            M[aa[L].id]--;
            if(M[aa[L].id] == 0)now--;
            L++;
        }
    }

    printf("%d",ans);
    return 0;
}
/**
5
1 1
2 1
3 1
4 1
5 2
*/

E

题意

  • n × m n\times m n×m 的图,要么为 X X X 要么为 . . .
    其中有两个 X X X 的连通块
    问你最少把多少个点变成 X X X ,使得变成一个 X X X 的连通块
  • n , m ≤ 50 n,m\le 50 n,m≤50

思路

  • B F S BFS BFS 让两坨 X X X 相遇即可。

F

  • 随便数时间就行了。
    我暴力数的,其实可以 O ( 1 ) O(1) O(1) 判…
int main()
{
    int d,h,m;
    scanf("%d%d%d",&d,&h,&m);
    if(d == 11 && h == 11 && m < 11){
        puts("-1");
    }else if(d == 11 && h < 11){
        puts("-1");
    }else{
        int ans = 0;
        int dd,hh,mm;
        for(dd = 11;dd <= d;++dd){
            if(dd == 11)hh = 11;
            else hh = 0;

            for(;hh <= 23;++hh){

                if(dd == 11 && hh == 11)mm = 11;
                else mm = 0;

                for(;mm <= 59;++mm){
                    ans++;
                    if(dd == d && hh == h && mm == m){
                        printf("%d",ans-1);
                        return 0;
                    }
                }
            }
        }
    }
    return 0;
}

H

  • n × m n\times m n×m 的图,要么为 X X X 要么为 . . .
    其中有个 X X X 的连通块
    问你最少把多少个点变成 X X X ,使得变成一个 X X X 的连通块
  • n , m ≤ 50 n,m\le 50 n,m≤50

思路

  • 首先受上一道题目的影响,我们想枚举其中的每一块,然后算出该块到其他两块的最短路,然后这两个加起来成为最后答案,取小。
    但是这样只有 67 67 67 分,我们考虑如下图:
3 5
X...X
.....
..X..
我们原来跑出来的:6
最优的策略:4
XXXXX
..X..
..X..
  • 有三坨 X X X,我们给它们编号为 1 、 2 、 3 1、2、3 1、2、3
    可能1到2的最短路和1到3的最短路有公共部分
    我们想成:先1到2的最短路中间加了一座桥,然后3直接跑到了桥上。
    容易想到,我们移动这座最短桥然后让3到其的距离变短,明显开销是更大的。
    也就是说,我们先让 1 到 2 跑好最短路,中间的所有最短桥 我们都给他加上去,使得1和2变成新的一坨 X X X,然后和3去跑bfs即可。

代码

  • 时间复杂度: O ( n m ) O(nm) O(nm)
#include <bits/stdc++.h>
#define IOS ios::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
using namespace std;
typedef long long ll;
void show(){std::cerr << endl;}template<typename T,typename... Args>void show(T x,Args... args){std::cerr << "[ " << x <<  " ] , ";show(args...);}

const int MAX = 52;
const int MOD = 1e9+7;
const int INF = 0x3f3f3f3f;
const ll LINF = 0x3f3f3f3f3f3f3f3f;
const double EPS = 1e-5;

int n,m;
char aa[MAX][MAX];
char bb[MAX][MAX];
int dis[MAX][MAX][4];
int dis2[MAX][MAX];
int col[MAX][MAX];
set<pair<int,int> >V[4];
int dx[]={-1,1,0,0};
int dy[]={0,0,-1,1};
void init(){
    for(int i = 1;i <= n;++i)
    for(int j = 1;j <= m;++j)
        aa[i][j] = bb[i][j];
}
void gei(int c){
    for(int i = 1;i <= n;++i)
    for(int j = 1;j <= m;++j)
        dis2[i][j] = dis[i][j][c];
}
void dfs(int x,int y,int c){
    dis[x][y][c] = 0;
    col[x][y] = c;
    V[c].insert(make_pair(x,y));
    for(int i = 0;i < 4;++i){
        int tx = x + dx[i];
        int ty = y + dy[i];
        if(tx < 1 || ty < 1 || tx > n || ty > m)continue;
        if(bb[tx][ty] == '.')continue;
        if(dis[tx][ty][c] == INF)dfs(tx,ty,c);
    }
}
void pre(int c){
    bool fd = false;
    for(int i = 1;i <= n;++i){
        for(int j = 1;j <= m;++j){
            dis[i][j][c] = INF;
        }
    }
    for(int i = 1;!fd && i <= n;++i){
        for(int j = 1;!fd && j <= m;++j){
            if(bb[i][j] == 'X' && col[i][j] == 0){
                fd = true;
                dfs(i,j,c);
            }
        }
    }
}
queue<pair<int,int> >Q;
int bfs(int c){
    int res = INF;
    for(auto it : V[c]){
        Q.push(it);
    }

    while(!Q.empty()){
        int x = Q.front().first;
        int y = Q.front().second;
        Q.pop();
        if(dis2[x][y] != 0 && aa[x][y] == 'X'){
            res = min(res,dis2[x][y]-1);
            continue;
        }

        for(int i = 0;i < 4;++i){
            int tx = x + dx[i];
            int ty = y + dy[i];
            if(tx < 1 || ty < 1 || tx > n || ty > m)continue;
            if(dis2[tx][ty] > dis2[x][y] + 1){
                dis2[tx][ty] = dis2[x][y] + 1;
                Q.push(make_pair(tx,ty));
            }
        }
    }
    return res;
}
int bfs(int c1,int c2){
    int res = INF;
    for(auto it : V[c1]){
        Q.push(it);
    }

    while(!Q.empty()){
        int x = Q.front().first;
        int y = Q.front().second;
        Q.pop();
        if(col[x][y] == c2){
            res = min(res,dis2[x][y]-1);
            continue;
        }

        for(int i = 0;i < 4;++i){
            int tx = x + dx[i];
            int ty = y + dy[i];
            if(tx < 1 || ty < 1 || tx > n || ty > m)continue;
            if(dis2[tx][ty] > dis2[x][y] + 1){
                dis2[tx][ty] = dis2[x][y] + 1;
                Q.push(make_pair(tx,ty));
            }
        }
    }
    map<int,map<int,int> >VIS;		// 注意这个加上,否则就 MLE了,因为是倒着把图变成 X 的
    for(auto it : V[c2]){
        if(dis2[it.first][it.second] == res + 1)Q.push(it),VIS[it.first][it.second] = true;
    }
    while(!Q.empty()){
        int x = Q.front().first;
        int y = Q.front().second;
        Q.pop();
        aa[x][y] = 'X';
        for(int i = 0;i < 4;++i){
            int tx = x + dx[i];
            int ty = y + dy[i];
            if(tx < 1 || ty < 1 || tx > n || ty > m)continue;
            if(dis2[tx][ty] == dis2[x][y] - 1 && !VIS[tx][ty]){
                VIS[tx][ty] = 1;
                Q.push(make_pair(tx,ty));
            }
        }
    }
    return res;
}
int ans = INF;
void dw(){
    puts("---");
    for(int i = 1;i <= n;++i){
        for(int j = 1;j <= m;++j){
            cout << aa[i][j];
        }
        puts("");
    }
    puts("---");
}
void work(int c){
    int ans1,ans2;
    init();
    if(c == 1){
        gei(2);
//        dw();
        ans1 = bfs(2,3);
//        dw();
        gei(1);
        ans2 = bfs(1);
    }else if(c == 2){
        gei(1);
        ans1 = bfs(1,3);
        gei(2);
        ans2 = bfs(2);
    }else{
        gei(1);
        ans1 = bfs(1,2);
        gei(3);
        ans2 = bfs(3);
    }
    ans = min(ans,ans1+ans2);
//    show(ans1,ans2);
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i = 1;i <= n;++i){
        scanf("%s",bb[i]+1);
    }

    for(int i = 1;i <= 3;++i){
        pre(i);
    }
    for(int i = 1;i <= 3;++i){
        work(i);
    }
    printf("%d",ans);
    return 0;
}
/**
3 5
X...X
.....
..X..

5 1
X
.
X
.
X
*/
  • 鬼知道为什么我写了那么长///

I

题意

  • 有竖着和横着的 n n n 个线段。竖着的线段 x x x 都不相同,横着的线段 y y y 都不相同。
    求最多可以选出多少个线段,让他们两两不想交。
  • 1 ≤ n ≤ 250 1\le n\le 250 1≤n≤250

思路

  • 选了某条线段就不能选这条线段相交的其他所有线段,容易想到是一个最大独立集的问题。
    由于竖着和横着的性质非常好,这里是一个二分图,可以直接用匈牙利二分图匹配去做,最大独立集=|V|-最大匹配。

代码

#include <bits/stdc++.h>
#define IOS ios::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
using namespace std;
typedef long long ll;
void show(){std::cerr << endl;}template<typename T,typename... Args>void show(T x,Args... args){std::cerr << "[ " << x <<  " ] , ";show(args...);}

const int MAX = 300;
const int MOD = 1e9+7;
const int INF = 0x3f3f3f3f;
const ll LINF = 0x3f3f3f3f3f3f3f3f;
const double EPS = 1e-5;

struct node{
    int sx,sy;
    int ex,ey;
    int st;
}aa[MAX];

bool M[MAX][MAX];
bool vis[MAX];
int match[MAX];
int sum = 0;
int n;
bool dfs(int u){
    for(int v=1;v<=n;++v){
        if(M[u][v] && !vis[v]){
            vis[v] = true;
            if(match[v] == -1 || dfs(match[v])){
                match[v] = u;
                return true;
            }
        }
    }
    return false;
}

void check(int i,int j){
    if(aa[i].st == aa[j].st)return;
    if(aa[i].st == 1)swap(i,j);
    if(aa[i].sx >= aa[j].sx && aa[i].sx <= aa[j].ex){
        if(aa[i].sy <= aa[j].sy && aa[i].ey >= aa[j].sy){
            M[i][j] = true;
            //show(i,j);
        }
    }
}

int main()
{
    scanf("%d",&n);
    for(int i = 1;i <= n;++i){
        scanf("%d%d%d%d",&aa[i].sx,&aa[i].sy,&aa[i].ex,&aa[i].ey);

        if(aa[i].sx == aa[i].ex){
            aa[i].st = 0;
            if(aa[i].sy > aa[i].ey)swap(aa[i].sy,aa[i].ey);
        }else {
            aa[i].st = 1;
            if(aa[i].sx > aa[i].ex)swap(aa[i].sx,aa[i].ex);
        }
    }

    for(int i = 1;i <= n;++i){
        for(int j = i+1;j <= n;++j){
            check(i,j);
            //if(M[i][j])show(i,j);
        }
    }

    memset(match,-1,sizeof(match));
    for(int i = 1;i <= n;++i){
        memset(vis,0,sizeof(vis));
        if(dfs(i))sum++;
    }

    //show(sum);

//    for(int i = 1;i <= n;++i){
//        bool dl = true;
//        for(int j = 1;j <= n;++j){
//            if(M[i][j] || M[j][i]){
//                dl = false;
//                break;
//            }
//        }
//        if(dl){
//            sum++;
//        }
//    }

    printf("%d",n-sum);
    return 0;
}
/**
1
0 0 1 1

4
0 0 5 0
2 -1 2 1

10 0 15 0
13 -1 13 1

2
0 0 5 0
2 -1 2 1
*/

K

题意

  • 有 N N N 个方块,每个有边长 A i A_i Ai​,给你一个 M M M
    你需要选出一些方块,让他们的边长变成 A i ′ A_i^\prime Ai′​,花费为 ( A i − A i ′ ) 2 (A_i-A_i^\prime)^2 (Ai​−Ai′​)2
    问最后所有方块的面积变成 M M M 的最小花费
  • 1 ≤ N ≤ 10 1\le N\le 10 1≤N≤10
    1 ≤ M ≤ 1 0 4 1\le M\le 10^4 1≤M≤104
    1 ≤ A i ≤ 100 1\le A_i\le 100 1≤Ai​≤100

思路

  • 首先,爆搜 O ( 1 0 x ) O(10^x) O(10x) 这里 x x x 很大,肯定不行 (会 T 四个点)
    考虑一般的状态保存, d p [ i ] [ j ] dp[i][j] dp[i][j] 表示目前搞定了前 i i i 个方块,得到的面积为 j j j 的最小花费。
    状态数已经 O ( N M ) O(NM) O(NM)了,但是转移的时间复杂度不会很大
    因为我们枚举的是边长,边长不会 > M >\sqrt M >M
    所以就不会有什么问题

代码

  • 时间复杂度: O ( N M M ) O(NM\sqrt M) O(NMM ​)
#include <bits/stdc++.h>
#define IOS ios::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
using namespace std;
typedef long long ll;
void show(){std::cerr << endl;}template<typename T,typename... Args>void show(T x,Args... args){std::cerr << "[ " << x <<  " ] , ";show(args...);}

const int MAX = 30;
const int MOD = 1e9+7;
const int INF = 0x3f3f3f3f;
const ll LINF = 0x3f3f3f3f3f3f3f3f;
const double EPS = 1e-5;

int aa[MAX];
int n,m;
ll dp[11][10050];

int main()
{
    scanf("%d%d",&n,&m);
    for(int i = 1;i <= n;++i)scanf("%d",&aa[i]);

    for(int i = 0;i <= n;++i)
    for(int j = 0;j <= m;++j)
        dp[i][j] = LINF;
    dp[0][0] = 0;
    for(int i = 1;i <= n;++i){
        for(int j = 1;j <= m;++j){
            for(ll k = 1;k*k <= m && j-k*k>=0;++k){
                dp[i][j] = min(dp[i][j],dp[i-1][j-k*k] + (aa[i] - k) * (aa[i] - k));
            }
        }
    }
    if(dp[n][m] >= LINF){
        puts("-1");
        return 0;
    }
    printf("%lld",dp[n][m]);
    return 0;
}
/**
1 2
1
*/
上一篇:13-jpql查询-分页查询


下一篇:一道红题.