day17
程序员文章站
2022-12-21 11:41:34
wdnmd什么垃圾网站,把我两道题分搞没了,实际得分50/300,应该得分150/300; 无话可说; T1暴力枚举; T2数论+DP; T3几何等; T1先枚举行的情况,再枚举列的情况; #include #include #include ......
wdnmd什么垃圾网站,把我两道题分搞没了,实际得分50/300,应该得分150/300;
无话可说;
t1暴力枚举;
t2数论+dp;
t3几何等;
t1先枚举行的情况,再枚举列的情况;
#include<iostream> #include<cstdio> #include<algorithm> #include<cstring> using namespace std; int xx[20],yy[20],ans=2147483647; char a[20][20],d; int n,m,r,c; void dfs(int x,int tot) { if(x>n) { memset(yy,0,sizeof(yy)); for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) { if(!xx[i]&&a[i][j]=='x')yy[j]=1; } for(int j=1;j<=m;j++) { if(yy[j]) { for(int k=0;k<c;k++) yy[min(j+k,m)]=0; tot++; } } ans=ans<tot?ans:tot; return; } else { for(int i=x;i<=min(x+r,n);i++)xx[i]=1; dfs(x+r,tot+1); for(int i=x;i<=min(x+r,n);i++)xx[i]=0; } dfs(x+1,tot); } int main() { cin>>n>>m; for(int i=1;i<=n;i++)for(int j=1;j<=m;j++) { d=getchar(); while(d!='.'&&d!='x') d=getchar(); a[i][j]=d; } cin>>r>>c; dfs(1,0); cout<<ans<<endl; return 0; }
t2
#include<iostream> #include<cstdio> using namespace std; unsigned long long h[1200],num[1000],f[1000],ans=1; int n,k; int main() { cin>>n>>k; for(int i=1;i<=n;i++) { h[i]=1; } for(int i=1;i<k;i++) { for(int j=1;j<=n;j++) { h[j]=(h[j]+h[j-1])%1000000009; } } int i=1,p=n; while(n) { int x=n; while(x%2==0) { x/=2; f[2]++; } for(int j=3;j<=x;j+=2) { while(x%j==0) { f[j]++; x/=j; } } if(x>1)f[x]++; for(int j=1;j<=n;j++) { num[j]=(num[j]+f[j]*h[i]%1000000009)%1000000009; f[j]=0; } i++;n--; } for(int i=2;i<=p;i++) { ans=ans*(num[i]+1)%1000000009; } cout<<ans<<endl; return 0; }
t3
截距只是为了缩小枚举范围,按纵截距排序后答案只在相邻两个点连成的线里;
#include<iostream> #include<cstdio> #include<algorithm> #include<cmath> using namespace std; struct node{ double x,y,b; }a[210000]; double p,q,temp,stand,minn=0x7fff; int x,y; int n,ans1,ans2; inline int read() { int x=0,f=1;char c=getchar(); while(!isdigit(c)){if(c=='-')f=-1;c=getchar();} while(isdigit(c)){x=(x<<3)+(x<<1)+(c^48);c=getchar();} return x*f; } inline int gcd(int p,int q){return q==0?p:gcd(q,p%q);} inline double xl(int i){return (a[i].y-a[i+1].y)/(a[i].x-a[i+1].x);} inline double cmp(node p,node q){return p.b<q.b;} int main() { freopen("slope.in","r",stdin);freopen("slope.out","w",stdout); n=read();p=read();q=read(); stand=p/q; for(int i=1;i<=n;i++){ a[i].x=read();a[i].y=read();a[i].b=a[i].y-a[i].x*stand;} sort(a+1,a+n+1,cmp); for(int i=1;i<n;i++) { temp=xl(i); if(abs(temp-stand)<abs(minn-stand)){ minn=temp;x=int(a[i].x)-int(a[i+1].x);y=a[i].y-a[i+1].y; } } x=abs(x);y=abs(y); int gcdd=gcd(max(x,y),min(x,y)); x/=gcdd;y/=gcdd; cout<<y<<'/'<<x<<endl; return 0; }
好了,day17全部改完了。
300/300
上一篇: 重学计算机组成原理(八)- 程序的装载
下一篇: day20