2025.8.20 Codeforces Round 1013 (Div. 3)

总结

感觉自己图论还是不太行，下一周还是要以加训图论专题为主了，不过终归还是有点进步的qwq，

一次第一次把div3补完，希望以后有一天能进前一千名

题目部分

A. Olympiad Date

题意

我们有 $ n $ 个数字，我们要凑出来 $ 01.03.2025 $ 问最早什么时候能凑出来，凑不出来就输出$ -1 $

思路

要哈希或数组存一下数字的数量, 如果到 $ 0 $ 的时候存一下，最后判断一下是否全部数字 $ <=0 $ 即可，这样如果凑的出来，我们肯定能得到最早的数字。

代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
vector<int>a(11 , 0 ) ;
a[0] = 3 ; 
a[1] = 1 ;
a[2] = 2 ; 
a[3] = 1 ;
a[5] = 1 ;  
int n ; cin >> n ;
int flag = 0 ; 
for(int i = 1; i<= n ; i++){
   int x ; cin >> x ;
   if(--a[x] == 0 )flag = i  ; 

} 

for(int i =0 ; i<=  9; i++){
   if(a[i] > 0 )flag = 0  ; 
}
cout << flag << '\n' ;

B. Team Training

题意

给我们长度为 $ n $ 的数组和一个数字 $ x $ ，我们需要寻找最多强度大于等于 $ x $ 的子序列。强度的计算公式为子序列大小乘以数组内的元素最低值。

思路

首先因为不要求连续，所以我们就可以先排个序。然后先去把强度 $ >=x $ 的一人组成一个队，剩下 $ < x $ 的就贪心的进行选择，如果符合条件就 $ ans++ $ 否则继续找下去，直到搜完。

代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
int n , x ;cin >> n >> x ;
 vector<int>a(n+1) ; 
 int ans = 0 ; 
 for(int i =1 ; i <= n ; i++){
    cin >> a[i] ;
    if(a[i] >= x )ans++ ; 
 }
 sort(a.begin() + 1 ,  a.end()) ;
 
 int num = 0 ;
 int mi = inf ;   
 for(int i = n ; i>= 1 ; i--){
    if(a[i]>=x)continue ;  
    mi = min(mi , a[i]) ; 
    num ++ ; 
    if(num * mi >= x){
       ans ++ ; 
       num = 0 ; 
       mi = inf ; 
    }
 }
 cout << ans << '\n';

C. Combination Lock

题意

我们需要判断一个长度为 $ n $ 的环形排列，这个排列会循环位移，要求每次循环都有恰好一个元素等于他在排列中的位置。如果存在我们就输出一组有效排列，否则输出 $ -1 $ 。

思路

我们使用瞪眼法,我们思考一下，要满足条件，我们需要构造的数组为 $ a $，我们设排列数组位置为 $ b $ , 我们可以构造 $ a_1 $ 距离 $ b_1 $ 为 $ 1 $ , $ a_2 $ 距离 $ b_2 $ 为 $ 2 $ , $ a_3 $ 距离 $ b_3 $ 为 $ 3\dots $ 。

我们顺着这个思路手玩一下，$ 12345 $ , 我们可以发现 $ 54321 $ 完美符合我们的需求, 而偶数情况下，我们则发现我们这样子搭配，肯定会有数字重复或者没有的情况，所以我们只需要先判断 $ n $ 的奇偶性，再倒序输出即可。

代码
1
2
3
4
5
6
7
int n ; cin >> n ; 
 if(!(n&1)){
    cout << -1 << '\n' ;
    return ;
 }
 for(int i = n ; i>= 1 ; i--)cout << i << ' ';
 cout << '\n';

D. Place of the Olympiad

题意

有 $ k $个人要分布到 $ n \times m $ 个位置上，如果同一行有多个人挨在一起则为他们放一个长凳，要求最长的长凳子尽可能小

思路

