2017 ccpc 하 얼 빈 현장 경기

8877 단어 해제주제 총 결마차이분-트 리 배열뇌 동
2017 ccpc 하 얼 빈 현장 경기
6 문제 밖 에 안 지 났 는데 라 이브 게임 에 넣 으 면 겨우 금 을 칠 수 있 겠 지.
A - Palindrome（hdu6230）
제목 설명https://vjudge.net/contest/258053#problem/A
문 제 를 풀 고 말 라 차 를 보다.두 개의 답문 센터 i, j (i > j) 에 대해 답문 꼬치 장 질문 fi 를 정의 합 니 다. 조건 을 만족 시 키 면 반드시 j > i - fi 와 j + f [j] > i 를 만족 시 켜 야 합 니 다.그래서 i 에 따라 작은 것 부터 큰 것 까지 그 데이터 구 조 는 j 를 유지 하고 모든 i + fi 에 대해 큰 수량 을 구 합 니 다.만약 j + f [j] < = i 가 삭제 되 었 으 면 좋 겠 습 니 다.
코드
#include
#define ll long long
#define N 1000010
using namespace std;
int tt,n,tot,num[N],f[N],c[N];char s[N];ll ans;
struct info{
  int p,v;
  bool operatorp.v;}
};
priority_queueq;
struct bit{
  void modify(int x,int v)
  {
    for(;x<=tot;x+=x&-x)c[x]+=v;
  }
  int qry(int x)
  {
    int res=0;
    for(;x;x-=x&-x)res+=c[x];
    return res;
  }
}T;

