首页 > 编程语言 >2022年华中科技大学程序设计新生赛

2022年华中科技大学程序设计新生赛

时间：2022-10-25 17:48:06浏览次数：59  
标签：ch int 华中科技大学 long while 2022 res 程序设计 getchar

背景：之前练的一场忘了写题解，补一下，赛时过了6题

A

解析

主要考察的是对于期望dp的理解
其实也没什么好说的，一般写过期望dp的还是很容易想到
img
这里就把官方的贴上来了
补充一下：期望dp一般设状态都是距离目标状态的期望，然后从目标状态倒过来递推
\(dp[i][j]的期望 = 下一个可能状态的综合期望 + 自己本身的期望 (指1)\)

代码

//                  ξ†(ᗜ ˰ ᗜ)†ξ
//           去吧，鸭鸭，把希儿和AC都带回来！
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
const int M = 998244353;
int dp[1005][1005];
int qmi(int a,int b){
    int res = 1;
    while(b){
        if(b & 1){
            res = res * a % M;
        }
        a = a * a % M;
        b >>= 1;
    }
    return res;
}
int a[1005];
int x[1005];
inline int read(){
    int x=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){
        if(ch=='-')
            f=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        x=x*10+ch-'0';
        ch=getchar();
    }
    return x*f;
    }
inline void print(int x){
    if(x<0){
        putchar('-');
        x=-x;
    }
    if(x>9)
        print(x/10);
        putchar(x%10+'0');
    }
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n;
    cin >> n;
    int p = qmi(100,M-2);
    for(int i = 1; i <= n; i++){
        cin >> a[i] >> x[i];
    }
    for(int i = 1; i <= 1000; i++) dp[n][i] = 0;
    for(int i = n-1; i >= 0; i--){
        for(int j = 1000; j >= 0; j--){
            if(j == a[i+1]){
                dp[i][j] = (dp[i+1][j] + 1) % M;
            }
            else if(j > a[i+1]){
                dp[i][j] = ((1 + (dp[i+1][j-1] * x[i+1]) % M * p) % M + ((100 - x[i+1]) * p) % M * dp[i+1][j] % M) %M;
            }
            else {
                dp[i][j] = (qmi(x[i+1],M-2)*100 % M + dp[i][j+1]) % M;
            }
        }
    }
    cout << dp[0][0] << endl;
    return 0;
}

C

解析

签到，观察一下可以发现答案是 \((a+b) \over b\)

代码

//                  ξ†(ᗜ ˰ ᗜ)†ξ
//           去吧，鸭鸭，把希儿和AC都带回来！
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
int gcd(int a,int b){
    if(b == 0) return a;
    else
    return b > a ? gcd(b,a) : gcd(b,a % b);
}
inline int read(){
    int x=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){
        if(ch=='-')
            f=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        x=x*10+ch-'0';
        ch=getchar();
    }
    return x*f;
    }
inline void print(int x){
    if(x<0){
        putchar('-');
        x=-x;
    }
    if(x>9)
        print(x/10);
        putchar(x%10+'0');
    }
void solve(){
    int a,b;
    cin >> a >> b;
    int p = gcd(a,b);
    a = a / p;
    b = b / p;
    a = a + b;
    cout << a << "/" << b << endl;
}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t;
    cin >> t;
    while(t--){
        solve();
    }
    return 0;
}

E

解析

贪心，发现合并石子每次让最大的两个合并一定不会使结果变差，用优先队列可以解决

代码

//                  ξ†(ᗜ ˰ ᗜ)†ξ
//           去吧，鸭鸭，把希儿和AC都带回来！
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
const int N = 1e5 + 5;
int s[N];
priority_queue<int> pri;
inline int read(){
    int x=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){
        if(ch=='-')
            f=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        x=x*10+ch-'0';
        ch=getchar();
    }
    return x*f;
    }
inline void print(int x){
    if(x<0){
        putchar('-');
        x=-x;
    }
    if(x>9)
        print(x/10);
        putchar(x%10+'0');
    }
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n;
    cin >> n;
    for(int i = 1; i <= n; i++) cin >> s[i],pri.push(s[i]);
    int res = 0;
    while(pri.size() != 1){
        int p = pri.top();
        pri.pop();
        int q = pri.top();
        pri.pop();
        res = res + p * q;
        pri.push(p+q);
    }
    cout << res << endl;
    return 0;
}

H

解析

签到，模拟即可

代码

//                  ξ†(ᗜ ˰ ᗜ)†ξ
//           去吧，鸭鸭，把希儿和AC都带回来！
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
inline int read(){
    int x=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){
        if(ch=='-')
            f=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        x=x*10+ch-'0';
        ch=getchar();
    }
    return x*f;
    }
