头像

1234abcd




离线:9分钟前


最近来访(228)
用户头像
lin0406
用户头像
acwing_92248
用户头像
yxᴄ
用户头像
x1uc
用户头像
ck1000
用户头像
yxc的小迷妹
用户头像
C.m
用户头像
玛卡巴卡要AC
用户头像
tyjz_yyds
用户头像
我是菜狗啊啊啊啊啊
用户头像
tfqyc
用户头像
Running_a_way
用户头像
牧雷
用户头像
种花家的虎式坦克
用户头像
akak
用户头像
ac0111
用户头像
TT_22
用户头像
ffffffffffffffffffffffffffffff
用户头像
天元之弈
用户头像
zeng9999jian

活动打卡代码 AcWing 1250. 格子游戏

1234abcd
2小时前

2022.11.26 第一次

映射原理:两位进制数。这个二维转一维真的是太妙辣!

#include <iostream>

using namespace std;

const int N = 210;
int n, m;
int f[(N * N + 1) + N];

int fun(int x, int y)
{
    return x * (n + 1) + y;
}

int root(int x)
{
    if (x != f[x]) f[x] = root(f[x]);
    return f[x];
}

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

    // 1 * (n + 1) + 1 —— n * (n + 1) + n;

    for (int i = n + 2; i <= n * (n + 1) + n; i ++ ) f[i] = i;

    for (int i = 1; i <= m; i ++ )
    {
        int x, y;
        char c;

        cin >> x >> y >> c;

        int a = fun(x, y), b;

        if (c == 'D') b = fun(x + 1, y);
        else b = fun(x, y + 1);

        if (root(a) == root(b))
        {
            cout << i;
            return 0;
        }else f[root(a)] = root(b);
    }

    cout << "draw";

    return 0;
}



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

1234abcd
6小时前

2022.11.26 第一次

背模板咋了?

#include <iostream>

using namespace std;

const int INF = 1e9, N = 210;

int d[N][N];
int n, m, k;

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

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

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

    while (m -- )
    {
        int a, b, c;
        cin >> a >> b >> c;

        d[a][b] = min(d[a][b], c);
    }

    floyd();

    while (k -- )
    {
        int a, b;
        cin >> a >> b;

        if (d[a][b] > INF / 2) cout << "impossible\n";
        else cout << d[a][b] << '\n';
    }

    return 0;
}




1. 有些题是构造题,发现规律后可以特殊且很简单地构造出一个符合题意的答案, 如1583B。构造一个"太阳图"


活动打卡代码 AcWing 904. 虫洞

2022.11.24 第一次

咱家也过了,嘿嘿

// 开始没想到:存在一个负环就行,且不管负的多小。反正一旦有负环,就可以在这个负环走上无数遍,回到很久很久以前
// 真是妙啊!雀氏妙!
#include <iostream>
#include <queue>
#include <cstring>

using namespace std;

const int N = 5e2 + 10, M = 3e3;
int e[M *2], w[M * 2], ne[M * 2], h[N], idx;
int dist[N], st[N], cnt[N];
int n, m1, m2;

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

int spfa()
{
    memset(cnt, 0, sizeof cnt); // 开始忘记对这个初始化
    memset(st, 0, sizeof st);  // 开始忘记对这个初始化

    queue<int>q;
    for (int i = 1; i <= n; i ++ ) q.push(i);

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

        st[t] = 0;

        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];
                cnt[j] = cnt[t] + 1;

                if (cnt[j] >= n) return 1;
                if (st[j] == 0) // 开始写的 st[t]
                {
                    st[j] = 1; // 开始写的 st[t]
                    q.push(j);
                }
            }
        }
    }
    return 0;
}

int main()
{
    int T;
    cin >> T;

    while (T -- )
    {
        idx = 0;
        cin >> n >> m1 >> m2;

        memset(h, -1, sizeof h);
        while (m1 -- )
        {
            int a, b, c;
            cin >> a >> b >> c;

            add(a, b, c), add(b, a, c);
        }

        while (m2 -- )
        {
            int a, b, c;
            cin >> a >> b >> c;

            add(a, b, -c);
        }

        int t = spfa();

        if (t == 1) cout << "YES\n";
        else cout << "NO\n";
    }

    return 0;
}


活动打卡代码 AcWing 3971. 最小的商

2022.11.24 第一次

嘎嘎水

#include <iostream>

using namespace std;