int main()
{
  int pos,p;
  scanf("%d",&tt);
  while(tt--)
  {
    scanf(" %s",s+1);n=strlen(s+1);tot=0;ans=0;
    for(int i=1;i<=n;i++)f[i]=0;
    for(int i=1,p=0;i<=n;i++)
    {
	  if(i<=p+f[p]-1)f[i]=min(f[p+p-i],p+f[p]-i);
	  else f[i]=1;
	  while(s[i-f[i]]==s[i+f[i]])f[i]++;
	  if(i+f[i]>p+f[p])p=i;
	  num[++tot]=i-f[i]+1;num[++tot]=i;
	}
	sort(num+1,num+tot+1);
	tot=unique(num+1,num+tot+1)-num-1;
	for(int i=1;i<=n;i++)
	{
	  while(q.size())
	  {
	    info x=q.top();
	    if(x.v>i)break;q.pop();
	    p=lower_bound(num+1,num+tot+1,x.p)-num;
	    T.modify(tot-p+1,-1);
	  }
	  pos=lower_bound(num+1,num+tot+1,i-f[i]+1)-num;
	  ans+=T.qry(tot-pos+1);
	  p=lower_bound(num+1,num+tot+1,i)-num;
	  T.modify(tot-p+1,1);q.push((info){i,i+f[i]});
	}
	printf("%I64d
",ans);
	while(q.size())q.pop();
	for(int i=1;i<=tot;i++)c[i]=0;
  }
  return 0;
}

B - K-th Number（hdu6231）
제목 설명http://acm.hdu.edu.cn/showproblem.php?pid=6231
문제 풀이 2 분 의 답 은 k 가 ans 와 같은 구간 의 수량 보다 훨씬 적다.ans 보다 큰 표 1 을 0 보다 작다.접두사 와 트 리 배열 을 가지 고 유지 하면 됩 니 다.
코드
#include
#define ll long long
#define N 200010
using namespace std;
int tt,n,k,maxn,s[N],t[N],c[N],sum[N];ll m;

class bit
{
  public:
  void modify(int x,int val)
  {
    for(;x<=n*2;x+=x&-x)c[x]+=val;
  }
  int qry(int x)
  {
  	int res=0;if(x<0)return 0;
  	for(;x;x-=x&-x)res+=c[x];
    return res;
  }
}T;

ll cal(int mid)
{
  ll res=0;
  for(int i=1;i<=n;i++)
  {
    if(s[i]>mid)t[i]=1;
    else t[i]=0;
  }
  for(int i=1;i<=n*2;i++)c[i]=0;
  for(int i=1;i<=n;i++)
  {
    if(i>=k)T.modify(n-sum[i-k]+1,1);
	sum[i]=sum[i-1]+t[i];
    res+=T.qry(n-sum[i]+k);
  }
  return res;
}

int main()
{
  scanf("%d",&tt);
  while(tt--)
  {
    scanf("%d%d%lld",&n,&k,&m);maxn=0;
    m=(ll)(n-k+2)*(n-k+1)/2-m+1;
    for(int i=1;i<=n;i++)
      scanf("%d",&s[i]),maxn=max(maxn,s[i]);
    int l=0,r=maxn;
    while(r-l>1)
    {
  	  int mid=l+r>>1;
      if(cal(mid)>=m)r=mid;
      else l=mid+1;
    }
    if(cal(l)>=m)printf("%d
",l);
    else printf("%d
",r);
  }
  return 0;
}

D - X-Men（hdu6233）
제목 설명http://acm.hdu.edu.cn/showproblem.php?pid=6233
이 문 제 를 푸 는 것 이 좀 재미 있어 서 전혀 생각 하지 못 했다.몇 사람 이 나무 위 를 마음대로 걸 으 면 매번 국면 에서 가장 먼 두 개의 점 에 대해 한 번 의 조작 거 리 는 반드시 1 로 줄 어 들 것 이다.모든 사람 은 반드시 누군가의 방향 으로 갈 것 이기 때문에 가장 먼 사람 에 게 거 리 를 줄 이지 않 는 다 면 이것 은 사람 에 게 가장 먼 것 이 아니 라 모순 된다 는 것 을 의미한다.그래서 정 답 은 나무의 가장 긴 사슬 길 이 를 2 로 나 누 는 것 이다.
코드
#include
#define N 1005
using namespace std;
int T,n,m,flag[N],f[N],q[N],k,la[N],ff[N*2];
struct node{int a,b;}e[N*2];
void add(int a,int b)
{
  e[++k]=(node){a,b};ff[k]=la[a];la[a]=k;
  e[++k]=(node){b,a};ff[k]=la[b];la[b]=k;
}

int bfs(int S,int tp)
{
  for(int i=1;i<=n;i++)f[i]=0;
  int l=1,r=2,pos=0;q[1]=S;f[S]=1;
  while(lf[pos])pos=x;
    for(int a=la[x];a;a=ff[a])
      if(!f[e[a].b])
        q[r]=e[a].b,f[q[r]]=f[x]+1,r++;
  }
  if(!tp)return pos;
  return f[pos]-1>>1;
}

int main()
{
  int x,y;
  scanf("%d",&T);
  while(T--)
  {
    scanf("%d%d",&n,&m);k=0;
    for(int i=1;i<=n;i++)la[i]=flag[i]=0;
    for(int i=1;i<=m;i++)
	  scanf("%d",&x),flag[x]=1;
    for(int i=1;i

F - Permutation（hdu6235）
제목 설명http://acm.hdu.edu.cn/showproblem.php?pid=6235 문제 풀이 출석 문제, 1, mid + 1, 2, mid + 2... 마음대로 구성 하면 돼 요.코드 동료 가 썼어 요. 코드 를 붙 이지 않 았 어 요.
J - Interview（hdu 6238）
제목 설명http://acm.hdu.edu.cn/showproblem.php?pid=6239
문제 풀이 D = 1: ans = (n + 2) / 4 D = 2: ans = 3 * (n + 2) / 8 유도 과정 에 구 덩이 를 남긴다.
코드
#include
#define mod 1000000007
#define ll long long
using namespace std;
int T,n,D;
ll Pow(ll a,int b)
{
  ll res=1;
  while(b)
  {
    if(b&1)res=res*a%mod;
    a=a*a%mod;b>>=1;
  }
  return res;
}

int main()
{
  scanf("%d",&T);
  while(T--)
  {
    scanf("%d%d",&n,&D);
    if(D==1)printf("%d
",(ll)(n+2)*Pow(4,mod-2)%mod);
    else printf("%d
",(3ll*n+6)%mod*Pow(8,mod-2)%mod);
  }
  return 0;
}

K - Server（hdu 6420）
제목 설명http://acm.hdu.edu.cn/showproblem.php?pid=6240
문제 풀이 01 점수 계획.2 분 답 mid, s [i] = ai - bi * mid, 최소 덮어 쓰 기 를 구하 십시오.이 문 제 는 겹 쳐 서 덮 을 수 있 는 구덩이 가 있다.그래서 먼저 마이너스 것 을 모두 올 리 고 si 를 0 으로 바 꾼 다음 에 왼쪽 에서 오른쪽 dp 로 바 꾸 고 f [i] 는 i 엔 딩 의 최소 커버 를 나타 낸다.옮 기 면 단조 로 운 스 택 을 유지 하고 매번 스 택 에서 2 분 이면 됩 니 다.
코드
#include
#define inf 99999999999999999.0
#define N 100010
using namespace std;
int T,n,m,sum,top,l[N],r[N],A[N],B[N],q[N];
double s[N],f[N];
struct info{
  int l,r,a,b;
  bool operator1)
  {
  	int mid=l+r>>1;
    if(q[mid]>=x)r=mid;
    else l=mid+1;
  }
  if(q[l]>=x)return f[q[l]];
  if(q[r]>=x)return f[q[r]];
  return inf;
}

bool check(double mid)
{
  double res=0;
  for(int i=1;i<=m;i++)f[i]=inf;
  for(int i=1;i<=n;i++)
  {
    s[i]=(double)t[i].a-mid*t[i].b;
    if(s[i]<0)res+=s[i],s[i]=0;
  }
  top=1;q[top]=0;
  for(int i=1;i<=n;i++)
  {
  	f[t[i].r]=min(f[t[i].r],find(t[i].l-1)+s[i]);
    if(t[i+1].r==t[i].r)continue;
    while(top&&f[q[top]]>=f[t[i].r])top--;
    q[++top]=t[i].r;
  }
  return f[m]+res<=0;
}

int main()
{
  int l,r,a,b;
  scanf("%d",&T);
  while(T--)
  {
    scanf("%d%d",&n,&m);sum=0;
    for(int i=1;i<=n;i++)
    {
	  scanf("%d%d%d%d",&l,&r,&a,&b);
	  t[i]=(info){l,r,a,b};sum+=a;
    }
    sort(t+1,t+n+1);
	double L=0,R=sum;
	for(int i=1;i<=100;i++)
	{
	  double mid=(L+R)*0.5;
	  if(check(mid))R=mid;
	  else L=mid;
	}
	if(check(L))printf("%.3lf
",L);
	else printf("%.3lf
",R);
  } 
  return 0;
}

L - Color a Tree（hdu 6241）
제목 설명http://acm.hdu.edu.cn/showproblem.php?pid=6241
문제 풀이 에 첫 번 째 제한 만 있다 면 아래 에서 위로 L [x] 를 유지 하 는 것 은 x 를 서브 트 리 로 적어도 몇 가지 점 을 염색 해 야 한 다 는 것 을 나타 낸다.두 번 째 제한 이 있 습 니 다. 그럼 두 번 째 답 으로 나 누 겠 습 니 다.두 번 째 제한 에 대해 서브 트 리 외 에 적어도 x 개의 점 을 염색 하 는 것 은 서브 트 리 내 에서 기껏해야 ans - x 개의 점 을 염색 하 는 것 과 같다.그래서 R [x] 를 하나 더 지 키 는 것 은 x 를 뿌리 로 하 는 서브 트 리 가 최대 몇 개의 점 을 염색 하 는 지 나타 낸다.L [i] 와 R [i] 의 관 계 를 체크 했 으 면 좋 겠 어 요.하면, 만약, 만약...
코드
#include
#define N 100010
using namespace std;
int T,n,L[N],R[N],flag,size[N],k,la[N],ff[N*2];
struct node{int a,b;}e[N*2];
vectort1[N],t2[N];
void add(int a,int b)
{
  e[++k]=(node){a,b};ff[k]=la[a];la[a]=k;
  e[++k]=(node){b,a};ff[k]=la[b];la[b]=k;
}

void dfs(int x,int pre,int ans)
{
  L[x]=0;R[x]=1;
  for(int a=la[x];a;a=ff[a])if(e[a].b!=pre)
	dfs(e[a].b,x,ans),L[x]+=L[e[a].b],R[x]+=R[e[a].b];
  for(int i=0;iR[i])return false;
    if(L[i]>mid)return false;
    if(L[i]>size[i])return false;
  }
  if(R[1]1)
    {
	  int mid=l+r>>1;
	  if(check(mid))r=mid;
	  else l=mid+1;
	}
	if(check(l))printf("%d
",l);
	else printf("%d
",r);
  }
  return 0;
}

M - Geometry Problem（hdu 6242）
제목 설명http://acm.hdu.edu.cn/showproblem.php?pid=6242
문제 풀이 팀 원 이 너무 강해 서 초 에 랜 덤 알고리즘 을 냅 니 다.나 같은 지적 장애 선 수 는 어차피 생각 이 안 나.제목 이 최소한 의 반 을 만족 시 키 는 점 은 대원 위 에 있다.그래서 각 점 이 더 큰 원 에 있 을 확률 은 1 / 2 이 고 매번 무 작위 로 3 개의 점 이 있 으 며 모두 큰 원 에 있 을 확률 은 1 / 8 이다.실패 할 확률 은 7 / 8, 7 / 8 의 수 십 차방 이 적다.그 러 니까 열 몇 번 을 뛰 면 풀 릴 거 야.n < = 4 때 아무 거나 두 점 만 골 랐 으 면 좋 겠 어 요. 특 판 해 주세요.여러 발 을 연 기 했 는데 롱 더 블 이 더 블 로 바 뀌 면 지 나 갔 어 요. 왜 그런 지 모 르 겠 어 요.
코드 동료 가 썼어 요. 코드 를 붙 이지 않 았 어 요.
H 팀 원 이 쓴 거 예요. 문 제 를 안 봤 어 요.CEGI 구덩이 남기 기
Leetcode 섬 문제 모음 - 그림 의 옮 겨 다 니 기
MySQL 필수 사항저장 프로세스

좋은 웹페이지 즐겨찾기

개발자 우수 사이트 수집

개발자가 알아야 할 필수 사이트 100선 추천 우리는 당신을 위해 100개의 자주 사용하는 개발자 학습 사이트를 정리했습니다
best100-homepage