传送门：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;
}传送门：
题目大意：
思路：
由模拟可得：
每一个矩阵都是一个正方形，我们只需求出左边界和右边界即可 ， 答案即是 ( r - l + 1 ) * 2
如何求出左右边界，可以有递推求出，具体可看代码
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1e5 + 10;
int first[N] , last[N] , min_first[N] , max_last[N];
int a[N];
void solve()
{int n , k; cin >> n >> k;for( int i = 1; i <= n; i++) cin >> a[i];for( int i = 1; i <= n; i++){if( !first[a[i]] )first[a[i]] = i;last[a[i]] = i;}for( int i = 0 ; i <= k + 1; i++ ) min_first[i] = 2e18 , max_last[i] = -2e18;for( int i = k ; i >= 1; i--){if( first[i] ){min_first[i] = min( first[i] , min_first[i+1] );}else min_first[i] = min_first[i + 1];}for( int i = k ; i >= 1 ; i--){if( last[i] ){max_last[i] = max( last[i] , max_last[i + 1] );}else max_last[i] = max_last[i + 1];}for( int i = 1 ; i <= k; i++){if( first[i] ){cout << (max_last[i] - min_first[i] + 1) *2 << " ";}else cout << 0 << " ";}cout << endl;for( int i = 0 ; i <= k + 1; i++) first[i] = last[i] = min_first[i] = max_last[i] = 0;
}
signed main()
{int tt; cin >> tt;while(tt--)solve();return 0;
}传送门：Problem - B - Codeforces
题目大意：
给定一个字符串 s ，长度为 n ，设定从右往左的下标为 1 , 2 , 3 , 4 , 5 .... n ，现有操作：交换两个相邻的字符，输出 下标为 i ，使得 <= i 的下标处 均为 '0' ，最小操作次数
AC代码：
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1e5 + 10;
int f[N];
void solve()
{int cnt = 0;int n ; string s; cin >> n >> s;int pos = n - 1;for( int i = n - 1 ; i >= 0 ; i-- ){if( s[i] == '0' ){f[++cnt] = pos - i;f[cnt] += f[cnt-1];pos--;}}for( int i = 1;i <= n; i++){if( i > cnt ){cout << -1 << " ";}else cout << f[i] << " ";}cout << endl;
}
signed main()
{int tt; cin >> tt;while(tt--)solve();return 0;
}传送门：Problem - 1864C - Codeforces
题目大意：
思路： 二进制 （ 相同的 d 值不能超过2次 ）
假设数字为 x ，二进制表示为 10001000101000
10001000101000 -> 10001000100000 -> 10001000000000 -> 10000000000000
这个过程 减去的因子只会出现一次
此时同除 2 ，可以将数字化为 1，这个过程，减去的因子只会出现一次
故整个过程减去的因子数量 不超过2
#include<bits/stdc++.h>
using namespace std;
#define int long long
void solve()
{int x; cin >> x;vector<int> a;int temp = x; while( temp ){a.push_back( temp % 2 );temp /= 2;}temp = x; vector<int> ans; ans.push_back(temp); int w = 1;for( int i = 0 ; i < a.size() - 1; i ++){if( a[i] == 1 ){temp -= w; ans.push_back(temp);}w *= 2;}while( w ){w /= 2;if( w )ans.push_back( w );}cout << ans.size() << endl;for( auto e : ans )cout << e << " ";cout << endl;
}
signed main()
{int tt; cin >> tt;while(tt--)solve();return 0;
}传送门：Problem - 1853B - Codeforces
题目大意：
思路：
这个题的范围很有意思
前言知识，斐波那契数列呈爆炸式增长
设序列为 a
这个题的 最小为a[1] = 0 , a[2] = 1，这个时候 当 a[i] <= 2e5 时，只有29项
第30项是 514229，第29项是 317811
有这个代码可以得到：
#include<bits/stdc++.h>
using namespace std;
#define int long long
signed main()
{int a1 = 0 ; int a2 = 1;int a3 = 0; int cnt = 2;while( cnt != 30 ){cnt++;a3 = a1 + a2;a1 = a2; a2 = a3;}cout << a3 << endl;
}所以可以知道 k >= 30 肯定没有答案
故 k < 30，此时就可以暴力枚举即可 a[k] = n ， a[ k - 1] >= ( n + 1 ) / 2
AC代码：
#include<bits/stdc++.h>
using namespace std;
void solve()
{int n , k;cin >> n >> k;if( k >= 30 ){cout << 0 << endl;return;}int ans = 0;for( int i = ( n + 1 ) / 2 ; i <= n ; i++){vector<int> a( k + 1 );a[k] = n; a[k-1] = i;for( int i = k - 2; i >= 1; i--){a[i] = a[i + 2] - a[i + 1];}bool flag = true;for( int i = 1; i < k; i++){if( a[i] < 0 || a[i] > a[i + 1]){flag = false ; break;}}if( flag ) ans++;}cout << ans << endl;
}
signed main()
{int tt; cin >> tt;while(tt--)solve();return 0;
}传送门：https://codeforces.com/problemset/problem/1851/D
题目大意：
思路：
考察 差分
删除前缀和中的一个元素，删除之后，前后两个元素之前的差值 有可能 > n ， < n ，并且差值只会出现一种情况 ( > n 或 < n )
1.构造差分数组
2.寻找差值 > n 或 < n 的情况
3. 1 ~ n 哪些数出现过，差值能否 == 未出现过的数
#include<bits/stdc++.h>
using namespace std;
#define int long long
int temp , x , y;
bool solve()
{int n; cin >> n;vector<int> a( n );for( int i = 1; i < n; i++) cin >> a[i];for( int i = n - 1; i >= 1; i--) a[i] -= a[i-1];bool st[ n + 1] = { 0 };temp = x = y = 0;for( int i = 1; i < n; i++){if( a[i] > n || st[a[i]] ){if( temp )return 0;temp = a[i];}else st[a[i]] = true;}for( int i = 1; i <= n; i++){if( st[i] == 0 ){if( x ) y = i;else x = i;}}return temp == x + y || !y;
}
signed main()
{int tt; cin >> tt;while(tt--)solve() ? cout << "YES" << endl : cout << "NO" << endl;return 0;
}传送门：Problem - 1848B - Codeforces
题目大意：
思路：
我看见这个题的第一思路：是二分答案
但是我始终想不出 check 函数怎么写
但仔细一想，这个题其实靠模拟也可以做出来
AC代码：
代码有注释
#include<bits/stdc++.h>
using namespace std;
#define int long long
void solve()
{int n, k; cin >> n >> k;vector<int> a(n + 1);for (int i = 1; i <= n; i++) cin >> a[i];map<int, vector<int>> mp;for (int i = 1; i <= n; i++) mp[a[i]].push_back(i);int ans = 2e18;for (int i = 1; i <= k; i++){if (mp[i].size() == 0)continue;else{mp[i].push_back(0); mp[i].push_back(n + 1);sort(mp[i].begin(), mp[i].end());// 排序好算距离int mx = -2e18; int cmx = -2e18;// 维护最大值和次大值// 加点，肯定会把最大值变小，故要用次大值for (int j = 0; j < mp[i].size() - 1; j++){int temp = mp[i][j + 1] - mp[i][j] - 1;if (temp >= mx){cmx = mx; mx = temp;}else if (temp > cmx) cmx = temp;}// 如果 mx 为奇数，加点后，距离缩短一半// 如果 mx 为偶数，加点后，距离 -> n / 2 和 n / 2 - 1，此时最大还是 n / 2ans = min(ans, max(cmx, mx / 2));}}cout << ans << endl;
}
signed main()
{int tt; cin >> tt;while (tt--)solve();return 0;
}