专栏文章

251113noip模拟赛总结

wwendywu
个人记录参与者 2已保存评论 1

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
1 条
当前快照
1 份
快照标识符
@min91pst
此快照首次捕获于
2025/12/01 22:33
3 个月前
此快照最后确认于
2025/12/01 22:33
3 个月前
查看原文
100 + 100 + 52 + 0 = 252：）
4个都是cutezrr题目，数论 + 构造 + 人类智慧 + 黑 = cutezrr

A - plant

烧烤10min10min没有思路，然后开心的发现读错题了：）
首先想到一个数（p1k1×p2k2×…p_1^{k_1} \times p_2^{k_2} \times …）的正因数个数为(k1+1)(k2+1)…(k_1 + 1)(k_2 + 1)…
一开始读错题是把“宽度的乘积”看成和了
然后我们发现每个质因数的总个数是确定的（总不可能不把ww用完吧），所以应该尽量平均的分配这些质因数
那就用质数个数个setset，直接模拟就好了
CPP
#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=6n = 6的时候直接就玩不下去了，怎么试都试不出结论（这个时候已经玩了30min30min，有点zrr）
然后决定用一下脑子，首先发现它是把所有的无序对填进去
然后感觉无序对中两个数的差的个数似乎有点符合这种三角形的形状（差11的有n−1n - 1个，差22的有n−2n - 2个……）
然后想到了这种构造方式（数字是一个间隔，是旁边两个数的差）：
CPP
1
1 2
1 2 3
1 2 3 4
感觉有点cute可行，所以决定试一试
CPP
4
1 2
2 3 1
3 4 2 qwq
哎呀怎么填不下去了，那就改一下顺序
CPP
4
1 2
3 4 2
2 3 1 4
成功了！！
于是又试了一下n=5n = 5的，还有n=6n = 6的：
CPP
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…n, 1, n - 1, 2, n - 2, 3…
稍微烧烤一下就能想到为什么，因为每一行其实就是i,i+1,i−1,i+2…i, i + 1, i - 1, i + 2…那越往下，要填的数越多，开头的数就得越靠近n2\frac{n}{2}
然后就可以做了：）
CPP
#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:209:20，我居然已经获得了200pts200pts，都怪zrr
然后因为我T3 + T4都只有52pts52pts，所以相当于我2.5h2.5h都没干什么事，T3T4真是【】题目
首先发现我不可能获得300分，所以直接看到部分分
n≤10n \le 10直接大暴力
k≤2k \le 2就相当于都是k=1k = 1，所以就贪心地把优美度大的往边上放，复杂度O(nlogn)O(nlogn)
难道就32pts32pts就结束了吗？qwq
又烧烤了1h1h发现这其实是人类智慧，当n>n >一个数（大概是3030几）的时候，值相同但本质不同的排列就会>k>k，也就是直接当k=1k = 1
开心了1s1s，然后发现就算k=1k = 1我也不会算n>106n > 10^6的答案，n=11n = 11到临界值的答案我也不会qwq
死去了啊。。。
于是和xbcxbc一起骂了5min5min题目过于bt，然后开心的发现原来那份暴力代码其实可以拿52pts52pts，而不是32pts32pts
后面又烧烤了很久，但没什么进展（感觉像dpdp或者一些神秘的数学）
CPP
#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;
}
看懂了题解，原来nn在11−2811-28的时候是用dpdp，>106> 10^6的时候是数论
我居然猜对了：）
但是dpdp的状态有66维，于是就发生了一些神奇的事情：
CPP
fill(&f[0][0][0][0][0][0], &f[15][8][4][2][1][M + 1], 0);
还有：
CPP
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
真的好难看懂啊！！看题花了20min20min qwq
没什么烧烤的方向，于是打了一个输出AA的00分代码：）
最后10min10min写了一个没样例测的爆搜，喜提00分
CPP
#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暴力没打好

评论

共 1 条评论，欢迎与作者交流。

正在加载评论...