补题篇--codeforces

传送门：Problem - 1881C - Codeforces

题目大意：

思路：

首先解决这个问题要知道 一个 ( x , y ) 顺时钟旋转 90 ， 180 ， 270可以得到 ( y , n - x + 1 ) ，

( n - x + 1 , n - y + 1 ) ，( n - y + 1 , x )

由于一个字符只能增大，所以可以找到旋转位置的最大字符，每个字符都要变成最大字符，因此求出答案

AC代码：

#include<bits/stdc++.h>
using namespace std;
#define int long long
void solve()
{int n; cin >> n;vector<vector<char>> arr(n + 1, vector<char>(n + 1));for (int i = 1; i <= n; i++){for (int j = 1; j <= n; j++) cin >> arr[i][j];}int ans = 0;for (int i = 1; i <= n; i++){for (int j = 1; j <= n; j++){int temp1 = max({ arr[i][j] , arr[j][n - i + 1] , arr[ n - j + 1 ][i] , arr[n - i + 1][n - j + 1] }) - 'a';int temp2 = arr[i][j] + arr[j][n - i + 1] + arr[n - j + 1][i] + arr[n - i + 1][n - j + 1] - 4 * 'a';ans += 4 * temp1 - temp2;}}cout << ans / 4 << endl;
}
signed main()
{int tt; cin >> tt;while (tt--)solve();return 0;
}

传送门：Problem - 1879C - Codeforces

题目大意：

思路：

如何计算最小操作次数： 相同的区间段只能保留一个数字     00011101001111  -> 3 3 1 1 2 4

需要删除的数字个数 sum = ( len1 - 1 ) + ( len2 - 1 ) + ( len3 - 1 ) ......

如何计算最短操作序列的个数：C( len - 1 , len )  == len，一个区间段需要删除的数字序列是 len，

而这些数 ( sum )做全排列，sum的阶乘 答案就是 len * sum!

0110110001 -> 1  2  1  2  3  1 ->第一个序列不用删除，第二个序列 11 可以删除 2 个(第二个或第三个1) ，第三个序列不用删除，第四个序列删除 3 个 ，第五个序列不用删除，删除的这些数还有做全排列

AC代码：

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N = 2e5 + 10;
const int mod = 998244353;
int f[N];
void solve()
{string s; cin >> s;int n = s.size();s = " " + s;int ans = 1;int sum = 0;int len = 1;for( int i = 2; i <= n; i++){if( s[i] != s[i-1] ) {ans = ans * len % mod ; sum += ( len - 1 ); len = 1;}else len++;}ans = ans * len % mod;sum += ( len - 1 );cout << sum << " " << ans * f[sum] % mod << endl;
}
signed main()
{f[0] = 1;for( int i = 1; i <= 2e5 ; i++ ) f[i] = f[i-1] * i % mod;// 预处理阶乘int tt; cin >> tt;while(tt--)solve();return 0;
}

传送门：Problem - 1877C - Codeforces

题目大意：

思路：

结论题：

当 k == 1 时，易得 a[ n + 1] = 0

当 k == 2 时，min( n - 1 , m ) + m / n 

当 k == 3 时 ，m - min( n - 1 , m ) - m / n

当 k > 3 时，0

AC代码：

#include<bits/stdc++.h>
using namespace std;
#define int long long
void solve()
{int n , m , k;cin >> n >> m >> k;if( k > 3 ){cout << 0 << endl;}else if( k == 1 ){cout << 1 << endl;}else if( k == 2 ){cout << min( n - 1 , m ) + m / n << endl;}else {cout << m - min( n - 1 , m ) - m / n << endl;}
}
signed main()
{int tt; cin >> tt;while(tt--)solve();return 0;
}

补题篇：Problem - A - Codeforces

 题目大意：

思路：

水母与海蜇进行的是相同的操作，同一个周期中，选手 a , b 的做法，都是一样的

所以可以缩短周期，进行模拟

新的周期 k = ( 100 + ( k & 1 ) ) 

AC代码：

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N = 55;
int a[N] , b[N];
void solve()
{int n , m , k;cin >> n >> m >> k;k = min( k , 100 + (k & 1) );for( int i = 1; i <= n; i++) cin >> a[i];for( int i = 1; i <= m ;i++) cin >> b[i];for( int i = 1; i <= k; i++){if( i & 1 ){int i1 = 1 , i2 = 1;for( int i = 1; i <= n; i++) if( a[i1] > a[i] ) i1 = i;for( int i = 1; i <= m; i++) if( b[i2] < b[i] ) i2 = i;if( b[i2] > a[i1] ) swap( a[i1] , b[i2] );}else{int i1 = 1 , i2 = 1;for( int i = 1; i <= n ;i++) if( a[i1] < a[i] ) i1 = i;for( int i = 1; i <= m; i++) if( b[i2] > b[i] ) i2 = i;if( a[i1] > b[i2] ) swap( a[i1] , b[i2] );}}int sum = 0;for( int i = 1; i <= n; i++) sum += a[i];cout << sum << endl;
}
signed main()
{int tt; cin >> tt;while(tt--)solve();return 0;
}