inline void print(int x){
    if(x<0){
        putchar('-');
        x=-x;
    }
    if(x>9)
        print(x/10);
        putchar(x%10+'0');
    }
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    string s;
    int n;
    cin >> n;
    cin >> s;
    int res = 0;
    int cnt = 0;
    for(int i = 0; i < n; i++){
        if(s[i] == 'f'){
            res = 1;
        }
        else if(s[i] == 'y'){
            if(res == 1){
                res++;
            }
            else res = 0;
        }
        else if(s[i] == 't'){
            if(res == 2){
                res++;
                cnt++;
            }
            else res = 0;
        }
        else res = 0;
    }
    cout << cnt << endl;
    return 0;
}

J

解析

博弈+思维
分几种情况考虑

  • Walk Alone的横坐标大于或等于另一个玩家的横坐标，这时walk alone可以一直斜向上或斜向下走，而另一个玩家的最优走法也是这样，所以他永远追不上Walk Alone
  • Walk Alone的横坐标小于另一个玩家的横坐标
    • 他们的纵坐标不等，同样Walk Alone 一直斜着走，而另一个玩家无论怎么走他与Walk ALone 的纵坐标至少相差1以上，所以他永远追不上Walk Alone
    • 他们的纵坐标相等，这时Walk Alone 无论怎么走，另一个玩家的最优走法是朝着Walk Alone 的方向走
      img
      如图所示，红色是Walk ALone 走的路程，蓝色是另一个玩家走的路程，可见下一次移动另一个玩家就能抓到Walk ALone
      横着走结局也是一样都是另一个玩家赢
      这时是两个玩家横坐标之差是偶数的时候
      如果两个玩家横坐标之差是奇数，那么红方就可以将蓝色方吃掉，最后依然是红色方赢
      那么答案就显而易见了

代码

//                  ξ†(ᗜ ˰ ᗜ)†ξ
//           去吧，鸭鸭，把希儿和AC都带回来！
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
inline int read(){
    int x=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){
        if(ch=='-')
            f=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        x=x*10+ch-'0';
        ch=getchar();
    }
    return x*f;
    }
inline void print(int x){
    if(x<0){
        putchar('-');
        x=-x;
    }
    if(x>9)
        print(x/10);
        putchar(x%10+'0');
    }
void solve(){
    int a,b,c,d;
    cin >> a >> b >> c >> d;
    if(a >= c){
        cout << "Walk Alone" << endl;
    }
    else {
        if(b != d){
            cout << "Walk Alone" << endl;
        }
        else {
            int p = c - a;
            if(p % 2 == 0){
                cout << "Salix Leaf" << endl;
            }
            else cout << "Walk Alone" << endl;
        
        }  
        
    }
}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t;
    cin >> t;
    while(t--){
        solve();
    }
    return 0;
}

L

解析

简单贪心，可以发现，当后续的曲子都置为Perfect时不会使结果变差

代码

//                  ξ†(ᗜ ˰ ᗜ)†ξ
//           去吧，鸭鸭，把希儿和AC都带回来！
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
inline int read(){
    int x=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){
        if(ch=='-')
            f=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        x=x*10+ch-'0';
        ch=getchar();
    }
    return x*f;
    }
inline void print(int x){
    if(x<0){
        putchar('-');
        x=-x;
    }
    if(x>9)
        print(x/10);
        putchar(x%10+'0');
    }
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    double n,k;
    cin >> n >> k;
    double per = 900000/n;
    double goo = 585000/n;
    double noww = 0;
    int maxx = 0;
    int cnt = 0;
    for(int i = 1; i <= k; i++){
        string s;
        cin >> s;
        if(s == "perfect"){
            cnt++;
            noww += per;
        }
        else if(s == "good"){
            cnt++;
            noww += goo;
        }
        else {
            maxx = max(maxx,cnt);
            cnt = 0;
         
        }
    }
    for(int i = k+1; i <= n; i++){
        cnt++;
        noww += per;
    }
    maxx = max(maxx,cnt);
    noww += 100000 * maxx / n;
    noww += 0.5;
    int res = noww;
    cout << res << endl;
    return 0;
}

N

解析

构造题，也是分情况来进行构造

  • a % 3 == 0 && a % 2 == 0 这时候我们直接构造 3a 和 2a 即可，这样可以直接保证两个条件，构造出来的两个数因子和原来一样
  • a % 3 != 0 && a % 2 != 0 这时候也和上面一样，构造出来的两个数分别多了2和3的因子
  • a % 3 != 0 && a % 2 == 0 构造 a 和 2a 构造出来的两个数因子和原来一样
  • a % 3 == 0 && a % 2 != 0
    这个情况也是最难想的情况，这个数不能被2整除，说明其是一个奇数。
    那么我们可以先找到这个数内第一个没出现过的质因子，根据数据范围可以知道这个因子一定不会超过100，设其为prime。
    可以知道prime一定是一个奇数，那么prime+1一定为偶数，并且prime+1一定也不是a的因子（如果它是a的因子，那么a一定能被2整除）
    $所以构造prime \times a 和 (prime + 1) \times a $ 即可

