T1 smooth

考场上水个了优先队列多带个$log$，前$80$分的点跑的飞快，后面直接萎了。

其实只需开$B$个队列，每次向对应队列中插入新的光滑数，就能保证队列中的数是单调的。

为了保证不重，只往编号大的队列中加入即可。

$code:$

 1 #include<bits/stdc++.h>

 2 #define int long long

 3 using namespace std;

 4 int b,k,cnt,ans,pos;

 5 int pri[21]={0,2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71};

 6 queue<int>q[16];

 7 inline int read(){

 8     int x=0,f=1; char ch=getchar();

 9     while(ch<'0'||ch>'9'){ if(ch=='-') f=-1; ch=getchar(); }

10     while(ch>='0'&&ch<='9'){ x=(x<<1)+(x<<3)+(ch^48); ch=getchar(); }

11     return x*f;

12 }

13 inline void write(int x){

14     char ch[20]; int len=0;

15     if(x<0) putchar('-'), x=~x+1;

16     do{

17         ch[len++]=x%10+(1<<5)+(1<<4);

18         x/=10;

19     }while(x);

20     for(int i=len-1;i>=0;--i) putchar(ch[i]);

21     return;

22 }

23 signed main(){

24     b=read(); k=read(); cnt=ans=1;

25     for(int i=1;i<=b;i++) q[i].push(pri[i]);

26     while(cnt<k){

27         cnt++; ans=2e18;

28         for(int i=1;i<=b;i++)

29             if(q[i].front()<ans) ans=q[i].front(), pos=i;

30         q[pos].pop();

31         for(int i=pos;i<=b;i++)

32             q[i].push(ans*pri[i]);

33     }

34     write(ans); putchar('\n');

35     return 0;

36 }

T2 six

看出是个状压，想三进制但没时间了，手模$2$分类讨论还炸了。哈哈

正解神仙。不难理解其实只需知道质因子集合出现的状态，可以预处理出每个集合可以表示的数的数量。

状态数组维护两个状态，分别为当前质因子集合与不同数中出现的质因子对集合。对于后者可以写个类似$hash$的东西来映射。

二进制数很大但状态数不多，可以用$map$维护。具体实现可以记忆化搜索。

$code:$

 1 #include<bits/stdc++.h>

 2 #define int long long

 3 using namespace std;

 4 const int p=1e9+7;

 5 int n,cnt,pri[10],ans,num[10],sum[1<<10];

 6 unordered_map<int,int>f;

 7 inline int read(){

 8     int x=0,f=1; char ch=getchar();

 9     while(ch<'0'||ch>'9'){ if(ch=='-') f=-1; ch=getchar(); }

10     while(ch>='0'&&ch<='9'){ x=(x<<1)+(x<<3)+(ch^48); ch=getchar(); }

11     return x*f;

12 }

13 inline void write(int x){

14     char ch[20]; int len=0;

15     if(x<0) putchar('-'), x=~x+1;

16     do{

17         ch[len++]=x%10+(1<<5)+(1<<4);

18         x/=10;

19     }while(x);

20     for(int i=len-1;i>=0;--i) putchar(ch[i]);

21     return;

22 }

23 void try_del(){

24     for(int i=2;i*i<=n;i++){

25         if(!(n%i)) pri[++cnt]=i;

26         while(!(n%i)) num[cnt]++, n/=i;

27     }

28     if(n!=1) pri[++cnt]=n, num[cnt]=1;

29 }

30 int upd(int a,int b){

31     int res=0;

32     for(int i=0;i<cnt;i++)

33         for(int j=0;j<=i;j++)

34             if(((a&(1<<i))&&(b&(1<<j)))||((a&(1<<j)&&(b&(1<<i))))) res|=(1<<(i*(i+1)/2+j));

35     return res;

36 }

37 bool check(int a,int b){

38     for(int i=0;i<cnt;i++)

39         for(int j=0;j<=i;j++)

40             if((a&(1<<i))&&(a&(1<<j))&&(b&(1<<(i*(i+1)/2+j)))) return 0;

41     return 1;

42 }

43 int dfs(int s,int t){

44     int now=(s<<30)+t;

45     if(f.find(now)!=f.end()) return f[now];

46     f[now]=1;

47     for(int i=1;i<(1<<cnt);i++){

48         if(!check(i,t)) continue;

49         f[now]=(f[now]+sum[i]*dfs(s|i,t|upd(s,i))%p)%p;

50     }

51     return f[now];

52 }

53 signed main(){

54     n=read(); try_del();

55     for(int i=1;i<1<<cnt;i++){

56         sum[i]=1;

57         for(int j=0;j<cnt;j++)

58             if(i&(1<<j)) (sum[i]*=num[j+1])%=p;

59     }

60     write(dfs(0,0)-1); putchar('\n');

61     return 0;

62 }