int main()
{
    int t;
    cin >> t;

    while (t -- )
    {
        int n, k;
        int ans = 1e9;

        cin >> n >> k;
        for (int i = 1; i <= n; i ++ )
        {
            int num;
            cin >> num;

            if (k % num == 0) ans = min(ans, k / num);
        }

        cout << ans << '\n';
    }

    return 0;
}


活动打卡代码 AcWing 4334. 农场网络

2022.11.23 第一次

大水题

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 5e2 + 10;
int p[N], f[N];

struct node
{
    int x, y, w;
}a[500010];

int root(int x)
{
    if (x != f[x]) f[x] = root(f[x]);
    return f[x];
}

int cmp(node a, node b)
{
    return a.w < b.w;
}

int main()
{
    int n;
    while (cin >> n)
    {
        for (int i = 1; i <= n; i ++ ) f[i] = i;

        int index = 0;
        for (int i = 1; i <= n; i ++ )
        {
            for (int j = 1; j <= n; j ++ )
            {
                cin >> a[ ++ index].w;
                a[index].x = i, a[index].y = j;
            }
        }

        sort(a + 1, a + index + 1, cmp);

        int ans = 0;

        for (int i = 1; i <= index; i ++ )
        {
            if (root(a[i].x) != root(a[i].y))
            {
                f[root(a[i].x)] = root(a[i].y);
                ans += a[i].w;
            }
        }

        cout << ans << '\n';
    }

    return 0;
}



活动打卡代码 AcWing 4295. QS网络

2022.11.23 第一次

又是奇怪易错的地方。别人是预处理,把两个路由器价格加在边权上,我;我是在连边的时候加边权和两个路由器价格,应该是等价的啊。为什么我的答案总是大于等于实际答案呢?!!!

// 将路由器价格加在边权上,就可以用 prim 算法了
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 5e2 + 10;
int p[N], f[N];

struct node
{
    int x, y, w;
}a[N * N];

int root(int x)
{
    if (x != f[x]) f[x] = root(f[x]);
    return f[x];
}

int cmp(node a, node b)
{
    return a.w < b.w;
}

int main()
{
    int t;
    cin >> t;

    while (t -- )
    {
        int n;
        cin >> n;

        for (int i = 1; i <= n; i ++ ) cin >> p[i];

        int index = 0;
        for (int i = 1; i <= n; i ++ )
        {
            for (int j = 1; j <= n; j ++ )
            {
                cin >> a[ ++ index].w;
                a[index].x = i, a[index].y = j;
            }
        }

        sort(a + 1, a + index +1, cmp);

        for (int i = 1; i <= n; i ++ ) f[i] = i;

        int ans = 0;
        for (int i = 1; i <= index; i ++ )
        {
            if (root(a[i].x) != root(a[i].y))
            {
                f[root(a[i].x)] = root(a[i].y);
                ans = ans + a[i].w + p[a[i].x] + p[a[i].y]; // 这样写为什么不可以呢?
            }
        }

        cout << ans << '\n';
    }


    return 0;
}

我悟了

需要关闭同步流,不然超时

// 将路由器价格加在边权上,就可以用 prim 算法了
// 也只有这样才能用 kruskal 算法
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 5e2 + 10;
int p[N], f[N];

struct node
{
    int x, y, w;
}a[N * N];

int root(int x)
{
    if (x != f[x]) f[x] = root(f[x]);
    return f[x];
}

int cmp(node a, node b)
{
    return a.w < b.w;
}

int main()
{
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);

    int t;
    cin >> t;

    while (t -- )
    {
        int n;
        cin >> n;

        for (int i = 1; i <= n; i ++ ) cin >> p[i];

        int index = 0;
        for (int i = 1; i <= n; i ++ )
        {
            for (int j = 1; j <= n; j ++ )
            {
                cin >> a[ ++ index].w;
                a[index].x = i, a[index].y = j;

                a[index].w += p[i] + p[j];
            }
        }

        sort(a + 1, a + index +1, cmp);

        for (int i = 1; i <= n; i ++ ) f[i] = i;

        int ans = 0;
        for (int i = 1; i <= index; i ++ )
        {
            if (root(a[i].x) != root(a[i].y))
            {
                f[root(a[i].x)] = root(a[i].y);
                ans += a[i].w;
            }
        }

        cout << ans << '\n';
    }


    return 0;
}


活动打卡代码 AcWing 4333. 高速公路

2022.11.23 第一次

f[i] 数组初始化要细心

#include <iostream>
#include <algorithm>
#include <cmath>

using namespace std;

const int N = 2e3 + 10;
int p[N], f[N];

