首页 > 代码库 > HDU 4879 ZCC loves march (2014多校2-1008,数据结构,STL,模拟题)

HDU 4879 ZCC loves march (2014多校2-1008,数据结构,STL,模拟题)

题目:

http://acm.hdu.edu.cn/showproblem.php?pid=4879

 

题意:

给一个n*m的矩阵,有n个人,t次操作,操作有以下两种:

1、令编号x的人上下左右移动

2、令与编号x的人同行同列的人聚集到x这里,输出花费

 

方法:

使用两个set,一个维护x轴,一个维护y轴

一个map<point,int>,表示这一个point有多少个人

然后根据要求的操作直接操作即可,nlgn复杂度

 

注意:

1、由于set或者map是红黑树,所以删除节点的后,内部节点重排,it++会变化,需要重新查询给迭代器it赋值,这里一直RE

2、计算两者距离时,计算xi-xj和yi-yj时需要mod,否则乘起来会爆long long

 

代码:

  1 // #pragma comment(linker, "/STACK:102400000,102400000")  2 #include <cstdio>  3 #include <iostream>  4 #include <cstring>  5 #include <string>  6 #include <cmath>  7 #include <set>  8 #include <list>  9 #include <map> 10 #include <iterator> 11 #include <cstdlib> 12 #include <vector> 13 #include <queue> 14 #include <stack> 15 #include <algorithm> 16 #include <functional> 17 using namespace std; 18 typedef long long LL; 19 #define ROUND(x) round(x) 20 #define FLOOR(x) floor(x) 21 #define CEIL(x) ceil(x) 22 const int maxn = 100010; 23 const int maxm = 0; 24 const LL mod = 1e9 + 7; 25 const int inf = 0x3f3f3f3f; 26 const LL inf64 = 0x3f3f3f3f3f3f3f3fLL; 27 const double INF = 1e30; 28 const double eps = 1e-6; 29 const int P[4] = {0, 0, -1, 1}; 30 const int Q[4] = {1, -1, 0, 0}; 31 const int PP[8] = { -1, -1, -1, 0, 0, 1, 1, 1}; 32 const int QQ[8] = { -1, 0, 1, -1, 1, -1, 0, 1}; 33 LL n, m; 34 LL ans = 0; 35 int id; 36 LL d; 37 struct Point 38 { 39     LL x, y; 40     int id; 41     Point(LL _x = -1, LL _y = -1, int _id = -1): x(_x), y(_y), id(_id) {} 42     bool operator == (const Point &o) const 43     { 44         return x == o.x && y == o.y; 45     } 46 } node[maxn]; 47 struct cmp1 48 { 49     bool operator () (const Point &A, const Point &B) const 50     { 51         if (A.x == B.x) return A.y < B.y; 52         return A.x < B.x; 53     } 54 }; 55 struct cmp2 56 { 57     bool operator () (const Point &A, const Point &B) const 58     { 59         if (A.y == B.y) return A.x < B.x; 60         return A.y < B.y; 61     } 62 }; 63 set<Point, cmp1> s1; 64 set<Point, cmp2> s2; 65 map<Point, int, cmp1> mp; 66 void debug() 67 { 68     cout << "debug:" << endl; 69     cout << "s1:" << endl; 70     for (set<Point>::iterator it = s1.begin(); it != s1.end(); it++) 71     { 72         cout << it->x << " " << it->y << endl; 73     } 74     cout << "s2:" << endl; 75     for (set<Point>::iterator it = s2.begin(); it != s2.end(); it++) 76     { 77         cout << it->x << " " << it->y << endl; 78     } 79     cout << "mp:" << endl; 80     for (map<Point, int>::iterator it = mp.begin(); it != mp.end(); it++) 81     { 82         cout << it->first.x << " " << it->first.y << " " << it->second << endl; 83     } 84     cout << endl; 85 } 86 void init() 87 { 88     mp.clear(); 89     s1.clear(); 90     s2.clear(); 91     ans = 0; 92 } 93 void add(Point p) 94 { 95     if (mp.count(p) == 0) 96     { 97         mp[p] = 1; 98         s1.insert(p); 99         s2.insert(p);100     }101     else mp[p]++;102 }103 void del(Point p)104 {105     map<Point, int, cmp1>::iterator ite = mp.find(p);106     ite->second--;107     if (ite->second == 0)108     {109         mp.erase(ite);110         s1.erase(p);111         s2.erase(p);112     }113 }114 void input()115 {116     s1.insert(Point(-1, 0));117     s1.insert(Point(m + 1, 0));118     s2.insert(Point(0, -1));119     s2.insert(Point(0, m + 1));120     // s2.insert(Point(0, m + 2));121     for (LL i = 1; i <= n; i++)122     {123         scanf("%I64d%I64d", &node[i].x, &node[i].y);124         node[i].id = i;125         add(node[i]);126     }127 }128 LL dis(Point a, Point b)129 {130     return ((((a.x - b.x) % mod) * ((a.x - b.x) % mod) % mod) + (((a.y - b.y) % mod) * ((a.y - b.y) % mod) % mod)) % mod;131 }132 void exq()133 {134     ans = 0;135     Point tt = node[id];136     map<Point, int, cmp1>::iterator ite = mp.find(tt);137 138     set<Point, cmp1>::iterator it1 = s1.find(tt);139     set<Point, cmp1>::iterator L1 = it1, R1 = it1;140     for (; L1->x == it1->x; --L1); ++L1;141     for (; R1->x == it1->x; ++R1);142     for (set<Point, cmp1>::iterator it = L1; it != R1;)143     {144         // cout << "it1: " << it->x << " " << it->y << endl;145         if (it == it1)146         {147             it++;148             continue;149         }150         Point nt = *it;151 152         node[it->id] = tt;153         int cnt = mp[nt];154         ans += cnt * dis(tt, nt) % mod;155         ans %= mod;156         ite->second += cnt;157         it++;158         Point ntt = *it;159         mp.erase(nt);160         s1.erase(nt);161         s2.erase(nt);162         it = s1.find(ntt);163     }164 165     set<Point, cmp2>::iterator it2 = s2.find(tt);166     set<Point, cmp2>::iterator L2 = it2, R2 = it2;167     for (; L2->y == it2->y; --L2); ++L2;168     for (; R2->y == it2->y; ++R2);169     // cout << "R2: " << R2->x << " " << R2->y << endl;170     for (set<Point, cmp2>::iterator it = L2; it != R2;)171     {172         // cout << "it2: " << it->x << " " << it->y << endl;173         // if (it == R2) break;174         if (it == it2)175         {176             it++;177             continue;178         }179         Point nt = *it;180         node[it->id] = tt;181         int cnt = mp[nt];182         ans += cnt * dis(tt, nt) % mod;183         ans %= mod;184         ite->second += cnt;185         //set<Point, cmp2>::iterator tmp = it;186         it++;187         Point ntt = *it;188         mp.erase(nt);189         s1.erase(nt);190         s2.erase(nt);191         it = s2.find(ntt);192     }193 194     printf("%I64d\n", ans);195 }196 void exu()197 {198     Point pre = node[id];199     Point now = Point(pre.x - d, pre.y, pre.id);200     node[id] = now;201     del(pre);202     add(now);203 }204 void exd()205 {206     Point pre = node[id];207     Point now = Point(pre.x + d, pre.y, pre.id);208     node[id] = now;209     del(pre);210     add(now);211 }212 void exl()213 {214     Point pre = node[id];215     Point now = Point(pre.x , pre.y - d, pre.id);216     node[id] = now;217     del(pre);218     add(now);219 }220 void exr()221 {222     Point pre = node[id];223     Point now = Point(pre.x , pre.y + d, pre.id);224     node[id] = now;225     del(pre);226     add(now);227 }228 void solve()229 {230     int T;231     scanf("%d", &T);232     char str[10];233     while (T--)234     {235         // debug();236         scanf("%s", str);237         // puts(str);238         if (str[0] == Q)239         {240             scanf("%d", &id);241             id ^= (int)ans;242             // cout << "id: " << ans << " " << id << endl;243             exq();244         }245         else246         {247             scanf("%d%I64d", &id, &d);248             id ^= (int)ans;249             // cout << "id: " << ans << " " << id << endl;250             if (str[0] == U)251                 exu();252             else if (str[0] == D)253                 exd();254             else if (str[0] == L)255                 exl();256             else257                 exr();258         }259         // debug();260     }261 }262 void output()263 {264     //265 }266 int main()267 {268     // std::ios_base::sync_with_stdio(false);269 // #ifndef ONLINE_JUDGE270 //     freopen("in.cpp", "r", stdin);271 // #endif272 273     while (~scanf("%I64d%I64d", &n, &m))274     {275         init();276         input();277         solve();278         output();279     }280     return 0;281 }
View Code

 

HDU 4879 ZCC loves march (2014多校2-1008,数据结构,STL,模拟题)