正文

bzoj1452:[jsoi2009]count

mt-li  2022-02-17  696

关键词：

Description

技术分享图片

Input

技术分享图片

Output

技术分享图片

Sample Input

Sample Output

1
2

HINT

技术分享图片

题目传送门

话说这好像是我第一次做树状数组的题

树状数组裸题，还是二维的，多一层for而已

代码如下：

#include<cmath>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
using namespace std;
int a[310][310][110];
int c[310][310];
int n,m;
int lowbit(int x){return x&-x;}
void change(int x,int y,int cc,int d)
{
    for(int i=x;i<=n;i+=lowbit(i))
        for(int j=y;j<=m;j+=lowbit(j))
            a[i][j][cc]+=d;
}
/*
3 3
1 2 3
3 2 2
2 1 3
*/
int findsum(int x,int y,int cc)
{
    int sum=0;
    for(int i=x;i>=1;i-=lowbit(i))
        for(int j=y;j>=1;j-=lowbit(j))
            sum+=a[i][j][cc];
    return sum;
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
        {
            scanf("%d",&c[i][j]);
            change(i,j,c[i][j],1);
        }
    int Q;
    scanf("%d",&Q);
    while(Q--)
    {
        int k,x,y,cc,tx,ty;
        scanf("%d",&k);
        if(k==1)
        {
            scanf("%d%d%d",&x,&y,&cc);
            change(x,y,c[x][y],-1);
            c[x][y]=cc;
            change(x,y,c[x][y],1);
        }
        else
        {
            scanf("%d%d%d%d%d",&x,&tx,&y,&ty,&cc);
            int ans;
            ans=findsum(tx,ty,cc)+findsum(x-1,y-1,cc);
            ans=ans-(findsum(x-1,ty,cc)+findsum(tx,y-1,cc));
            printf("%d
",ans);
        }
    }
    return 0;
}

by_lmy

[bzoj1452][jsoi2009]count

来自FallDream的博客，未经允许，请勿转载，谢谢。有一个n*m的矩阵，每个点有一个权值。需要支持两种操作：1)改变一个点的权值2)查询一个矩形内权值为c的个数n,m<=300q<=200000权值<=100权值有点小吧？那就每种权值开一... 查看详情

bzoj1452(代码片段)

1452:[JSOI2009]CountTimeLimit: 10Sec MemoryLimit: 64MBSubmit: 2821 Solved: 1655[Submit][Status][Discuss]Description一个N*M的方格，初始时每个格子有一个整数权值，接下来每次有2个操作:改变一个格子的权查看详情

jsoi2009count[树状数组]

BZOJ我们可以发现N,M,C都十分的小，那么只要开100个二维BIT来维护就可以了。每种颜色对应一个BIT。然后查询的时候再用二维前缀和来搞搞就可以了。开始在BZOJ时候是T了的，后来才发现是BIT开太大了，导致寻址过慢。#include<bits... 查看详情

bzoj1452count

http://www.lydsy.com/JudgeOnline/problem.php?id=1452题目全是图片，不复制了。开100个二维树状数组，分别记录区间内各个颜色的出现位置……简单粗暴。注意查询操作的读入顺序是x1x2y1y21/*bySilverN*/2#include<algorithm>3... 查看详情

bzoj1449[jsoi2009]球队收益

TimeLimit: 5Sec MemoryLimit: 64MBSubmit: 741 Solved: 423DescriptionInputOutput一个整数表示联盟里所有球队收益之和的最小值。SampleInput331021111010133122331SampleOutput43HINTSource&n 查看详情

bzoj1443:[jsoi2009]游戏game

1443:[JSOI2009]游戏GameTimeLimit:10SecMemoryLimit:162MBSubmit:1334Solved:613[Submit][Status][Discuss]DescriptionInput输入数据首先输入两个整数N,M，表示了迷宫的边长。接下来N行，每行M个字符，描述了迷宫。Output若小AA能够赢得游戏，则输出一行"WIN... 查看详情

bzoj2257:[jsoi2009]瓶子和燃料

