251113noip模拟赛总结

wendywu · 2025-11-13 14:59:29 · 个人记录

100 + 100 + 52 + 0 = 252：）
4个都是cutezrr题目，数论 + 构造 + 人类智慧 + 黑 = cutezrr

A - plant

烧烤10min没有思路，然后开心的发现读错题了：）

首先想到一个数（p_1^{k_1} \times p_2^{k_2} \times …）的正因数个数为(k_1 + 1)(k_2 + 1)…

一开始读错题是把“宽度的乘积”看成和了

然后我们发现每个质因数的总个数是确定的（总不可能不把w用完吧），所以应该尽量平均的分配这些质因数

那就用质数个数个set，直接模拟就好了

#include <bits/stdc++.h>
#define LL long long

using namespace std;

const int N = 1e4 + 5, mod = 998244353;

LL n, w, p[N], ans;
priority_queue <LL> q[N];

LL qpow (LL x, LL y) {
  LL ret = 1;
  for (; y; y >>= 1) {
    if (y & 1) {
      (ret *= x) %= mod;
    }
    (x *= x) %= mod;
  }
  return ret;
}

void add (int x) {
  // cout << x << ' ' << q[x].size() << '\n';
  if (q[x].size() < n) {
    ans *= 2;
    ans %= mod;
    q[x].push(-1);
    // cout << " 1\n";
  } else {
    LL tmp = -q[x].top();
    q[x].pop();
    ans *= qpow(tmp + 1, mod - 2);
    ans %= mod;
    tmp++;
    ans *= tmp + 1;
    ans %= mod;
    q[x].push(-tmp);
    // cout << "  " << tmp << '\n';
  }
}

int main () {
  ios::sync_with_stdio(0), cin.tie(0);
  cin >> n >> w;
  ans = 1;
  for (int i = 1; i <= n; i++) {
    cin >> p[i];
    for (int j = 2; j * j <= p[i]; j++) {
      if (p[i] % j) continue;
      LL sum = 0;
      for (; p[i] % j == 0; p[i] /= j, sum++);
      ans *= sum + 1;
      ans %= mod;
      q[j].push(-sum);
    }
    if (p[i] != 1) {
      ans *= 2;
      ans %= mod;
      q[p[i]].push(-1);
    }
  }
  for (int i = 2; i * i <= w; i++) {
    for (; w % i == 0; w /= i, add(i));
  }
  if (w != 1) {
    add(w);
  }
  cout << ans;
  return 0;
}

B - woof

~~哎呀第一次场切紫题：）qwq~~

看到这种~~cutezrr~~题目，首先肯定会想要手玩一下

然后到n = 6的时候直接就玩不下去了，怎么试都试不出结论（这个时候已经玩了30min，有点zrr）

然后决定用一下脑子，首先发现它是把所有的无序对填进去

然后感觉无序对中两个数的差的个数似乎有点符合这种三角形的形状（差1的有n - 1个，差2的有n - 2个……）

然后想到了这种构造方式（数字是一个间隔，是旁边两个数的差）：

感觉有点~~cute~~可行，所以决定试一试

哎呀怎么填不下去了，那就改一下顺序

成功了！！

于是又试了一下n = 5的，还有n = 6的：

5
1 2
4 5 3
2 3 1 4
3 4 2 5 1

6
1 2
5 6 4
2 3 1 4
4 5 3 6 2
3 4 2 5 1 6

然后继续烧烤这个顺序怎么排，~~注意到~~其实就是n, 1, n - 1, 2, n - 2, 3…

稍微烧烤一下就能想到为什么，因为每一行其实就是i, i + 1, i - 1, i + 2…那越往下，要填的数越多，开头的数就得越靠近\frac{n}{2}

然后就可以做了：）

#include <bits/stdc++.h>
#define LL long long

using namespace std;

const int N = 4e3 + 5;

int n, t, ans[N][N];

int main () {
  // freopen("woof2.in", "r", stdin);
  // freopen("woof.out", "w", stdout);
  cin >> n >> t;
  for (int i = 1; i <= n; i++) {
    if (i * 2 <= n) ans[i * 2][1] = i;
    else ans[n - (i * 2 - n) + 1][1] = i;
  }
  for (int i = 1; i <= n; i++) {
    for (int j = 2; j <= i; j++) {
      if (j & 1) {
        ans[i][j] = ans[i][j - 1] - j + 1;
      } else {
        ans[i][j] = ans[i][j - 1] + j - 1;
      }
    }
  }
  for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= i; j++) {
      cout << ans[i][j] << ' ';
    }
    cout << '\n';
  }
  return 0;
}

/*
5
1 2
4 5 3
2 3 1 4
3 4 2 5 1

6
1 2
5 6 4
2 3 1 4
4 5 3 6 2
3 4 2 5 1 6

c***z**
*/

赛后看HKE的代码，原来根本不用管顺序，按每一个开头能有的长度排个序就行。。。wssb

C - npc

现在是9:20，我居然已经获得了200pts，~~都怪zrr~~

然后因为我T3 + T4都只有52pts，所以相当于我2.5h都没干什么事，T3T4真是【】题目

~~首先发现我不可能获得300分~~，所以直接看到部分分

$k \le 2$就相当于都是$k = 1$，所以就贪心地把优美度大的往边上放，复杂度$O(nlogn)

难道就32pts就结束了吗？qwq

又烧烤了1h发现这其实是人类智慧，当n >一个数（大概是30几）的时候，值相同但本质不同的排列就会>k，也就是直接当k = 1

