大连大学程序设计竞赛(2023.11)正式赛题解

题目链接:http://dluacm.cn/wp-content/uploads/2023/11/202311zhengshi.pdf

补题链接:https://ac.nowcoder.com/acm/contest/69510

难度预测

Check-in:C
Easy:A,M
Easy-Medium:I,K
Medium:B,L,E
Medium-Hard:D,H,J
Hard:G,F

统计

A:43/74
B:5/63
C:48/3
D:2/40
E:4/51
F:5/11
G:0/21
H:0/57
I:17/22
J:3/49
K:10/61
L:4/9
M:35/196

problem A 加训时间!

根据题意可知,答案为数组最大值*n

problem B 爆wa种子!

对于形如\space y=ax^2+bx+c\space的函数方程只可能有三种情况:

  1. 抛物线,由于数据保证a\ge 0,所以必定开口向上,那么此时最低点x坐标可以由\Large\frac{-b}{2a}得到再代入方程\space y=ax^2+bx+c\space即可得到最小值
  2. 一条平行于x轴的直线
  3. 一条既不平行于y轴也不平行于x轴的直线

如果出现情况3,答案只能是负无穷。

如果没出现过情况3,则对情况1以及情况2求出的最低点取min即可。

problem C 晚上不睡觉

输出a\cdot b的错误答案即可。例如可以直接输出-1a\cdot b+1

problem D 书生的负数

当将所有数字相加,数字之和大于-n时将除最后一个数之外的所有数改为-1,最后一个数为非负数,输出n-1
否则所有的数都可以改为负数,输出n

problem E 明天

tomorrow的子串全部提取出来,存到map中,每次判断即可。

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

int main()
{
    ios::sync_with_stdio(false) ;
    cin.tie(nullptr) ;

    map<string, bool> mp ;
    string T = "tomorrow" ;

    for(int i = 0; i < 8; ++ i)
        for(int j = i; j < (!i ? 7 : 8); ++ j)
            mp[T.substr(i, j - i + 1)] = 1 ;

    int Q ; cin >> Q ;
    while(Q --)
    {
        string s ; cin >> s ;
        cout << (mp.count(s) ? "yes" : "no") << '\n' ;
    }
    return 0 ;
}

problem F 跳棋

观察到如果有任意两个棋子相邻,整个棋盘的位置都能被跳到,枚举一下判断是否有棋子相邻即可。

#include <bits/stdc++.h>
using namespace std ;
using ll = long long ;

int main()
{
    ios::sync_with_stdio(false) ;
    cin.tie(nullptr) ;

    int n ; string s ; cin >> n >> s ;
    for(int i = 0; i < n - 1; ++ i)
        if(s[i] == 'X' && s[i + 1] == 'X')
            return cout << n << '\n', 0 ;

    int ans = 0 ;
    for(int i = 0; i < n; ++ i) ans += s[i] == 'X' ;
    cout << ans << '\n' ;
    return 0 ;
}


problem G 河流管理

并查集。

每一次打开挡板,便将当前的河段与下一段河流合并,然后跳到下一段尚未与当前河段合并的河流继续合并。

#include <bits/stdc++.h>
using namespace std ;
const int N = 5e5 + 5 ;

int n, q ;
int a[N], fa[N], nxt[N] ;

int get(int x) { return x == fa[x] ? x : fa[x] = get(fa[x]) ; }

int main()
{
    ios::sync_with_stdio(false) ;
    cin.tie(nullptr) ;

    cin >> n >> q ;
    for(int i = 1; i <= n; ++ i) cin >> a[i] ;

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

    while(q --)
    {
        int opt ; cin >> opt ;
        if(opt == 1)
        {
            int l, r, g ; cin >> l >> r ;
            while((g = nxt[get(l)]) <= r)
            {
                int fl = get(l), fr = get(g) ;
                fa[fl] = fr ;
                a[fr] =  max(a[fr], a[fl]) ;
                l = g ;
            }
        }
        else
        {
            int x ; cin >> x ;
            cout << a[get(x)] << '\n' ;
        }
    }
    return 0 ;
}

problem H 冒险

观察到背包内物品体积成指数级增长,所以背包内物品个数在log\ k级别。

假设背包内要放入x个物品,显然那么一定是放入前x小的物品,且优先放体积较小的物品。

排序后暴力枚举选多少个物品即可。

#include <bits/stdc++.h>
using namespace std ;
#define ll long long
const int N = 1e6 + 5, M = 20 ;
const ll INF = 1e18 ;
int n, k, a[N] ;
ll f[M] ;
int main()
{
    ios::sync_with_stdio(false) ;
    cin >> n >> k ;
    for(int i = 1; i <= n; ++ i) cin >> a[i] ;
    sort(a + 1, a + n + 1) ;
    int ans = 0 ;
    for(int i = 0; i <= min(M - 1, n); ++ i)
    {
        ll t = 0 ;
        for(int j = 1; j <= i; ++ j)
            t += a[j] * (1ll << (i - j)) ;
        if(t <= k) ans = i ;
    }
    cout << ans << '\n' ;
    return 0 ;
}


problem I 妙wa种子!

由于每段对于答案的贡献是该段中的最大值,那么最优方案就是选出这些数中前k大的数求和。

我们先选出前k大的数,以这些前k大的数为起点不断往左、右扩张,直到这些前k个数所在段能覆盖整个数组,就划分出了每段。

problem J 货币系统

由裴蜀定理可得a, b, c能凑出的最小正整数为gcd(a,b,c),所以判断gcd(a, b, c)是否为1即可。

problem K 从南到北II

读入字符串,从0n-3逐个比对,每一位和后面两位是否是“hui”和“hen”,如果为“hui”和“hen”则将这三位改为0,最后输出非0的字符即可。

problem L 选拔

找到每个数组的最大值,然后把剩下的放进一个数组a里。由于之前已经选了n个数组的最大值,所以还需选出m-n个,将数组a按降序排序后选出前m-n个即可。

problem M 远方

如果所有的建筑物都不会挡住enterdawn的视线,即x > \max_{i=1}^n y时,输出yes,否则输出no

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

int main()
{
    ios::sync_with_stdio(false) ;
    cin.tie(nullptr) ;

    int n, x, y, maxv = -1 ; cin >> n >> x ;
    for(int i = 1; i <= n; ++ i)
    {
        cin >> y ;
        maxv = max(maxv, y) ;
    }

    cout << (x > maxv ? "yes" : "no") << '\n' ;
    return 0 ;
}

暂无评论

发送评论 编辑评论


				
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