BestCoder Round #77

링크:http://bestcoder.hdu.edu.cn/
1001: 부분 집합 이 다 르 거나 합, n = 1 이 0 이 아 닌 다른 것 은 모두 0 이다.
코드:

#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<string>
#include<vector>
#include<queue>
#include<cmath>
#include<stack>
#include<set>
#include<map>
#define INF 0x3f3f3f3f
#define Mn 105
#define Mm 200
#define mod 1000000007
#define CLR(a,b) memset((a),(b),sizeof((a)))
#define CPY(a,b) memcpy ((a), (b), sizeof((a)))
#pragma comment(linker, "/STACK:102400000,102400000")
#define ul u<<1
#define ur (u<<1)|1
using namespace std;
typedef long long ll;
int a[1005];
int main() {
    int t;
    scanf("%d",&t);
    while(t--) {
        int n;
        scanf("%d",&n);
        for(int i=1;i<=n;i++) {
            scanf("%d",&a[i]);
        }
        if(n==1) cout<<a[1]<<endl;
        else  cout<<0<<endl;
    }
    return 0;
}

1002: 구 성 된 답문 열 개수.
먼저 회 문 열 을 구성 할 수 있 는 지 판단 한 다음 에 홀수 개의 문자 가 1 보다 많 을 때 회 문 열 을 구성 할 수 없 음 이 분명 하 다. 그 다음 에 조합 수 를 구 하려 면 역 원 이나 페 이 마 를 사용 해 야 한다.

#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<string>
#include<vector>
#include<queue>
#include<cmath>
#include<stack>
#include<set>
#include<map>
#define INF 0x3f3f3f3f
#define Mn 10005
#define Mm 200
#define mod 1000000007
#define CLR(a,b) memset((a),(b),sizeof((a)))
#define CPY(a,b) memcpy ((a), (b), sizeof((a)))
#pragma comment(linker, "/STACK:102400000,102400000")
#define ul u<<1
#define ur (u<<1)|1
using namespace std;
typedef long long ll;
int a[1005];
ll fac[1010];
ll ppow(ll k,ll n) {
    ll c=1;
    while(n) {
        if(n%2) c=(c*k)%mod;
        k=(k*k)%mod;
        n>>=1;
    }
    return c;
}
ll C(int a,int b) {
    return (((fac[b]*ppow((fac[a]*fac[b-a])%mod,mod-2)))%mod)%mod;
}
int num[Mn];
int main() {
    int t; fac[0]=1;
    for(int i=1;i<1010;i++) {
        fac[i]=(fac[i-1]*i)%mod;
    }
    scanf("%d",&t);

    while(t--) {
        string s;
        cin>>s;CLR(num,0);
        for(int i=0;i<s.size();i++) {
            num[s[i]-'a']++;
        }
        int flag=0;
        for(int i=0;i<26;i++) {
            if(num[i]%2) flag++;
            num[i]/=2;
        }
        ll ans=1;
        if(flag>1) cout<<0<<endl;
        else {
            int l=s.size()/2;
            for(int i=0;i<26;i++) {
                if(num[i]==0) continue;
                ans=(ans*C(num[i],l))%mod;
                l-=num[i];
            }
            cout<<ans<<endl;
        }
    }
    return 0;
}

1003: 먼저 모든 산봉 우 리 를 그림 에 넣 은 다음 에 모든 연결 블록 을 찾 아 낸 다음 에 마지막 해 의 산봉우리 부터 삭제 하고 상하 가 연결 되 는 지 여 부 를 판단 할 때마다 연결 시 답 은 바로 이 해 입 니 다.

