首页 > 代码库 > Codeforces Round #259 (Div. 2) 解题报告
Codeforces Round #259 (Div. 2) 解题报告
终于重上DIV1了。。。。
A：在正方形中输出一个菱形
解题代码：
1 // File Name: a.cpp 2 // Author: darkdream 3 // Created Time: 2014年08月01日 星期五 23时27分55秒 4 5 #include<vector> 6 #include<set> 7 #include<deque> 8 #include<stack> 9 #include<bitset>10 #include<algorithm>11 #include<functional>12 #include<numeric>13 #include<utility>14 #include<sstream>15 #include<iostream>16 #include<iomanip>17 #include<cstdio>18 #include<cmath>19 #include<cstdlib>20 #include<cstring>21 #include<ctime>22 23 #define LL long long24 using namespace std;25 int a[104][104];26 int main(){27 int n;28 memset(a,0,sizeof(a));29 scanf("%d",&n);30 int t = n/2+1;31 int be = t;32 for(int i = 1;i <= n;i ++)33 {34 if(i <= t)35 {36 for(int j = be ;j <= be + i*2-2 ;j ++)37 a[i][j] = 1;38 be --;39 }else{40 if(i == t + 1)41 be = 2;42 else 43 be ++ ; 44 for(int j = be;j <= be +(n-i+1)*2-2;j ++)45 a[i][j] = 1;46 }47 }48 for(int i =1 ;i <= n;i ++)49 {50 for(int j = 1;j <= n;j++)51 {52 if(a[i][j])53 printf("D");54 else printf("*");55 }56 printf("\n");57 }58 return 0;59 }
B:问一个循环序列是否可以变成不递减的序列，如果可以，输出循环最小步数
解题代码：
1 // File Name: b.cpp 2 // Author: darkdream 3 // Created Time: 2014年08月01日 星期五 23时41分55秒 4 5 #include<vector> 6 #include<list> 7 #include<map> 8 #include<set> 9 #include<deque>10 #include<stack>11 #include<bitset>12 #include<algorithm>13 #include<functional>14 #include<numeric>15 #include<utility>16 #include<sstream>17 #include<iostream>18 #include<iomanip>19 #include<cstdio>20 #include<cmath>21 #include<cstdlib>22 #include<cstring>23 #include<ctime>24 25 #define LL long long26 using namespace std;27 int a[200005];28 int main(){29 int n ;30 scanf("%d",&n);31 int ok = 0 ;32 a[0] = 0 ;33 int be = 0 ; 34 for(int i =1 ;i <= n;i ++)35 {36 scanf("%d",&a[i]);37 if(a[i] < a[i-1] && !ok)38 {39 ok = 1;40 be = i ; 41 }42 }43 if(ok == 0 )44 {45 printf("0\n");46 return 0;47 }48 for(int i = 1 ;i <= n;i ++)49 a[i+n] = a[i];50 ok =0 ;51 for(int i = be +1;i<= be +n -1;i ++)52 {53 if(a[i] < a[i-1])54 {55 ok = 1 ;56 break;57 }58 }59 if(ok == 0 )60 printf("%d\n",n-be + 1);61 else printf("-1\n");62 return 0;63 }
C：问你 有m面的筛子，投n次，最大的那个数的期望值是多少
解题思路：可知如果都为 1 ，那么 几率为（1/m）^n
既有1又有2且仅有 1,2 那么 几率为 （2/m）^n ，那么 答案为一的几率 就是 (2/m)^n - (1/m)^n以此递推，答案为 x 的几率为 (x/m)^n - ((x-1)/m)^n，所以累加即为答案解题代码：1 // File Name: c.cpp 2 // Author: darkdream 3 // Created Time: 2014年08月02日 星期六 00时14分13秒 4 5 #include<vector> 6 #include<list> 7 #include<map> 8 #include<set> 9 #include<deque>10 #include<stack>11 #include<bitset>12 #include<algorithm>13 #include<functional>14 #include<numeric>15 #include<utility>16 #include<sstream>17 #include<iostream>18 #include<iomanip>19 #include<cstdio>20 #include<cmath>21 #include<cstdlib>22 #include<cstring>23 #include<ctime>24 25 #define LL long long26 using namespace std;27 double P(double x,int n)28 {29 if(n == 1)30 return x; 31 double t = P(x,n/2);32 if(n % 2 == 0)33 {34 return t*t; 35 }else{36 return t*t*x;37 }38 }39 double a[100005];40 int main(){41 int n , m; 42 scanf("%d %d",&m,&n);43 double ans ;44 a[1] = ans = P(1.0/m,n);45 for(int i = 2;i <= m;i ++)46 {47 a[i] = P(i*1.0/m,n);48 ans += i *(a[i] - a[i-1]);49 }50 printf("%lf\n",ans);51 return 0;52 }
D：给你长度为n的数组，让你构造一个数组使得b数组两两互质且 |Bi - Ai| 累加和最小
解题思路： DP + 2进制运算，DP[i][j]表示第i个 状态为j 的最小累加和，每一种状态都用 1-60的情况去枚举 然后2进制快速判断是否满足条件，就可以DP出答案了
解题代码：
1 // File Name: 454d.cpp 2 // Author: darkdream 3 // Created Time: 2014年08月02日 星期六 18时29分50秒 4 5 #include<vector> 6 #include<list> 7 #include<map> 8 #include<set> 9 #include<deque> 10 #include<stack> 11 #include<bitset> 12 #include<algorithm> 13 #include<functional> 14 #include<numeric> 15 #include<utility> 16 #include<sstream> 17 #include<iostream> 18 #include<iomanip> 19 #include<cstdio> 20 #include<cmath> 21 #include<cstdlib> 22 #include<cstring> 23 #include<ctime> 24 25 #define LL long long 26 using namespace std; 27 int n ; 28 int hs[40]; 29 int b[40]; 30 int lb = 0 ; 31 int p2[30]; 32 int fuck[66]; 33 void init() 34 { 35 memset(hs,0,sizeof(hs)); 36 for(int i = 2 ;i <= 60 ;i ++) 37 { 38 int ok = 1 ; 39 for(int j =2;j < i ;j ++) 40 if(i % j == 0 ) 41 ok = 0 ; 42 if(ok == 1) 43 { 44 lb ++ ; 45 b[lb] = i ; 46 } 47 } 48 p2[1] = 1; 49 for(int i= 2;i <= 20;i ++) 50 p2[i] = p2[i-1] * 2; 51 memset(fuck,0,sizeof(fuck)); 52 for(int i =2;i <= 60 ;i ++) 53 { 54 for(int j = 1;j <= lb ;j ++) 55 if(i % b[j] == 0 ) 56 fuck[i] += p2[j]; 57 } 58 } 59 const int mx = 1 << 17; 60 int dp[101][mx+10]; 61 struct node{ 62 int from; 63 int num; 64 }exdp[101][mx+10]; 65 int rans[40] = {0}; 66 int a[104]; 67 void dfs(int n,int k) 68 { 69 if(k == 0 ) 70 return; 71 dfs(exdp[k][n].from,k-1); 72 printf("%d ",exdp[k][n].num); 73 } 74 int main(){ 75 init(); 76 //printf("%d",sizeof(dp)/4); 77 scanf("%d",&n); 78 for(int i =1 ;i <= n;i ++) 79 { 80 int temp ; 81 scanf("%d",&a[i]); 82 hs[a[i]] ++; 83 } 84 memset(dp,0xff,sizeof(dp)); 85 dp[0][0] = 0 ; 86 for(int i =1;i <= n;i ++) 87 { 88 for(int j = 0 ;j <= mx;j ++) 89 { 90 if(dp[i-1][j] != -1) 91 { 92 for(int s = 2;s <= 60;s ++) 93 { 94 if((j & fuck[s]) == 0 ) 95 { 96 int t = j^fuck[s]; 97 int ans = dp[i-1][j] + abs(s-a[i]); 98 if(ans < dp[i][t] || dp[i][t] == -1 ) 99 {100 dp[i][t] = ans ; 101 exdp[i][t].from = j;102 exdp[i][t].num = s;103 }104 }105 }106 int ans = dp[i-1][j] + abs(1-a[i]);107 if(ans < dp[i][j] || dp[i][j] == -1) 108 {109 dp[i][j] = ans ; 110 exdp[i][j].from = j;111 exdp[i][j].num = 1;112 }113 }114 }115 }116 int anssum = 1e9 ; 117 int ansnum = 0 ;118 for(int i = 0 ;i <= mx ;i ++)119 {120 if(dp[n][i] != -1 && anssum > dp[n][i])121 { 122 anssum = dp[n][i];123 ansnum = i ; 124 }125 }126 dfs(ansnum,n);127 return 0;128 }
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。