寒假每日一題（入門組）Week2

756. 蛇形矩陣 (1月11日)

分析

定義方向上右下左, 然後res裡放元素即可

關聯leetcode54

code

#include <iostream>
#include <vector>
using namespace std;
const int N = 110
int n, m;

int main(){
    scanf("%d%d", &n, &m);
    int d = 1;
    int dx[] = {-1, 0, 1, 0}, dy[] = {0, 1, 0, -1};
    int x = 0, y = 0;
    vector<vector<int>> res(n, vector<int>(m));
    for (int i = 1; i <= n * m; i ++ ){
        res[x][y] = i;
        int a = x + dx[d], b = y + dy[d];
        if (a < 0 || a >= n || b < 0 || b >= m || res[a][b]){
            d = (d + 1) % 4;
            a = x + dx[d], b = y + dy[d];
        }
        x = a, y = b;
    }
    for (int i = 0; i < n; i ++ ){
        for (int j = 0; j < m; j ++ )
            cout << res[i][j] << ' ';
        cout << endl;
    }
    return 0;   
}
           

1113. 紅與黑(1月12日)

分析

洪水灌溉模闆題

code(bfs)

#include <iostream>
#include <queue>
using namespace std;
const int N = 30;
int n, m;
char g[N][N];
typedef pair<int, int> PII;
#define x first
#define y second

int bfs(int x, int y){
    int dx[] = {-1, 0, 1, 0}, dy[] = {0, 1, 0, -1};
    queue<PII> q;
    q.push({x, y});
    int res = 1;
    while (q.size()){
        auto t = q.front(); q.pop();
        for (int i = 0; i < 4; i ++ ){
            int sx = t.x + dx[i], sy = t.y + dy[i];
            if (sx >= 0 && sx < n && sy >= 0 && sy < m && g[sx][sy] == '.'){
                q.push({sx, sy});
                g[sx][sy] = '#';
                res ++;
            }
        }
            
    }
    return res;
}

int main(){
    while (scanf("%d%d", &m, &n), n || m){
        for (int i = 0; i < n; i ++ ) scanf("%s", g[i]);
        
        int x, y;
        for (int i = 0; i < n; i ++ )
            for (int j = 0; j < m; j ++ )
                if (g[i][j] == '@') x = i, y = j;
        cout << bfs(x, y) << endl;
    }
    return 0;
    
}
           

code(dfs)

遞歸中res 記錄由目前點出發可以擴充到哪些點, 然後傳回給上一層

#include <iostream>
#include <queue>
using namespace std;
const int N = 30;
int n, m;
char g[N][N];
typedef pair<int, int> PII;
#define x first
#define y second

int dfs(int x ,int y){
    int dx[] = {-1, 0, 1, 0}, dy[] = {0, 1, 0, -1};
    g[x][y] = '#';
    int res = 1;
    
    for (int i = 0; i < 4; i ++ ){
        int sx = x + dx[i], sy = y + dy[i];
        if (sx >= 0 && sx < n && sy >= 0 && sy < m && g[sx][sy] == '.') {
            res += dfs(sx, sy);
        }
    }
    return res;
}

int main(){
    while (scanf("%d%d", &m, &n), n || m){
        for (int i = 0; i < n; i ++ ) scanf("%s", g[i]);
        
        int x, y;
        for (int i = 0; i < n; i ++ )
            for (int j = 0; j < m; j ++ )
                if (g[i][j] == '@') x = i, y = j;
        cout << dfs(x, y) << endl;
        
    }
    return 0;
    
}
           

1346. 回文平方 (1月13日)

分析

枚舉每一個數, 比如x, 先求下 ( x 2 ) b (x^2)_{b} (x2)b​, 比如 y = ( x 2 ) b y = (x^2)_{b} y=(x2)b​, 如果 y y y是回文數, 那麼輸出 ( x ) b , ( x 2 ) b (x)_b, (x^2)_b (x)b​,(x2)b​

進制轉換

問題在于如何将 ( x ) 10 (x)_{10} (x)10​轉化為b進制的數 ---- 短除法

比如 ( 123 ) 10 (123)_{10} (123)10​ 轉化為3進制

對123 不斷除以3, 直到商為0位置, 右邊是餘數

那麼轉化為3進制後的數為倒着看餘數

