2017.10.7 NOIP模拟赛

题解 套题

目录

• 2017.10.7 NOIP模拟赛
  • 流光溢彩
    • 思路
    • 代码
  • 世代相传
    • 思路
    • 代码
  • 继往开来
    • 思路
    • 代码

流光溢彩

思路

• 为了快速求出$S_{j,i}$，我们考虑维护一个后缀$sumb_i$，如$S=\overline{abcdefg}$，则$sumb_3=\overline{efg}\bmod{B}$；
• 所以条件二就是$(sumb_j-sumb_{i+1})\div 10^k \equiv 0 \pmod{B}$，所以可推出$sumb_j \equiv sumb_i+1 \pmod{B}$；
• 条件一也很好弄，我们也弄一个前缀$suma_i$即可；
• 那么$ans_i$就是求有多少$j \leq i$满足$suma_{j-1}=0,sumb_j=sumb_{i+1}$；
• 那么我们用一个map维护就好了。

代码

#include <cstdio>
#include <map>
using std::map;
const int MAXN=1e6+5;
int n,a,b;
int suma[MAXN],sumb[MAXN];
char s[MAXN];
map<int,int> mp;
inline int pow(int x,int y,int p){
    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 void deal(){
    for(int i=1;i<=n;++i)
        suma[i]=((long long)suma[i-1]*10%a+(s[i]^'0'))%a;
    for(int i=n;i;--i)
        sumb[i]=((long long)(s[i]^'0')*pow(10,n-i,b)%b+sumb[i+1])%b;
}
int main(){
    scanf("%d%d%d",&n,&a,&b);
    scanf("%s",s+1);
    deal();
    for(int i=1;i<=n;++i){
        printf("%d\n",mp[sumb[i+1]]);
        if(suma[i]==0) ++mp[sumb[i+1]];
    }
    return 0;
}

世代相传

思路

• 如果我们对于每组满足条件的$i,j$连一条双向边，那么我们就是要求该图的最大团，这是NPC问题，不可做；
• 考虑转化为对于不满足条件的$i,j$连一条双向边，那么求的就是该图的最大独立集，这个在二分图上是可做的；
• 观察到，当$a_i \equiv a_j \pmod{2}$时，$a_i,a_j$比然满足要求；
• 那么可以根据$a_i$的奇偶性构建二分图，用总点数减去最大匹配数就是最大独立集的大小了，也就是$ans$；
• 这题卡匈牙利。。。所以用Dinic，复杂度$O(n^2 \sqrt{n})$。

代码

#include <cstdio>
#include <queue>
#include <cstring>
#include <algorithm>
#include <climits>
using std::queue;
using std::min;
using std::__gcd;
const int MAXN=2005;
int n,s,t;
int he[MAXN],iter[MAXN],dis[MAXN];
unsigned a[MAXN];
struct line{int to,nex,cap;}ed[MAXN*MAXN];
inline void addE(int u,int v,int cap){
    static int cnt=1;
    ed[++cnt]=(line){v,he[u],cap};
    he[u]=cnt;
}
inline int revE(int i){return i^1;}
int aug(int u,int rest){
    if(u==t || !rest) return rest;
    int ret=0;
    for(int &i=iter[u],v,cap,flow;i;i=ed[i].nex){
        v=ed[i].to,cap=ed[i].cap;
        if(dis[v]!=dis[u]+1 || !cap) continue;
        flow=aug(v,min(rest,cap));
        ed[i].cap-=flow,ed[revE(i)].cap+=flow;
        rest-=flow,ret+=flow;
        if(!rest) return ret;
    }
    if(!ret) dis[u]=-1;
    return ret;
}
inline bool BFS(){
    static queue<int> que;
    memset(dis,-1,sizeof(dis));
    dis[s]=0;
    que.push(s);
    int u;
    while(que.size()){
        u=que.front();
        que.pop();
        for(int i=he[u],v;i;i=ed[i].nex){
            if(!ed[i].cap) continue;
            v=ed[i].to;
            if(dis[v]==-1){
                dis[v]=dis[u]+1;
                que.push(v);
            }
        }
    }
    return dis[t]!=-1;
}
inline int Dinic(){
    int ret=0;
    while(BFS()){
        memcpy(iter,he,sizeof(iter));
        ret+=aug(s,INT_MAX);
    }
    return ret;
}
inline void build(){
    static int odd[MAXN],even[MAXN];
    s=n+1,t=n+2;
    for(int i=1;i<=n;++i){
        if(a[i]&1) odd[++odd[0]]=i;
        else even[++even[0]]=i;
    }
    for(int i=1;i<=odd[0];++i){
        for(int j=1;j<=even[0];++j){
            if(__gcd(a[odd[i]],a[even[j]])==1 && __gcd(a[odd[i]]+1,a[even[j]]+1)==1)
                addE(odd[i],even[j],INT_MAX),addE(even[j],odd[i],0);
        }
    }
    for(int i=1;i<=odd[0];++i)
        addE(s,odd[i],1),addE(odd[i],s,0);
    for(int i=1;i<=even[0];++i)
        addE(even[i],t,1),addE(t,even[i],0);
}
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;++i)
        scanf("%d",&a[i]);
    build();
    printf("%d",n-Dinic());
    return 0;
}

