2017.10.12 NOIP模拟赛

题解 套题

目录

• 2017.10.12 NOIP模拟赛
  • 奶牛没问么，要穿越马路 1？
    • 思路
    • 代码
  • 奶牛没问么，要穿越马路 2？
    • 思路
    • 代码
  • 奶牛没问么，要穿越马路 3？
    • 思路
    • 代码

奶牛没问么，要穿越马路 1？

思路

• 就是一个剪枝BFS，其实不用考虑那么多；
• 考虑记录状态$his(x,y,k \bmod{3})$是走到$(x,y)$处，这是第$k \bmod{3}$步的最少时间；
• 那么BFS时，只有下一个转移到的状态优于历史记录才可以入队；
• 这样少了很多无用状态，复杂度不会大过$his$数组大小的数量级；
• 但是可以发现，这样其实就类似Dijkstra了，的确是这样，这题就是个最短路，可以拆点成三个点表示不同状态，也可以把刚刚的BFS的队列改成优先队列。

代码

#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>
#include <cstring>
#include <climits>
#include <queue>
#include <vector>
#include <functional>
using std::min;
using std::priority_queue;
using std::vector;
using std::greater;
const int MAXN=105;
int n,t;
int G[MAXN][MAXN];
int dirx[]={0,1,0,-1},diry[]={1,0,-1,0};
struct state{
    int x,y,k;
    long long d;
    state(int x=0,int y=0,int k=0,long long d=0):x(x),y(y),k(k),d(d){}
    friend bool operator> (const state &a,const state &b){
        return a.d>b.d;
    }
};
inline bool inG(state &u){
    return 1<=u.x && u.x<=n && 1<=u.y && u.y<=n;
}
inline long long Dijkstra(){
    static long long his[MAXN][MAXN][3];
    static priority_queue<state,vector<state>,greater<state> > hp;
    memset(his,0x7f,sizeof(his));
    his[1][1][0]=0;
    hp.push(state(1,1,0,0));
    state u,v;
    long long d;
    while(hp.size()){
        u=hp.top();
        hp.pop();
        if(his[u.x][u.y][u.k]<d) continue;
        v.k=(u.k+1)%3;
        for(int i=0;i<4;++i){
            v.x=u.x+dirx[i],v.y=u.y+diry[i];
            v.d=u.d+t;
            if(v.k==0) v.d+=G[v.x][v.y];
            if(inG(v) && his[v.x][v.y][v.k]>v.d){
                his[v.x][v.y][v.k]=v.d;
                hp.push(v);
            }
        }
    }
    long long ret=INT_MAX;
    for(int i=0;i<3;++i)
        ret=min(ret,his[n][n][i]);
    return ret;
}
int main(){
#ifdef DEBUG
    setIO("a");
#endif
    read(n),read(t);
    for(int i=1;i<=n;++i){
        for(int j=1;j<=n;++j)
            read(G[i][j]);
    }
    write(Dijkstra());
    return 0;
}

奶牛没问么，要穿越马路 2？

思路

• 乍一看是个二分图匹配，仔细一想，这个限制根本不可做；
• 那么贪心也不行，我们考虑DP，设$dp_{0/1}(i,j)$是匹配到$x_i,y_j$时$x_i,y_j$中有没有被匹配上的最优解；
• 那么：
  $$dp_0(i,j)=\max\{dp_0(i-1,j),dp_0(i,j-1),dp_0(i-1,j-1),dp_1(i-1,j-1),dp_1(i-1,j-1),dp_1(i-1,j)-1,dp_1(i,j-1)-1\}$$
• 而$dp_1(i,j)=(dp_0(i,j)+1)\cdot G(i,j)$；
• 总复杂度$O(n^2)$（我的转移可能有些麻烦，但是这样似乎会清楚一些，我还是太弱了orz）。

代码

#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>
#include <cmath>
using std::max;
using std::abs;
const int MAXN=1005;
int n;
int x[MAXN],y[MAXN];
bool can[MAXN][MAXN];
inline int DP(){
    static int dp[MAXN][MAXN][2];
    int ret=0;
    for(int i=1;i<=n;++i){
        for(int j=1;j<=n;++j){
            dp[i][j][0]=max(max(dp[i-1][j][0],dp[i][j-1][0]),max(dp[i-1][j][1],dp[i][j-1][1])-1);
            dp[i][j][0]=max(dp[i][j][0],max(dp[i-1][j-1][0],dp[i-1][j-1][1]));
            if(can[i][j]) dp[i][j][1]=dp[i][j][0]+1;
            ret=max(ret,max(dp[i][j][0],dp[i][j][1]));
        }
    }
    return ret;
}
int main(){
#ifdef DEBUG
    setIO("b");
#endif
    read(n);
    for(int i=1;i<=n;++i)
        read(x[i]);
    for(int i=1;i<=n;++i)
        read(y[i]);
    for(int i=1;i<=n;++i){
        for(int j=1;j<=n;++j)
            can[i][j]=(abs(x[i]-y[j])<=4);
    }
    write(DP());
    return 0;
}

奶牛没问么，要穿越马路 3？

思路

• 开始居然想用主席树求区间内种类个数，结果还忘初始化一个数组写挂了。
• 虽然是个环形，但是直接按序列做没有问题，因为序列最后的点绕一圈连到前面的和前面的直接按照序列方向连到后面的是等价的（画个图就明白了，我当时还纠结半天orz）；
• 那么我们就是要统计同种牛之间的部分有多少种牛，这个用树状数组足矣，反正离线，顺着扫一遍吗；
• 具体看代码吧，这个似乎比T2还简单，只要敢写。。。

代码

#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);
}
const int MAXN=50005;
int n,m;
int last[MAXN];
class BIT{
    private:
        long long c[MAXN<<1];
        int lowbit(int x){return x&-x;}
        long long qry(int r){
            long long ret=0;
            for(;r;r-=lowbit(r))
                ret+=c[r];
            return ret;
        }
    public:
        void add(int l,int x){
            for(;l<=m;l+=lowbit(l))
                c[l]+=x;
        }
        long long qry(int l,int r){
            return qry(r)-qry(l-1);
        }
}ta;
int main(){
#ifdef DEBUG
    setIO("c");
#endif
    read(n);
    m=n<<1;
    long long ans=0;
    for(int i=1,a;i<=m;++i){
        read(a);
        if(last[a]){
            ans+=ta.qry(last[a]+1,i);
            ta.add(last[a],-1);
        }
        else{
            last[a]=i;
            ta.add(i,1);
        }
    }
    write(ans);
    return 0;
}