本文主要是介绍2021“MINIEYE杯”中国大学生算法设计超级联赛（3）部分题解，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

文章目录

• D.Game on Plane
• G.Photoshop Layers
• I.Rise in Price
• J.Road Discount
• K.Segment Tree with Pruning

D.Game on Plane

• 题意
  给你 n n n条直线，现在需要 A l i c e Alice Alice需要从中选出 k k k条直线，之后 B o b Bob Bob生成一条直线 l l l，其中贡献为这 k k k条直线与 l l l相交的数量，而 A l i c e Alice Alice想最大化贡献， B o b Bob Bob想最小化贡献，求 k k k为 [ 1 , n ] [1,n] [1,n]时的贡献。

• 解题思路
  我们知道，两条直线存在公共点当且仅当它们重合或者它们斜率不同。对于 A l i c e Alice Alice自然是尽可能最小化斜率出现次数的最大值，而 B o b Bob Bob自然是选择其中斜率出现次数最多的最大值。故我们可以将斜率存储起来，然后每种直线依次选择即可。

• AC代码

/**
  *@filename:D_Game_on_Plane
  *@author: pursuit
  *@csdn:unique_pursuit
  *@email: 2825841950@qq.com
  *@created: 2021-07-31 09:14
**/
#include <bits/stdc++.h>
#define x first 
#define y second

using namespace std;

typedef pair<int,int> pii;
typedef long long ll;
const int N = 100000 + 5;
const int P = 1e9+7;

int t,n;
int f[N];
pii v[N];
void solve(){
    sort(v + 1,v + 1 + n);
    memset(f,0,sizeof(f));
    int i,j,k;
    for(i = 1; i <= n; i = j){
        for(j = i; j <= n && v[i] == v[j]; ++ j){
            //计算从i开始有几条斜率相同的直线。
        }
        for(k = 1; k <= j - i; ++ k){
            f[k] ++;
        }
    }
    for(i = j = 1; i <= n; ++ i){
        //i为可选择的直线数。
        while(!f[j]){
            j ++;
        }
        f[j] --;
        printf("%d\n", i - j);
    }
}
int main(){
    scanf("%d", &t);
    pii a,b;
    while(t -- ){
        scanf("%d", &n);
        for(int i = 1; i <= n; ++ i){
            scanf("%d%d%d%d", &a.x, &a.y, &b.x, &b.y);
            int dx = a.x - b.x,dy = a.y - b.y;
            if(dx == 0){
                //说明是垂直的。
                dy = 1;
            }
            else if(dy == 0){
                //说明是水平的。
                dx = 1;
            }
            else{
                //将dx，dy统一化。
                if(dx < 0){
                    dx = -dx, dy = -dy;
                }
                int gcd = __gcd(abs(dx),abs(dy));
                dx /= gcd, dy /= gcd;
            }
            v[i] = pii(dx,dy);
        }
        solve();
    }
    return 0;
}

G.Photoshop Layers

• 题意
  给你 n n n张图层，每张图层都有 r , g , b r,g,b r,g,b三种颜色属性还有一个特征 m m m，即为 1 1 1说明不受前面图层影响，为 2 2 2说明受前面图层影响。问 [ l , r ] [l,r] [l,r]这区间的图层依次放置后最后的 r , g , b r,g,b r,g,b值。

• 解题思路
  妥妥的前缀和，只不过我们需要注意分割点，记录每个图层最近出现 1 1 1的图层下标。然后利用前缀和计算即可。

• AC代码

/**
  *@filename:G_Photoshop_Layers
  *@author: pursuit
  *@csdn:unique_pursuit
  *@email: 2825841950@qq.com
  *@created: 2021-07-27 13:43
**/
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
const int N = 100000 + 5;
const int P = 1e9+7;

int t,n,q,x,f[N];
struct node{
    int m,r,g,b;
}a[N];
int change(int x){
    return x < 255 ? x : 255;
}
void solve(){
    int l,r;
    while(q -- ){
        scanf("%d%d", &l, &r);
        int x = f[r];
        if(x >= l){
            //说明中间出现1，中断了。
            l = x;
        }
        printf("%02X%02X%02X\n", change(a[r].r - a[l - 1].r), change(a[r].g - a[l - 1].g), change(a[r].b - a[l - 1].b));
    }
}
int main(){
    scanf("%d", &t);
    while(t -- ){
        scanf("%d%d", &n, &q);
        for(int i = 1; i <= n; ++ i){
            scanf("%d%X", &a[i].m, &x);
            a[i].b = x & 255;
            x >>= 8;
            a[i].g = x & 255;
            x >>= 8;
            a[i].r = x & 255;
            a[i].b += a[i - 1].b, a[i].g += a[i - 1].g, a[i].r += a[i - 1].r;
            if(a[i].m == 1){
                f[i] = i;
            }
            else{
                f[i] = f[i - 1];
            }
        }
        solve();
    }
    return 0;
}