继往开来

思路

• 因为抽牌方案数只有$C_{26}^3$，所以考虑枚举抽牌方案，只需验证符不符合条件即可；
• 设两个人分别为$A,B$，则对于一张牌，虽然看似有三种状态：在$A$处、在$B$处、被抽走，但实际上可用两个布尔值表示：$A0/1,B0/1$，即在不在$A$和在不在$B$；
• 对于这些布尔值，因为每次的约数条件都是二元的，所以可以使用2-SAT判断（为了便于理解，下面说的选就是那个布尔值为真）；
• 若$i$被抽走，则$A0_i=A1_i,B0_i=B1_i$，所以必须选$A0_i,B0_i$，即使选了$A1_i$或$B1_i$。也就可表示为$A1_i$可推出$A0_i$，$B1_i$可推出$B0_i$，下面的必须选也是这个意思；
• 若未被抽走，则$A0_i=B1_i,A1_i=B0_i$，即选了$A1_i$必须选$B0_i$，选了$B1_i$必须选$A0_i$，反之亦然；
• 上面是最基础的逻辑要求，下面我们只需考虑输入数据中的条件即可（因为有时可能会误认为下面的部分少了一些条件，其实在上面已经要求过了）；
• 我们都假设询问的两张牌为$i,j$，回答的人是$A$，因为回答是$B$的条件相同：
  
  1. 回答是$0$，那么$i,j$一定不在$A$中，所以必须选$A0_{i/j}$；
  2. 回答是$2$，那么$i,j$一定在$A$中，所以必须选$A1_{i/j},B0_{i/j}$；
  3. 回答是$1$，这个就复杂了，我们只能确定$i,j$有且只有一个在$A$中，所以选了$A0_i$就必须选$A1_j$，选了$A1_i$就必须选$A0_j$，对于$j$的亦然。进一步还可以推出选了$A0_i$就必须选$B0_j$，选了$B1_i$就必须选$A1_j$，对于$j$的亦然；
• 有了上面的逻辑条件，应该不难实现了，但是代码有些复杂，最好先理清思路了再顺着思路写。如果不是很理解上面的逻辑条件，建议先仔细思考，推敲一下，上面的逻辑条件是不重不漏的，十分严密，思考清楚就会觉得十分妙。
• 复杂度取决于输入数据，但是最坏情况下也只有$O(C_{26}^3 \times(26 \times 4)^2)$。

代码

