[关闭]
@Scarlet 2017-03-27T11:09:01.000000Z 字数 7572 阅读 835

傻逼题范鏼

直播不看题解鏼题

BZOJ


随机数开题法,拒绝USACO
加了奇奇怪怪的形容词意为不能眼秒
打钩貌似可做,做了会写题解(大概)


4750【PJ好题】

从后往前找看到一堆1A中的一道15人A的题。
点开一看,啊好难,多组数据。

观察了一下发现,这种形式好像是套路题。先把最大值区间罗出来,问题转化相当于一个表格中对应之和。发现按位分解以后就是傻逼玩意儿了。

  1. /*
  2. Author:Scarlet
  3. */
  4. #include<bits/stdc++.h>
  5. #define maxn 100010
  6. #define mod 1000000061
  7. #define INF 2000000000
  8. using namespace std;
  9. typedef long long LL;
  10. #define G c=getchar()
  11. inline LL read()
  12. {
  13. LL x=0,f=1;char G;
  14. while(c>57||c<48){if(c=='-')f=-1;G;}
  15. while(c>47&&c<58)x=x*10+c-48,G;
  16. return x*f;
  17. }
  18. int l[maxn],r[maxn],q[maxn],p[maxn];
  19. LL aa[2][32],a[maxn][32],s[maxn];
  20. int bin[32];
  21. int main()
  22. {
  23. bin[0]=1;
  24. for(int i=1;i<32;i++)
  25. bin[i]=bin[i-1]<<1;
  26. int T=read();
  27. q[0]=INF;
  28. while(T--)
  29. {
  30. int n=read();
  31. for(int i=1;i<=n;i++)
  32. s[i]=read();
  33. p[0]=0;
  34. for(int top=0,i=1;i<=n;i++)
  35. {
  36. for(;s[i]>=q[top];)top--;
  37. l[i]=p[top]+1;q[++top]=s[i];p[top]=i;
  38. }
  39. p[0]=n+1;
  40. for(int top=0,i=n;i>=1;i--)
  41. {
  42. for(;s[i]>q[top];)top--;
  43. r[i]=p[top]-1;q[++top]=s[i];p[top]=i;
  44. }
  45. for(int i=1;i<=n;i++)
  46. s[i]^=s[i-1];
  47. for(int i=1;i<=n;i++)
  48. for(int x=s[i],j=0;x;x>>=1,j++)
  49. a[i][j]=x&1;
  50. for(int i=1;i<=n;i++)
  51. for(int j=0;j<32;j++)
  52. a[i][j]+=a[i-1][j];
  53. for(int i=n;i>=1;i--)
  54. s[i]^=s[i-1];
  55. LL ans=0;
  56. for(int i=1;i<=n;i++)
  57. {
  58. LL S=0;
  59. for(int j=0;j<32;j++)
  60. {
  61. LL x=r[i]-i+1,y=i-l[i]+1;
  62. LL s=a[r[i]][j]-a[i-1][j],t=a[i-1][j]-a[l[i]-2][j];
  63. (S+=((x-s)*t+(y-t)*s)%mod*bin[j]%mod)%=mod;
  64. }
  65. (ans+=S*s[i]%mod)%=mod;
  66. }
  67. printf("%lld\n",ans);
  68. }
  69. return 0;
  70. }

2996【简单数位DP】

题意:求之间被第大的数位整除的数的个数
MD每道数位DP都要写不知多久。
十分simple,枚举第大的数位,dp[x][top][qd0][h][P][s][t][rem]表示前位,是否有可能超过原数,是否还在前导0阶段,是否含有,第大的数位,小于的数位有几个,小于等于的数位有几个,余数是的方案数。
然后就轻松转移了。

