A-迎新小游戲——抽獎品
命題人：19計科C1 占淼
題解：
概率通過組合數求得：
C
a
2
C
a
+
b
2
￣
\begin{aligned}C_{a}^{2}\\ \overline{C_{a+b}^{2}}\end{aligned}
Ca2?Ca+b2???，化簡得：
a
×
(
a
?
1
)
(
a
+
b
)
×
(
a
+
b
?
1
)
\dfrac{a\times \left( a-1\right) }{\left( a+b\right) \times \left( a+b-1\right) }
(a+b)×(a+b?1)a×(a?1)?
記
m
=
a
?
(
a
?
1
)
,
n
=
(
a
+
b
)
?
(
a
+
b
?
1
)
m=a*(a-1),n=(a+b)*(a+b-1)
m=a?(a?1),n=(a+b)?(a+b?1)
運用歐幾里得演算法（輾轉相除法）求出
m
,
n
m,n
m,n的最大公約數
k
k
k，
m
,
n
m,n
m,n同時除以k
Code：
#include <bits/stdc++.h>
using namespace std;
#define ll long long
ll gcd(ll a,ll b) {
return b?gcd(b,a%b):a;
}
int main(void) {
ll a,b;
cin>>a>>b;
ll m=a*(a-1),n=(a+b)*(a+b-1);
ll k=gcd(m,n);
cout<<m/k<<"/"<<n/k<<endl;
return 0;
}
B-Coda’s Fibonacci Password
命題人：19軟工A1 陳萬鵬
題解：
斐波那契數列，根據
a
1
=
a
2
=
1
,
a
i
=
a
i
?
1
+
a
i
?
2
(
i
>
=
3
)
a_1=a_2=1,a_i=a_{i-1}+a_{i-2}(i>=3)
a1?=a2?=1,ai?=ai?1?+ai?2?(i>=3)計算即可，
Code：
#include <bits/stdc++.h>
using namespace std;
int an[20];
int main(void) {
an[1]=an[2]=1;
for(int i=3;i<=10;i++) an[i]=an[i-1]+an[i-2];
int n;
cin>>n;
cout<<an[n]<<endl;
}
C-密室
命題人：19軟工A1 陳萬鵬
題解：
遍歷字串，模擬移動操作，遇到墻壁的時候特判一下
Code：
#include <bits/stdc++.h>
using namespace std;
int main(void) {
string s;
cin>>s;
int x=0,y=0;
for(auto i:s) {
if(i=='l') x--;
if(i=='r') x++;
if(i=='u') y--;
if(i=='d') y++;
if(x<0) x=0;
if(x>99) x=99;
if(y<0) y=0;
if(y>99) y=99;
}
cout<<x<<" "<<y<<endl;
return 0;
}
D-迎新小游戲——送禮物
命題人：19計科C1 占淼
題解：
如果剛好能平均分就0
否則，計算當前每個人能分到的數，加1，乘以人數，減去當前有的
Code：
#include <bits/stdc++.h>
using namespace std;
#define ll long long
int main(void) {
ll a,b;
cin>>a>>b;
cout<<(b%a==0?0:(b/a+1)*a-b)<<endl;
return 0;
}
E-CSGO與IU
命題人：19軟工A2 陳旭東
題解：
用string的find函式找到需要替換的字符，替換即可
手動模擬find函式的查找程序也可
Code：
#include <bits/stdc++.h>
using namespace std;
int main(void) {
string s;
getline(cin,s);
while(1) {
int pos=s.find("iu");
if(pos==s.npos) break;
s[pos]='I';
s[pos+1]='U';
}
while(1) {
int pos=s.find("csgo");
if(pos==s.npos) break;
s[pos]=s[pos+1]='s';
s[pos+2]='p';
s[pos+3]='u';
}
cout<<s<<endl;
return 0;
}
F-迎新小游戲——排隊形
命題人：19計科C1 占淼
題解：
f
(
i
,
j
,
k
,
m
)
f(i,j,k,m)
f(i,j,k,m) 表示選
i
i
i個男生，
j
j
j個女生，最后連續
k
k
k個m，以
m
m
m結尾的情況數，
轉移方程分為
k
=
1
k=1
k=1和
k
>
1
k>1
k>1兩種情況：
a.
k
=
1
k=1
k=1時，以0結尾為例
f
[
i
]
[
j
]
[
1
]
[
0
]
=
∑
k
=
1
m
i
n
(
j
,
k
2
)
f
[
i
?
1
]
[
j
]
[
k
]
[
1
]
f[i][j][1][0] = \sum ^{min(j,k2)}_{k=1} f[i-1][j][k][1]
f[i][j][1][0]=k=1∑min(j,k2)?f[i?1][j][k][1]
b.
k
>
1
k>1
k>1時，以0結尾為例
f
[
i
]
[
j
]
[
k
]
[
0
]
+
=
f
[
i
?
1
]
[
j
]
[
k
?
1
]
[
0
]
f[i][j][k][0]+=f[i-1][j][k-1][0]
f[i][j][k][0]+=f[i?1][j][k?1][0]
最后求和
壓軸題，這題存在的目的就是不能有人通過所有題，最后還是成功卡住了軒神哈哈哈哈
Code：
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int maxn=110,maxp=20,mod=998244353;
ll f[maxn][maxn][maxp][maxp];
int main(void) {
int n,m,p,q;
cin>>n>>m>>p>>q;
for(int i=1;i<=p;i++) f[i][0][i][0]=1;
for(int i=1;i<=q;i++) f[0][i][i][1]=1;
for(int i=1;i<=n;i++) {
for(int j=1;j<=m;j++) {
for(int k=1;k<=min(j,q);k++) (f[i][j][1][0]+=f[i-1][j][k][1])%=mod;
for(int k=1;k<=min(i,p);k++) (f[i][j][1][1]+=f[i][j-1][k][0])%=mod;
for(int k=2;k<=min(i,p);k++) (f[i][j][k][0]+=f[i-1][j][k-1][0])%=mod;
for(int k=2;k<=min(j,q);k++) (f[i][j][k][1]+=f[i][j-1][k-1][1])%=mod;
}
}
ll ans=0;
for(int i=1;i<=p;i++) (ans+=f[n][m][i][0])%=mod;
for(int i=1;i<=q;i++) (ans+=f[n][m][i][1])%=mod;
cout<<ans<<endl;
return 0;
}
G-A Broken Ancient Robot
命題人：19軟工A1 陳萬鵬
題解：
簽到題，直接輸出"Error!" (不帶引號)
Code：
#include <bits/stdc++.h>
using namespace std;
int main(void) {
cout<<"Error!\n";
return 0;
}
H-Raki的學習小劇場
命題人：19軟工A1 劉仲家
題解：
按題意排序即可
難點在于結構體排序，可以在結構體內部多載運算子，也可以自定義一個排序函式
C++可以直接呼叫sort()函式進行快速排序，C語言中的qsort()也具有相同的功能
Code：
#include <bits/stdc++.h>
using namespace std;
const int maxn=1e6+10;
struct node {
int val,id;
bool operator<(const node &a) const {
if(val==a.val) return id<a.id;
return val>a.val;
}
} an[maxn];
vector<int> vt;
int main(void) {
int n,k;
cin>>n>>k;
for(int i=1;i<=n;i++) {
int a,b,c;
cin>>a>>b>>c;
an[i]={a/b*c,i};
}
sort(an+1,an+n+1);
for(int i=1;i<=k;i++) vt.push_back(an[i].id);
sort(vt.begin(),vt.end());
for(int i=0;i<vt.size();i++) cout<<vt[i]<<" ";
cout<<endl;
return 0;
}
I-新冠病毒之解救Coda
命題人：19軟工A2 陳旭東
題解：
預處理前綴和
然后二分答案，判斷當前長度是否有解，根據結果縮小區間
雙指標演算法也可以
Code：
#include <bits/stdc++.h>
using namespace std;
const int maxn=2e6+10;
#define ll long long
ll n,k;
ll an[maxn],sum[maxn];
bool check(int len) {
for(int l=1;l+len-1<=n;l++) {
int r=l+len-1;
if(sum[r]-sum[l-1]<=k) return 1;
}
return 0;
}
int main(void) {
ios::sync_with_stdio(0);
cin>>n>>k;
for(int i=1;i<=n;i++) cin>>an[i],sum[i]=sum[i-1]+an[i];
int l=0,r=n;
while(l<r) {
int mid=l+r+1>>1;
if(check(mid)) l=mid;
else r=mid-1;
}
cout<<l<<endl;
return 0;
}
J-旅游難題
命題人：19軟工A1 劉仲家
題解：
使
n
n
n個城市互連最少需要
n
?
1
n-1
n?1條航線
在
n
n
n個城市互連的前提下，任意再連1條航線，即可實作存在城市滿足"在不原路回傳的情況下回到原來的城市"
Code:
#include <bits/stdc++.h>
using namespace std;
int main(void) {
int T;
scanf("%d",&T);
while(T--) {
int n,m;
scanf("%d %d",&n,&m);
if(m>=n-1) cout<<"YES ";
else cout<<"NO ";
if(m>=n) cout<<"YES\n";
else cout<<"NO\n";
}
return 0;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/ruanti/233163.html
標籤：其他