因为我们只有同一行有多个人挨在一起才会是长凳，所以我们各个行都可以使用同样的贪心策略，一行则最多有 $ \lceil \frac{k}{n} \rceil $ 人。令 $ x = m - \lceil \frac{k}{n} \rceil + 1 $ 。我们有x个空位来隔开人群，问题则转化为了我们有 $ x $ 个空地来放 $ \lceil \frac{k}{n} \rceil $ 个人，使得最大值最小。

根据鸽巢原理，我们的答案则是 $ ( \lfloor \frac{k}{n} \rfloor -1 ) / x + 1 $

代码
1
2
3
4
5
int n , m , k ; cin >> n >> m >> k ;
int st = (n + k - 1 ) / n; //最长的一排最多几个 
int kong = m - st ; 
kong++ ; 
cout << (st - 1 ) / kong + 1 << '\n';

E. Interesting Ratio

题意

给我们一个 $ n $ 令 $F(a,b)=\frac{lcm(a, b)}{gcd(a, b)}$ , 求 $ 0< a < b \leq n $ 并且 $F(a, b)$ 是个素数的数量

思路

我们将公式展开可得 $ F(a,b)=\frac{lcm(a, b)}{gcd(a, b)} = \frac{\frac{a \times b}{gcd(a, b)}}{gcd(a, b)} = \frac{a\times b}{gcd(a, b)^2} = \frac{a}{gcd(a, b)} \times \frac{b}{gcd(a, b)} $ 。

因为 $ F(a,b) $ 一个因子必须为 $ 1 $ , 我们令 $ \frac{a}{gcd(a, b)} = 1 $ 且 $ \frac{b}{gcd(a, b)} = p $ 其中 $ p $ 为一个素数。

对于每个 $ p $ , $ a $ 和 $ b $ 的个数为$ \frac{n}{p} $，我们统计一下即可

代码
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
  void primes()//欧拉筛板
{
	for(int i = 2;i<=N - 5;i++)
	{
		if(!vis[i])
		{
			prime.push_back(i);
		}
		for(int j = 0;j<prime.size()&&i*prime[j]<=N;j++)
		{
			vis[i*prime[j]] = 1;
			if(i%prime[j]==0)
			{
				break;
			}
		}
	}
}
void solve(){
   int n ; cin >> n ;
   i64 ans = 0 ;
   for(int i =0 ; i< prime.size() && prime[i] <= n ; i++){
      ans += n / prime[i] ; 
   }
   cout << ans << '\n' ;
}
int main(){
   //cout << helpme ;
   ios::sync_with_stdio(0) , cin.tie(0) ; 
   int t = 1 ;
   cin >> t ;
   primes() ; 
   while(t--){
      solve() ; 
   }
   return 0;
}

F. Igor and Mountain

题意

题目要求我们从下面往上面，一行一行的爬，每一行最少用一个支点，最多两个支点，直到山顶有多少个路线

思路

很容易的发现，从最下面爬到最上面和从最上面爬到最下面没啥区别，从习惯上，我们就选择从最上面爬到最下面。

首先考虑dp，我们面对子问题去思考，可以发现这种只有两种方式，一种状态是从左边往右边转移，一种是从上面转移到下面。我们可以发现，选择从上面转移到下面，再从左边转移到右边是合适的。

我们可以从 $ d = \sqrt{(i_1 - i_2) ^ 2 + (j_1 - j_2) ^ 2} \leq k $ 的地方转移过来，当我们 $ \lvert i_1 - i_2 \rvert = 1 $ 的时候 $ \lvert j_1 - j_2\rvert \leq k -1 $ 。 当我们 $ \lvert i_1 - i_2 \rvert = 0 $ 的时候 $ \lvert j_1 - j_2\rvert \leq k $ .

而对于dp计算的时候，我们可以使用前缀和进行快速, 得到 $ dp[i][j] = pre[r] - pre[l-1] $ 。又因为第一个操作对于第二个操作没有后效性。所以我们重复沿用即可
$ dp[i][j] = dp[i][j] + pre[r] - pre[l-1] $

最后答案就是 $ pre[m] $

