2017.10.25 NOIP模拟赛

题解 套题

目录

• 2017.10.25 NOIP模拟赛
  • mine
    • 思路
    • 代码
  • water
    • 思路
    • 代码
  • gcd
    • 思路
    • 代码

mine

思路

• 这种求方案数的显然递推求解；
• 设$dp(i,0$~$4)$表示前$i$个字符，第$i$个状态为$0$~$4$的合法方案数；
• 这$5$个状态分别表示：左右和自己都不是雷，只有左边是雷，左右都是雷但自己不是，自己是雷（不考虑左右），只有右边是雷；
• 我们首先扫一边，判断序列是否合法，这样之后就可以少考虑很多情况；
• 之后考虑怎么转移，注意到递推到第$i$位时，我们与其根据上一个的状态确定当前的不如根据当前的转移到下一个，也就是刷表法；
• 我们不考虑下一个是什么，只考虑当前$i$的状态可以合法转移到$i+1$的什么状态；
• 比如：$i$的状态是$3$，那么可以转移到的$i+1$状态可以是$1,2,3$；
• 具体过程分清楚情况写就不会乱了，注意不要将自己设的状态和题中的弄混！

代码

#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>
const int MAXN=1e6+5,P=1e9+7;
int n;
char s[MAXN];
inline int idx(char c){
    if(isdigit(c)) return c^'0';
    return 3;
}
inline int DP(){
    //0,1,2,3=*,4->1
    static int dp[MAXN][5];
    if(s[1]=='?') dp[1][0]=dp[1][3]=dp[1][4]=1;
    else if(s[1]!='1') dp[1][idx(s[1])]=1;
    else dp[1][4]=1;
    for(int i=1;i<n;++i){
        if(s[i]=='?'){
            //3
            if(s[i-1]!='0'){
                for(int j=1;j<4;++j)
                    dp[i+1][j]=dp[i][3];
            }
            if(s[i-1]!='*'){
                //0
                dp[i+1][0]=(dp[i+1][0]+dp[i][0])%P;
                dp[i+1][4]=(dp[i+1][4]+dp[i][0])%P;
                //4
                dp[i+1][3]=(dp[i+1][3]+dp[i][4])%P;
            }
            if(s[i-1]=='*' || s[i-1]=='?'){
                //1
                dp[i+1][0]=(dp[i+1][0]+dp[i][1])%P;
                dp[i+1][4]=(dp[i+1][4]+dp[i][1])%P;
                //2
                dp[i+1][3]=(dp[i+1][3]+dp[i][2])%P;
            }
        }
        else{
            switch(idx(s[i])){
                case 0: dp[i+1][0]=(dp[i+1][0]+dp[i][0])%P;
                        dp[i+1][4]=(dp[i+1][4]+dp[i][0])%P;
                        break;
                case 1: dp[i+1][0]=(dp[i+1][0]+dp[i][1])%P;
                        dp[i+1][4]=(dp[i+1][4]+dp[i][1])%P;
                        dp[i+1][3]=(dp[i+1][3]+dp[i][4])%P;
                        break;
                case 2: dp[i+1][3]=(dp[i+1][3]+dp[i][2])%P;
                        break;
                case 3: dp[i+1][1]=(dp[i+1][1]+dp[i][3])%P;
                        dp[i+1][2]=(dp[i+1][2]+dp[i][3])%P;
                        dp[i+1][3]=(dp[i+1][3]+dp[i][3])%P;
                        break;
            }
        }
    }
    if(s[n]!='?') return dp[n][idx(s[n])];
    else{
        int ret=0;
        if(s[n-1]!='0') ret=(ret+dp[n][3])%P;
        if(s[n-1]!='*') ret=(ret+dp[n][0])%P;
        if(s[n-1]=='*' || s[n-1]=='?') ret=(ret+dp[n][1])%P;
        return ret;
    }
}
inline bool jud(){
    for(int i=1;i<=n;++i){
        if(s[i]=='0' && (s[i-1]=='*' || s[i+1]=='*'))
            return false;
        if(s[i]=='1' && (s[i-1]!='*' && s[i-1]!='?' && s[i+1]!='*' && s[i+1]!='?'))
            return false;
        if(s[i]=='2' && ((s[i-1]!='*' && s[i-1]!='?') || (s[i+1]!='*' && s[i+1]!='?')))
            return false;
        if(s[i]=='*' && (s[i-1]=='0' || s[i+1]=='0'))
            return false;
    }
    return true;
}
int main(){
#ifdef DEBUG
    setIO("a");
#endif
    scanf("%s",s+1);
    n=strlen(s+1);
    if(!jud()) putchar('0');
    else write(DP());
    return 0;
}

water

思路

• 这个题很妙，是个图论题；
• 考虑我们灌水之后的图有什么特点，那就是每个格子带水的高度是到最外面一圈的路径上的最小值；
• 而最外面一圈除非高度为负，不然不可能有水；
• 那么这就和最短路有些像，我们设每个格子的距离为带水的高度；
• 设格子原来高$G(i,j)$，则最外面一圈的距离就确定了，是$\max(G(i,j),0)$；
• 我们用SPFA求最短路（Dijkstra不符合要求），把最外面一圈的格子当作已经求出$dis$的，加入队列，像正常最短路一样，每次更新相邻格子的$dis$；
• 怎么更新呢，就是$\min\{\max(G(i,j),dis(i',j'))\}$，因为$dis(i,j) \geq G(i,j)$，而我们要最小化带水的高度（前面说了，带水高度再高水就流出去了）；
• 于是$ans(i,j)=dis(i,j)-G(i,j)$，但是这题居然卡输出。。。

