头像

ranba




离线:5天前


活动打卡代码 AcWing 439. 细胞分裂

ranba
5天前
#include <iostream>
#include <cmath>
using namespace std;

const int N = 1e4+10;
int n, m1, m2, s;
int a[100],b[100], cnt;

int main() {
    cin >> n >> m1 >> m2;

    int factor = 1;
    for (int i = 2; i <= m1; i ++) {
        if (m1%i == 0) {
            factor *= i;
            cnt ++;
            a[cnt] = i;
            b[cnt] ++;
            m1 /= i;

            while (m1%i == 0) {
                b[cnt] ++;
                m1 /= i;
            }
        }
    }

    for (int i = 1; i <= cnt; i ++) {
        b[i] *= m2;
    }

    bool flag = true;
    int minn = 1e9, maxx;
    for (int i = 1; i <= n; i ++) {
        cin >> s;
        if (s%factor == 0) {
            flag = false;
            maxx = 0;
            for (int j = 1; j <= cnt; j ++) {
                int t = s, count = 0;
                while (t%a[j] == 0) {
                    count ++;
                    t /= a[j];
                }
                maxx = max(maxx, int(ceil(b[j]*1.0/count)));
            }           
            minn = min(minn, maxx);
        }
    }

    if (flag) cout << -1;
    else cout << minn;

    return 0;
}



ranba
4个月前
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;

const int N = 510, INF = 0x3f3f3f3f;
int n, m;       //n表示点数
int g[N][N];    //用邻接矩阵存储所有边
int dist[N];    //存储其它点到点集st的距离(代价)
bool st[N];     //标记每个点是否已经被加入到集合

//如果图不连通,则返回INF;否则返回最小生成树的边权之和
int prim() {
    int res = 0;
    //初始化所有点的距离为正无穷
    memset(dist, 0x3f, sizeof(dist));

    //开始时可以将任意一个点的距离设为0,这样第一次循环时,就会把该点加入到集合
    //因为n >= 1,所以选点1
    //因为是第一个点,所以dist[1] = 0
    dist[1] = 0;

    //因为要找n个点,所以循环n次
    for (int i = 1; i <= n; i ++) {
        //从其它点中,寻找到集合距离最短(代价最小)的一个点,记为t
        int t = 0;
        for (int j = 1; j <= n; j ++) {
            if (!st[j] && dist[j] < dist[t]) {
                t = j;
            }
        }

        //如果t == 0,意味着其它点和集合中的点均没有连接,这种情况下不存在最小生成树
        if (t == 0) return INF;

        //将边权之和加上点t到集合的距离;把点t标记为在集合中
        res += dist[t];
        st[t] = true;

        //点t是距离最短(代价最小)的点,用它来更新剩余点到集合的距离(代价)
        for (int j = 1; j <= n; j ++) {
            if (!st[j]) dist[j] = min(dist[j], g[t][j]);
        }
    }

    return res;
}

int main() {
    scanf("%d%d", &n, &m);

    int u, v, w;
    memset(g, 0x3f, sizeof(g));
    for (int i = 1; i <= m; i ++) {
        scanf("%d%d%d", &u, &v, &w);
        g[u][v] = g[v][u] = min(g[u][v], w);    //如果两点之间有重边,存储最小的权重
    }

    int t = prim();

    if (t == INF) puts("impossible");
    else printf("%d\n", t);

    return 0;
}



ranba
7个月前
#include <iostream>
#include <cstring>

using namespace std;

const int N = 510;
int n, m, e[N][N], dist[N];
bool vst[N];

int dijkstra() {
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;

    for (int i = 1; i < n; i ++ ) {
        int t = -1;
        for (int j = 1; j <= n; j ++ ) {
            if (!vst[j] && (t == -1 || dist[j] < dist[t])) {
                t = j;
            }
        }
        vst[t] = true;

        for (int j = 1; j <= n; j ++ ) {
            dist[j] = min(dist[j], dist[t] + e[t][j]);
        }
    }

}

