文章目录
- 写在前面
- A. Two Screens
- 思路
- code
- B. Binomial Coefficients, Kind Of
- 思路
- code
- C. New Game
- 思路
- code
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^m_n=C^m_{n-1}+C^{m-1}_{n-1} Cnm=Cn−1m+Cn−1m−1 更改为 C n m = C n m − 1 + C n − 1 m − 1 C^m_n=C^{m-1}_n+C^{m-1}_{n-1} Cnm=Cnm−1+Cn−1m−1
简单的打个表,不难发现 C n k C_n^k Cnk 与n无关,只与k有关,且满足 2 k 2^k 2k 的关系
因此我们只需要用一个快速幂即可
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 a_i ai 与当前位置 i i i 无关,那么我们可以用桶的思维将 a i a_i ai 的值放入一个数组中
对于每个 a i a_i ai ,我们都需要判断 a i a_i ai 到 a i + k a_{i+k} ai+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 ;
}