代码

#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 <queue>
#include <algorithm>
#include <cstring>
using std::queue;
using std::max;
const int MAXN=305;
int n,m;
int G[MAXN][MAXN];
int dirx[]={1,0,-1,0},diry[]={0,1,0,-1};
long long dis[MAXN][MAXN];
bool inQ[MAXN][MAXN];
struct node{
    int x,y;
    node(int x=0,int y=0):x(x),y(y){}
};
queue<node> que;
inline void init(){
    for(int i=1;i<=n;++i){
        dis[i][1]=max(0,G[i][1]);
        que.push(node(i,1));
        inQ[i][1]=true;
        dis[i][m]=max(0,G[i][m]);
        que.push(node(i,m));
        inQ[i][m]=true;
    }
    for(int i=1;i<=m;++i){
        dis[1][i]=max(0,G[1][i]);
        que.push(node(1,i));
        inQ[1][i]=true;
        dis[n][i]=max(0,G[n][i]);
        que.push(node(n,i));
        inQ[n][i]=true;
    }
}
inline bool inG(node &u){
    return 1<u.x && u.x<n && 1<u.y && u.y<m;
}
inline void SPFA(){
    node u,v;
    while(que.size()){
        u=que.front();
        que.pop();
        inQ[u.x][u.y]=false;
        for(int i=0,d;i<4;++i){
            v.x=u.x+dirx[i],v.y=u.y+diry[i];
            if(!inG(v)) continue;
            d=max((long long)G[v.x][v.y],dis[u.x][u.y]);
            if(dis[v.x][v.y]>d){
                dis[v.x][v.y]=d;
                if(!inQ[v.x][v.y]){
                    que.push(v);
                    inQ[v.x][v.y]=true;
                }
            }
        }
    }
}
int main(){
#ifdef DEBUG
    setIO("b");
#endif
    read(n),read(m);
    for(int i=1;i<=n;++i){
        for(int j=1;j<=m;++j)
            read(G[i][j]);
    }
    memset(dis,0x7f,sizeof(dis));
    init();
    SPFA();
    for(int i=1;i<=n;++i){
        for(int j=1;j<=m;++j){
            write(dis[i][j]-G[i][j]);
            if(j!=m) putchar(' ');
        }
        if(i!=n) putchar('\n');
    }
    return 0;
}

gcd

思路

• 显然是个数学题，由数据范围可知，每次加入或删去一个数，不可能直接计算出对答案的影响，所以考虑容斥；
• 怎么容斥呢？和一个数$x$互质的数的个数等于：
  $$n-\sum_{i=1}^k (-1)^{k-1}\sum_{j=1}^n\left[\left(\prod_{l=1}^i p_l \right)\mid a_j\right]\\其中，x=\prod_{i=1}^k p_i^{r_i}且p_i为质数$$
• 为什么忽略了指数$r$呢，因为我们只考虑有没有这个质因子，后来存的时候也是这样存的，所以就不需要考虑了，如果考虑，复杂度就没有保证了；
• 而发现$x$不是很大，只有$5 \times 10^5$，我们考虑存一下每个数的倍数有多少在集合中；
• 这样后面那个$\sum$就可以$O(1)$得出了；
• 从集合中删除也一样操作就好了；
• 至于这个容斥的复杂度，由于$2 \times 3 \times 5 \times 7 \times 11 \times 13 \times 17=510510$，所以每次操作的枚举量不会超过$2^7$;
• 而且，提前筛出质数，并对$1$~$5 \times 10^5$内的数都求一下质因数存到vector里，会很方便，而且这也是$O(x_{max})$的；
• 其实只要意识到质因数种类不多，这题应该就很好切了。

代码

#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 <vector>
using std::vector;
const int MAXN=200005,MAXX=500005;
int n;
long long ans;
int x[MAXN],fac[MAXX],prm[MAXX];
bool slc[MAXN];
vector<int> div[MAXX];
inline void Euler_prm(){
    static bool notP[MAXX];
    notP[1]=true;
    for(int i=2;i<MAXX;++i){
        if(!notP[i]) prm[++prm[0]]=i;
        for(int j=1;j<=prm[0] && i*prm[j]<MAXX;++j){
            notP[i*prm[j]]=true;
            if(i%prm[j]==0) break;
        }
    }
}
inline void pre_tab(){
    Euler_prm();
    for(int i=1;i<=prm[0];++i){
        for(int j=prm[i];j<MAXX;j+=prm[i])
            div[j].push_back(prm[i]);
    }
}
void cal(int x,int cur,int num,int pm,bool add){
    if(cur==div[x].size()){
        if(!add) --fac[num];
        ans+=pm*fac[num];
        if(add) ++fac[num];
        return;
    }
    cal(x,cur+1,num,pm,add);
    cal(x,cur+1,num*div[x][cur],-pm,add);
}
int main(){
#ifdef DEBUG
    setIO("c");
#endif
    pre_tab();
    int m;
    read(n),read(m);
    for(int i=1;i<=n;++i)
        read(x[i]);
    for(int i=1,id;i<=m;++i){
        read(id);
        if(!slc[id]){
            slc[id]=true;
            cal(x[id],0,1,1,true);
        }
        else{
            slc[id]=false;
            cal(x[id],0,1,-1,false);
        }
        write(ans,'\n');
    }
    return 0;
}