#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<string>
#include<vector>
#include<queue>
#include<cmath>
#include<stack>
#include<set>
#include<map>
#define INF 0x3f3f3f3f
#define Mn 505
#define Mm 2000005
#define mod 1000000007
#define CLR(a,b) memset((a),(b),sizeof((a)))
#define CPY(a,b) memcpy ((a), (b), sizeof((a)))
#pragma comment(linker, "/STACK:102400000,102400000")
#define ul u<<1
#define ur (u<<1)|1
using namespace std;
typedef long long ll;
int g[Mn*Mn];
int x[Mn*Mn],y[Mn*Mn];
int pre[Mn*Mn];
int n,m;
int way[4][2]={0,-1,-1,0,1,0,0,1};
int find(int x) {
    return x==pre[x]?pre[x]:pre[x]=find(pre[x]);
}
void ol(int x,int y) {
    int a=find(x);
    int b=find(y);
    if(a!=b) pre[a]=b;
}
int main() {
    int t;
    scanf("%d",&t);
    while(t--) {
        string s;
        scanf("%d%d",&n,&m);
        for(int i=0;i<n;i++) {
            cin>>s;
            for(int j=0;j<m;j++) {
                g[i*m+j]=s[j]-'0';
                pre[i*m+j]=i*m+j;
            }
        }
        int k,ans=0;
        scanf("%d",&k);
        for(int i=1;i<=k;i++) {
            scanf("%d%d",&x[i],&y[i]);
            g[x[i]*m+y[i]]=1;
        }
        int ss=n*m,tt=ss+1;
        pre[ss]=ss;pre[tt]=tt;
        for(int i=0;i<m;i++) if(!g[i])ol(ss,i);
        for(int i=(n-1)*m;i<m*n;i++) if(!g[i])ol(tt,i);
        for(int i=0;i<n;i++) {
            for(int j=0;j<m;j++) {
                //cout<<g[i*m+j];
                if(!g[i*m+j]) {
                    for(int v=0;v<4;v++) {
                        int xx=i+way[v][0];
                        int yy=j+way[v][1];
                        int pos=xx*m+yy;
                        if(yy<0||yy>=m||xx<0||xx>=n||g[pos]) continue;
                        ol(i*m+j,pos);
                    }
                }
            }
        }
        if(find(ss)==find(tt)) {
            cout<<-1<<endl;
            continue;
        }
        for(int i=k;i>=1;i--) {
            g[x[i]*m+y[i]]=0;
            if(x[i]==0) ol(ss,x[i]*m+y[i]);
            else if(x[i]==n-1) ol(tt,x[i]*m+y[i]);
            for(int v=0;v<4;v++) {
                int xx=x[i]+way[v][0];
                int yy=y[i]+way[v][1];
                int pos=xx*m+yy;
                if(yy<0||yy>=m||xx<0||xx>=n||g[pos]) continue;
                ol(x[i]*m+y[i],pos);
            }
            if(find(ss)==find(tt)) {
                ans=i;
                break;
            }
        }
        cout<<ans<<endl;
    }
    return 0;
}

1004：
dp [i] 를 업데이트 할 때마다 i 가 튀 길 수 있 는 범 위 를 옮 겨 다 닙 니 다.

