首页 > 代码库 > ZOJ Monthly, November 2014
ZOJ Monthly, November 2014
做了一次月赛，没想到这么难，加上后来补上的题目也只有3个题。第一名也只有4个题啊啊啊啊~.其中两道还是水题。留坑慢慢补上来。
3832 Tilt Cylinder
给定如图所示有盖圆柱体，R，H,水面高度h，倾角a，求水得体积。
分析：明显的数值积分题，这样考虑。圆下底面即A点与地面高度lim1, 圆上底面一点B与地面高度lim2,h所处的范围进行讨论从而确定积分几何体的两边的高度。我们积分的几何体应该是一个圆柱体被削掉一部分了。
h>lim1时，几何体左半部分可以减掉一个圆柱，对剩下部分积分，剩下部分左边截面的高度2*R；否则高度为2*R/cos(a);
h>lim2时，几何体右半部分截面的高度需要计算，为(h-lim2)/cos(a);否则为0.
注意：这里所说的结合体截面的高度是相对与下面的母线而言，并不是对地高度。
然后对上面给出的高度范围结合夹角a进行积分，需要推导截面的面积。最后答案需要加上截掉的那部分完整的圆柱体体积（如果是那种情况的话）。
代码：
1 #include <bits/stdc++.h> 2 #define pb push_back 3 #define mp make_pair 4 #define esp 1e-12 5 #define lowbit(x) ((x)&(-x)) 6 #define lson l, m, rt<<1 7 #define rson m+1, r, rt<<1|1 8 #define sz(x) ((int)((x).size())) 9 #define pb push_back 10 #define pf(x) ((x)*(x)) 11 12 #define pi acos(-1.0) 13 14 #define in freopen("solve_in.txt", "r", stdin); 15 #define out freopen("solve_out.txt", "w", stdout); 16 17 #define bug(x) printf("Line : %u >>>>>>\n", (x)); 18 #define inf 0x0f0f0f0f 19 using namespace std; 20 21 22 int dblcmp(double x) { 23 if(fabs(x) < esp) return 0; 24 return x > 0 ? 1 : -1; 25 } 26 const int N = 200; 27 double R, H, a, h; 28 double f1(double x) { 29 double cth = (R-x)/R; 30 return acos(cth)*pf(R)-(R-x)*sqrt(pf(R)-pf(R-x)); 31 } 32 double f2(double x) { 33 double cth = (x-R)/R; 34 return (pi-acos(cth))*pf(R)+(x-R)*sqrt(pf(R)-pf(x-R)); 35 } 36 double s1(double l, double r) { 37 double x = 0, y = (l-r)/tan(a); 38 double h0 = (y-x)/N; 39 40 double res = 0.0; 41 res = f1(l)+f1(r); 42 for(int i = 1; i <= N; i++) { 43 if(i < N) 44 res += 2*f1(l-(x+i*h0)*tan(a)); 45 res += 4*f1(l-(x+(2*i-1)*h0/2)*tan(a)); 46 } 47 return res*h0/6; 48 49 } 50 double s2(double l, double r) { 51 double x = 0, y = (l-r)/tan(a); 52 double h0 = (y-x)/N; 53 54 double res = 0.0; 55 res = f2(l)+f2(r); 56 for(int i = 1; i <= N; i++) { 57 if(i < N) 58 res += 2*f2(l-(x+i*h0)*tan(a)); 59 res += 4*f2(l-(x+(2*i-1)*h0/2)*tan(a)); 60 } 61 return res*h0/6; 62 } 63 64 double getAns(double h0, double h1) { 65 if(h1 > R) { 66 return s2(h0, h1); 67 } else if(h0 < R) { 68 return s1(h0, h1); 69 } else { 70 return s2(h0, R)+s1(R, h1); 71 } 72 } 73 int main() { 74 75 while(scanf("%lf%lf%lf%lf", &R, &H, &h, &a) == 4) { 76 double res = 0.0; 77 if(fabs(a) > esp && fabs(a-90.0) > esp) { 78 a = a*pi/180.0; 79 double lim2 = sin(a)*H; 80 double lim1 = 2*R*cos(a); 81 82 double h1, h2; 83 if(h > lim1) { 84 h1 = 2*R; 85 res += pi*pf(R)*(h/sin(a)-2*R/tan(a)); 86 } else { 87 h1 = h/cos(a); 88 } 89 if(h > lim2) { 90 h2 = (h-lim2)/cos(a); 91 } else { 92 h2 = 0.0; 93 } 94 res += getAns(h1, h2); 95 96 } else { 97 if(fabs(a) < esp) { 98 double Sr; 99 if(h > R){100 Sr = f2(h);101 }else{102 Sr = f1(h);103 }104 res = Sr*H;105 } else {106 res = pi*pf(R)*h;107 }108 }109 printf("%.12f\n", res);110 }111 return 0;112 }
3839 Poker Face
分析：第n个是将第n/2个倒插进去然后加上眼睛等部分。
代码：
1 #include <bits/stdc++.h> 2 #define pb push_back 3 #define mp make_pair 4 #define esp 1e-8 5 #define lowbit(x) ((x)&(-x)) 6 #define lson l, m, rt<<1 7 #define rson m+1, r, rt<<1|1 8 #define sz(x) ((int)((x).size())) 9 #define pb push_back10 #define in freopen("solve_in.txt", "r", stdin);11 #define out freopen("solve_out.txt", "w", stdout);12 13 #define bug(x) printf("Line : %u >>>>>>\n", (x));14 #define inf 0x0f0f0f0f15 #define Fill(x, b1, b2, l, r) {16 for(int i = 0; i < l; i++)17 maze[x][i+b1][b2] = maze[x][i+b1][b2+r-1] = ‘*‘;18 for(int i = 0; i < r; i++)19 maze[x][b1][i+b2] = maze[x][b1+l-1][i+b2] = ‘*‘;20 }21 22 using namespace std;23 typedef long long LL;24 typedef pair<int, int> PII;25 typedef map<string, int> MPS;26 27 using namespace std;28 const int maxn = 1100;29 char s[maxn][maxn] = {30 {"********"}, {"*** ***"}, {"*** ***"}, {"*** ***"}, {"* **** *"}, {"* * * *"},31 {"* * * *"}, {"********"}32 };33 34 char maze[12][maxn][maxn];35 36 int popcount(int x){37 int ans = 0;38 while(1){39 if(x&1) break;40 ans++;41 x >>= 1;42 }43 return ans;44 }45 void dfs(int n){46 if(n <= 8) return;47 int x = popcount(n);48 // cout << x << endl;49 for(int i = 0; i < n; i++) for(int j = 0; j < n; j++)50 maze[x][i][j] = ‘ ‘;51 Fill(x, 0, 0, n, n)52 int st1 = n/8, st2 = st1+n/2;53 Fill(x, n/8, st1, n/4+1, n/4)54 Fill(x, n/8, st2, n/4+1, n/4)55 dfs(n>>1);56 int b1 = n/2, b2 = n/4;57 int nn = n>>1;58 for(int i = 0; i < (n>>1); i++)59 for(int j = 0; j < (n>>1); j++){60 maze[x][b1+i][b2+j] = maze[x-1][nn-1-i][nn-1-j];61 }62 }63 int main() {64 65 int n;66 for(int i = 0; i < 8; i++)67 strcpy(maze[3][i], s[i]);68 dfs(1024);69 70 while(scanf("%d", &n), n >= 8) {71 // cout << n <<endl;72 int x = popcount(n);73 // cout << x << endl;74 for(int i = 0; i < n; i++)75 puts(maze[x][i]);76 puts("");77 }78 return 0;79 }
3838 Infusion Altar
分析：对每个点和其对称点访问一遍，将数目最多的那种保留，其他全部替换成这种。
代码：
1 #include <bits/stdc++.h> 2 #define pb push_back 3 #define mp make_pair 4 #define esp 1e-8 5 #define lowbit(x) ((x)&(-x)) 6 #define lson l, m, rt<<1 7 #define rson m+1, r, rt<<1|1 8 #define sz(x) ((int)((x).size())) 9 #define pb push_back10 #define in freopen("solve_in.txt", "r", stdin);11 #define out freopen("solve_out.txt", "w", stdout);12 13 #define bug(x) printf("Line : %u >>>>>>\n", (x));14 #define inf 0x0f0f0f0f15 using namespace std;16 const int maxn = 110;17 char maze[maxn][maxn];18 int vis[maxn][maxn];19 vector<char> tmp;20 int n;21 22 void dfs(int x, int y){23 if(vis[x][y]) return;24 vis[x][y] = 1;25 tmp.pb(maze[x][y]);26 dfs(y, x);27 dfs(n-1-y, n-1-x);28 dfs(n-1-x, y);29 dfs(x, n-1-y);30 }31 int main(){32 33 int T;34 for(int t = scanf("%d", &T); t <= T; t++){35 scanf("%d", &n);36 int ans = 0;37 for(int i = 0; i < n; i++)38 scanf("%s", maze[i]);39 // for(int i = 0; i < n; i++)40 // cout << maze[i];41 memset(vis, 0, sizeof vis);42 for(int i = 0; i < n; i++)for(int j = 0; j < n; j++){43 if(vis[i][j]) continue;44 tmp.clear();45 dfs(i, j);46 sort(tmp.begin(), tmp.end());47 int jj;48 int mx = 0;49 for(int ii = 0; ii < sz(tmp); ii = jj){50 int ok = 0;51 for(jj = ii; jj < sz(tmp) && tmp[jj] == tmp[ii]; jj++)52 ok++;53 mx = max(ok, mx);54 }55 ans += sz(tmp)-mx;56 }57 cout << ans << endl;58 }59 return 0;60 }
ZOJ Monthly, November 2014
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。