Codeforces Round #411 (Div. 2) 题解

比赛链接:http://codeforces.com/contest/805

A Fake NP

题意

给出一个范围[l,r],对于所有的从l到r的数的因子数中出现最多的因子数

题解

可以发现除了范围内只有一个数,其他情况2都是出现次数最多的因子数

代码

1
2
3
4
5
6
7
8
9
10
11
void solve()
{
int l,r;
while(cin>>l>>r)
{
if(l==r)
cout<<l<<endl;
else
cout<<"2"<<endl;
}
}

B 3-palindrome

题意

要求你创建一个仅含有a、b、c三个字符的长度为n的序列,要求序列中不含有长度为3的回文串,,并且要求含有c字符的数目尽可能少。

题解

“aabb”这样的字符创不断循环就不会含有长度为3的回文串

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
olve()
{
string st="aabb";
int n;
while(cin>>n)
{
int d=n/4;
n%=4;
for(int i=0;i<d;i++)
cout<<st;
for(int i=0;i<n;i++)
cout<<st[i];
cout<<endl;
}
}

C Find Amir

题意

给出编号为1到n的n个点,规定两点(i,j)之间的权值为(i+j)mod(n+1),求将所有点连接起来的最小代价

题解

  • 最小生成树问题,用贪心思想,发现将第1小的点和第1大的点配对,第2小的点和第2大的点配对,。。。(以此类推可以配对n/2条边),这样的每次配对的代价都是0
  • 这样两两结对以后(奇数情况下会多出一个点),再将第i大点和第i+1小的点配对,这种配对的每次代价为1。这样就可以生成一棵最小生成树,总体的代价就是后面的配对产生的代价:偶数时候为(n/2-1),奇数的时候是n/2

代码

1
2
3
4
5
6
7
8
9
10
11
void solve()
{
int n;
while(cin>>n)
{
if(n%2)
cout<<n/2<<endl;
else
cout<<n/2-1<<endl;
}
}

D Minimum number of steps

题意

给出一个只含有字符a、b的字符串,规定一次操作为将原字符串的一个’ab’子串转换成’bba’,求转换成最终无法转换的状态要进行的操作次数(对10^9+7取模)

题解

  • 操作完的最终状态应该是所有的字符a都换到了字符串的最后,同时每次操作我们可以看成a向后移动一位的过程,这样的话我们可以计算每个字符a到字符串最后全是a的部分的距离来对于这个a要进行的操作次数。
  • 但是每次a向后移动一位对前面的a是有影响的————每向后移动一位对于前面的a相当于增加了一个b,也就是增加了前面的a到字符串最后的距离。这样我们可以从后往前进行考虑来统一这种影响。
  • 从后往前扫描,用tmp记录中间b的个数,遇到a时累加到ans中同时对tmp加倍(相当于已经将当前的a转移到了最后,这样对于前面的a来说就是增加了tmp个b)。最后的答案就是所有操作的代价ans

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
void solve()
{
string a;
while(cin>>a)
{
ll tmp=0,ans=0,num=0;
for(int i=a.size()-1;i>=0;i--)
{
if(a[i]=='a')
{
ans=(ans+tmp)%MOD;
tmp=(2*tmp)%MOD;
}
else
tmp++;
}
cout<<ans<<endl;
}
}

小结

  • 看清题意再敲代码,B题就是因为误以为是长度>=3的回文子串而导致错了两发
  • 提高debug水平,D题思路一直对但是因为else分支里面的一个错误导致迟迟没有AC