头像

小笨

公主岭荣超实验中学




离线:3天前


最近来访(138)
用户头像
普通学生
用户头像
童心
用户头像
OLIVEIRA
用户头像
xxy0727
用户头像
坠落的余晖
用户头像
夜寐
用户头像
Pz.Climb
用户头像
jimhuang
用户头像
敲爱笑的晨晨
用户头像
不拿周赛牌不改名
用户头像
爱吃干煸鱼的大布丁
用户头像
Anoxia_3
用户头像
垫底抽風
用户头像
1234_6
用户头像
wKingYu
用户头像
WangJY
用户头像
冰中月
用户头像
我是好人
用户头像
0x37.
用户头像

活动打卡代码 AcWing 920. 最优乘车

小笨
11天前
#include <iostream>
#include <cstring>
#include <algorithm>
#include <sstream>

using namespace std;

const int N = 510;

bool g[N][N];
int dist[N];
int stop[N];
int n, m;
int q[N];

void bfs()
{
    memset(dist, 0x3f, sizeof dist);
    int hh = 0, tt = 0;
    q[0] = 1;
    dist[1] = 0;

    while(hh <= tt)
    {
        auto t = q[hh ++];

        for(int i = 1; i <= n; i ++ )
        {
            if(g[t][i] &&  dist[i] > dist[t] + 1 )
            {
                q[++ tt] = i;
                dist[i] = dist[t] + 1;
            }
        }
    }
}

int main() 
{
    cin >> m >> n; // m条路线,n条车站

    string line;
    getline(cin, line);

    while(m --)
    {
        getline(cin, line);
        stringstream ssin(line);
        int cnt = 0, p = 0;
        while(ssin >> p) stop[cnt ++] = p;

        for(int i = 0; i < cnt; i ++ )
            for(int k = i + 1; k < cnt; k ++ )
                g[stop[i]][stop[k]] = true;
    }

    bfs();

    if(dist[n] == 0x3f3f3f3f) puts("NO");
    else cout << max(dist[n] - 1, 0) << endl;

    return 0;

}


活动打卡代码 AcWing 1126. 最小花费

小笨
11天前
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 2010;

double dist[N];   
int n, m, S, T;
double g[N][N];
bool st[N];

void Dijkstra()
{
    dist[S] = 1;
    for(int i = 1; i <= n; i ++ )
    {
        int t = -1;
        for(int j = 1; j <= n; j ++ )
            if(!st[j] && (t == -1 || dist[t] < dist[j]))
                t = j;
        st[t] = true;

        for(int j = 1; j <= n; j ++ )
            dist[j] = max(dist[j], dist[t] * g[t][j]);
    }
}

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

    for(int i = 1; i <= m; i ++ )
    {
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        double z = (100.0 - c) / 100;
        g[a][b] = g[b][a] = max(g[a][b], z);
    }

    cin >> S >> T;
    Dijkstra();

    printf("%.8lf\n", 100 / dist[T]);
    return 0;
}


活动打卡代码 AcWing 1127. 香甜的黄油

小笨
13天前
#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

const int N = 810, M = 3000, INF = 0x3f3f3f3f;

int dist[N], q[N], id[N];
int h[N], e[M], ne[M], w[M], idx;
int n, p, m;
bool st[N];

int spfa(int s)
{
    memset(dist, 0x3f, sizeof dist);
    dist[s] = 0;

    int hh = 0, tt = 1;

    q[0] = s;
    st[s] = true;
    dist[s] = 0;

    while(hh != tt)
    {
        auto t = q[hh ++];
        if(hh == N) hh = 0;
        st[t] = false;

        for(int i = h[t]; ~i; i = ne[i] )
        {
            int j = e[i];
            if(dist[j] > dist[t] + w[i])
            {
                dist[j] = dist[t] + w[i];
                if(!st[j])
                {
                    q[tt ++] = j;
                    if(tt == N) tt = 0;
                    st[j] = true;
                }

            }
        }
    }
    int res = 0;
    for(int i = 0; i < n; i ++ )
    {
        int j = id[i];
        if(dist[j] == INF) return INF;
        res += dist[j];
    }
    return res;
}

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

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

     memset(h, -1, sizeof h);
     for(int i = 0; i < n; i ++) cin >> id[i]; 
     for(int i = 0; i < m; i ++)
     {
         int a, b, c;
         cin >> a >> b >> c;
         add(a, b, c), add(b, a, c);
     }

     int ans = INF;

     for(int i = 1; i <= p; i ++)  ans = min(ans, spfa(i));

     cout << ans << endl;

     return 0;
}


活动打卡代码 AcWing 1128. 信使

小笨
14天前
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 110, INF = 0x3f3f3f3f;

int dist[N][N];

int n, m;

int main()
{
    cin >> n >> m;
    memset(dist, 0x3f, sizeof dist);

    for(int i = 0; i < m; i ++)
    {
        int a, b, c;
        cin >> a >> b >> c;
        dist[a][b] = dist[b][a] = min(dist[a][b], c);
    }

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

    int ans = 0;

    for(int i = 2; i <= n; i ++)
        if(dist[1][i] == INF) 
        {
            ans = -1;
            break;
        }
        else ans = max(ans, dist[1][i]);

    cout << ans << endl;
    return 0;
}


活动打卡代码 AcWing 1129. 热浪

小笨
14天前
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 2510, M = 6200 * 2 + 10;
int n, m, S, E;
int h[N], e[M], ne[M], w[M], idx;
int dist[N], q[N];
bool st[N];

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

