Educational Codeforces Round 170 (Rated for Div. 2)（A~E题解）

本场也算是对我努力的一个reward吧，也是非常nice啊，话不多说，先写题解，写完直接休息

A. Two Screens

思路：我们先去想其最多需要多少次，也就是两个串长度之和，然后在哪里有优化呢？就是说两个串之间有可能有相等的前缀，可以将前缀直接拓印过来，将相同长度k的的前缀串复制过来，将操作化简为1，直接用sum-k+1即可，当然了，有可能有相同的部分为0，如果为0，直接输出两个串长度之和

#include<bits/stdc++.h>
using namespace std;
#define int long longint q;
string s,t;
void solve()
{cin>>s>>t;int cnt=0;int sum=s.size()+t.size();for(int i=0;i<min(s.size(),t.size());i++){if(s[i]==t[i])cnt++;elsebreak;}if(cnt==0)cout<<sum<<"\n";elsecout<<sum-cnt+1<<"\n";
}
signed main()
{cin>>q;while(q--)solve();return 0;
}

B. Binomial Coefficients, Kind Of

思路：看题就是说求错误的最终结果，我们每次取的都是左边一个+左上一个

我们手玩一下就发现了规律，第k列的值就是2的k次方，直接用快速幂

#include<bits/stdc++.h>  
using namespace std;  
#define int long long  int t;  
const int mod = 1e9 + 7;  
int n[100005];  
int k[100005];  // 快速幂公式  
int fast(int a, int b)   
{  long long result = 1;  long long base = a % mod;  // 计算base时取mod，防止溢出  while (b > 0)   {  if (b % 2 == 1)   {  result = (result * base) % mod;  }  base = (base * base) % mod;  b /= 2;  }  return result;  
}  signed main()  
{  cin >> t;  for (int i = 1; i <= t; i++)  {  cin >> n[i];  }  for (int i = 1; i <= t; i++)  {  cin >> k[i];  }  for (int i = 1; i <= t; i++)  {  cout << fast(2, k[i]) << "\n";  }  return 0;  
}

 C. New Game

思路：我们首先需要用一个map去统计每个数出现的次数，然后快排一下，去重，跑一遍单调队列，我们在单调队列中去处理结果

我们用sum去表示过程中的值，ans表示最终的最大值

如果队列不为空并且当前要插入的元素和队尾元素差值不是1，那么去更新最大值，然后将sum变为0 

如果队列不为空，但是插入的值和第一个元素的值差值大于等于k，说明插入的元素要多于k了，因此我们需要将队首元素弹出，并且sum-队首元素的次数

#include<bits/stdc++.h>
using namespace std;int t;
int n, k;
int a[200005];
map<int, int> mp;
struct node
{int x;int cnt;
};
deque<node> que;
void solve()
{cin >> n >> k;mp.clear();for(int i = 1; i <= n; i++){cin >> a[i];mp[a[i]]++;}sort(a + 1, a + 1 + n);int len = unique(a + 1, a + 1 + n) - (a + 1);vector<node> q(len + 1);for(int i = 1; i <= len; i++){q[i].x = a[i];q[i].cnt = mp[a[i]];}int sum = 0;int ans = 0;for(int i = 1; i <= len; i++){if (!que.empty() && q[i].x - 1 != que.back().x){ans = max(ans, sum);sum = 0;while (!que.empty()){que.pop_back();}}while (!que.empty() && que.front().x<=q[i].x-k){ans = max(ans, sum);sum -= que.front().cnt;que.pop_front();}que.push_back(q[i]);sum += q[i].cnt;ans = max(ans, sum);}cout << ans << "\n";while (!que.empty()){que.pop_back();}
}signed main()
{ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);cin >> t;while (t--)solve();return 0;
}

D. Attribute Checks

思路：我们只需要去枚举每个0的位置，然后用dp[i]去表示前面加了i次智力的最大值，如果前面有cnt个0，那么就是加了cnt-i次力量，然后去统计每次属性之后的最值

#include<bits/stdc++.h>
using namespace std;
#define int long long
int t;
int n,m;
int a[2000005];
int dp[2000005];
int zhi[2000005];
int wu[2000005];
void solve()
{cin>>n>>m;for(int i=1;i<=n;i++){cin>>a[i];}int cnt=0;for(int i=1;i<=n;i++){if(a[i]>0){zhi[a[i]]++;}if(a[i]<0){wu[-a[i]]++;}if((a[i]==0&&cnt<2*m)||i==n)  {  for (int j=1;j<=cnt;j++)  {zhi[j]+=zhi[j-1];wu[j]+=wu[j-1];  }for (int j=0;j<=cnt;j++)  {dp[j]+=zhi[j]+wu[cnt-j];}for (int j=cnt+1;j>0;j--)  {dp[j] = max(dp[j],dp[j-1]);  }cnt++;for (int j=1;j<=cnt;j++)  {zhi[j]=0;wu[j]=0;  }}  }int ans=0;for(int i=1;i<=cnt;i++){ans=max(ans,dp[i]);} cout<<ans<<"\n";return;
}
signed main()
{t=1;while(t--)solve();return 0;
}

E. Card Game

等白天来更新思路，太困了，不想码字了 

#include<bits/stdc++.h>  
using namespace std;  
#define int long long  
const int MAX = 1007, MOD = 998244353;  int dp[1007][1007];    
int fac[1007];        
int inv[1007];         int fastpow(int a, int b, int mod)   
{  int res = 1;  while (b)   {  if (b & 1) res = res * a % mod;a = a * a % mod; b >>= 1;}  return res;  
}  int calc(int n, int cnt)   
{  return (fac[2 * n - cnt] * inv[n - cnt] % MOD * inv[n] % MOD - fac[2 * n - cnt] * inv[n - cnt - 1] % MOD * inv[n + 1] % MOD + MOD) % MOD;  
}  void solve()   
{  int n, m;  cin >> n >> m;fac[0] = 1;  for (int i = 1; i < MAX; i++)  fac[i] = fac[i - 1] * i % MOD;  inv[MAX - 1] = fastpow(fac[MAX - 1], MOD - 2, MOD);  for (int i = MAX - 2; i >= 0; i--)  inv[i] = inv[i + 1] * (i + 1) % MOD;  for (int i = m; i >= 0; i -= 2)   {  dp[1][i] = calc((m + i) / 2, i);  }  for (int i = 2; i <= n; i++)   {  for (int j = 0; j <= m; j++)   {  for (int k = 0; k <= j; k++)   {  if ((j - k + m) % 2 == 0)  dp[i][k] = (dp[i][k] + dp[i - 1][j] * calc((j - k + m) / 2, j - k) % MOD) % MOD;  }  }  }  cout << dp[n][0] << '\n';  
}  signed main()   
{  ios_base::sync_with_stdio(false);  cin.tie(0);  cout.tie(0);  solve(); return 0;  
}