300pt
一個人在一個圖上行走，每次走邊權值最小的邊，如果有多個邊權最小的邊就選擇標號最小的。現在讓你修改某個邊權，請問如何才能讓這個人走的最多。
邊權小于10000大于0。點數不超過30的完全圖。
算法分析：
根據數據范圍可以確定，枚舉修改每條邊，強制讓那個人走這條邊就可以了。時間復雜度V^4。
比賽的時候沒有看到邊權一定要大于0。結果悲劇了。
1 #include<iostream>
2 #include<string>
3 #include<vector>
4 #include<cstring>
5 using namespace std;
6 const int V = 60;
7 int G[V][V],num[V];
8 void chkmax(int &a,int b){
9 if(a < b) a = b;
10 }
11 int vis[V],n;
12 int work(){
13 memset(vis,0,sizeof(vis));
14 int u = 0, ans = 0;
15 while(1){
16 vis[u] = 1;
17 int fst = -1, snd = -1, mx = 10000, mn = 10000;
18 for(int v = 0; v < n; v ++) if(!vis[v]){
19 if(G[u][v] < mn){
20 mx = mn; snd = fst;
21 mn = G[u][v]; fst = v;
22 }
23 else if(G[u][v] < mx){
24 mx = G[u][v]; snd = v;
25 }
26 }
27 if(fst == -1) return ans;
28 int k = num[u];
29 if(vis[k]) return 0;
30 int val;
31 if(u==18 && num[u]==27){
32 // cout<<fst<<" "<<snd<<endl;
33 // cout<<mn<<" "<<mx<<endl;
34
35 }
36 if(k == fst) {
37 if(snd == -1) val = 9999;
38 else val = mx - (k < snd ? 0 : 1);
39 u = fst;
40 }
41 else if(k == -1){
42 val = G[u][fst];
43 u = fst;
44 }
45 else {
46 val = G[u][fst] - (k < fst ? 0 : 1);
47 if(k == snd && !(mx == 9999 && fst < snd)){
48 val = mx;
49 }
50 if(val == 0) return 0;
51 u = k;
52 }
53 ans += val;
54 }
55 }
56 class GreedyTravelingSalesman{
57 public : int worstDistance(vector <string> thousands, vector <string> hundreds, vector <string> tens, vector <string> ones){
58 n = ones.size();
59 for(int i=0;i<n;i++)
60 for(int j=0;j<n;j++)
61 G[i][j] = (thousands[i][j]-'0')*1000+ (hundreds[i][j]-'0')*100 + (tens[i][j]-'0')*10 + (ones[i][j]-'0');
62 int ans = 0;
63 for(int i=0;i<n;i++)
64 for(int j=0;j<n;j++) {
65 memset(num,-1,sizeof(num));
66 num[i] = j;
67 int v = work();
68 chkmax(ans, v);
69 //if(v == 40375 || v ==39896)cout<<i<<" "<<j<<" "<<v<<endl;
70 }
71 return ans;
72 }
73 };
500pt
歐式平面上有N個點，(N<30,000)。橫縱坐標在0到1,000,000,000之間，且保證沒有x值或者y值相同的點。請問滿足x1<x2<x3 && y1<y3<y2的點一共有多少個？
算法分析：
將橫坐標排序，從左到右掃描，檢查縱坐標。問題變成了點i之前有多少個yj>yi && yk<yi且j>k的點對。顯然離散化之后線段樹可以搞。
我們按照從左到右的順序插入點。要維護三個值：
1. 區間[l,r]有多少個點。由此我們在插入i的時候就知道之前有多少個比i小的點了。
2. 區間[l,r]有多少個以k為右上端點的線段。
3. 區間[l,r]有多少個以k為左下端點的線段。
在查詢的時候，對于比i大的區間[l,r]，(值2-值3)就是這個區間里符合條件的線段數。都加上就好了。
我們可以用值1來維護值2。用懶惰標記更新值3。
寫起來還是比較容易寫錯的。
upt: 磊哥教了我一個從右向左掃描動態求逆序數的方法 Orz!!!! 比這個好想很多也好寫很多。。。。。
1 #include<iostream>
2 #include<cstdlib>
3 #include<algorithm>
4 using namespace std;
5 typedef
long long ll;
6 typedef pair<ll, ll> pnt;
7 const int N = 300005;
8 ll num[N<<2], sum[N<<2], hash[N], suma[N<<2] , ans, v;
9 int chg[N<<2];
10 pnt flag[N];
11 int find(ll val,
int n){
12 int l = 0, r = n;
13 while(l < r){
14 int mid = l+r >> 1;
15 if(hash[mid] >= val) r = mid;
16 else l = mid+ 1;
17 }
18 return l;
19 }
20 void pushdown(
int pos){
21 if(chg[pos]){
22 int l = pos <<1, r = pos<<1 |1;
23 chg[l] += chg[pos];
24 chg[r] += chg[pos];
25 suma[l] += num[l] * chg[pos];
26 suma[r] += num[r] * chg[pos];
27 chg[pos] = 0;
28 }
29 }
30 void sumup(
int pos){
31 int l = pos <<1;
int r = pos<<1|1;
32 sum[pos] = sum[l] + sum[r];
33 num[pos] = num[l] + num[r];
34 suma[pos] = suma[l] + suma[r];
35 }
36 void update(
int P,
int pos,
int L,
int R){
37 if(L==R){
38 // cout<<"v: "<<v<<endl;
39 sum[pos] += v;
40 num[pos] ++;
41 chg[pos] = 0;
42 return ;
43 }
44 pushdown(pos);
45 int mid = L+R>>1, l = pos <<1, r = pos<<1|1;
46 if(P <=mid) {
47 // cout<<"left: "<<L<<" "<<R<<" "<<sum[r]<<" "<<suma[r]<<endl;
48 ans += sum[r] - suma[r];
49 update(P,l,L,mid);
50 }
51 else {
52 v += num[l];
53 // cout<<"right: "<<v<<endl;
54 chg[l] ++; suma[l] += num[l];
55 update(P,r,mid+1,R);
56 }
57 sumup(pos);
58 // cout<<"back: "<<pos<<" "<<L<<" "<<R<<" sum: "<<sum[pos]<<" num : "<<num[pos]<<endl;
59 }
60 class ThreePoints{
61 public :ll countColoring(
int n,
int xzero,
int xmul,
int xadd,
int xmod,
int yzero,
int ymul,
int yadd,
int ymod){
62 flag[0] = make_pair(xzero, yzero);
63 hash[0] = yzero;
64 for(
int i=1; i< n; i++){
65 ll x = (flag[i-1].first*xmul + xadd) % xmod ;
66 ll y = (flag[i-1].second*ymul + yadd) % ymod;
67 flag[i] = make_pair (x,y);
68 hash[i] = y;
69 }
70 sort(hash,hash+n);
71 sort(flag,flag+n);
72 //for(int i=0;i<n;i++) cout<<hash[i]<<" "; cout<<endl;
73 ans = 0;
74 for(
int i=0; i< n; i++){
75 // cout<<"pnt: "<<flag[i].first <<" "<<flag[i].second<<endl;
76 int P = find(flag[i].second,n);
77 // cout<<"P: "<<P<<endl;
78 v = 0;
79 update(P,1,0,n-1);
80 // cout<<"ans: "<<ans<<endl;
81 // for(int i=1;i<=15;i++) cout<<num[i]<<" "; cout<<endl;
82 }
83 return ans;
84 }
85 };
posted on 2012-06-17 13:19
西月弦 閱讀(303)
評論(0) 編輯 收藏 引用