当前位置： 首页 > news >正文

“Shopee杯“e起来编程暨武汉大学2020年大学生程序设计大赛决赛

news 来源：原创 2024/5/20 22:59:30

A - A Simple Problem about election（贪心）

传送门

题目有点难懂，现在每个人可以投m票且只能给另外的一个人最多投一票（包括自己），现在给出n个人的目前票数，而且只剩第一个人该投它的m票，因为某些原因，即使是他和其他人票数相同，他的排名是最低的。问如何使他自己的排名尽可能高并输出最高排名

首先第一票投给自己，现在的票数是自己最多得到的票数，第一步贪心看如果其他还没投票的比他现在的更高，那么这些是无论如何都不能超过的，就投一部分票给他们。如果还有剩余，对除他外的所有人的票数排序，不难发现目前票数越小的人对他造成影响的可能性越小，那么贪心从小的投直到投完即可

#include <set>
#include <map>
#include <stack>
#include <queue>
#include <math.h>
#include <cstdio>
#include <string>
#include <cstring>
#include <sstream>
#include <iostream>
#include <algorithm>
using namespace std;
#define lowbit(x) (x&(-x))
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> P;
const double eps=1e-8;
const double pi=acos(-1.0);
const int inf=0x7fffffff;
const ll INF=1e18;
const int Mod=1e9+7;
const int maxn=2e5+10;
 
struct node{
    int id,val;
}a[maxn];
 
bool cmp1(node &p,node &q){
    return p.val<q.val;
}
 
bool cmp2(node &p,node &q){
    return p.val==q.val?p.id>q.id:p.val>q.val;
}
 
int main(){
    int t,n,m;
    cin>>t;
    while(t--){
        cin>>n>>m;
        for(int i=0;i<n;i++){
            cin>>a[i].val;
            a[i].id=i;
        }
        a[0].val++;
        m--;
        for(int i=1;i<n;i++)
            if(a[i].val>=a[0].val) a[i].val++,m--;
        sort(a+1,a+n,cmp1);
        for(int i=1;i<n;i++){
            if(m<=0) break;
            a[i].val++,m--;
        }
        sort(a,a+n,cmp2);
        for(int i=0;i<n;i++){
            if(a[i].id==0){
                cout<<i+1<<endl;
                break;
            }
        }
 
    }
    return 0;
}

D - Deploy the medical team（简单快速幂）

传送门

n个人中m个可以做队长，每个队伍至少有一个队长且至少一个人，问有多少种队伍

m个人任选一个作队长，接着就是从n-1个人中组合数学选人
C(n-1,0)+C(n-1,1)+…+C(n-1,n-1) = 2n-1
答案是m*2n-1

#include <set>
#include <map>
#include <stack>
#include <queue>
#include <math.h>
#include <cstdio>
#include <string>
#include <cstring>
#include <sstream>
#include <iostream>
#include <algorithm>
#include <unordered_map>
using namespace std;
#define lowbit(x) (x&(-x))
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> P;
const double eps=1e-8;
const double pi=acos(-1.0);
const int inf=0x3f3f3f3f;
const ll INF=1e18;
const int Mod=1e9+7;
const int maxn=2e5+10;

ll quick_pow(ll x,ll n){
    ll ans=1;
    while(n){
        if(n&1) ans=ans*x%Mod;
        x=x*x%Mod;
        n>>=1;
    }
    return ans;
}

int main(){
    //freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    ll t,n,m;
    cin>>t;
    while(t--){
        cin>>n>>m;
        cout<<(m*quick_pow(2,n-1))%Mod<<endl;
    }
    return 0;
}

F - Figure out the sequence（字符串找规律）

传送门

第一眼以为要先求出最后的串直接统计即可，但是看到初始串长度最大40，检测一下答案串可以达到1e10，显然不能构造串

观察样例的每个串的规律，发现对于s1，它的每个字母在构造串的规律是：
1 0 1 1 2 3 …
同理对于s2：
0 1 1 2 3 5…
那么使用数组预处理存下初始串每个字符出现的次数，最后分大小写统计到两个数组，使用预处理的个数乘以每个字符的初始次数即可

可以少开数组的，我这里开的有点多了

#include <set>
#include <map>
#include <stack>
#include <queue>
#include <math.h>
#include <cstdio>
#include <string>
#include <cstring>
#include <sstream>
#include <iostream>
#include <algorithm>
#include <unordered_map>
using namespace std;
#define lowbit(x) (x&(-x))
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> P;
const double eps=1e-8;
const double pi=acos(-1.0);
const int inf=0x3f3f3f3f;
const ll INF=1e18;
const int Mod=1e9+7;
const int maxn=2e5+10;

ll check(int x){  //检查最大长度
    if(x==1 ||x==2) return 40;
    else return check(x-1)+check(x-2);
}


