Educational Codeforces Round 16

Problem A King Moves

题目大意

　　有一个国际象棋的棋盘，给定一个国王的位置，求其移动一步可到达的合法位置数量。

解题分析

　　国王的位置可以分为3类，每类的答案为8、5、3。

参考程序

 1 #include <map>
 2 #include <set>
 3 #include <stack>
 4 #include <queue>
 5 #include <cmath>
 6 #include <ctime>
 7 #include <string>
 8 #include <vector>
 9 #include <cstdio>
10 #include <cstdlib>
11 #include <cstring>
12 #include <cassert>
13 #include <iostream>
14 #include <algorithm>
15 #pragma comment(linker,"/STACK:102400000,102400000")
16 using namespace std;
17 
18 #define N 508             
19 #define M 50008    
20 #define LL long long
21 #define lson l,m,rt<<1
22 #define rson m+1,r,rt<<1|1 
23 #define clr(x,v) memset(x,v,sizeof(x));
24 #define bitcnt(x) __builtin_popcount(x)
25 #define rep(x,y,z) for (int x=y;x<=z;x++)
26 #define repd(x,y,z) for (int x=y;x>=z;x--)
27 const int mo  = 1000000007;
28 const int inf = 0x3f3f3f3f;
29 const int INF = 2000000000;
30 /**************************************************************************/ 
31 
32 int main(){
33     char c,n;
34     scanf("%c%c",&c,&n);
35     int num=0;
36     if (c=='a' || c=='h') num++;
37     if (n=='1' || n=='8') num++;
38     if (num==0) puts("8");
39     if (num==1) puts("5");
40     if (num==2) puts("3");
41 }
View Code

Problem B Optimal Point on a Line

题目大意

　　在一条直线上有n个点，求某个点使得其到其他点的距离之和最小。

解题分析

　　排序之后输出正中间的点即可。

参考程序

 1 #include <map>
 2 #include <set>
 3 #include <stack>
 4 #include <queue>
 5 #include <cmath>
 6 #include <ctime>
 7 #include <string>
 8 #include <vector>
 9 #include <cstdio>
