首页 > 代码库 > Educational Codeforces Round 16
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 long21 #define lson l,m,rt<<122 #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 }
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 long21 #define lson l,m,rt<<122 #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\n",a[(n+1)/2]);38 }
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 long21 #define lson l,m,rt<<122 #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 else54 {55 printf("%d ",y);56 y+=2;57 }58 printf("\n");59 }60 61 }
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 long21 #define lson l,m,rt<<122 #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\n",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 else78 {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\n",r-l+1>0 ? r-l+1 : 0 );91 }
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 long21 #define lson l,m,rt<<122 #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\n",f[n]);50 }
Problem F String Set Queries
Educational Codeforces Round 16
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。