传送门：Problem - D - Codeforces

题目大意：

思路：

x 的倍数位置上应该放大数 ， y 的倍数位置上应该放小数，如果说 一个位置是 x 的倍数 ，y的倍数，这个位置是没有贡献的（不计算）

len_x = n / x - n / lcm( x , y ) 

len_y = n / y - n / lcm( x , y )

AC代码：

#include<bits/stdc++.h>
using namespace std;
#define int long long
int gcd( int a ,int  b)
{return b ? gcd( b , a % b ) : a;
}
int lcm( int a ,int  b)
{return a * b / gcd( a , b );
}
int sum ( int l ,int r )
{return ( l + r ) * ( r - l + 1 ) / 2;
}
void solve()
{int n , x , y;cin >> n >> x >> y;int temp = lcm( x , y );int a = n / x  - n / temp;int b = n / y - n / temp;int ans = 0;cout << sum( n - a + 1 , n ) - sum( 1 , b ) << endl;
}
signed main()
{int tt; cin >> tt;while(tt--)solve();return 0;
}

传送门：Problem - D - Codeforces

题目大意：

思路：

插入 n - 2 个字符，一定会有一个二位数，由此作为突破口

f[i][j] （ 1 <= i <= n ,  0 <= j <= 1） 

f[i][0] 表示为前 i 个字符，并没有二位数，插入 i - 2 个字符的最小结果

f[i][1] 表示为前 i 个字符，有二位数，插入 i - 2 个字符的最小结果

状态转移：

f[i][0] = min( f[i-1][0] * ( s[i] - '0' ) , f[i-1][0] * ( s[i] - '0' ) )

f[i][1] = min( f[i-1][1] * ( s[i] - '0' ) , f[i-1][1] + ( s[i] - '0' ) , f[i-2][0] * ( 10 * ( s[i-1] - '0' ) + s[i] - '0' ),

f[i-2][0] + ( 10 * ( s[i-1] - '0' ) + s[i] - '0' ) );

AC代码：

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N = 25;
int f[N][2];
void solve()
{int n; string s;cin >> n >> s;s = " " + s;int a = s[1] - '0'; int b = s[2] - '0';f[1][0] = a;f[1][1] = 2e18; // 不可能存在的状态f[2][0] = min( a * b , a + b );f[2][1] = 10 * a + b;for( int i = 3 ; i <= n; i++){int a = s[i] - '0';int b = s[i-1] - '0';f[i][0] = min( f[i-1][0] * a , f[i-1][0] + a );f[i][1] = min({ f[i-1][1] * a , f[i-1][1] + a , f[i-2][0] + ( 10 * b + a ) , f[i-2][0] * ( 10 * b + a ) } );}cout << f[n][1] << endl;
}
signed main()
{int tt; cin >> tt;while(tt--)solve();return 0;
}

传送门：登录—专业IT笔试面试备考平台_牛客网

题目大意：

思路：

类似于 dp 问题 ，定义为 sum 为能够表示的 <= sum 的数都能够表达出来

当 sum >= a[i] - 1 才能转移 ，假设 sum == 7 , a[i] == 9 此时数字8无法表示，

sum == 7 , a[i] == 8 就可以转移

AC代码：

#include<bits/stdc++.h>
using namespace std;
#define int long long
void solve()
{int sum = 0;int n; cin >> n;vector<int> a( n + 1 );for( int i = 1; i <= n; i++) cin >> a[i];sort( a.begin() + 1 , a.end());for( int i = 1; i <= n; i++){if( sum >= a[i] - 1 )sum += a[i];}if( sum >= n )puts("Cool!");else cout << sum + 1 << endl;
}
signed main()
{int tt; cin >> tt;while(tt--)solve();return 0;
}

传送门：Problem - C - Codeforces

题目大意：

给定数组 a ，一共有 n 个元素，请构造数组 b ，使得 a[i] * b[i] > sum ( sum 为 数组 b 的和 )，

如果不能构造输出-1，如果能输出数组 b

思路：

结论题：类似的这种题可以往 gcd , lcm 这类问题上套

AC代码：

#include<bits/stdc++.h>
using namespace std;
#define int long long
int gcd( int a ,int b )
{return b ? gcd( b , a % b ) : a;
}
int lcm( int a , int b )
{return a * b / gcd( a , b );
}
void solve()
{int n; cin >> n;vector<int> a( n + 1 );int sum = 1;for( int i = 1; i <= n; i++){cin >> a[i];sum = lcm( sum , a[i] );}vector<int> ans( n + 1 );int temp = 0;for( int i = 1; i <= n ;i++){ans[i] = sum / a[i];temp += ans[i];}if( temp >= sum ){cout << -1 << endl;return;}else{for( int i = 1; i <= n; i++)cout << ans[i] << " ";cout << endl;}
}
signed main()
{int tt; cin >> tt;while(tt--)solve();return 0;
}