大连大学程序设计竞赛(2022.11)热身赛题解

题目链接:http://dluacm.cn/wp-content/uploads/2022/11/202211reshen.pdf

Problem RA 一些你应该知道的东西

把题面上代码复制粘贴过去即可AC。

注意空间只有4M,所以必须输入一组输出一组。

Problem RB 对对联

我校有名湖边上亭子的对联,按照提示去提问即可得到正确答案。

答案是“handeyingwuhoujiejusoucaiqingruosihuyouming”。
http://dluacm.cn/wp-content/uploads/2022/11/AKYUIX9XGCUVCUH758C.jpg

Problem RC 佩里科岛

我们只需要遍历一遍,根据题目“上岛后选择立即下岛”,所以收益最小为0,当我们遍历过程中遇到小于0的时候,直接置为0.
然后我们可以“选择在进入任意房间前上岛并在离开任意房间后下岛”,我们只需要取遍历过程中最大值即可。

#include <bits/stdc++.h>
using namespace std;
#define inf 0x7ffffffffffffff
#define N 1005000
#define mod 1000000007
#define mod2 998244353
#define ll long long
ll a[N];
int main()
{
    ll t;
    scanf("%lld",&t);
    while(t--)
    {
        ll n;
        scanf("%lld",&n);
        ll sum=0,ans=0;
        for(int i=1;i<=n;i++)
        {
            ll x;
            scanf("%lld",&x);
            sum+=x;
            if(sum<0) sum=0;
            ans=max(sum,ans);
        }
        printf("%lld\n",ans);
    }
    return 0;
}

另外本题也可以使用线性dp解决。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e5+5;
int a[N];
int dp[N];
void solve(){
    int n;
    cin>>n;
    for(int i=1;i<=n;++i)cin>>a[i];
    int ans=0;
    for(int i=1;i<=n;++i){
        dp[i]=max(dp[i-1]+a[i],a[i]);
        ans=max(dp[i],ans);
    }
    cout<<ans<<endl;
}
int main()
{
    int t;
    cin>>t;
    while(t--){
        solve();
    }
}

Problem RD amiloac’s a+b

本题略有歧义,对a+b整体取余,不要求是结果是非负数。

在C/C++, JAVA言中,’%’运算符都是做取余运算,而在python中的’%’是做取模运算。

#include<stdio.h>
int main(){
    long long a,b;
    scanf("%lld%lld",&a,&b);
    printf("%lld",(a+b)%10000000000007);
    return 0;
}

Problem RE 删除数

注意空间只有4M,所以你存下所有的数再排序一定会爆空间。
相信大家都听过高斯小时候的故事,由于是连续整数,我们只需要求出它们的和,然后再求出区间和,减一下即可。

int main() {
    long long a, b, n, sum = 0;
    scanf("%lld%lld", &a, &b);
    for (long long i = a; i < b; i++) {
        scanf("%lld", &n);
        sum += n;
    }
    printf("%lld", (b + a) * (b - a + 1) / 2 - sum );
    return 0;
}

还有一种方法是用桶存相对位置

#include<bits/stdc++.h>
#define oo 0x3f3f3f3f
#define OO 0x3f3f3f3f3f3f3f3f
#define LL long long
#define all(x) x.begin(),x.end()
#define close() ios::sync_with_stdio(0),cin.tie(nullptr),cout.tie(nullptr)
using namespace std;
const int N=6e5;
bool vis[N];
void Solve(){
    LL l,r,x;
    cin>>l>>r;
    int n=r-l+1;
    for(int i=0;i<n-1;++i){
        cin>>x;
        vis[x-l]=true;
    }
    for(int i=0;i<n;++i){
        if(!vis[i]){
            cout<<l+i<<'\n';
            return ;
        }
    }
}
int main(){
    close();
    Solve();
    return 0;
}

Problem RF 鸽子的小心思

注意题面“这10个数在对10取模后互不同余,但是我想的数很大,你肯定猜不对。你就告诉我它们对10取余以后的结果就行。”
所以我们很容易想到其中一组答案“0 1 2 3 4 5 6 7 8 9”。
由于special judge出现未预料的问题,所以本题不计成绩,在此对所有参赛同学表示诚挚的歉意。

暂无评论

发送评论 编辑评论


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