2025.8.20 Codeforces Round 1016 (Div. 3)
总结
最近跑去参加了贵阳的代码源集训营，回去又摸鱼了好久，最近大补了一下图论，感觉还好。准备接下来继续补图。
昨天vp了一下，个人感觉其实自己分治的思维不太行，(关于F做的出来D反而不会这档事),等图论练完可以尝试训练一下，以及有空可以补一下字典树。
ok，唠嗑完了，开局
题目部分
题意
我们有一个长度为 $ k $ 的数组 $ a $ ,如果这个数组和对任意 $ n(n>=k) $ ，并且有回文的特性，我们就称他为理性生成器，否则输出No
思路
我们手玩一下，可以注意到对于任意奇数$k$,我们都可以通过使除中间数以外的数字都为1，中间数为$n-x+1$来满足条件，对任意偶数，我们都可以构造$ n=k+1 $来卡掉。
代码
1
2
3
| int k ; cin >> k ;
if(k&1)cout << "Yes\n" ;
else cout << "No\n";
|
题意
正整数$ n $的价值的定义的成本定义为数字$n$除以其位数之和的结,例如 $104$ 的价值是 $ \frac{104}{1 + 0 + 4} = 20.8 $ 允许前导零的存在。我们可以删除任意位数的数字,剩余的数字必须$ > 0 $，我们该怎么使得操作最少，价值最小
思路
首先我们先考虑什么时候成本的最小值应该是多少，不难发现，分子增长严格大于等于分母增长,所以我们成本最小值是$ 1 $
所以我们就需要构造$ 000….x $的存在。因为只有前导0的存在，不会影响最小值，其它值的存在都会使得价值增大
所以我们从右往左扫一遍。只保留右边出现的一个正整数与左边的零。
代码
1
2
3
4
5
6
| for(int i = 1 ; i< n ; i++){
if(abs(a[i] - a[i+1] ) <= 1 ){
cout << "0\n" ;
return ;
}
}
|
题意
我们有一个新数字 $ y $ 。将数字 $ x $ 的十进制表示（不含前导零）重 $ k $ 次。例如 $ x = 6 $ 和 $ k = 7 $ , 可以得到 $y = 6666666$ .
求$y$是否是素数
思路
首先我们需要注意到，对于任何 $ x (x>1) $ 的数，他的约数肯定有 $ x $ 。必然不是素数。当然 $ 1 $ 不是素数的同时 $ 11 $ 是素数。
所以我们只需要特判一下 $ n $ 是否是素数与 $ k $ 是否等于$ 1 $
因为 $ n $ 很大但是 $ t $ 很小,所以我们根据定义求是否是素数
代码
1
2
3
4
5
6
7
8
9
10
11
12
| int n , k ; cin >> n >> k ;
bool ok = 1 ;
for(int i = 2 ; i <= sqrt(n) ; i++){
if(n % i == 0 ){
ok = 0 ;
break ;
}
}
if( n == 1 && k == 2 )cout << "Yes\n" ;
else if(!ok || k != 1 || n == 1 ){
cout << "No\n" ;
}else cout << "Yes\n" ;
|
题意
大概的意思是，把一个边长为 $ 2^k $ 的表格分割并填上数字，以左上，右下，左下，右上的顺序填充。并且给予两个问题
给$ (x,y) $ 坐标求对应数字。
给出数字求对应坐标。
思路
大概思路就是，我们使用递归的思路，根据题意的左上，右下，左下，右上的顺序，不停的调整我们的起点和终点，不停的递归下去，直到找到。(这题我也不太会，可以根据前往洛谷进行学习)。
代码
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
| i64 n ; cin >> n ;
int q ; cin >> q;
n = pow(2 , 2* n) ;
while(q--){
string s ; cin >> s;
if( s== "->"){
int x , y ; cin >> x >> y ;
const auto dfs =[&](auto && self , i64 mx , i64 T) ->i64{
if(mx == 1 )return T ;
if(x <= sqrt(mx )/2){
if(y <= sqrt(mx) /2 ){
return self(self,mx /4 , T);
}else{
y-=sqrt(mx / 4) ;
return self(self ,mx / 4 , T +(mx / 4) * 3 ) ;
}
}else{
if(y <= sqrt(mx) / 2 ){
x -= sqrt(mx / 4) ;
return self(self , mx / 4 , T +mx /2 ) ;
}else{
x -= sqrt(mx / 4) , y-=sqrt(mx / 4) ;
return self(self,mx / 4 , T + mx / 4) ;
}
}
};
cout << dfs(dfs ,n , 1 ) << '\n';
}else{
i64 x = 1 , y = 1 ;
i64 d ; cin >> d ;
const auto dfs =[&](auto && self , i64 mx , i64 T )-> void{
if(mx == 1 )return ;
if(T <= mx / 4){
self(self , mx / 4 , T) ;
}else if(T <= mx / 2 ){
x += sqrt(mx / 4) , y+=sqrt(mx / 4) ;
self(self , mx / 4 , T-= mx / 4 ) ;
}else if(T <= ((mx / 4 )* 3)){
x +=sqrt(mx / 4 );
self(self , mx /4 , T-= (mx /2) ) ;
}else{
y+=sqrt(mx / 4 );
self(self,mx/4, T-=((mx / 4 )* 3 ) );
}
};
dfs(dfs , n , d ) ;
cout << x << ' ' << y << '\n' ;
}
}
|
题意
初始我们有一个长度为 $ n $ 的数组 c ，其中每个元素都是空白（用符号 * 表示）。
给我们 $ m $ 长度为 $ n $ 个长度字符串数组，我们有两种操作
选择一个字符串数组，随机选择一个空白位置将为$c_j$ 替换为 $b_{i, j}$.
选择一个位置 $ j $ ,将 $ c_j $ 清空。
求多少次操作必然成为指定数组 $ a $ ，如果不可能输出 $ -1 $ 。
思路
首先，手玩一下，我们可以发现，我们可以将所有位置填满，然后剩下的位置先后执行 $ 2,1 $ 操作，这样是最优的。所以我们最好就是找一个元素最符合的数组进行填满。这样是最优的。
通过这样的操作，我们假设选择的字符串和目标相同的字符数量为 $ x $ ，那么答案就是 $ n+(n−x)×2 $ 。
代码
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
| int n , m ; cin >> n >> m ;
vector<string>s1(n+1) ;
vector<vector<string>>s2(m+1 ,vector<string> (n + 1 )) ;
vector<bool>vis(n+1) ;
for(int i =1 ; i<= n ; i++)cin >> s1[i] ;
int mi = inf ;
for(int i = 1; i<= m ; i++){
for(int j = 1 ; j<= n ; j++){
cin >> s2[i][j] ;
}
}
for(int i = 1; i <= m ; i++){
int st = 0 ;
for(int j = 1; j<= n ; j++ ){
if(s2[i][j] == s1[j]){
st ++ ;
vis[j] = 1 ;
}
}
mi = min(mi , n - st ) ;
}
bool flag = 1;
for(int i =1; i<= n ; i++){
flag&= vis[i] ;
}
if(! flag)cout << -1 << '\n' ;
else cout << n +mi * 2 << '\n' ;
|