看了前后排名的空间和效率我觉得我一定是写了假DP方程

  1. /*
  2. Author:Scarlet
  3. */
  4. #include<bits/stdc++.h>
  5. #define maxn 20
  6. using namespace std;
  7. typedef long long LL;
  8. #define G c=getchar()
  9. inline LL read()
  10. {
  11. LL x=0,f=1;char G;
  12. while(c>57||c<48){if(c=='-')f=-1;G;}
  13. while(c>47&&c<58)x=x*10+c-48,G;
  14. return x*f;
  15. }
  16. int dig[maxn],k,hhh;
  17. LL f[20][2][2][2][10][20][20][10];
  18. LL dfs(int x,bool top,bool qd0,bool h,int s,int t,int rem)
  19. {
  20. if(x<=0)return h&&s<k&&k<=t&&rem==0;
  21. if (f[x][top][qd0][h][hhh][s][t][rem]+1)return f[x][top][qd0][h][hhh][s][t][rem];
  22. int w=top?dig[x]:9;LL sum=0;
  23. for(int i=0;i<=w;i++)
  24. {
  25. sum+=dfs(x-1,top&(i==w),qd0&(i==0),h|(i==hhh),s+((qd0&&i==0)?0:i<hhh),t+((qd0&&i==0)?0:i<=hhh),(rem*10+i)%hhh);
  26. }
  27. return f[x][top][qd0][h][hhh][s][t][rem]=sum;
  28. }
  29. LL solve(LL x)
  30. {
  31. int cnt=0;
  32. memset(f,-1,sizeof(f));
  33. for(;x;x/=10)dig[++cnt]=x%10;
  34. LL ans=0;
  35. for(hhh=1;hhh<=9;hhh++)
  36. ans+=dfs(cnt,1,1,0,0,0,0);
  37. return ans;
  38. }
  39. int main()
  40. {
  41. LL L=read(),R=read();k=read();
  42. printf("%lld",solve(R)-solve(L-1));
  43. return 0;
  44. }

4247【推求和公式】

题意:表示把重复遍,表示把n的所有子串视作数字相加,求

假设没有重复

考虑

那么

  1. /*
  2. Author:Scarlet
  3. */
  4. #include<bits/stdc++.h>
  5. #define maxn 100010
  6. using namespace std;
  7. typedef long long LL;
  8. #define G c=getchar()
  9. inline LL read()
  10. {
  11. LL x=0,f=1;char G;
  12. while(c>57||c<48){if(c=='-')f=-1;G;}
  13. while(c>47&&c<58)x=x*10+c-48,G;
  14. return x*f;
  15. }
  16. using namespace std;
  17. char ss[maxn];
  18. LL s[maxn],k,m,mod,len,ten[maxn];
  19. LL mul(LL a, LL b)
  20. {
  21. LL ret=0;
  22. for(;b;b>>=1,a=(a<<1)%mod)
  23. if(b&1)ret=(ret+a)%mod;
  24. return ret;
  25. }
  26. LL Pow(LL a,LL b)
  27. {
  28. LL ret=1;
  29. for(;b;b>>=1,a=mul(a,a))
  30. if(b&1)ret=mul(ret,a);
  31. return ret;
  32. }
  33. LL C1(LL a, LL b)
  34. {
  35. if(b==1)return 1;
  36. if(b&1)return(C1(a,b-1)+Pow(a, b-1))%mod;
  37. else return mul(C1(a,b>>1),(1+Pow(a,b>>1))%mod);
  38. }
  39. LL C2(LL a, LL b)
  40. {
  41. if(b==1)return 0;
  42. if(b&1)return(C2(a,b-1)+mul(b-1,Pow(a,b-1)))%mod;
  43. else return(mul(C2(a,b>>1),1+Pow(a,b>>1))+mul(mul(b>>1,Pow(a,b>>1)),C1(a,b>>1)))%mod;
  44. }
  45. LL solve()
  46. {
  47. LL ans=0;
  48. ten[0]=1;
  49. for(int i=1;i<=len;i++)
  50. ten[i]=(ten[i-1]*10)%mod;
  51. LL t1=C1(ten[len],k);
  52. LL t2=C2(ten[len],k);
  53. LL t3=(k*(k-1)/2)%mod;
  54. for(int i=1;i<=len;i++)
  55. ans=(ans+mul(s[i],(mul(mul(t1,(k*len-i+1)%mod),ten[i])-mul((k*len-i+1)%mod,k)-mul(mul(t2,len),ten[i])+mul(len,t3)+2*mod)%mod))%mod;
  56. return ans;
  57. }
  58. int main()
  59. {
  60. scanf("%s",ss);
  61. k=read(),m=read();
  62. mod=9*m;
  63. len=strlen(ss);
  64. for(int i=0;i<=len-1;i++)
  65. s[len-i]=ss[i]-'0';
  66. LL ans=solve();
  67. cout<<ans/9<<endl;
  68. return 0;
  69. }

