Codeforces Round #341 (Div. 2) CDE

本文主要是介绍Codeforces Round #341 (Div. 2) CDE，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

C Wet Shark and Flowers

计算$s_i$为$p$的倍数的概率，当$s_i$是$p$的倍数时，贡献是4000。然后减去相邻两个数同时为$p$的倍数的情况。

#include <bits/stdc++.h>      
using namespace std;   #define ll long long  int l[100010];
int r[100010];
int flag[100010];
double m[100010];int main(){int n,p;cin>>n>>p;for(int i=1;i<=n;i++){scanf("%d %d",&l[i],&r[i]);flag[i]= (r[i]/p) - (l[i]-1)/p ;m[i]=r[i]-l[i]+1;}double ans = 0;for(int i=1;i<=n;i++){if(flag[i]){ans += 4000*(flag[i]/m[i]);}}for(int i=1;i<=n;i++){int next = i+1;if(next>n)next=1;if(flag[i] && flag[next]){ans -= 2000.0*(flag[i]/m[i])*(flag[next]/m[next]);}}printf("%.10f\n",ans);return 0;
}

D Rat Kwesh and Cheese

正解是取2次对数分类讨论，然而我用long double取一次对数水过了。。需要引起注意的是对数函数的定义域。

#include <bits/stdc++.h>      
using namespace std;   #define ll long long  
#define ld long doubleld a_bc(ld a,ld b,ld c){return log(a)*(pow(b,c));
}ld ab_c(ld a,ld b,ld c){return c*(log(a)*b);
}int main(){ld x,y,z;cin>>x>>y>>z;ld a[22];a[1]=a_bc(x,y,z);a[2]=a_bc(x,z,y);a[3]=ab_c(x,y,z);a[4]=ab_c(x,z,y);//a[5]=a_bc(y,x,z);a[6]=a_bc(y,z,x);a[7]=ab_c(y,x,z);a[8]=ab_c(y,z,x);//a[9]=a_bc(z,x,y);a[10]=a_bc(z,y,x);a[11]=ab_c(z,x,y);a[12]=ab_c(z,y,x);int ans;ld MAX=-1e9;for(int i=1;i<=12;i++){if(a[i]>MAX+1e-15){ans=i;MAX=a[i];}}switch (ans){case 1:cout<<"x^y^z";break;case 2:cout<<"x^z^y";break;case 3:cout<<"(x^y)^z";break;case 4:cout<<"(x^z)^y";break;case 5:cout<<"y^x^z";break;case 6:cout<<"y^z^x";break;case 7:cout<<"(y^x)^z";break;case 8:cout<<"(y^z)^x";break;case 9:cout<<"z^x^y";break;case 10:cout<<"z^y^x";break;case 11:cout<<"(z^x)^y";break;case 12:cout<<"(z^y)^x";break;}return 0;
}

E Wet Shark and Blocks

一个$0$~$x-1$的数，在末尾添上一个数字，再对$x$取模，仍然会得到$0$~$x-1$，这是一种“变换”。用矩阵来描述这种“变换”，然后使用快速幂可解。

#include <bits/stdc++.h>      
using namespace std;   #define ll long long  int a[50010];
int cnt[10];
int ans[2][111];const int maxsize = 105;const int mod =1000000007;struct mat{  ll v[maxsize][maxsize];  mat(){  memset(v,0,sizeof(v));  }  
};  mat mat_mul(mat a,mat b,int siz){  mat re;  for(int i=0;i<siz;i++){  for(int j=0;j<siz;j++){  for(int k=0;k<siz;k++){  re.v[i][j]+=a.v[i][k]*b.v[k][j];  re.v[i][j]%=mod;  }  }  }  return re;  
}  mat mat_pow(mat m,int n,int siz){  mat re;  mat tmp=m;  for(int i=0;i<siz;i++){  re.v[i][i]=1;  }  while(n){  if(n&1){  re=mat_mul(re,tmp,siz);  }  tmp=mat_mul(tmp,tmp,siz);  n>>=1;  }  return re;  
}  void print(mat m,int sz){for(int i=0;i<sz;i++){for(int j=0;j<sz;j++){cout<<m.v[i][j]<<" ";}cout<<endl;}
}int main(){int n, b, k ,x;cin>>n>>b>>k>>x;for(int i=1;i<=n;i++){scanf("%d",&a[i]);cnt[a[i]]++;}mat mm;for(int i=0;i<x;i++){for(int j=1;j<=9;j++){int tmp=i*10+j;tmp%=x;mm.v[i][tmp]+=cnt[j];}}mat s;for(int i=1;i<=9;i++){s.v[0][i%x]+=cnt[i];}mm = mat_pow(mm,b-1,x);mat ans = mat_mul(s,mm,x);cout<<ans.v[0][k]<<endl;return 0;
}

这篇关于Codeforces Round #341 (Div. 2) CDE的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---