开心了1s，然后发现就算k = 1我也不会算n > 10^6的答案，n = 11到临界值的答案我也不会qwq

死去了啊。。。

于是和xbc一起骂了5min题目过于bt，然后开心的发现原来那份暴力代码其实可以拿52pts，而不是32pts

后面又烧烤了很久，但没什么进展（感觉像dp或者一些神秘的数学）

#include <bits/stdc++.h>
#define LL long long

using namespace std;

const int N = 1e6 + 5, mod = 998244353;

LL q, n, k, f[N], vis[N];
priority_queue <LL> pq;

int lb (int x) {
  return x & -x;
}

LL qwq (int x) {
  return log2(lb(x)) + 1;
}

void dfs (int x) {
  if (x == n + 1) {
    LL sum = 0;
    for (LL i = 1; i <= n; i++) {
      sum += qwq(f[i]) * i * (n - i + 1);
    }
    if (pq.size() == k && pq.top() <= sum) return;
    if (pq.size() < k) {
      pq.push(sum);
    } else {
      pq.pop();
      pq.push(sum);
    }
    return;
  }
  for (int i = 1; i <= n; i++) {
    if (vis[i]) continue;
    vis[i] = 1;
    f[x] = i;
    dfs(x + 1);
    vis[i] = 0;
  }
}

LL solve1 () {
  for (; pq.size(); pq.pop());
  dfs(1);
  return pq.top() % mod;
}

LL solve2 () {
  LL l = 1, r = n, ret = 0;
  for (; pq.size(); pq.pop());
  for (int i = 1; i <= n; i++) {
    pq.push(qwq(i));
  }
  for (int i = 1; i <= n; i++) {
    if (l < n - r + 1) {
      ret += pq.top() * l * (n - l + 1) % mod;
      ret %= mod;
      l++;
    } else {
      ret += pq.top() * r * (n - r + 1) % mod;
      ret %= mod;
      r--;
    }
    pq.pop();
  }
  return ret;
}

int main () {
  ios::sync_with_stdio(0), cin.tie(0);
  for (cin >> q; q--;) {
    cin >> n >> k;
    if (n <= 10) {
      cout << solve1() << '\n';
    } else {
      cout << solve2() << '\n';
    }
  }
  return 0;
}

看懂了题解，原来n在11-28的时候是用dp，> 10^6的时候是数论

我居然猜对了：）

但是dp的状态有6维，于是就发生了一些神奇的事情：

fill(&f[0][0][0][0][0][0], &f[15][8][4][2][1][M + 1], 0);

还有：

for (now[1] = 0; now[1] <= c[1]; now[1]++)
for (now[2] = 0; now[2] <= c[2]; now[2]++)
for (now[3] = 0; now[3] <= c[3]; now[3]++)
for (now[4] = 0; now[4] <= c[4]; now[4]++)
for (now[5] = 0; now[5] <= c[5]; now[5]++)

ctr就是个~~zrr~~大变态！

太变态了qwq
太变态了qwq
太变态了qwq
太变态了qwq
太变态了qwq
太变态了qwq
太变态了qwq
太变态了qwq
太变态了qwq
太变态了qwq
太变态了qwq
太变态了qwq
太变态了qwq
太变态了qwq
太变态了qwq
太变态了qwq
太变态了qwq
太变态了qwq
太变态了qwq
太变态了qwq
太变态了qwq
太变态了qwq
太变态了qwq
太变态了qwq
太变态了qwq
太变态了qwq
太变态了qwq
太变态了qwq
太变态了qwq
太变态了qwq
太变态了qwq
太变态了qwq
太变态了qwq
太变态了qwq
太变态了qwq

D - mahjong

黑色的博弈论！！~~zrr~~

“打过麻将的话，题意应该不是很难看懂，没打过的话，应该也还可以”
——kkksc03

真的好难看懂啊！！看题花了20min qwq

没什么烧烤的方向，于是打了一个输出A的0分代码：）

最后10min写了一个没样例测的爆搜，喜提0分

#include <bits/stdc++.h>
#define LL long long

using namespace std;

int n, m, k, a[5];

int dfs (int x, int aa, int bb) {
  if (x & 1) {
    if (a[x] == aa) return 0;
    if (a[x] == bb && aa == bb) return 2;
    if (a[x] == bb) {
      return dfs(x + 1, a[x], bb);
    }
    if (aa == bb) {
      return dfs(x + 1, aa, bb);
    }
    return min(dfs(x + 1, aa, bb), dfs(x + 1, a[x], bb));
  } else {
    if (a[x] == bb) return 2;
    if (a[x] == aa && aa == bb) return 0;
    if (a[x] == aa) {
      return dfs(x + 1, aa, a[x]);
    }
    if (aa == bb) {
      return dfs(x + 1, aa, bb);
    }
    return max(dfs(x + 1, aa, bb), dfs(x + 1, aa, a[x]));
  }
}

int main () {
  cin >> n >> m >> k;
  if (n <= 3 && m <= 3) {
    for (int i = 1; i <= n; i++) cin >> a[i];
    for (int i = 1, aa, b, l, r; i <= m; i++) {
      cin >> aa >> b >> l >> r;
      int tmp = dfs(1, aa, b);
      if (tmp == 0) {
        cout << "A\n";
      } else if (tmp == 1) {
        cout << "D\n";
      } else {
        cout << "B\n";
      }
    }
    return 0;
  }
  while (m--) {
    cout << "A\n";
  }
  return 0;
}

前两题还挺顺利的，T3烧烤了太久才发现是人类智慧，T4暴力没打好