題目編號：hdu 4257~4266 (對應(yīng)比賽題號1001~1010)

　　這是我們第十二場組隊(duì)賽，在今天中午進(jìn)行。

　　比賽剛開始，依然是由我的隊(duì)友讀題。還沒看幾題，就發(fā)現(xiàn)了好多題judge時長高達(dá)20秒，這真的有點(diǎn)給我們心理造成壓力。不過，我們很快就緩解下來，然后進(jìn)入讀題切題的狀態(tài)。因?yàn)樗讲蛔?#xff0c;所以還是選擇跟board做。開始沒幾分鐘，大board就有人過了1003，于是我們就趕緊看1003了！題目相當(dāng)簡短，很快就看懂了是紙牌經(jīng)過一系列操作以后得到另一個序列，問操作多少次會再次出現(xiàn)初始序列。剛開始還打算打表來看看規(guī)律，程序打出來了，發(fā)現(xiàn)跑起來，答案可以超過10^9，就是說暴力是不可能的。不過隊(duì)友還是叫我提交上去試試，結(jié)果不言而喻，開門一個TLE了。然后我就打了一個n到9的表，讓我的隊(duì)友觀察。十分慶幸的是，我的隊(duì)友以前做過置換群的題目，所以很快就想到了可以用置換群來做。直接套入模板，然后最后加了個特判，提交上去，AC了~

代碼如下（優(yōu)化的不太好，時間大約要3s hdu 4259）：

View Code 1 #include <cstdio> 2 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){ // 求置換群循環(huán)節(jié)的長度 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){ // 轉(zhuǎn)換成置換群 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，一道與漢諾塔有關(guān)的題。剛開始的時候，打算用漢諾塔的原理來推出公式，但是看了好些時間都沒看出是應(yīng)該怎么判斷的。于是我就將碟數(shù)為3的8種情況都寫出來了，然后被我發(fā)現(xiàn)一個很有趣的規(guī)律，描述如下：

　　最后一個碟只可能是在A或B柱子上，如果在A柱子上，那么當(dāng)前操作數(shù)就沒有超過總數(shù)的一半。然后再觀察倒數(shù)第二個碟子，如果跟最后一個碟子的狀態(tài)一樣的話，就是和最后一個碟子處于同一趨勢。這里解釋不太好，如果換成代碼語言就是，從最后面開始判斷，假設(shè)有n+1層碟子，就設(shè)第n+1個總是在A處。再說，整個過程就是移動前n層的碟子到B，所以第n+1層總是在A的位置。然后就是判斷了，相鄰兩個碟子比較，初始狀態(tài)是第n+1層是1，如果不同，就從1變成0，否則保持不變。然后，這樣就可以得到一個長度為n的01串了。這個01串表示的值就是要輸出的答案了！

代碼很簡單(hdu 4260)：

View Code 1 #include <cstdio> 2 #include <cstring> 3 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了。題目是隊(duì)友看的，然后他將題意告訴我，這是一個毫無掩飾的暴力三維凸包啊！可是剛開始的時候，隊(duì)友因?yàn)閺奈磳戇^凸包，所以就說不敢做。不過，凡是都應(yīng)該有第一次的嘗試，就是這次要用嘗試來較真而已。我們好不容易才搞到一個三維凸包的模板，不過以前從未用過這樣的模板，所以剛開始的時候拿著模板看了好長時間，先研究一下模板各個參數(shù)的含義。搞了個十來分鐘，最后看懂的各個變量的意思了，然后就是打上去試用。打字還是慢啊，花了近半個鐘才抄完代碼。然后，我們將它當(dāng)作黑箱，隨便測了一下返回的結(jié)果。沒有問題！然后就是將它放心的套入我們的暴力搜索的代碼中去了！ ?在封榜前3分鐘，提交上去，1y~ ?相當(dāng)好的結(jié)果！

代碼(hdu 4266)：

View Code 1 #include <cmath> 2 #include <cstdio> 3 #include <cstring> 4 #include <cstdlib> 5 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); // 求點(diǎn)到面的距離 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(); // 構(gòu)建凸包 150 cnt = hull.facetCnt_tri(); // 凸包的三角形面的個數(shù) 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當(dāng)時是比較多人過的，當(dāng)時沒想懂為什么求兩次生成樹得到一個范圍，然后如果k在這個范圍里就是存在這樣的生成樹，所以沒敢將這個想法轉(zhuǎn)換成代碼！ ?現(xiàn)在想起來就覺得后悔了，因?yàn)楫?dāng)時還剩1個小時，這題如果是嘗試的話是絕對可能過的！不過也算了吧，今天的成績還算是挺好的了！下周依然要加把努力，爭取最后能夠有質(zhì)的飛躍！

?

1007代碼(hdu 4263)：

View Code 1 #include <cstdio> 2 #include <cstring> 3 #include <cmath> 4 #include <cstdlib> 5 #include <algorithm> 6 #include <queue> 7 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_queue<edge, vector<edge>, less<edge> > 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_JUDGE 48 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 #endif 53 } 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

?

轉(zhuǎn)載于:https://www.cnblogs.com/LyonLys/archive/2012/08/26/2012_08_25_Lyon.html

創(chuàng)作挑戰(zhàn)賽新人創(chuàng)作獎勵來咯，堅(jiān)持創(chuàng)作打卡瓜分現(xiàn)金大獎

總結(jié)

以上是生活随笔為你收集整理的hdu区域赛在线热身赛 暨 第十二场组队赛的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。