T3 walker

看到反三角函数直接弃了，混了是个人都能拿的$30pts$。其实在三角函数名前加个$a$就行。

把三个操作合并，一共得到四个未知数：$scale\times cos\theta$，$scale\times sin\theta$，$d_x$，$d_y$。

一组数据$x$,$y$得到两个方程，随机选出两组数据高斯消元后检验即可。

一次高斯消元$O(64)$，检验$O(n)$，单次检验通过的概率是$\frac{1}{4}$，进行$50$次时间没问题，不正确率$(\frac{3}{4})^{50}<10^{-5}$，直接过了。

$code:$

 1 #include<bits/stdc++.h>

 2 using namespace std;

 3 const int NN=1e5;

 4 const double eps=1e-6;

 5 double x[NN],y[NN],xx[NN],yy[NN],a[10][10];

 6 int n,cnt,ra,rb;

 7 double sca,arc;

 8 inline int read(){

 9     int x=0,f=1; char ch=getchar();

10     while(ch<'0'||ch>'9'){ if(ch=='-') f=-1; ch=getchar(); }

11     while(ch>='0'&&ch<='9'){ x=(x<<1)+(x<<3)+(ch^48); ch=getchar(); }

12     return x*f;

13 }

14 inline void write(int x){

15     char ch[20]; int len=0;

16     if(x<0) putchar('-'), x=~x+1;

17     do{

18         ch[len++]=x%10+(1<<5)+(1<<4);

19         x/=10;

20     }while(x);

21     for(int i=len-1;i>=0;--i) putchar(ch[i]);

22     return;

23 }

24 bool guass(){

25     double temp; int r=1;

26     for(int i=1;i<=4;i++){

27         int h=r;

28         for(int j=r;j<=4;j++) if(fabs(a[j][i])>fabs(a[h][i])) h=j;

29         if(h!=r) for(int j=i;j<=i+1;j++) swap(a[h][j],a[r][j]);

30         if(fabs(a[r][i])<eps) return 0;

31         for(int j=r+1;j<=4;j++){

32             temp=a[j][i]/a[r][i];

33             for(int k=i;k<=5;k++) a[j][k]-=temp*a[r][k];

34         }

35         r++;

36     }

37     for(int i=r;i;i--){

38         for(int j=i+1;j<=4;j++) a[i][5]-=a[i][j]*a[j][5];

39         a[i][5]/=a[i][i];

40     } return 1;

41 }

42 bool check_in_check(int i){

43     if(fabs(x[i]*a[1][5]-y[i]*a[2][5]+a[3][5]-xx[i])>eps) return 0;

44     if(fabs(x[i]*a[2][5]+y[i]*a[1][5]+a[4][5]-yy[i])>eps) return 0;

45     return 1;

46 }

47 bool check(int fi,int se){

48     a[1][1]=x[fi]; a[1][2]=-y[fi]; a[1][3]=1; a[1][4]=0; a[1][5]=xx[fi];//scale*cos

49     a[2][1]=y[fi]; a[2][2]= x[fi]; a[2][3]=0; a[2][4]=1; a[2][5]=yy[fi];//scale*sin

50     a[3][1]=x[se]; a[3][2]=-y[se]; a[3][3]=1; a[3][4]=0; a[3][5]=xx[se];//dx

51     a[4][1]=y[se]; a[4][2]= x[se]; a[4][3]=0; a[4][4]=1; a[4][5]=yy[se];//dy

52     if(!guass()) return 0;

53     int res=0;

54     for(int i=1;i<=n;i++)

55         if(check_in_check(i)) ++res;

56     return res>=(n+1)/2;

57 }

58 signed main(){

59     n=read(); srand(time(0));

60     for(int i=1;i<=n;i++)

61         scanf("%lf%lf%lf%lf",&x[i],&y[i],&xx[i],&yy[i]);

62     while(cnt<50){

63         ++cnt; ra=rand()%n+1; rb=rand()%n+1;

64         while(ra==rb) ra=rand()%n+1, rb=rand()%n+1;

65         if(check(ra,rb)) break;

66     }

67     sca=sqrt(a[1][5]*a[1][5]+a[2][5]*a[2][5]);

68     arc=acos(a[1][5]/sca);

69     if(a[2][5]<0) arc=-arc;

70     printf("%.10lf\n%.10lf\n%.10lf %.10lf\n",arc,sca,a[3][5],a[4][5]);

71     return 0;

72 }

巴特西

2021.8.6考试总结[NOIP模拟32]

T1 smooth

T2 six

T3 walker

最新文章

热门文章