| 题目名称 | 2000. [ZLXOI 2015][异次元圣战I]虐狗大赛 |
|---|---|
| 输入输出 | thebigmatch.in/out |
| 难度等级 | ★★★ |
| 时间限制 | 250 ms (0.25 s) |
| 内存限制 | 256 MiB |
| 测试数据 | 10 |
| 题目来源 |
 Satoshi
于2015-10-17加入 |
| 开放分组 | 全部用户 |
| 提交状态 | |
| 分类标签 | |
| 分享题解 |
| 通过：55， 提交：106， 通过率：51.89% | ||||
 浮生随想 |
100 | 0.118 s | 1.47 MiB | C++ |
 _Itachi |
100 | 0.143 s | 1.45 MiB | C++ |
 史莱克音洛 |
100 | 0.148 s | 2.79 MiB | C++ |
 AntiLeaf |
100 | 0.157 s | 1.45 MiB | C++ |
 Dissolute丶Tokgo |
100 | 0.226 s | 1.82 MiB | C++ |
 Hzoi_ |
100 | 0.242 s | 1.82 MiB | C++ |
 白&夜 |
100 | 0.250 s | 1.84 MiB | C++ |
 MISS Yin |
100 | 0.251 s | 2.79 MiB | C++ |
 Kirito |
100 | 0.255 s | 1.82 MiB | C++ |
 梦那边的美好ET |
100 | 0.264 s | 4.68 MiB | C++ |
| 本题关联比赛 | |||
| ZLXOI2015Day1 | |||
| 关于 虐狗大赛 的近10条评论(全部评论) | ||||
|---|---|---|---|---|
|
| ||||
|
回复 @叶子の宿敌 :
现在把你自己也烧了吧  Hzoi_chairman
2016-07-14 09:50
10楼
| ||||
|
那时太小不懂事，看见情侣就想烧......
| ||||
|
单身狗之歌配上铃儿响叮当的调贼好听
 | ||||
|
#include<iostream>
#include<cstdio> #include<cmath> #include<cstring> #include<algorithm> using namespace std; const int maxn=1010; int t,n,q; int c[maxn][maxn]={0}; int lowbit(int); int getsum(int ,int); int gengxin(int,int,int); char Getchar(); void Init(); int main() { scanf("%d",&t); for(int i=1;i<=t;i++) { Init(); } return 0; } void Init() { scanf("%d%d",&n,&q); for(int i=1;i<=q;i++) { char ch=Getchar(); if(ch=='C'){ int x1,x2,y1,y2; scanf("%d%d%d%d",&x1,&y1,&x2,&y2); gengxin(x1,y1,1); gengxin(x2+1,y2+1,1); gengxin(x2+1,y2,-1); gengxin(x2,y2+1,-1); } if(ch=='Q'){ int x1,y1; scanf("%d%d",&x1,&y1); int k=getsum(x1,y1); printf("%d\n",k%2); } } memset(c,0,sizeof(c)); } char Getchar() { char ch; while(ch=getchar(),ch!='C'&&ch!='Q'); return ch; } int lowbit(int x) { return x&-x; } int getsum(int x,int y) { int tot=0; for(int i=x;i>0;i-=lowbit(i)) for(int j=y;j>0;j-=lowbit(j)) tot+=c[i][j]; return tot; } int gengxin(int x,int y,int z) { for(int i=x;i<=n;i+=lowbit(i)) for(int j=y;j<=n;j+=lowbit(j)) c[i][j]+=z; } | ||||
|
建了两个树状数组，一个记录第i只单身狗到目前被攻击的次数，一个记录第i只单身狗到目前受到的伤害吨数。
我们其实可以认为，第i只单身狗每被攻击一次就会回血d[i]。 所以，若一只单身狗被攻击了m次，伤害总吨数t，则现在它的h值即为“初始h”+m*d[i]-t | ||||
|
差分果然快如闪电
Dissolute丶Tokgo
2015-10-30 21:03
5楼
| ||||
|
你们这些提前交的是何居心！
 Satoshi
2015-10-29 11:53
4楼
| ||||
|
黑的一匹
 NVIDIA
2015-10-29 10:02
3楼
| ||||
|
回复 @cstdio : 这题原本题目名称、题目解释全是“1”，我给改了一下，就是为了节省页面，让以后的题用这个新页面
Satoshi
2015-07-22 22:24
2楼
| ||||
皮波Forever
SOBER GOOD BOY
liu_runda2000. [ZLXOI 2015][异次元圣战I]虐狗大赛
★★★ 输入文件：thebigmatch.in
输出文件：thebigmatch.out
简单对比时间限制：0.25 s 内存限制：256 MiB
【题目描述】
Single dog
single dog
single all the day
See the AV
hit the plane
they're doing all the day 
Hey
Single dog
single dog
why not be a gay
No more wait
no more afraid
make him be a gay--刘晨晨
很久很久以前，在遥远的南方的阿里木多大陆，一群单身狗无忧无虑的生活着，与世隔绝，怡然自得
可以是有一天，一群自称“情侣教会”的组织突然袭击了阿里木多大陆，科技无比落后的单身狗们迅速被击败。
情侣教会建立了殖民帝国，用独裁和高压手段统治单身狗们。
然而随着北方所谓“民主”、“科学”思想的传入，单身狗们似乎有了觉醒的姿态，一系列抗议、游行引起了社会骚乱。
此时帝国的皇帝为黄小明·阿卜杜拉二世，皇后为安杰拉·卑鄙
他们打算用残酷的手段来警示单身狗们造反的后果，为此，帝国的首相奉皇后之命要举办一场虐狗大赛。
他从巴士迪监狱里拖出来了N条被逮捕的反动的单身狗(4<=n<=100000),让他们站成一排。
许多情侣来参加这场大赛，他们以各种姿势、各种方法在单身狗面前秀恩爱，并且在情侣中央广播电视台现场直播。每对情侣对i号单身狗和j号单身狗为两端组成的子序列的单身狗造成k吨伤害。
每个单身狗都有两个参数：心理状态值H和心理承受能力D
单身狗受到的实际伤害为k-D(H-=(k-D)),若实际伤害小于0，则反而能参加H
在几段攻击之后首相要求实时更新每个单身狗的H，输出在大屏幕上。（更新次数很少）
【输入格式】
第一行一个正整数n
第二行为H1,H2,H3.....Hn
第三行为D1,D2,D3.....Dn
第四行一个正整数q,表示q次操作
5-q+6行，每行第一个数为0或1
若为0接下来三个数i,j,k
若为1表示更新
【输出格式】
每次更新输出所有单身狗的H，每次输出一行
【样例输入】
4
1 2 3 4
1 3 2 1
5
0 1 2 4
0 2 3 3
1
0 1 1 0
1
【样例输出】
-2 1 2 4
-1 1 2 4
【提示】
第一次攻击输出为4，对1号实际伤害为4-1=3，对2号实际伤害为4-3=1
第二次攻击输出为3，对2号实际伤害为0，对3号实际伤害为1
第三次攻击输出为0，对1号实际伤害为-1，使得H1增大1
对于20%的数据,n<=1024,q<=1024
对于另外20%的数据，Di=0;
对于另外10%的数据, 所有Di相同
对于100%的数据，n<=100005,q<=10050,更新次数<=50
【来源】