代码
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
int n , m , d ; 
cin >> n >> m >> d ; 
vector<vector<int>>G(n+1) ; 
for(int i = 1 ; i<= n ; i++){
   for(int j =1 ; j<= m ; j++){
      char c ; cin >> c ;
      if(c == 'X')G[i].push_back(j) ; 
   }
}
vector<vector<i64>>dp(n+1 , vector<i64>(m+1)) ; 
for(int x : G[1]){
     dp[1][x] = 1;
     auto l = lower_bound(G[1].begin(), G[1].end(), x - d) - G[1].begin();
     auto r = upper_bound(G[1].begin(), G[1].end(), x + d) - G[1].begin();
     (dp[1][x] += r - l - 1) %= MOD;
 }
vector<int>pre(m+1) ; 
for(int i = 1; i <= m; i++) pre[i] = (pre[i - 1] + dp[1][i]) % MOD; 
for(int i = 2 ; i<= n ; i++){
   for(const auto & x : G[i]){
      int l = max(1 , x - d + 1 ) , r = min(m , x + d -1 ) ; 
      dp[i][x] = (dp[i][x] +pre[r] - pre[l-1]) % MOD;
   }
   for(int j = 1;  j<= m ;j++)pre[j] =(pre[j-1] + dp[i][j] )%MOD ; 
   for(const auto & x: G[i]){
      int l =max(1 , x-d) , r = min(m,x + d ) ; 
      dp[i][x] = (dp[i][x] +pre[r] - pre[l-1] - dp[i][x])%MOD ; 
   }
   for(int j = 1;  j<= m ;j++)pre[j] =(pre[j-1] + dp[i][j] )%MOD ; 
}
cout << ((pre[m] % MOD + MOD )% MOD )<< '\n' ;

G. leb and Boating

题意

我们需要在 $ [0,s] $ 的数轴上移动，初始步长为k，默认方向是 $ 0 \rightarrow s $ 转弯一次会使方向取反，并且必须滑动一次,并且使得 $ k = max(k-1 , 1 ) $ , 求到达 $ s $ 的 $ k $ 的最大值

多测 $ 1 \leq s \leq 1e^9 , 1 \leq k \leq 1000 $ , 保证所有测试用例的 k 之和不超过 2000

思路

注意到如果 $s \mid k $ 的时候，我们肯定可以划过去，如果 $ s \geq k^2 $ 的时候，我们肯定可以划到 $ k - 2 $ 的倍数然后调头划过去，答案不劣于 $ k - 2 $

所以我们将范围缩小成 $ k^2 $ 的级别，并且当 $ s \geq k^2 $ 的时候，我们肯定可以得到答案，我们考虑bfs，每一次我们都滑过每一个没滑过的点，跑一遍，当我们到达了一个没达到的时候，我们就收入，接着跑，直到有一次到达了终点，时间复杂度最多 $ O(n^3) $

代码
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
int s , k ;cin >> s >> k ;
if(s%k == 0 ){
   cout << k << '\n' ; 
   return ;
}else if(s > k* k) {
   cout << max(k-2 , 1) << '\n' ; 
   return ; //如果过大，我们肯定能找到一个地方是k-2 然后转头回去
}
queue<Node>q ;
q.push({0,k+ 1 , -1}) ;int now = 0;
vector<int>vis(s + 1) ; 
while(!q.empty()){
   auto [pos , val , d ] = q.front() ; q.pop() ; 
   d = -d ; //n-2疯狂走，走到最后回去再看看等不等于0
   if(val != 1 )val -- ; 
   if(val != now){
      now = val ;
      fill(vis.begin(), vis.end(), 0);//重制

   }
   for(int i =1 ; ; i++){
      int nxt =pos + d * val * i ;
      if(nxt < 0 || nxt > s )break ; 
      if(nxt == s ){
         cout << val << '\n' ;
         return ;
      }
      if(!vis[nxt]){
         q.push(Node{nxt,val , d }) , vis[nxt] = 1 ; 
      }
   }
}