#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<string>
#include<vector>
#include<queue>
#include<cmath>
#include<stack>
#include<set>
#include<map>
#define INF 0x3f3f3f3f
#define Mn 2010
#define Mm 2000005
#define mod 1000000007
#define CLR(a,b) memset((a),(b),sizeof((a)))
#define CPY(a,b) memcpy ((a), (b), sizeof((a)))
#pragma comment(linker, "/STACK:102400000,102400000")
#define ul u<<1
#define ur (u<<1)|1
using namespace std;
typedef long long ll;
int a[Mn];
double dp[Mn];
int main() {
    int t,n,m,x;
    scanf("%d",&t);
    while(t--) {
        scanf("%d%d",&n,&m);
        CLR(a,0);
        for(int i=1;i<=m;i++) {
            scanf("%d",&x);
            a[x+1]=1;
        }
        CLR(dp,0);
        for(int i=1;i<=n;i++) {
            int flag=0;
            for(int j=i;j>0;j--) {
                if(a[j]) flag++;
                if(flag>1) break;
                if(flag==1) dp[i]=max(dp[i],dp[j-1]+log2(i-j+1));
            }
        }
        printf("%.0f
",floor(1000000.0*dp[n]));
    }
    return 0;
}

1005: 우선 수열 에 있 는 모든 조건 을 만족 시 키 는 3 원 조 를 처리 합 니 다.pre [i] 를 i 번 째 3 원 그룹 이 이전에 나타 난 위치 로 설정 하고 앞에서 나타 나 지 않 으 면 1 로 설정 합 니 다. 비합법적 인 3 원 그룹 에 대해 서 는...
n 으로 설정 하 다.이렇게 하면 하나의 조회 [L, R] 에 대해 우 리 는 이 구간 에 몇 개의 3 원 그룹의 pre 값 이 L 보다 작은 지 계산 해 야 한다.여기까지 만 하면 지속 가능 한 선분 트 리 로 계산 할 수 있 습 니 다.

#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<string>
#include<vector>
#include<queue>
#include<cmath>
#include<stack>
#include<set>
#include<map>
#define INF 0x3f3f3f3f
#define Mn 200005
#define Mm 4000005
#define mod 1000000007
#define CLR(a,b) memset((a),(b),sizeof((a)))
#define CPY(a,b) memcpy ((a), (b), sizeof((a)))
#pragma comment(linker, "/STACK:102400000,102400000")
#define ul u<<1
#define ur (u<<1)|1
using namespace std;
typedef long long ll;
struct node {
    int x,y,z,w;
    node(){}
    node(int x,int y,int z,int w):x(x),y(y),z(z),w(w){}
}p[Mn];
bool cmp(node a,node b) {
    if(a.x!=b.x) return a.x<b.x;
    if(a.y!=b.y) return a.y<b.y;
    if(a.z!=b.z) return a.z<b.z;
    return a.w<b.w;
}
int tot=0;
int root[Mn],ls[Mm],rs[Mm],sum[Mm];
void Insert(int l,int r,int x,int &y,int val) {
    y=++tot;
    sum[y]=sum[x]+1;
    if(l==r) return ;
    ls[y]=ls[x],rs[y]=rs[x];
    int mid=(l+r)>>1;
    if(val<=mid) Insert(l,mid,ls[x],ls[y],val);
    else Insert(mid+1,r,rs[x],rs[y],val);
}
int ask(int l,int r,int x,int y,int k) {
    if(l==r) return sum[y]-sum[x];
    int mid=(l+r)>>1;
    if(mid>=k) return ask(l,mid,ls[x],ls[y],k);
    else return sum[ls[y]]-sum[ls[x]]+ask(mid+1,r,rs[x],rs[y],k);
}
int fl[Mn];
int pre[Mn];
int b[Mn];
int a[Mn];
int main() {
    int t;scanf("%d",&t);
    while(t--) {
        int n;
        scanf("%d",&n);
        for(int i=1;i<=n;i++) scanf("%d",&a[i]);
        for(int i=1;i<=n-2;i++) p[i]=node(a[i],a[i+1],a[i+2],i);
        sort(p+1,p+n-1,cmp);
        p[0].x=p[0].y=p[0].z=p[0].w=-1;
        int cnt=0;
        for(int i=1;i<=n-2;i++) {
            if(p[i].x<=p[i].y&&p[i].y<=p[i].z) {
                if(p[i].x!=p[i-1].x||p[i].y!=p[i-1].y||p[i].z!=p[i-1].z) fl[p[i].w]=++cnt;
                else fl[p[i].w]=cnt;
            } else fl[p[i].w]=0;
        }
        CLR(b,0);
        sum[0]=root[0]=ls[0]=rs[0]=tot=0;
        for(int i=1;i<=n-2;i++) {
            if(!fl[i]) pre[i]=n;
            else pre[i]=b[fl[i]]+1;b[fl[i]]=i;
            Insert(1,n,root[i-1],root[i],pre[i]);
        }
        int m;
        scanf("%d",&m);
        while(m--) {
            int l,r;
            scanf("%d%d",&l,&r);
            if(r-l<2) printf("0
");
            else printf("%d
",ask(1,n,root[l-1],root[r-2],l));
        }
    }
    return 0;
}