ll f1[105],f2[105];
ll a1[30],A1[30],a2[30],A2[30];
ll ans_a[30],ans_A[30];

void init(){
    f1[1]=f1[3]=f1[4]=f2[2]=f2[3]=1,f1[2]=f2[1]=0;
    for(int i=5;i<=50;i++)
        f1[i]=f1[i-1]+f1[i-2];
    for(int i=4;i<=50;i++)
        f2[i]=f2[i-1]+f2[i-2];
}

int main(){
    //freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);
    //ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    char s1[50],s2[50];
    int n;
    scanf("%s",s1);
    scanf("%s",s2);
    scanf("%d",&n);
    init();
    for(int i=0;i<strlen(s1);i++){
        if(s1[i]>'Z') a1[s1[i]-'a']++;
        else A1[s1[i]-'A']++;
    }
    for(int i=0;i<strlen(s2);i++){
        if(s2[i]>'Z') a2[s2[i]-'a']++;
        else A2[s2[i]-'A']++;
    }
    for(int i=0;i<26;i++)
        ans_A[i]=f1[n]*A1[i]+f2[n]*A2[i];
    for(int i=0;i<26;i++)
        ans_a[i]=f1[n]*a1[i]+f2[n]*a2[i];
    for(int i=0;i<26;i++)
        if(ans_A[i]) printf("%c: %lld\n",i+'A',ans_A[i]);
    for(int i=0;i<26;i++)
        if(ans_a[i]) printf("%c: %lld\n",i+'a',ans_a[i]);
    return 0;
}

G - Game Strategy（思维/博弈）

传送门

第一个人使结果尽量大，第二个人使结果尽量小，第三个人使结果尽量接近0
，如果答案对应多个选择输出第三个人选择的最大的数

对于第一个人他只能考虑下第二个人可选择的所有情况，对于第二个人，第一个人的选择他无法考虑，但是他可以考虑第三个人选择的所有情况来达到自己的预期，第三个人只能根据前两个人的选择去选择尽量接近0的

考虑一个三重循环，那么第一个人肯定是枚举自己所有情况，并参考后面两个人的情况后选择最后最大的；第二个人枚举所有情况后考虑第三个人的想法后选择最小的，第三个人贪心即可

#include <set>
#include <map>
#include <stack>
#include <queue>
#include <math.h>
#include <cstdio>
#include <string>
#include <cstring>
#include <sstream>
#include <iostream>
#include <algorithm>
#include <unordered_map>
using namespace std;
#define lowbit(x) (x&(-x))
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> P;
const double eps=1e-8;
const double pi=acos(-1.0);
const int inf=0x3f3f3f3f;
const ll INF=1e18;
const int Mod=1e9+7;
const int maxn=2e5+10;

int a[105],b[105],c[105];

int main(){
    //freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    int n;
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i];
    for(int i=1;i<=n;i++) cin>>b[i];
    for(int i=1;i<=n;i++) cin>>c[i];
    ll ans=-INF;
    for(int i=1;i<=n;i++){
        ll res1=INF;
        for(int j=1;j<=n;j++){
            ll res2=INF;
            int p=0;
            for(int k=1;k<=n;k++){
                ll sum=a[i]+b[j]+c[k];
                if(abs(sum)<abs(res2) || (abs(sum)==abs(res2) && c[k]>c[p]))
                    res2=sum,p=k;
            }
            res1=min(res1,res2);
        }
        ans=max(res1,ans);
    }
    cout<<ans<<endl;
    return 0;
}

H - Hinnjaku（字符串模拟）

传送门

数据范围小，暴力预处理后缀后按题意模拟，注意循环结束判断的先后

#include <set>
#include <map>
#include <stack>
#include <queue>
#include <math.h>
#include <cstdio>
#include <string>
#include <cstring>
#include <sstream>
#include <iostream>
#include <algorithm>
#include <unordered_map>
using namespace std;
#define lowbit(x) (x&(-x))
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> P;
const double eps=1e-8;
const double pi=acos(-1.0);
const int inf=0x3f3f3f3f;
const ll INF=1e18;
const int Mod=1e9+7;
const int maxn=2e5+10;
 
char s1[maxn],s2[maxn];
int p[maxn],q[maxn];
int t,n,h;
 
