头像

4_3




离线:2小时前


最近来访(10)
用户头像
結城友奈
用户头像
zzzgw
用户头像
tianming
用户头像
shy_
用户头像
狗头人挖土豆
用户头像
edgdcgxgbx
用户头像
HH123_
用户头像
pikachu_
用户头像
Promise_You

活动打卡代码 AcWing 1934. 贝茜放慢脚步

4_3
4小时前

模拟恶心心
复习归并

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


using namespace std;

const int N = 10010;

int n, tt, dd;
int t[N], d[N];

int main()
{
    cin >> n;

    for (int i = 0; i < n ; i ++)
    {
        char a;
        int b;
        cin >> a >> b;
        if (a == 'T') t[++ tt] = b;
        else d[++ dd] = b;
    }
    sort(t + 1, t + tt + 1);
    sort(d + 1, d + dd + 1);

    int x = 1, y = 1;
    double s = 0, v = 1, tim = 0;
    while (x <= tt && y <= dd)
    {
        double td = (d[y] - s) * v;
        double ts = t[x] - tim;
        if (td < ts)
        {
            s = d[y ++];
            tim += td;
            v ++;
        }
        else
        {
            tim = t[x ++];
            s += ts / v;
            v ++;
        }
    }
    while (x <= tt)
    {
        s += (t[x] - tim) / v;
        tim = t[x ++];
        v ++;
    }
    while (y <= dd)
    {
        tim += (d[y] - s) * v;
        s = d[y ++];
        v ++;
    }

    tim += (1000 - s) * v + 0.5;
    cout << int(tim) << endl;

    return 0;

}


活动打卡代码 AcWing 4. 多重背包问题

4_3
13小时前
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 110;

int n, m, s;
int f[N], v[N], w[N];

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

    for (int i = 0; i < n; i ++)
    {
        cin >> v[i] >> w[i] >> s;
        for (int j = m; j >= v[i]; j --)
            for (int k = 0; k <= s && k * v[i] <= j; k ++)
                f[j] = max(f[j], f[j - k * v[i]] + k * w[i]);
    }

    cout << f[m] << endl;

    return 0;
}


活动打卡代码 AcWing 3. 完全背包问题

4_3
13小时前
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 1010;

int n, m;
int v[N], w[N], f[N];

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

    for (int i = 1; i <= n; i ++)
        for (int j = v[i]; j <= m; j ++)
            f[j] = max(f[j], f[j - v[i]] + w[i]);

    cout << f[m] << endl;

    return 0;
}


活动打卡代码 AcWing 2. 01背包问题

4_3
1天前
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 1010;

int n, m;
int f[N], v[N], w[N];

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

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

    for (int i = 1; i <= n; i ++)
        for (int j = m; j >= v[i]; j --)
            f[j] = max(f[j], f[j - v[i]] + w[i]);   
            /* 保证更新等式左边第i轮f[j]时,等式右边f[j]和f[j-v[i]]是i-1轮算出的,所以j从大到小循环
                                    f[i][j] = max(f[i-1][j], f[i-1][j-v[i]]+w[i])

                j从小到大枚举,更新左边f[j]时,右边j-v[i]比j小,f[j-v[i]]先更新了
                                            f[i][j] = max(f[i-1][j], f[i][j-v[i]]+w[i])
                使k=j-v[i], k比j小,更新k时,f[k] = max(f[k], f[k-v[i]]+w[i]),v[i]可能用了两次或更多次
                如果i物品价值最大,体积最小,背包里全是它了

            */
    /*
            f[i][j] = f[i-1][j];        

            去掉i维度对赋值没影响,f[j] = f[j],更新时,右边的f[j]是i-1循环算出来的

            if(j>=v[i]) f[i][j] = max(f[i][j], f[i-1][j-v[i]]+w[i]);   
                                  max(f[i-1][j], f[i-1][j-v[i]]+w[i])
                                    上面这个f[i][j]其实也是f[i-1][j],上面那行赋值的

        去掉i维度后,保证更新第i轮循环的f[j]时f[j-v[i]]在i轮循环没更新就能保证,f[j-v[i]]就是i-1维度的算出的
        j从大到小枚举,更新第i轮的f[j]时,f[j - v[i]]是上一轮i-1循环求出的,也就是f[j-v[i]]==f[i-1][j-v[i]]
    */

    printf("%d", f[m]);

    return 0;
}




4_3
2天前
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>

using namespace std;

typedef long long LL;

const int N = 12, M = 1 << 12;