代码

//                  ξ†(ᗜ ˰ ᗜ)†ξ
//           去吧，鸭鸭，把希儿和AC都带回来！
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
int prime[105];
bool vis[105];
int ans;
inline int read(){
    int x=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){
        if(ch=='-')
            f=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        x=x*10+ch-'0';
        ch=getchar();
    }
    return x*f;
    }
inline void print(int x){
    if(x<0){
        putchar('-');
        x=-x;
    }
    if(x>9)
        print(x/10);
        putchar(x%10+'0');
    }
void solve(){
    int a;
    cin >> a;
    if(a % 3 == 0 && a % 2 == 0){
        cout << a * 2 << " ";
        cout << a * 3 << endl;
        
    }
    else if(a % 3 != 0 && a % 2 != 0){
        cout << a * 2 << " ";
        cout << a * 3 << endl;
        
    }
    else if(a % 3 != 0 && a % 2 == 0){
        cout << a << " ";
        cout << a * 2 << endl;
        
    }
    else{
        int prim = 0;
        for(int i = 1; i <= 8; i++){
            if(a % prime[i] != 0){
                prim = prime[i];
                break;
            }
        }
        cout << a * prim << " ";
        cout << a * (prim + 1) << endl;
        
    }
}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int x = 100;

    for(int i = 2; i <= x; i++)
    {
       if(!vis[i]) prime[ans++] = i;//判断是否是素数
       for(int j = 0; prime[j] <= x / i;++j)
       {
           vis[prime[j] * i] = true;//最小质因数和最大因子的乘积
           if(i % prime[j] == 0) break;//说明不是最小质因数
       }
    }
    int res = 1;
    int t;
    cin >> t;
    while(t--){
        solve();
    }
    return 0;
}

标签：ch,int,华中科技大学,long,while,2022,res,程序设计,getchar
From： https://www.cnblogs.com/Sun-Wind/p/16825658.html

相关文章

  • 2022-10-25 uniapp项目运行至小程序后出现问题：1、点击事件传递的值为undefined；2：v-for
    前言，uniapp编译到微信后，代码变得诡异起来。一些效果比如题目所言，效果和h5端的不一样（h5端正常，小程序端异常）问题1：原因：key值不明确，我绑定的是数组的index，心想这都不行？然后把......
  • 【2022-10-20】剧能解压
    20:00有志竟成，我们在这个世界上，一个很重要的就是要励志，有志竟成，不是说你有志就行，而是竟成，做的也很有力，很有眼光，那么你就成功了。            ......
  • 【2022-10-19】免疫下降
    20:00醒来听见鸟啭，一天都是快活的。走到街上，看见草上的露珠还没有干，砖缝里被蚯蚓倒出一堆一堆的沙土......这时候我忠心充满了喜悦！这是一个活的世界，这是一个人的世界，这是......
  • J-PSC2022保龄寄
    迟到了1个月的游记。初赛Day0复习ing，没什么好说的。越来越慌了。初赛Day1考场在ylsy。什么**学校，进门楼梯那么长。好多人啊qwq考试中，这是我的心理变化：......
  • 20221025 英文单词
    1、arbitrate仲裁；公断  2、aisle 3、accounting  4、admit  5、admittance进入权   6、applause  7、applaud  8、appetizer ......
  • 云原生爱好者周刊：买个蓝牙打印机实时打印新提交的 PR 吧 | 2022-10-24
    开源项目推荐blue这个项目非常有意思，利用树莓派、蓝牙热敏打印机和GitHubActions自动将新提交的PR或者Issue通过打印机打印出来，非常适合各个项目的维护者使用......
  • 20221011
    AESKEY–ENCODEDINTHEMACHINEREADABLEZONEOFAEUROPEANEPASSPORTAES加密模式为CBC，初始化矢量即IV为零，填充为01-00。此外，相应的密钥在身份证件上的机器可......
  • Oct 24 2022 学习日志
    Dijkstra用pair实现$edge$（struct）建立edge数组$E$来记录每个点的出边$pair<int,int>$（struct）用来给优先队列服务，$first$为$dis[u]$,$second$为$u$初始化：$dis[u]=......
  • JavaScript高级程序设计笔记11 期约与异步函数（Promise & Async Function）
    期约与异步函数ES6新增Promise引用类型，支持优雅地定义和组织异步逻辑。ES8增加了使用async和await关键字定义异步函数的机制。异步编程JavaScript这种单线程事件循环模......
  • 【闲话】2022.10.24
    今天考试，又炸了乐死怎么会有考试一次出两个诈骗题啊（笑今日一歌是《有顶天变》！晚上有一会自由活动时间大家都疯了，大家都疯了（笑对了，我，Kaguya和WR进行了混沌的三星......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99