当前位置:网站首页>【2022河南萌新联赛第(五)场:信息工程大学】【部分思路题解+代码解析】

【2022河南萌新联赛第(五)场:信息工程大学】【部分思路题解+代码解析】

2022-08-10 03:05:00 Eternity_GQM


2022河南萌新联赛第(五)场:信息工程大学

赛题地址


A 钢筋切割


B 交通改造

题目描述

A城是一座繁忙又有活力的城市,随着城市的发展,原有的道路越发拥堵,所以政府决定对原有的道路交通系统进行改造。

A城目前的道路是这样的:城市中有n个交叉路口,部分交叉路口通过道路直接相连,任意两个交叉路口之间最多有一条道路连接。A城的只有双向道,没有单向道,并且所有交叉路口都通过道路直接或间接相连。现在给每条道路设定一个通畅值,通畅值越小则该道路越繁忙也越需要改造。出于节约资金的思想考虑,现在政府希望改造的道路尽可能少,于是提出了下列要求:

接受改造的道路能够令所有的交叉路口直接或间接相连,并且改造的道路数量应尽可能的少,其次在满足上述条件的情况下,令被改造的道路中通畅值最大的道路的通畅值尽量小

现在你作为政府的顾问,请设计一套方案,确定哪些道路需要被改造。

输入描述:
第一行有两个整数n,m表示城市有n个交叉路口,m条道路。

接下来m行是对每条道路的描述,u, v,c表示交叉路口u和v之间有道路相连,分值为c。

输出描述:
两个整数s,max,表示你选出了几条道路,分值最大的那条道路的分值是多少。

示例1

输入

4 5
1 2 3
1 4 5
2 4 7
2 3 6
3 4 8

输出

3 6

备注:

1≤n≤300,1≤c≤10000,1≤m≤100000

题目解析:

思路1:

  1. 改造的那些道路能够把所有的交叉路口直接或间接的连通起来。
  2. 在满足要求 1 的情况下,改造的道路尽量少。
  3. 在满足要求 1、2 的情况下,改造的那些道路中分值最大的道路分值尽量小。

题面中有最大值最小,典型的二分!首先二分边权,然后把边权小于等于二分的边权的边全部用并查集连接到一起,判断是否联通即可。

const int N = 8100;
struct node{
    
    int a, b, w;
} sz[N];//存边
int n, m;
//并查集
int p[N];
int find(int a){
    
    if (p[a] != a)
        p[a] = find(p[a]);
    return p[a];
}
bool cmp(const node &A, const node &B){
    
    return A.w < B.w;
}
bool check(int x){
    
    for (int i = 1; i <= n; i++)
        p[i] = i;
    for (int i = 1; i <= m; i++){
    
        int a = sz[i].a, b = sz[i].b, w = sz[i].w;
        if (w > x)
            break;
        if (find(a) != find(b)){
    
            p[find(a)] = find(b);
        }
    }
    int flag = 0;
    for (int i = 1; i <= n; i++){
     // 并查集检验是否联通
        if (p[i] == i)
            flag++;
    }
    if (flag == 1)//全部连通
        return true;
    return false;
}
void solve(){
    
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
        p[i] = i;
    for (int i = 1; i <= m; i++){
    
        int a, b, c;
        cin >> a >> b >> c;
        sz[i] = {
    a, b, c};
    }
    sort(sz + 1, sz + 1 + m, cmp);
    int l = 0, r = 10001;
    while (l < r){
     // 二分枚举可能的最大边权 
        int mid = l + r >> 1;
        if (check(mid))
            r = mid;
        else
            l = mid + 1;
    }
    cout << n - 1 << " " << l;
}

思路2:

题目中1,2两个满足点暗示答案为一棵树,也就是用最小代价n-1条边完成n个点的联通。

可以用Kruskal算法直接求解。因为Kruskal算法是从边权由小到大枚举。筛选出的边完成的最小生成树自然满足最大边权最小。

struct node{
    
