头像

坚持就是胜利!




离线:20小时前


最近来访(152)
用户头像
DLRzzz
用户头像
PotremZ
用户头像
x.ac
用户头像
LcccY
用户头像
koyomi
用户头像
沄逸
用户头像
王文波08
用户头像
zzz2
用户头像
ChaseAug_0
用户头像
叮当叮当喵
用户头像
Meteor_Z
用户头像
矿工小队
用户头像
自由如风_1
用户头像
d_
用户头像
要挥剑了
用户头像
canyun
用户头像
zqiceberg
用户头像
浅墨央
用户头像
无心无情
用户头像
Zver

活动打卡代码 AcWing 1996. 打乱字母


3天前
#include <algorithm>
#include <iostream>
#include <vector>
#include <cstring>

using namespace std;

int n;
vector<string> r, u, d;//u(up)存储字典序排列的字符串,d(down)存储倒字典序排列的字符串

int main()
{
    cin >> n;
    for(int i = 0; i < n; i ++ )
    {
        string s;
        cin >> s;

        sort(s.begin(), s.end(), less()); //字符串正字典序排列
        u.push_back(s);
        r.push_back(s);//r数组存的是正字典序排列的字符串,方便之后处理(因为题目要求按照输入的顺序输出)

        //sort(s.begin(), s.end(), greater()); //字符串倒字典序排列
        reverse(s.begin(), s.end());
        d.push_back(s);

    }
    sort(u.begin(), u.end(), less());//u中都是字典序排列字符串(升序,每个都是最小情况)
    sort(d.begin(), d.end(), less());//d中都是倒字典序排列的字符串(升序,每个都是最大情况)

    for(auto &s : r)
    {
        //最小的情况在最大的数组里面找(左边界),最大的情况在最小的里面找(右边界)

        //此时s它是最小的(因为一开始r存的就是把他正字典序重排的结果),所以在倒字典序排列的字符串(字符串都是最大的情况)中找它的最小位置
        int a = lower_bound(d.begin(), d.end(), s) - d.begin() + 1;//因为从1开始标号,所以+1

        //sort(s.begin(), s.end(), greater());//将s倒字典序排列重组
        reverse(s.begin(), s.end());
        //此时s是最大的,在字典序排列的字符串(都是最小的情况)中找他的最大位置
        int b = upper_bound(u.begin(), u.end(), s) - u.begin();//因为找的是第一个大于s的位置,所以-1再+1

        cout << a << ' ' << b << endl;
    }
    return 0;
}



活动打卡代码 AcWing 2005. 马蹄铁


3天前
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 10;

int n;
char g[N][N];
bool st[N][N];
int ans;

int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};

void dfs(int x, int y, int l, int r)
{
    st[x][y] = true;

    if (l == r)
    {
        ans = max(ans, l + r);
        st[x][y] = false;
        return;
    }

    for (int i = 0; i < 4; i ++ )
    {
        int a = x + dx[i], b = y + dy[i];
        if (a >= 0 && a < n && b >= 0 && b < n && !st[a][b])
        {
            if (g[x][y] == ')' && g[a][b] == '(') continue;
            if (g[a][b] == '(') dfs(a, b, l + 1, r);
            else dfs(a, b, l, r + 1);
        }
    }

    st[x][y] = false;
}

