头像

帽子




在线 


最近来访(64)
用户头像
不止于此
用户头像
不吃菠菜
用户头像
东非不开森
用户头像
一切皆有解
用户头像
星光璀璨
用户头像
Fatin
用户头像
无人圣地
用户头像
垫底抽風
用户头像
执着_麕懬
用户头像
Fluent
用户头像
人生如戏ba
用户头像
Cold_heartless
用户头像
_LRJ_
用户头像
啥也不会的小白菜
用户头像
V1CI-_-
用户头像
Reducing_Sugar
用户头像
YSW_7
用户头像
努力学习的小白
用户头像
我呼吸了
用户头像
John_0

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

帽子
23小时前
#include <iostream>
#include <cstdio>
#include <string>
#include <cstring>
#include <cctype>
using namespace std;
const int N = 1e6 + 10;
string a, b;
bool check(int i, int j) {
    if(tolower(a[i]) == tolower(b[j])) return true;
    return false;
}
int main() {
    cin >> b;

    getline(cin, a);
    getline(cin, a);

    int len1 = b.size();
    int len2 = a.size();
    int st = len2;
    int cnt = 0;
    for(int i = 0, j = 0; i < len2; i++) {
        if(a[i] == ' ') continue;
        int t = i;
        //cout << i << ' ' << j << endl;
        while(j < len1 && i < len2 && check(i, j)) {
            i++, j++;
        }
        if(j == len1 && a[i] == ' ' && (a[t - 1] == ' ' || t == 0)) {
            cnt ++;
            st = min(st, t);
            i -= 1;
        }
        j = 0;
    }

    if(cnt)
        cout << cnt << " " << st << endl;
    else puts("-1");

    return 0;
}


活动打卡代码 AcWing 445. 数字反转

帽子
1天前
#include <iostream>
#include <cstdio>
#include <vector>
using namespace std;
vector<int> q;
int main() {
    string str;
    cin >> str;

    int len = str.size();
    int st = 0;

    if(len == 1 && str[0] == '0') {
        cout << 0 << endl;
        return 0;
    }

    if(str[0] == '-' || str[0] == '+') {
        cout << str[0];
        st = 1;
    }

    int j = len - 1;
    while(j >= st && str[j] == '0') j --;
    for(int i = j; i >= st; i--) 
        cout << str[i];

    return 0;
}



帽子
1天前

题目描述

题目链接:
https://www.acwing.com/problem/content/description/736/

算法1

(贪心 + 01背包) $O(n*m)$

这是一个贪心 + 01背包问题,
我们通过贪心来确定谁先选,再进行01背包问题,
本题难以理解的地方就是为什么要用贪心确定谁先选?
直接dp不行吗?答案是:不行
为什么呢? 因为我们本题有随时间流逝,能量值减少的限制,
所以,我们不能采用01背包直接算,因为01背包再考虑前i个
物品时是讲究顺序的.

也就是说,01背包问题只能直接用于和选择顺序无关的组合问题.

贪心证明

对于此题和耍杂技的牛,都有一个特点,就是要确定谁在谁前面,就是顺序最优贪心问题(我瞎起的),这一类的心问题,我们都可采用,假设法(也是我瞎起的).

我们先只对两个对象进行考虑:
对于本题,我们假设有能量石i和能量石j,
若先吃(先选)能力石i,再吃能力石j,那么获得的能量为
Ei + Ej - Lj * Si
若先吃(先选)能力石i,再吃能力石j,那么获得的能量为
Ei + Ej - Li * Sj
我们假设先选能力石i最优,那么我们需要满足的条件是,Lj * Si < Li * Sj

也就是对能力石按此条件排序即可

时间复杂度

O(n*m)
n表示能量石的个数,m表示吃所有能量石所消耗的总时间

C++ 代码

