首页 > 代码库 > Codeforces Round #258 (Div. 2)
Codeforces Round #258 (Div. 2)
A - Game With Sticks
题目的意思:
n个水平条,m个竖直条,组成网格,每次删除交点所在的行和列,两个人轮流删除,直到最后没有交点为止,最后不能再删除的人将输掉
解题思路:
每次删除交点所在的行和列,则剩下n-1行和m-1列,直到行或列被删完为止,最多删除的次数为min(n,m),删除min(n,m)后剩余的都是行或者列(注意行与行,列与列之间不可能有交点)。只需要判断min(n,m)的奇偶性。
#include <iostream>#include <vector>#include <algorithm>using namespace std;int main(){ int n,m; cin >> n >> m; if(min(n,m)%2) cout<<"Akshat"<<endl; else cout<<"Malvika"<<endl;}
B - Sort the Array
题目的意思:
给一个含有n个不同数的数组,通过反转数组的一个片段,该数组变成递增排序,问该数组是不是满足要求
解题思路:
可想而知,这样的数组基本有序的,而且中间最多只有一个片段是单调递减的,这样的数组看起来像这样先单调递增,再单调递减,在单调递增
假设找到单调递减的片段(程序很简单实现),该片段的起始索引为startIdx,结束索引为endIdx,如果数组中存在多个这样的片段,说明要将多个部分反转,不满足条件,输出“no”,所以增加一个计数器cnt,记录这样的片段个数,如果cnt>1肯定不能满足条件。
如果只有一个这样的片段,反转后a[endIdx]在startIdx处,要判断a[startIdx-1]与a[endIdx]大小,如果a[endIdx]>a[startIdx-1],说明反转后左边的可以保证单调递增,现在来考虑右边的a[endIdx+1],反转后a[startIdx]位于a[endIdx],在这个地方要判断endIdx+1是不是存在,如果a[endIdx+1]>a[startIdx],则反转后右边也是单调递增的。
时间复杂度O(n),注意下面代码中左右各增加了一个哨兵,可以避免边界的判断,可以继续在下面程序优化,将空间的时间复杂度优化为O(1)
#include <iostream>#include <vector>#include <algorithm>#define MAX 1000000000+1using namespace std;int main(){ int n; cin >> n ; vector<int> a(n+2,0); a[0]= 0;a[n+1] = MAX; int startIdx =1,endIdx = 1,cnt = 0; bool flag = false; for(int i = 1; i <=n; ++ i){ cin >> a[i]; if(a[i] < a[i-1]){ if(!flag){ startIdx = i-1;flag = true;cnt++;} endIdx =i; }else{ if(flag) flag = false; } } if(cnt > 1) cout<<"no"<<endl; else{ if(a[endIdx] > a[startIdx-1] && a[endIdx+1] > a[startIdx]){ cout<<"yes"<<endl; cout<<startIdx<<" "<<endIdx<<endl; }else cout<<"no"<<endl; }}
C - Predict Outcome of the Game
题目的意思:
三个队进行n场比赛,已经比赛了k场,第一队赢得次数与第二队赢得次数的绝对值之差是d1,第二队与第三队赢得次数绝对值之差是d2,问是否存在n场比赛后3个队都没有赢,即三个队赢得次数相等,即每个队赢的次数是n/3,(n一定要能被3整除,否则不可能每个队赢的次数相等)
解题思路:
设在已经比赛的k场比赛中,第一队赢的次数为a,第二队赢的次数为b,第三队赢的次数是c,则a+b+c=k
证明a+b+c=k
设第一队与第二队,第一队赢a1次(输了b1次),第二队赢b1次(输了a1次),则总共比赛了a1+b1次
设第二队与第三队,第二队赢了b2次(输了c1次),第三队赢了c1次(输了b2次),则总共比赛了b2+c1次
设第三队与第一队,第三队赢了c2次(输了a2次),第一队赢了a2次(输了c2次),则总共比赛了c2+a2次
第一队赢的次数a1+a2,第二队赢的次数b1+b2,第三队赢的次数c1+c2
则 a1+b1+b2+c1+c2+a2=k => a+b+c=k
根据题意
|a-b|=d1
|b-c|=d2
现在开始解方程
(1)当a>=b时 a = d1+b, c = k-a-b=k-d1-2b
|b-c|=|b-k+d1+2b|=|3b-k+d1|=d2
当3b-k+d1>=0时
3b = d2-d1+k
要满足的条件是d2-d1+k要能整除3,且a>=0 b>=0 c>=0,还要满足a<=n/3 b<=n/3 c<=n/3 (因为每个队最多赢的次数是n/3)
如果条件都满足,则存在
当3b-k+d1< 0时
3b=k-d1-d2
要满足的条件是k-d1-d2要能整除3,且a>=0 b>=0 c>=0,还要满足a<=n/3 b<=n/3 c<=n/3 (因为每个队最多赢的次数是n/3)
如果条件都满足,则存在
(2)当a < b时 a=b-d1, c = k-a-b=k+d1-2*b
|b-c|=|b-k-d1+2*b|=|3b-k-d1|=d2
当3b-k-d1>=0时
3b=k+d2+d1
要满足的条件是d2+d1+k要能整除3,且a>=0 b>=0 c>=0,还要满足a<=n/3 b<=n/3 c<=n/3 (因为每个队最多赢的次数是n/3)
如果条件都满足,则存在
当3b-k-d1< 0时
3b=k+d1-d2
要满足的条件是k+d1-d2要能整除3,且a>=0 b>=0 c>=0,还要满足a<=n/3 b<=n/3 c<=n/3 (因为每个队最多赢的次数是n/3)
如果条件都满足,则存在
不用考虑剩余的n-k场比赛,因为前面k场比赛中,三个队赢的次数已经确定,剩下的n-k场比赛,第一队赢的肯定是n/3-a,第二队赢的是n/3-b,第三队赢的是n/3-c
#include <iostream>#include <vector>#include <algorithm>#include <string>#define ll long longusing namespace std;int main(){ int t; cin >> t; while(t-->0){ ll n,k,d1,d2; cin >> n >> k >> d1 >> d2; if(n%3){cout<<"no"<<endl;continue;} ll a = 0,b = 0, c =0; int flag = 0; if((d2-d1+k)>=0 && ((d2-d1+k)%3 == 0)){ b = (d2-d1+k)/3; c = k-d1-2*b; a = d1+b; if(c>=0 && a>=0 && a-b>=0 && a<=n/3 && b<=n/3 && c<=n/3){ flag|=1; } } if((k-d1-d2)>=0 && ((k-d1-d2)%3 ==0)){ b = (k-d1-d2)/3; c = k-d1-2*b; a = d1+b; if(c>=0 && a>=0 && a-b>=0 && a<=n/3 && b<=n/3 && c<=n/3){ flag|=1; } } if((k+d1+d2)%3==0){ b=(k+d1+d2)/3; c = k+d1-2*b; a = b-d1; if(c>=0&& a>=0 && b>=a && a<=n/3 && b<=n/3 && c<=n/3 ){ flag|=1; } } if((k+d1-d2)>=0 && (k+d1-d2)%3 ==0){ b = (k+d1-d2)/3; c = k+d1-2*b; a = b-d1; if(c>=0&& a>=0 && b>=a && a<=n/3 && b<=n/3 && c<=n/3){ flag|=1; } } if(flag == 0) cout<<"no"<<endl; else cout<<"yes"<<endl; }}
D - Count Good Substrings
题目意思:
goog string:字符串中连续相同的字符用一个字符替换后,形成回文串的字符串。
给出一个字符串,该字符串的字串中,长度为奇数的good string有多少个,长度为偶数的good string有多少个。
解题思路:
因为字符串只有a和b组成,只要是头尾相同的字串都是good string。
设头尾相同的字符串都是a,str="a.....a"由于相同的字符串都是用一个字符串替换,所以不可能存在相邻的字符相同,故将连续相同的字符替换后,就形成了a和b交替排列。故str变成了"ababababa....baba",这种类型的字符显然是回文串。所以要使子串为good string,则头尾应该是相同的。
现在问题是如果头尾相同的字串,如何判断子串的长度?这里要利用字符的索引的奇偶性
假设子串str="a...a",开头a在输入字符串中的索引为i,结尾a在输入字符串中的索引为j,则str的长度为
如果i和j都为偶数或者奇数,则str的长度是j-i+1为奇数,(奇数-奇数=偶数,偶数-偶数=偶数,偶数+奇数=奇数)
如果i和j一奇一偶,则str的长度j-i+1为偶数,(奇数-偶数=奇数,偶数-奇数=奇数,奇数+奇数=偶数)
所以只需要统计a,b在奇数位置和在偶数位置的个数
长度为偶数的good string来源,开头a的索引和结尾a的索引一奇一偶的子串,开头b的索引和结尾b的索引一奇一偶,
长度为奇数的good string来源,开头a的索引和结尾a的索引奇偶性相同,开头b索引和结尾b的索引的奇偶性相同
#include <iostream>#include <string>#define C(num) ((num)*(num-1)/2)using namespace std;int main(){ string s; cin >> s; long long cnt_even[2]={0},cnt_odd[2]={0}; for(int i = 0 ; i < s.length(); ++ i){ int index = s[i]-‘a‘; if(i&1) cnt_odd[index]++; else cnt_even[index]++; } cout<<cnt_even[0]*cnt_odd[0]+cnt_even[1]*cnt_odd[1]<<" "; cout<<C(cnt_even[0])+C(cnt_even[1])+C(cnt_odd[0])+C(cnt_odd[1])+s.length()<<endl;}
E - Devu and Flowers
题目的意思:
有n个花坛,每个花坛有f[i]支花。同一个花坛的花颜色相同,不同花坛的花颜色不同,问取s朵花一共有多少种取法
解题思路:
用母函数解决过硬币问题的,这题看起来应该很熟悉,就是通过母函数求组合数,不同之处,此题的数据量比较大,要经过处理。
得到的母函数为(1 + x + x^2 + x^3 + + ..x^f1) ...... (1 + x + x^2 + x^3 + + ..x^fn).
最后得到的指数为s的前面的系数就是答案,即x^s前面的系数是答案,现在关键问题是如何求x^s的系数
由于(1+x+x^2+x^3....+x^f1)=(1-x(f1+1))/(1-x)
故上面的母函数转换为(1-x(f1+1))/(1-x).....(1-x(fn+1))/(1-x)=(1-x(f1+1))....(1-x(fn+1))*(1-x)-n
现在考虑前面(1-x(f1+1))....(1-x(fn+1)),由于n的值不大,最大是20,故x的指数最多有2n种不同的值,220近似(103)2=106个值
可以浪费点空间算出这些值,注意大于s的指数直接抛弃
由于题目结果要取模,可以在算组合数时根据Lucas定理——组合数求模 去计算,在计算组合数时还要用到求逆元运算(辗转相除法或者快速幂算法)
最后求出 (1-x)-n的指数及相关系数,如果其指数与前面部分的指数和是s,者前面系数即是答案。