void init(){
    memset(p,0,sizeof p);
    memset(q,0,sizeof q);
    for(int i=0;i<n;i++){
        if(s1[i]=='a' && i+1>=3){
            if(s1[i-1]=='r' && s1[i-2]=='o') p[i]=1;
        }
        if(s1[i]=='o' && i+1>=9){
            if(s1[i-1]=='u' && s1[i-2]=='d' && s1[i-3]=='u' && s1[i-4]=='l' && s1[i-5]=='a' && s1[i-6]=='w' && s1[i-7]=='a' && s1[i-8]=='z')
                p[i]=-1;
        }
    }
    for(int i=0;i<n;i++){
        if(s2[i]=='a' && i+1>=4){
            if(s2[i-1]=='d' && s2[i-2]=='u' && s2[i-3]=='m') q[i]=1;
        }
        if(s2[i]=='o' && i+1>=9){
            if(s2[i-1]=='u' && s2[i-2]=='d' && s2[i-3]=='u' && s2[i-4]=='l' && s2[i-5]=='a' && s2[i-6]=='w' && s2[i-7]=='a' && s2[i-8]=='z')
                q[i]=-1;
        }
    }
}
 
int main(){
    scanf("%d",&t);
    while(t--){
        scanf("%d%d",&n,&h);
        scanf("%s",s1);
        scanf("%s",s2);
        init();
        int h1=h,h2=h;
        int flag=0;
        for(int i=0;i<n;i++){
            if(p[i]==-1 && q[i]==-1){
                h1=0;
                break;
            }else if(p[i]==-1){
                h2=0;
                break;
            }else if(q[i]==-1){
                h1=0;
                break;
            }
            if(p[i]==1) h2--;
            if(q[i]==1) h1--;
            if(h1==0){
                break;
            }
            if(h2==0){
                break;
            }
        }
        if(h1>h2) printf("Wryyyyy\n");
        else if(h2>h1) printf("Hinnjaku\n");
        else if(h1==h2) printf("Kono Dio da\n");
    }
    return 0;
}

I - Interesting Matrix Problem（规律+整除分块）

题解传送

J - Jogging along the Yangtze River（卡特兰数）

题解传送

相关文章：

  • iPhone开发秘籍一书中的翻译错误
  • 2020WHU校赛 I - Interesting Matrix Problem（规律+整除分块）
  • UVA1025 A Spy in the Metro （dp）
  • 欢迎大家来这里学习
  • UVA437 The Tower of Babylon（记忆化搜索）
  • MySQL启多个实例
  • UVA116 Unidirectional TSP（dp/多段图的最短路）
  • 忍受未知很重要
  • 背包九讲(1)——01背包
  • 两大重要活动议程
  • 背包九讲(2)——完全背包
  • Winforms: 把Label显示为多行
  • Codeforces Round #639 (Div. 2)
  • XXX项目鉴定总结！
  • UVA12563 Jin Ge Jin Qu hao（01背包）
  • android高仿小视频、应用锁、3种存储库、QQ小红点动画、仿支付宝图表等源码...
  • CEF与代理
  • ES6之路之模块详解
  • Git学习与使用心得（1）—— 初始化
  • JS正则表达式精简教程（JavaScript RegExp 对象）
  • Object.assign方法不能实现深复制
  • Puppeteer：浏览器控制器
  • REST架构的思考
  • zookeeper系列（七）实战分布式命名服务
  • 对象管理器（defineProperty）学习笔记
  • 关于使用markdown的方法（引自CSDN教程）
  • 函数式编程与面向对象编程[4]:Scala的类型关联Type Alias
  • 利用jquery编写加法运算验证码
  • 如何使用 JavaScript 解析 URL
  • 数据仓库的几种建模方法
  • MyCAT水平分库
  • puppet连载22：define用法
  • Spark2.4.0源码分析之WorldCount 默认shuffling并行度为200(九) ...
  • UI设计初学者应该如何入门？
  • ​2021半年盘点，不想你错过的重磅新书
  • ​批处理文件中的errorlevel用法
  • #pragma预处理命令
  • （1）Nginx简介和安装教程
  • （173）FPGA约束：单周期时序分析或默认时序分析
  • (2)Java 简介
  • （39）STM32——FLASH闪存
  • (4) openssl rsa/pkey(查看私钥、从私钥中提取公钥、查看公钥)
  • （C语言）输入自定义个数的整数，打印出最大值和最小值
  • (env: Windows,mp,1.06.2308310； lib: 3.2.4) uniapp微信小程序
  • （pytorch进阶之路）扩散概率模型
  • （附源码）ssm高校升本考试管理系统 毕业设计 201631
  • (附源码)计算机毕业设计SSM智能化管理的仓库管理
  • （一一四）第九章编程练习
  • (转)Android中使用ormlite实现持久化(一)--HelloOrmLite
  • (转)Java socket中关闭IO流后，发生什么事？（以关闭输出流为例） .
  • （转）JAVA中的堆栈
  • （转）ObjectiveC 深浅拷贝学习
  • （转）编辑寄语：因为爱心，所以美丽
  • (转)菜鸟学数据库（三）——存储过程
  • ******IT公司面试题汇总+优秀技术博客汇总