個人場第十場題解

• 花札洗牌
• 點與圓
• 單位分數(shù)劃分

花札洗牌

題目描述
洗牌的方法有很多種。日本紙牌游戲“hanafuda”的洗牌就是這樣一個例子。下面是如何執(zhí)行Hanafuda洗牌。

有一副n張牌。從卡組頂部的第p張卡開始，c卡被拉出并放在卡組頂部，如圖1所示。此操作稱為切割操作，然后重復(fù)進行。

編寫一個程序，模擬花花公子洗牌，并回答哪張牌將最終放在牌組頂部。

輸入格式
輸入包含多組數(shù)據(jù)。

對于每組數(shù)據(jù)首先輸入一行兩個用空格分開的整數(shù)n和r，分別是組中的卡數(shù)和剪切操作數(shù)1≤n≤50,1≤r≤50。
接下來輸入r行，每行代表一次切割操作。這些切割操作按列出的順序執(zhí)行。每行包含兩個正整數(shù)p和c（p+c<=n+1）。從卡組頂部的第p張卡開始，c張卡應(yīng)抽出并放在頂部。

輸入以兩個用空格分開的0結(jié)尾

輸出格式
對于每組數(shù)據(jù)，輸出最后在牌堆頂部的牌的編號，牌最初從底部到頂部編號為1-n

題目大意：

有一堆卡片，編號從1.。。n，從第p個卡片開始向后取出c張卡片放到底部。這里的頂部是第n個后邊。同時注意的是在將卡片放到頂部的時候，之前在前邊的卡片后到后邊。

解題思路：

我們用數(shù)組來模擬這個過程，我們從前往后存n~1，這個時候下標(biāo)為1的地方就是頂部。同時用一個額外的數(shù)組來存操作后的數(shù)據(jù)。模擬的過程是將c張卡片放到前面c個位置，然后才將之后的數(shù)據(jù)填入。

代碼：

#include <stdio.h> #include <cstring>int game[100]; int n, r;int main() {while (~scanf("%d%d", &n, &r)) {if (!n && !r)break;for (int i = 0; i <= n; ++i)game[i] = n - i + 1;int barcup[200];memcpy(barcup, game, sizeof game);// 以 10 9 8 7 6 5 4 3 2 1 為例while (r--) {int p, c;scanf("%d%d", &p, &c);// p = 8,c = 3;// 將第8個開始的3張放到頂部，即 4,3,2for (int i = p + c - 1, j = c; i >= p; --i, --j)barcup[j] = game[i];// 4 3 2 7 6 5 4 3 2 1// 之后將 第1位到第 p-1 為的元素放到后邊for (int i = c + 1, j = 1; j <= p - 1; i++, ++j)barcup[i] = game[j];// 4 3 2 10 9 8 7 6 5 1memcpy(game, barcup, sizeof game);}printf("%d\n", game[1]);}return 0; }

點與圓

在笛卡爾坐標(biāo)系中已知N個點。你有一個半徑為1的圓，并在笛卡爾坐標(biāo)系中移動它，以便盡可能多地包圍這些點。找出有多少點可以同時被包圍在最大。當(dāng)點在圓內(nèi)或圓上時，它被認為是被圓包圍的。

輸入
輸入由一系列數(shù)據(jù)集組成，后面跟著一行，只包含一個字符’0’，這表示輸入的結(jié)束。 每個數(shù)據(jù)集都以包含整數(shù)N的行開始，N表示數(shù)據(jù)集中的點數(shù)。 后面N行描述點的坐標(biāo)。 每一行都有兩個小數(shù)X和Y，分別描述點的X和Y坐標(biāo)。 小數(shù)點后保留五位數(shù)字。

你可以假設(shè)1 <= N <= 300, 0.0 <= X <= 10.0, 0.0 <= Y <= 10.0。 沒有兩個點之間距離小于0.0001。 數(shù)據(jù)集中沒有兩個點的距離近似為2.0。 更準(zhǔn)確地說，對于數(shù)據(jù)集中的任意兩點，兩者之間的距離d永遠不滿足1.9999 <= d <= 2.0001。 最后，一個數(shù)據(jù)集中沒有三個點同時非常接近一個半徑為1的圓。 更準(zhǔn)確地說，讓P1, P2, P3是數(shù)據(jù)集中的任意三個點，d1, d2, d3分別是笛卡爾坐標(biāo)系中任意點到這三個點的距離。 然后它永遠不會同時持有0.9999 <= di <= 1.0001 (i = 1,2,3)。

輸出
對于每個數(shù)據(jù)集，打印單行，其中包含數(shù)據(jù)集中可以同時被半徑為1的圓包圍的最大點數(shù)。 不應(yīng)該打印其他字符，包括前導(dǎo)和尾隨空格。