	int u, v, w;
}a[51000];
bool cmp(node x, node y){
    
	return x.w < y.w;
}
int n, m, u, v, w, maxn, k;
int f[305];
int find(int x){
    
	if(x == f[x]) 
		return x;
	return f[x] = find(f[x]);
}
int main(){
    
	cin >> n >> m;
	for(int i = 1; i <= m; i++)
		cin >> a[i].u >> a[i].v >> a[i].w; 
	for(int i = 1; i <= n; i++) 
		f[i] = i;
	sort(a + 1, a + 1 + m, cmp);//按权值从小到大排序
	for(int i = 1; i <= m; i++){
    
		if(find(f[a[i].u]) != find(f[a[i].v])){
    //不在同一个并查集里
			f[find(a[i].u)] = find(a[i].v);//连通
			maxn = a[i].w;//更新最大值
			k++;
		}
		if(k == n - 1)
			break;//最小生成树构建完成
	}
	cout << n - 1 << " " << maxn;
}

C 丢手绢

题目描述

N N N 个小朋友正在玩一种类似丢手绢的游戏,但与丢手绢又有所区别。

小朋友们先围坐一圈,然后从 0 0 0 N − 1 N-1 N1 顺时针进行编号。开始游戏前小朋友的编号与所在位置的编号相同,即 0 0 0 号小朋友在 0 0 0 号位置, 1 1 1 号小朋友在 1 1 1 号位置,以此类推。随后小朋友们会进行 1 0 k 10^k 10k 轮移动,每一轮所有小朋友都顺时针移动 M M M 个位置。
所以 0 0 0 号位置的小朋友到达 M M M 号位置,1号位置的小朋友到达 M + 1 M+1 M+1 号位置,以此类推, N − M N-M NM 号位置的小朋友到达 0 0 0 号位置, N − M + 1 N-M+1 NM+1 号位置的小朋友到达 1 1 1 号位置…… N − 1 N-1 N1 号位置的小朋友到达 M − 1 M-1 M1 号位置。
输入描述:
只有一行,包含4个整数 n , m , k , x n,m,k,x n,m,k,x,整数间用空格隔开。

输出描述:
一个整数,表示 1 0 k 10^k 10k 轮后 x x x 号小朋友所在的位置编号。

示例1

输入

10 3 4 5

输出

5

备注:

对于100%的数据,1<n<1,000,000,0<m<n,1≤x≤n,0<k<109。

题目分析:

约瑟夫环问题,取模由总人数n确定,问题就转化为求(x + m * (10 ^ k % n) % n ) % n,然后套快速幂就可以了。

快速幂:

递归版:

ll quickpow(ll a, ll b, ll n){
    
    if (b == 1)
        return a;
    else{
    
        if (b % 2 == 0){
    
            ll t = quickpow(a, b / 2, n);
            return t * t % n;
        }
        else{
    
            ll t = quickpow(a, b / 2, n);
            t = t * t % n;
            t = t * a % n;
            return t;
        }
    }
}

递推版:(比递归快)

ll quick_pow(ll a,ll b,ll m){
    
    a %= m;
    ll res = 1;
    while(b){
    
        if (b & 1)
            res = res * a % m;
        a = a * a % m;
        b >>= 1;
    }
    return res;
}

AC代码:

typedef long long ll;
ll quick_pow(ll a,ll b,ll m){
    
    a %= m;
    ll res = 1;
    while(b){
    
        if (b & 1)
            res = res * a % m;
        a = a * a % m;
        b >>= 1;
    }
    return res;
}
void solve(){
    
    ll n, m, k, x;
    cin >> n >> m >> k >> x;
    cout << (x + m * quick_pow(10, k, n) % n) % n;
    //取模由总人数n确定,问题就转化为求(x + m * (10 ^ k % n) % n ) % n;
}

D 敌情侦查
E QQ宠物


F 分割草坪

题目描述

小明的大学里有很多正多边形的草坪,但是小明只喜欢三角形的草坪,他决定把这些正多边形的草坪分割成许多个三角形的草坪,这时候园丁告诉小明其实这些正多边形的草坪都是有魔力的法阵,每一个顶点都有着属于自己的魔力,如果把一个正n边形的顶点顺时针从1到n标号,那么每个顶点的魔力与他的标号数值相等,也就是说这些顶点的魔力值分别从1到n,对于一个三角形的法阵来说,他的总魔力为三个顶点的魔力乘积,现在小明想破坏掉这个法阵,把这个正多边形的草坪划分成许多个面积互不相交的三角形草坪,使得所有的草坪魔力之和相加最小,可是小明只是喜欢三角形而已,他不想去算这么复杂的问题,他想问问你,最小的魔力之和是多少?