1091【枚举+计算几何】

,也不需要维护半平面交,只要计算和之前直线集的交点就好了。

  1. #include<bits/stdc++.h>
  2. #define maxn 20
  3. using namespace std;
  4. typedef long long LL;
  5. struct poi
  6. {
  7. double x,y;
  8. void in(){scanf("%lf%lf",&x,&y);}
  9. poi operator+(poi a){return (poi){x+a.x,y+a.y};}
  10. poi operator-(poi a){return (poi){x-a.x,y-a.y};}
  11. poi operator*(double a){return (poi){x*a,y*a};}
  12. double operator*(poi a){return x*a.y-y*a.x;}
  13. double dot(poi a){return x*a.x+y*a.y;}
  14. double abs(){return sqrt(x*x+y*y);}
  15. }ps[maxn];
  16. double mn,mx,v1,v2,ans=1e233;
  17. struct uuz
  18. {
  19. poi a,b;
  20. void chk(uuz w)
  21. {
  22. double c=w.b*b;
  23. if(c==0)return;
  24. c=(a*w.b+w.b*w.a)/c;
  25. if(c>0.5)c<mx&&(mx=c);
  26. else c>mn&&(mn=c);
  27. }
  28. }ls[maxn],l0[maxn];
  29. int n,id[maxn],lp=0;
  30. int main()
  31. {
  32. scanf("%lf%lf%d",&v1,&v2,&n);
  33. for(int i=1;i<=n;i++)ps[i].in(),id[i]=i;
  34. ps[n+1]=ps[1];
  35. poi p1=(poi){0,0},p2=(poi){v1,0},p3=(poi){v1,v2},p4=(poi){0,v2};
  36. ls[lp++]=(uuz){p1,p2-p1};
  37. ls[lp++]=(uuz){p2,p3-p2};
  38. ls[lp++]=(uuz){p3,p4-p3};
  39. ls[lp++]=(uuz){p4,p1-p4};
  40. for(int i=1;i<=n;++i)l0[i]=(uuz){ps[i],ps[i+1]-ps[i]};
  41. do
  42. {
  43. lp=4;
  44. double s=0;
  45. for(int i=1;i<=n;++i)
  46. {
  47. int w=id[i];
  48. mn=-1e10,mx=1e10;
  49. for(int j=0;j<lp;++j)l0[w].chk(ls[j]);
  50. ls[lp++]=l0[w];
  51. s+=(mx-mn)*l0[w].b.abs();
  52. }
  53. if(s<ans)ans=s;
  54. }
  55. while(std::next_permutation(id+1,id+n+1));
  56. printf("%.3f",ans);
  57. return 0;
  58. }

3003【SPFA+状压DP】

傻逼到没有心情写


4690【带权并查集】

大家都会


3938【线段树维护凸包】

李超线段树


4710【组合DP】


3268【倍增】


3800【暴力】

