`
lovnet
  • 浏览: 6865603 次
  • 性别: Icon_minigender_1
  • 来自: 武汉
文章分类
社区版块
存档分类
最新评论

NYOJ 228 士兵杀敌五(插线问线__离线版)

 
阅读更多

题目链接:Click here~~

观察这道题你会发现它的特点:查询操作全部在插完后进行,也就是传说中的离线问题。

这道题有种巧妙的O(n)的做法。其思想和树状数组的插线思想类似。

#include <stdio.h>
#define base 10003
const int M = 1000003;
int c[M];
int main()
{
    int n,m,Q,a,b,x;
    scanf("%d%d%d",&n,&m,&Q);
    while(m--)
    {
        scanf("%d%d%d",&a,&b,&x);
        c[a]   += x;                //把从a  到n的值全部加x
        c[b+1] -= x;                //把从b+1到n的值全部减x
    }
    for(int i=1;i<=n;i++)
        c[i] += c[i-1];             //此操作过后得到的就是每个士兵的战功
    for(int i=1;i<=n;i++)
        c[i] = (c[i-1]+c[i])%base;  //得到前缀和
    while(Q--)
    {
        scanf("%d%d",&a,&b);
        printf("%d\n",(c[b]-c[a-1]+base)%base);//+base是因为由于取前缀和的时候,保存的是余数的值,所以可能导致c[b]<c[a-1],所以要+base保证它为正。
    }
	return 0;
}

其中的奥妙,还是请读者细细体会吧。

分享到:
评论

相关推荐

    NYOJ题目 离线版

    这个离线版包含了NYOJ的所有题目,为编程爱好者和参赛者提供了一个方便的本地化练习环境。通过爬虫技术,这些题目被转化为独立的网页,使得用户可以在没有网络连接的情况下查阅和练习题目。 离线版的制作通常是为了...

    ACM在线评测系统 NYOJ 题库 离线看题网页版 nyoj

    用户可以通过离线看题网页版访问这些题目,即使在无网络连接的情况下也能预览题目详情。 2. **代码提交**:用户可以编写代码并提交到系统,系统会使用特定的评测环境对代码进行编译和运行。这通常包括C++, Java, ...

    nyoj部分ACM答案

    ### nyoj部分ACM答案解析 #### 背景与目的 本篇文章旨在解析一个针对NYOJ(网络在线裁判系统)中ACM题目解答的示例代码。该代码使用了C++语言,并且主要涉及到了回溯算法的实现。对于初学者来说,通过深入理解这段...

    NYOJ.290.DictionaryTree.zip_trie树c_字典树_高级数据结构

    在NYOJ.290.DictionaryTree.cpp文件中,可能包含了以下内容: 1. `TrieNode`结构体定义,用于表示Trie树的节点。 2. 插入函数,如`insert(char *str)`,用于将字符串插入到Trie树中。 3. 查询函数,如`search(char *...

    ACM题库题库啊

    离线版的NYOJ可能是将该平台的部分内容打包成CHM文件,方便用户在没有网络的情况下查阅和练习。这个CHM文件可能包含题目的详细描述、数据范围、样例输入输出,以及可能的解题思路或者算法分析。 “北大ACM题库.zip...

    nyoj16.rar_site:www.pudn.com

    标题中的“nyoj16.rar”可能是指一个编程竞赛或者在线判题系统(如NOIP、NYOJ)的问题编号16的题目,而“site:www.pudn.com”通常用于搜索引擎查询,表明这个压缩文件可能来源于PUDN(普渡大学电子论坛)这个网站。...

    nyoj 61 传纸条(一)

    双线程动态规划问题,很值得练习。传一个ac代码,测试一下csdn的功能。

    算法-矩形嵌套(NYOJ-16)(包含源程序).rar

    《算法-矩形嵌套(NYOJ-16)》是针对计算机科学中的一个典型问题进行探讨的资源包,其中包含了解决该问题的源程序。这个问题涉及到数据结构、图论以及算法设计等多个核心领域,是编程竞赛或算法学习中的常见题目。在...

    nyoj_lvy实战开发系列《三》: 获取城市信息

    由于微信小程序没有方法可以获得当前用户所在城市的信息,所以需要调用方法来获取城市信息,用了两个方法去发送请求并返回城市信息  1. @Controller public class WechatLocationManager { private Logger logger ...

    nyoj_lvy实战开发系列《二》: 微信端开发:登录小程序

    这个小程序的主要目的是为了用户用微信的用户信息登录后将用户信息授权存入自己的数据库中,这样以后每次微信登录得到的code 所得到的 openid 可以在项目的数据库中查到该用户的相关信息。 在测试的过程中,需要用户...

    nyoj_lvy实战开发系列《一》:发送JSON信息,加密数据解密算法,UnionID机制说明

    前期小程序开发只进行到根据微信用户登录获取的code 去微信的API去获取到该用户的openId和session_key,到了第二阶段,老大让我重写OAuthManager的代码来实现微信小程序和微信公众号平台获取用户信息的优化,即将...

    南阳理工oj stl练习ac代码

    NYOJ(南阳理工在线判题系统)是南阳理工学院开发的OJ平台,它提供编程题目的提交和评测服务,帮助学生提升编程技能。在这个平台上,用户可以通过提交代码并获取反馈来检验自己对STL的理解和应用。 在STL的练习...

    南阳理工学院OJ第1版解题报告V1.0.pdf

    ### 南阳理工学院OJ第1版解题报告概览 #### 1. A+B Problem 虽然解题思路在报告中被省略,但我们可以推测这是一个基础的数学加法问题,涉及到数字输入与基本算术操作。此类题目旨在测试初学者对编程语言基本输入...

    经典动态规划 南阳104最大和

    给定一个由整数组成二维矩阵(r*c),现在需要找出它的一个子矩阵,使得这个子矩阵内的所有元素之和最大,并把这个子矩阵称为最大子矩阵。

Global site tag (gtag.js) - Google Analytics