本文主要是介绍[ACM] hrbustoj 1161 Leyni （树状数组），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
| Leyni | ||||||
| ||||||
| Description | ||||||
| Leyni被人掳走，身在水深火热之中... 现在小奈叶专心战斗，Leyni昏迷，他们无法得知小护盾遭受的有效攻击次数，他们需要你的帮助。 只要能帮到他们，Leyni就会赠送出一份小奈叶写真集。  | ||||||
| Input | ||||||
| 第一行是一个整数T，表示有多少组测试数据。 | ||||||
| Output | ||||||
| 每一组测试数据，先输出一行"Case i:",i表示第i组测试数据，从1开始计数。 | ||||||
| Sample Input | ||||||
| 1 | ||||||
| Sample Output | ||||||
| Case 1: | ||||||
| Author | ||||||
| 黄李龙 |
编号1到n的保护盾，某编号的保护盾被攻击后产生防御，有个冷却时间t，如果在这t秒内该编号的盾又被攻击，则属于有效攻击，t秒后，该编号的盾又有了一次产生防御的能力。问某个区间内一共产生多少次有效攻击。用树状数组来保存区间有效攻击数，为每个盾保存一个状态，该状态为最后一次该盾产生防御是在第几次攻击d[number]，当后来再对该盾产生攻击时，判断的d[number] + t 是否大于 该次攻击是第几次攻击，如果大于，则该次攻击属于有效攻击，更新树状数组，因为冷却时间还没完，否则，属于无效攻击，更新d[number]的值为 该次攻击是第几次攻击 。做题时犯了一个严重的错误，就是没有保存当前状态下一共发生了多少次攻击，直接把循环的变量当做攻击数了，但是题目中说查询是不需要时间的，所以要单独设一个变量来保存总发生攻击数。
代码：
#include <iostream>
#include <stdio.h>
#include <string.h>
using namespace std;
const int maxn=100002;
int c[maxn];//保存数组中某一段区间的和
int d[maxn];//保存每个保护盾最后一次无效攻击发生在第几秒
int n,q,t;
char cm[10];//命令
int number;//被攻击的编号
int lowbit(int x)
{
return x&(-x);
}
void update(int x,int rt)//这里rt为1
{
while(x<=n)
{
c[x]+=rt;
x+=lowbit(x);
}
}
int sum(int x)
{
int s=0;
while(x>0)
{
s+=c[x];
x-=lowbit(x);
}
return s;
}
int main()
{
int k;cin>>k;
for(int ti=1;ti<=k;ti++)
{
cout<<"Case "<<ti<<":"<<endl;
scanf("%d%d%d",&n,&q,&t);
memset(c,0,sizeof(c));
memset(d,0,sizeof(d));
int a,b;
int attacknum=0;
for(int i=1;i<=q;i++)
{
scanf("%s",cm);
if(cm[0]=='A')
{
attacknum++;
scanf("%d",&number);
if(d[number]==0)//第一次被攻击
{
d[number]=attacknum;
}
else
{
if(d[number]+t>attacknum)
update(number,1);
else//一开始犯了错误d[number]=i，这是错的，i既包括了攻击的时间也包括了查询时间，但题意中查询是不花时间的，所以不能用i
d[number]=attacknum;//编号为number的保护盾最后产生无效攻击发生在attacknum秒
}
}
if(cm[0]=='Q')
{
scanf("%d%d",&a,&b);
printf("%d\n",sum(b)-sum(a-1));//输出区间和
}
}
}
return 0;
}
这篇关于[ACM] hrbustoj 1161 Leyni （树状数组）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
