首页 > 代码库 > HDU 4941
HDU 4941
昨天做的多校题目。
题目大概就是说有n*m的一个方格，其中k个格子里放了数字。然后进行q个操作，1是交换列，2是交换行，3是查询当前x，y有什么数字，没有输出0。
题目不难，但是写起来有点别扭。主要的思想是hash。
#include <iostream>#include <cstdio>#include <algorithm>#include <cstring>using namespace std;#define maxn 100010struct N{ int x, y, val;} node[maxn];int x[maxn], y[maxn];int xx[maxn], yy[maxn];int changex[maxn], changey[maxn];int n, m, k;void solve1(){ int q; cin >> q; while(q--) { int a, b, c; scanf("%d%d%d", &a, &b, &c); if(a == 3) puts("0"); } return ;}int find(int qq[], int q, int tk){ // for(int i = 0; i < tk; i ++) // cout << qq[i] << endl; int l = lower_bound(qq, qq+tk, q) - qq; int r = upper_bound(qq, qq+tk, q) - qq; // cout << qq[l] << " " << qq[r] << " " << q << endl; if(l > r) return -1; if(l == r-1) return l; else while(1) l++;}int solve(int qx, int qy){ qx = changex[qx]; qy = changey[qy]; int l = lower_bound(x, x+k, xx[qx]) - x; int r = upper_bound(x, x+k, xx[qx]) - x; r--; qy = yy[qy]; while(l <= r) { int m = (l + r) / 2; if(node[m].y > qy) r = m-1; else if(node[m].y < qy) l = m+1; else return node[m].val; } return 0;}bool cmp(N a, N b){ if(a.x == b.x) return a.y < b.y; return a.x < b.x;}int main(){ // f//reopen("in.txt", "r", stdin); //freopen("out(2).txt", "w", stdout); int t; cin >> t; for(int Ca = 1; Ca <= t; Ca++) { scanf("%d%d%d", &n, &m, &k); for(int i = 0; i < k; i++) { scanf("%d%d%d", &node[i].x, &node[i].y, &node[i].val); x[i] = node[i].x; y[i] = node[i].y; } printf("Case #%d:\n", Ca); sort(node, node + k, cmp); sort(x, x + k); sort(y, y + k); if(!k) { solve1(); continue; } xx[0] = x[0]; int sumx = 1; for(int i = 1; i < k; i++) if(x[i] != x[i-1]) xx[sumx++] = x[i]; yy[0] =y[0]; int sumy = 1; for(int i = 1; i < k; i++) if(y[i] != y[i-1]) yy[sumy++] = y[i]; for(int i = 0; i < sumx; i++) changex[i] = i; for(int i = 0; i < sumy; i++) changey[i] = i; int q; cin >> q; while(q--) { int a, b, c; scanf("%d%d%d", &a, &b, &c); //cout << a << " " << b << " " << c << endl; if(a == 2) { b = find(yy, b, sumy); c = find(yy, c, sumy); if(b == -1 && c == -1) continue; swap(changey[b], changey[c]); } else if(a == 1) { b = find(xx, b, sumx); c = find(xx, c, sumx); //cout << a << " " << b << " " << c << endl; if(b == -1 && c == -1) continue; swap(changex[b], changex[c]); } else { b = find(xx, b, sumx); c = find(yy, c, sumy); if(b == -1 || c == -1) puts("0"); else printf("%d\n", solve(b, c)); } } }}
开始的时候WA了几发，因为upper_bound()， 返回的是大于键值的第一个位置，我以为是小于等于键值的第一个位置。。。
真心跪了，我这基础是有多不扎实啊。
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。