输入描述:

输入包含一个正整数n表示园丁需要让小明区划分一个正n边形变成一些三角形,使得他们的魔力和最小。

输出描述:

输出包含一个正整数表示最小的魔力和。

示例1

输入

3

输出

6

示例2

输入

4

输出

18

备注:

【数据范围与约定】对于100%的数据,保证n≤1,000,000。

题目解析:

看见题目的第一时刻就想到了这不是划分凸多边形的题吗?

区间dp啊

const int maxn = 300;
typedef long long ll;
ll dp[maxn][maxn]; //代表 区间i-1点到j点最优三角形剖分。
ll a[maxn];
int n;
void solve(){
    
    int n;
    cin >> n;
    for (int i = 0; i < n; i++)
        a[i] = i + 1;
    // dp[i][j] = dp[i][k]+dp[k+1][j]+a[k]*a[i-1]*a[l];
    memset(dp, 0, sizeof(dp));
    for (int len = 1; len < n - 1; len++){
    
        for (int i = 1; i + len < n; i++){
    
            int r = i, l = i + len;
            dp[r][l] = INF;
            for (int k = r; k < l; k++)
                dp[r][l] = min(dp[r][l], dp[r][k] + dp[k + 1][l] + a[k] * a[r - 1] * a[l]);
        }
    }
    printf("%d\n", dp[1][n - 1]);
    return 0;
}

段错误:数据给的 x <= 1e6

能过就怪了

然后就找规律:很明显的贪心,要所有的三角形顶点乘积的和最小,则越小的顶点越要多次使用,所以1要使用(n-2)次,如图所示划分为最优:

在这里插入图片描述
所以就转换为:2 * 3 + 3 * 4 + ··· +(n-1)* n

不开long long 见祖宗:

AC代码:

void solve(){
    
    ll n;
    cin >> n;
    ll ans = 0;
    ll temp = 1;
    for (ll i = 2; i <= n - 1;i++){
    
        ans += i * (i + 1);
    }
    cout << ans << nl;
}

G 数学大师
H 小明喝奶茶
I 光棱塔


J AC自动机

P4343 [SHOI2015]自动刷题机

题目背景

曾经发明了信号增幅仪的发明家 SHTSC 又公开了他的新发明:自动刷题机——一种可以自动 AC 题目的神秘装置。

题目描述

自动刷题机刷题的方式非常简单:首先会瞬间得出题目的正确做法,然后开始写程序。每秒,自动刷题机的代码生成模块会有两种可能的结果:

1.写了 x x x 行代码
2.心情不好,删掉了之前写的 y y y 行代码。(如果 y y y 大于当前代码长度则相当于全部删除。)

对于一个 OJ,存在某个固定的正整数长度 n n n,一旦自动刷题机在某秒结束时积累了大于等于 n n n 行的代码,它就会自动提交并 AC 此题,然后新建一个文件(即弃置之前的所有代码)并开始写下一题。SHTSC 在某个 OJ 上跑了一天的自动刷题机,得到了很多条关于写代码的日志信息。他突然发现自己没有记录这个 OJ 的 n n n 究竟是多少。所幸他通过自己在 OJ 上的 Rank 知道了自动刷题机一共切了 k k k 道题,希望你计算 n n n 可能的最小值和最大值。

输入格式

第一行两个整数 l , k l , k l,k,表示刷题机的日志一共有 l l l 行,一共了切了 k k k 题。

接下来 l l l 行,每行一个整数 x i x_i xi,依次表示每条日志。若 x i ≥ 0 x_i \geq 0 xi0,则表示写了 x i x_i xi 行代码,若 x i < 0 x_i \lt 0 xi<0,则表示删除了 − x i -x_i xi 行代码。

输出格式

输出一行两个整数,分别表示 n n n 可能的最小值和最大值。
如果这样的 n n n 不存在,请输出一行一个整数 − 1 -1 1

样例 #1

样例输入 #1

4 2
2
5
-3
9

样例输出 #1

3 7

提示