課堂練習

( 245 ) 10 = ( x ) 5 (245)_{10} = (x)_5 (245)10​=(x)5​

命題:短除法的正确性

證明:

判斷回文

雙指針算法, i前指針往後走, j後指針往前走, 每次比較下目前所指的數是否相同, 如果不同的話, 就不是回文數, 如果相同, 則繼續往中間靠攏

擴充

1. 10進制轉化為其他進制 — 短除法
2. 其他進制轉化成10進制 ? 直接掃描一遍做

( 11101 ) 2 (11101)_2 (11101)2​

= 1 ∗ 2 4 + 1 ∗ 2 3 + 1 ∗ 2 2 + 0 ∗ 2 1 + 1 ∗ 2 0 =1*2^4 + 1* 2^3 + 1* 2^2 + 0 * 2^1 + 1* 2^0 =1∗24+1∗23+1∗22+0∗21+1∗20

但是寫代碼的時候, 一般不這麼寫, 因為你需要先算下 2 4 , 2 3 , 2 2 , 2 1 , 2 0 2^4, 2^3, 2^2, 2^1, 2^0 24,23,22,21,20, 算的次數比較多

秦九韶算法

比如算 a n x n + a n − 1 x n − 1 + . . . + a 0 x 0 a_nx^n + a_{n - 1}x^{n - 1} + ... + a_0x_0 an​xn+an−1​xn−1+...+a0​x0​

先算 a n a_n an​, 第2次算 a n x + a n − 1 a_nx + a_{n - 1} an​x+an−1​, 然後第3次算 ( a n x + a n − 1 ) ∗ x + a n − 2 (a_nx + a_{n - 1}) * x + a_{n - 2} (an​x+an−1​)∗x+an−2​, 第4次 ( ( a n x + a n − 1 ) ∗ x + a n − 2 ) ∗ x + a n − 3 ((a_nx + a_{n - 1}) * x + a_{n - 2})* x + a_{n - 3} ((an​x+an−1​)∗x+an−2​)∗x+an−3​, 依此類推, 做n + 1次, 就可以計算得到結果

發現隻要做n次加法, n次乘法就可以了, 不需要預處理指數的問題

例子:

( 11101 ) 2 (11101)_2 (11101)2​

計算第2位的時候: 1 ∗ 2 + 1 = 3 1 * 2 + 1 = 3 1∗2+1=3

計算第3位的時候: 3 ∗ 2 + 1 = 7 3 * 2 + 1 = 7 3∗2+1=7

計算第4位的時候: 7 ∗ 2 + 0 = 14 7 * 2 + 0 = 14 7∗2+0=14

計算第5位的時候: 14 ∗ 2 + 1 = 29 14 * 2 + 1 = 29 14∗2+1=29

代碼:

3. 如何将其他進制轉化為其他進制(a進制轉化為b進制)

最簡單的做法 a —> 10 —> b

也可以直接用短除法做

關聯題

acwing 124.進制轉換

code

#include <iostream>
#include <algorithm>
using namespace std;

char get(int x){ // 如果高于10進制, 轉化成A
    if (x <= 9) return x + '0';
    return x - 10 + 'A';
}

string base(int n, int b){ // 短除法
    string num;
    while (n) num += get(n % b), n /= b;
    reverse(num.begin(), num.end());
    return num;
}

bool check(string num){
    for (int i = 0, j = num.size() - 1; i < j; i ++, j -- )
        if (num[i] != num[j]) return false;
    return true;
}
int main(){
    int b;
    cin >> b;
    for (int i = 1; i <= 300; i ++ ){
        auto num = base(i * i, b); // i * i 的 b 進制表示
        if (check(num)){
            cout << base(i, b) << ' ' << num << endl;
        }
    }
    return 0;
}
           

680. 剪繩子(1月14日)

分析

轉換下思想, 如果告訴我們已經切出來x長度, 然後問n根繩子一共可以切出多少條長度為x的, 那就比較容易了

比方說第1條繩子可以裁出1條長度為x的繩子, 第2條繩子可以裁出2條長度為x的繩子, 第3條繩子可以裁出1條長度為x的繩子, 總共可以裁出4條長度為x的繩子, 是以長度為x的繩子, 我們最多可以裁出4條

