NOIP 시 뮬 레이 션 문제 qu ming zi [욕심] [시 뮬 레이 션] [재 귀]

T1: 제목: 주어진 작업 과 작업 의 수 는 특정한 데이터 구조 에 대해 이 작업 을 하고 추출 작업 을 위해 추출 한 수량 이 이 데이터 구조 에서 추출 한 수량 과 일치 하 는 지 판단 합 니 다.분석: 마찬가지 로 STL 은 자동 으로 공 을 판정 하지 않 고 공 을 판정 해 야 합 니 다.

#include
#include
#include
#include
#include
using namespace std;
stack<int>p1;
queue<int>p2;
int p3[1000+5],cnt,pd[5],n,opt,v;
int main()
{

    freopen("qu.in","r",stdin);
    freopen("qu.out","w",stdout);
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%d %d",&opt,&v);
        if(opt==1){
            if(!pd[1])p1.push(v);
            if(!pd[2])p2.push(v);
            if(!pd[3])p3[++cnt]=v;
        }
        else{
            if(!pd[1]&&!p1.empty()){
                int tmp=p1.top();p1.pop();
                if(tmp!=v)pd[1]=1;
            }
            else pd[1]=1;
            if(!pd[2]&&!p2.empty()){
                int tmp=p2.front();p2.pop();
                if(tmp!=v)pd[2]=1;
            }
            else pd[2]=1;
            if(!pd[3]&&cnt>=0){
                sort(p3+1,p3+cnt+1);
                int tmp=p3[cnt--];
                if(tmp!=v)pd[3]=1;
            }
            else pd[3]=1;
        }
    }
    for(int i=1;i<=3;i++)if(pd[i])printf("No
");
    else printf("YES
");
    return 0;
}

T2: 제목: 주어진 작업 이 진행 되 는 시간 과 시간 에 영향 을 줍 니 다. 여기 서 영향 시간 에 대한 정 의 는 완성 시간 이 영향 시간 을 초과 하면 이 시간 을 초과 한 모든 작업 이 값 을 초과 하 는 가장 큰 결과 입 니 다.0 부터 최소 결 과 를 구하 다.분석: 정렬 부등식 을 직접 사용 할 수도 있 고 최종 완성 시간 을 확정 할 수도 있다.

#include
#include
#include
using namespace std;
int n,f,maxn;
struct buss
{
    int d,t;
}a[100000+5];
bool cmp(buss x,buss y)
{
    if(x.dreturn true;
    return false;
}
int main()
{
    freopen("ming.in","r",stdin);
    freopen("ming.out","w",stdout);
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        scanf("%d %d",&a[i].t,&a[i].d);
    sort(a+1,a+n+1,cmp);
    for(int i=1;i<=n;i++){
    f+=a[i].t;
    maxn=max(maxn,f-a[i].d);
    }
    printf("%d",maxn);
    return 0;
}

T3: 제목: 주어진 트 리 의 생 성 방식 (구체 적 으로 는 A 트 리 의 C 노드 와 B 트 리 의 D 노드 가 한 줄 로 연결 되 어 있 습 니 다. 물론 A 트 리 와 B 트 리 자 체 는 변 하지 않 습 니 다. 현재 트 리 를 만 들 기 위해 하나의 COPY 를 만 들 었 을 뿐 입 니 다). 이 트 리 의 모든 노드 에서 번호 가 큰 노드 의 거리 와 합 을 구하 십시오.분석: 이것 은 절차 만 볼 수 있 습 니 다. 공식 이 비교적 번 거 롭 습 니 다. 아마도 A 나무 와 C 나무의 답 에 두 나무 포인트 의 적 곱 하기 연 결 된 가장자리 의 거 리 를 더 하고 각 나무 의 모든 노드 에서 연 결 된 노드 의 거리 에 다른 나무의 점 수 를 곱 합 니 다. 마지막 으로 이 양 을 돌려 서 구 해 야 합 니 다. 최대 60 번 까지 재 귀 하 는 것 을 고려 하면 MAP 로 상수 가 크 더 라 도 전혀 문제 가 없습니다.여기 서 몇 가 지 를 주의해 야 합 니 다. 하 나 는 dis 와 len 은 하나의 물건 이 아 닙 니 다. - g [a [cur] 에 있 을 때 여기 의 d [cur] 를 줄 일 필요 가 있 는 지, (예 를 들 어 dis 에서 줄 일 필요 가 없 는 지), 그리고 dis 에서 인용 한 len 은 기본적으로 g 를 곱 했 지만 len 에 서 는 꼭 그렇지 않 습 니 다. 이런 것들 은 모두 명확 한 논리 에 의존 하고 변 수 를 사용 할 때 그들의 뜻 을 항상 기억 해 야 합 니 다.마지막 으로 많은 stl 프로그램 을 사용 하여 조절 하기 어렵 고 자신의 강력 한 정적 오류 능력 을 키 워 야 한다 (그리고 나 같은 소금 에 절 인 생선 에 대해 서 는 감히 조 치 를 써 야 한다).

#include
#include
#include
#define ll long long 
#define p(x,y) make_pair((x),(y))
using namespace std;
const ll modd=1e9+7;
mapmap<int,ll> >dis;
mapmap,ll> >len;
int a[65],b[65],n;
long long g[65],c[65],d[65],ans[65],l[65];
void getlen(int cur,ll x,ll r)
{
    if(!cur)return;
    if(x==r)return;
    if(x>r)swap(x,r);
    if(len[cur][p(x,r)])return;
    if(x+1>g[a[cur]]){
        getlen(b[cur],x-g[a[cur]],r-g[a[cur]]);
        len[cur][p(x,r)]=len[cur][p(r,x)]=len[b[cur]][p(x-g[a[cur]],r-g[a[cur]])]%modd;
    }
    else if(relse {
        getlen(a[cur],x,c[cur]);
        getlen(b[cur],r-g[a[cur]],d[cur]);
        len[cur][p(x,r)]=len[cur][p(r,x)]=len[a[cur]][p(x,c[cur])]+
                         len[b[cur]][p(r-g[a[cur]],d[cur])]+l[cur];
        len[cur][p(x,r)]%=modd;
        len[cur][p(r,x)]%=modd;
    }
}
void getdis(int cur,ll y)
{
    if(!cur)return;
    if(dis[cur][y])return;
    int atmp=a[cur],btmp=b[cur];
    long long ctmp=c[cur],dtmp=d[cur],ytmp=y;
    if(y+1>g[atmp]){
        y-=g[atmp];
        swap(atmp,btmp);
        swap(ctmp,dtmp);
    }
    getdis(atmp,y);
    getdis(btmp,dtmp);
    getlen(atmp,y,ctmp);
    dis[cur][ytmp]=dis[atmp][y]+dis[btmp][dtmp]+len[atmp][p(y,ctmp)]*g[btmp]%modd+l[cur]*g[btmp]%modd;
    dis[cur][ytmp]%=modd;
}
void work(int u)
{
    scanf("%d %d %I64d %I64d %I64d",&a[u],&b[u],&c[u],&d[u],&l[u]);
    g[u]=g[a[u]]+g[b[u]];
    g[u]%=modd;
    ans[u]=ans[a[u]]+ans[b[u]]+g[a[u]]*g[b[u]]%modd*l[u]%modd;
    getdis(a[u],c[u]);
    getdis(b[u],d[u]);
    ans[u]+=dis[a[u]][c[u]]*g[b[u]]%modd+dis[b[u]][d[u]]*g[a[u]]%modd;
    ans[u]%=modd;
    printf("%I64d
",ans[u]);
}
int main()
{
    freopen("zi.in","r",stdin);
    freopen("zi.out","w",stdout);
    scanf("%d",&n);g[0]=1;
    for(int i=1;i<=n;i++)work(i);
    return 0;
}