int n, m;       // n行m列   我们铺一个砖头,左边在哪列,哪列的相应行的状态记1
LL f[N][M];     // f[i][j] 表示前i列的所有铺法中,i列摆放j状态的合法铺法有多少种
bool st[M];     // st[j] 表示状态j是否合法,即是否有奇数个连续的0
vector<int> state[M];   // state[j]里存放能和j状态合法插入的所有状态(即互相交叉着插入且没空奇数个空)
                        // 用vector的妙处,用二维数组存的话state[i][j]还需要记每个i中用到的j有多少个

int main()
{
    while (cin >> n >> m, n || m)
    {
        if (n & m & 1)      // 特判 奇数个格子,蒙德里安的梦想幻灭,从头来过吧
        {
            puts("0");
            continue;
        }

        // 填充st数组,找出不合法的状态
        for (int i = 0; i < 1 << n; i ++)   
        {
            int cnt = 0;    // 表示连续的0的个数
            bool is_valid = true;   // 标记状态是否合法
            for (int j = 0; j < n; j ++)    // 循环每一行
                if (i >> j & 1)         // i >> j & 1,先执行>>再执行&,判断第j行是否是1(即是否有块儿)
                {
                    if (cnt & 1)        // 如果当前行有块儿,同时此行之前有奇数个块儿
                    {                   // 当前状态不合法,break,
                        is_valid = false;
                        break;
                    }
                    cnt = 0;            // 当前行有块且之前行有偶数个0,计数归0重新开始记
                }
                else cnt ++;            // 当前行没块,计数加一
            if (cnt & 1) is_valid = false;  // 所有行循环完,判断是否有奇数个尾0躲过判决(之前只是遇到块之后才判决他之前的零)
            st[i] = is_valid;           // 终审
        }

        // 优化的步骤,先计算了与状态i插入并且合法的状态j,放入state[i]中
        for (int i = 0; i < 1 << n; i ++)   // 枚举所有状态i
        {   
            state[i].clear();       // 多组数据,先清除state[i]
            for (int j = 0; j < 1 << n; j ++)   // 枚举所有状态j
                if ((i & j) == 0 && st[i | j])  // (i & j) == 0 如果i和j完美插入(即i的1和j的1分别对应对方的0)
                                                //  st[i | j] 并且插入后的状态合法
                    state[i].push_back(j);      // 放到state[i]中
        }

        memset(f, 0, sizeof f);         // 多组数据,初始化数组
        f[0][0] = 1;                    // 我们要填满第1列到第m列,第0列不铺
                                        // 第0列只有一种情况f[0][0],即第0列没有块为状态0

        for (int i = 1; i <= m; i ++)   // 循环1到m列
            for (int j = 0; j < 1 << n; j ++)   // 循环i列的所有状态
                for (auto k: state[j])          // 循环能和i列的状态j合法插入的所有状态k
                    f[i][j] += f[i - 1][k];     
                                    /*
                                        前i-1列合法铺完的所有铺法中,找到能和i列j铺法相适应的铺法(即f[i-1][k])
                                        加到f[i][j]中,表示前i列合法铺完,且第i列用j铺法的所有合法铺法总数          
                                    */
        cout << f[m][0] << endl;    // f[m][0] 表示前m列都铺完,且m列不铺的所有合法铺法,即我们要的结果
                                    // 我们铺一个砖头,左边在哪列,哪列的相应行的状态记1,如果m列铺了,砖头必然伸出到m+1列
    }

    return 0;
}


活动打卡代码 AcWing 1945. 奶牛棒球

4_3
2天前

手写二分和upper_bound, lower_bound
upper_bound: 返回第一个大于等于目标值的下标,不存在返回end
lower_bound: 犯规第一个大于目标值的下标, 不存在返回end

手写的二分没有不存在的判定,统一返回数组边界下标
需要先判定数组里有没有目标值,或者去优化自己写的二分(二分里去判断)

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

using namespace std;

const int N = 1010;

int q[N], n, cnt;

int b_search(int a, int b, int ll, int rr)
{
    int l = ll, r = rr;
    while (l < r)
    {
        int mid = l + r + 1 >> 1;
        if (b >= q[mid]) l = mid;
        else r = mid - 1;
    }
    b = l;

    l = ll, r = rr;
    while (l < r)
    {
        int mid = l + r >> 1;
        if (a <= q[mid]) r = mid;
        else l = mid + 1;
    }
    a = l;

    return b - a + 1;
}

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

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

    sort(q, q + n);

    for (int i = 1; i < n - 1; i ++)
    {
        for (int j = 0; j < i; j ++)
        {
            int c = q[i] - q[j];
            if (q[i + 1] - q[i] > c * 2) break;
            else if (q[n - 1] - q[i] < c) continue;
            else cnt += b_search(q[i] + c, q[i] + 2 * c, 0, n - 1);
         //   else cnt += upper_bound(q + i, q + n, q[i] + 2 * c) - lower_bound(q + i, q + n, q[i] + c);
        }
    }

    printf("%d", cnt);

    return 0;
}

