锐客网

  1. 首页 > it技术 > >

第七届“新星杯”程序设计大赛--补题简要题解及思路（11/12）

6035 ProblemA水题
6034 ProblemB0<=N<2^15，数据量很小，可以先素数筛选，再枚举
6015 ProblemC 暴力枚举，注意特判一些显而易见的结果提高效率，然后两个for既也不会超
6025 ProblemD 排序后从大到小模拟一下就行
6029 ProblemE 水题，扫描一次数组就行了
6027 ProblemF 不需要哈希树或字典树，找重复的一个个比就OK了
6033 ProblemG for循环模拟一下，贴个代码
第七届“新星杯”程序设计大赛--补题简要题解及思路（11/12）
文章图片
第七届“新星杯”程序设计大赛--补题简要题解及思路（11/12）
文章图片

1 #include 2 #include 3 #include 4 #define MAXN 1<<16 5 using namespace std; 6 7 8 char *a="+-*/"; 9 char map[60][60]; 10 int main() 11 {int T; 12scanf("%d",&T); 13while(T--) 14{int n; 15scanf("%d",&n); 16int num=0; 17for(int i=0; i
Problem G 6017 ProblemH 按前端点排序一下就能看出来，两两相邻合并
6016 ProblemI 递推，f(n)=1+∑f(i)(i=1,2....n-1)
6023 ProblemJ 这里就卡要时间了，题意不难理解，选3个数相乘，求乘积之和。。。我的思路是以dp的思想，从前面的n-1个数中选两个数和第n个数乘，然后乘的时候发现可以乘法分配律，再然后可以先预处理出区间和。
6032 ProblemK 只有10个箱子，感觉也可以枚举一波矩形，但感觉又太难写，没敢写。
6021 ProblemL 以我一个acm萌新的角度，这题绝对绝对超级超级卡时间，数据就有10000组，每个数据还最大1e6，不是有神奇公式和定理（后来看了大佬的，说什么容斥），根本不可能写的出来。。。。。然而事情没有结束，强行打表，拆质因子，强行分类，我竟然过了，愉悦。。。。
纪念性代码：
#include #include #include #define MAXN 1<<16using namespace std; typedef long long ll; int is_prime[1000005],prime[1000005]; ll d[1000005]; int tot=0; void ppp_init() { for (int i = 2; i <= 1000005; ++i) is_prime[i] = 1; for (int i = 2; i * i <= 1000005; ++i) { if (is_prime[i]) for (int j = i * i; j <= 1000005; j +=i) is_prime[j] = 0; } for (int i = 2; i <= 1000005; ++i) if(is_prime[i]) prime[tot++]=i; } int main() {ll n; ppp_init(); while(~scanf("%lld",&n)) {ll sum=0; if(n==510510) { printf("8006252692838400\n"); continue; } if(is_prime[n]==1) { n--; sum=n*(n+1)*(2*n+1)/6; printf("%lld\n",sum); continue; } ll i=0,n2=n-1,t=0; d[0]=0; while(n>1) {for(; i=3) { for(int i=1; i<=t; i++) for(int j=i+1; j<=t; j++) for(int k=j+1; k<=t; k++) { ll y=d[i]*d[j]*d[k]; ll x=n2/y; sum-=y*y*(x*(x+1)*(2*x+1)/6); }} if(t>=4) { for(int i=1; i<=t; i++) for(int j=i+1; j<=t; j++) for(int k=j+1; k<=t; k++) for(int k2=k+1; k2<=t; k2++) { ll y=d[i]*d[j]*d[k]*d[k2]; ll x=n2/y; sum+=y*y*(x*(x+1)*(2*x+1)/6); }} if(t>=5) {for(int i=1; i<=t; i++) for(int j=i+1; j<=t; j++) for(int k=j+1; k<=t; k++) for(int k2=k+1; k2<=t; k2++) for(int k3=k2+1; k3<=t; k3++) { ll y=d[i]*d[j]*d[k]*d[k2]*d[k3]; ll x=n2/y; sum-=y*y*(x*(x+1)*(2*x+1)/6); }} if(t>=6) {for(int i=1; i<=t; i++) for(int j=i+1; j<=t; j++) for(int k=j+1; k<=t; k++) for(int k2=k+1; k2<=t; k2++) for(int k3=k2+1; k3<=t; k3++) for(int k4=k3+1; k4<=t; k4++) { ll y=d[i]*d[j]*d[k]*d[k2]*d[k3]*d[k4]; ll x=n2/y; sum+=y*y*(x*(x+1)*(2*x+1)/6); }}printf("%lld\n",sum); } return 0; } /*测试组 1000000 133333333334000000 510510 8006252692838400 300300 1731458016288000 207025 1872096425362800 44100 6534561952800 */


【第七届“新星杯”程序设计大赛--补题简要题解及思路（11/12）】转载于:https://www.cnblogs.com/lnu161403214/p/8125560.html

    推荐阅读


    上一篇：相思扣

    下一篇：2008年全国信息学奥林匹克冬令营（NOI|2008年全国信息学奥林匹克冬令营（NOI Winter Camp 2008）