先钦点一段路程长度,然后就能做暴力计算啦
呀啦?好像不是我写的...

  1. #include<stdio.h>
  2. #include<string.h>
  3. #define zero 1e-8
  4. #define MAXD 210
  5. #define INF 10000
  6. struct point
  7. {
  8. double x, y;
  9. }wa[MAXD], wb[MAXD], *a, *b;
  10. int N, na, nb;
  11. double u[MAXD], v[MAXD], w[MAXD];
  12. double fabs(double x)
  13. {
  14. return x < 0 ? -x : x;
  15. }
  16. int dcmp(double x)
  17. {
  18. return fabs(x) < zero ? 0 : (x < 0 ? -1 : 1);
  19. }
  20. double det(double x1, double y1, double x2, double y2)
  21. {
  22. return x1 * y2 - x2 * y1;
  23. }
  24. void init()
  25. {
  26. int i, j, k;
  27. for(i = 0; i < N; i ++)
  28. scanf("%lf%lf%lf", &v[i], &u[i], &w[i]);
  29. }
  30. void add(double x, double y)
  31. {
  32. b[nb].x = x, b[nb].y = y;
  33. ++ nb;
  34. }
  35. void cut(double a1, double a2, double a3)
  36. {
  37. int i, j, k;
  38. point *t;
  39. double x, y, t1, t2, x1, y1, x2, y2;
  40. nb = 0;
  41. if(dcmp(a2) == 0)
  42. {
  43. x1 = x2 = (-a3) / a1;
  44. if(dcmp(a1) < 0)
  45. y1 = INF, y2 = 0;
  46. else
  47. y1 = 0, y2 = INF;
  48. }
  49. else
  50. {
  51. if(dcmp(a2) < 0)
  52. x1 = 0, x2 = INF;
  53. else
  54. x1 = INF, x2 = 0;
  55. y1 = (-a3 - a1 * x1) / a2, y2 = (-a3 - a1 * x2) / a2;
  56. }
  57. for(i = 0; i < na; i ++)
  58. {
  59. t1 = det(x2 - x1, y2 - y1, a[i].x - x1, a[i].y - y1);
  60. t2 = det(x2 - x1, y2 - y1, a[i + 1].x - x1, a[i + 1].y - y1);
  61. if(dcmp(t1) >= 0)
  62. add(a[i].x, a[i].y);
  63. if(dcmp(t1) * dcmp(t2) < 0)
  64. {
  65. x = (fabs(t2) * a[i].x + fabs(t1) * a[i + 1].x) / (fabs(t1) + fabs(t2));
  66. y = (fabs(t2) * a[i].y + fabs(t1) * a[i + 1].y) / (fabs(t1) + fabs(t2));
  67. add(x, y);
  68. }
  69. }
  70. t = a, a = b, b = t;
  71. na = nb;
  72. a[na] = a[0];
  73. }
  74. int check()
  75. {
  76. int i, j, k;
  77. double s = 0;
  78. for(i = 0; i < na; i ++)
  79. s += det(a[i].x, a[i].y, a[i + 1].x, a[i + 1].y);
  80. if(dcmp(s) == 0)
  81. return 0;
  82. return 1;
  83. }
  84. void solve()
  85. {
  86. int i, j, k;
  87. double a1, a2, a3;
  88. a = wa, b = wb;
  89. for(i = 0; i < N; i ++)
  90. {
  91. na = 3;
  92. a[0].x = 0, a[0].y = 0, a[1].x = INF, a[1].y = 0, a[2].x = 0, a[2].y = INF;
  93. a[na] = a[0];
  94. for(j = 0; j < N; j ++)
  95. {
  96. if(j == i)
  97. continue;
  98. a1 = (w[i] - v[i]) / (w[i] * v[i]) - (w[j] - v[j]) / (w[j] * v[j]);
  99. a2 = (w[i] - u[i]) / (w[i] * u[i]) - (w[j] - u[j]) / (w[j] * u[j]);
  100. a3 = INF * (w[j] - w[i]) / (w[i] * w[j]);
  101. if(dcmp(a2) == 0 && dcmp(a1) == 0)
  102. {
  103. if(dcmp(a3) < 0)
  104. continue;
  105. break;
  106. }
  107. cut(a1, a2, a3);
  108. }
  109. if(j != N || !check())
  110. printf("No\n");
  111. else
  112. printf("Yes\n");
  113. }
  114. }
  115. int main()
  116. {
  117. while(scanf("%d", &N) == 1)
  118. {
  119. init();
  120. solve();
  121. }
  122. return 0;
  123. }
添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注