首页 > 试题广场 >

交换查询

[编程题]交换查询
  • 热度指数:1222 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 128M,其他语言256M
  • 算法知识视频讲解

M有一个N*M的方格,行列下标均从0开始。其中有K个方格中有数字,表示为(X, Y)方格中有数字C。对方格有2种操作,交换方格的两行或者交换方格的两列。

M希望随时能够知道在经过一系列交换之后某一方格中是否含有数字,并且如果有的话,数字是多少。


输入描述:
输入数据第一行包含3个整数N, M, K。表示N行M列的方格,并且其中K个方格有数字。
(1 <= N, M <= 10^5, 0 <= K <= 10^5)
接下来K行,每行有3个整数,X, Y, C,表示(X,Y)方格中有数字C。
(0 <= X <= N - 1, 0 <= Y <= M - 1, 1 <= C <= 1000)
接下来有一个整数T,表示有T次操作或询问。(0 <= T <= 10^5)
接下来T行,买行有三个整数Q, A, B。
当Q == 0时,交换行A和行B所有方格。
当Q == 1时,交换列A和列B所有方格。
当Q == 2时,询问(A, B)是否有数字,如果有则输出该数字,如果没有输出-1。
数据保证Q,A,B均在合法的范围之内。


输出描述:
对于每个询问,输出一个整数表示其答案。
示例1

输入

3 3 2
1 1 1
2 2 2
5
2 1 1
0 0 1
1 0 1
2 1 1
2 2 2

输出

1
-1
2

说明

首先有3x3的方格,其中(1,1)有数字1,(2,2)有数字2,即:
-1 -1 -1
-1 1 -1
-1 -1 2
5次操作,
第一次查询(1,1)得到1;
第二次交换行1和行2,即:
-1 1 -1
-1 -1 -1
-1 -1 2
第三次交换列1和列2,即:
1 -1 -1
-1 -1 -1
-1 -1 2
第四次查询(1,1)得到-1;
第五次查询(2,2)得到2;
#include <bits/stdc++.h>
using namespace std;

int main(){
    int n, m, k, x, y, c, t, q, a, b;
    cin>>n>>m>>k;
    unordered_map<long, int> M;
    int px[n], py[m];
    for(int i=0;i<n;i++)
        px[i] = i;
    for(int i=0;i<m;i++)
        py[i] = i;
    for(int i=0;i<k;i++){
        cin>>x>>y>>c;
        M[x*m+y] = c;
    }
    cin>>t;
    while(t--){
        cin>>q>>a>>b;
        if(q==0)
            swap(px[a], px[b]);
        else if(q==1)
            swap(py[a], py[b]);
        else if(q==2){
            int s = px[a]*m  + py[b];
            if(M.find(s) == M.end())
                cout<<-1<<endl;
            else
                cout<<M[s]<<endl;
        }
    }
    return 0;
}

编辑于 2020-01-07 10:57:42 回复(0)
/*
查询交换操作
本题单次的查询、交换操作需要O(1)完成
交换优化:将指向行列的数字交换
查询优化:设置unordered_map字典
*/
#include <bits/stdc++.h>
using namespace std;
unordered_map<long, int> dic;

int main(void)
{
//    freopen("input.txt", "r", stdin);
    int n, m, k, t, x, y, c, Q, a, b, ans;
    cin >> n >> m >> k;
    int pointX[n], pointY[m];
    for (int i = 0; i < n; ++i) {
        pointX[i] = i;
    }
    for (int i = 0; i < m; ++i) {
        pointY[i] = i;
    }
    for(int i = 0; i < k; i++) {
        scanf("%d%d%d", &x, &y, &c);
        dic[x * m + y] = c;
    }
    cin >> t;
    while(t--) {
        scanf("%d%d%d", &Q, &a, &b);
        if(Q == 2) {
            int key = pointX[a] * m + pointY[b];
            int ans;
            if(dic.find(key) == dic.end()) ans = -1;
            else ans = dic[key];
            printf("%d\n", ans);
        } else if(Q == 0) {
            swap(pointX[a], pointX[b]);
        } else {
            swap(pointY[a], pointY[b]);
        }
    }
    return 0;
}

发表于 2019-07-17 16:16:20 回复(0)
开辟一个临时数组,数组的长度为max(n,m),用于交换
发表于 2019-04-03 21:12:01 回复(0)