int main() {
    cin >> n >> m;

    memset(e, 0x3f, sizeof(e));

    int x, y, z;
    for (int i = 1; i <= m; i ++ ) {
        cin >> x >> y >> z;
        e[x][y] = min(e[x][y], z);
    }

    dijkstra();

    if (dist[n] == 0x3f3f3f3f) cout << -1;
    else cout << dist[n] << endl;

}


活动打卡代码 AcWing 844. 走迷宫

ranba
7个月前
#include <iostream>
#include <cstring>

using namespace std;

const int N = 105;
int e[N][N], d[N][N];
int n, m;

struct node{
    int x, y;
} q[11000];
int hh, tt;

void bfs() {
    memset(d, -1, sizeof d);
    d[1][1] = 0;    
    q[++tt] = {1,1};

    while (hh < tt) {
        int a = q[hh + 1].x;
        int b = q[hh + 1].y;

        if (a-1>=1 && d[a-1][b] == -1 && !e[a][b]) q[++tt] = {a-1, b}, d[a-1][b] = d[a][b] + 1;
        if (a+1<=n && d[a+1][b] == -1 && !e[a][b]) q[++tt] = {a+1, b}, d[a+1][b] = d[a][b] + 1;
        if (b-1>=1 && d[a][b-1] == -1 && !e[a][b]) q[++tt] = {a, b-1}, d[a][b-1] = d[a][b] + 1;
        if (b+1<=m && d[a][b+1] == -1 && !e[a][b]) q[++tt] = {a, b+1}, d[a][b+1] = d[a][b] + 1;

        hh ++ ;
    }
}

int main() {
    cin >> n >> m;

    for (int i = 1; i <= n; i ++ ) {
        for (int j = 1; j <= m; j ++ ) {
            cin >> e[i][j];
        }
    }

    bfs();

    // for (int i = 1; i <= n; i ++ ) {
    //     for (int j = 1; j <= m; j ++ ) {
    //         cout << d[i][j] << ' ';
    //     }
    //     cout << endl;
    // }    

    cout << d[n][m] << endl;

    return 0;
}


活动打卡代码 AcWing 842. 排列数字

ranba
7个月前
#include <iostream>

using namespace std;

int n, path[10];
bool vst[10];

void dfs(int u) {
    if (u > n) {
        for (int i = 1; i <= n; i ++ ) cout << path[i] << ' ';
        cout << endl;

        return;
    }

    for (int i = 1; i <= n; i ++ ) {
        if (!vst[i]) {
            vst[i] = true;
            path[u] = i;

            dfs(u + 1);
            vst[i] = false;
        }
    }
}

int main() {
    cin >> n;

    dfs(1);

    return 0;
}


活动打卡代码 AcWing 854. Floyd求最短路

ranba
7个月前
#include <cstdio>
#include <iostream>

using namespace std;

const int N = 210;
int e[N][N], n, m, Q;
int INF = 1e9;

int main() {
    cin >> n >> m >> Q;

    for (int i = 1; i <= n; i ++ ) {
        for (int j = 1; j <= n; j ++ ) {
            if (i == j) e[i][j] = 0;
            else e[i][j] = INF;
        }
    }

    int x, y, z;
    while (m -- ) {
        cin >> x >> y >> z;
        e[x][y] = min(e[x][y], z);      //可能有重边
    }

    for (int k = 1; k <= n; k ++ ) {
        for (int i = 1; i <= n; i ++ ) {
            for (int j = 1; j <= n; j ++ ) {
                e[i][j] = min(e[i][j], e[i][k] + e[k][j]);
            }
        }
    }

    while (Q -- ) {
        cin >> x >> y;
        if (e[x][y] > INF / 2) cout << "impossible" << endl; 
        else cout << e[x][y] << endl;
    }

    return 0;
}


活动打卡代码 AcWing 847. 图中点的层次

ranba
7个月前
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>

using namespace std;

const int N = 100010;
int n, m;
int h[N], e[N], ne[N], idx;
int d[N];

void add(int a, int b) {
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}

