tjut 3450

news/2025/2/13 20:30:14/
/*分析:每次寻找以a[i]结尾的子序列能有多少个,只需要寻找a[i]-d和a[i]+d之之间数结尾的子序列 
的全部个数,然后把a[i]直接放在那些数后面即可 
找寻和更新都是用树状数组  
*/  
#include <iostream>  
#include <cstdio>  
#include <cstdlib>  
#include <cstring>  
#include <string>  
#include <queue>  
#include <algorithm>  
#include <map>  
#include <cmath>  
#include <iomanip>  
#define INF 99999999  
typedef long long LL;  
using namespace std;  const int MAX=100000+10;  
const int mod=9901;  
int n,d,size;  
int c[MAX],a[MAX],hash[MAX];  int lowbit(int x){  return x&(-x);  
}  void Update(int x,int d){  while(x<=size){  c[x]=(c[x]+d)%mod;  x+=lowbit(x);  }  
}  int Query(int x){  int sum=0;  while(x>0){  sum+=c[x];  x-=lowbit(x);  }  return sum%mod;  
}  int search1(int x){//寻找第一个>=x的数   int left=1,right=size,mid;  while(left<=right){  mid=left+right>>1;  if(hash[mid]<x)left=mid+1;  else right=mid-1;  }  return right+1;   
}  int search2(int x){//寻找最后一个<=x的数   int left=1,right=size,mid;  while(left<=right){  mid=left+right>>1;  if(hash[mid]<=x)left=mid+1;  else right=mid-1;  }  return left-1;  
}  int main(){  while(~scanf("%d%d",&n,&d)){  for(int i=1;i<=n;++i)scanf("%d",a+i),hash[i]=a[i];  sort(hash+1,hash+n+1);  size=1;  for(int i=2;i<=n;++i)if(hash[i] != hash[size])hash[++size]=hash[i];  int sum=0;  memset(c,0,sizeof c);  for(int i=1;i<=n;++i){  int x=search1(a[i]-d),y=search2(a[i]+d),k=search1(a[i]);  int ans=Query(y)-Query(x-1);  ans=ans%mod+mod;  sum=(sum+ans)%mod;  Update(k,ans+1);  }  printf("%d\n",sum);  }  return 0;  
}  


http://www.ppmy.cn/news/201291.html

相关文章

POJ 3450题解

题目连接 POJ 3450 Corporate Identity 思路 先用后缀数组处理出height数组&#xff0c;然后我们二分最长公共子串的长度&#xff0c;然后再height中找大于这个长度并且不在一个字符串的个数&#xff0c;如果等于n则返回true否则返回false即可。 前期一直TLE不知道为何&…

hdu 3450

吐吐槽吧&#xff1a;本来思路完全对了&#xff0c;但是那个二分查找搞错了&#xff0c;我还以为一个就可以了&#xff0c;结果查找上界和下界分别要一个查找函数&#xff08;WA时就看了一下别人的代码&#xff0c;发现别人都是用两个查找函数的&#xff0c;模仿别人写的查找函…

poj3450

Corporate Identity http://poj.org/problem?id3450 Description Beside other services, ACM helps companies to clearly state their “corporate identity”, which includes company logo but also other signs, like trademarks. One of such companies is Internet Bu…

HDU 3450(树状数组)

题目链接:HDU 3450 题目大意: 求长度大于等于且相邻差值不超过d的子序列的个数. 分析: 没什么好说的水题,就是没给a的范围真的天坑. 以下是代码: #include <set> #include <map> #include <stack> #include <queue> #include <vector> #inclu…

HDU 3450 Counting Sequences(树状数组+离散化+二分+dp思想 详细解答)

题目链接&#xff1a;HDU 3450 题意&#xff1a;给出一段序列&#xff0c;让你找出一段子序列&#xff08;长度>2&#xff09;满足序列中每相邻的两个数之间的差 <d&#xff0c;求出这样的序列的个数。 思路&#xff1a;本题利用dp思想&#xff0c;dp[i] 表示 以 i 为结…

小米路由器R1C或R1CM小米R1C 原厂Bootloader和epproom

想把刷机后的小米路由器R1C刷回小米原厂,而又没备份的小伙伴可以使用下面的BootLoader和epprom&#xff08;也就是原厂分区里面的Factory分区&#xff09;都是我自己手动备份的。 分享给大家 链接&#xff1a;https://pan.baidu.com/s/1v6iUB5idgxUPqclk2KJLkA 提取码&#x…

android 7.1 小米,你的小米手机,能升Android 7.1吗?

对于诸多资深Android手机用户来说&#xff0c;官方何时放出最新Android系统更新包&#xff0c;是他们所关心的&#xff0c;小米手机用户也是如此。今天MIUI官方汇总了支持Android N的小米机型。你的手机能升Android 7.1吗&#xff1f; 根据MIUI官方的汇总数据(注&#xff1a;7月…

小米全系列机型代码查询与 制作rom分区架构图示

安卓机型的不断更新与芯片型号的不同和各自厂家研发的方向差异导致目前各品牌机型固件架构也不同。这种现象对于普通大众来说没有丝毫影响。一般只有玩家类和第三方rom制作有所关注 来几张图看下当前小米系列机型的代码和分区架构图示 做第三方rom时注意各机型的分区架构和线刷…