暴力

hihocoder 1513 小Hi的烦恼

Posted on

别看了……bitset入门题……

bitset就是将32个01位操作整合成一个32位整数,一次位操作。
作为一个位运算的优化方法,可以省去 \( 2^5 \)的时间复杂度。
有些大佬 sb 就故意让你 \( O ( n^2 ) \)过不了,加个 bitset 优化就可以卡过去了。
不过也可以说是一个很巧妙的操作。

这题是今晚出去撸串的时候听其他三个沙雕吹的一道题,今晚补上。

题意:
给你一群学生每门功课的排名,总共 5 门学科,问你对于每个学生,所有成绩排名都比他高的学生数有多少。

不存在共列一个名次的数据。

思路:
很暴力……
直接\( n^2 \) + bitset 优化就可以卡过

但是不知道为什么,我的循环在 [ 1, n ] 就 T 了,[0, n ) 就 A 了……

#include <bits/stdc++.h>

#define each(i, n) for (int(i) = 0; (i) < (n); (i)++)
#define reach(i, n) for (int(i) = n - 1; (i) >= 0; (i)--)
#define range(i, st, en) for (int(i) = (st); (i) <= (en); (i)++)
#define rrange(i, st, en) for (int(i) = (en); (i) >= (st); (i)--)
#define fill(ary, num) memset((ary), (num), sizeof(ary))

using namespace std;
const int inf = 0x3f3f3f3f;
const int maxn = 3e4 + 5;

bitset<maxn> up[5][maxn], res;
int rnk[maxn], rrnk[5][maxn];

int main()
{
    int n;
    scanf("%d", &n);
    each(i, n) each(j, 5) scanf("%d", &rrnk[j][i]);
    each(c, 5)
    {
        each(i, n) rnk[rrnk[c][i]] = i + 1;
        range(i, 2, n)
        {
            up[c][rnk[i]] = up[c][rnk[i - 1]];
            up[c][rnk[i]][rnk[i - 1]] = 1;
        }
    }
    range(i, 1, n)
    {
        res = up[0][i] & up[1][i] & up[2][i] & up[3][i] & up[4][i];
        printf("%ld\n", res.count());
    }
    return 0;
}
暴力

CodeForces 398A Cards

Posted on

昨天搬了一下午的原博客……
晚上玩了一下就没写了

今天补上这道

题意:
xn个x卡片和on和o卡片,让你摆放。
每个x卡连续形成xlen 则减去 xlen×xlen
每个o卡连续形成olen 则减去 olen×olen

思路:
枚举分割的段数,直接暴力做……

但是我在一个地方思想出了偏差……一直得不到正解。
就是当我分割成split段时,长度为 cnum = xn / split ,这是偏小的,可以有 mod = xn % split 个 cnum + 1 个

AC Code

#include <algorithm>
#include <cctype>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <queue>
#include <stack>
#include <vector>

#define ll long long
#define each(i, n) for (int(i) = 0; (i) < (n); (i)++)
#define reach(i, n) for (int(i) = n - 1; (i) >= 0; (i)--)
#define range(i, st, en) for (int(i) = (st); (i) <= (en); (i)++)
#define rrange(i, st, en) for (int(i) = (en); (i) >= (st); (i)--)
#define fill(num, ary) memset((ary), (num), sizeof((ary)))

using namespace std;

const int maxn = 2e5 + 5;
const ll inf = 0x3f3f3f3f3f3f3f3f;

long long xn, on;

inline long long mul(const long long& x)
{
    return x * x;
}

inline void output(int len)
{
    ll cnum = xn / len, mod = xn % len;
    each(i, len-1)
    {
        if (i)
            putchar('o');
        each(j, cnum)
            putchar('x');
        if (i < mod)
            putchar('x');
    }
    each(i, on - len + 2)
        putchar('o');
    each(i, cnum)
        putchar('x');
}

int main()
{
    scanf("%lld %lld", &on, &xn);
    if (on == 0) {
        printf("%lld\n", -xn * xn);
        each(i, xn)
            putchar('x');
    } else if (xn == 0) {
        printf("%lld\n", on * on);
        each(i, on)
            putchar('o');
    } else {
        ll ans = -inf, cans, split = 1, len = 1;
        while (split <= on) {
            ll cnum = xn / (split + 1), mod = xn % (split + 1);
            cans = mul(on - split + 1) + split - 1 - mod * mul(cnum + 1) - (split + 1 - mod) * mul(cnum);
            if (cans > ans) {
                len = split;
                ans = cans;
            }
            split++;
        }
        printf("%lld\n", ans);
        output(len + 1);
    }
    return 0;
}