首页 > 代码库 > 济南-1030试题解题报告
济南-1030试题解题报告
济南-1030试题解题报告
By shenben
本解题报告解析均为100分解题思路。
上午
T1
题意：从1− n中找一些数乘起来使得答案是一个完全平方数，求这个完全平方数
最大可能是多少.
解析：
1、 质因数分解
2、 1->n用质因数指数的相加的形式将1*n累乘起来
3、 扫一遍指数为奇数的质因数都-1，偶数的不变
4、 快速幂乘一遍，同时取模
T2
题意：有n个数，随机选择一段区间，如果这段区间的所有数的平均值在[L,R]中则
你比较厉害。求你比较厉害的概率
解析：（暴力枚举 40分）
100分需要推式子，过程略，最后式子：求S[R]-S[L]
(S[x]=前缀和a[i]-x的逆序对个数)
Fz= S[R]-S[L];
Fm=(n+1)*n/2;
Fz=fm-fz;
Ans=fz/fm(需要约分)
T3
题意：n*m的方阵上有?棵葱，你要修一些栅栏把它们围起来。一个栅栏是一段
沿着网格建造的封闭图形（即要围成一圈） 。各个栅栏之间应该不相交、不重叠
且互相不包含。如果你最多修?个栅栏，那么所有栅栏的长度之和最小是多少
解析：
搜索+各种剪枝
详见代码
下午
T1
题意：
一张长度为n的纸带，我们可以从左至右编号为0 −n（纸带最左端标号为
0） 。现在有m次操作，每次将纸带沿着某个位置进行折叠，问所有操作之后纸带
的长度是多少
解析：
模拟
折痕左边大，右边往左边折，同时右边向左边映射.L不变，R=折痕
折痕右边大，左边往右边折，同时左边向右边映射.L=折痕，R不变
(100分不能用并查集维护，应为并查集依靠数组的size太大)
T2
题意：给你 L,R,S,M，求满足L<=(S*x) mod M<=R最小的正整数x
解析：
略
详见代码
T3
题意：n个人坐成一圈，其中第k个人拿着一个球。每次每个人会以一定的概率向左边的人和右边的人传球。当所有人都拿到过球之后，最后一个拿到球的人即为胜者。求第n个人获胜的概率（所有人按照编号逆时针坐成一圈）
解析：
等比数列（还是推式子）
上午
T1代码：
#include<cstdio>#include<cstring>#define ll long long#define mod 100000007using namespace std;const int N=5e6+10;int n,tot,prime[N];bool check[N];void prepare(){ for(int i=2;i<=n;i++){ if(!check[i]) prime[++tot]=i; for(int j=1;j<=tot&&prime[j]*i<=n;j++){ check[prime[j]*i]=1; if(i%prime[j]==0) break; } }}#define name "hao"int main(){ freopen(name".in","r",stdin); freopen(name".out","w",stdout); scanf("%d",&n); prepare(); memset(check,0,sizeof check); for(ll res,i=1;i<=tot;i++){ res=0; for(ll j=prime[i];j<=n;j*=(ll)prime[i]) res+=n/j; if(res&1) check[prime[i]]=1; } ll ans=1; for(ll i=2;i<=n;i++) if(!check[i]) ans=ans*i%mod; printf("%I64d",ans); fclose(stdin); fclose(stdout); return 0;}
T2代码：
#include<cstdio>#include<cstring>#include<algorithm>#define name "jian"#define ll long long#ifdef unix#define LL "%lld"#else#define LL "%I64d"#endifusing namespace std;const int N=1e6+10;int n,L,R,a[N],b[N];ll fz,fm,gy,ans,s[N],c[N];inline const int read(){ register int x=0,f=1; register char ch=getchar(); while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();} while(ch>=‘0‘&&ch<=‘9‘){x=(x<<3)+(x<<1)+ch-‘0‘;ch=getchar();} return x*f;}void binary_chop(int l,int r){ if(l==r) return ; int mid=l+r>>1; binary_chop(l,mid);binary_chop(mid+1,r); int p=l,q=l,j=mid+1; while(p<=mid&&j<=r){ if(s[p]>s[j]){ ans+=mid-p+1; c[q++]=s[j++]; } else{ c[q++]=s[p++]; } } while(p<=mid) c[q++]=s[p++]; while(j<=r) c[q++]=s[j++]; for(int i=l;i<=r;i++) s[i]=c[i];}int main(){ freopen(name".in","r",stdin); freopen(name".out","w",stdout); n=read();L=read();R=read(); for(int i=1;i<=n;i++) a[i]=read(); for(int i=1;i<=n;i++) b[i]=a[i]-L; for(int i=1;i<=n+1;i++) s[i]=s[i-1]+b[i-1]; binary_chop(1,n+1);fz+=ans; memset(s,0,sizeof s);ans=0; for(int i=1;i<=n;i++) b[i]=a[i]-R; for(int i=1;i<=n+1;i++) s[i]=s[i-1]+b[i-1]; reverse(s+1,s+n+2); binary_chop(1,n+1);fz+=ans; fm=(ll)n*(n+1)/2; fz=fm-fz; gy=__gcd(fz,fm); fz/=gy;fm/=gy; if(fm==1) printf(LL"\n",fz); else printf(LL "/" LL,fz,fm); fclose(stdin); fclose(stdout); return 0;}/*40分代码，长个记性#include<cstdio>#include<cstring>#include<algorithm>using namespace std;#define name "jian"#define ll long long#ifdef unix#define LL "%lld"#else#define LL "%I64d"#endifinline const ll read(){ register ll x=0,f=1; register char ch=getchar(); while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();} while(ch>=‘0‘&&ch<=‘9‘){x=(x<<3)+(x<<1)+ch-‘0‘;ch=getchar();} return x*f;}const int N=5e5+10;int n,p,L,R,a[N];ll sum[N];ll fz,fm,gy;int main(){ freopen(name".in","r",stdin); freopen(name".out","w",stdout); n=read();L=read();R=read(); for(int i=1;i<=n;i++) a[i]=read(); for(int i=1;i<=n;i++) sum[i]=sum[i-1]+a[i]; fm=(ll)(n+1)*n/2; double tmp; for(int i=1;i<=n;i++){ for(int j=i;j<=n;j++){ tmp=(double)(sum[j]-sum[i-1])/(j-i+1);//必须用double类型（除法有精度要求)，否则会炸 //当时脑残了，还去排序，这是一个数列。连四十分都没有拿到。QAQ if(tmp>=L&&tmp<=R) fz++;//直接判是否在[L,R]中就好了 } } gy=__gcd(fz,fm); fz/=gy;fm/=gy; if(fm==1) printf(LL"\n",fz); else printf(LL "/" LL,fz,fm); fclose(stdin); fclose(stdout); return 0;}*/
T3代码：
#include<cstdio>#include<algorithm>using namespace std;inline const int read(){ register int x=0,f=1; register char ch=getchar(); while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();} while(ch>=‘0‘&&ch<=‘9‘){x=(x<<3)+(x<<1)+ch-‘0‘;ch=getchar();} return x*f;}const int N=1e6+10;const int M=20;int m,n,k,xx[M],yy[M];int cost[N],s[M];int tot,nowmask,answer,full;struct rect{ int x1,x2,y1,y2; int mask,w; rect(){} rect(int _x1,int _y1,int _x2,int _y2){ x1=_x1,y1=_y1,x2=_x2,y2=_y2; mask=0; for(int i=0;i<n;i++) if(x1<=xx[i]&&xx[i]<=x2&&y1<=yy[i]&&yy[i]<=y2) mask|=(1<<i); w=((x2-x1+1)+(y2-y1+1))*2; if(mask==full) answer=w; }}a[N];void dfs(int cnt,int j,int cost){ if(nowmask==full){ //if(clock()>=1950){printf("%d",answer);exit(0);} answer=min(answer,cost);return ; } if(cnt>=k||j>tot||cost>=answer) return ; for(int i=j;i<=tot;i++){ if(nowmask&a[i].mask) continue; nowmask^=a[i].mask; dfs(cnt+1,i+1,cost+a[i].w); nowmask^=a[i].mask; }}void DFS(int now,int cnt,int res){ if(now==n){ if(res<answer) answer=res;return; } if(res+(k-cnt)*4>=answer) return; for(int i=1;i<=cnt;i++){ int pres=s[i]; s[i]|=(1<<now); DFS(now+1,cnt,res-cost[pres]+cost[s[i]]); s[i]^=(1<<now); } if(cnt<k){ s[++cnt]=(1<<now); DFS(now+1,cnt,res+4); }}#define name "dan"int main(){ freopen(name".in","r",stdin); freopen(name".out","w",stdout); m=read();k=read();n=read(); full=(1<<n)-1; for(int i=0;i<n;i++) xx[i]=read(),yy[i]=read(); if(n<15){ for(int i=0;i<n;i++){ for(int j=i;j<n;j++){ for(int k=j;k<n;k++){ for(int l=k;l<n;l++){ a[++tot]=rect(min(min(xx[i],xx[j]),min(xx[k],xx[l])),min(min(yy[i],yy[j]),min(yy[k],yy[l])), max(max(xx[i],xx[j]),max(xx[k],xx[l])),max(max(yy[i],yy[j]),max(yy[k],yy[l]))); } } } } nowmask=0; dfs(0,1,0); printf("%d",answer); } else{ answer=4000; for(int i=1;i<=full;i++){ int sx=1001,mx=-1,sy=1001,my=-1; for(int j=0;j<n;j++){ if((i>>j)&1){ if(xx[j]<sx) sx=xx[j]; if(xx[j]>mx) mx=xx[j]; if(yy[j]<sy) sy=yy[j]; if(yy[j]>my) my=yy[j]; } } cost[i]=(mx-sx+1)*2+(my-sy+1)*2; } DFS(0,0,0); printf("%d",answer); } fclose(stdin); fclose(stdout); return 0;}
下午
T1代码：
#include<iostream>#include<cstdio>#define ll long long#define name "he"#ifdef unix#define LL "%lld"#else#define LL "%I64d"#endifusing namespace std;const int N=1e4+10;ll f[N],n,L,R;int m;inline const ll read(){ register ll x=0,f=1; register char ch=getchar(); while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();} while(ch>=‘0‘&&ch<=‘9‘){x=(x<<3)+(x<<1)+ch-‘0‘;ch=getchar();} return x*f;}int main(){ freopen(name".in","r",stdin); freopen(name".out","w",stdout); n=read();m=read(); L=0;R=n; for(int i=1;i<=m;i++) f[i]=read(); for(int i=1;i<=m;i++){ if(f[i]*2>=L+R) R=f[i];//舍掉右边 else L=f[i];//舍掉左边 for(int j=i+1;j<=m;j++){ if(f[j]>R) f[j]=R*2-f[j]; if(f[j]<L) f[j]=L*2-f[j]; } } printf(LL,R-L); return 0;}/*60分代码存档#include<cstdio>#define name "he"using namespace std;inline const int read(){ register int x=0,f=1; register char ch=getchar(); while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();} while(ch>=‘0‘&&ch<=‘9‘){x=(x<<3)+(x<<1)+ch-‘0‘;ch=getchar();} return x*f;}const int N=1e6+10;int n,m,a[N],fa[N];inline const int ABS(int x){ return x>0?x:-x;}int find(int x){ return fa[x]==x?x:fa[x]=find(fa[x]);}int main(){ freopen(name".in","r",stdin); freopen(name".out","w",stdout); n=read();m=read(); for(int i=1;i<=m;i++) a[i]=read(); int starting=0,ending=n; for(int i=0;i<=n;i++) fa[i]=i; for(int i=1,j,k,t1,t2,fx,fy;i<=m;i++){ a[i]=find(a[i]); t1=ABS(a[i]-starting); t2=ABS(a[i]-ending); if(t1<t2){ for(j=a[i]-1,k=a[i]+1,fx,fy;j>=starting;j--,k++){ fx=find(j); fy=find(k); fa[fx]=fy; } starting=a[i]; } else{ for(j=a[i]+1,k=a[i]-1;j<=ending;j++,k--){ fx=find(j); fy=find(k); fa[fx]=fy; } ending=a[i]; } } printf("%d",ending-starting); return 0;}*/
T2代码：
//copy from other‘s#include<cstdio>#include<algorithm>using namespace std;const int N=1e5+10; int a[N],top;int erfen(int x){ int l=1,r=top,mid,res=0; while(l<=r){ mid=(l+r)>>1; if(a[mid]>=x) res=mid,r=mid-1; else l=mid+1; } return res;}int main(){ freopen("she.in","r",stdin); freopen("she.out","w",stdout); int i,j,k,n,m,s,l,r,x,now,t,ans,ans2; bool fl; scanf("%d",&t); while(t--){ scanf("%d%d%d%d",&m,&s,&l,&r); if(l>=m){printf("-1\n");continue;} if(r>=m)r=m-1; now=0;fl=0; top=0; for(n=1;n*n<=m;n++){ now=(now+s)%m; if(l<=now&&now<=r){ printf("%d\n",n); fl=1;break; } a[++top]=now; } --n; int ste=a[top]; if(fl) continue; sort(a+1,a+top+1); for(now=1;now*n<=m;now++){ l=(l-ste+m)%m;r=(r-ste+m)%m; if(l>r) { if(a[top]>=l){fl=1;break;} if(a[1]<=r){fl=1;break;} } else{ if(a[top]<l) continue; int x=erfen(l); if(a[x]<=r){fl=1;break;} } } if(!fl){printf("-1\n");continue;} ans=now*n; now=0; for(i=1;i<=top;i++){ now=(now+s)%m; if(l<=now&&now<=r)break; } ans+=i; printf("%d\n",ans); } return 0;}/*30分代码存档#include<cstdio>#include<ctime>#include<cstdlib>#include<iostream>#include<algorithm>#include<cstring>#include<cmath>#define ll long long#define name "she"using namespace std;inline const ll read(){ register ll x=0,f=1; register char ch=getchar(); while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();} while(ch>=‘0‘&&ch<=‘9‘){x=(x<<3)+(x<<1)+ch-‘0‘;ch=getchar();} return x*f;}ll cas,tx,m,s,l,r;ll sx=1e6+10;bool falg;void go(int tt){ tt++; while(tt--) puts("-1"); exit(0);}int main(){ freopen(name".in","r",stdin); freopen(name".out","w",stdout); cas=read(); while(cas--){ m=read();s=read();l=read();r=read(); if(m<=l){puts("-1");continue;} if(clock()>=900) go(cas); if(l==r) tx=m*10,falg=1; for(ll i=1;i<=sx;i++){ if(clock()>=900) go(cas); if(falg){ if(i>tx){ puts("-1"); falg=0; break; } } ll tmp=s*i%m; if(tmp>=l&&tmp<=r){ printf("%d\n",(int)i); break; } if(tmp==1&&i>m){ puts("-1"); break; } } } return 0;}*/
T3代码：
#include<cstdio>#define LDB long double#define DB doubleusing namespace std;const int N=1000+10;int T,n,k,pre[N],next[N];LDB p[N],q[N];void deal(int b){ int a=pre[b],c=next[b]; LDB pa=p[a],pb=p[b],pc=p[c]; p[a]=pa*pb/(1-pa*(1-pb)); q[a]=1-p[a]; q[c]=(1-pc)*(1-pb)/(1-pb*(1-pc)); p[c]=1-q[c]; next[a]=c;pre[c]=a;}LDB solve(){ if(n<=2) return 1; if(n<=3) return k==1?p[1]:q[2]; for(int i=1;i<=n;i++) pre[i]=i-1,next[i]=i+1; pre[1]=n;next[n]=1; if(k==1){ for(int i=2;i<n-1;i++) deal(i); return p[1]; } if(k==n-1){ for(int i=2;i<n-1;i++) deal(i); return q[n-1]; } for(int i=2;i<n-1;i++) if(i!=k) deal(i); deal(k); return q[k]*p[1]+p[k]*q[n-1];}DB v;#define name "it"int main(){ freopen(name".in","r",stdin); freopen(name".out","w",stdout); scanf("%d",&T); while(T--){ scanf("%d%d",&n,&k); for(int i=1;i<=n;i++){ scanf("%lf",&v); p[i]=v; q[i]=1-v; } printf("%.9lf\n",(DB)solve()); } fclose(stdin); fclose(stdout); return 0;}/*可骗30分代码存档 #include<cstdio>const int MAXN=110;double p[MAXN];int n=0,k=0;void solve() { for(int i=1;i<=n;i++) scanf("%lf",p+i); p[0]=p[n]; if(n==1) printf("%.9lf\n",1.0); else if(n==k) printf("%.9lf\n",0.0); else if(n==2) printf("%.9lf\n",1.0); else printf("%.9lf\n",k==1?p[1]:(1-p[2]));}int main() { freopen("it.in","r",stdin); freopen("it.out","w",stdout); int T=0; scanf("%d\n",&T); while(T--){ scanf("%d%d",&n,&k); solve(); } return 0;}*/
济南-1030试题解题报告
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。