昨晚的模拟赛很好啊
T1:Super GCD
1 #include<cstdio> 2 #include<cstring> 3 #include<iostream> 4 #include<algorithm> 5 #include<cmath> 6 using namespace std; 7 struct bignum{ 8 int a[205],len; 9 bignum(){ 10 memset(a,0,sizeof a); 11 len=0; 12 } 13 bignum(int x){ 14 memset(a,0,sizeof a);len=0; 15 while(x){ 16 a[++len]=x%10; 17 x/=10; 18 } 19 } 20 void div(){ 21 for(int i=len;i;i--){ 22 if((i>1)&&(a[i]&1))a[i-1]+=10; 23 a[i]>>=1; 24 } 25 while(len>1&&!a[len])len--; 26 } 27 bignum operator - (bignum b){ 28 bignum c; 29 c.len=max(len,b.len); 30 for(int i=1;i<=c.len;i++){ 31 c.a[i]+=a[i]-b.a[i]; 32 if(c.a[i]<0){ 33 c.a[i]+=10; 34 a[i+1]--; 35 } 36 } 37 while(c.a[c.len+1])c.len++; 38 while(c.len>1&&!c.a[c.len])c.len--; 39 return c; 40 } 41 bool operator < (const bignum & b)const{ 42 if(b.len>len)return 1; 43 for(int i=len;i;i--){ 44 if(b.a[i]>a[i])return 1; 45 if(b.a[i]<a[i])return 0; 46 } 47 return 0; 48 } 49 }A,B,C,tmpl,tmpr,tmpm,one; 50 int T,la,lb; 51 char sa[205],sb[205]; 52 int main(){ 53 scanf("%d",&T); 54 one=1; 55 while(T--){ 56 scanf("%s%s",sa+1,sb+1); 57 la=strlen(sa+1);lb=strlen(sb+1); 58 memset(A.a,0,sizeof A.a); 59 memset(B.a,0,sizeof B.a); 60 A.len=la;B.len=lb; 61 for(int i=1;i<=la;i++)A.a[la-i+1]=sa[i]-'0'; 62 for(int i=1;i<=lb;i++)B.a[lb-i+1]=sb[i]-'0'; 63 if(A.a[1]%2==0&&B.a[1]%2==0){puts("No");continue;} 64 while(A.a[1]%2==0)A.div(); 65 while(B.a[1]%2==0)B.div(); 66 while(1){ 67 if(A<B){C=A;A=B;B=C;} 68 if(B.len==1&&B.a[1]==0)break; 69 A=A-B; 70 while((A.len!=1||A.a[1]!=0)&&A.a[1]%2==0)A.div(); 71 } 72 if(A.len==1&&A.a[1]==1)puts("Yes"); 73 else puts("No"); 74 } 75 return 0; 76 }
T2:数数题，012的序列，问有多少个区间满足区间内最大的数不超过一半
正难则反，考虑有多少个不满足，不符合条件的区间为$j+1～i$,则一定有
$sumi-sumj>(i-j)/2$
$2*sumi-i>2*sumj-j$树状数组啊，于是我就60分gg了
再考虑性质，每往后移动一位，上述的val波动只有可能是1或-1；
于是处理前缀和O(1)转移即可
1 #include<cstdio> 2 #include<cstring> 3 #include<iostream> 4 #include<algorithm> 5 #include<cmath> 6 #define N 5000050 7 #define LL long long 8 using namespace std; 9 LL ans; 10 char s[N]; 11 int n,a[N],sum[3][N]; 12 int c[2*N],ss; 13 int main(){ 14 scanf("%d",&n); 15 scanf("%s",s+1); 16 for(int i=1;i<=n;i++){ 17 a[i]=s[i]-'0'; 18 sum[0][i]=sum[0][i-1]; 19 sum[1][i]=sum[1][i-1]; 20 sum[2][i]=sum[2][i-1]; 21 sum[a[i]][i]++; 22 } 23 ans=(LL)n*(n+1)/2; 24 for(int t=0;t<3;t++){ 25 memset(c,0,sizeof c); 26 c[n+5]++;ss=1; 27 for(int i=1,val,last;i<=n;i++){ 28 val=2*sum[t][i]-i+n+5; 29 last=2*sum[t][i-1]-i+1+n+5; 30 if(last==val-1){ans-=ss;} 31 if(last==val+1){ss-=c[last]+c[val];ans-=ss;} 32 c[val]++; 33 ss+=c[val]; 34 } 35 } 36 printf("%lld ",ans); 37 return 0; 38 }
T3:codeforces 739E加强版
O(n3)dp很好想，40分到手，然后我就gg了
如果贪心的话肯定是都喂A，也都喂B，但是球可能不够
考虑给每个A球赋一个额外的权值cost，每选一个A球就给最终答案减去cost，二分这个cost，就可以保证最终的A球在范围内，同理可以二分B
O(n3)->O(nlog2)
好像卡eps
1 #include<cstdio> 2 #include<cstring> 3 #include<iostream> 4 #include<algorithm> 5 #include<cmath> 6 #define eps 1e-8 7 #define N 100500 8 using namespace std; 9 int n,na,nb; 10 double p[N],q[N],pq[N]; 11 double ff; 12 int num1,num2; 13 bool judge(double x,double y){ 14 num1=0,num2=0;ff=0; 15 for(int i=1;i<=n;i++){ 16 int o=0; 17 double tmp1=p[i]-x,tmp2=q[i]-y,tmp3=pq[i]-x-y,last=ff; 18 if(last+tmp1>ff-eps){ff=last+tmp1;o=1;} 19 if(last+tmp2>ff-eps){ff=last+tmp2;o=2;} 20 if(last+tmp3>ff-eps){ff=last+tmp3;o=3;} 21 if(o&1)num1++;if(o&2)num2++; 22 } 23 } 24 double l,r,mid; 25 void check(double x){ 26 l=0;r=1; 27 while(l+eps<r){ 28 mid=(l+r)/2.0; 29 judge(x,mid); 30 if(num2<=nb)r=mid; 31 else l=mid; 32 } 33 } 34 int main(){ 35 while(scanf("%d%d%d",&n,&na,&nb)==3){ 36 for(int i=1;i<=n;i++)scanf("%lf",&p[i]); 37 for(int i=1;i<=n;i++)scanf("%lf",&q[i]); 38 for(int i=1;i<=n;i++)pq[i]=p[i]+q[i]-p[i]*q[i]; 39 double L=0,R=1,MID; 40 while(L+eps<R){ 41 MID=(L+R)/2.0; 42 check(MID); 43 judge(MID,r); 44 if(num1<=na)R=MID; 45 else L=MID; 46 } 47 judge(R,r); 48 printf("%0.3f ",ff+R*na+r*nb); 49 } 50 return 0; 51 }