HDOJ 4941 Magical Forest

2024-05-05 12:38
文章标签 forest hdoj magical 4941

本文主要是介绍HDOJ 4941 Magical Forest,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

题目:

Magical Forest

Time Limit: 24000/12000 MS (Java/Others)    Memory Limit: 131072/131072 K (Java/Others)
Total Submission(s): 389    Accepted Submission(s): 186


Problem Description
There is a forest can be seen as N * M grid. In this forest, there is some magical fruits, These fruits can provide a lot of energy, Each fruit has its location(Xi, Yi) and the energy can be provided Ci. 

However, the forest will make the following change sometimes: 
1. Two rows of forest exchange. 
2. Two columns of forest exchange. 
Fortunately, two rows(columns) can exchange only if both of them contain fruits or none of them contain fruits. 

Your superior attach importance to these magical fruit, he needs to know this forest information at any time, and you as his best programmer, you need to write a program in order to ask his answers quick every time.

Input
The input consists of multiple test cases. 

The first line has one integer W. Indicates the case number.(1<=W<=5)

For each case, the first line has three integers N, M, K. Indicates that the forest can be seen as maps N rows, M columns, there are K fruits on the map.(1<=N, M<=2*10^9, 0<=K<=10^5)

The next K lines, each line has three integers X, Y, C, indicates that there is a fruit with C energy in X row, Y column. (0<=X<=N-1, 0<=Y<=M-1, 1<=C<=1000)

The next line has one integer T. (0<=T<=10^5)
The next T lines, each line has three integers Q, A, B. 
If Q = 1 indicates that this is a map of the row switching operation, the A row and B row exchange. 
If Q = 2 indicates that this is a map of the column switching operation, the A column and B column exchange. 
If Q = 3 means that it is time to ask your boss for the map, asked about the situation in (A, B). 
(Ensure that all given A, B are legal. )

Output
For each case, you should output "Case #C:" first, where C indicates the case number and counts from 1.

In each case, for every time the boss asked, output an integer X, if asked point have fruit, then the output is the energy of the fruit, otherwise the output is 0.

Sample Input
  
1 3 3 2 1 1 1 2 2 2 5 3 1 1 1 1 2 2 1 2 3 1 1 3 2 2

Sample Output
  
Case #1: 1 2 1

传送门:点击打开链接

解题思路:

离散化。我们可以存储所有给出的点,对所有的点的行和列进行离散化。可以用map来进行映射,定义mpr表示mpr[i]表示现在第i行是原来的mpr[i]行。在进行交换操作时,只需要将mpr和mpc的值进行交换,查找时进行二分查找。

代码:

#include <cstdio>
#include <map>
#include <cstring>
#include <algorithm>
using namespace std;const int MAXN = 1e5+10;
struct Forest
{int r, c, v;
};
Forest p[MAXN];
map<int, int> mpr;
map<int, int> mpc;bool cmp(const Forest &a, const Forest &b)
{return a.r==b.r ? a.c<b.c : a.r<b.r;
}int find(int row, int col, int k)
{row = 0==mpr[row] ? row : mpr[row];col = 0==mpc[col] ? col : mpc[col];int l = 0, r = k-1;while(l <= r){int mid = (l+r) >> 1;if(p[mid].r==row && p[mid].c==col)return p[mid].v;if(p[mid].r<row || (p[mid].r==row && p[mid].c<col))l = mid + 1;elser = mid - 1;}return 0;
}int main()
{int icase, n, m, t, k;while(~scanf("%d", &icase)){int w = 1;while(icase--){mpr.clear(); mpc.clear();printf("Case #%d:\n", w++);scanf("%d%d%d", &n, &m, &k);for(int i = 0; i < k; ++i){scanf("%d%d%d", &p[i].r, &p[i].c, &p[i].v);//  mpr[p[i].r] = p[i].r; mpc[p[i].c] = p[i].c;}sort(p, p+k, cmp);scanf("%d", &t);while(t--){int q, a, b;scanf("%d%d%d", &q, &a, &b);switch(q){case 1:{int t1 = 0==mpr[a] ? a : mpr[a];int t2 = 0==mpr[b] ? b : mpr[b];mpr[a] = t2;mpr[b] = t1;break;}case 2:{int t1 = 0==mpc[a] ? a : mpc[a];int t2 = 0==mpc[b] ? b : mpc[b];mpc[a] = t2;mpc[b] = t1;break;}case 3:{printf("%d\n", find(a, b, k));break;}}}}}return 0;
}



这篇关于HDOJ 4941 Magical Forest的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/961740

相关文章

2014多校联合七(HDU 4937 HDU 4938 HDU 4939 HDU 4941)

好几天没写题解了… 都怪我太弱  补题补不动… HDU 4937 Lucky Number 题意:一个数字如果只有3456这四种数字组成  那么这个数字是幸运的  问  给出一个x  它在几种进制下是幸运的  如果无穷输出-1 思路: 分类讨论  如果x是3或4或5或6  那么一定有无穷个进制满足(从十进制开始…)  直接输出-1 除去上述情况  那么我们可以将一个数字写成这样 a0 +

1034 forest

大水题,WA到吐了,结果发现犯了一弱智错误,擦 1.定义dept[]数组,主要用bfs ,将子节点的dept值累加父节点的dept值,遍历一颗或者若干树。从根节点(bepointed[]值为false的点)出发遍历全棵树。 2.存储方式:邻接表存边 vector+queue  , #include <iostream>#include<queue>#include<vector>

hdoj 2371 decoded string. Decode the Strings

http://acm.hdu.edu.cn/showproblem.php?pid=2371 题意:给出编码的原则,给一个字符串,输出该字符串经过m次解码后的字符串。 啊啊啊啊。。。。无耻的看错题意了,以为给出字符串输出经过m次解码的后的字符串,样例死活过不了,赛后才发现问的是“decoded string”. 即解码后的字符串。。 思路:对于 5 3 2 3 1 5 4 helol

孤立森林 Isolation Forest 论文翻译(上)

README 自己翻译的+参考有道,基本是手打的可能会有很多小问题。 括号里的斜体单词是我觉得没翻译出那种味道的或有点拿不准的或翻译出来比较奇怪的地方,尤其是profile、swamping和masking这三个词不知道怎样更准确。 欢迎指正和讨论,需要Word版可以留言。 孤立森林 摘要         大多数现有的基于模型的异常检测算法构建了一个正常实例的特征轮廓(profil

HDOJ 1874 畅通工程续——结构体模拟邻接链表的SPFA算法

Problem Description 某省自从实行了很多年的畅通工程计划后,终于修建了很多路。不过路多了也不好,每次要从一个城镇到另一个城镇时,都有许多种道路方案可以选择,而某些方案要比另一些方案行走的距离要短很多。这让行人很困扰。 现在,已知起点和终点,请你计算出要从起点到终点,最短需要行走多少距离。   Input 本题目包含多组数据,请处理到文

Aizu 2541 Magical Bridges

题意: n个岛屿,由m条桥连接,其中有k条是魔法桥,你可以用魔法把他们变成相同长度。 求在执行魔法后,两个起点S1和S2到终点T的最短路的最小绝对差。 (1≤n≤1000,1≤m≤2000,1≤k≤100) (1\leq n\leq 1000,1\leq m\leq 2000,1\leq k\leq 100) S1 S_1和 S2 S_2到 T T的最短路将会是如 j×x+disj\t

九度OJ-1435-迷瘴(HDOJ-2570)

题目地址:点击打开链接 题目描述: 通过悬崖的yifenfei,又面临着幽谷的考验—— 幽谷周围瘴气弥漫,静的可怕,隐约可见地上堆满了骷髅。由于此处长年不见天日,导致空气中布满了毒素,一旦吸入体内,便会全身溃烂而死。 幸好yifenfei早有防备,提前备好了解药材料(各种浓度的万能药水)。现在只需按照配置成不同比例的浓度。 现已知yifenfei随身携带有n种浓度的万能药水,体积V都相

[LightOJ 1342] Aladdin and the Magical Sticks (期望的线性性质+几何分布+邮票收集问题)

LightOJ - 1342 有 N根棍子,每根棍子都有一个权值 其中有若干根可识别的,若干根不可识别的 抽到了可识别的棍子,就不放回,抽到了不可识别的,就要放回 问所有棍子都至少被抽过一次后的期望权值和 根据期望的线性性, E(CX)=CE(X) E(CX) = CE(X) 所以可以对每根棍子求一下它被抽到的期望次数,再乘以它的权值 对于不可识别的棍子,由于它被抽到的概率

Deep Forest,非神经网络的深度模型

欢迎转载,转载请注明:本文出自Bin的专栏blog.csdn.net/xbinworld。  深度学习最大的贡献,个人认为就是表征学习(representation learning),通过端到端的训练,发现更好的features,而后面用于分类(或其他任务)的输出function,往往也只是普通的softmax(或者其他一些经典而又简单的方法)而已,所以,只要特征足够好,分类

HDoj Integer Inquiry(大数)

真心要哭了。。这几天在搞大数  高精度计算  昨晚在机房敲 很快敲完了  就是过不了啊过不了  劳资都想骂脏话啊   NMB  一开始不输出前面的0啊 过不了  看discuss 百度 找了个AC的代码 找了几组测试数据  那个代码输出前面的0啊  我的妈  今天有找了个代码 不输出0啊 我的天。。。真心要被逼疯了  幸好还是AC了。。。算是有进步吧  之前的心态肯定坚持不下来啊