struct node
{
    double x, y, w;
} a[N * N], b[N];

int root(int x)
{
    if (x != f[x]) f[x] = root(f[x]);
    return f[x];
}

int cmp(node a, node b)
{
    return a.w < b.w;
}

char s[N][N];

double get_dist(int i, int j)
{
    return sqrt((b[i].x - b[j].x) * (b[i].x - b[j].x) + (b[i].y - b[j].y) * (b[i].y - b[j].y));
}

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

    for (int i = 1; i <= n; i ++ ) cin >> b[i].x >> b[i].y;

    int index = 0;
    for (int i = 1; i <= n; i ++ )
    {
        for (int j = 1; j <= n; j ++ )
        {
            a[ ++ index] = {i, j, get_dist(i, j)};
        }
    }

    int m;
    cin >> m;

    for (int i = 1; i <= n; i ++ ) f[i] = i;

    while (m -- )
    {
        int x, y;
        cin >> x >> y;

        f[root(x)] = root(y);
    }

    sort(a + 1, a + index + 1, cmp);

    for (int i = 1; i <= index; i ++ )
    {
        if (root(a[i].x) != root(a[i].y))
        {
            f[root(a[i].x)] = root(a[i].y);

            cout << a[i].x << ' ' << a[i].y << '\n';
        }
    }

    return 0;
}



活动打卡代码 AcWing 4332. 卡车历史

2022.11.23 第一次

j 从 1 开始就 TLE 了,从 i + 1 开始就 AC 了。

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 2e3 + 10;
int p[N], f[N];

struct node
{
    int x, y, w;
} a[N * N];

int root(int x)
{
    if (x != f[x]) f[x] = root(f[x]);
    return f[x];
}

int cmp(node a, node b)
{
    return a.w < b.w;
}

char s[N][N];

int get_dist(int i, int j)
{
    int sum = 0;
    for (unsigned int k = 0; k < 7; k ++ )
    {
        if (s[i][k] != s[j][k]) sum ++ ;
    }

    return sum;
}

int main()
{
   // ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);

    int n;
    while (scanf("%d", &n))
    {
        if (n == 0) break;

        for (int i = 1; i <= n; i ++ )
        {
            //cin >> s[i];
            scanf("%s", s[i]);
        }

        for (int i = 1; i <= n; i ++ ) f[i] = i;

        int index = 0;
        for (int i = 1; i <= n; i ++ )
        {
            for (int j = i + 1; j <= n; j ++ ) // j 从 1 开始就 TLE 了
            {
                a[ ++ index] = {i, j, get_dist(i, j)};
            }
        }

        sort(a + 1, a + index + 1, cmp);

      /*  for (int i = 1; i <= n; i ++ )
        {
            for (int j = 1; j <= n; j ++ )
            {
                cout << "i=" << i << ' ' << "j=" << j << ' ' << "dist=" << get_dist << '\n';
                cout << "s[i]=" << s[i] << ' ' << "s[j]=" << s[j] << '\n';
            }
            cout << '\n';
        }*/

        int ans = 0;
        for (int i = 1; i <= index; i ++ )
        {
             if (root(a[i].x) != root(a[i].y))
             {
                 f[root(a[i].x)] = root(a[i].y);
                 ans += a[i].w;
             }
        }

       // cout << "The highest possible quality is 1/" << ans << '.' << '\n';
       printf("The highest possible quality is 1/%d.\n", ans);
    }


    return 0;
}



活动打卡代码 AcWing 3955. 统一大小写

2022.11.22 第一次

水题

#include <iostream>
#include <cstring>
#include <string>
#include <cstdlib>
#define int long long
using namespace std;

signed main()
{
    int t;
    cin >> t;

    while (t -- )
    {
        string s;
        cin >> s;

        int nx = 0, nd = 0;

        for (unsigned int i = 0; i < s.size(); i ++ )
        {
            if (s[i] >= 'a' && s[i] <= 'z') nx ++ ;
            else nd ++ ;
        }

        if (nd > nx)
        {
            for (unsigned int i = 0; i < s.size(); i ++ )
            {
                if (s[i] >= 'a' && s[i] <= 'z') cout << char(s[i] - 32);
                else cout << s[i];
            }

            cout << '\n';
        }else
        {
            for (unsigned int i = 0; i < s.size(); i ++ )
            {
                if (s[i] >= 'A' && s[i] <= 'Z') cout << char(s[i] + 32);
                else cout << s[i];
            }

            cout << '\n';
        }
    }

    return 0;
}