补题篇--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;
}