I.Rise in Price

• 题意
  有 n × n n\times n n×n的网格地图，起始点在 ( 1 , 1 ) (1,1) (1,1)，终止点在 ( n , n ) (n,n) (n,n)，其中只能向东或南方向移动，每个 ( i , j ) (i,j) (i,j)都有两个个值 a i , b i a_i,b_i ai​,bi​，分别代表钻石数量和可上升的单价，问最终到达终止点可售卖得到的最大价值。

• 解题思路
  这是最经典的 D P DP DP问题，只不过现在每个点有两个参数影响，所以一个状态可以有好多候选解，我们可以用 v e c t o r vector vector存储候选解，当然我们也要剔除不可能的解，即一个解两个参数值都小于等于另一个解，那这个是不可能的。按题意进行状态转移即可。

• AC代码

/**
  *@filename:I Rise in Price
  *@author: pursuit
  *@csdn:unique_pursuit
  *@email: 2825841950@qq.com
  *@created: 2021-07-27 12:08
**/
#include <bits/stdc++.h>
#define a first 
#define b second
using namespace std;

typedef pair<int,int> pii;
typedef long long ll;
const int N = 100 + 5;
const int P = 1e9+7;

int t,n,a[N][N],b[N][N];
int cnt;//(i,j)可选状态的大小。
vector<pii> f[N][N];//f[i][j]表示(i,j)的可选状态。
pii pool[N * 10000];//可选状态池。
void push(pii x){
    while(cnt && pool[cnt].b <= x.b){
        cnt --;
    }
    pool[++ cnt] = x;//加入新的数。
}
void judge(int x,int y){
    int i = 0, j = 0;
    cnt = 0;
    //这里我们默认让a小的先进入pool。然后比较第二维的，若先前进入pool的b也比别的状态小，那就剔除掉。
    while(i < f[x - 1][y].size() && j < f[x][y - 1].size()){
        push(f[x - 1][y][i].a < f[x][y - 1][j].a ? f[x - 1][y][i ++ ] : f[x][y - 1][j ++ ]);
    }
    while(i < f[x - 1][y].size())push(f[x - 1][y][i ++]);
    while(j < f[x][y - 1].size())push(f[x][y - 1][j ++]);
    f[x][y].clear();
    //cout << "judge : " << endl;
    for(i = 1; i <= cnt; ++ i){
        f[x][y].push_back(pool[i]);
        //cout << pool[i].a << " " << pool[i].b << endl;
    }
}
void solve(){
    f[1][1].clear();
    f[1][1].push_back({a[1][1],b[1][1]});
    for(int i = 1; i <= n; ++ i){
        for(int j = 1; j <= n; ++ j){
            if(i == j && i == 1)continue;
            if(i == 1){
                //说明只能水平转移。
                f[i][j] = f[i][j - 1];
            }
            else if(j == 1){
                //说明只能垂直转移。
                f[i][j] = f[i - 1][j];
            }
            else{
                //计算可选状态。
                judge(i,j);
            }
            for(int k = 0; k < f[i][j].size(); ++ k){
                f[i][j][k].a += a[i][j],f[i][j][k].b += b[i][j];
            }
        }
    }
    ll maxx = 0;
    for(int i = 0; i < f[n][n].size(); ++ i){
        maxx = max(maxx,1LL * f[n][n][i].a * f[n][n][i].b);
        //cout << maxx << endl;
    }
    printf("%lld\n", maxx);
}
int main(){
    scanf("%d", &t);
    while(t -- ){
        scanf("%d", &n);
        for(int i = 1; i <= n; ++ i){
            for(int j = 1; j <= n; ++ j){
                scanf("%d", &a[i][j]);
            }
        }
        for(int i = 1; i <= n; ++ i){
            for(int j = 1; j <= n; ++ j){
                scanf("%d", &b[i][j]);
            }
        }
        solve();
    }
    return 0;
}

J.Road Discount

• 题意
  给你 n n n个顶点， m m m条边的图，其中边权值有原价和折扣价。问当只能使用 k k k条折扣价边的最小生成树权重。

• 解题思路
  假定原边是白边，折扣边是黑边，那么对于每次要输出的，问题就转换成了选 k k k条黑边的最小生成树的代价是多少。我们可以先将只用白边和只用黑边的最小生成树所用边给求出来，其他的边都是多余的，然后我们对黑边附上值使得我们能够让黑边和白边组合排序，再跑一下最小生成树求黑边使用数量以及最小权重。最后二分得到满足条件的解即可。