int bfs() {
    memset(d, -1, sizeof d);

    queue<int> q;
    d[1] = 0;
    q.push(1);

    while (q.size()) {
        int t = q.front();
        q.pop();

        for (int i = h[t]; i != -1; i = ne[i]) {
            int j = e[i];

            if (d[j] == -1) {
                d[j] = d[t] + 1;
                q.push(j);
            }
        }
    }

    return d[n];
}

int main() {
    scanf("%d %d", &n, &m);
    memset(h, -1, sizeof h);        //一定要初始化!!

    for (int i = 0; i < m; i ++ ) {
        int a, b;
        scanf("%d %d", &a, &b);
        add(a, b);
    }

    cout << bfs();

    return 0;
}




活动打卡代码 AcWing 846. 树的重心

ranba
7个月前
#include <cstdio>
#include <iostream>
#include <cstring>

using namespace std;

const int N = 1e5+10, M = 2 * N;

int n, h[N], e[M], ne[M], idx;
int ans = N;
bool vst[N];

void add(int a, int b) {
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}

int dfs(int u) {
    vst[u] = true;

    int size = 0, sum = 0;
    for (int i = h[u]; i != -1; i = ne[i]) {
        int j = e[i];
        if (vst[j]) continue;

        int s = dfs(j);
        size = max(size, s);
        sum += s;
    }

    size = max(size, n - 1 - sum);
    ans = min(ans, size);

    return sum + 1;
}

int main() {
    scanf("%d", &n);
    memset(h, -1, sizeof h);

    for (int i = 1; i < n; i ++ ) {
        int a, b;
        scanf("%d %d", &a, &b);
        add(a, b), add(b, a);
    }

    // for (int i = 1; i <= n; i ++ ) {
    //     cout << endl << i << ':';
    //     for (int j = h[i]; j != -1; j = ne[j]) {
    //         cout << e[j] << ' ';
    //     }
    // }

    dfs(1);

    printf("%d\n", ans);

    return 0;
}



活动打卡代码 AcWing 438. 分数线划定

ranba
8个月前
#include<bits/stdc++.h>
using namespace std;

const int N = 5010;

int main(){
    int n, k[N], s[N];
    double m;
    cin >> n >> m;

    for(int i = 1; i <= n; i++){
        cin >> k[i] >> s[i];
    }
    //paixv
    for(int i = n; i > 1; i--){
        int t = i;
        for(int j = 1; j <= i; j++){
            if(s[j] < s[t]) t = j;
            else if(s[j] == s[t]){
                if(k[j] > k[t]) t = j;
            }
        }

        swap(k[i], k[t]);
        swap(s[i], s[t]);
    }

    //shaixuan
    int ress, resk = 0;
    for(int i = 1; i <= n; i++){
        ress = s[int(m*1.5)];
        if(s[i] >= s[int(m*1.5)]){
            resk ++;
        }
    }

    cout << ress <<' '<< resk<<endl;
    for(int i = 1; i <= n; i++){
        if(s[i] >= s[int(m*1.5)]){
            cout << k[i]<<' '<< s[i]<<endl;
        }
    }

    return 0;
}


活动打卡代码 AcWing 446. 统计单词数

ranba
8个月前
#include<bits/stdc++.h>
using namespace std;

const int N = 1e6+10;

int main(){
    string a, b;
    getline(cin, a);
    getline(cin, b);

    for(int i = 0; i < a.size(); i ++){
        if(a[i] >= 'A' && a[i] <= 'Z') a[i] += 32;  
    }
    for(int i = 0; i < b.size(); i ++){
        if(b[i] >= 'A' && b[i] <= 'Z') b[i] += 32;  
    }

    int cnt = 0, min = 1e6;
    for(int i = 0; i < b.size(); i ++){
        int j = i;
        while(b[j] != ' ' && j <= b.size()) j ++;

        if(b.substr(i, j-i) == a) {
            cnt ++;
            if(i < min) min = i;
        }

        i = j;

    }

    if(cnt == 0) cout << -1;
    else cout << cnt <<' '<< min;

    return 0;
}