Educational Codeforces Round 170 (Rated for Div. 2)

写在前面

这场比赛打的巨烂······，前几周没有认真学算法，这周刷了几道题就直接打了这场比赛，结果就是大败而归，算法的学习还得是日积月累，隔好几天不敲，不仅手生疏了，连原来的知识储备都忘的一干二净了，在比赛的时候我感觉我脑子空空的，啥都忘记了QWQ。

A. Two Screens

思路

签到题，找出S字符串和T字符串相同的前缀子串，分别计算S、T字符串除去相同前缀子串，剩下子串的个数

code

void solve(){string s,t;cin >> s >> t;int k=-1;for(int i=0;i<s.size() && i<t.size();++i){if(s[i]!=t[i]) break;else k=i;} if(k==-1){cout << t.size()+s.size() << endl;return ;}k++;cout << k+1+(s.size()-k)+(t.size()-k) << endl;return ;
}

B. Binomial Coefficients, Kind Of

思路

考点：打表找规律

将组合数公式： $C_n^m=C_{n-1}^m+C_{n-1}^{m-1}$ 更改为 $C_n^m=C_n^{m-1}+C_{n-1}^{m-1}$
简单的打个表，不难发现 $C_n^k$ 与n无关，只与k有关，且满足 $2^k$ 的关系
因此我们只需要用一个快速幂即可

code

int a[N],b[N];
int fpow(int a,int b){int ans=1;while(b){if(b & 1) ans=ans*a%mod;b>>=1;a=a*a%mod;}return ans;
}
void solve(){int n;cin >> n;for(int i=1;i<=n;++i) cin >> a[i];for(int i=1;i<=n;++i) cin >> b[i];for(int i=1;i<=n;++i){cout << fpow(2,b[i]) << endl;}return ;
}

C. New Game

思路

考点：滑动窗口

首先题目中 $a_i$ 与当前位置 $i$ 无关，那么我们可以用桶的思维将 $a_i$ 的值放入一个数组中
对于每个 $a_i$ ，我们都需要判断 $a_i$ 到 $a_{i+k}$ 的个数
我们不妨用滑动窗口的思想，先将数组进行排序，从左到右依次遍历
当一个数进入窗口时，我们需要进行判断：

• 如果当前数减窗口末尾的数的差值大于1，那么更新窗口，窗口只包含当前数
• 反之，我们就让这个数进入窗口，这时需要判断窗口里面的个数是否超过k，如果超过需要将窗口开头的元素排出去

最后找出窗口移动过程中最大牌数即可

code

void solve(){int n,s;cin >> n >> s;map<int,int> m;for(int i=1;i<=n;++i){int x;cin >> x;m[x]++;}int ans=0,sum=0;int k=0,g=0;for(auto i : m){if(sum==0){sum+=i.se;k=i.fi;g=i.fi;}else{if(i.fi-k==1){sum+=i.se;if(i.fi-g==s){sum-=m[g];g++;}} else{sum=i.se;g=i.fi;}k=i.fi;}ans=max(ans,sum);}cout << ans << endl;return ;
}