头像

迷人的杰凯瑞

徐州工程学院




离线:14小时前


最近来访(66)
用户头像
T-D-S
用户头像
宇宙_5
用户头像
挑战关注所有大佬
用户头像
季之秋
用户头像
RyanMoriarty
用户头像
LvTao
用户头像
SinceJuly
用户头像
yxc
用户头像
空银子
用户头像
逐风
用户头像
和彦在等空银子
用户头像
limie
用户头像
tgeuuy
用户头像
__Meilyゝ海绵宝宝亮亮鞋
用户头像
MZZDX
用户头像
我叫猫萌
用户头像
该用户被封禁
用户头像
封禁用户
用户头像
白墙
用户头像
karrrrri

活动打卡代码 AcWing 1473. A + B 格式

学会to_string()函数直接轻松解决!

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>

using namespace std;

int main()
{
    int a,b;
    cin >> a >> b;

    string c = to_string(a + b);

    reverse(c.begin(),c.end());

    string ans;
    for(int i = 0;i < c.size();i ++)
    {
        ans += c[i];

        if(i % 3 == 2 && isdigit(c[i + 1]))
            ans += ',';
    }

    reverse(ans.begin(),ans.end());

    cout << ans;

    return 0;
}


分享 PAT辅导课



新鲜事 原文

AcWing《PAT甲级辅导课》拼团优惠!https://www.acwing.com/activity/content/introduction/27/group_buy/42654/


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

暴力枚举两个连通块的每个点,选择最近的两个点即可!

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>

using namespace std;

const int N = 60;
const int M = 60;
const int INF = 0x3f3f3f3f;

int n,m;
char g[N][M];
int dx[4] = {0,0,-1,1},dy[4] = {-1,1,0,0};

struct node
{
    int x,y;
};

vector<node> s[2];

void dfs(int x,int y,vector<node>& s)
{
    s.push_back({x,y});
    g[x][y] = '.';
    for(int i = 0;i < 4;i ++)
    {
        int nx = x + dx[i],ny = y + dy[i];
        if(nx >= 1 && nx <= n && ny >= 1 && ny <= m && g[nx][ny] == 'X')
            dfs(nx,ny,s);
    }
}

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

    for(int i = 1;i <= n;i ++)
        scanf("%s",g[i] + 1);

    for(int i = 1,k = 0;i <= n;i ++)
        for(int j = 1;j <= m;j ++)
            if(g[i][j] == 'X')
                dfs(i,j,s[k ++]);

    int ans = INF;
    for(auto a : s[0])
        for(auto b : s[1])
            ans = min(ans,abs(a.x - b.x) + abs(a.y - b.y));

    cout << ans - 1;

    return 0;
}


活动打卡代码 AcWing 2041. 干草堆

裸的差分,没有任何技术含量!

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>

using namespace std;

const int N = 1e6 + 10;

int a[N];

void add(int l,int r)
{
    a[l] ++;
    a[r + 1] --;
}

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

    while(k --)
    {
        int l,r;
        cin >> l >> r;

        add(l,r);
    }

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

    sort(a + 1,a + n + 1);

    cout << a[n + 1 >> 1];

    return 0;
}


活动打卡代码 AcWing 2058. 笨拙的手指

等价于暴力枚举!

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <set>

using namespace std;

int getnum(string s,int k)
{
    int res = 0;
    for(auto c : s)
        res = res * k + c - '0';

    return res;
}

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

    set<int> s;
    for(auto& c : a)
    {
        c = (c == '0' ? '1' : '0');
        s.insert(getnum(a,2));
        c = (c == '0' ? '1' : '0');
    }

    for(auto& c : b)
    {
        char t = c;
        for(int i = 0;i < 3;i ++)
            if(i + '0' != t)
            {
                c = i + '0';
                int x = getnum(b,3);
                if(s.count(x))
                {
                    cout << x;
                    return 0;
                }
            }

        c = t;
    }

    return 0;
}


活动打卡代码 AcWing 3417. 砝码称重

动态规划
对于每个物品:可以不放可以放到天平的左边也可以放到天平的右边
用f[i][j]来表示在前i个物品中选,是否可以凑出重量恰好为j的方案,那么每种状态可以由三种转移转移而来
f[i][j] = f[i - 1][j] | f[i - 1][j - w[i]] | f[i - 1][j + w[i]]

Δ:这个题中,假设我们所有的砝码总质量为m,那么实际上可以凑出的重量范围应该是[-m,m]
但是数组的下标不可以为负数,这时可以给数组的下标加上一个偏移量dm = 1e5

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>

using namespace std;

const int N = 110;
const int M = 2e5 + 10;
const int dm = 1e5;

int w[N];
bool f[N][M];