数据规模与约定

  • 对于 20 % 20\% 20% 的数据,保证 l ≤ 10 l \le 10 l10
  • 对于 40 % 40\% 40% 的数据,保证 l ≤ 100 l \le 100 l100
  • 对于 60 % 60\% 60% 的数据,保证 l ≤ 2 × 1 0 3 l \le 2 \times 10^3 l2×103
  • 对于 100 % 100\% 100% 的数据,保证 1 ≤ l ≤ 1 0 5 1 \leq l \le 10^5 1l105 − 1 0 9 ≤ x i ≤ 1 0 9 -10^9 \le x_i \le 10^9 109xi109

解题思路:

明显二分答案。然后直接 O ( n ) O ( n ) O(n) 判断即可。

我们如何二分这个区间的左右边界呢,我们可以用l<=r mid=(l+r)/2 l=mid+1 r=mid-1的版本。并在check(x)==k时做记录。若要二分左边界则在check(x)==kr=mid-1,二分右边界则l=mid+1

时间复杂度 O ( n log ⁡ n ) O(n\log n) O(nlogn)

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<pair<int, int>> vpii;
#define all(a) a.begin(), a.end()
#define nl '\n'
#define debug() cout << "debug:"
const int inf = 0x3f3f3f3f;
const int maxn = 2e5 + 5;
ll n, k, a[100005];
ll l, r, ans;
ll check(ll x) {
    //这里直接模拟即可
    ll num = 0, len = 0;
    for (ll i = 1; i <= n; i++){
    
        num += a[i];
        if (num < 0)
            num = 0;
        if (num >= x)
            num = 0, len++;
    }
    return len;
}
void solve(){
    
    cin >> n >> k;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    l = 1, r = 1e15;
    ans = 1e15 + 1;
    while (l <= r) {
    //二分左边界
        ll mid = (l + r) / 2;
        if (check(mid) > k)
            l = mid + 1;
        else if (check(mid) < k)
            r = mid - 1;
        else
            ans = mid, r = mid - 1;
    }
    if (ans != 1e15 + 1)
        cout << ans << " "; //判断是否存在这样的区间
    else{
    
        cout << -1 << " ";
        return;
    }
    l = 1, r = 1e15;
    ans = 1e15 + 1;
    while (l <= r) {
    //二分右边界
        ll mid = (l + r) / 2;
        if (check(mid) > k)
            l = mid + 1;
        else if (check(mid) < k)
            r = mid - 1;
        else
            ans = mid, l = mid + 1;
    }
    cout << ans << nl;
}
int main(){
    
    // ios::sync_with_stdio(0);
    // freopen("in", "r", stdin);
    int t = 1;
    // cin>>t;
    while (t--)
        solve();
    return 0;
}

K 矩阵生成

P2615 [NOIP2015 提高组] 神奇的幻方

题目描述

小明一日突发奇想发明了一种全新的神奇 M x M MxM MxM(保证 M M M为奇数)矩阵,由整数 1 , 2 , 3 ⋯ ⋯ , M × M 1,2,3⋯⋯,M×M 1,2,3⋯⋯,M×M 填充生成,矩阵中各行数字之和、各列数字之和以及两条对角线上数字之和结果都完全相同。

生成矩阵前先将数字1放在第一行的中间位置。随后按照如下规则填写其余数字 S ( S = 2 , 3 ⋯ ⋯ , M × M ) S(S=2,3⋯⋯,M×M) SS=2,3⋯⋯,M×M

1.若 ( S − 1 ) (S-1) (S1)在第一行但不在最后一列,则将 S S S填在最后一行, ( S − 1 ) (S-1) (S1)所在列的右一列;

2.若 ( S − 1 ) (S-1) (S1)在最后一列但不在第一行,则将 S S S填在第一列, ( S − 1 ) (S-1) (S1)所在行的上一行;

3.若 ( S − 1 ) (S-1) (S1)在第一行最后一列,则将 S S S填在 ( S − 1 ) (S-1) (S1)的正下方;

4.若 ( S − 1 ) (S-1) (S1)既不在第一行,也不在最后一列,如果 ( S − 1 ) (S-1) (S1)的右上方还未填数,则将 S S S填在 ( S − 1 ) (S-1) (S1)的右上方,否则将 S S S填在 ( S − 1 ) (S-1) (S1)的正下方。

现提供M,请按上述方法生成 M × M M×M M×M的矩阵。

输入描述:

一个整数 M M M,即矩阵的大小。

输出描述:
共M行,每行 M M M个整数,输出生成的 M x M MxM MxM矩阵,同一行中相邻两个整数用空格隔开。

