[关闭]
@KirinBill 2018-03-07T15:15:10.000000Z 字数 6023 阅读 432

2018.03.07 HAOI 模拟赛

套题

puts("gg");

目录


diyiti

oAVvw.png

思路

代码

  1. #include <cstdio>
  2. const int MAXN=2005,P=998244353;
  3. int n,psb;
  4. int p[MAXN][MAXN];
  5. inline int pow(int x,int y){
  6. int ret=1;
  7. for(;y;x=(long long)x*x%P,y>>=1){
  8. if(y&1) ret=(long long)ret*x%P;
  9. }
  10. return ret;
  11. }
  12. inline int inv(int x){return pow(x,P-2);}
  13. inline void cal_p(){
  14. p[0][0]=1;
  15. for(int i=1;i<=n;++i){
  16. for(int j=0;j<i;++j){
  17. p[i][j]=(p[i][j]+(long long)p[i-1][j]*pow((1-psb+P)%P,j)%P)%P;
  18. p[i][j+1]=(p[i][j+1]+(long long)p[i-1][j]*pow(psb,i-(j+1))%P)%P;
  19. }
  20. }
  21. }
  22. inline int cal_f(){
  23. static int f[MAXN];
  24. f[1]=1;
  25. for(int i=2,tmp;i<=n;++i){
  26. tmp=0;
  27. for(int j=1;j<i;++j)
  28. tmp=(tmp+(long long)f[j]*p[i][j]%P)%P;
  29. f[i]=(1-tmp+P)%P;
  30. }
  31. return f[n];
  32. }
  33. int main(){
  34. freopen("diyiti.in","r",stdin);
  35. freopen("diyiti.out","w",stdout);
  36. int a,b;
  37. scanf("%d%d%d",&n,&a,&b);
  38. psb=(long long)a*inv(b)%P;
  39. cal_p();
  40. printf("%d",cal_f());
  41. return 0;
  42. }

dierti

oAtf8.png
oAJlW.png

思路

代码:

  1. #include <cstdio>
  2. #include <cstring>
  3. const int MAXN=5005,P=1e9+7;
  4. int n;
  5. int fac[MAXN],l[MAXN][MAXN],r[MAXN][MAXN];
  6. int ans[MAXN];
  7. char s[MAXN];
  8. inline void cal_l(){
  9. l[0][0]=1;
  10. for(int i=1;i<=n;++i){
  11. for(int j=1;j<=i;++j)
  12. l[i][j]=(long long)l[i-1][j]*j%P;
  13. if(s[i]=='<'){
  14. for(int j=1;j<=i;++j)
  15. l[i][j]=(l[i][j]+(long long)l[i-1][j+1]*(j+1)%P*j%P)%P;
  16. }
  17. else{
  18. for(int j=1;j<=i;++j)
  19. l[i][j]=(l[i][j]+l[i-1][j-1])%P;
  20. }
  21. }
  22. }
  23. inline void cal_r(){
  24. r[n+1][0]=1;
  25. for(int i=n,lim;i;--i){
  26. lim=n-i+1;
  27. for(int j=1;j<=lim;++j)
  28. r[i][j]=(long long)r[i+1][j]*j%P;
  29. if(s[i]=='>'){
  30. for(int j=1;j<=lim;++j)
  31. r[i][j]=(r[i][j]+(long long)r[i+1][j+1]*(j+1)%P*j%P)%P;
  32. }
  33. else{
  34. for(int j=1;j<=lim;++j)
  35. r[i][j]=(r[i][j]+r[i+1][j-1])%P;
  36. }
  37. }
  38. }
  39. inline void pre_fac(){
  40. fac[0]=1;
  41. for(int i=1;i<=n;++i)
  42. fac[i]=(long long)fac[i-1]*i%P;
  43. }
  44. inline void DP(){
  45. for(int i=1;i<=n;++i){
  46. for(int j=0;j<=n;++j){
  47. ans[i]=(ans[i]+(long long)l[i-1][j+1]*fac[j+1]%P*r[i+1][j]%P*fac[j]%P)%P;
  48. ans[i]=(ans[i]+(long long)l[i-1][j]*fac[j]%P*r[i+1][j+1]%P*fac[j+1]%P)%P;
  49. ans[i]=(ans[i]+((long long)l[i-1][j]*fac[j]%P*r[i+1][j]%P*fac[j]%P<<1)%P)%P;
  50. }
  51. }
  52. }
  53. int main(){
  54. freopen("dierti.in","r",stdin);
  55. freopen("dierti.out","w",stdout);
  56. scanf("%s",s+1);
  57. n=strlen(s+1);
  58. if(n==1){
  59. putchar('1');
  60. return 0;
  61. }
  62. cal_l();
  63. cal_r();
  64. pre_fac();
  65. DP();
  66. for(int i=1;i<=n;++i)
  67. printf("%d ",ans[i]);
  68. return 0;
  69. }

