【HDU】 4831 Scenic Popularity 暴力模拟

2024-09-05 15:48

本文主要是介绍【HDU】 4831 Scenic Popularity 暴力模拟,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

Scenic Popularity

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 340    Accepted Submission(s): 110


Problem Description
  临近节日,度度熊们最近计划到室外游玩公园,公园内部包括了很多的旅游景点区和休息区,由于旅游景点很热门,导致景点区和休息区都聚集了很多人。所以度度熊在旅游之前想通过百度地图查看一下公园内各个地方的热门程度。
  假设所有景点区和休息区都是X轴直线上的一系列顶点,所对应的坐标Xi 保证唯一。每个景点区有个初始的热度值,而一个休息区(坐标为Xi)的热度值等于离它距离最近的景点区Xj的热度值(距离定义为|Xi-Xj|),如果此休息区与两个景点区的距离一样,则休息区的热度值选择两个景点区中的热度值最大值,如果两个热度值都一样,则随意选择其中一个。
  度度熊在出门之前会经常去查看百度地图,每次查看前会有某些景点区的热度值已发生改变,从而也会导致周围的休息区的热度值发生改变,然后度度熊想知道当前热度值<=Rk的顶点(包括景点区和休息区)有多少个
 
 
Input
  输入数据的第一行是测试Case的个数(T<=100)。
  每个Case的第一行是N(0<N<=10000),表示景点区和休息区的总数。
  接着会有N行数据,每一列首先是顶点的X坐标Xi (0< Xi <=1e8),第二列是一个整数Hi(0=<Hi <=100000),如果Hi 不为0,则表示当前顶点为风景区且初始的热度值为Hi,否则表示当前顶点为休息区。这N行数据会按照坐标Xi递增的方式依次给出。
  接着的一行数据是操作的次数K(K<=100),最后会有K行数据,每一行的第一列要么是’U’或者’Q’,’U’表示当前操作为更改热度操作,’Q’表示当前操作为查询操作。如果是更改操作,接着会有两列数据,分别是热度值要改变的风景区的下标Lk(0<=Lk<N)以及改变后的热度值Vk(0< Vk<=100000);如果是查询操作,第二列是要查询的热度范围Rk(0< Rk<=100000)
 
 
Output
  对于第k组测试数据,第一行输出Case #k:,接下来对每次查询操作(即Q操作)会输出一个整数,表示满足条件的顶点数有多少个
 
 
Sample Input
1 4 10 020 330 0 40 23Q 3 U 3 4 Q 3
 
 
Sample Output
Case #1:42
 
 
Source
2014年百度之星程序设计大赛 - 初赛(第二轮)
 
 
题目分析:
 

跟着题意模拟就行了,主要是通过对每个休息区保存离他距离最近的至多两个风景区(不可能比这个还多,因为只在X轴上),然后对每个风景区能影响到的休息区连边,当风景区的热度改变时, 就通过这条边跳到休息区,进而改变休息区的热度值(可能不会改变)。


 代码如下:


#include <stdio.h>
#include <string.h>
typedef long long ll;
const int O = 1000000;
const int maxn = 10005;
typedef struct E{int v, n;
}E;
typedef struct point{int x, h;int g[2];
}point;
point a[maxn];
E edge[O];
int Adj[maxn], l;
int f[maxn];
void addedge(int u, int v){edge[l].v = v; edge[l].n = Adj[u]; Adj[u] = l++;
}
void check(int i, int i1, int i2){if(!i2 || a[i1].h >= a[i2].h) a[i].h = a[i1].h;else if(a[i2].h > a[i1].h) a[i].h = a[i2].h;
}
int abs(int x){return x > 0 ? x : -x;
}
int read(){char ch = ' ';while(ch < '0' || ch > '9') ch = getchar();int x = 0;while(ch >= '0' && ch <= '9'){x = x * 10 + ch - '0';ch = getchar();}return x;
}
void work(){int n, q, x, y;char ch[2];n = read();memset(Adj, -1, sizeof(Adj[0]) * (n + 1));memset(a, 0, sizeof(a[0]) * (n + 1));l = 0;int flag = 0, pre = 0, next = 0;for(int i = 1; i <= n; ++i){a[i].x = read(); a[i].h = read();if(a[i].h) flag = 1;}if(flag){for(int i = 1; i <= n; ++i){if(!a[i].h){a[i].g[0] = pre;if(next <= i && next <= n){next = i + 1;while(next <= n){if(a[next].h) break;++next;}}a[i].g[1] = (next <= n ? next : 0);if(!a[i].g[0] || abs(a[i].x - a[a[i].g[0]].x) > abs(a[a[i].g[1]].x - a[i].x)){a[i].g[0] = a[i].g[1];a[i].g[1] = 0;}else if(abs(a[i].x - a[a[i].g[0]].x) < abs(a[a[i].g[1]].x - a[i].x)){a[i].g[1] = 0;}if(a[i].g[0]) addedge(a[i].g[0], i);if(a[i].g[1]) addedge(a[i].g[1], i);}else pre = i;}}for(int i = 1; i <= n; ++i){if(!a[i].h) check(i, a[i].g[0], a[i].g[1]);}scanf("%d", &q);for(int i = 0; i < q; ++i){scanf("%s", ch);if(ch[0] == 'Q'){int cnt = 0;scanf("%d", &x);for(int j = 1; j <= n; ++j) if(a[j].h <= x) cnt++;printf("%d\n", cnt);}else{scanf("%d%d", &x, &y);a[++x].h = y;for(int j = Adj[x]; ~j; j = edge[j].n){int v = edge[j].v;check(v, a[v].g[0], a[v].g[1]);}}}
}
int main(){int t, cas;for(scanf("%d", &t), cas = 1; cas <= t; ++cas){printf("Case #%d:\n", cas);work();}return 0;
}


