題意:

許多 k 維點, 求這些點之間的最遠曼哈頓距離. 并且有 q 次操作, 插入一個點或者刪除一個點. 每次操作之后均輸出結果.

思路:

用"疑似絕對值"的思想, 維護每種狀態下各點的計算值, 插入或刪除一個點就更新一次每種狀態(用 multiset 或 map 或 priority_queue 實現), 每次求ans時掃一遍最大差值即可.

為了練習STL, 每一個都實現一次.

multiset

?

/* ********************************************** Author : kuangbin Created Time: 2013/8/13 18:25:38 File Name : F:\2013ACM練習\2013多校7\1001.cpp *********************************************** */ //4640MS?? ?14972K #include <cstdio> #include <algorithm> #include <set> using namespace std; int a[60010][10]; multiset<int>mst[1<<5];int main() {//freopen("in.txt","r",stdin);//freopen("out.txt","w",stdout);int q,k;while(scanf("%d%d",&q,&k)==2){for(int i = 0;i < (1<<k);i++)mst[i].clear();int od,x;for(int i = 1;i <= q;i++){scanf("%d",&od);if(od == 0){for(int j = 0;j < k;j++)scanf("%d",&a[i][j]);for(int j = 0; j < (1<<k); j++){//計算當前點在每種情況下的"疑似絕對值"int s = 0;for(int t = 0; t < k;t++)if(j & (1<<t))s += a[i][t];else s -= a[i][t];mst[j].insert(s);//插入到該種情況下}}else{scanf("%d",&x);for(int j = 0; j < (1<<k); j++){//一次操作,插入或刪除一個點,都是將這個點對應的所有狀態插入每種狀態中int s = 0;//因此,要清除一次操作,就要刪除所有狀態中的那一個for(int t = 0; t < k;t++)if(j & (1<<t))s += a[x][t];else s -= a[x][t];multiset<int>::iterator it = mst[j].find(s);mst[j].erase(it);}}int ans = 0;for(int j = 0; j < (1<<k);j++){multiset<int>::iterator it = mst[j].end();it--;int t1 = (*it);it = mst[j].begin();int t2 = (*it);//用于作差ans = max(ans,t1-t2);//保留最大值}printf("%d\n",ans);}}return 0; }

?

map

?

//8359MS 37928K慢死了#include <cstdio> #include <algorithm> #include <map> using namespace std;int a[60010][6]; map<int, int> mp[1<<5];int main() {int q,k;while(scanf("%d %d",&q,&k)==2){for(int i=0;i<1<<k;i++)mp[i].clear();int od, x;for(int i=1;i<=q;i++){scanf("%d",&od);if(!od){for(int j=0;j<k;j++)scanf("%d",a[i]+j);for(int s=0;s<1<<k;s++){int t = 0;for(int j=0;j<k;j++){if(s & (1<<j)) t += a[i][j];else t -= a[i][j];}mp[s][t]++;// printf("map[s][t] = %d\n",mp[s][t]);}}else{scanf("%d",&x);for(int s=0;s<1<<k;s++){int t = 0;for(int j=0;j<k;j++){if(s & (1<<j)) t += a[x][j];else t -= a[x][j];}map<int, int>::iterator it = mp[s].find(t);mp[s][t]--;}}int ans = 0;for(int s=0;s<(1<<k);s++){map<int, int>::iterator it = mp[s].end();it--;while(it->second==0) it--;int mx = it->first;///first~~~it = mp[s].begin();while(it->second==0) it++;int mi = it->first;ans = max(ans, mx - mi);// printf("mx = %d, mi = %d\n",mx,mi);}printf("%d\n",ans);}} }

?

priority_queue

優先隊列只能返回隊首元素,因此需要兩個隊列分別求最大最小值.

對于已刪除的元素, 無法直接刪除, 可以做標記, 碰到已刪除的元素時直接pop掉就行了.

因此入隊的就不能僅僅是一個值(前兩個有find功能, 不需要額外標號), 而應該是一個記錄key和value的結構體.

?

//2218MS 36748K #include <cstring> #include <cstdio> #include <algorithm> #include <queue> using namespace std;int a[6]; bool vis[60005]; typedef struct ascending_node {int id,t;bool operator<(const ascending_node& a) const{return t > a.t;} }anode; typedef struct descending_node {int id,t;bool operator<(const descending_node& a) const{return t < a.t;} }dnode; /* 2812MS 30224K priority_queue<anode> apq[1<<5]; priority_queue<dnode> dpq[1<<5]; int main() {int q,k;while(scanf("%d %d",&q,&k)==2){for(int i=0;i<1<<k;i++){while(!apq[i].empty()) apq[i].pop();while(!dpq[i].empty()) dpq[i].pop();}*/ /**/ int main() {int q,k;while(scanf("%d %d",&q,&k)==2){priority_queue<anode> apq[1<<5];priority_queue<dnode> dpq[1<<5];/**/anode t1;dnode t2;memset(vis,false,sizeof(vis));int od, x;for(int i=1;i<=q;i++){scanf("%d",&od);if(!od){for(int j=0;j<k;j++)scanf("%d",a+j);for(int s=0;s<1<<k;s++){int t = 0;for(int j=0;j<k;j++){if(s & (1<<j)) t += a[j];else t -= a[j];}t1.t = t2.t = t;t1.id = t2.id = i;apq[s].push(t1);dpq[s].push(t2);// printf("map[s][t] = %d\n",mp[s][t]);}}else{scanf("%d",&x);vis[x] = true;}int ans = 0;for(int s=0;s<(1<<k);s++){while(1){t1 = apq[s].top();if(!vis[t1.id]) break;apq[s].pop();}while(1){t2 = dpq[s].top();if(!vis[t2.id]) break;dpq[s].pop();}ans = max(ans, t2.t-t1.t);}printf("%d\n",ans);}} }

?

?

轉載于:https://www.cnblogs.com/james1207/p/3293807.html

總結

以上是生活随笔為你收集整理的[HDU 4666]Hyperspace[最远曼哈顿距离][STL]的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。