好久没写过一整套题了
smooth
题解
题意转化为用前15个素数凑出第k小的数(每个素数可以乘多次)
类似于蚯蚓,最简单的方法就是维护一个优先队列,但由于优先队列带$log$如何优化掉
十五个单调队列\十五个单调指针
十五个单调指针(其实还有一个队列)
举个例子,挺难说的
初始队列里只有1,十五个单调指针都指向1,表示为2*1,3*1,5*1,,,,,,,
第一轮发现2最小将2放进队列,并将2指针前移 此时2*2 3*1 5*1,,,,,,
又发现3最小 把3放进队列3指针前移,此时2*2 3*2 5*1
每次前移都是前移到队列中下一个数
这样还会出现重复,去一下重即可(不去重会T(重复状态很多))
十五个队列
和上面类似,不再重复叙述,队列里存最大质因子为$p_j$,同样需要去重
代码
#include<bits/stdc++.h> using namespace std; #define ll long long #define inf 1234567891011121314 ll it[20],prime[20]={0,2,3,5,7,11,13,17,19,23,29,31,37,41,43,47}; ll ans[11111111]; ll b,k,cnt,tmp; int main(){ ans[0]=1; scanf("%lld%lld",&b,&k); ll mnid,minn; while(cnt<k-1){ mnid=1,minn=inf; for(ll j=1;j<=b;j++){ while(ans[it[j]]*prime[j]<=ans[cnt])it[j]++; tmp=prime[j]*ans[it[j]]; if(tmp<minn&&ans[cnt]<minn){ minn=tmp; mnid=j; } } ans[++cnt]=minn; it[mnid]++; } printf("%lld\n",minn); }
six
题解
这里用的是Paris神的状态定义,先%%%为敬,
一个质因子最多会分6批加入
判断非法就非常简单了
例如现在加入的某个数(6)有两个质因子2,3
如果之前2,3在同一批加入是合法的,例如之前加入12,现在加入6是合法的
如果2,3不是同一批被加入是非法的
还有一个数已经被加入两次,现在又加入是非法的之前有2,2现在又加入2(第三次)
八进制压位
0表示没有被加入
1~6表示第1~6批被加入
7表示已经加入过两次
类似情况判定
for(ll p=1;p<=cnt;p++) if(s2&&s1){ if(s2==7) goto eat_lunch;
类似情况判定
else if(!m) m=s2; else if(m!=s2) goto eat_lunch;
代码
#include<stdio.h> #define ll long long #define s1 ((k>>(p-1))&1) #define s2 ((j>>(3*(p-1))&7)) ll n,cnt,ans; const ll mod=1e9+7; ll rate[67],f[852741],t[741]; int main(){ scanf("%lld",&n); for(ll i=2;i*i<=n;i++){ if(n%i==0){ cnt++; while(n%i==0) n/=i,t[cnt]++; } } if(n!=1) t[++cnt]=1; for(ll i=1;i<1<<cnt;i++){ rate[i]=1; for(ll j=1;j<=cnt;j++){ if((i>>(j-1))&1) rate[i]*=t[j]; } } f[0]=1; for(ll j=0;j<(1<<(cnt*3));j++){ if(f[j]){ ans=(ans+f[j])%mod; // printf("f[%lld]=%lld\n",j,f[j]); for(ll k=1;k<1<<cnt;k++){ ll x=0,now=j,m=0; for(ll p=1;p<=cnt;p++) if(!s2&&s1){ x=p; break; } for(ll p=1;p<=cnt;p++) if(s2&&s1){ if(s2==7) goto eat_lunch; else if(!m) m=s2; else if(m!=s2) goto eat_lunch; } for(ll p=1;p<=cnt;p++){ if(s1){ if(s2) now|=7<<(3*(p-1)); else now|=x<<(3*(p-1)); } } f[now]=(f[now]+f[j]*rate[k])%mod; eat_lunch:; } } } printf("%lld\n",ans-1); }
walker
题解
随机化
为什么随机化是正解
因为其中有一半是正确的随便选出来两个正确总概率是$\frac{1}{4}$
进行50次全部出错概率${\frac{1}{4}}^50$
为什么选出两个
只选一个解不出来,,,,,,,,,,,,,,,,,
推式子
代码
#include<bits/stdc++.h> using namespace std; #define ll long long #define eps 1e-4 #define A 789456 struct node{ double bex,bey,afx,afy; }p[A]; double dx,dy,the,s; double a[50][50]; void gauss(ll n,ll ii,ll jj){ a[1][1]=p[ii].bex,a[1][2]=-p[ii].bey,a[1][3]=1,a[1][4]=0,a[1][5]=p[ii].afx; a[2][1]=p[ii].bey,a[2][2]=p[ii].bex,a[2][3]=0,a[2][4]=1,a[2][5]=p[ii].afy; a[3][1]=p[jj].bex,a[3][2]=-p[jj].bey,a[3][3]=1,a[3][4]=0,a[3][5]=p[jj].afx; a[4][1]=p[jj].bey,a[4][2]=p[jj].bex,a[4][3]=0,a[4][4]=1,a[4][5]=p[jj].afy; for(ll i=1;i<=n;i++){ ll r=i; for(ll j=i+1;j<=n;j++) if(fabs(a[j][i])>fabs(a[r][i])) r=j; if(fabs(a[r][i])<eps) continue ; if(r!=i) for(ll j=1;j<=n+1;j++) swap(a[r][j],a[i][j]); for(ll j=1;j<=n;j++){ if(j==i) continue ; for(ll k=n+1;k>=i;k--){ a[j][k]-=a[j][i]/a[i][i]*a[i][k]; } } } for(ll i=1;i<=n;i++){ if(fabs(a[i][i])>eps) a[i][n+1]=a[i][n+1]/a[i][i]; } s=sqrt(a[1][5]*a[1][5]+a[2][5]*a[2][5]); the=atan(a[2][5]/a[1][5]); if(fabs(a[2][5]/s-sin(the))>eps) the+=3.1415926535; dx=a[3][5],dy=a[4][5]; }ll n; ll check(){ ll haf=(n+1)/2; ll cnt=0; for(ll i=1;i<=n;++i){ if(fabs(cos(the)*s*p[i].bex-s*sin(the)*p[i].bey+dx-p[i].afx)<eps&&fabs(sin(the)*s*p[i].bex+cos(the)*s*p[i].bey+dy-p[i].afy)<eps) ++cnt; if(cnt>=haf) return 1; } return 0; } int main(){ srand((unsigned)time(0)); scanf("%lld",&n); for(ll i=1;i<=n;i++){ scanf("%lf%lf%lf%lf",&p[i].bex,&p[i].bey,&p[i].afx,&p[i].afy); } ll times=90; while(times){ ll aa=rand()%n+1,bb=rand()%n+1; gauss(4,aa,bb); while(s<0||s>10){ aa=rand()%n+1,bb=rand()%n+1; gauss(4,aa,bb); times--; } if(check()) break; } printf("%.10lf\n",the); printf("%.10lf\n",s); printf("%.10lf %.10lf\n",dx,dy); }