这篇关于【HDU】 4831 Scenic Popularity 暴力模拟的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



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

相关文章

【C++】_list常用方法解析及模拟实现

相信自己的力量,只要对自己始终保持信心,尽自己最大努力去完成任何事,就算事情最终结果是失败了,努力了也不留遗憾。💓💓💓 目录   ✨说在前面 🍋知识点一:什么是list? •🌰1.list的定义 •🌰2.list的基本特性 •🌰3.常用接口介绍 🍋知识点二:list常用接口 •🌰1.默认成员函数 🔥构造函数(⭐) 🔥析构函数 •🌰2.list对象

usaco 1.3 Mixing Milk (结构体排序 qsort) and hdu 2020(sort)

到了这题学会了结构体排序 于是回去修改了 1.2 milking cows 的算法~ 结构体排序核心: 1.结构体定义 struct Milk{int price;int milks;}milk[5000]; 2.自定义的比较函数,若返回值为正,qsort 函数判定a>b ;为负,a<b;为0,a==b; int milkcmp(const void *va,c

usaco 1.2 Transformations(模拟)

我的做法就是一个一个情况枚举出来 注意计算公式: ( 变换后的矩阵记为C) 顺时针旋转90°:C[i] [j]=A[n-j-1] [i] (旋转180°和270° 可以多转几个九十度来推) 对称:C[i] [n-j-1]=A[i] [j] 代码有点长 。。。 /*ID: who jayLANG: C++TASK: transform*/#include<

poj 3974 and hdu 3068 最长回文串的O(n)解法(Manacher算法)

求一段字符串中的最长回文串。 因为数据量比较大,用原来的O(n^2)会爆。 小白上的O(n^2)解法代码:TLE啦~ #include<stdio.h>#include<string.h>const int Maxn = 1000000;char s[Maxn];int main(){char e[] = {"END"};while(scanf("%s", s) != EO

hdu 2093 考试排名(sscanf)

模拟题。 直接从教程里拉解析。 因为表格里的数据格式不统一。有时候有"()",有时候又没有。而它也不会给我们提示。 这种情况下,就只能它它们统一看作字符串来处理了。现在就请出我们的主角sscanf()! sscanf 语法: #include int sscanf( const char *buffer, const char *format, ... ); 函数sscanf()和

hdu 2602 and poj 3624(01背包)

01背包的模板题。 hdu2602代码: #include<stdio.h>#include<string.h>const int MaxN = 1001;int max(int a, int b){return a > b ? a : b;}int w[MaxN];int v[MaxN];int dp[MaxN];int main(){int T;int N, V;s

hdu 1754 I Hate It(线段树,单点更新,区间最值)

题意是求一个线段中的最大数。 线段树的模板题,试用了一下交大的模板。效率有点略低。 代码: #include <stdio.h>#include <string.h>#define TREE_SIZE (1 << (20))//const int TREE_SIZE = 200000 + 10;int max(int a, int b){return a > b ? a :

hdu 1166 敌兵布阵(树状数组 or 线段树)

题意是求一个线段的和,在线段上可以进行加减的修改。 树状数组的模板题。 代码: #include <stdio.h>#include <string.h>const int maxn = 50000 + 1;int c[maxn];int n;int lowbit(int x){return x & -x;}void add(int x, int num){while

hdu 3790 (单源最短路dijkstra)

题意: 每条边都有长度d 和花费p,给你起点s 终点t,要求输出起点到终点的最短距离及其花费,如果最短距离有多条路线,则输出花费最少的。 解析: 考察对dijkstra的理解。 代码: #include <iostream>#include <cstdio>#include <cstdlib>#include <algorithm>#include <cstrin

hdu 2489 (dfs枚举 + prim)

题意: 对于一棵顶点和边都有权值的树,使用下面的等式来计算Ratio 给定一个n 个顶点的完全图及它所有顶点和边的权值,找到一个该图含有m 个顶点的子图,并且让这个子图的Ratio 值在所有m 个顶点的树中最小。 解析: 因为数据量不大,先用dfs枚举搭配出m个子节点,算出点和,然后套个prim算出边和,每次比较大小即可。 dfs没有写好,A的老泪纵横。 错在把index在d