A
核心思路
按照题目模拟就好了
// Problem: A. Flip Flop Sum
// Contest: Codeforces - Codeforces Round #848 (Div. 2)
// URL: https://codeforces.com/contest/1778/problem/A
// Memory Limit: 256 MB
// Time Limit: 1000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#define _CRT_SECURE_NO_WARNINGS
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
#define IOS std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define NO {puts("NO") ; return ;}
#define YES {puts("YES") ; return ;}
#define endl "\n"
#define int long long
void solve()
{
int n;
cin>>n;
vector<int> a(n);
for(int i=0;i<n;i++)
cin>>a[i];
int flag=0;
for(int i=0;i<n-1;i++)
{
if(a[i]==-1&&a[i+1]==-1)
{
a[i]=a[i+1]=1 ;
flag=1;
break;
}
}
int sum=0;
if(flag)
{
for(int i=0;i<n;i++)
{
sum+=a[i];
}
cout<<sum<<endl;
}
else
{
int t=0;
for(int i=0;i<n-1;i++)
{
if(a[i]*a[i+1]==-1)
{
t=1;
break;
}
}
if(!t)
{
a[0]=-a[0];
a[1]=-a[1];
}
for(int i=0;i<n;i++)
{
sum+=a[i];
}
cout<<sum<<endl;
}
}
signed main()
{
int T;
cin>>T;
while(T--)
{
solve();
}
}
B
核心思路
老样子先往我们的操作的性质入手，这里有个很关键的点那就是只能操作相邻的元素。所以我们线性扫描下对两种操作取最大值就好了，有个需要注意的点就是特判0这个答案。
// Problem: B. The Forbidden Permutation
// Contest: Codeforces - Codeforces Round #848 (Div. 2)
// URL: https://codeforces.com/contest/1778/problem/B
// Memory Limit: 256 MB
// Time Limit: 2000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#define _CRT_SECURE_NO_WARNINGS
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
#define IOS std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define NO {puts("NO") ; return ;}
#define YES {puts("YES") ; return ;}
#define endl "\n"
#define int long long
int pos[100000];
void solve()
{
int n,m,d;
cin>>n>>m>>d;
vector<int> a(n);
vector<int> p(m);
for(int i=0;i<n;i++)
{
cin>>a[i];
pos[a[i]]=i;
}
for(int i=0;i<m;i++)
cin>>p[i];
for(int i=1;i<m;i++)
{
if(pos[p[i]]<pos[p[i-1]]||pos[p[i]]-pos[p[i-1]]>d)
{
cout<<0<<endl;
return ;
}
}
int ans=0x3f3f3f3f;
for(int i=1;i<m;i++)
{
ans=min(abs(pos[p[i]]-pos[p[i-1]]),ans);
if(n-1>d)
{
ans=min(ans,d-abs(pos[p[i]]-pos[p[i-1]])+1);
}
}
cout<<ans<<endl;
}
signed main()
{
int T;
cin>>T;
while(T--)
{
solve();
}
}
C
核心思路
首先我们其实可以分析出来这个方案的数量是:\(C_{10}^{5}=200\).所以我们可以暴力搜索出来所有的方案数。我们暴力搜索的次数最多也就是\(2^10=1024\)。
下面讲下主要的做法吧：先对我们的字符串a进行去重，因为我们一但进行操作就是对所有的相同的字符操作。所以去重之后方便我们使用mark数组对对应的字符进行标记，同时这也是一种冗余性剪枝吧。
然后就是dfs枚举进行相应操作和不进行相应操作所得到的方案，再就是枚举完毕后计算相应的答案，这里我们可以推导出来一个小公式：\(假如匹配的长度是n，那么当前匹配的长度就是n*(n+1)/2\).
// Problem: C. Flexible String
// Contest: Codeforces - Codeforces Round #848 (Div. 2)
// URL: https://codeforces.com/contest/1778/problem/C
// Memory Limit: 256 MB
// Time Limit: 2000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#define _CRT_SECURE_NO_WARNINGS
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
#define IOS std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define NO {puts("NO") ; return ;}
#define YES {puts("YES") ; return ;}
#define endl "\n"
#define int long long
int n,k;
string char_list;
string a,b;
int mark[26];
int ans;
int count_match_pair()
{
int tot_pair=0;
int match_count=0;
for(int i=0;i<a.size();i++)
{
if(a[i]==b[i]||mark[a[i]-'a'])
match_count++;
else
{
tot_pair+=match_count*(match_count+1)/2;
match_count=0;
}
}
tot_pair+=match_count*(match_count+1)/2;
return tot_pair;
}
void dfs(int pos,int cnt)
{
if(pos==char_list.size())
{
if(cnt==k)
ans=max(ans,count_match_pair());
return ;
}
dfs(pos+1,cnt);
mark[char_list[pos]-'a']=1;
dfs(pos+1,cnt+1);
mark[char_list[pos]-'a']=0;
}
void solve()
{
cin>>n>>k;
cin>>a>>b;
unordered_set<char> unq;//去重map
for(auto &ch:a)
unq.insert(ch);
char_list.clear();
for(auto &x:unq)
char_list.push_back(x);
k = min(k, (int)unq.size());
// cout<<char_list<<endl;
ans=0;
dfs(0,0);
cout<<ans<<endl;
}
signed main()
{
int T;
cin>>T;
while(T--)
{
solve();
}
}
D
核心思路
答案说是期望线性性，但是我感觉完全可以当作期望dp来进行理解。
集合定义
\(f[i]定义为从i-1出发第一次到i的期望的操作次数\)
集合划分
\(f[i+1]=(n-i)/n+i/n*(f[i]+f[i+1]+1)\)
为什么会是这样呢，首先我们可以知道\(f[i+1]肯定是由f[i]转移来的，因为我们的状态就是这么定义的\)。那么我们可以有两种选择：
- 从没有匹配的n-i个位置翻转，概率是\(\frac{n-i}{i},操作次数是1，所以就是\frac{n-i}{i}*1\)
- 从匹配了的位置翻转，那么我们肯定要操作\(f[i]+f[i+1]才可以，还要加上我们翻转了的这一个操作\)。
然后答案就是已经匹配了的位置加上对应的操作数，一定要从集合定义出发，我们这f[i]只是对应一步的操作，又因为我们的期望是线性的所以可以相加。
// Problem: D. Flexible String Revisit
// Contest: Codeforces - Codeforces Round #848 (Div. 2)
// URL: https://codeforces.com/contest/1778/problem/D
// Memory Limit: 256 MB
// Time Limit: 2000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include <bits/stdc++.h>
#define debug_(x) cerr << #x << " = " << x << ' '
#define debug(x) cerr << #x << " = " << x << '\n'
using namespace std;
typedef long long ll;
constexpr int P = 998244353;
using i64 = long long;
// assume -P <= x < 2P
int norm(int x) {
if (x < 0) {
x += P;
}
if (x >= P) {
x -= P;
}
return x;
}
template<class T>
T power(T a, int b) {
T res = 1;
for (; b; b /= 2, a *= a) {
if (b % 2) {
res *= a;
}
}
return res;
}
struct Z {
int x;
Z(int x = 0) : x(norm(x)) {}
int val() const {
return x;
}
Z operator-() const {
return Z(norm(P - x));
}
Z inv() const {
// assert(x != 0);
return power(*this, P - 2);
}
Z &operator*=(const Z &rhs) {
x = i64(x) * rhs.x % P;
return *this;
}
Z &operator+=(const Z &rhs) {
x = norm(x + rhs.x);
return *this;
}
Z &operator-=(const Z &rhs) {
x = norm(x - rhs.x);
return *this;
}
Z &operator/=(const Z &rhs) {
return *this *= rhs.inv();
}
friend Z operator*(const Z &lhs, const Z &rhs) {
Z res = lhs;
res *= rhs;
return res;
}
friend Z operator+(const Z &lhs, const Z &rhs) {
Z res = lhs;
res += rhs;
return res;
}
friend Z operator-(const Z &lhs, const Z &rhs) {
Z res = lhs;
res -= rhs;
return res;
}
friend Z operator/(const Z &lhs, const Z &rhs) {
Z res = lhs;
res /= rhs;
return res;
}
};
void solve()
{
int n;
cin>>n;
vector<Z> f(n+1);
f[1]=1;
for(int i=1;i<n;i++)//不需要等于。
f[i+1]=1+(f[i]+1)*i/Z(n-i);
string a,b;
cin>>a>>b;
int cnt=0;
for(int i=0;i<n;i++)
cnt+=a[i]==b[i];
Z ans=0;
for(int i=cnt+1;i<=n;i++)
ans+=f[i];
cout<<ans.val()<<'\n';
}
signed main()
{
// IOS;
int T;
cin>>T;
while(T--)
{
solve();
}
return 0;
}