int main()
{
    int n,m = 0;
    cin >> n;

    for(int i = 1;i <= n;i ++)
        cin >> w[i],m += w[i];

    f[0][dm] = true;    
    for(int i = 1;i <= n;i ++)
        for(int j = -m;j <= m;j ++)
        {
            f[i][j + dm] = f[i - 1][j + dm];

            if(j - w[i] >= -m)
                f[i][j + dm] |= f[i - 1][j - w[i] + dm];
            if(j + w[i] <= m)
                f[i][j + dm] |= f[i - 1][j + w[i] + dm];
        }

    int ans = 0;
    for(int j = 1;j <= m;j ++)
        if(f[n][j + dm])
            ans ++;

    cout << ans;

    return 0;
}


活动打卡代码 AcWing 3416. 时间显示

小学生都能写的题!

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>

using namespace std;

typedef long long ll;

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

    printf("%02lld:%02lld:%02lld",n / 1000 / 60 / 60 % 24,n / 1000 / 60 % 60,n / 1000 % 60);

    return 0;
}



1.png

首先,这是经典的01背包问题
按照正常思路来写的话
两重循环,并且空间优化成一维,没有问题

但问题是,这题的M = 365 * 24 * 60,会超时
所以不能按照正常的写法来写

那么怎么优化呢?
01背包没有其它写法,最终还是只能这样写,只能选择更换体积和价值的位置
让体积去充当价值,价值反过来充当体积

  • 原f[i][j]表示:从前i件物品里选,总体积不超过j时所能获得的最大价值
  • 现f[i][j]表示:从前i件物品里选,总价值不超过j时所需要的最小背包体积

那么要想求n件物品的价值最大,就求最大价值时体积最小就行了

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>

using namespace std;

const int N = 1e3 + 10;
const int M = 3e4 + 10;

int v[N],w[N],f[M];

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

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

    int sum = 0;
    for(int i = 1;i <= n;i ++)
    {
        cin >> w[i];

        sum += w[i];
    }

    memset(f,0x3f,sizeof(f));
    f[0] = 0;

    for(int i = 1;i <= n;i ++)
        for(int j = sum;j >= w[i];j --)
            f[j] = min(f[j],f[j - w[i]] + v[i]);

    for(int i = sum;i >= 0;i --)
        if(f[i] <= m)
        {
            cout << i;
            return 0;
        }
}



1.png
首先题目很长,归纳题意就是一个无向图
其中每条边都有两个权值
距离和价值

题目也问了两个问题:
(1)找一个起点,从这个点出发,到离它最远的点的距离最小:
(2)有多次询问,每次询问一个点,要求输出从起点到这个点距离最小且价值最大的路径。

(1)先用Floyd计算多源最短路,再枚举起点,暴力算出每种情况下的最远距离,取最小值;
(2)Dijkstra算法,按照距离优先,价值其次的原则进行更新。

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <stack>

using namespace std;

const int N = 1010;
const int INF = 0x3f3f3f3f;

struct node
{
    int a,b;
}dis[N],g[N][N];

int n,m;
int path[N];
bool vis[N];

void dijkstra(int s)
{
    for(int i = 1;i <= n;i ++)
        dis[i].a = INF;
    dis[s].a = 0;

    for(int i = 1;i <= n;i ++)
    {
        int k,mind = INF;
        for(int j = 1;j <= n;j ++)
            if(!vis[j] && dis[j].a < mind)
                k = j,mind = dis[j].a;

        vis[k] = true;

        for(int j = 1;j <= n;j ++)
            if(dis[k].a + g[k][j].a < dis[j].a || dis[k].a + g[k][j].a == dis[j].a && dis[k].b + g[k][j].b > dis[j].b)
                dis[j] = {dis[k].a + g[k][j].a,dis[k].b + g[k][j].b},path[j] = k;
    }
}

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

    for(int i = 1;i <= n;i ++)
        for(int j = 1;j <= n;j ++)
            if(i != j)
                g[i][j].a = INF;

    while(m --)
    {
        int x,y,a,b;
        scanf("%d %d %d %d",&x,&y,&a,&b);

        g[x][y] = g[y][x] = {a,b};
    }

    for(int k = 1;k <= n;k ++)
        for(int i = 1;i <= n;i ++)
            for(int j = 1;j <= n;j ++)
                if(g[i][k].a + g[k][j].a < g[i][j].a)
                    g[i][j] = {g[i][k].a + g[k][j].a,0};

    int s,mind = INF;
    for(int i = 1;i <= n;i ++)
    {
        int maxd = 0;
        for(int j = 1;j <= n;j ++)
            maxd = max(maxd,g[i][j].a);

        if(maxd < mind)
            s = i,mind = maxd;
    }

    dijkstra(s);

    cout << s << endl;

    int k;
    cin >> k;

    while(k --)
    {
        int e;
        cin >> e;

        int end = e;
        stack<int> ans;
        while(end != s)
        {
            ans.push(end);
            end = path[end];
        }

        cout << s;
        while(ans.size())
        {
            printf("->%d",ans.top());
            ans.pop();
        }
        cout << endl << dis[e].a << ' ' << dis[e].b << endl;
    }

    return 0;
}