10 #include <cstdlib>
11 #include <cstring>
12 #include <cassert>
13 #include <iostream>
14 #include <algorithm>
15 #pragma comment(linker,"/STACK:102400000,102400000")
16 using namespace std;
17 
18 #define N 508             
19 #define M 50008    
20 #define LL long long
21 #define lson l,m,rt<<1
22 #define rson m+1,r,rt<<1|1 
23 #define clr(x,v) memset(x,v,sizeof(x));
24 #define bitcnt(x) __builtin_popcount(x)
25 #define rep(x,y,z) for (int x=y;x<=z;x++)
26 #define repd(x,y,z) for (int x=y;x>=z;x--)
27 const int mo  = 1000000007;
28 const int inf = 0x3f3f3f3f;
29 const int INF = 2000000000;
30 /**************************************************************************/ 
31 int n; 
32 int a[300008];
33 int main(){
34     scanf("%d",&n);
35     rep(i,1,n) scanf("%d",&a[i]);
36     sort(a+1,a+n+1);
37     printf("%d
",a[(n+1)/2]);
38 }
View Code

Problem C Magic Odd Square

题目大意

　　将1~n^2的数字填入n*n的矩形，使得每行每列每条正对角线的数字之和均为奇数。

　　n <= 49 , 且n为奇数。

解题分析

　　通过观察样例和探索后可以发现一种合法的构造方案。

　　在n*n的矩形正中间放置一个完全由奇数组成的旋转45度的（n-1）*（n-1）的矩形。

参考程序

 1 #include <map>
 2 #include <set>
 3 #include <stack>
 4 #include <queue>
 5 #include <cmath>
 6 #include <ctime>
 7 #include <string>
 8 #include <vector>
 9 #include <cstdio>
10 #include <cstdlib>
11 #include <cstring>
12 #include <cassert>
13 #include <iostream>
14 #include <algorithm>
15 #pragma comment(linker,"/STACK:102400000,102400000")
16 using namespace std;
17 
18 #define N 508             
19 #define M 50008    
20 #define LL long long
21 #define lson l,m,rt<<1
22 #define rson m+1,r,rt<<1|1 
23 #define clr(x,v) memset(x,v,sizeof(x));
24 #define bitcnt(x) __builtin_popcount(x)
25 #define rep(x,y,z) for (int x=y;x<=z;x++)
26 #define repd(x,y,z) for (int x=y;x>=z;x--)
27 const int mo  = 1000000007;
28 const int inf = 0x3f3f3f3f;
29 const int INF = 2000000000;
30 /**************************************************************************/ 
31 int n,x,y; 
32 int a[108][108];
33 int main(){
34     scanf("%d",&n);
35     int mid=(n+1)/2;
36     rep(i,1,mid){
37         rep(j,mid-i+1,mid+i-1)
38             a[i][j]=1;
39     }
40     rep(i,1,mid-1){
41         rep(j,mid-i+1,mid+i-1)
42             a[n-i+1][j]=1;
43     }
44     x=1; y=2;
45     rep(i,1,n)
46     {
47         rep(j,1,n)
48             if (a[i][j]==1)
49             {
50                 printf("%d ",x);
51                 x+=2;
52             }
53             else
54             {
55                 printf("%d ",y);
56                 y+=2;
57             }
58         printf("
");
59     }
60 
61 }
View Code

Problem D Two Arithmetic Progressions

题目大意

　　给定a1, b1, a2, b2, L, R (0 < a1, a2 ≤ 2·109,  - 2·109 ≤ b1, b2, L, R ≤ 2·109, L ≤ R)。

　　求所有满足条件的x的数量，x=a1*k+b1=a2*l+b2,且 L≤x≤R。

解题分析

　　x=a1*k'+b1=a2*l'+b2

　　移项后可得 a1*k-a2*l=b2-b1。

　　用exgcd解出最小的k',l'。

　　则k=k'+(a2/gcd(a1,a2))*m。

　　由 k>=0 ，l>=0 和 L<=a1*k+b1<=R 解出m的范围。 

参考程序

 1 #include <map>
 2 #include <set>
 3 #include <stack>
 4 #include <queue>
 5 #include <cmath>
 6 #include <ctime>
 7 #include <string>
 8 #include <vector>
 9 #include <cstdio>
10 #include <cstdlib>
11 #include <cstring>
12 #include <cassert>
13 #include <iostream>
14 #include <algorithm>
15 #pragma comment(linker,"/STACK:102400000,102400000")
16 using namespace std;
17 
18 #define N 508             
19 #define M 50008    
20 #define LL long long
21 #define lson l,m,rt<<1
22 #define rson m+1,r,rt<<1|1 
23 #define clr(x,v) memset(x,v,sizeof(x));
24 #define bitcnt(x) __builtin_popcount(x)
25 #define rep(x,y,z) for (int x=y;x<=z;x++)
26 #define repd(x,y,z) for (int x=y;x>=z;x--)
27 const int mo  = 1000000007;
28 const int inf = 0x3f3f3f3f;
29 const LL INF = 20000000000000ll;
30 /**************************************************************************/ 
31 
32 LL a1,b1,a2,b2,L,R,x,y,d;
33 
34 LL gcd(LL x,LL y){
35     return y == 0 ? x : gcd(y,x % y);
36 }
37 
38 LL exgcd(LL a,LL b,LL &x,LL &y){
39     if (b==0){
40         x=1;
41         y=0;
42         return a; 
43     }
44     LL d=exgcd(b,a%b,y,x);
45     y-=x*(a/b);
46     return d;
47 }
48 LL up(LL x,LL y){
49     if (x>0) return x % y ? x / y + 1 : x / y;   
50     return x / y;
51 }
52 LL down(LL x,LL y){
53     if (x>0) return x / y;
54     return x % y ? x / y - 1 : x / y;
55 }
56 int main(){
57     scanf("%lld%lld%lld%lld%lld%lld",&a1,&b1,&a2,&b2,&L,&R);
58     d=exgcd(a1,-a2,x,y);
59     if ((b2-b1) % d!=0){
60         printf("%d
",0);
61         return 0;
62     }
63     LL k0 = x * (b2-b1) / d;
64     k0 =(k0 % (a2/d) + (a2/d)) % (a2/d);
65     LL l0 = (a1*k0+b1-b2) /a2;
66 
67    // cout << k0 << " " << l0 << endl;
68     LL l,r,ll,lll,rr,rrr;
69     if (d>0)
70     {
71         r = down((R-a1*k0-b1)*d,a1*a2);
72         l = up((L-a1*k0-b1)*d,a1*a2);
73         ll = up(-k0*d,a2);
74         lll = up(-l0*d,a1);
75         l=max(max(ll,lll),l);
76     }
77     else
78     {
79         l = up((R-a1*k0-b1)*d,a1*a2);
80         r = down((L-a1*k0-b1)*d,a1*a2);
81         rr = down(-k0*d,a2);
82         rrr = down(-l0*d,a1);
83         r=min(min(rr,rrr),r);    
84 
85         LL x1 = (R-a1*k0-b1)*d ; 
86         LL x2 = (L-a1*k0-b1)*d ;
87         LL y1 = a1 * a2;
88         
89     }
90     printf("%lld
",r-l+1>0 ? r-l+1 : 0 );
91 }
View Code

Problem E Generate a String

题目大意

　　每次操作可以花费x的代价将数字加1或减1，或者花费y的代价将数字乘2。

　　求将数字从0变到数字n的最小代价。

　　n<=10^7。

解题分析

　　可以发现一个显然的dp方程

　　　　dp[i]=min{dp[i-1]+x,dp[i+1]+x,dp[i/2]+y(2|i)}

　　由于n很大，不能高斯消元。

　　经过思考后可以发现-1的操作不会连续执行两次（必然可以通过+1和*2来代替）。

　　所以每次dp[i]时，顺便求出dp[i+1],再由dp[i+1]来更新dp[i]。　　

参考程序

 1 #include <map>
 2 #include <set>
 3 #include <stack>
 4 #include <queue>
 5 #include <cmath>
 6 #include <ctime>
 7 #include <string>
 8 #include <vector>
 9 #include <cstdio>
10 #include <cstdlib>
11 #include <cstring>
12 #include <cassert>
13 #include <iostream>
14 #include <algorithm>
15 #pragma comment(linker,"/STACK:102400000,102400000")
16 using namespace std;
17 
18 #define N 508             
19 #define M 50008    
20 #define LL long long
21 #define lson l,m,rt<<1
22 #define rson m+1,r,rt<<1|1 
23 #define clr(x,v) memset(x,v,sizeof(x));
24 #define bitcnt(x) __builtin_popcount(x)
25 #define rep(x,y,z) for (int x=y;x<=z;x++)
26 #define repd(x,y,z) for (int x=y;x>=z;x--)
27 const int mo  = 1000000007;
28 const int inf = 0x3f3f3f3f;
29 const int INF = 2000000000;
30 /**************************************************************************/ 
31 
32 LL f[10000008];
33 
34 int n,x,y;
35 
36 int main(){
37     scanf("%d%d%d",&n,&x,&y);
38     f[0]=0;
39     rep(i,1,n){
40         f[i]=f[i-1]+x;
41         if (i % 2 == 0) f[i]=min(f[i],f[i/2]+y);
42         
43         f[i+1]=f[i]+x;
44         if ((i+1) % 2==0) f[i+1]=min(f[i+1],f[(i+1)/2]+y);
45 
46         f[i]=min(f[i],f[i+1]+x);
47 
48     }
49     printf("%I64d
",f[n]);
50 }
View Code

Problem F String Set Queries

【推广】 免费学中医，健康全家人
原文地址：https://www.cnblogs.com/rpSebastian/p/5817570.html