2020 樂山師范學院程式設計大賽題解
比賽鏈接
交題要在題庫搜索對應的題才能交
總結：
心態爆炸！！！
被 F F F 卡 i n t int int
被 C C C 卡 I N F INF INF
算完 E E E 的復雜度不敢寫
心態爆炸
A: 好數對
題意：
給定一個長度為 n n n 的 a a a 陣列， 如果存在一個下標 i , j , i < j i,j, i<j i,j,i<j 并且 a [ i ] = = a [ j ] a[i] == a[j] a[i]==a[j]，就是好數對，求有多少個這樣的數對
思路：
各種方法都行，直接通過下標計數法快速計算
代碼：
#include <bits/stdc++.h>
using namespace std;
#define me(a, b) memset(a, b, sizeof(a))
#define IOS() ios::sync_with_stdio(false), cin.tie(0)
#define endl '\n'
typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
const int INF = 0x3f3f3f3f;
const int maxn = 2e5 + 5;
const ll mod = 1e9 + 7;
int cnt[maxn];
int main()
{
IOS();
int n;
ll ans = 0;
cin >> n;
for(int i = 0; i < n; ++i) {
int x;
cin >> x;
ans += cnt[x];
++cnt[x];
}
cout << ans << endl;
return 0;
}
B: 設計網頁
題意：
給定一個 n n n， 問是否能找到 a ? b = = n , a > 1 , b > 1 a*b == n, a>1,b>1 a?b==n,a>1,b>1，
思路：
直接判斷 n n n 是不是素數，因為素數的因子只有 1 1 1 和本身
代碼：
#include <bits/stdc++.h>
using namespace std;
#define me(a, b) memset(a, b, sizeof(a))
#define IOS() ios::sync_with_stdio(false), cin.tie(0)
#define endl '\n'
typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
const int INF = 0x3f3f3f3f;
const int maxn = 2e5 + 5;
const ll mod = 1e9 + 7;
int main()
{
int n;
cin >> n;
int flag = 1;
for(int i = 2; i*i <= n; ++i)
if(n % i == 0) {
flag = 0;
break;
}
if(flag == 1) cout << "YES\n";
else cout << "NO\n";
return 0;
}
C: 最大乘積
題意：
給定長度為 n n n 的陣列，問選 5 5 5 個數相乘最大可以的結果是多少
思路：
其實是分情況討論，但分情況討論寫起來很麻煩，直接暴力就
將陣列從小到大排序，
前面選 0 0 0 個, 后面選 5 5 5個
前面選 1 1 1 個, 后面選 4 4 4個
前面選 2 2 2 個, 后面選 3 3 3個
…
前面選 5 5 5 個, 后面選 0 0 0個
所有結果選一個最大值即可
資料范圍超出了 i n t int int，
代碼：
#include <bits/stdc++.h>
using namespace std;
#define me(a, b) memset(a, b, sizeof(a))
#define IOS() ios::sync_with_stdio(false), cin.tie(0)
#define endl '\n'
typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
const ll INF = 0x3f3f3f3f3f3f3f3f;
const int maxn = 2e5 + 5;
const ll mod = 1e9 + 7;
ll num[maxn];
int main()
{
IOS();
int T;
cin >> T;
while(T--) {
int n;
cin >> n;
for(int i = 0; i < n; ++i)
cin >> num[i];
sort(num, num+n);
ll ans = -INF;
for(int i = 0; i <= 5; ++i) {
ll sum = 1;
for(int j = 0; j < i; ++j)
sum *= num[j];
for(int j = n-5+i; j < n; ++j)
sum *= num[j];
ans = max(ans, sum);
}
cout << ans << endl;
}
return 0;
}
D: 后綴語言
題意：
給定一個字串，根據字串的后綴判斷是哪國語言
思路：
直接看最后一個字母就完了
代碼：
#include <bits/stdc++.h>
using namespace std;
#define me(a, b) memset(a, b, sizeof(a))
#define IOS() ios::sync_with_stdio(false), cin.tie(0)
#define endl '\n'
typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
const ll INF = 0x3f3f3f3f3f3f3f3f;
const int maxn = 2e5 + 5;
const ll mod = 1e9 + 7;
int main()
{
IOS();
int T;
cin >> T;
while(T--) {
string s;
cin >> s;
char c = *s.rbegin();
if(c == 'o') {
cout << "FILIPINO\n";
}
else if(c == 'u') {
cout << "JAPANESE\n";
}
else {
cout << "KOREAN\n";
}
}
return 0;
}
E: 分石頭
題意：
給定一堆石頭，每個石頭都有重量，要求分成兩堆，每堆之間的重量盡可能平均，
思路：
01 01 01 背包，復雜度 O ( n ? n ? w / 2 ) = 1.8 ? 1 0 8 O(n*n*w/2) = 1.8*10^8 O(n?n?w/2)=1.8?108
這題直接無語
代碼：
#include <bits/stdc++.h>
using namespace std;
#define me(a, b) memset(a, b, sizeof(a))
#define IOS() ios::sync_with_stdio(false), cin.tie(0)
#define endl '\n'
typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
const ll INF = 0x3f3f3f3f3f3f3f3f;
const int maxn = 2e5 + 5;
const ll mod = 1e9 + 7;
int dp[3000005];
int w[maxn];
int main()
{
IOS();
int n;
cin >> n;
int sum = 0;
for(int i = 1; i <= n; ++i) {
cin >> w[i];
sum += w[i];
}
ll lim = sum/2;
for(int i = 1; i <= n; ++i) {
for(int j = lim; j >= w[i]; --j)
dp[j] = max(dp[j], dp[j-w[i]]+w[i]);
}
ll ans = abs(sum-2*dp[lim]);
cout << ans << endl;
return 0;
}
F: 我的魔法
題意：
你有 a a a 個紅寶石 b b b 個藍寶石 c c c 個紅藍寶石，紅藍寶石可以相互轉成紅色或藍色，現在你要消耗 x x x 個紅寶石 y y y 個藍寶石 z z z 個任意寶石，問夠不夠
思路：
先算紅寶石夠不夠，不夠從紅藍寶石扣除
如果夠多余的就記著加到 s u m sum sum 上
藍寶石同上
最后就是判斷 c > = 0 a n d s u m + c > = z c >= 0 and sum + c >= z c>=0andsum+c>=z
代碼：
#include <bits/stdc++.h>
using namespace std;
#define me(a, b) memset(a, b, sizeof(a))
#define IOS() ios::sync_with_stdio(false), cin.tie(0)
#define endl '\n'
typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
const int INF = 0x3f3f3f3f;
const int maxn = 2e5 + 5;
const ll mod = 1e9 + 7;
int main()
{
IOS();
ll a, b, c;
ll x, y, z;
cin >> a >> b >> c;
cin >> x >> y >> z;
ll sum = 0;
if(a >= x)
sum += a-x;
else
c -= x-a;
if(b >= y)
sum += b-y;
else
c -= y-b;
if(c < 0 || c + sum < z) {
cout << "There are no miracles in life\n";
}
else cout << "It is a kind of magic\n";
return 0;
}
G: 最大公約數
題意：
給定一個數 n n n，另外任意整數 a a a 和 b b b 的最大公約數記為 g c d ( a , b ) gcd(a, b) gcd(a,b)，求解從 1 1 1 到 n n n 中的任意兩個不相同的整數的最大公約數的最大值，
思路：
如果 n n n 是偶數，那么 a = n / 2 , b = n a = n/2, b = n a=n/2,b=n，這樣最大公因數就是 n / 2 n/2 n/2，很明顯這是最大的因為 a < b a < b a<b
如果 n n n 是奇數，那么 n ? 1 n-1 n?1 是偶數，那就回到第一條，所以答案就是 n / 2 n/2 n/2，
代碼：
#include <bits/stdc++.h>
using namespace std;
#define me(a, b) memset(a, b, sizeof(a))
#define IOS() ios::sync_with_stdio(false), cin.tie(0)
#define endl '\n'
typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
const ll INF = 0x3f3f3f3f3f3f3f3f;
const int maxn = 2e5 + 5;
const ll mod = 1e9 + 7;
ll num[maxn];
int main()
{
IOS();
int T;
cin >> T;
while(T--) {
int n;
cin >> n;
cout << n/2 << endl;
}
return 0;
}
H: 最小公倍數
題意：
給定一個整數 b b b，另外 a a a 表示 1 1 1 到 1 0 18 10^{18} 1018 中的所有整數，計算式子 [ a , b ] / a [a, b] / a [a,b]/a 有多少個不同的結果，這里 [ a , b ] [a, b] [a,b] 表示整數 a a a 與整數 b b b 的最小公倍數，
思路：
化解公式 求
l c m ( a , b ) / a = ( a ? b / g c d ( a , b ) ) / a = b / g c d ( a , b ) lcm(a,b)/a = (a*b/gcd(a,b))/a = b/gcd(a,b) lcm(a,b)/a=(a?b/gcd(a,b))/a=b/gcd(a,b)
因為 a a a 取值范圍超過 b b b，所以 g c d ( a , b ) gcd(a, b) gcd(a,b) 的結果就都是 b b b 的因子
所以答案就轉換成求 b b b 有多少個因子
代碼：
#include <bits/stdc++.h>
using namespace std;
#define me(a, b) memset(a, b, sizeof(a))
#define IOS() ios::sync_with_stdio(false), cin.tie(0)
#define endl '\n'
typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
const int INF = 0x3f3f3f3f;
const int maxn = 2e5 + 5;
const ll mod = 1e9 + 7;
int main()
{
IOS();
ll b;
cin >> b;
ll cnt = 0;
for(ll i = 1; i*i <= b; ++i) {
if(b % i == 0) {
++cnt;
if(b / i != i) ++cnt;
}
}
cout << cnt << endl;
return 0;
}
I: 絕對值游戲
題意：
有兩個元素個數長度相等的陣列 a a a 和 b b b , 每一輪都會從每個陣列拿走一個數字，到最后只剩下一個數字結束，一個人希望剩下的數字絕對值之差最大，一個人希望最小，最后的絕對值是多少.
思路：
不管怎么操作一個陣列總會剩下一個數，那么第二個人就會選擇剩下對應絕對值最小的數，所以對第一個陣列的每個數，第二個陣列都能選到相應最小的，那答案很明顯就是所有最小里面選最大的，
這其實就是對應關系，只要第一個陣列不刪這個數，那么第二個陣列也不會洗掉讓它答案最小的數，第一個刪了第二個也就跟著刪.
代碼：
#include <bits/stdc++.h>
using namespace std;
#define me(a, b) memset(a, b, sizeof(a))
#define IOS() ios::sync_with_stdio(false), cin.tie(0)
#define endl '\n'
typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
const int INF = 0x3f3f3f3f;
const int maxn = 2e5 + 5;
const ll mod = 1e9 + 7;
ll a[maxn], b[maxn];
int main()
{
IOS();
int n;
cin >> n;
for(int i = 0; i < n; ++i) {
cin >> a[i];
}
for(int i = 0; i < n; ++i) {
cin >> b[i];
}
ll ans = 0;
for(int i = 0; i < n; ++i) {
ll mi = INF;
for(int j = 0; j < n; ++j)
mi = min(mi, abs(a[i]-b[j]));
ans = max(ans, mi);
}
cout << ans << endl;
return 0;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/237539.html
標籤：其他
下一篇：微信小程式：自定義滾動彈窗