郑外—衡中欢乐赛 之二

感想

大概是，药丸吧...
反正就是...兜兜转转，最后也爆出了10分...rating掉了三百...

题解

T1

不知道说自己智障还是神经（。）
关于括号的问题，不就是我之前那个 区间dp吗？？？
然后我们按照那个区间dp的思路，直接dp。
没了，注意点就是空格不能直接跳过，要化成 $1$ 的

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
char s[60];
bool f[60][60];
int main()
{
    int t,n;
    scanf("%d",&t);getchar();
    while(t--)
    {
        gets(s+1);
        n=strlen(s+1);
        memset(f,0,sizeof(f));
        for(int i=1;i<=n;++i)
        {
            int k;
            if(s[i]<'0'||s[i]>'9')  continue;
            f[i][i]=1;
            k=i+1;while(s[k]==' '&&k<=n)    f[i][k++]=1;
            k=i-1;while(s[k]==' '&&k>=1)    f[k--][i]=1;
            k=i+1;while(k<=n&&s[k]>='0'&&s[k]<='9') f[i][k++]=1;
            k=i-1;while(k>=1&&s[k]>='0'&&s[k]<='9') f[k--][i]=1;
        }
        for(int l=2;l<=n;++l)
        {
            for(int i=1;i+l-1<=n;++i)
            {
                int j=i+l-1;
                for(int k=i+1;k<j;++k)
                    if(s[k]=='+'||s[k]=='-'||s[k]=='/'||s[k]=='*')
                        if(f[i][k-1]&&f[k+1][j])    f[i][j]=1;
                if(f[i+1][j-1]&&s[i]=='('&&s[j]==')')   f[i][j]=1;
                int k,L,R;
                if(f[i][j]==1)
                {
                    k=j+1;while(k<=n&&s[k]==' ')    f[i][k++]=1;
                    R=k-1;
                    k=i-1;while(k>=1&&s[k]==' ')    f[k--][i]=1;
                    L=k+1;
                    for(int i_=L;i_<=i;++i_)    
                        for(int j_=j;j_<=R;++j_)
                            f[i_][j_]=1;
                }
            }
        }
        if(f[1][n]) puts("Yes");
        else    puts("No");
    }
    return 0;
}

T2

这个...拓扑排序。
我不是很会，但是基本上知道的，和bfs基本一样，需要注意多起点终点情况，以及入度要减去。
字符串哈希，也不苟什么哈希表了，直接MAP，建图直接跑拓扑。
好了。
注意：可能有多个入口和出口。

    #include<map>
    #include<queue>
    #include<cstdio>
    #include<cstring>
    #include<algorithm>
    #define ll long long
    using namespace std;
    const int N=50005;
    const int Q=1e9+7;
    const int seed=131;
    struct data{
        int to,next;
    }e[N<<1];
    int head[N],gs,in[N],out[N],m,n,tot;
    int cnt[N];
    char u[101],v[101];
    void add(int fr,int to)
    {
        in[to]++,out[fr]++,e[++gs].to=to,e[gs].next=head[fr],head[fr]=gs;
    }
    void bfs()
    {
        queue<int> q;
        for(int i=1;i<=tot;++i)
            if(in[i]==0)    q.push(i),cnt[i]=1;
        while(!q.empty())
        {
            int u=q.front();q.pop();
            for(int i=head[u];i;i=e[i].next)
            {
                int v=e[i].to;
                cnt[v]=((ll)cnt[v]+cnt[u])%Q;
                in[v]--;
                if(in[v]==0)    q.push(v);
            }
        }
    }
    ll hash(char s[])
    {
        ll h=0;
        int l=strlen(s+1);
        for(int i=1;i<=l;++i)
            h=(h*seed%Q+s[i]-'a')%Q;
        return h;
    }
    map <ll,int> M;
    void solve()
    {
        int x,y,s,t;
        int ans=0;
        for(int i=1;i<=m;++i)
        {
            scanf("%s%s",u+1,v+1);
            ll tmp=hash(u);
            ll tmp2=hash(v);
            if(M[tmp])  x=M[tmp];
            else    x=++tot,M[tmp]=tot;
            if(M[tmp2]) y=M[tmp2];
            else    y=++tot,M[tmp2]=tot;
            add(x,y);
        //  printf("%d %d\n",x,y);
        }
        bfs();
        for(int i=1;i<=tot;++i)
            if(out[i]==0)   ans=(cnt[i]+ans)%Q;
        printf("%d\n",ans); 
    }   
    int main()
    {
    //  freopen("c.txt","r",stdin);
    //  freopen("ch.txt","w",stdout);
        scanf("%d",&m);
        solve();
        return 0;
    }

T3

这道题，首先必须要能看出来是一个组合数（。）
比如我就没看出来...
然后我们推出组合数公式一看，好嘛。
还有限制。
这个限制，dp时候能绕开，但是组合数算是不好算的，所以我们想，用dp把他绕开。
那么我们就很清晰的知道，我们这时候，可以手动绕开这些不好的点。
所以说我我们设置dp的时候，需要这样：

$dp[i]$ 即为第 $i$ 个坏点处的方案数（不经过其他坏点）

这样的话我们排个序，可以很快的算出来答案了。

#include<cstdio>
#include<algorithm>
#define ll long long
using namespace std;
const int N=2000005;
const int Q=1e9+7;
ll fac[N],inv[N];
ll dp[N];
struct data{
    ll x,y;
    bool friend operator <(data a,data b)
    {
        if(a.x!=b.x)    return a.x<b.x;
        return a.y<b.y;
    }
}p[3005];
int m,n,k;
ll quick_pow(ll x,ll k)
{
    ll an=1;
    for(int i=k;i;i>>=1,x=x*x%Q)
        if(i&1) an=an*x%Q;
    return an;
}
void init()
{
    fac[0]=1;inv[0]=1;
    for(int i=1;i<N;++i)
        fac[i]=(ll)fac[i-1]*i%Q;
    inv[N-1]=quick_pow(fac[N-1],Q-2);
    for(int i=N-2;i;--i)
        inv[i]=inv[i+1]*(i+1)%Q;
}
int c(int x,int y)
{
    return fac[x]*inv[y]%Q*inv[x-y]%Q;
}
void solve()
{
    init();
    sort(p+1,p+1+k);
    for(int i=1;i<=k;++i)
    {
        dp[i]=c(p[i].x+p[i].y,p[i].x);
        for(int j=1;j<i;++j)
        {
            if(p[i].x>=p[j].x&&p[i].y>=p[j].y)
            {
                dp[i]=(dp[i]-dp[j]*c(p[i].x-p[j].x+p[i].y-p[j].y,p[i].x-p[j].x)%Q+Q)%Q;
            }
        }
    }
    printf("%lld\n",dp[k]);
}
inline int read()
{
    int x=0;char c=getchar();
    while(c<'0'||c>'9') c=getchar();
    while(c>='0'&&c<='9')   x=x*10+c-'0',c=getchar();
    return x;
}
int main()
{
    n=read(),m=read();
    k=read();
    for(int i=1;i<=k;++i)   p[i].x=read(),p[i].y=read();
    k++,p[k].x=n,p[k].y=m;
    solve();
    return 0;
}