NOIP模拟9.17（TYVJ NOIP2017模拟赛D2）

T1.天天寄快递（贪心）AC。
T2.天天和不可描述（栈模拟+递归）暴力了40.
先预处理出括号匹配关系，然后递归输出，带个标记rev表示l…r是否翻转。
T3.罪犯分组（状压dp）特判了20分。
T3这么简单的状压dp我居然想不出来！！！

T1 天天寄快递

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define inf 0x3f3f3f3f
#define N 200010
inline int read(){
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
    return x*f;
}
int n,m,s,k;
ll ans=0;
vector<int>a[N];
int main(){
//  freopen("a.in","r",stdin);
    n=read();m=read();s=read();k=read();
    if(s<n&&k){puts("-23333333");return 0;}
    while(m--){
        int x=read(),y=read();if(y<=2) continue;
        a[x].push_back(y-2);
    }
    for(int i=1;i<=n;++i){
        if(a[i].empty()&&k){puts("-23333333");return 0;}
        sort(a[i].begin(),a[i].end());int tmp=0;
        while(s&&tmp<k&&!a[i].empty()){
            tmp+=a[i][a[i].size()-1];a[i].pop_back();s--;
        }
        if(tmp<k){puts("-23333333");return 0;}
        ans+=tmp;
        for(int j=0;j<a[i].size();++j) a[0].push_back(a[i][j]);
    }
    sort(a[0].begin(),a[0].end());int p=a[0].size()-1;
    while(s&&p>=0){
        ans+=a[0][p];p--;s--;
    }
    printf("%lld\n",ans);
    return 0;
}

T2天天和不可描述

#include <bits/stdc++.h>
using namespace std;
#define N 500100
int n,to[N];
char s[N];
void print(int l,int r,bool rev){
    if(!rev)
        for(int i=l;i<=r;++i)
            if(s[i]=='(') print(i+1,to[i]-1,rev^1),i=to[i];
            else putchar(s[i]);
    else
        for(int i=r;i>=l;--i)
            if(s[i]==')') print(to[i]+1,i-1,rev^1),i=to[i];
            else putchar(s[i]);
}
int main(){
//  freopen("unknown.in","r",stdin);
    scanf("%s",s+1);n=strlen(s+1);
    stack<int>q;
    for(int i=1;i<=n;++i)
        if(s[i]=='(') q.push(i);
        else if(s[i]==')'){int x=q.top();q.pop();to[x]=i;to[i]=x;}
    print(1,n,0);
    return 0;
}

T3 罪犯分组

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define inf 0x3f3f3f3f
#define N 18
inline int read(){
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
    return x*f;
}
int n,m,kk,bin[N],f[1<<N];//f[s]表示s状态的人都分好组最少需要几个组 
bool a[N][N],ok[1<<N];
int main(){
//  freopen("*.in","r",stdin);
    n=read();m=read();kk=read();
    for(int i=0;i<=n;++i) bin[i]=1<<i;
    while(m--){
        int x=read(),y=read();a[x][y]=a[y][x]=1;
    }
    for(int s=1;s<=bin[n]-1;++s){//预处理状态s是否可以分在一组 
        int cnt=0;
        for(int i=1;i<=n;++i)
            for(int j=i+1;j<=n;++j)
                if(a[i][j]&&(s&bin[i-1])&&(s&bin[j-1])) cnt++;
        if(cnt>kk) ok[s]=0;else ok[s]=1;
    }
    for(int s=1;s<=bin[n]-1;++s){
        if(ok[s]) f[s]=1;else f[s]=inf;
        for(int i=s;i>=1;i=(i-1)&s){//枚举状态i表示的人一组。 
            if(ok[i]) f[s]=min(f[s],f[s-i]+1);
        }
    }
    printf("%d\n",f[bin[n]-1]);
    return 0;
}