比賽鏈接

文章目錄

• A題 A Simple Problem about election
• • 題目描述
  • 題解：
  • 代碼：
• D題 Deploy the medical team
• • 題意：
  • 題解：
  • 代碼：
• F題 Figure out the sequence
• • 題意：
  • 題解：
  • 代碼

A題 A Simple Problem about election

鏈接：

題目描述

n名候選人，每個人必須提名其中m個人，（也可以提名自己），候選人將按照獲得的提名降序排列，如果數量相同則按照名字字典序遞增排列。
每個人也是按照名字依次提名m人，
叫ZZZZSGW的這個人感覺自己太倒霉了，（名字這么多z，每次提名），他最后提名，問還能不能讓自己獲得最高地位？

樣例：
輸入

2 5 3 5 1 2 6 7 5 3 5 1 2 5 7

輸出

3 2

題解：

自己肯定還是要給的，然后剩下的m-1個票就要盡可能與自己票數相差大的人（也就是不對自己的排名造成影響），有兩種情況，一個是比自己票多的，還有個是被投一票也趕不上自己的
但是如果票過多，就只能被迫給剩下的人投票
貪心即可
詳細見代碼

代碼：

#include<bits/stdc++.h> #define forr(n) for(int i=1;i<=n;i++) using namespace std; const int maxn=1e5+7; int a[maxn]; int main(){int T,ans=0;;cin>>T;while(T--){int n,m;scanf("%d%d",&n,&m);forr(n)cin>>a[i];int w=++a[1];//先給自己投票 int q=m;--q;//投完自己，投票次數少一個 if(q==0);else {for(int i=2;i<=n;++i){if(a[i]>=w)//如果票比他多 {++a[i];--q;}else if(a[i]+1<w)//如果這個人投一票也趕不上 {++a[i];--q;}if(!q)//如果都投完退出 {break;}}}for(n){if(a[i]>=a[1])ans++;}//全部投完票后看看自己排第幾名 cout<<ans+q<<endl;//如果還有余票 }return 0; }

D題 Deploy the medical team

鏈接：

題目描述

The outbreak of the COVID-19 has infected more than 50,000 people in
Wuhan and nearly 70,000 people in Hubei province, which brings on
great pressure on the local hospital and medical workers. To help the
people in Hubei defeating the virus and returning to normal life as
soon as possible, many other province deployed their medical teams to
Hubei and offered lots of help.

Now it’s the time for a hospital in Bitland to choose who will be sent
to join this great mission. There are nn medical workers in the
hospital ready to deploy and you can send arbitrary numbers of persons
to the team. Also, a medical team need a captain in charge of all the
work, so once we confirm the people in the team, we need to set one of
them as captain too. However, being a captain needs a lot experience,
so there are only mm people capable with the responsibility of a
captain. Therefore, A team cannot be made up of people without someone
that can be the captain.

And here’s the question: How many ways are there to pick up a medical
team with a captain? Notice that two teams are consider different as
long as they have different participants or have different captain.

Also, due to the large memory of Bitland, the number of workers in
hospital can be as large as 10⁹ ! And that means your answer can be
very large, so please output the result of the answer modulo 10⁹+7

輸入描述:

The input consists of multiple test cases. The first line of the input
contains an integer T — the number of the test cases.

For each test cases, there will be two integers nn,mm separated by
space in one line, which means the number of workers in hospital and
the numbers of people who can be the captain. Here 0≤m≤n≤10⁹ .

輸出描述:

For each test case, output a single integer ansans in a line, denoting
the answer modulo 10⁹+7

示例1
輸入

3 3 3 5 4 2 1

輸出

12 64 2

題意：

一共n個人，m個人可以當隊長，每個隊只能有一個隊長，也必須有一個隊長，問組隊方法？
（最討厭英語題了）

題解：

組合數問題
先從m人中選一個隊長，剩下n-1個人任選即可
C⁰_n-1+C¹_n-1+C²_n-1…+C^n-1_n-1=2^n-1
sum=m*2^n-1

代碼：

#include<bits/stdc++.h> using namespace std; typedef long long ll; const int mod=1e9+7; ll qpow(ll a, ll b) {ll ans = 1;while(b) {if(b & 1) ans = ans * a % mod;a = a * a % mod;b >>= 1;}return ans; } int T; ll n, m; int main() {cin >> T;while(T--) {cin >> n >> m;printf("%lld\n",m * qpow(2, n - 1) % mod );}return 0; }

F題 Figure out the sequence

題意：

兩個字符串，一次疊加，問你n輪后，每個字母出現個數

樣例：
鏈接：https://ac.nowcoder.com/acm/contest/5523/F
來源：牛客網

輸入

Abc def 4

輸出

A: 1 b: 1 c: 1 d: 2 e: 2 f: 2

根據樣例輸入我們可以都到每輪疊加后的串

n=4時就是 defabcdef
分別統計每個字母的個數

題解：

dp
我們可以看出要求第n輪，就是第n-1輪加n-2輪
因為問的是個數，所以不用管順序遞推就可以
f[i][j]表示第i個字符串中字母j出現的次數（此處j為int型對應的是char型的字符）
得到遞推式：f [ i ] [ j ] = f[ i - 1 ] [ j ]+ f [ i -2 ] [ j ]
我們一開始將讀入的s1和s2進行預處理
也就是先給f[1][j]與f[2][j]賦值
具體可以看代碼：

代碼

#include<bits/stdc++.h> #define forr(i,n) for(int i=0;i<n;i++) using namespace std; typedef long long ll; const int maxn=1e5+7; ll f[maxn][1000]; inline ll read() {ll s=0,w=1;char ch=getchar();while(ch<48||ch>57){if(ch=='-')w=-1;ch=getchar();}while(ch>=48&&ch<=57)s=(s<<1)+(s<<3)+(ch^48),ch=getchar();return s*w; } int main() {string s1,s2;int n;cin>>s1>>s2;n=read();forr(i,s1.size()){int w=(int)s1[i];f[1][w]++; // printf("%c %lld\n",w,f[1][w]);}forr(i,s2.size()){int w=(int)s2[i];f[2][w]++;}for(int i=3;i<=n;i++){forr(j,300){f[i][j]=f[i-1][j]+f[i-2][j];}}forr(j,300){if(f[n][j])printf("%c: %lld\n",j,f[n][j]);}return 0;} //“defabcdef”

總結

以上是生活随笔為你收集整理的“Shopee杯” e起来编程暨武汉大学2020年大学生程序设计大赛决赛（重现赛）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。