1001

描述

• 給出四個(gè)三維坐標(biāo)下的點(diǎn), 判定是否為正方形.

分析

• 用向量的數(shù)量積來判定是否垂直, 再判斷長(zhǎng)度.
• 我是在紙上畫出了A(3,2)=6 種情況然后暴力枚舉判斷是否為正方形. 組合數(shù)的意義表示在 2、3、4 三個(gè)點(diǎn)中有序選出兩個(gè)點(diǎn)和 1 相鄰.
• 我寫了一百多行的代碼, 看了看別人簡(jiǎn)潔的代碼, 發(fā)現(xiàn)可以直接用STL的 next_permutation 來生成下一個(gè)排列, 把排列看做從左上角開始的順時(shí)針 (或逆時(shí)針) 四個(gè)點(diǎn)的編號(hào), 就可以少打很多暴力枚舉.
  
  • 尤其是在點(diǎn)數(shù)更多時(shí)這個(gè)辦法更有用.
• 然后就去看題解, 發(fā)現(xiàn)可以直接用三個(gè)點(diǎn)來判斷, 用向量法推出第四個(gè)點(diǎn)的坐標(biāo), 判定是否符合.
• 計(jì)算幾何的一些常用函數(shù)還是打成函數(shù)比較好, 可以降低代碼復(fù)雜度.

代碼

https://code.csdn.net/snippets/647464

#include <cstdio> using namespace std; typedef long long lli;struct Vector {lli x, y, z;Vector(lli x=0, lli y=0, lli z=0) : x(x), y(y), z(z) {}void init() {scanf("%lld%lld%lld", &x, &y, &z);} };Vector operator - (Vector A, Vector B) {return Vector(A.x-B.x, A.y-B.y, A.z-B.z); }lli Dot(Vector A, Vector B) { return A.x*B.x + A.y*B.y + A.z*B.z; } lli Length2(Vector A) { return Dot(A, A); }int main() {int T;scanf("%d", &T);Vector p1, p2, p3, p4;Vector u1, u2, u3, u4;Vector v1, v2, v3, v4;for(int kase = 1; kase <= T; kase++) {printf("Case #%d: ", kase);p1.init(); p2.init(); p3.init(); p4.init();u1 = p2-p1; v1 = p3-p1;u2 = p1-p2; v2 = p4-p2;u3 = p2-p4; v3 = p3-p4;u4 = p1-p3; v4 = p4-p3;if(Dot(u1, v1) == 0 && Dot(u2, v2) == 0 && Dot(u3, v3) == 0 && Dot(u4, v4) == 0) {if(Length2(u1) == Length2(v1) && Length2(u2) == Length2(v2) && Length2(u3) == Length2(v3) && Length2(u4) == Length2(v4)) puts("Yes");else puts("No");continue;}u1 = p2-p1; v1 = p4-p1;u2 = p1-p2; v2 = p3-p2;u3 = p2-p3; v3 = p4-p3;u4 = p1-p4; v4 = p3-p4;if(Dot(u1, v1) == 0 && Dot(u2, v2) == 0 && Dot(u3, v3) == 0 && Dot(u4, v4) == 0) {if(Length2(u1) == Length2(v1) && Length2(u2) == Length2(v2) && Length2(u3) == Length2(v3) && Length2(u4) == Length2(v4)) puts("Yes");else puts("No");continue;}u1 = p3-p1; v1 = p2-p1;u2 = p1-p3; v2 = p4-p3;u3 = p3-p4; v3 = p2-p4;u4 = p1-p2; v4 = p4-p2;if(Dot(u1, v1) == 0 && Dot(u2, v2) == 0 && Dot(u3, v3) == 0 && Dot(u4, v4) == 0) {if(Length2(u1) == Length2(v1) && Length2(u2) == Length2(v2) && Length2(u3) == Length2(v3) && Length2(u4) == Length2(v4)) puts("Yes");else puts("No");continue;}u1 = p3-p1; v1 = p4-p1;u2 = p1-p3; v2 = p2-p3;u3 = p3-p2; v3 = p4-p2;u4 = p1-p4; v4 = p2-p4;if(Dot(u1, v1) == 0 && Dot(u2, v2) == 0 && Dot(u3, v3) == 0 && Dot(u4, v4) == 0) {if(Length2(u1) == Length2(v1) && Length2(u2) == Length2(v2) && Length2(u3) == Length2(v3) && Length2(u4) == Length2(v4)) puts("Yes");else puts("No");continue;}u1 = p4-p1; v1 = p2-p1;u2 = p1-p4; v2 = p3-p4;u3 = p4-p3; v3 = p2-p3;u4 = p1-p2; v2 = p3-p2;if(Dot(u1, v1) == 0 && Dot(u2, v2) == 0 && Dot(u3, v3) == 0 && Dot(u4, v4) == 0) {if(Length2(u1) == Length2(v1) && Length2(u2) == Length2(v2) && Length2(u3) == Length2(v3) && Length2(u4) == Length2(v4)) puts("Yes");else puts("No");continue;}u1 = p4-p1; v1 = p3-p1;u2 = p1-p4; v2 = p2-p4;u3 = p3-p2; v3 = p4-p2;u4 = p1-p3; v2 = p2-p3;if(Dot(u1, v1) == 0 && Dot(u2, v2) == 0 && Dot(u3, v3) == 0 && Dot(u4, v4) == 0) {if(Length2(u1) == Length2(v1) && Length2(u2) == Length2(v2) && Length2(u3) == Length2(v3) && Length2(u4) == Length2(v4)) puts("Yes");else puts("No");continue;}puts("No");}return 0; }