disanti

oAgLR.png
oAyKL.png

思路

代码:

  1. #include <cstdio>
  2. #include <algorithm>
  3. #include <vector>
  4. #include <climits>
  5. #include <cstring>
  6. using std::sort;
  7. using std::vector;
  8. using std::min;
  9. const int MAXN=200005,MAXM=200005;
  10. const long long INF=1LL<<60;
  11. int n,m,ocnt;
  12. long long dp[MAXM];
  13. struct data{int u,v,s,t;}flight[MAXM];
  14. struct option{
  15. int now,tm,id;
  16. bool type;
  17. static bool cmp_tm(const option &a,const option &b){
  18. return a.tm<b.tm || (a.tm==b.tm && a.type<b.type);
  19. }
  20. }opt[MAXM<<1];
  21. inline long long sqr(long long x){return x*x;}
  22. inline int slope(int i){return -(flight[i].t<<1);}
  23. inline long long y_itsct(int i){return sqr(flight[i].t)+dp[i];}
  24. inline long long cal(int i,int j){
  25. return (long long)slope(j)*flight[i].s+y_itsct(j);
  26. }
  27. inline double itcpt(int i,int j){
  28. return (double)(y_itsct(j)-y_itsct(i))/(slope(i)-slope(j));
  29. }
  30. inline long long DP(){
  31. static int head[MAXN],tail[MAXN];
  32. static vector<int> dq[MAXN];
  33. sort(opt+1,opt+ocnt+1,option::cmp_tm);
  34. memset(tail,-1,sizeof(tail));
  35. memset(dp,0x3f,sizeof(dp));
  36. dp[0]=0;
  37. ++tail[1],dq[1].push_back(0);
  38. long long ret=LLONG_MAX;
  39. for(int i=1;i<=ocnt;++i){
  40. if(opt[i].type==0){
  41. if(head[opt[i].now]>tail[opt[i].now]) continue;
  42. while(head[opt[i].now]<tail[opt[i].now] && cal(opt[i].id,dq[opt[i].now][head[opt[i].now]])>=cal(opt[i].id,dq[opt[i].now][head[opt[i].now]+1]))
  43. ++head[opt[i].now];
  44. dp[opt[i].id]=cal(opt[i].id,dq[opt[i].now][head[opt[i].now]])+sqr(flight[opt[i].id].s);
  45. }
  46. else{
  47. while(head[opt[i].now]<tail[opt[i].now] && itcpt(opt[i].id,dq[opt[i].now][tail[opt[i].now]-1])<=itcpt(dq[opt[i].now][tail[opt[i].now]],dq[opt[i].now][tail[opt[i].now]-1]))
  48. --tail[opt[i].now],dq[opt[i].now].pop_back();
  49. ++tail[opt[i].now],dq[opt[i].now].push_back(opt[i].id);
  50. if(opt[i].now==n) ret=min(ret,dp[opt[i].id]);
  51. }
  52. }
  53. return ret;
  54. }
  55. int main(){
  56. freopen("disanti.in","r",stdin);
  57. freopen("disanti.out","w",stdout);
  58. scanf("%d%d",&n,&m);
  59. for(int i=1,u,v,s,t;i<=m;++i){
  60. scanf("%d%d%d%d",&u,&v,&s,&t);
  61. flight[i]=(data){u,v,s,t};
  62. opt[++ocnt]=(option){u,s,i,0};
  63. opt[++ocnt]=(option){v,t,i,1};
  64. }
  65. printf("%lld",DP());
  66. return 0;
  67. }
添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注