首页 > 代码库 > ACdream原创群赛(18)のAK's dream题解
ACdream原创群赛(18)のAK's dream题解
只做了4题水题ADGI
A题需要注意的就是“[...]”的输出了，何时输出，何时不输出。
1 #include <stdio.h> 2 int main() 3 { 4 int n, cur, d; 5 int cnt = 1; 6 while(scanf("%d%d%d",&n,&cur,&d)!=EOF) 7 { 8 printf("Case #%d: ",cnt++); 9 if(cur==1)10 printf("[<<]");11 else12 printf("(<<)");13 int start = cur - d;14 int end = cur + d;15 if(start >0 && start!=1 && cur!=1)//说明前面有隐藏页，需要输出[...]16 printf("[...]");17 for(int i=start; i<=end && i<=n; ++i)18 {19 if(i <=0 )20 continue;21 else22 {23 if(i == cur)24 printf("[%d]",i);25 else26 printf("(%d)",i);27 }28 }29 if(end<n && cur!=n)//说明后面有隐藏页，需要输出[...]30 printf("[...]");31 if(cur==n)32 printf("[>>]");33 else34 printf("(>>)");35 printf("\n");36 37 }38 }
D题应该是数学题吧（分步计数原理），将数组weight 和数组pow排序
然后分别判断每个数有多少种选择，然后一一相乘取模
对于第一个hero，如果有a1把剑的weight小于等于power，对于第二个hero，有a2把剑的weight小于等于power,一次类推
那么第一个英雄有a1种选择，第二个英雄有a2-1种选择，第三个英雄有a3-2种选择，一次类推。
至于判断有多少把剑的weight小于每个英雄的power，普通查找会超时，要用二分查找。
二分查找的特性是，对于key，如果数组中有元素与之相等，那么就返回该元素的下标，不然就返回就返回第一个比key大的元素的下标（如果有的话）
如果没有，就返回数组最后一个元素的下标。 所以我们可以用二分查找找出比power[i]小的weight有多少个
1 #include <stdio.h> 2 #include <string.h> 3 #include <algorithm> 4 using namespace std; 5 typedef long long LL; 6 const int N = 100000 + 10; 7 const int MOD = 1000000007; 8 int w[N]; 9 int p[N];10 void input(int &x)11 {12 char ch = getchar();13 while(ch<‘0‘ || ch >‘9‘)14 ch = getchar();15 x = 0;16 while(ch>=‘0‘ && ch<=‘9‘)17 {18 x = x * 10 + ch - ‘0‘;19 ch = getchar();20 }21 }22 int main()23 {24 int t;25 int n;26 int i,j,k,z;27 int tCase = 1;28 input(t);29 while(t--)30 {31 printf("Case #%d: ",tCase++);32 input(n);33 for(i=1; i<=n; ++i)34 input(w[i]);35 for(i=1; i<=n; ++i)36 input(p[i]);37 sort(w+1, w+n+1);38 sort(p+1, p+n+1);39 LL ans = 1;40 int cnt;41 for(i=1; i<=n; ++i)42 {43 cnt = 0;44 int low = 1; int high = n;45 int mid;46 while(low <= high)47 {48 mid = (low + high)/2;49 if(p[i] == w[mid])50 break;51 else if(p[i] >= w[mid])52 low = mid + 1;53 else54 high = mid - 1;55 }56 if(p[i] < w[mid])57 mid--;58 ans = (ans*(mid-i+1))%MOD;59 }60 printf("%lld\n",ans);61 }62 }
G题要没什么，先用字符串读入，判断有没有可能爆，如果有可能，继续进一步的字符串判断，如果没可能，就用sscanf读入，然后判断范围
1 #include <iostream> 2 #include <stdio.h> 3 #include <string> 4 using namespace std; 5 typedef long long LL; 6 string Max = "9223372036854775807";//19 7 int main() 8 { 9 int i;10 string str;11 LL num;12 while(cin>>str)13 {14 if(str[0] != ‘-‘) 15 {16 if(str.size() < 19)17 {18 sscanf(str.c_str(),"%lld",&num);19 if(num <= 32767)20 puts("short");21 else if(num <= 2147483647)22 puts("int");23 else24 puts("long long");25 }26 else if(str.size()==19)27 {28 if(str > Max)29 puts("It is too big!");30 else31 puts("long long");32 }33 else34 puts("It is too big!");35 }36 else37 {38 if(str.size() < 20)39 {40 sscanf(str.c_str(),"lld",&num);41 if(num >= -32767)42 puts("short");43 else if(num >= 2147483647)44 puts("int");45 else46 puts("long long");47 48 }49 else if(str.size() == 20)50 {51 str.erase(str.begin());52 if(str > Max)53 puts("It is too big!");54 else55 puts("long long");56 }57 else58 puts("It is too big!");59 60 }61 }62 }
I题要注意的就是最大公约数可能是负数的情况，导致负号出现在分母。应该处理一下再输出。
1 #include <stdio.h> 2 const int N = 1000 + 10; 3 int gcd(int n, int m) 4 { 5 if(m == 0) 6 return n; 7 return gcd(m,n%m); 8 } 9 int main()10 {11 int n, i;12 int coe,exp;13 while(scanf("%d",&n)!=EOF)14 {15 for(i=1; i<n; ++i)16 {17 scanf("%d%d",&coe,&exp);18 if( coe % (exp+1)==0)19 printf("%d %d ",coe / (exp+1),exp+1);20 else21 {22 int g = gcd(coe, exp+1);23 if(g>0)24 printf("%d/%d %d ",coe/g,(exp+1)/g, exp+1);25 else26 printf("%d/%d %d ",-coe/g,-(exp+1)/g, exp+1);27 28 } 29 }30 scanf("%d%d",&coe,&exp);31 if( coe % (exp+1)==0)32 printf("%d %d\n",coe / (exp+1),exp+1);33 else34 {35 int g = gcd(coe, exp+1);36 if(g>0)37 printf("%d/%d %d\n",coe/g,(exp+1)/g, exp+1);38 else39 printf("%d/%d %d\n",-coe/g,-(exp+1)/g, exp+1);40 } 41 }42 }
ACdream原创群赛(18)のAK's dream题解
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。