#include <cstdio>
#include <stack>
#include <cstring>
#include <algorithm>
using std::stack;
using std::min;
const int MAXN=1005,MAXSZ=30,MAXV=MAXSZ<<2,MAXE=MAXV*MAXV;
int n,Ecnt,cnt,tot,idx;
int he[MAXV];
int dfn[MAXV],low[MAXV],scc[MAXV];
int idA[MAXSZ][2],idB[MAXSZ][2];
int cdt[MAXN][2],pers[MAXN],ans[MAXN];
bool away[MAXSZ];
struct line{int to,nex;}ed[MAXE];
inline void addE(int u,int v){
    ed[++Ecnt]=(line){v,he[u]};
    he[u]=Ecnt;
}
void Tarjan_SCC(int u){
    static int low[MAXV];
    static bool inS[MAXV];
    static stack<int> stk;
    dfn[u]=low[u]=++idx;
    stk.push(u);
    inS[u]=true;
    for(int i=he[u],v;i;i=ed[i].nex){
        v=ed[i].to;
        if(!dfn[v]){
            Tarjan_SCC(v);
            low[u]=min(low[u],low[v]);
        }
        else if(inS[v]) low[u]=min(low[u],dfn[v]);
    }
    if(dfn[u]==low[u]){
        ++tot;
        int now;
        do{
            now=stk.top();
            stk.pop();
            inS[now]=false;
            scc[now]=tot;
        }while(now!=u);
    }
}
inline void mge_node(){
    idx=tot=0;
    memset(dfn,0,sizeof(dfn));
    for(int i=1;i<=cnt;++i){
        if(!dfn[i]) Tarjan_SCC(i);
    }
}
inline void build(){
    Ecnt=0;
    memset(he,0,sizeof(he));
    for(int i=0;i<26;++i){
        //i in A or B is both true and false
        if(away[i]){
            addE(idA[i][1],idA[i][0]);
            addE(idB[i][1],idB[i][0]);
        }
        //i in A and i in B are different
        else{
            addE(idA[i][1],idB[i][0]);
            addE(idA[i][0],idB[i][1]);
            addE(idB[i][0],idA[i][1]);
            addE(idB[i][1],idA[i][0]);
        }
    }
    for(int i=1;i<=n;++i){
        //i is in A or B or C(the set which the pokers we took out are in)
        if(ans[i]==0){
            for(int j=0;j<=1;++j){
                //cannot in A
                if(pers[i]==1) addE(idA[cdt[i][j]][1],idA[cdt[i][j]][0]);
                //cannot in B
                else addE(idB[cdt[i][j]][1],idB[cdt[i][j]][0]);
            }
        }
        //can know where i is,so <=> in C
        else if(ans[i]==2){
            for(int j=0;j<=1;++j){
                if(pers[i]==1){
                    addE(idA[cdt[i][j]][0],idA[cdt[i][j]][1]);
                    addE(idB[cdt[i][j]][1],idB[cdt[i][j]][0]);
                }
                else{
                    addE(idB[cdt[i][j]][0],idB[cdt[i][j]][1]);
                    addE(idA[cdt[i][j]][1],idA[cdt[i][j]][0]);
                }
            }
        }
        //cannot know
        else{
            for(int j=0;j<=1;++j){
                if(pers[i]==1){
                    addE(idA[cdt[i][j]][0],idA[cdt[i][j^1]][1]);
                    addE(idA[cdt[i][j]][1],idA[cdt[i][j^1]][0]);
                    addE(idA[cdt[i][j]][0],idB[cdt[i][j^1]][0]);
                    addE(idB[cdt[i][j]][1],idA[cdt[i][j^1]][1]);
                }
                else{
                    addE(idB[cdt[i][j]][0],idB[cdt[i][j^1]][1]);
                    addE(idB[cdt[i][j]][1],idB[cdt[i][j^1]][0]);
                    addE(idB[cdt[i][j]][0],idA[cdt[i][j^1]][0]);
                    addE(idA[cdt[i][j]][1],idB[cdt[i][j^1]][1]);
                }
            }
        }
    }
}
inline bool jud(){
    for(int i=0;i<26;++i){
        if(scc[idA[i][0]]==scc[idA[i][1]])
            return false;
        else if(scc[idB[i][0]]==scc[idB[i][1]])
            return false;
    }
    return true;
}
inline bool two_SAT(){
    build();
    mge_node();
    return jud();
}
inline int solve(){
    int ret=0;
    //pockers that are taken away
    for(int i=0;i<26;++i){
        away[i]=true;
        for(int j=i+1;j<26;++j){
            away[j]=true;
            for(int k=j+1;k<26;++k){
                away[k]=true;
                ret+=two_SAT();
                away[k]=false;
            }
            away[j]=false;
        }
        away[i]=false;
    }
    return ret;
}
inline void prepare(){
    for(int i=0;i<26;++i){
        for(int j=0;j<=1;++j){
            idA[i][j]=++cnt;
            idB[i][j]=++cnt;
        }
    }
    char qry[5];
    for(int i=1;i<=n;++i){
        scanf("%s",qry);
        //cdt=condition
        for(int j=0;j<=1;++j)
            cdt[i][j]=qry[j]-'A';
        //pers=person
        scanf("%d%d",&pers[i],&ans[i]);
    }
}
int main(){
    scanf("%d",&n);
    prepare();
    printf("%d",solve());
    return 0;
}