首页 > 代码库 > 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 }
HDU 4879 ZCC loves march (2014多校2-1008,数据结构,STL,模拟题)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。