Posted on 2009-02-09 18:43
hello_world 閱讀(1138)
評論(0) 編輯 收藏 引用
題目
|
題目分類
|
| The Trip |
分析 |
| Doublets |
字符串，搜索 |
| |
|
| Factovisors |
math |
| |
|
The Trip ：
題目大意是有群人出去旅行，每個人都付了一定的費用（不等），回來后要把錢均攤，但錢的最小面值是一分（cent），換句話說是個整數，現在問最少需要轉移多少錢？
如果轉移的錢可以是浮點數(或者保證一定能分得平
sample) ，那題目就簡單了，但這里稍微煩一些。首先要均攤的話，能做到最大的差價不會超過一分，假設支付費用最小為a， 最大為a+1（我們這里只討論分不平的情況），而且能算出有x個人要付 a 分， y個人要付 a+1 分，這樣就可以開始討論了
多退少補，而退的錢==補的錢，所以我們只考慮要退多少錢給多付的人
如果有人出的錢 k 大于a+1，那他肯定要退，先讓他支付 a+1分。那么這就退了 k - （a+1）分
如果所有大于a + 1分錢的人都考慮了，并且有 q 個人大于或等于 a +1 塊錢，就有兩種情況
1 q > y，說明 q個人中還有人要退，加上 q - y就好了
2 q <= y,說明多付錢的人當中沒人需要退了，結束
只考慮要退多少錢會使思路清晰些
剩下值得一提的是精度問題
有一種比較好的方法可以避免這種問題：
scanf("%d.%d",&tema, &temb); 直接把錢全部轉化為分（cent），這不涉及任何浮點數，所以也不存在精度問題
Doublets
題目意思就是說一個單詞與另一個單詞如果只有一個字母不同，這兩個單詞就可以互相到達，給出一些單詞作為字典，每次任意詢問兩個單詞的最短路徑，并輸出！
我的做法，先對字典排序，然后建圖，對一個單詞，每次構造字典序比它大的且僅相差一個字符的單詞，在它后面二分查找是否出現在字典中！這樣建圖的時間大概是25000*log(25000)*26*16；然后從起點bfs之即可，這一步大概是25000*26*16；不過都是理論上的最壞估計，實際上小得多！
我看了下標程的做法，標程的做法快在建圖上，貌似是跟桶排序差不多，每排一次序就掃一遍，在一個桶中的就是能夠到達的！
Factovisors
題目大意是給你兩個數n， m
問 m 能否整除 n 的階乘， 即 n！% m ==0 （n, m 都很大 < 2^31 )
可以將 m 質因數分解，對于每一個質數，如果n！中包含的個數 都 比m中的多，說明n！能整除 m 。
1對于m質因數分解只要用o(sqrt(n) )；
2對于n！檢查一個質因子，用循環除的方法需要log（n），而質數最多不超過log2（m）（假設質因子都挑最小的2,3,5,7。。
這樣大部分時間是在分解質因數，算是有效的方法
Waterloo local 1999.06.19
| 題目分類 |
| Billiard |
physics
|
| The Brick Stops Here |
DP |
| Election |
簡單題 |
| |
|
| Boastin' Red Socks |
數學方程求最小值，暴力 |
補充：
Billiard :
題目大意是一張臺球桌，假設這桌子沒洞，桌子橫 a 豎 b ，在桌子中心以某個角度 angel 某個速度 v 彈出一小球，這個小球和橫的邊界碰撞 p 次，與豎的邊界碰撞 q 次，經過 s 秒回到中心（起點）。
已知 a b p q s 求 angel 和 v
我們可以將兩個維度分開考慮
水平方向看，碰了 q 次回到原點，顯然可以得到走了q*a長度
豎直方向看，同理也可以知道他走了p*b；
那么他就等效于這么一個三角形，o（0， 0），A（q*a，0），B（p*b，q*a），求得角度是<AoB，總路程是oB
The Brick Stops Here：
這是一道典型的DP題目，其實就是背包問題；我們用dp[i][j][k]表示前i種磚中用了j種磚總含銅量為k的最少費用，那么dp[i][j][k]=min{dp[i-1][j-1][[k-copper[i]]+price[i] , dp[i-1][j][k]}；對于該題i<=200,j<=20,k<=20*1000！這個時間復雜度可以勉強接受，因為其實可以求出 j 和 k 的上限！而數組也可以省去第一維，避免超內存，其實根據上面的轉移方程就可以看出來跟背包的思想很類似，所以可以從后往前倒推！還有就是建議先全都處理出來然后再一起找出答案！核心代碼如下：
1
int i,j,k,h;
2 for(i=0;i<=UP_N;i++)
3 for(j=0;j<=UP_W;j++)
4 dp[i][j] = PINF;
5 dp[0][0]=0;
6 for(k=0;k<n;k++)
7 for(i=UP_N;i>=1;i--)
8 for(j=UP_W;j>=copper[k];j--)
9 checkmin(dp[i][j],dp[i-1][j-copper[k]]+price[k]);
10
Boastin' Red Socks
題目大意是有一個健忘的小孩不知道自己有多少只紅色的襪子，多少只黑色的襪子（他只有這兩種襪子），但他知道從中他拿出兩只紅色的襪子的概率是 p / q （q=>p>=0 q>0），總共最多有50,000只襪子,讓你求滿足條件的情況中襪子總數最少的那種中的紅襪子的數量
假設有x只紅襪子，總共有sum只襪子
p/ q = C(x，2) / C（sum， 2）
由于sum < 50000，對于這么小的一個數，我們可以暴一暴
從小到大枚舉 sum，解關于 整數 x 的方程，如果途中得到可行解就可以跳出，它是總數最少的
這個剪枝好像也比較重要，不加會超時
當然這個枚舉過程也可以用二分來加速，就更快了
在計算中注意細節，避免溢出