向 更好 出发！

• 放假尽量每天更。开学了应该是每周更。

• 如果没有更的话，强烈建议大家催更（雾）

• 如果沉思咕咕咕了的话可以私信骚扰她。
  P.S.不要太过头哦以免被JC时被发现

• 沉思希望大佬在沉思遇到问题时帮帮忙qwq如果完全没必要可以直接D吖qwq

2022

2 - 8

• P1426 （红）

基本是爆切。但是有了一个很坑的坑：要先判断，再运算。

结果还是调了 $10$ 分钟。

• P7303 （橙）

也是爆切。好久没有切橙题这么爽过，还是我太弱了嘤嘤嘤

白痴构造题。直接从 $1$ 枚举到 $n - 1$ 按照 $1$ 至 $n - 1$ 的递加数列输出，最后一个输出 $k$ 减掉已经输出的数的总和。

2 - 9

• P8115 （红）

模拟题。虽然是很简单，但是很难。打月赛那天是写出了 $80$ 分，最后一个点 TLE 。

那时候主程序是这样写的（后来发现这样写是错的）：

while (1) {
    cin >> c, cout << c;
    if (c == '}') return 0;

然后我就很疑惑，看了一位大佬的代码，然后算了算我的时间复杂度，感觉我的不会超时啊。。。

加了快读快输，全 WA 。

去问了另一位大佬，发现不能用快读，因为是 ull 类型的，就改了一下，变成最后一个点是 3ms ，但是答案错误。我发现了一个问题，就是如果输入是 {} ，会输出 {0} （感谢 @Liu_Kevin 指出问题 sto LK orz）

这里还是要放一下最终代码。

#include <bits/stdc++.h>
using namespace std;

#define ull unsigned long long
ull x, l, lx;
char ans[200010], c;
int cnt;
const char ta[] = {'0', '1', '2', '3', '4', '5', '6', '7', '8', '9', 'A', 'B', 'C', 'D', 'E', 'F'};

inline void write(int x) {
    char F[200];
    int tmp = x > 0 ? x : -x;
    if (x < 0) putchar('-') ;
    int cnt = 0 ;
    while (tmp > 0) {
        F[cnt++] = tmp % 10 + '0';
        tmp /= 10;
    }
    while (cnt > 0) putchar(F[--cnt]) ;
} 

char* _16(ull a) {
    int num[210], i = 0;
    cnt = 0;
    memset(ans, 0, sizeof(ans));

    while (a > 0)
        num[++i] = a % 16, a /= 16;
    for (; i > 0; --i) ans[cnt++] += ta[num[i]];
    return ans;
} 

ull _l(ull a) {
    ull i = 0;
    while (a) a /= 10, ++i;
    return i;
}

int main() {
    while (1) {
        cin >> c, cout << c;
        if (c == '}') return 0;
        if (scanf("%llu", &x) == 0) continue;


        _16(x);
        l = _l(x), lx = cnt + 2;

        //cout << _16(x).length() << "&" << _l(x) << "&" << _16(x) << "=" << x << " ";

        if (l < lx) printf("%llu", x);
        else {
            printf("0x");
            for (int i = 0; i < cnt; ++i)
                putchar(ans[i]);
        }
    }
}

• P1104 （橙）

傻逼题我都能 WA 我真牛逼啊。。。

一开始打算手写冒泡排序，然后想想就算了，写了个 cmp ，然后就运行时错误。。。

狂改了一阵，感觉没问题了，搞死我了，还是 RE ，我就一边改成冒泡一边想，还没写完就突然发现我 string 用 scanf 了。。。改成了 cin ，果然没问题了。。。

提交上去。。。最后两个点 WA 。

我再看代码，发现我最后一个判断错了，总是想着年龄大的排前面，结果输入的顺序就也是 < 了。。。然后才AC。。。

真的是太菜了 /kk

贴一下代码吧。。。

#include <bits/stdc++.h>
using namespace std;
int n;
struct xxs{
    int y, m, d, t;
    string s;
} a[105];

bool cmp(xxs a, xxs b) {
    if      (a.y != b.y) return a.y < b.y;
    else if (a.m != b.m) return a.m < b.m;
    else if (a.d != b.d) return a.d < b.d;
    else return a.t > b.t;
}

void inp(void) {
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i)
        cin >> a[i].s, scanf("%d%d%d", &a[i].y, &a[i].m, &a[i].d), a[i].t = i;
}

