[NOI 2015 Day 1]문제 풀이 보고서
난 그냥 SunshinAK 라 고 말 하고 싶 었 어.신 난다.
T3 데이터 가 너무 엉망 이 야.시계 가 컴 파일 환경 에 걸 려 서...
T1:프로그램 자동 분석
(http://www.lydsy.com/JudgeOnline/problem.php?id=4195)T1 은 매우 물 입 니 다.바로 이산+를 수집 하 는 것 입 니 다.
T2:패키지 관리자
(http://www.lydsy.com/JudgeOnline/problem.php?id=4196)T2 는 누 드 체인 으로 장 착 된 점 을 1 로 설정 하고 없 는 것 은 0 으로 조회 하 는 것 은 이 노드 까지 의 구간 과 이 노드 를 뿌리 로 하 는 서브 트 리 의 구간 과.그리고 없어 졌어 요.
T3:초밥 만찬
(http://www.lydsy.com/JudgeOnline/problem.php?id=4197)T1,T2 가 이렇게 물 을 마 시 면 T3 가 신 이 날 거 야.우 리 는 주제 의 뜻 에 따라 조화 로 운 집합 은 두 집합 중의 요소 가 서로 질 을 나타 내 는 것 을 알 수 있다.즉,두 집합 의 모든 요소 에 함 유 된 질 인 수 는 교차 하지 않 았 다 는 것 이다.우 리 는 모든 수 에 대해 질 인 수 를 분해 할 수 있 지만,질 인 자 는 80 여 개 를 더 할 수 있 으 며,분명히 안 된다.그러면 우 리 는 이러한 질량 인 수 를 두 가지 로 나 눌 수 있다.하 나 는 sqrt(n)보다 크 고 다른 하 나 는 작은 것(8 개 만)이다.첫 번 째 종 류 를 포함 하 는 수 에 대해 우 리 는 한 종류 로 나 누고,다른 것 은 다른 종류 로 나 누 면,이후 에 우 리 는 상 압 할 수 있다.우 리 는 2 진법 의 모든 사람 이 하나의 질량 인자 의 유 무 를 나타 낸다.f[i][j]는 첫 번 째 집합 중의 질 인자 상황 이 i 이 고 다른 집합 중의 질 인자 상황 이 j 라 는 방안 수 를 나타 낸다.g[1][j][k]는 i 번 째 숫자 에 당선 되 었 을 때 첫 번 째 집합 선 또는 선택 하지 않 는 방안 수 를 나타 낸다.그러면(k&number[i].use)=0 일 때(즉,두 번 째 집합 과 같은 질량 인수 가 없 음)이 값 을 더 합 니 다.g[1][j][k]는 i 번 째 숫자 에 당선 되 었 을 때 두 번 째 집합 선 또는 선택 하지 않 는 방안 수 를 나타 낸다.동상 으로 옮기다.그리고 매번 g 로 f 를 업데이트 합 니 다.그러나 또 하나의 상황 은 빼 야 한다.바로 i 일 때 g[1]과 g[2]가 모두 i 를 선택 한 것 이다.이런 상황 은 비합법적 이 고 우 리 는 이런 상황 을 빼 야 한다.
T1code：
#include
");
else printf("NO
");
}
}T2code：
#includeif(k==0) return ;
dfs_2(k,y);
li[x]=min(li[x],li[k]);
ri[x]=max(ri[x],ri[k]);
for(i=point[x];i;i=next[i])
if(deep[aa[i].en]>deep[x]&&k!=aa[i].en){
dfs_2(aa[i].en,aa[i].en);
li[x]=min(li[x],li[aa[i].en]);
ri[x]=max(ri[x],ri[aa[i].en]);
}
}
#define mid (l+r)/2
#define L k<<1,l,mid
#define R k<<1|1,mid+1,r
void paint(int k,int l,int r,int z)
{
if(z==0) tr[k]=0;
if(z==1) tr[k]=r-l+1;
de[k]=z;
}
void pushdown(int k,int l,int r)
{
paint(k<<1,l,mid,de[k]);
paint(k<<1|1,mid+1,r,de[k]);
de[k]=-1;
}
void insert(int k,int l,int r,int x,int y,int z)
{
if(x<=l&&y>=r){
paint(k,l,r,z);
return ;
}
if(de[k]>=0) pushdown(k,l,r);
if(x<=mid) insert(L,x,y,z);
if(y>mid) insert(R,x,y,z);
tr[k]=tr[k<<1]+tr[k<<1|1];
}
int query(int k,int l,int r,int x,int y)
{
int sum=0;
if(x<=l&&y>=r) return tr[k];
if(de[k]>=0) pushdown(k,l,r);
if(x<=mid) sum+=query(L,x,y);
if(y>mid) sum+=query(R,x,y);
return sum;
}
int ask(int x,int y)
{
int sum=0;
while(belong[x]!=belong[y]){
sum+=query(1,1,n,pos[belong[x]],pos[x]);
insert(1,1,n,pos[belong[x]],pos[x],1);
x=fa[belong[x]];
}
sum+=query(1,1,n,pos[y],pos[x]);
insert(1,1,n,pos[y],pos[x],1);
return sum;
}
int main()
{
int i,x;
scanf("%d",&n);
memset(de,128,sizeof(de));
for(i=2;i<=n;++i){
scanf("%d",&x);
add(x+1,i);
}
dfs_1(1,0); dfs_2(1,1);
scanf("%d",&q);
while(q--){
scanf("%*c%s%d",&ch,&x); x+=1;
if(ch[0]=='i') printf("%d
",deep[x]+1-ask(x,1));
if(ch[0]=='u'){
printf("%d
",query(1,1,n,li[x],ri[x]));
insert(1,1,n,li[x],ri[x],0);
}
}
} T3code：
#includex;
}
f[0][0]=1;
sort(num+2,num+n+1,cmp);
for(i=2;i<=n;++i){
if(i==2||num[i].big==1||num[i].big!=num[i-1].big){
memcpy(g[1],f,sizeof(f));
memcpy(g[2],f,sizeof(f));
}
for(j=255;j>=0;--j)
for(k=255;k>=0;--k){
if(!(k&num[i].use)) g[1][j|num[i].use][k]=(g[1][j|num[i].use][k]+g[1][j][k])%p;
if(!(j&num[i].use)) g[2][j][k|num[i].use]=(g[2][j][k|num[i].use]+g[2][j][k])%p;
}
if(i==n||num[i].big==1||num[i].big!=num[i+1].big)
for(j=0;j<=255;++j)
for(k=0;k<=255;++k)
f[j][k]=((g[1][j][k]+g[2][j][k])%p-f[j][k]+p)%p;
}
for(i=0;i<=255;++i)
for(j=0;j<=255;++j)
if(!(i&j))
ans=(ans+f[i][j])%p;
printf("%d
",ans);
} 이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
항 저 우 전기 1878 오 라 회 로 (오 라 회 로 의 판단)오 라 회 로 는 펜 이 지면 을 떠 나 지 못 하 게 그림 의 각 변 을 한 번 만 그 릴 수 있 고 출발점 으로 돌아 갈 수 있 는 회 로 를 말한다.이제 오 라 회 로 가 있 는 지 그림 을 정 해 주 시 겠 ...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
