2024/05/03 期中考

選修期中考

Scoreboard

意外的快XD

scoreboard

考試過程

原本想說從

$pA$寫到

$pD$
結果

$pA$太麻煩就直接由後寫到前了:)

$8$

$mins$

$pD$

$AC$

$12$

$mins$

$pC$

$AC$

$14$

$mins$

$pB$

$AC$

$20$

$mins$

$pA$

$AC$

$Total$ :

$20$

$mins$

$4$

$AC$

$$

$0$

$WA$

題目

• pA

  題意 :
  給一數

  $N$ 表示接下來會有

  $N$ 個數字

  $(1\le d\le N)$且數字皆不相同
  把

  $N$ 分成

  $K$ 個集合

  $(1\le K\le N\cap K\times t=N)$
  符合

  $i<j$ 則 第

  $i$ 個集合的數字皆小於第

  $j$ 個集合的數字

  想法 :
  觀察而得 : 在第

  $i$ 段的集合中
  符合題目要求的集合 必只有

  $(i-1)\times (n/k)+1$ ~

  $(i-1)\times (n/k)+(n/k)$ 的數字
  

  
  

  
  所以每次只要看

  $k$ 個集合有沒有都符合題意就行

  code

  ​​​​#include <bits/stdc++.h>
  ​​​​using namespace std;
  ​​​​#define ll long long
  ​​​​int main() {
  ​​​​    ios::sync_with_stdio(false), cin.tie(0);
  
  ​​​​    int n; cin >> n;
  ​​​​    vector<int> v(n);
  ​​​​    for(int &d : v) {cin >> d;}
  
  ​​​​    bool ans = false;
  ​​​​    for(int k = 2; k <= n; k++) {
  ​​​​        if(n % k ==0) {
  ​​​​            bool ok = true;
  ​​​​            for(int i = 0; i < n; i++) {
  ​​​​                if(v[i] > i-i%(n/k)+n/k) {ok = false;}
  ​​​​            }
  ​​​​            if(ok) {cout << k << '\n'; ans = true;}
  ​​​​        }
  ​​​​    }
  
  ​​​​    if(!ans) {cout << "-1\n";}
  
  
  ​​​​}
  

  心得 :
  需要耐心觀察的題目
  但是我先跑去搶

  $pD$ 首殺
  這題最重要的是_通靈出解題思路
  實作不難 (但我卡在i-i%(n/k)+n/k這行XD

• pB

  題意 :
  給三數

  $A$

  $B$

  $C$
  假如有兩數相同則輸出另外一數
  沒有則輸出

  $0$

  思路 :
  if elseif elseif else

  code

  ​​​​#include <bits/stdc++.h>
  ​​​​using namespace std;
  ​​​​#define ll long long 
  ​​​​int main() {
  ​​​​    ios::sync_with_stdio(false), cin.tie(0);
  
  ​​​​    int a, b, c; cin >> a >> b >> c;
  ​​​​    if(a == b) {
  ​​​​        cout << c << '\n';
  ​​​​    } else if(b == c) {
  ​​​​        cout << a << '\n';
  ​​​​    } else if(c == a) {
  ​​​​        cout << b << '\n';
  ​​​​    } else {
  ​​​​        cout << "0\n";
  ​​​​    }
  ​​​​}
  

  心得 :
  abc_a水題

• pC

  題意 :
  給兩數

  $ST$
  求

  $(x,y,z)$ 滿足

  $x+y+z\le S$ 和

  $x\times y\times z\le T$ 有多少組可能
  

  $(1\le S\le 100)$

  思路 :
  

  $S^3\le {10}^6$
  暴力就行 (但其實

  ${10}^6$ 在一些比較古早的環境下會

  $TLE$)
  我有稍微壓一下複雜度以免出事XD
  但很多人

  $S^3$ 過了 就很玄

  code

  ​​​​#include <bits/stdc++.h>
  ​​​​using namespace std;
  ​​​​#define ll long long 
  ​​​​int main() {
  ​​​​    ios::sync_with_stdio(false), cin.tie(0);
  
  ​​​​    ll s, t; cin >> s >> t;
  ​​​​    int ans = 0;
  ​​​​    for(int i = 0; i <= s; i++) {
  ​​​​        for(int j = 0; j <= s-i; j++) {
  ​​​​            for(int k = 0; k <= s-i-j; k++) {
  ​​​​                if((ll)i * j * (k)<=t) {ans++;} 
  ​​​​            }
  ​​​​        }
  ​​​​    }
  ​​​​    cout << ans << '\n';
  ​​​​}
  

  心得 :
  應該又是一題水題:D

• pD

  題意 :
  給一數

  $N$ 代表一陣列有

  $N$ 個數
  你可以對陣列的每一個數做以下操作 :
  把

  $A_i$ 變成 {

  $A_i-1$ or

  $A_i$ or

  $A_i+1$}
  求這個陣列最多同樣的數字有多少個

  思路 :
  

  
  每一行(直的三格)必不相同
  代表我這個數字出現多少次就是在陣列裡面能出現的最多次
  -> 找所有可能的數字的最多出現次數
  1. 開一個陣列然後暴搜

  $1$ ~

  ${10}^5+5$ (

  $1\le A_i\le {10}^5$) 複雜度 :

  $O({10}^5+4)$
  2. map 複雜度 :

  $O(n\times 3)$

  code

  ​​​​#include <bits/stdc++.h>
  ​​​​using namespace std;
  ​​​​#define ll long long 
  ​​​​int main() {
  ​​​​    ios::sync_with_stdio(false), cin.tie(0);
  
  ​​​​    map<int, int> mp;
  ​​​​    int n; cin >> n;
  
  ​​​​    for(int i = 0; i < n; i++) {
  ​​​​        int a; cin >> a;
  ​​​​        mp[a]++;
  ​​​​        mp[a-1]++;
  ​​​​        mp[a+1]++;
  ​​​​    }
  ​​​​    int mx = 0;
  ​​​​    for(auto &d : mp) {
  ​​​​        mx = max(mx, d.second);
  ​​​​    }
  ​​​​    cout << mx << '\n';
  ​​​​}
  

  心得
  當下就真的感覺是這樣寫
  然後就

  $AC$ 證明法
  感覺我好毒瘤XD