---

1002

描述

• 在數(shù)組 a中找出兩個(gè)數(shù) ai, aj (i≠j), 使得 gcd(ai,aj) 取到最大值.
• 數(shù)組元素個(gè)數(shù) n≤50000

分析

• 因?yàn)閿?shù)組是給出的, 有不確定性, 所以放棄了找規(guī)律.
• 暴力拆解因數(shù), 用 hash 表來存儲(chǔ)這個(gè)因數(shù)有沒有出現(xiàn)過. 如果這個(gè)因數(shù)出現(xiàn)過就更新答案, 否則標(biāo)記為已出現(xiàn).
• 枚舉因數(shù)肯定是 [1,n√] 之內(nèi)的, 同時(shí)如果 i 是 x 的因數(shù), xi 也是 x 的因數(shù), 如果 xi 出現(xiàn)過, 那么就可以不再繼續(xù)枚舉了. 因?yàn)殡S著 i 的增大, xi 會(huì)減小, 不會(huì)比現(xiàn)在答案更優(yōu).
• O(nn√)
• 還可以加一個(gè)優(yōu)化, 就是把 a 數(shù)組 sort 后從大往小來判定. 這樣提前搜到答案的幾率或許更大一些.

代碼

https://code.csdn.net/snippets/647465

#include <cstdio> #include <cmath> #include <cstring> #include <algorithm> using namespace std; const int maxn = 100000 + 10;bool factor[maxn]; int c[maxn];int main() {int T;scanf("%d", &T);for(int kase = 1; kase <= T; kase++) {int n, ans = 1;scanf("%d", &n);memset(factor, 0, sizeof(factor));for(int i = 0; i < n; i++) scanf("%d", &c[i]);sort(c, c + n);for(int i = n-1; i >= 0; i--) {int x = c[i];for(int k = 1; k*k <= x; k++)if(x % k == 0) {if(ans >= x/k) break;if(factor[k]) ans = max(ans, k); else factor[k] = 1;if(k*k == x) continue;if(factor[x/k]) { ans = x/k; break; } else factor[x/k] = 1;} else if(ans >= x/k) break;}printf("Case #%d: %d\n", kase, ans);}return 0; }

1003

待補(bǔ)

1004

描述

小F今天3歲生日，他爸爸送給他一套魔法積木作為生日禮物，積木一共包含n塊，編號(hào)從1到n，每塊積木都可以任意設(shè)置高度為整數(shù)h(1≤h≤m)。小F非常開心地玩起了積木，并按照以下步驟進(jìn)行操作

(1) 首先，拿出編號(hào)為1的積木，任意設(shè)置高度為h1，放在第一行行首處。
(2) 當(dāng)進(jìn)行到第i步時(shí)（假設(shè)前i?1塊積木已經(jīng)擺放成r行）：拿出編號(hào)為i的積木，這時(shí)有兩種放法：
(I) 任意設(shè)置積木i的高度，然后把它放在r+1行行首（產(chǎn)生新的一行）
(II)從r行中任意選擇一行，任意設(shè)置積木i的高度hi使得hi不低于被選行最后一個(gè)積木高度，然后將積木i放在該行的最后
(3) n塊積木都使用后操作結(jié)束，形成了一個(gè)圖案

小F非常好奇,所有可能的操作下會(huì)形成多少種不同的圖案？對(duì)于兩種圖案，如果它們積木總行數(shù)相同，并且對(duì)應(yīng)行總積木數(shù)相同，并且對(duì)應(yīng)位置的編號(hào)高度都相同，兩種圖案便被視為相同。

分析

• 看題解、補(bǔ)題解.
• 動(dòng)態(tài)規(guī)劃
• f[i] 表示前 i 個(gè)積木的圖案數(shù).
• f[0]=1
• 接下來看由 f[j] 如何得到 f[i].
  
  • 假設(shè)已經(jīng)排好 j 個(gè)積木, 剩余 i?j 個(gè)積木, 為了不重復(fù), 把它們?nèi)糠旁谛碌囊恍? 假設(shè) s[i] 表示 h[i]?h[i?1], 也就是差分. 規(guī)定 h[0]=1,h[i?j+1]=m. 則 ∑i?j+1i=1si=m?1, 求正整數(shù)解就可以限定 h 的取值在 [1,m] 之間. 正整數(shù)解的個(gè)數(shù)為 (i?j+1+m?1?1i?j+1?1)=(i?j+m?1i?j).
  • 看題解還發(fā)現(xiàn)一個(gè)細(xì)節(jié), 就是先拿出第一個(gè)積木來. 這樣可以保證該積木不會(huì)包含在那 j 個(gè)積木中, 只能在新的一行中. 保證不會(huì)出現(xiàn)重復(fù).

總結(jié)

以上是生活随笔為你收集整理的BestCoder-Round#38的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

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