• AC代码

/**
  *@filename:J_Road_DIscount
  *@author: pursuit
  *@created: 2021-07-27 13:20
**/
#include <bits/stdc++.h>
#define debug(a) cout << (#a)<< ":" << a << endl;
using namespace std;

typedef pair<int,int> pii;
typedef long long ll;
const int N = 200000 + 5;
const int P = 1e9+7;

int t,n,m;
int father[1010 * 2 + 10];
struct node{
    int u,v,w;
    int tag;//0表示正常价，1表示折扣价。
    bool operator < (const node &A){
        return w < A.w;
    }
}edges[N],edges1[N],edges2[N];
pii f[N];//第一维表示适用黑边的次数，第二维表示最小代价。
int find(int x){
    int r = x;
    while(r != father[r])r = father[r];
    int i = x,j;
    while(father[i] != r){
        j = father[i];
        father[i] = r;
        i = j;
    }
    return r;
}
void work(node *edges){
    for(int i = 1; i <= n; ++ i)father[i] = i;
    int tot = 0;
    for(int i = 1; i <= m; ++ i){
        int fu = find(edges[i].u),fv = find(edges[i].v);
        if(fu != fv){
            father[fu] = fv;
            edges[++ tot] = edges[i];
        }
    }
}
pii cal(int x){
    int cnt = 0,ans = 0,tot = 0;
    for(int i = 1; i <= m; ++ i){
        edges2[i].w += x;
    }
    edges1[m + 1].w = edges2[m + 1].w = 1e8;
    for(int i = 1; i <= n; ++ i)father[i] = i;
    for(int i = 1, j = 1; i <= m || j <= m;){
        if(edges1[i].w < edges2[j].w){
            edges[++ tot] = edges1[i ++];
        }
        else{
            edges[++ tot] = edges2[j ++];
        }
    }
    for(int i = 1; i <= tot; ++ i){
        int fu = find(edges[i].u),fv = find(edges[i].v);
        if(fu != fv){
            father[fu] = fv;
            cnt += edges[i].tag;
            ans += edges[i].w;
        }
    }
    for(int i = 1; i <= m; ++ i){
        edges2[i].w -= x;
    }
    return {cnt,ans};
}
void solve(){
    sort(edges1 + 1,edges1 + 1 + m);
    sort(edges2 + 1, edges2 + 1 + m);
    work(edges1),work(edges2);
    //处理完之后提取出我们要的n - 1条边。
    m = n - 1;
    //让黑边加上一个值。
    for(int i = -1010; i <= 1010; ++ i){
        f[1010 + i] = cal(i);
    }
    for(int k = 0; k < n; ++ k){
        int l = -1010, r = 1010,res,mid;
        while(l <= r){
            mid = l + r >> 1;
            if(f[mid + 1010].first >= k){
                //说明使用黑边数量多
                res = f[mid + 1010].second - mid * k;
                l = mid + 1;
            }
            else{
                r = mid - 1;
            }
        }
        printf("%d\n", res);
    }
}
int main(){
    scanf("%d", &t);
    while(t -- ){
        scanf("%d%d", &n, &m);
        for(int i = 1; i <= m; ++ i){
            scanf("%d%d%d%d", &edges1[i].u, &edges1[i].v, &edges1[i].w, &edges2[i].w);
            edges2[i].u = edges1[i].u,edges2[i].v = edges1[i].v;
            edges1[i].tag = 0,edges2[i].tag = 1;
        }
        solve();
    }
    return 0;
}

K.Segment Tree with Pruning

• 题意
  给你一个建树函数，求生成的结点数。

• 解题思路
  记忆化递推求解。这样只要跑 l o g n logn logn即可。

• AC代码

/**
  *@filename:K_Segment_Tree_with_Pruning
  *@author: pursuit
  *@csdn:unique_pursuit
  *@email: 2825841950@qq.com
  *@created: 2021-07-27 12:27
**/
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
const int N = 100000 + 5;
const int P = 1e9+7;

int t;
ll k,n;
unordered_map<ll,ll> p;
ll build(ll n){
    if(p.find(n) != p.end())return p[n];
    if(n <= k)return p[n] = 1;
    return p[n] = build(n / 2) + build(n - n / 2) + 1;
}
void solve(){
    p.clear();
    cout << build(n) << endl;
}
int main(){
    cin >> t;
    while(t -- ){
        cin >> n >> k;
        solve();
    }
    return 0;
}

这篇关于2021“MINIEYE杯”中国大学生算法设计超级联赛（3）部分题解的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！