2013年3月4日 星期一
USACO 2012 三月 金組
第一題：
關鍵：
這個數量約等於 nlgn，因為你在建表的時候，大致像下面那樣
這樣子的數量級差不多是O(nlgn)，因為 sum of 1/x 是 lgn。
所以：2^質因數個數 <= 因數的數量 <= nlgn
至於第一項是哪裡來的呢？是排容原理。
總之因數數量的總和其實是很小的，要注意這一個地方。
第二題：
相信大家都寫過，這題直鏈的版本，想通就解決了，較為簡單的一個題目。
第三題：
我寫的是一個暴力搜的方法，並用目前答案去做剪枝，但這種作法在暴力方式是1*2*3*4*5*6*7...這樣子會比較有效。
我一開始寫的暴力方式 n*n-1*n-2...，就會顯得沒有什麼意義，以後要多想由小到大的方法，會比較好Cut。
官方題解不知道是在寫什麼毛，明天再去看看。
關鍵：
這個數量約等於 nlgn，因為你在建表的時候，大致像下面那樣
for(int i = 1; i < N; i++)
for(int j = i; j < N; j += i) P[j].PB(i);
for(int j = i; j < N; j += i) P[j].PB(i);
這樣子的數量級差不多是O(nlgn)，因為 sum of 1/x 是 lgn。
所以：2^質因數個數 <= 因數的數量 <= nlgn
至於第一項是哪裡來的呢？是排容原理。
總之因數數量的總和其實是很小的，要注意這一個地方。
第二題：
相信大家都寫過，這題直鏈的版本，想通就解決了，較為簡單的一個題目。
第三題：
我寫的是一個暴力搜的方法，並用目前答案去做剪枝，但這種作法在暴力方式是1*2*3*4*5*6*7...這樣子會比較有效。
我一開始寫的暴力方式 n*n-1*n-2...，就會顯得沒有什麼意義，以後要多想由小到大的方法，會比較好Cut。
官方題解不知道是在寫什麼毛，明天再去看看。
2013年3月1日 星期五
2013年2月28日 星期四
Codeforces 198 C. Delivering Carcinogen
Codeforces 的題目還蠻有品質保證的
很不錯的幾何題。不知道怎麼做就，二分搜
假設答案是 t 秒，那麼 > t 秒的都可以（先走到跟他一樣，而且V > Vp），利用這個性質來二分搜。
所以現在那個一直在繞圈圈的行星，被我們固定住
你只要找到所在位置與該行星的最短距，就解決了
直線永遠是最短距離，所以假如你不會穿越中間的圓圈，就直接拿他們的直線距離。
假設有穿越中間的圓圈，可以知道走切線再走圓弧再走切線，會是最短距離，
所以把他們一一算出來之後，就成功了。
＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝
子問題－
1. 判斷有沒有穿越中間：直線與中心的距離 <= r 且OAB和OBA都是銳角
2. 直線與中心的距離：算外積後（平行四邊形面積），再除掉底 ＝ 高
3. 判斷兩個向量是否形成銳角：內積後，正的為銳角，負的為鈍角
4. 切線的長度：OA^2 - R^2
5. 圓弧的角度：設切點是C, D，設高是M，
若BOA是銳角: (BOM-BOD-AOC)，若BOA是鈍角: (180 - BOM - BOD - AOC)
Codeforces 198E. Gripping Story
線段樹的變形真的很經典
這題要做的就是我們希望可以把 距離 <= r 的區段
重量都小於等於力量的物質挑出來，放入queue裡
每一個物質都有兩個變量，距離以及重量
要對 <= 某距離內，找出 <= 某重量 的物質
這時，我們要用到一個很基本的概念：區段樹
就是一個線段樹，但是他的每一個節點，不是單單包含一個值
而是包含了這個區段的所有元素！
這麼看的話，感覺還挺崩潰的，但是可以知道每個元素只會被lgn個包含
所以元素數量是 NlgN ，非常的好用
有了這個方向之後，是否就很簡單了呢？答案是：Yes
只要讓那個區段的值都是由小排到大的，之後在query時
就從前面開始取出即可
（我是用Set去讓他由小到大的，整體複雜度nlg^2n，但只要質量小的放到質量大的，就可以用nlgn的時間，解出來了）
想要看code，可以直接去codeforces，上面找。
這題要做的就是我們希望可以把 距離 <= r 的區段
重量都小於等於力量的物質挑出來，放入queue裡
每一個物質都有兩個變量，距離以及重量
要對 <= 某距離內，找出 <= 某重量 的物質
這時，我們要用到一個很基本的概念：區段樹
就是一個線段樹，但是他的每一個節點，不是單單包含一個值
而是包含了這個區段的所有元素！
這麼看的話，感覺還挺崩潰的，但是可以知道每個元素只會被lgn個包含
所以元素數量是 NlgN ，非常的好用
有了這個方向之後，是否就很簡單了呢？答案是：Yes
只要讓那個區段的值都是由小排到大的，之後在query時
就從前面開始取出即可
（我是用Set去讓他由小到大的，整體複雜度nlg^2n，但只要質量小的放到質量大的，就可以用nlgn的時間，解出來了）
想要看code，可以直接去codeforces，上面找。
2013年2月8日 星期五
Codeforces 266D BerDonalds
奇怪的題目名字，應該是學 Mcdonalds 的吧
如果他說只能在點上，就好辦了
直接做一次Floyd，就可以得到答案了
但！問題就在於你可以位於其中的無限多個點的其中一個
前面都很無腦，接下來就需要用到好腦袋惹～
（要了解很簡單，但要想到有點難＝＝）
＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝
其實可以這樣想，先想對於一個邊你要到所有人的最短距離
就是，這邊的兩端為 a, b，min( x + dis[ a ][ i ], c - x + dis[ b ][ i ] )對所有 i 的max要最小
直接做枚舉可能答案的動作，是最簡單也是最方便的（比起二分搜或三分搜）
所以就先朝著枚舉答案的方向思考（也就是哪些中間點要試放看看這樣）
假設所有點的集合是這樣（a, b, c, d, e...），將他分成兩個集合A, B
A代表要讓這個邊的 a 去連會是min， B代表要讓這個邊的 b 去連會是min
也就是我們假定對A集合min(剛剛那團) 會是 a 的比較小，B也是同樣的道理
而若是這麼一回事的話，拿A的最大值，B的最大值，就可以組出想要的 x 了。
枚舉A的最大值，然後求B（補集）的最大值，弄出所有可能的X，再取最小的即可。
如果他說只能在點上，就好辦了
直接做一次Floyd，就可以得到答案了
但！問題就在於你可以位於其中的無限多個點的其中一個
前面都很無腦，接下來就需要用到好腦袋惹～
（要了解很簡單，但要想到有點難＝＝）
＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝
其實可以這樣想，先想對於一個邊你要到所有人的最短距離
就是，這邊的兩端為 a, b，min( x + dis[ a ][ i ], c - x + dis[ b ][ i ] )對所有 i 的max要最小
直接做枚舉可能答案的動作，是最簡單也是最方便的（比起二分搜或三分搜）
所以就先朝著枚舉答案的方向思考（也就是哪些中間點要試放看看這樣）
假設所有點的集合是這樣（a, b, c, d, e...），將他分成兩個集合A, B
A代表要讓這個邊的 a 去連會是min， B代表要讓這個邊的 b 去連會是min
也就是我們假定對A集合min(剛剛那團) 會是 a 的比較小，B也是同樣的道理
而若是這麼一回事的話，拿A的最大值，B的最大值，就可以組出想要的 x 了。
枚舉A的最大值，然後求B（補集）的最大值，弄出所有可能的X，再取最小的即可。
//By momo
#include
#include
#include
#define N 210
#define INF 999999999
using namespace std;
double ans = INF;
int n, m, dis[N][N];
int a[N*N], b[N*N], c[N*N];
struct pairr{ int a, b; }d[N];
bool comp(pairr x, pairr y){ return x.a > y.a; }
int main (){
scanf("%d%d", &n, &m);
for(int i = 0; i < n; i++){
for(int j = 0; j < n; j++) dis[i][j] = INF;
dis[i][i] = 0;
}
for(int i = 0; i < m; i++){
scanf("%d%d%d", &a[i], &b[i], &c[i]);
a[i]--, b[i]--;
dis[a[i]][b[i]] = dis[b[i]][a[i]] = c[i];
}
for(int k = 0; k < n; k++)
for(int i = 0; i < n; i++)
for(int j = 0; j < n; j++)
dis[i][j] = min(dis[i][j],
dis[i][k] + dis[k][j]);
for(int i = 0; i < m; i++){
int C = c[i];
for(int j = 0; j < n; j++){
d[j].a = dis[a[i]][j];
d[j].b = dis[b[i]][j];
}
sort(d, d+n, comp);
int M = d[0].b; ans = min(ans, 1.0*d[0].a);
for(int j = 1; j < n; j++){
double val;
if(d[j].a > M - C && M + C > d[j].a)
val = (d[j].a+M+C) / 2.0;
else val = max(d[j].a, M);
ans = min(ans, val);
M = max(M, d[j].b);
}
}
printf("%lf\n", ans);
}
#include
#include
#include
#define N 210
#define INF 999999999
using namespace std;
double ans = INF;
int n, m, dis[N][N];
int a[N*N], b[N*N], c[N*N];
struct pairr{ int a, b; }d[N];
bool comp(pairr x, pairr y){ return x.a > y.a; }
int main (){
scanf("%d%d", &n, &m);
for(int i = 0; i < n; i++){
for(int j = 0; j < n; j++) dis[i][j] = INF;
dis[i][i] = 0;
}
for(int i = 0; i < m; i++){
scanf("%d%d%d", &a[i], &b[i], &c[i]);
a[i]--, b[i]--;
dis[a[i]][b[i]] = dis[b[i]][a[i]] = c[i];
}
for(int k = 0; k < n; k++)
for(int i = 0; i < n; i++)
for(int j = 0; j < n; j++)
dis[i][j] = min(dis[i][j],
dis[i][k] + dis[k][j]);
for(int i = 0; i < m; i++){
int C = c[i];
for(int j = 0; j < n; j++){
d[j].a = dis[a[i]][j];
d[j].b = dis[b[i]][j];
}
sort(d, d+n, comp);
int M = d[0].b; ans = min(ans, 1.0*d[0].a);
for(int j = 1; j < n; j++){
double val;
if(d[j].a > M - C && M + C > d[j].a)
val = (d[j].a+M+C) / 2.0;
else val = max(d[j].a, M);
ans = min(ans, val);
M = max(M, d[j].b);
}
}
printf("%lf\n", ans);
}
訂閱：
文章 (Atom)