2017.10.15 NOIP模拟赛

题解 套题

目录

• 2017.10.15 NOIP模拟赛
  • 表达式
    • 思路
    • 代码
  • 食物链
    • 思路
    • 代码
  • 路径
    • 思路
    • 代码

表达式

思路

• 这题，不说啥了。。。
• 石姐区间DP怒切orz，我只会暴力判断所有情况：
  
  1. 首先，按照题目的意思，出现$,(,),+,-,*,/,0$~$9,\_$（空格）以外的字符都是不合法的；
  2. 然后，全是空格的也不合法，这两个比较好判断；
  3. 以后都用$\_$代替空格，考虑这种情况$1\_\_2$怎么判断，若我们直接压缩空格的话会判对，我们可以考虑将每一串连续数字压缩为一个，那么这样相连的数字就是不合法情况了；
  4. 对于括号，我们可以用一个$cnt$记录，遇到$($则$cnt+=1$，遇到$)$则$cnt-=1$，最后看一下$cnt$是否为$0$即可；
  5. 之后我们还要判断是否有两个相连的运算符，或者$+),(+,(),1(,)1$这样的情况；
  6. 最后，表达式的结尾不能是运算符；

代码

#include <cstdio>
#include <cctype>
#include <string>
using std::string;
inline void setIO(string file){
    string in=file+".in",out=file+".out";
    freopen(in.c_str(),"r",stdin);
    freopen(out.c_str(),"w",stdout);
}
template<typename type>
inline void read(type &x){
    int pm=1; char c;
    do{
        c=getchar();
        if(c=='-') pm=-1;
    }while(!isdigit(c));
    x=c^'0';
    while(c=getchar(),isdigit(c))
        x=x*10+(c^'0');
    x*=pm;
}
template<typename type>
void write(type x,char c=0){
    if(x<0) putchar('-'),x=-x;
    if(x>9) write(x/10);
    putchar(x%10|'0');
    if(c) putchar(c);
}
#include <cstring>
#include <iostream>
using std::getline;
using std::cin;
const int MAXN=155;
int n,len;
char fml[MAXN];
string s;
inline bool jud_oper(char fml[]){
    int cnt=0;
    bool oper=false;
    for(int i=1;i<=len;++i){
        if(!isdigit(fml[i]) && fml[i]!='*' && fml[i]!='/' && fml[i]!='+' && fml[i]!='-' && fml[i]!='(' && fml[i]!=')') return false;
        else if(fml[i]=='('){
            if(isdigit(fml[i-1])) return false;
            ++cnt,oper=false;
        }
        else if(fml[i]==')'){
            if(fml[i-1]=='(') return false;
            --cnt;
        }
        else if(isdigit(fml[i])){
            if(fml[i-1]==')' || isdigit(fml[i-1])) return false;
            oper=false;
        }
        else{
            if(oper) return false;
            else if(fml[i-1]=='(') return false;
            oper=true;
        }
    }
    return cnt==0 && !oper;
}
int main(){
    setIO("expr");
    read(n);
    bool num,blk;
    for(int i=1;i<=n;++i){
        memset(fml,0,sizeof(fml));
        getline(cin,s);
        s.copy(fml+1,s.length(),0);
        len=0;
        num=blk=false;
        for(int j=1,lim=strlen(fml+1);j<=lim;++j){
            if(fml[j]!=' ' && (!num || !isdigit(fml[j])))
                fml[++len]=fml[j];
            if(!isdigit(fml[j])) num=false;
            else num=true;
            if(fml[j]!=' ') blk=true;
        }
        if(!blk) puts("No");
        else if(jud_oper(fml)) puts("Yes");
        else puts("No");
    }
    return 0;
}

食物链

思路

• 对于字符串，很简单std::map即可，也可以哈希，不过要是用std::cin>>string的话记着关闭缓存同步（std::ios::sync_with_stdio(false)），不然后面会T；
• 之后建图，显然拓扑排序后DAG上的DP，比较水。

代码

#include <cstdio>
#include <cctype>
#include <string>
using std::string;
inline void setIO(string file){
    string in=file+".in",out=file+".out";
    freopen(in.c_str(),"r",stdin);
    freopen(out.c_str(),"w",stdout);
}
template<typename type>
inline void read(type &x){
    int pm=1; char c;
    do{
        c=getchar();
        if(c=='-') pm=-1;
    }while(!isdigit(c));
    x=c^'0';
    while(c=getchar(),isdigit(c))
        x=x*10+(c^'0');
    x*=pm;
}
template<typename type>
void write(type x,char c=0){
    if(x<0) putchar('-'),x=-x;
    if(x>9) write(x/10);
    putchar(x%10|'0');
    if(c) putchar(c);
}
#include <iostream>
#include <map>
#include <queue>
#include <cstring>
using std::cin;
using std::map;
using std::queue;
const int MAXN=50005,MAXM=100005,P=1e9+7;
int n;
int he[MAXN],inD[MAXN],outD[MAXN],topo[MAXN];
map<string,int> mp;
struct line{int to,nex;}ed[MAXM];
inline void addE(int u,int v){
    static int cnt=0;
    ed[++cnt]=(line){v,he[u]};
    he[u]=cnt;
}
inline void topo_sort(){
    static int inD[MAXN];
    static queue<int> que;
    memcpy(inD,::inD,sizeof(inD));
    for(int i=1;i<=n;++i){
        if(!inD[i]) que.push(i);
    }
    int u;
    while(que.size()){
        u=que.front();
        que.pop();
        topo[++topo[0]]=u;
        for(int i=he[u],v;i;i=ed[i].nex){
            v=ed[i].to;
            if(--inD[v]==0) que.push(v);
        }
    }
}
inline int DAG_DP(){
    static int dp[MAXN];
    int ret=0;
    for(int i=n,u;i;--i){
        u=topo[i];
        if(!outD[u]){
            dp[u]=1;
            continue;
        }
        for(int i=he[u],v;i;i=ed[i].nex){
            v=ed[i].to;
            dp[u]=(dp[u]+dp[v])%P;
        }
        if(!inD[u]) ret=(ret+dp[u])%P;
    }
    return ret;
}
int main(){
    setIO("chain");
    int m;
    read(m);
    string u,v;
    for(int i=1;i<=m;++i){
        cin>>u>>v;
        if(!mp.count(u)) mp[u]=++n;
        if(!mp.count(v)) mp[v]=++n;
        addE(mp[u],mp[v]);
        ++outD[mp[u]],++inD[mp[v]];
    }
    topo_sort();
    write(DAG_DP());
    return 0;
}

路径

思路

• 首先考虑没有障碍的情况，那么方案数就是$C_{n+m}^n$，因为走上去只能走$n+m$步，我们选$n$步向上走，剩下的向右走；
• 对于障碍，如果考虑容斥的话，枚举的复杂度高达$O(2^k)$，显然不可行；
• 如果这样考虑，把点从左下到右上排序，按顺序计算，每一个障碍$(x_i,y_i)$计算从$(0,0)$到它，不经过其它障碍的方案数$dp(i)$；
• 最后把$(n,m)$抽象为一个障碍，那么$ans=dp_{k+1}$，复杂度为$O(k^2)$；
• 为什么这样不会漏呢？考虑到我们只考虑的是经过两个障碍的不合法方案，其它的没有考虑，但递推计算时一早就排除掉了，所以不会影响。

代码

#include <cstdio>
#include <cctype>
#include <string>
using std::string;
inline void setIO(string file){
    string in=file+".in",out=file+".out";
    freopen(in.c_str(),"r",stdin);
    freopen(out.c_str(),"w",stdout);
}
template<typename type>
inline void read(type &x){
    int pm=1; char c;
    do{
        c=getchar();
        if(c=='-') pm=-1;
    }while(!isdigit(c));
    x=c^'0';
    while(c=getchar(),isdigit(c))
        x=x*10+(c^'0');
    x*=pm;
}
template<typename type>
void write(type x,char c=0){
    if(x<0) putchar('-'),x=-x;
    if(x>9) write(x/10);
    putchar(x%10|'0');
    if(c) putchar(c);
}
#include <algorithm>
using std::sort;
using std::unique;
const int MAXN=100005,MAXK=3005,P=1e9+7;
int n,m,k;
int fac[MAXN<<1],fac_inv[MAXN<<1];
struct point{
    int x,y;
    friend bool operator< (const point &a,const point &b){
        return a.x<b.x || (a.x==b.x && a.y<b.y);
    }
    friend bool operator== (const point &a,const point &b){
        return a.x==b.x && a.y==b.y;
    }
}d[MAXK];
inline int pow(int x,int y){
    int ret=1;
    for(;y;y>>=1,x=(long long)x*x%P){
        if(y&1) ret=(long long)ret*x%P;
    }
    return ret;
}
inline int inv(int x){return pow(x,P-2);}
inline void pre_tab(){
    fac[0]=1;
    for(int i=1,lim=n+m;i<=lim;++i)
        fac[i]=(long long)fac[i-1]*i%P;
    fac_inv[n+m]=inv(fac[n+m]);
    for(int i=n+m-1;i>=0;--i)
        fac_inv[i]=(long long)fac_inv[i+1]*(i+1)%P;
}
inline int C(int n,int m){
    return (long long)fac[n]*fac_inv[n-m]%P*fac_inv[m]%P;
}
inline int cal(){
    static int dp[MAXK];
    for(int i=1;i<=k;++i){
        dp[i]=C(d[i].x+d[i].y,d[i].x);
        for(int j=1;j<i;++j){
            if(d[j].x<=d[i].x && d[j].y<=d[i].y)
                dp[i]=(dp[i]-(long long)dp[j]*C(d[i].x-d[j].x+d[i].y-d[j].y,d[i].x-d[j].x)%P+P)%P;
        }
    }
    return dp[k];
}
int main(){
    setIO("path");
    read(n),read(m),read(k);
    pre_tab();
    for(int i=1;i<=k;++i)
        read(d[i].x),read(d[i].y);
    ++k;
    d[k].x=n,d[k].y=m;
    sort(d+1,d+k+1);
    k=unique(d+1,d+k+1)-d-1;
    write(cal());
    return 0;
}