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
西月弦 阅读(291)
评论(0) 编辑 收藏 引用