暴力

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

using namespace std;

const int N = 1010;

int a[N], n, cnt;

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

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

    sort(a, a + n);

    for (int i = 1; i < n - 1; i ++)
    {
        for (int j = 0; j < i; j ++)
        {
            for (int k = i + 1; k < n; k ++)
            {
                if (a[k] - a[i] > 2 * (a[i] - a[j])) break;
                else if (a[k] - a[i] < a[i] - a[j]) continue;
                else cnt ++;
            }
        }
    }

    printf("%d", cnt);

    return 0;
}

真暴力,这么暴力都能过

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

using namespace std;

const int N = 1010;

int a[N], n, cnt;

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

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

    sort(a, a + n);

    for (int i = 1; i < n - 1; i ++)
    {
        for (int j = 0; j < i; j ++)
        {
            for (int k = i + 1; k < n; k ++)
            {
                if (a[k] - a[i] > 2 * (a[i] - a[j]) || a[k] - a[i] < a[i] - a[j]) continue;
                cnt ++;
            }
        }
    }

    printf("%d", cnt);

    return 0;
}



4_3
3天前
#include <iostream>
#include <cstring>
#include <algorithm>
#define x first
#define y second

using namespace std;

typedef pair<int, int> PII;

const int N = 40010;

PII ps[N];
int n, X, Y, Z, ans;

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

    for (int i = 1; i < n * 2; i += 2)
    {
        int a, b;
        scanf("%d%d", &a, &b);
        ps[i] = {a, Y - X};
        ps[i + 1] = {b + 1, Z - Y};
    }

    sort(ps + 1, ps + n * 2 + 1);

    int res = n * X;
    for (int i = 1; i <= n * 2; i ++)
    {
        res += ps[i].y;
        ans = max(ans, res);
    }

    printf("%d", ans);

    return 0;
}


活动打卡代码 AcWing 1960. 闪烁

4_3
4天前
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

typedef long long LL;

const int N = 70000;

int n, state, step;
int a[N], g[N];
LL b;

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

    for (int i = n - 1; ~i; i --)
    {
        int x;
        cin >> x;
        if (x) state += (1 << i);
    }

    for (int i = 0; i < N; i ++)
    {
        if (a[state])
        {
            step = a[state] - 1;
            b = (b - step) % (i - step);
            break;
        }

        a[state] = i + 1;
        g[i] = state;

        state ^= ((state >> 1) | (state & 1) << (n - 1));

    }

    state = g[step + b];

    for (int i = n - 1; ~i; i --)
        cout << ((state >> i ) & 1) << endl;

    return 0;
}


活动打卡代码 AcWing 1969. 品种邻近

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

using namespace std;

const int N = 5e4 + 10;
const int M = 1e6 + 10;

int n, k, pre[M];
int id = -1;

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

    for (int i = 1; i <= n; i ++)
    {
        int x;
        scanf("%d", &x);
        if (pre[x] && pre[x] + k >= i) 
            id = max(id, x);
        pre[x] = i;
    }

    printf("%d", id);

    return 0;
}   


活动打卡代码 AcWing 1978. 奶牛过马路

4_3
6天前
#include <iostream>
#include <cstring>
#include <algorithm>

#define x first
#define y second

using namespace std;

typedef pair<int, int> PII;

const int N = 1e5 + 10;

PII pa[N];
int pe[N], ps[N];
int n, ans;


int main()
{
    scanf("%d", &n);
    for (int i = 0; i < n; i ++)
    {
        int a, b;
        scanf("%d%d", &a, &b);
        pa[i] = {a, b};
    }
    sort(pa, pa + n);

    ps[0] = pa[0].y;
    for (int i = 1; i < n; i ++)
        ps[i] = max(ps[i - 1], pa[i].y);

    pe[n - 1] = pa[n - 1].y;
    for (int i = n - 2; i >= 0; i --)
        pe[i] = min(pe[i + 1], pa[i].y);

    for (int i = 0; i < n; i ++)
        if (ps[i] == pe[i])
            ans ++;

    printf("%d", ans);

    return 0;
}