csp-s模拟测试84「smooth·six·walker」
rtrt
3月 14, 2025
归档于 2019-10-26 17:10
好久没写过一整套题了
smooth
题解
题意转化为用前15个素数凑出第k小的数(每个素数可以乘多次)
类似于蚯蚓,最简单的方法就是维护一个优先队列,但由于优先队列带$log$如何优化掉
十五个单调队列\十五个单调指针
十五个单调指针(其实还有一个队列)
举个例子,挺难说的
初始队列里只有1,十五个单调指针都指向1,表示为21,31,5*1,,,,,,,
第一轮发现2最小将2放进队列,并将2指针前移 此时22 31 5*1,,,,,,
又发现3最小 把3放进队列3指针前移,此时22 32 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表示没有被加入
16表示第16批被加入
7表示已经加入过两次
还有一个数已经被加入两次,现在又加入是非法的之前有2,2现在又加入2(第三次)
类似情况判定
for(ll p=1;p<=cnt;p++)
if(s2&&s1){
if(s2==7) goto eat_lunch;
如果之前2,3在同一批加入是合法的,例如之前加入12,现在加入6是合法的
类似情况判定
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);
}
View Code
walker
题解
随机化
为什么随机化是正解
因为其中有一半是正确的随便选出来两个正确总概率是$\frac{1}{4}$
进行50次全部出错概率${\frac{1}{4}}^50$
为什么选出两个
只选一个解不出来,,,,,,,,,,,,,,,,,
推式子得高斯消元系数是这样
自己手动推一下,其实很简单
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;
代码
#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);
}
View Code