2024年1月16日模拟赛

2024年1月16日模拟赛

混氏新子 蒟蒻

总结

今天腊月初六。今天的模拟赛挺有趣的,还可以。不是很想说太多的话,今天有一点累。想清净一下。

30+100+15。C 写挂了,应该搞到 3 的,只算到了 2。

题解

难得这里不写东西。这不还是写了吗?

A. rabbit

怎么说呢?简而言之,就是左右两边一些点,限制了每个点的最大度数,最大度数都小于等于另一边点的个数。然后连边成为二分图,不能有重边,问边最多多少?

这道题其实我到现在都还不是很理解。就枚举然后取 min。我贴个 admin 的代码在这里。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for (int i=a;i<n;i++)
#define per(i,a,n) for (int i=n-1;i>=a;i--)
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
typedef vector<int> VI;
typedef long long ll;
typedef pair<int,int> PII;
const ll mod=1000000007;
ll powmod(ll a,ll b) {ll res=1;a%=mod;for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
// head

const int N=2501000;
int n,m,cnt0[N],cnt1[N];
ll m0,md,cnt2[N];
int main() {
scanf("%d%d",&m,&n);
scanf("%lld%lld",&m0,&md);
rep(i,1,m+1) {
// printf("%lld\n",m0);
cnt0[m0]++;
m0=(m0*58+md)%(n+1);
}
// puts("");
scanf("%lld%lld",&m0,&md);
rep(i,1,n+1) {
// printf("%lld\n",m0);
cnt1[m0]++; cnt2[m0]+=m0;
m0=(m0*58+md)%(m+1);
}
int x=0; ll sx=0;
rep(i,1,m+1) cnt1[i]+=cnt1[i-1],cnt2[i]+=cnt2[i-1];
ll ans=cnt2[m];
// puts("");
rep(i,0,n+1) {
rep(j,0,cnt0[i]) {
x++; sx+=i;
int y=cnt1[m-x];
assert(x<=m&&y<=n);
ll ret=(ll)(m-x)*(n-y)+cnt2[m-x]+sx;
// printf("%lld\n",ret);
ans=min(ans,ret);
}
}
printf("%lld\n",ans);
}

B. count

原题:AT_agc013_e。

就是把一个带子切成很多段,每一段的权值是长度的平方,切法的权值是每一段的权值乘积,有一些位置不能切。求所有方案的权值和。

和上次有一道题有一点类似,还是矩阵快速幂维护就可以了。

C. 会考

原题:CF1510J

就是和上次有一道 IOI 的题目很类似。就是求一个序列,然后给你一个字符串里面为黑的位置表示所有满足黑色连通块和序列对应的字符串的这一位都是黑的。求合法的这个序列。我们考虑把所有黑色段都挤到左边,最右边可能会留下一些空的,那么每一段都可以往右移动最多那么多,因此黑色不动位置一定是一段最靠左和一段最靠右与起来的。(只是同段之间)。那么我们考虑原来最右边有多少个空的,那么就在原串为 1 的位置前补几个 1 就行。简单推一下 1 的情况,大于 1 的情况都类似,而且发现只用考虑 3 以内的。因为如果 4 可以或者以上,那么 2 是一定可以的。

感觉并不是很难啊,感觉今天最难的是 A。

D. Y神

简单来说就是树上每个点有一个权值,为代表未知。然后每次给一条链(有方向),然后给你一个给未知权值上填数的区间,然后问你使得这个序列是单调递增或者单调不减的方案数。

就是一个树上维护 dp 之类的东西。一段之间的东西就可以用组合数,单调不减就用插板法搞一下,的限制可以理解成在序列开头或者结尾加一个或者,取决于比较是否严格。

总之可以理解为码量题。

后记

写完博客好爽,感觉又有做题的动力了!今天表现还不错,但是要注意细节,思考还是不是很严谨,犯了 C 那样的低级错误。低级错误不能再出现!(话说上一次低级错误是啥来着,得赶紧去复习一下)。

  • 标题: 2024年1月16日模拟赛
  • 作者: 混氏新子
  • 创建于 : 2024-01-16 22:40:14
  • 更新于 : 2024-01-16 22:47:43
  • 链接: https://blog.huasushis.cn/2024/2024年1月16日模拟赛/
  • 版权声明: 本文章采用 CC BY-NC-SA 4.0 进行许可。
评论
此页目录
2024年1月16日模拟赛