解題思路是，將問題轉(zhuǎn)化為特定形式的答案。畫個圖我們假設(shè)有一個圓包含了一推點在里邊，我們在可以一直包含所有點的情況下移動圓，我們首先呢圓與其中一個點相交，這個時候是滿足的，當(dāng)與兩個點相交的時候，如果還移動圓就無法包含所有的點了。因此極限就是兩個點。
因此我們可以枚舉兩個不同點的組合，通過這兩個點算出過這兩個點的圓的圓心，之后因為是單位元，遍歷所有點如果與圓心的距離在圓內(nèi)就+1，取這個結(jié)果的最大值。

注意事項：

• 一個點的情況，所以我們初始化為1即可。
• 因為題目描述如果兩點距離大于2就不計算。

代碼：

#include <stdio.h> #include <math.h> #include <algorithm>using namespace std; const double eps = 1e-8; struct point {double x, y; } p[3010]; int n;double dist(point a, point b) {return sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y)); }// 已知圓上兩點，求圓心坐標(biāo) void getmid(point p1, point p2, point &center) {point mid;mid.x = (p1.x + p2.x) / 2.0;mid.y = (p1.y + p2.y) / 2.0;double angle = atan2(p1.x - p2.x, p2.y - p1.y);double dcm = sqrt(1 - dist(p1, mid) * dist(p1, mid));center.x = mid.x + dcm * cos(angle);center.y = mid.y + dcm * sin(angle); }int main() {while (~scanf("%d", &n)) {if (!n)break;for (int i = 1; i <= n; ++i)scanf("%lf%lf", &p[i].x, &p[i].y);int ans = 1, cnt = 0;for (int i = 1; i < n; ++i)for (int j = i + 1; j <= n; ++j) {if (dist(p[i], p[j]) > 2.0)continue;point center;getmid(p[i], p[j], center);int cnt = 0;for (int k = 1; k <= n; ++k) {if (dist(p[k], center) < 1.0 + eps)cnt++;}ans = max(ans, cnt);}printf("%d\n", ans);}return 0; }

單位分數(shù)劃分

輸入格式
分子為1，分母為正整數(shù)的分數(shù)稱為單位分數(shù)。正有理數(shù)p/q作為有限多個單位分數(shù)之和的表示稱為p/q到單位分數(shù)的劃分。例如，1/2+1/6是將2/3劃分為單位分數(shù)的一種方式。加法順序的差異被忽略。例如，我們不區(qū)分1/6+1/2和1/2+1/6。

對于給定的四個正整數(shù)p、q、a和n，將p/q的分區(qū)數(shù)計算為滿足以下兩個條件的單位分數(shù)。

劃分為最多n個單位分數(shù)的總和。

劃分中單位分數(shù)分母的乘積小于或等于a
例如，如果(p,q,a,n)=(2,3,120,3),能夠找到如下四種劃分

輸入格式
輸入不超過1000組數(shù)據(jù)

對于每組數(shù)據(jù)，輸入p q a n，相鄰兩個數(shù)以空格分開，p,q≤800,a≤12000,n≤7

輸入以包含四個用空格分開的0結(jié)束

輸出格式
對于每組數(shù)據(jù)，輸出一個整數(shù)，表示劃分方案數(shù)

題意：

給了一個分數(shù)p/q，求有多少種單位分數(shù)之和等于p/q，且滿足所有單位分數(shù)的分母之積小于等于a，個數(shù)小于n。

思路：

分母從1開始枚舉，每次記錄一下枚舉到哪個數(shù)了，如果滿足分母之ji積小于等于a，且個數(shù)不超過n，從此數(shù)繼續(xù)讓下搜，因為單位分數(shù)之間不分先后順序，所以這樣就涵蓋了所有情況。

代碼：

#include <stdio.h> #include <cstring>int p, q, a, n; int ans; void dfs(int p, int q, int mul, int x, int num) {if (p == 0 && mul <= a) {ans ++;return ;}// 剪枝// 分別為 數(shù)量達到上限，mul * x 是等會分母要乘的最小//的的值這都大于 a 了就不用玩了。// p*x>q*num 就是說因為這一條路徑往后分母乘的都>= xif (num == 0 || mul * x > a || p * x > q * num)return ;for (int i = x; i <= a ; ++i) {if (mul * i <= a) {int dp = p * i - q; // 不能直接改變p呀不然這一曾就不是以p為根了if (p >= 0)dfs(dp, q * i, mul * i, i, num - 1);}} }int main() {while (~scanf("%d%d%d%d", &p, &q, &a, &n)) {if (!p && !q && !n && !a)break;ans = 0;dfs(p, q, 1, 1, n);printf("%d\n", ans);}return 0; }

總結(jié)

以上是生活随笔為你收集整理的个人场第十场题解的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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