2257:[Jsoi2009]瓶子和燃料TimeLimit: 10Sec MemoryLimit: 128MBDescriptionjyy就一直想着尽快回地球，可惜他飞船的燃料不够了。有一天他又去向火星人要燃料，这次火星人答应了，要jyy用飞船上的瓶子来换。jyy的飞船上共... 查看详情

bzoj-2257:[jsoi2009]瓶子和燃料(中国剩余定理)

2257:[Jsoi2009]瓶子和燃料TimeLimit: 10Sec MemoryLimit: 128MBSubmit: 1583 Solved: 965[Submit][Status][Discuss]Descriptionjyy就一直想着尽快回地球，可惜他飞船的燃料不够了。有一天他又去向火星人要查看详情

bzoj1560jsoi2009火星藏宝图[dp]

火星藏宝图TimeLimit:10Sec MemoryLimit:64MB[Submit][Status][Discuss]Description　　Input　　Output　　SampleInput　　410　　1120　　101010　　3560　　5330SampleOutput　　-4HINT　　1<=M<=2000,2<=N<=100000 查看详情

bzoj1443[jsoi2009]游戏game

DescriptionInput输入数据首先输入两个整数N,M，表示了迷宫的边长。接下来N行，每行M个字符，描述了迷宫。Output若小AA能够赢得游戏，则输出一行"WIN"，然后输出所有可以赢得游戏的起始位置，按行优先顺序输出每行一个,否则输出... 查看详情

bzoj1558[jsoi2009]等差数列

传送门：http://www.lydsy.com/JudgeOnline/problem.php?id=1558【题解】这题恶心死人了啊。。网络上题解很多都是看代码看代码。。真是太不负责任了。。我这里详细说一下吧。。题解在代码下面。#include<stdio.h>#include<string.h>#include&... 查看详情

bzoj2257:[jsoi2009]瓶子和燃料数论：裴蜀定理

2257:[Jsoi2009]瓶子和燃料TimeLimit:10Sec MemoryLimit:128MBSubmit:1326 Solved:815[Submit][Status][Discuss]Descriptionjyy就一直想着尽快回地球，可惜他飞船的燃料不够了。有一天他又去向火星人要燃料，这次火星人答应了，要jyy用飞船... 查看详情

bzoj1443[jsoi2009]游戏game

AC通道:http://www.lydsy.com/JudgeOnline/problem.php?id=1443分析:对于这种棋子在棋盘上走来走去,只能走相邻的格子的问题,感觉还是挺好玩的...　　然后好玩归好玩,可是有点不会做啊.　　貌似棋盘上相邻格子这种不断移动的问题,都大概能... 查看详情

bzoj1449/bzoj2895[jsoi2009]球队收益/球队预算费用流

题目描述输入输出一个整数表示联盟里所有球队收益之和的最小值。样例输入331021111010133122331样例输出43题解费用流由于存在一个赢一个输，比较难算。我们可以先假设它们都输掉，然后再安排赢的情况。设fi为i还要打的比赛数... 查看详情

bzoj:1443:[jsoi2009]游戏game

原题链接：http://www.lydsy.com/JudgeOnline/problem.php?id=1443反正不看题解我是完全想不出系列……先把棋盘黑白染色，也就是同一对角线上颜色相同，使得一个格子上下左右都不同色。然后我们会发现，某一个人所走的全部格子颜色都... 查看详情

bzoj2257:[jsoi2009]瓶子和燃料

Descriptionjyy就一直想着尽快回地球，可惜他飞船的燃料不够了。有一天他又去向火星人要燃料，这次火星人答应了，要jyy用飞船上的瓶子来换。jyy的飞船上共有N个瓶子(1<=N<=1000)，经过协商，火星人只要其中的K个。jyy将K... 查看详情

bzoj2257:[jsoi2009]瓶子和燃料

bzoj1444[jsoi2009]有趣的游戏ac自动机+概率dp+矩阵乘法

【BZOJ1444】[Jsoi2009]有趣的游戏DescriptionInput注意是0<=POutputSampleInputSampleOutputHINT 30%的数据保证,n≤2.50%的数据保证,n≤5.100%的数据保证,n,l,m≤10.题解：本题的做法真的很多啊，概率DP，期望DP，当然还有矩乘黑科技~就是先跑AC... 查看详情