int main()
{
    cin >> n;
    for (int i = 0; i < n; i ++ ) cin >> g[i];

    if (g[0][0] == '(')
        dfs(0, 0, 1, 0);

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




活动打卡代码 AcWing 2014. 岛


3天前
#include <iostream>
#include <cstring>
#include <algorithm>
#include <map>

typedef long long LL;

using namespace std;
const int N = 100005, M = 1e9+1;
int a[N];
map<int ,int >b;
int n;

int main()
{
    cin >> n;

    for (int i = 1; i <= n; i ++ )
    {
        cin >> a[i];
        if(a[i]>a[i-1])
        {
            //数的大小在[a[i-1],a[i]-1]之间的所有数大小都+1
            b[a[i-1]]++, b[a[i]]--;
        }
    }
    LL sum = 0, res = 0;
    for (auto i: b )
    {
        //求前缀和
        sum+=i.second;
        res = max(res,sum);
    }
    cout << res;
}



活动打卡代码 AcWing 2019. 拖拉机


3天前
#include <iostream>
#include <cstring>
#include <algorithm>
#include <deque>

#define x first
#define y second

using namespace std;

typedef pair<int, int> PII;
const int N = 1010;

bool g[N][N], st[N][N];
int dist[N][N];

int bfs(int sx, int sy)
{
    deque<PII> q;
    q.push_back({sx, sy});
    memset(dist, 0x3f, sizeof dist);
    dist[sx][sy] = 0;

    int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};

    while (q.size())
    {
        auto t = q.front();
        q.pop_front();

        if (st[t.x][t.y]) continue;
        st[t.x][t.y] = true;

        if (!t.x && !t.y) break;

        for (int i = 0; i < 4; i ++ )
        {
            int x = t.x + dx[i], y = t.y + dy[i];
            if (x >= 0 && x < N && y >= 0 && y < N)
            {
                int w = 0;
                if (g[x][y]) w = 1;
                if (dist[x][y] > dist[t.x][t.y] + w)
                {
                    dist[x][y] = dist[t.x][t.y] + w;
                    if (!w) q.push_front({x, y});
                    else q.push_back({x, y});
                }
            }
        }
    }

    return dist[0][0];
}

int main()
{
    int n, sx, sy;
    scanf("%d%d%d", &n, &sx, &sy);
    while (n -- )
    {
        int x, y;
        scanf("%d%d", &x, &y);
        g[x][y] = true;
    }

    printf("%d\n", bfs(sx, sy));

    return 0;
}






3天前




3天前

分析题意,我们要求的是将两个斑点连起来所需的最短距离,这就好比星星消消乐(不知道大家玩过没哈哈),现在左边有一疙瘩,右边有一疙瘩,且颜色和左边相同,如果要将两个疙瘩连成一个疙瘩再把它们一起消掉的话,就需要在它们中间建一条“路”,我们所要求的就是这条路的最短长度。

思路

1、搜出两个连通块 (flood fill算法)
2、枚举连接的两个端点,找到两个距离最近的点 (曼哈顿距离 $ \lvert x_1 - y_2 \rvert + | y_1 - y_2 | $)

// dfs暴搜

#include<iostream>
#include<algorithm>
#include<vector>

#define x first
#define y second

using namespace std;

typedef pair<int, int> PII;

const int N = 55;

int n, m;
char g[N][N];
vector<PII> points[2]; // 两个点集

int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};

void dfs(int x, int y, vector<PII>& ps)
{
    g[x][y] = '.'; // 将搜过的点由‘X’改为‘.’
    ps.push_back({x, y});

    // 沿着四个方向继续搜
    for (int i = 0; i < 4; i ++)
    {
        int a = x + dx[i], b = y + dy[i];
        if (a >= 0 && a < n && b >= 0 && b < m && g[a][b] == 'X')
            dfs(a, b, ps);
    }
}

int main()
{
    cin >> n >> m;
    for (int i = 0; i < n; i ++ ) cin >> g[i]; // 存储地图

    // 暴搜得到两个连通块
    for (int i = 0, k = 0; i < n; i ++)
        for (int j = 0; j < m; j ++)
            if (g[i][j] == 'X')
                dfs(i, j, points[k ++]); 

    int res = 1e8; 
    for (auto& a: points[0])
        for (auto& b: points[1])
            res = min(res, abs(a.x - b.x) + abs(a.y - b.y) - 1); // 求的是中间的数量,需要再减去1

    cout << res << endl;

    return 0;

}
// bfs

#include<iostream>
#include<algorithm>
#include<vector>
#include <queue>>

#define x first
#define y second

using namespace std;

typedef pair<int, int> PII;

const int N = 55;

int n, m;
char g[N][N];
bool st[N][N];
vector<PII> points[2];

int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};