/*
    这是一个贪心 + 01背包问题,
    我们通过贪心来确定谁先选,再进行01背包问题,
    本题难以理解的地方就是为什么要用贪心确定谁先选?
    直接dp不行吗?答案是:不行
    为什么呢? 因为我们本题有随时间流逝,能量值减少的限制,
    所以,我们不能采用01背包直接算,因为01背包再考虑前i个
    物品时是讲究顺序的.

    也就是说,01背包问题只能直接用于和选择顺序无关的组合问题.
*/
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 110, M = 1e4 + 10;
struct Stone {
    int s;
    int e;
    int l;
}q[N];
int f[N][M];
bool mycmp(Stone a, Stone b)
{
    return a.s * b.l < b.s * a.l;
}
int main() {
    int T;
    scanf("%d", &T);

    for(int cases = 1; cases <= T; cases++) {
        int n;
        scanf("%d", &n);

        int m = 0;
        for(int i = 1; i <= n; i++) {
            int s, e, l;
            scanf("%d%d%d", &s, &e, &l);
            q[i].s = s, q[i].e = e, q[i].l = l;
            m += s;
        }

        sort(q + 1, q + n + 1, mycmp); 

        memset(f, -0x3f, sizeof f);

        f[0][0] = 0;
        for(int i = 1; i <= n; i++)
            for(int j = 0; j <= m; j++) {
                int s = q[i].s, e = q[i].e, l = q[i].l;

                f[i][j] = f[i - 1][j];
                if(j >= s) f[i][j] = max(f[i][j], f[i - 1][j - s] + max(0, e - l * (j - s)));
            }

        int res = 0;
        for(int j = 0; j <= m; j++)
                res = max(res, f[n][j]);

        printf("Case #%d: %d\n", cases, res);
    }   

    return 0;
}


活动打卡代码 AcWing 734. 能量石

帽子
1天前
/*
    这是一个贪心 + 01背包问题,
    我们通过贪心来确定谁先选,再进行01背包问题,
    本题难以理解的地方就是为什么要用贪心确定谁先选?
    直接dp不行吗?答案是:不行
    为什么呢? 因为我们本题有随时间流逝,能量值减少的限制,
    所以,我们不能采用01背包直接算,因为01背包再考虑前i个
    物品时是讲究顺序的.

    也就是说,01背包问题只能直接用于和选择顺序无关的组合问题.
*/
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 110, M = 1e4 + 10;
struct Stone {
    int s;
    int e;
    int l;
}q[N];
int f[N][M];
bool mycmp(Stone a, Stone b)
{
    return a.s * b.l < b.s * a.l;
}
int main() {
    int T;
    scanf("%d", &T);

    for(int cases = 1; cases <= T; cases++) {
        int n;
        scanf("%d", &n);

        int m = 0;
        for(int i = 1; i <= n; i++) {
            int s, e, l;
            scanf("%d%d%d", &s, &e, &l);
            q[i].s = s, q[i].e = e, q[i].l = l;
            m += s;
        }

        sort(q + 1, q + n + 1, mycmp); 

        memset(f, -0x3f, sizeof f);

        f[0][0] = 0;
        for(int i = 1; i <= n; i++)
            for(int j = 0; j <= m; j++) {
                int s = q[i].s, e = q[i].e, l = q[i].l;

                f[i][j] = f[i - 1][j];
                if(j >= s) f[i][j] = max(f[i][j], f[i - 1][j - s] + max(0, e - l * (j - s)));
            }

        int res = 0;
        for(int j = 0; j <= m; j++)
                res = max(res, f[n][j]);

        printf("Case #%d: %d\n", cases, res);
    }   

    return 0;
}


活动打卡代码 AcWing 443. 导弹拦截

帽子
1天前
/*
    思路:
        先把所有点按到第一枚导弹的距离按降序排序,
        也就是先让第一个导弹系统包含所有点,再依次退出,
        让第二个导弹系统包围这个导弹,对res依次取min.
*/
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
const int N = 1e5 + 10;
struct Node {
    int x;
    int y;
    int d;
    bool operator<(Node other) const {
        return d < other.d;
    }
}q[N];
int get_distance(int x1, int y1, int x2, int y2) {
    int a = x2 - x1;
    int b = y2 - y1;
    return a * a + b * b;
}
int main() {
    int a1, b1, a2, b2;
    cin >> a1 >> b1 >> a2 >> b2;

    int n;
    cin >> n;

    for(int i = 0; i < n; i++) {
        int x, y;
        cin >> x >> y;

        q[i].x = x;
        q[i].y = y;
        q[i].d = get_distance(x, y, a1, b1);
    }

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

    int res = q[0].d, r = 0;
    for(int i = 1; i <= n; i++) {
        r = max(r, get_distance(q[i - 1].x, q[i - 1].y, a2, b2));
        res = min(res, q[i].d + r);
    }

    cout << res << endl;

    return 0;
}


