首页 > 代码库 > 10.30上午考试
10.30上午考试
P75
竞赛时间： ????年??月??日??:??-??:??
注意事项（请务必仔细阅读）
【 问题描述】
从1 − ??中找一些数乘起来使得答案是一个完全平方数，求这个完全平方数
最大可能是多少。
【输入格式】
第一行一个数字??。
【输出格式】
一行一个整数代表答案对100000007取模之后的答案。
【样例输入】
7
【样例输出】
144
【样例解释】
但是塔外面有东西。
【数据规模与约定】
对于20%的数据， 1 ≤ ?? ≤ 100。
对于50%的数据， 1 ≤ ?? ≤ 5000。
对于70%的数据， 1 ≤ ?? ≤ 105。
对于100%的数据， 1 ≤ ?? ≤ 5 × 106。
/*对于n的阶乘质因数分解后如果一个素数次数是奇数那么不选这个素数否则选这个素数这样就能保证最大并且不会出现一个数的一部分选一部分不选的情况因为不选的一定是素数 */#include<iostream>#include<cstdio>#include<cstring>#define LL long long#define maxn 5000010#define mod 100000007using namespace std;LL n,tot,ans=1;LL prime[maxn],f[maxn],a[maxn];LL init(){ LL x=0,f=1;char c=getchar(); while(c<‘0‘||c>‘9‘){if(c==‘-‘)f=-1;c=getchar();} while(c>=‘0‘&&c<=‘9‘){x=x*10+c-‘0‘;c=getchar();} return x*f;}void prepare(){ for(int i=2;i<=n;i++) { if(!f[i])prime[++tot]=i; for(int j=1;j<=tot&&prime[j]*i<=n;j++) { f[prime[j]*i]=1; if(i%prime[j]==0)break; } }}LL pow(LL x,LL m){ if(m==0)return 1; LL he=pow(x,m/2); he=(he*he)%mod; if(m&1)he=(he*x)%mod; return he;}int main(){ freopen("hao.in","r",stdin); freopen("hao.out","w",stdout); n=init(); prepare(); for(int i=1;i<=tot;i++) { LL ha=n; while(ha) { a[i]+=ha/prime[i]; ha/=prime[i]; } } for(int i=1;i<=tot;i++) ans=(ans*pow(prime[i],a[i]/2*2))%mod; cout<<ans<<endl; return 0;}
【问题描述】
有??个数，随机选择一段区间，如果这段区间的所有数的平均值在[??, ??]中则
你比较厉害。求你比较厉害的概率。
【输入格式】
第一行有三个数??, ??, ??，含义如上描述。
接下来一行有??个数代表每一个数的值。
【输出格式】
输出一行一个分数??
??
代表答案，其中??, ??互质。 如果答案为整数则直接输出该
整数即可。
【样例输入 1】
4 2 3
3 1 2 4
【样例输出 1】
7/10
【样例输入 2】
4 1 4
3 1 2 4
【样例输出 2】
1
【样例解释】
塔外面有棵树。
【数据规模与约定】
对于30%的数据， 1 ≤ ?? ≤ 104。
对于60%的数据， 1 ≤ ?? ≤ 105。
对于100%的数据， 1 ≤ ?? ≤ 5 × 105, 0 < ?? ≤ ?? ≤ 100。
/*维护前缀和O(n2)暴力 30分 */#include<iostream>#include<cstdio>#include<cstring>#define LL long long#define maxn 500010using namespace std;LL n,l,r,x,y;LL a[maxn],s[maxn];LL init(){ LL x=0,f=1;char c=getchar(); while(c<‘0‘||c>‘9‘){if(c==‘-‘)f=-1;c=getchar();} while(c>=‘0‘&&c<=‘9‘){x=x*10+c-‘0‘;c=getchar();} return x*f;}LL GCD(LL a,LL b){ return b==0?a:GCD(b,a%b);}int main(){ freopen("jian.in","r",stdin); freopen("jian.out","w",stdout); n=init();l=init();r=init(); for(LL i=1;i<=n;i++) { a[i]=init(); s[i]=s[i-1]+a[i]; } for(LL i=1;i<=n;i++) { for(LL j=i;j<=n;j++) { double sum=s[j]-s[i-1]; if(sum>=l*(j-i+1)&&sum<=r*(j-i+1))x++; } } y=n*(n+1)/2; if(x%y==0) cout<<x/y<<endl; else { LL gcd=GCD(x,y); cout<<x/gcd<<"/"<<y/gcd<<endl; } return 0;}
正解:暂无
【问题描述】
?? × ??的方阵上有??棵葱， 你要修一些栅栏把它们围起来。 一个栅栏是一段
沿着网格建造的封闭图形（ 即要围成一圈）。 各个栅栏之间应该不相交、 不重叠
且互相不包含。 如果你最多修??个栅栏， 那么所有栅栏的长度之和最小是多少？
【 输入格式】
第一行三个整数??, ??, ??。
接下来??行每行两个整数??, ??代表某棵葱的位置。
【 输出格式】
一行一个整数代表答案。
【样例输入 1】
6 1 4
1 3
4 2
4 4
6 4
【 样例输出 1】
18
【样例输入 2】
6 2 4
1 3
4 2
4 4
6 4
【 样例输出 2】
16
【 样例解释】
你猜树上有啥。
【数据规模与约定】
对于10%的数据， ?? = 1。
对于30%的数据， ?? ≤ 2。
对于60%的数据， ?? ≤ 10。
对于100%的数据， 1 ≤ ?? ≤ ?? ≤ 16, ?? ≤ 1000。
/*O(k的n次方)无任何剪枝超时 45分 */#include<iostream>#include<cstdio>#include<cstring>using namespace std;int m,w,n,ans=0x7ffffff;struct node{ int x; int y;}a[20];int c[20][20];int init(){ int x=0,f=1;char c=getchar(); while(c<‘0‘||c>‘9‘){if(c==‘-‘)f=-1;c=getchar();} while(c>=‘0‘&&c<=‘9‘){x=x*10+c-‘0‘;c=getchar();} return x*f;}void work1(){ int minx=10000,maxx=0,miny=10000,maxy=0; for(int i=1;i<=n;i++) { minx=min(minx,a[i].x); miny=min(miny,a[i].y); maxx=max(maxx,a[i].x); maxy=max(maxy,a[i].y); } printf("%d\n",2*(maxx-minx+1+maxy-miny+1));}void dfs(int x){ if(x==n+1) { int sum=0; for(int i=1;i<=w;i++) { int minx=10000,maxx=0,miny=10000,maxy=0; for(int j=1;j<=c[i][0];j++) { int t=c[i][j]; minx=min(minx,a[t].x); miny=min(miny,a[t].y); maxx=max(maxx,a[t].x); maxy=max(maxy,a[t].y); } if(c[i][0])sum+=2*(maxx-minx+1+maxy-miny+1); } ans=min(ans,sum); return ; } for(int i=1;i<=w;i++) { c[i][0]++;c[i][c[i][0]]=x; dfs(x+1); c[i][0]--; }}int main(){ freopen("dan.in","r",stdin); freopen("dan.out","w",stdout); m=init();w=init();n=init(); for(int i=1;i<=n;i++) a[i].x=init(),a[i].y=init(); if(w==1) { work1(); return 0; } dfs(1); printf("%d\n",ans); return 0;}
正解:暂无
10.30上午考试