商城网站模板免费,在线代理浏览网址,建筑面积计算规范2023下载最新版,江阴建设银行网站题目编号#xff1a;hdu 4257~4266 (对应比赛题号1001~1010) 这是我们第十二场组队赛#xff0c;在今天中午进行。 比赛刚开始#xff0c;依然是由我的队友读题。还没看几题#xff0c;就发现了好多题judge时长高达20秒#xff0c;这真的有点给我们心理造成压力。不过hdu 4257~4266 (对应比赛题号1001~1010) 这是我们第十二场组队赛在今天中午进行。 比赛刚开始依然是由我的队友读题。还没看几题就发现了好多题judge时长高达20秒这真的有点给我们心理造成压力。不过我们很快就缓解下来然后进入读题切题的状态。因为水平不足所以还是选择跟board做。开始没几分钟大board就有人过了1003于是我们就赶紧看1003了题目相当简短很快就看懂了是纸牌经过一系列操作以后得到另一个序列问操作多少次会再次出现初始序列。刚开始还打算打表来看看规律程序打出来了发现跑起来答案可以超过10^9就是说暴力是不可能的。不过队友还是叫我提交上去试试结果不言而喻开门一个TLE了。然后我就打了一个n到9的表让我的队友观察。十分庆幸的是我的队友以前做过置换群的题目所以很快就想到了可以用置换群来做。直接套入模板然后最后加了个特判提交上去AC了~ 代码如下优化的不太好时间大约要3s hdu 4259 View Code 1 #include cstdio2 3 const int maxn 801;4 typedef __int64 ll;5 int s[maxn][maxn], top[maxn];6 int pp[maxn];7 8 ll gcd(ll a, ll b){9 return b ? gcd(b, a % b) : a;
10 }
11
12 ll polya(int *perm, int n, int num){ // 求置换群循环节的长度
13 int i, j, p, v[maxn] {0};
14 ll cycle 1;
15
16 for (num i 0; i n; i){
17 if (!v[i]){
18 num;
19 p i;
20 for (j 0; !v[perm[p]]; j){
21 p perm[p];
22 v[p] 1;
23 }
24 cycle * j / gcd(cycle, j);
25 }
26 }
27
28 return cycle;
29 }
30
31 ll deal(int n, int m){ // 转换成置换群
32 for (int i 0; i m; i){
33 top[i] 0;
34 }
35 for (int i 0; i n; i){
36 int j i % m;
37 s[j][top[j]] i;
38 }
39
40 int k 0;
41
42 for (int i 0; i m; i){
43 while (top[i]){
44 pp[k] s[i][top[i] - 1];
45 top[i]--;
46 }
47 }
48 return polya(pp, n, k);
49 }
50
51 int main(){
52 int n, m;
53
54 while (~scanf(%d%d, n, m) (n || m)){
55 if (m n){
56 printf(1\n);
57 continue;
58 }
59 if (m 1){
60 printf(2\n);
61 continue;
62 }
63 printf(%I64d\n, deal(n, m));
64 }
65
66 return 0;
67 } 然后就是1004一道与汉诺塔有关的题。刚开始的时候打算用汉诺塔的原理来推出公式但是看了好些时间都没看出是应该怎么判断的。于是我就将碟数为3的8种情况都写出来了然后被我发现一个很有趣的规律描述如下 最后一个碟只可能是在A或B柱子上如果在A柱子上那么当前操作数就没有超过总数的一半。然后再观察倒数第二个碟子如果跟最后一个碟子的状态一样的话就是和最后一个碟子处于同一趋势。这里解释不太好如果换成代码语言就是从最后面开始判断假设有n1层碟子就设第n1个总是在A处。再说整个过程就是移动前n层的碟子到B所以第n1层总是在A的位置。然后就是判断了相邻两个碟子比较初始状态是第n1层是1如果不同就从1变成0否则保持不变。然后这样就可以得到一个长度为n的01串了。这个01串表示的值就是要输出的答案了 代码很简单(hdu 4260) View Code 1 #include cstdio2 #include cstring3 4 typedef __int64 ll;5 const int maxn 70;6 7 int main(){8 char s[maxn];9 ll ans, last;
10 int len;
11
12 while (~scanf(%s, s) s[0] ! X){
13 ans 0;
14 len strlen(s);
15 s[len] A;
16 last 1;
17 for (int i len - 1; i 0; i--){
18 if (s[i 1] ! s[i]) last (last 1) 1;
19 ans last i;
20 }
21 printf(%I64d\n, ans);
22 }
23
24 return 0;
25 } 然后就是1010了。题目是队友看的然后他将题意告诉我这是一个毫无掩饰的暴力三维凸包啊可是刚开始的时候队友因为从未写过凸包所以就说不敢做。不过凡是都应该有第一次的尝试就是这次要用尝试来较真而已。我们好不容易才搞到一个三维凸包的模板不过以前从未用过这样的模板所以刚开始的时候拿着模板看了好长时间先研究一下模板各个参数的含义。搞了个十来分钟最后看懂的各个变量的意思了然后就是打上去试用。打字还是慢啊花了近半个钟才抄完代码。然后我们将它当作黑箱随便测了一下返回的结果。没有问题然后就是将它放心的套入我们的暴力搜索的代码中去了 在封榜前3分钟提交上去1y~ 相当好的结果 代码(hdu 4266) View Code 1 #include cmath2 #include cstdio3 #include cstring4 #include cstdlib5 6 const int inf 0x7fffffff;7 #define max2(a, b) ((a) (b) ? (a) : (b))8 #define min2(a, b) ((a) (b) ? (a) : (b))9 const double eps 1e-7;10 const int maxn 1005;11 const double _4to5 5e-5;12 13 14 struct pt{15 double x, y, z;16 pt(){}17 pt(double _x, double _y, double _z): x(_x), y(_y), z(_z) {}18 pt operator - (const pt p1) {return pt(x - p1.x, y - p1.y, z - p1.z);}19 pt operator * (pt p) {return pt(y * p.z - z * p.y, z * p.x - x * p.z, x * p.y - y * p.x);}20 double operator ^ (pt p) {return x * p.x y * p.y z * p.z;}21 };22 23 void swap(int a, int b){24 int t a;25 a b;26 b t;27 }28 29 struct _3DCH{30 struct fac{31 int a, b, c;32 bool ok;33 };34 35 int n;36 pt P[maxn];37 38 int cnt;39 fac F[maxn * 8];40 41 int to[maxn][maxn];42 43 double vlen(pt a) {return sqrt(a.x * a.x a.y * a.y a.z * a.z);}44 double area(pt a, pt b, pt c) {return vlen((b - a) * (c - a));}45 double volume(pt a, pt b, pt c, pt d) {return (b - a) * (c - a) ^ (d - a);}46 47 double ptof(pt p, fac f){48 pt m P[f.b] - P[f.a], n P[f.c] - P[f.a], t p - P[f.a];49 return (m * n) ^ t;50 }51 void deal(int p, int a, int b){52 int f to[a][b];53 fac add;54 55 if (F[f].ok){56 if (ptof(P[p], F[f]) eps)57 dfs(p, f);58 else{59 add.a b, add.b a, add.c p, add.ok true;60 to[p][b] to[a][p] to[b][a] cnt;61 F[cnt] add;62 63 }64 }65 }66 67 void dfs(int p, int cur){68 F[cur].ok false;69 deal(p, F[cur].b, F[cur].a);70 deal(p, F[cur].c, F[cur].b);71 deal(p, F[cur].a, F[cur].c);72 }73 74 bool same(int s, int t){75 pt a P[F[s].a], b P[F[s].b], c P[F[s].c];76 return fabs(volume(a, b, c, P[F[t].a])) eps fabs(volume(a, b, c, P[F[t].b])) eps fabs(volume(a, b, c, P[F[t].c])) eps;77 }78 79 void construct(){80 cnt 0;81 if (n 4) return ;82 83 fac add;84 for (int i 0; i 4; i){85 add.a (i 1) % 4, add.b (i 2) % 4, add.c (i 3) % 4, add.ok 1;86 87 if (ptof(P[i], add) 0)88 swap(add.b, add.c);89 to[add.a][add.b] to[add.b][add.c] to[add.c][add.a] cnt;90 F[cnt] add;91 }92 93 for (int i 4; i n; i){94 for (int j 0; j cnt; j){95 if (F[j].ok ptof(P[i], F[j]) eps){96 dfs(i, j);97 break;98 }99 }
100 }
101
102 int tmp cnt;
103 cnt 0;
104 for (int i 0;i tmp; i){
105 if (F[i].ok){
106 F[cnt] F[i];
107 }
108 }
109 }
110
111 int facetCnt_tri(){
112 return cnt;
113 }
114 };
115
116 _3DCH hull;
117
118 double vlen(pt p){
119 return sqrt(p ^ p);
120 }
121
122 pt pvec(pt a, pt b, pt c){
123 return (a - b) * (b - c);
124 }
125
126 double ptoplane(pt p, int a, int b, int c){
127 return fabs((pvec(hull.P[a], hull.P[b], hull.P[c]) ^ (p - hull.P[a])) / vlen(pvec(hull.P[a], hull.P[b], hull.P[c])));
128 }
129
130 double final(pt a, int cnt){
131 double mindis 1e300;
132
133 for (int i 0; i cnt; i){
134 double dis ptoplane(a, hull.F[i].a, hull.F[i].b, hull.F[i].c); // 求点到面的距离
135
136 if (mindis dis) mindis dis;
137 }
138
139 return mindis;
140 }
141
142 int main(){
143 int cnt;
144
145 while (scanf(%d, hull.n) hull.n){
146 for (int i 0; i hull.n; i){
147 scanf(%lf%lf%lf, hull.P[i].x, hull.P[i].y, hull.P[i].z);
148 }
149 hull.construct(); // 构建凸包
150 cnt hull.facetCnt_tri(); // 凸包的三角形面的个数
151 #ifndef ONLINE_JUDGE
152 for (int i 0; i cnt; i){
153 printf(%3d %3d %3d\n, hull.F[i].a, hull.F[i].b, hull.F[i].c);
154 }
155 puts();
156 #endif
157 int m;
158 pt tmp;
159
160 scanf(%d, m);
161 while (m--){
162 scanf(%lf%lf%lf, tmp.x, tmp.y, tmp.z);
163 printf(%.4f\n, final(tmp, cnt)); // 暴力搜索最小解
164 }
165 }
166
167 return 0;
168 } 最后还有一个钟我们就尝试着做1007。1007当时是比较多人过的当时没想懂为什么求两次生成树得到一个范围然后如果k在这个范围里就是存在这样的生成树所以没敢将这个想法转换成代码 现在想起来就觉得后悔了因为当时还剩1个小时这题如果是尝试的话是绝对可能过的不过也算了吧今天的成绩还算是挺好的了下周依然要加把努力争取最后能够有质的飞跃 1007代码(hdu 4263) View Code 1 #include cstdio2 #include cstring3 #include cmath4 #include cstdlib5 #include algorithm6 #include queue7 8 using namespace std;9 10 const int maxn 1005;11 const int inf 0x7f7f7f7f;12 13 int eh[maxn], tt, dis[maxn];14 bool vis[maxn];15 struct edge{16 int s;17 int t;18 int c;19 void add(int _s, int _t, int _c){20 s _s;21 t _t;22 c _c;23 }24 bool operator (const edge x) const{25 return c x.c;26 }27 }E[maxn * maxn];28 priority_queueedge, vectoredge, lessedge Q;29 30 bool cmp(edge a, edge b){31 return a.s b.s;32 }33 34 void pre_prim(int n, int m){35 sort(E, E m, cmp);36 int p 0, k;37 38 for (int i 1; i n; i){39 eh[i] 0;40 }41 for (k 0; k m; k){42 while (p E[k].s) eh[p] k;43 }44 while (p n 1) {45 eh[p] m;46 }47 #ifndef ONLINE_JUDGE48 for (int i 0; i n 1; i){49 printf(%d : %d %d %d eh %d\n, i, E[i].s, E[i].t, E[i].c, eh[i]);50 }51 puts();52 #endif53 }54 55 int prim(int n, int m, int s){56 edge tmp;57 int ret 0;58 59 pre_prim(n, m);60 tmp.add(s, 0, 0);61 for (int i 1; i n; i){62 vis[i] false;63 dis[i] -inf;64 }65 while (Q.size()) Q.pop();66 Q.push(tmp);67 dis[s] 0;68 69 while (Q.size()){70 edge cur Q.top();71 Q.pop();72 73 int u cur.s, cost cur.c;74 if (vis[u]) continue;75 ret cost;76 vis[u] true;77 for (int i eh[u]; i eh[u 1]; i){78 int v E[i].t;79 80 if (!vis[v] dis[v] E[i].c){81 dis[v] E[i].c;82 cur.add(v, 0, dis[v]);83 Q.push(cur);84 }85 }86 }87 88 return ret;89 }90 91 void reverse(int m){92 for (int i 0; i m; i){93 E[i].c;94 E[i].c 1;95 }96 }97 98 bool deal(int n, int m, int k){99 int high, low;
100
101 high prim(n, m, 1);
102 reverse(m);
103 low prim(n, m, 1);
104 low n - low - 1;
105 #ifndef ONLINE_JUDGE
106 printf(%d %d\n, high, low);
107 #endif
108 return low k k high;
109 }
110
111 int main(){
112 int n, m, k;
113 int s, t, i1, i2;
114 char cl[3];
115
116 #ifndef ONLINE_JUDGE
117 freopen(in, r, stdin);
118 #endif
119 while (~scanf(%d%d%d, n, m, k) (n || m || k)){
120 for (int i 0; i m; i){
121 scanf(%s%d%d, cl, s, t);
122 i1 i 1;
123 i2 i 1 | 1;
124 E[i1].add(s, t, cl[0] B);
125 E[i2].add(t, s, cl[0] B);
126 }
127 printf(%d\n, deal(n, m 1, k));
128 }
129
130 return 0;
131 } ——written by Lyon 转载于:https://www.cnblogs.com/LyonLys/archive/2012/08/26/2012_08_25_Lyon.html
