HDU-6356 Glad You Came （rmq）
사고: 시간 카드 가 너무 빡빡 합 니 다. 경기 할 때 우선 대기 열 유지 T, 라인 트 리 도 T, 시간 복잡 도 O (qlogn) 이지 만 q 가 너무 커서 데이터 그룹 수가 많 습 니 다.경기 후 공식 문 제 를 보고 분석 한 것 은 rmq, O (nlogn) 이 며, 업데이트 시 역방향 으로 업데이트 하면 된다.
#include
using namespace std;
#define inf 0x3f3f3f3f
#define u unsigned int
#define ll long long
const int maxn=1e5+10;
const u mod=(1<<30);
u x,y,z,w;
u rng61()
{
x=x^(x<<11);
x=x^(x>>4);
x=x^(x<<5);
x=x^(x>>14);
w=x^(y^z);
x=y;
y=z;
z=w;
return z;
}
ll dp[maxn][25],f[maxn],p[110],a[maxn];
int main()
{
#define int ll
int t,sum=1,num=0;
p[0]=1;
cin>>t;
for(int i=1;i>n>>q>>x>>y>>z;
for(int i=1;i<=n;i++)
for(int j=0;j<=22;j++)
dp[i][j]=0;
u nn=n;
for(int i=1;i<=q;i++)
{
ll f1=rng61();
ll f2=rng61();
ll f3=rng61();
int l=(int)min((f1%nn)+1,(f2%nn)+1);
int r=(int)max((f1%nn)+1,(f2%nn)+1);
int v=(int)(f3%mod);
int d=f[r-l+1];// 2
dp[l][d]=max(dp[l][d],v);
dp[r-p[d]+1][d]=max(dp[r-p[d]+1][d],v);
}
for(int j=f[n];j;j--)
for(int i=1;i<=n;i++)
{
dp[i][j-1]=max(dp[i][j-1],dp[i][j]);///rmq
if(i+p[j-1]<=n)
dp[i+p[j-1]][j-1]=max(dp[i+p[j-1]][j-1],dp[i][j]);///rmq
}
ll ans=0;
for(int i=1;i<=n;i++)
ans^=1ll*i*1ll*dp[i][0];
cout< 이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
정수 반전Udemy 에서 공부 한 것을 중얼거린다 Chapter3【Integer Reversal】 (예) 문자열로 숫자를 반전 (toString, split, reverse, join) 인수의 수치 (n)가 0보다 위 또는 ...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