示例1

输入

3

输出

8 1 6
3 5 7
4 9 2

备注:
对于100%的数据, 3 ≤ M ≤ 41 3≤M≤41 3M41,保证 M M M为奇数。

题目解析:

模拟题意即可:

const int maxn = 100;
int a[maxn][maxn];
void solve(){
    
    int n;
    cin >> n;
    int x = 1, y = n / 2 + 1;
    for (int i = 1; i <= n * n; i++){
    
        a[x][y] = i;
        if (x == 1 && y == n)
            x++;
        else if (x == 1)
            x = n, y++;
        else if (y == n)
            x--, y = 1;
        else if (a[x - 1][y + 1])
            x++;
        else
            x--, y++;
    }
    for (int i = 1; i <= n; i++){
    
        for (int j = 1; j <= n; j++)
            cout << a[i][j] << " ";
        cout << nl;
    }
}

数学解法:

int n, a[40][40], x, y;
void solve2(){
    
    scanf("%d", &n);
    x = 1, y = (n + 1) / 2;
    for (int i = 1; i <= n * n; i++){
    
        a[x][y] = i;
        if (!a[(x - 2 + n) % n + 1][y % n + 1])
            x = (x - 2 + n) % n + 1, y = y % n + 1;
        else
            x = x % n + 1; //数学运算
    }
    for (int i = 1; i <= n; i++){
    
        for (int j = 1; j <= n; j++)
            cout << a[i][j] << " ";
        cout << nl;
    }
}

L 方程求解

P1022 [NOIP2000 普及组] 计算器的改良

题目描述

经过多年潜心研究,小明终于掌握了编程技能!现在他要迈出他伟大实践的第一步,用编程解决一元一次方程问题!

当然为了防止第一步太过好高骛远,小明保证需要程序处理的一元一次方程中包含整数、小写字母及+、-、=这三个数学符号(当然,符号“-”既可作减号,也可作负号)。方程中并没有括号,也没有除号,方程中的字母表示未知数。并且保证一元一次方程合法并有唯一实数解。

输入描述:

一个一元一次方程。
例如:

4+3x=8
6a-5+1=2-2a
6a−5+1=2−2a
-5+12y=0

输出描述:

解方程的结果(精确至小数点后三位)。格式为 “【未知数】=【所求值】”

示例1

输入

6a-5+1=2-2a

输出

a=0.750

备注:
保证题中输入数字均为整型并且结果在浮点型范围内。

题目解析:

模拟题意处理即可:

const int maxn = 2e5 + 5;
char s[maxn];
void solve(){
    
    cin >> s;
    char a;//最终都移到等式的左边
    int fuhao = 1, x = 0, sum1 = 0, sum2 = 0, t = 1; 
    //正负号、目前的数、未知数的系数、常数项的系数、判断在等式的那边
    //开始负号默认为正号
    for (int i = 0; i < strlen(s); i++){
    
        if (s[i] == '='){
    
            if (x){
    //如果等式的左边一项是常数项,要特判
                sum2 += x * fuhao; //符号为正
                x = 0;             //清零
            }
            fuhao = 1; //开始默认为正号
            t = -1;    //转换到等式的右边
            continue;
        }
        switch (s[i]){
    
            case '-':{
    
                if (x) //又是特判
                    sum2 += x * fuhao * t;
                fuhao = -1;
                x = 0;
                break;
            }
            case '+':{
    
                if (x) //仍然是特判
                    sum2 += x * fuhao * t;
                fuhao = 1;
                x = 0;
                break;
            }
            default:
                break;
        }
        if (s[i] >= '0' && s[i] <= '9')
            x = x * 10 + s[i] - '0';
        else if (s[i] >= 'a' && s[i] <= 'z'){
    
            a = s[i];
            sum1 += x ? x * fuhao * t : fuhao * t; //如果是+a的话,还是要特判
            x = 0;
        }
    }
    if (x)
        sum2 -= x * fuhao;//注意是负号
    printf("%c=%0.3lf", a, -double(sum2) / double(sum1)); //因为移到了等式的左边,所以要加个负号
}

原网站

版权声明
本文为[Eternity_GQM]所创,转载请带上原文链接,感谢
https://blog.csdn.net/eternity_memory/article/details/126211510