int main() {
    inp();
    stable_sort(a + 1, a + n + 1, cmp);
    for (int i = 1; i <= n; ++i) cout << a[i].s << endl;
}

• P1271 （橙）

傻逼桶排。数据太大。直接上代码。

#include <bits/stdc++.h>
using namespace std;

int t[1010], x, maxn, n, m;

void inp(void) {
    cin >> n >> m;
    for (int i = 1; i <= m; ++i)
        cin >> x, ++t[x];
}

int main() {
    inp();
    for (int i = 1; i <= n; ++i) 
        if (t[i]) 
            for (int j = 1; j <= t[i]; ++j) cout << i << " ";
}

2 - 10 ~ 2 - 11

• P8116 （黄）

月赛第二题。数论。

是听了一个大佬讲的才懂的 /kk

我太弱了 /kk

就是说，很显然，就是那个很明显的，就可以看出来的东西，例如说题面举的那个 $1 ÷ (1 ÷ 3)$ 就可以看出来，必须是因子。

然后我们就知道必须是因子了对吧，那我们就得整除对吧？

我们先设想要判断是否合法的数为 $x$ 。

我们怎么做除法呢？很显然除不尽， 例如说 $10$ 进制的，在有小数的情况下，我们是不是把它 $*10$ 然后继续除？但是，这是有限的，因为显示屏只有 $k$ 位， $0$ 占了一位。所以，我们就可以得到：想要判断 $x$ 是否合法，就判断 $b^{k - 1}$是否能整除 $x$ 。

所以，只要求出 $b^{k - 1}$ 能整除的所有数的数量就好了对吧？

然后，你转念一想，这不就是在求 $b^{k - 1}$ 的因子个数吗？！？！

而且通过亿点数学技巧，这里其实就是求 $b$ 的因子分别 $* (k - 1) $ 。

然后，就可以啦~

整理亿下思路：

求 $b$ 的质因数 -> 求因子个数

思路就出来啦~

对了对了，别忘了开 long long 哦~

放代码：

#include <bits/stdc++.h> 
using namespace std;

long long b, k, num[200010], ans, n, cnt;
vector <int> v;
const int mod = 998244353;

bool isp(int x) {
    if (x < 2) return 0;
    for (int i = 2; i <= sqrt(x); ++i)
        if (x % i == 0) return 0;
    return 1;
}

void run(void) {
    cin >> b >> k;
    n = b, ans = 1, cnt = 0, v.clear();
    memset(num, 0, sizeof(num));

    for (int i = 2; i <= sqrt(b); ++i) {
        if (!isp(i) || n % i != 0) continue;

        v.push_back(i), cnt++;
        while (n % i == 0) num[i]++, n /= i;
    }

    if (n != 1) v.push_back(n), num[n]++;

    for (int i = 0; i < cnt; ++i) {
        num[v[i]] = (num[v[i]] * (k - 1)) % mod;
        ans = (ans * (num[v[i]] + 1)) % mod;
    }
    cout << ans % mod << endl;
}

int main() {
    int t;
    cin >> t;
    while (t--) run();
}

• P1177 （橙）

快排啊孩子

我竟然不会了快排了

额，就是两边从中间搜，然后换换换，然后再分开，重复上面步骤。

void qs(int a[], int l, int r) {
    int i = l, j = r, f = a[(l + r) / 2];
    do {
        while (a[i] < f) ++i;
        while (a[j] > f) ++j;
        if (i <= j)
            swap(a[i], a[j]), ++i, --j;
    } while (i <= j);
    if (l < j) qs(a, l, j);
    if (i < r) qs(a, i, r);
}

wtcl呜呜呜

2 - 12

• P2036 （橙）

搜索。

但是比较巧妙。

直接贴代码。

#include <bits/stdc++.h>
using namespace std;

int s[15], b[15], n, ans = 0x7fffffff;

void dfs(int i, int x, int y) {
    if (i > n) {
        if (x == 1 && y == 0) return;
        ans = min(ans, abs(x - y));
        return;
    }
    dfs(i + 1, x * s[i], y + b[i]);
    dfs(i + 1, x, y);
}

int main() {
    cin >> n;
    for (int i = 1; i <= n; ++i) 
        cin >> s[i] >> b[i];
    dfs(1, 1, 0);
    cout << ans;
    return 0;
}