活动打卡代码 AcWing 442. 接水问题

帽子
1天前
// 贪心问题,每个同学都会先去最先接完的水龙头去接,最后求每个水龙头的最大值
#include <iostream>
#include <cstdio>
using namespace std;
const int N = 10010;
int w[N];
int q[N]; // 水龙头结束时间
int main() {
    int n, m;
    cin >> n >> m;

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

    for(int i = 0; i < n; i++) {
        int t = 0;
        for(int j = 0; j < m; j++)
            if(q[j] < q[t])
                t = j;

        q[t] += w[i];
    }

    int res = 0;
    for(int i = 0; i < n; i++) res = max(res, q[i]);

    cout << res << endl;

    return 0;
}


活动打卡代码 AcWing 441. 数字统计

帽子
1天前
#include <iostream>
#include <cstdio>
using namespace std;
int main() {
    int l, r;
    cin >> l >> r;

    int res = 0;
    for(int i = l; i <= r; i++) {
        int t = i;
        while(t) {
            int x = t % 10;
            if(x == 2) res ++;
            t /= 10;
        }
    }

    cout << res << endl;

    return 0;
}


活动打卡代码 AcWing 90. 64位整数乘法

帽子
2天前
// 注意long long已经不够用了
#include <iostream>
#include <cstdio>
using namespace std;
typedef unsigned long long ULL;
typedef long long LL;
ULL qmi(LL a, LL b, LL p) {
    LL res = 0;
    while(b) {
        if(b & 1) res = (ULL)(res + a) % p;
        b >>= 1;
        a = (ULL)a * 2 % p;
    }
    return res;
}
int main() {
    LL a, b, p;
    cin >> a >> b >> p;

    cout << qmi(a, b, p) << endl;

    return 0;
}


活动打卡代码 AcWing 4617. 解方程

帽子
2天前
// 这种题一定有公式,如果想不出来,就对着样例猜,我们可以借用
// 程序员计算器,来观察其二进制组成
// 发现本题的答案即二进制中有多少个1,则答案为2的多少次方
/*
    正解:
        二进制为1的位代表当前位独立,也就是说,
        做减法一定与做异或相等,无论x的二进制当前位
        是0还是1,一定满足,所以当前位有两种选择,
        而二进制为0的位代表只能填0,也就是只有一种可能.
*/
#include <iostream>
#include <cstdio>
using namespace std;
int count(int x) {
    int res = 0;
    for(int i = 0; i < 30; i++)
        if(x >> i & 1)
            res ++;
    return res;
}   
int qmi(int a, int k) {
    int res = 1;
    while(k) {
        if(k & 1) res = res * a;
        k >>= 1;
        a = a * a;
    }
    return res;
} 
int main() {
    int T;
    cin >> T;

    while(T--) {
        int a;
        cin >> a;

        int n = count(a);
        cout << qmi(2, n) << endl;
    }

    return 0;
}


活动打卡代码 AcWing 434. 排座椅

帽子
2天前
// 贪心 + 排序
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
const int N = 1010;
struct Node {
    int pos;
    int w;
}row[N], col[N];
bool mycmp1(Node x, Node y) {
    return x.w > y.w;
}
bool mycmp2(Node x, Node y) {
    return x.pos < y.pos;
}
int main() {
    int n, m, k, l, d;
    cin >> n >> m >> k >> l >> d;

    for(int i = 1; i <= d; i++) {
        int x1, y1, x2, y2;
        cin >> x1 >> y1 >> x2 >> y2;

        if(x1 == x2) {
            int y = min(y1, y2);
            col[y].pos = y;
            col[y].w ++;
        }
        else if(y1 == y2) {
            int x = min(x1, x2);
            row[x].pos = x;
            row[x].w ++;
        }
    }

    sort(row + 1, row + n, mycmp1);
    sort(col + 1, col + m, mycmp1);

    sort(row + 1, row + k + 1, mycmp2);
    sort(col + 1, col + l + 1, mycmp2);

    for(int i = 1; i <= k; i++) {
        cout << row[i].pos;
        if(i == k) puts("");
        else printf(" ");
    }

    for(int i = 1; i <= l; i++) {
        cout << col[i].pos;
        if(i == l) puts("");
        else printf(" ");
    }

    return 0;
}