Super Mario2012 ACM/ICPC Asia Regional Hangzhou Online

2024-01-10 07:18

本文主要是介绍Super Mario2012 ACM/ICPC Asia Regional Hangzhou Online,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

 这道题和树状数组求逆序数体很像,但是比赛的时候就是建立不好解题模型,比赛时好多人说需要离散化,看完别人的解题报告后才发现此题处理的便不是以前处理的值,这一题处理的是下标,用的是树状数组的离线算法,这题给我的感觉就是 自己的数状数组跟没学一个样,今后需要多多努力。

思路:分别对原始数组和要处理的值按从小到大排序,然后定义两个指针扫描排过序的数组,写两个条件判断,什么时候向树状数组插入,什么时候查询,

 

 

 

#include<iostream>
#include<stack>
#include<string.h>
#include<string>
#include<map>
#include<set>
#include<sstream>
#include<fstream>
#include<iterator>
#include<vector>
#include<algorithm>
#include<numeric>
#include<list>
#define N 100010
#define lowbit(x) (x&(-x))
#define CLR(arr,val) memset(arr,val,sizeof(arr))
using namespace std;
int s[N];
typedef struct node
{
int val;
int index;
}Node;
typedef struct snode
{
int L;
int R;
int val;
int index;
}Snode;
Node s1[N];
Snode s2[N];
int answer[N];
int n,m;
void add(int x)
{
while(x<=n)
{
s[x]++;
x+=lowbit(x);
}
}
int sum(int x)
{
int ans=0;
while(x>0)
{
ans+=s[x];
x-=lowbit(x);
}
return ans;
}
bool cmp(const Node& x,const Node& y)
{return x.val<y.val;}
bool cmp1(const Snode& x,const Snode& y)
{return x.val<y.val;}
void input(int& a)
{
char ch;
while((ch=getchar())>'9'||ch<'0') ;
for(a=0;ch>='0'&&ch<='9';ch=getchar()) a=a*10+ch-'0';
}
int main()
{
int T;
input(T);
for(int k=1;k<=T;++k)
{
input(n),input(m);
for(int i=1;i<=n;++i) input(s1[i].val),s1[i].index=i;
for(int i=0;i<m;++i)  input(s2[i].L),input(s2[i].R),input(s2[i].val),s2[i].L++,s2[i].R++,s2[i].index=i;
sort(s1+1,s1+1+n,cmp);
sort(s2,s2+m,cmp1);
CLR(s,0);
CLR(answer,0);
int i=1,j=0;
while(j<m)
{
while(i<=n)
{
if(s1[i].val>s2[j].val) break;
add(s1[i].index);
i++;
}
while(j<m)
{
if(i<=n&&s1[i].val<=s2[j].val) break;
answer[s2[j].index]=sum(s2[j].R)-sum(s2[j].L-1);
j++;
}
}
printf("Case %d:\n",k);
for(int i=0;i<m;++i) printf("%d\n",answer[i]);
}return 0;
}


 

这篇关于Super Mario2012 ACM/ICPC Asia Regional Hangzhou Online的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



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

相关文章

认识、理解、分类——acm之搜索

普通搜索方法有两种:1、广度优先搜索;2、深度优先搜索; 更多搜索方法: 3、双向广度优先搜索; 4、启发式搜索(包括A*算法等); 搜索通常会用到的知识点:状态压缩(位压缩,利用hash思想压缩)。

Regionals 2004 Asia - Beijing Argus 小根堆

点击打开链接 小根堆 import java.io.BufferedReader;import java.io.InputStream;import java.io.InputStreamReader;import java.io.PrintWriter;import java.math.BigInteger;import java.util.StringTokeni

问:Super与this在Java中有什么区别?

this: this 关键字用于引用当前对象。它通常用于区分成员变量和方法参数或局部变量。在实例方法中,this 指向调用该方法的对象。在构造函数中,this 指向正在被初始化的对象。 super: super 关键字用于引用父类(超类)的构造函数、方法或变量。在子类的构造函数中,super() 用于调用父类的构造函数。在子类的方法中,super.methodName() 用于调用父类的方法。

Unity 资源 之 Super Confetti FX:点亮项目的璀璨粒子之光

Unity 资源 之 Super Confetti FX:点亮项目的璀璨粒子之光 一,前言二,资源包内容三,免费获取资源包 一,前言 在创意的世界里,每一个细节都能决定一个项目的独特魅力。今天,要向大家介绍一款令人惊艳的粒子效果包 ——Super Confetti FX。 二,资源包内容 💥充满活力与动态,是 Super Confetti FX 最显著的标签。它宛如一位

MTK Android P/Q system/vendor/super快速打包

一、Android 新版本默认开启了动态分区,把system vendor  product等分区打包成一个super分区。这对于我们使用替换分区的方法来排查问题不是很方便,直接替换一个super也不知道到底是哪个部分导致的。所以我们需要自己制作super.img来缩小范围。下面讲讲如何快速生成system、vendor、super,以及vbmeta(校验image,不匹配可能会导致不开机) 二

? extends T 和 ? super T分别是什么意思?有什么不同?

<? extends T>首先你很容易误解它为继承于T的所有类的集合,这是大错特错的,相信能看下去你一定见过或用过List<? extends T>吧?为什么我说理解成一个集合是错呢?如果理解成一个集合那为什么不用List<T>来表示?所以<? extends T>不是一个集合,而是T的某一种子类的意思,记住是一种,单一的一种,问题来了,由于连哪一种都不确定,带来了不确定性,所以是不可能通过add

【转载】ACM感悟

今天看了一篇我们学校前辈的ACM的感悟,觉得写的十分有道理,这里转载,文章还会不断的改进和更新。 原文链接:http://www.cnblogs.com/Chierush/p/3760870.html?ADUIN=1339764596&ADSESSION=1401536826&ADTAG=CLIENT.QQ.5329_.0&ADPUBNO=26349 声明:本文是写给弱校ACM新手的一点

我们依旧在追梦的路上-山东省第六届ACM比赛总结

这场比赛从结果而言达到了预期(金牌),从过程而言和我的预期相差甚远(打的太乱,个人发挥很差),还好关键时刻队友抗住压力,负责后果真的不堪设想。 热身赛 热身赛纯粹测机器的,先把A,B,C草草水过(A题小写x打成大写的也是醉了),我和老高开始各种测机器,long long不出所料是lld的,试了一下除0和数组越界的re问题,发现没有re,只有wa(甚至数组越界还AC了),至于栈深的话也没过多追

java基础总结11-面向对象7(super关键字)

在JAVA类中使用super来引用父类的成分,用this来引用当前对象,如果一个类从另外一个类继承,我们new这个子类的实例对象的时候,这个子类对象里面会有一个父类对象。怎么去引用里面的父类对象呢?使用super来引用,this指的是当前对象的引用,super是当前对象里面的父对象的引用。 1 super关键字测试 package cn.galc.test;/*** 父类* @autho

ACM东北地区程序设计大赛

不得不说随着参赛级别的提高,题目真的是越来越难啊,不过队长真是给力啊,在我们三个共同努力之下拿下了地区赛三等奖,哈哈我们可是大一唯一一只获奖队,终于在这次比赛打败了田大神。。。大神是失手了,俺和他差距还是挺大的。。。队友陈彤马上要去服兵役了,他说这是我们送给他最好的离别礼物,希望那家伙在部队好好干,以后谁干揍我!!!东北地区赛结束后,今年已经估计没机会参加亚洲区比赛了,赶紧补高数和线数啊!!别挂了