是以發現直接求最優解不好求, 但是已知x, 讓我們求可以裁出多少根的話, 就比較容易了

考慮能不能用二分, 可以幫助我們将 最優化問題->判定問題

判定問題比原來的問題多了一個額外的條件x

求目前繩子能夠裁剪出多少條長度為x的繩子: ⌊ L i x ⌋ \lfloor \frac{L_i}{x} \rfloor ⌊xLi​​⌋ , 然後周遊下每根繩子, 求和

二分之前, 先考慮下能不能二分(即判斷mid無論何種情況, 能否将區間縮小一半)

假如二分中點mid成立, 那麼答案區間在[mid, R]

mid不成立, 說明答案一定不在右邊, 因為mid⬆️ ∑ ⌊ L i m i d ⌋ \sum \lfloor \frac{Li}{mid} \rfloor ∑⌊midLi​⌋, 會更得更小, 是以答案所在區間變成[L, mid]

是以, 不管怎樣, 答案所在的區間長度都會/2, 不斷/2, 區間長度變得很小, 直到小于eps

code

#include <iostream>
using namespace std;
const int N = 100010;

int n, m;
int w[N];

bool check(double x){
    int cnt = 0;
    for (int i = 0; i < n; i ++ )
        cnt += w[i] / x;
    return cnt >= m;
}

int main(){
    cin >> n >> m;
    for (int i = 0; i < n; i ++ ) cin >> w[i];
    
    double l = 0, r = 1e9;
    while (r - l > 1e-4){
        double mid = (l + r) / 2;
        if (check(mid)) l = mid;
        else r = mid;
    }
    
    printf("%.2lf\n", l);
    return 0;
}
           

1227. 分巧克力(1月15日)

分析

二分長度即可

code

#include <iostream>
using namespace std;
const int N = 1e5 + 10;
int a[N], b[N];
int n, k;

bool check(int x){
    int res = 0;
    for (int i = 0; i < n; i ++ ){
        res += (a[i] / x) * (b[i] / x);
    }
    
    return res >= k;
}

int main(){
    scanf("%d%d", &n, &k);
    for (int i = 0; i < n; i ++ ){
        scanf("%d%d", &a[i], &b[i]);
    }
    
    int l = 1, r = N;
    while (l < r){
        int mid = l + r  + 1 >> 1;
        if (check(mid)) l = mid;
        else r = mid - 1;
    }
    
    printf("%d\n", l);
    return 0;
}
           

422. 校門外的樹(1月16日)

分析

題目給了總區間 求除去給定另外一段區間後, 剩餘的點的數量

直接掃描一遍給的區間, 标記下, 然後再掃描一遍總區間, 對沒打标記的點統計下個數, 就可以了

code

#include <iostream>
using namespace std;
const int N = 100010;
bool st[N];
int res;
int l, m;

int main(){
    cin >> l >> m;
    while (m -- ){
        int a, b;
        scanf("%d%d", &a, &b);
        for (int i = a; i <= b; i ++ ) st[i] = 1;
    }
    
    for (int i = 0; i <= l; i ++ ) res += !st[i];
    
    cout << res << endl;
    return 0;
}
           

429. 獎學金(1月17日)

分析

注意排序的寫法

錯誤寫法(要重視)

struct Stu{
    int a, b, c, sum, id;
    bool operator < (Stu &W){
        return sum > W.sum;
        if (sum == W.sum) return a > W.a;
        if (a == W.a) return id < W.id;
    }
}stu[N];
           

這樣寫

sum == W.sum

的時候會在第1個語句

sum > W.sum

傳回0, 無法繼續判斷

code

#include <iostream>
#include <algorithm>
using namespace std;
const int N = 310;
struct Person{
    int id, sum, a, b, c;
    bool operator < (const Person &w){
        if (sum != w.sum) return sum > w.sum;
        if (a != w.a) return a > w.a;
        return id < w.id;
    }
}p[N];
int n;
int main(){
    cin >> n;
    for (int i = 1; i <= n; i ++) {
        int a, b, c;
        cin >> a >> b >> c;
        p[i] = {i, a + b + c, a, b, c};
    }
    sort(p + 1,  p + n + 1);
    for (int i = 1; i <= 5; i ++) cout << p[i].id << ' ' << p[i].sum << endl;
    return 0;
}