首页 > 代码库 > 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;}
View Code

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;    }}
View Code

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;    }}
View Code

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;}
View Code

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,者前面系数即是答案。