void bfs(int x, int y, vector<PII>& ps)
{
    queue<PII> q;
    q.push({x, y});
    st[x][y] = true;

    while(q.size())
    {
        auto t = q.front();  q.pop();
        ps.push_back(t);

        for(int i = 0; i < 4; i++)
        {
            int a = t.x + dx[i], b = t.y + dy[i];

            if (a >= 0 && a < n && b >= 0 && b < m && g[a][b] == 'X' && !st[a][b])
            {
                q.push({a, b});
                st[a][b] = true;
            }

        }
    }
}

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

    for(int i = 0; i < n; i++) cin >> g[i];



    for(int i = 0, k = 0; i < n; i++)
        for(int j = 0; j < m; j++)
            if(g[i][j] == 'X' && !st[i][j])
                bfs(i, j, points[k++]);

    int res = 1e8;
    for(auto& a: points[0])
        for(auto& b: points[1])
            res = min(res, abs(a.x - b.x) + abs(a.y - b.y) - 1);

    cout << res << endl;

    return 0;
}



活动打卡代码 AcWing 2060. 奶牛选美


4天前
#include<iostream>
#include<algorithm>
#include<vector>

#define x first
#define y second

using namespace std;

typedef pair<int, int> PII;

const int N = 55;

int n, m;
char g[N][N];
vector<PII> points[2]; // 两个点集

int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};

void dfs(int x, int y, vector<PII>& ps)
{
    g[x][y] = '.'; // 将搜过的点由‘X’改为‘·’
    ps.push_back({x, y});

    // 沿着四个方向继续搜
    for (int i = 0; i < 4; i ++)
    {
        int a = x + dx[i], b = y + dy[i];
        if (a >= 0 && a < n && b >= 0 && b < m && g[a][b] == 'X')
            dfs(a, b, ps);
    }
}

int main()
{
    cin >> n >> m;
    for (int i = 0; i < n; i ++ ) cin >> g[i]; // 存储地图

    // 暴搜得到两个连通块
    for (int i = 0, k = 0; i < n; i ++)
        for (int j = 0; j < m; j ++)
            if (g[i][j] == 'X')
                dfs(i, j, points[k ++]);

    int res = 1e8; 
    for (auto& a: points[0])
        for (auto& b: points[1])
            res = min(res, abs(a.x - b.x) + abs(a.y - b.y) - 1); // 求的是中间的数量,需要再减去1

    cout << res << endl;

    return 0;

}



活动打卡代码 AcWing 125. 耍杂技的牛


5天前
#include<iostream>
#include<algorithm>

using namespace std;

typedef pair<int, int> PII;

const int N = 50010;

int n;
PII cow[N];

int main()
{
    scanf("%d", &n);
    for (int i = 0; i < n; i ++ )
    {
        int s, w;
        scanf("%d%d", &w, &s);
        cow[i] = {w + s, w}; // 这里存w+s是为了排序
    }

    sort(cow, cow + n);

    int res = -2e9, sum = 0;
    for (int i = 0; i < n; i ++ )
    {
        int s = cow[i].first - cow[i].second, w = cow[i].second;
        res = max(res, sum - s); // 求最大风险值
        sum += w;
    }

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

    return 0;
}


活动打卡代码 AcWing 104. 货仓选址


5天前
#include<iostream>
#include<algorithm>

using namespace std;

const int N = 100010;

int n;
int q[N];

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

    // 这里的i是从0开始的
    for (int i = 0; i < n; i ++ ) scanf("%d", &q[i]);

    sort(q, q + n);

    int res = 0;
    for (int i = 0; i < n; i ++ ) res += abs(q[i] - q[n/2]);

    printf("%d\n", res);
}


活动打卡代码 AcWing 913. 排队打水


5天前
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

typedef long long LL;

const int N = 100010;

int n;
int a[N];

int main()
{
    cin >> n;

    for (int i = 0; i < n; i ++ ) cin >> a[i];
    sort(a, a + n);

    // res是总时间,t表示每个人的等待时间
    LL res = 0, t = 0;
    for (int i = 0; i < n; i ++ )
    {
        res += t;
        t += a[i];
    }

    cout << res << endl;

    return 0;
}