首页 > 代码库 > Codeforces Round #421(div 2)

Codeforces Round #421(div 2)

A

= =

B

题意:

在一个正n边形中,画一个三角形,找这个三角形里的一个角,使得这个角最接近给定的angle

分析:

画画图会发现,相邻三个点构成的三角形的最小角是所有可能角中的最小角

然后发现其它角都是这个最小角的整数倍

所以只要枚举整数倍就行了

C

题意:

初始有一串长度为a的序列,是26个字母的前a个(比如a=5时候,初始就是abcde)

我和对手轮流操作,我每次在后面加上b个英文字母,对手每次在后面加上a个英文字母

我的b个英文字母任意选择

对手的a个英文字母有套路:

  对手会观察当前字符串的后a个,从‘a’~‘z’依次挑出a个英文字母不在后缀中出现,把这a个字符接在后面

现在问字符串的[L,R]中,最少可能有多少个不同的字母

分析:

这题标程翻车了……所以就unrated了,现在也不知道正解……

标程的做法就是我的策略为:

将字符串最后一个字母抄b遍……

然后周期是2(a+b),来进行判断

D

题意:

有长度为n(n<=1e6)的数列a,它是n的一个全排列

现在你可以将这个数列a循环移动,求MIN(Σ|a[i]-i|)

分析:

数组的移动可以看成是下标的移动

O(n)枚举下标为1的地方,然后再根据上一次的结果快速转移到这次的结果

先对于初始状态,求出b[i]=a[i]-i (有正负)

假设我们枚举下标为1的位置是i

那么实际上,每次i左边的下标都集体加1,所以左边的b[j]相当于集体减1;每次i右边的下标都集体加1,所以右边的b[j]相当于集体加1

我们考察对结果的贡献:原本>0的数,对结果负贡献;原本<=0的数,对结果正贡献

所以这完全可以用一个线段树来进行修改和查询(查询就是查一段区间有多少个<=0的数)

时间复杂度O(nlogn)

但是这题n=1e6,而且线段树常数比较大,实际上可以有O(n)的做法

我们考虑不用线段树来求解

以考虑左边为例:

  我们只关心i的左边有多少个数>0,有多少个数=0,有多少个数<0,这完全可以用三个变量来记录

  但关键是有一个全体-1的操作

  我们其实可以不考虑这个修改,而去重新定义当前时刻的“0”

  比如全体-1操作进行了2次,那么当前时刻的"0"就是原始的2

  也就是说询问变成了有多少个数>a,有多少个数=a,有多少个数<a

  从a-1转移到a的过程中,只需要维护三个变量的值就行了

  具体的:原来的负数还是负数,原来的"0"现在变成了负数,原来的正数少了原来的“0”这么多个

  要完成这个操作就需要知道一些数中,有多少个数的值是a,这只要开个桶就可以了

综上所述,O(n)枚举下标为1的位置,左右两边用2个桶维护,O(1)时间转移答案

细节:当我们将第i位从左边桶中抽离,放到右边桶的时候,并不是把a[i]-1放进右边的桶,因为此时右边的桶“0”的基准变了,假设当前右边桶“0”的基准是m,那么我们应该把a[i]-1+m放进右边桶

代码:

技术分享
 1 #include<bits/stdc++.h> 2 using namespace std; 3 const int maxn=1e6; 4 int a[maxn+50],b[maxn+50]; 5 int x[maxn*2+50],y[maxn*2+50]; 6 int numx[3],numy[3]; 7 int n; 8 long long ans,s; 9 int ansi;10 int getnum(int x,int zero)11 {12     if(x==zero) return 0;13     if(x>zero) return 1;14     return 2;15 }16 int main()17 {18 19     scanf("%d",&n);20     for(int i=1;i<=n;++i) scanf("%d",&a[i]);21     for(int i=1;i<=n;++i) b[i]=a[i]-i,++x[b[i]+n],ans+=abs(b[i]);22     ansi=0;23     s=ans;24     for(int i=1;i<=n;++i) ++numx[getnum(b[i],0)];25     for(int i=n;i>=2;--i)26     {27         --x[b[i]+n];28         --numx[getnum(b[i],n-i)];29         numx[2]+=numx[0];30         numx[0]=x[n-i+1+n];31         numx[1]-=x[n-i+1+n];32         s+=numx[2];33         s-=numx[0]+numx[1];34 35         s-=abs(a[i]-n);36         s+=abs(1-a[i]);37 38         numy[2]+=numy[0];39         numy[0]=y[n-i+n];40         numy[1]-=y[n-i+n];41         s+=numy[2];42         s-=numy[0]+numy[1];43         ++y[a[i]-1+n-i+n];44         ++numy[getnum(a[i]-1+n-i,n-i)];45 46         if(s<ans)47         {48             ans=s;49             ansi=n-i+1;50         }51     }52     printf("%lld %d",ans,ansi);53     return 0;54 }
View Code

Codeforces Round #421(div 2)