void spfa()
{
    memset(dist, 0x3f, sizeof dist);
    dist[S] = 0;
    int hh = 0, tt = 1; 
    q[0] = S;
    st[S] = true;

    while(hh != tt)
    {
        int t = q[hh ++];
        if(hh == N) hh = 0;
        st[t] = false;

        for(int i = h[t]; i != -1; i = ne[i] )
        {
            int j = e[i];
            if(dist[j] > dist[t] + w[i])
            {
                dist[j] = dist[t] + w[i];
                if(!st[j])
                {
                    q[tt ++] = j;
                    if(tt == N) tt = 0;
                    st[j] = true;
                }
            }
        }
    }
}

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

    memset(h, -1, sizeof h);
    for(int i = 0; i < m; i ++)
    {
        int a, b, c;
        cin >> a >> b >> c;
        add(a, b, c), add(b, a, c);
    }

    spfa();

    cout << dist[E] << endl;
    return 0;
}



小笨
20天前
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#include <iostream>
#include <algorithm>

using namespace std;

typedef long long LL;

const int N = 50;

int n, m, k;
int ans;
int cnt = 1;
int w[N];
int weights[1 << 25];

void dfs1(int u, int s)
{
    if(u == k)
    {
        weights[cnt ++] = s;
        return;
    }

    dfs1(u + 1, s);
    if((LL)s + w[u] <= m) dfs1(u + 1, w[u] + s);
} 

void dfs2(int u, int s)
{
    if(u == n)
    {
        int l = 0, r = cnt - 1;
        while(l < r)
        {
            int mid = l + r + 1 >> 1;
            if(weights[mid] + (LL)s <= m) l = mid;
            else r = mid - 1;
        }
        ans = max(ans, weights[l] + s);
        return;
    }
    dfs2(u + 1, s);
    if((LL)s + w[u] <= m) dfs2(u + 1, s + w[u]);
}

int main()
{
    cin >> m >> n;
    for(int i = 0; i < n; i ++) scanf("%d", &w[i]);

    sort(w, w + n);
    reverse(w, w + n);

    k = n / 2 + 2;
    dfs1(0, 0);

    sort(weights, weights + cnt);
    cnt = unique(weights, weights + cnt) - weights;

    dfs2(k, 0);

    cout << ans << endl;
    return 0;
}


活动打卡代码 AcWing 170. 加成序列

小笨
20天前
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 110;

int n;
int path[N];

bool dfs(int u, int depth)
{
    if(u > depth) return false;
    if(path[u - 1] == n) return true;

    bool st[N] = {0};

    for(int i = u - 1; i >= 0; i --)
        for(int j = i; j >= 0; j --)
        {
            int s = path[i] + path[j];
            if(s > n || s <= path[u - 1] || st[s]) continue;

            path[u] = s;
            st[s] = true;
            if(dfs(u + 1, depth)) return true;
        }
    return false;
}

int main()
{
    path[0] = 1;
    while(cin >> n, n)
    {
        int depth = 1;
        while(!dfs(1, depth)) depth ++;

        for(int i = 0; i < depth; i ++) cout << path[i] << ' ';
        cout << endl;
    }
    return 0;
}


活动打卡代码 AcWing 165. 小猫爬山

小笨
22天前
#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

const int N = 20;

int ans = N;
int n, m;
int w[N], sum[N];

void dfs(int u,int k)
{
    if(k >= ans) return;
    if(u == n)
    {
        ans = k;
        return;
    }

    for(int i = 0; i < k; i ++)
    {
        if(sum[i] + w[u] <= m)
        {
            sum[i] += w[u];
            dfs(u + 1, k);

            sum[i] -= w[u];
        }
    }

    sum[k] = w[u];
    dfs(u + 1, k + 1);
    sum[k] = 0;
}

int main()
{
    cin >> n >> m;
    for(int i = 0; i < n; i ++) cin >> w[i];
    sort(w, w + n);
    reverse(w, w + n);

    dfs(0, 0);

    cout << ans << endl;
    return 0;
}


活动打卡代码 AcWing 1116. 马走日

小笨
23天前
#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

const int N = 10;

int T;
int g[N][N];
bool st[N][N];
int n, m, x, y, ans;
int dx[] = {-2, -1, 1, 2, 2, 1, -1, -2}, dy[] = {1, 2, 2, 1, -1, -2, -2, -1};

void dfs(int x, int y, int cnt)
{
    if(cnt == n * m)
    {
        ans ++;
        return;
    }

    st[x][y] = true;

    for(int i = 0; i < 8; i ++)
    {
        int a = dx[i] + x, b = dy[i] + y;
        if(a >= 0 && a < n && b >= 0 && b < m && !st[a][b])
        {
            st[a][b] = true;
            dfs(a, b, cnt + 1);
            st[a][b] = false;
        }
    }
}

int main()
{
    cin >> T;
    while(T --)
    {
        ans = 0;
        memset(st, 0, sizeof st);
        cin >> n >> m >> x >> y;
        dfs(x, y, 1);
        cout << ans << endl;
    }

    return 0;
}


活动打卡代码 AcWing 3784. 交换相邻元素

小笨
23天前
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 2e5 + 10;

int a[N];
char s[N];
int n, maxx;

int main()
{
    scanf("%d", &n);
    for(int i = 1; i <= n; i ++) scanf("%d", &a[i]);

    scanf("%s", s + 1);

    bool flag = true;
    for(int i = 1; i < n; i ++)
    {
        maxx = max(maxx, a[i]);
        if(s[i] == '0' &&  maxx != i) flag = false;
    }
    if(flag) puts("YES");
    else puts("NO");

    return 0;
}