2017.10.5 NOIP模拟赛

题解 套题

目录

• 2017.10.5 NOIP模拟赛
  • 猜数游戏
    • 思路
    • 代码
  • 暴力快递
    • 思路
    • 代码
  • 超越光速
    • 思路
    • 代码

猜数游戏

思路

• 显然要统计每个字母出现的次数；
• 又发现，有些字母只在某个数字对应的单词出现，如$0,2,4,6,8$；
• 确定这些之后，剩下的数字除$9$外也都有唯一使用的字母了，于是最后确定$9$即可；
• 这种题一般在纸上写一下，找一下特性就切了。

代码

#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 MAXL=2005;
int n;
int cnt[26],tot[10];
char s[MAXL];
inline int idx(char c){return c-'A';}
inline void deal(){
    for(int i=1;i<=n;++i)
        ++cnt[idx(s[i])];
}
inline void solve(){
    //0
    tot[0]=cnt[idx('Z')];
    cnt[idx('Z')]=0;
    cnt[idx('E')]-=tot[0];
    cnt[idx('O')]-=tot[0];
    cnt[idx('R')]-=tot[0];
    //2
    tot[2]=cnt[idx('W')];
    cnt[idx('W')]=0;
    cnt[idx('O')]-=tot[2];
    cnt[idx('T')]-=tot[2];
    //4
    tot[4]=cnt[idx('U')];
    cnt[idx('U')]=0;
    cnt[idx('F')]-=tot[4];
    cnt[idx('O')]-=tot[4];
    cnt[idx('R')]-=tot[4];
    //6
    tot[6]=cnt[idx('X')];
    cnt[idx('X')]=0;
    cnt[idx('I')]-=tot[6];
    cnt[idx('S')]-=tot[6];
    //8
    tot[8]=cnt[idx('G')];
    cnt[idx('G')]=0;
    cnt[idx('E')]-=tot[8];
    cnt[idx('H')]-=tot[8];
    cnt[idx('I')]-=tot[8];
    cnt[idx('T')]-=tot[8];
    //3
    tot[3]=cnt[idx('T')];
    cnt[idx('T')]=0;
    cnt[idx('E')]-=tot[3]<<1;
    cnt[idx('H')]-=tot[3];
    cnt[idx('R')]-=tot[3];
    //5
    tot[5]=cnt[idx('F')];
    cnt[idx('F')]=0;
    cnt[idx('E')]-=tot[5];
    cnt[idx('I')]-=tot[5];
    cnt[idx('V')]-=tot[5];
    //1
    tot[1]=cnt[idx('O')];
    cnt[idx('O')]=0;
    cnt[idx('E')]-=tot[1];
    cnt[idx('N')]-=tot[1];
    //7
    tot[7]=cnt[idx('S')];
    cnt[idx('S')]=0;
    cnt[idx('E')]-=tot[7]<<1;
    cnt[idx('N')]-=tot[7];
    cnt[idx('V')]-=tot[7];
    //9
    tot[9]=cnt[idx('E')];
    cnt[idx('E')]=0;
    cnt[idx('I')]-=tot[9];
    cnt[idx('N')]-=tot[9]<<1;
}
int main(){
    setIO("number");
    scanf("%s",s+1);
    n=strlen(s+1);
    deal();
    solve();
    for(int i=0;i<=9;++i){
        for(int j=1;j<=tot[i];++j)
            putchar(i|'0');
    }
    return 0;
}

暴力快递

思路

• 这个题乍一看想要DP或者网络流，但是发现不可做；
• 这种情况下一般要考虑抽象建图跑最短路了；
• 考虑到一个人扔包裹最多一次，不然肯定不是最优的；
• 那么每个人将包裹扔出去后就不与剩下的操作无关了；
• 于是我们先用BFS求出图中每个点最近的快递员（不含$n$号，因为他不能动）到它的距离；
• 接着包裹从$1$号快递员的位置开始跑最短路，每个快递员可以抱着包裹移动$1$的距离，或者向某个方向扔$x$个距离；
• 扔到某个点后，由据该点最近的快递员跑过去捡起来继续跑，直到到达$n$号快递员的位置；
• 具体转移也很好写，但是这题数据很铁，正常的Dijkstra或SPFA会被卡掉一些点，需要用SPFA在正权图上的优化来卡常，这里我本来写的Dijkstra被卡了，懒省事就改成堆优化的SPFA了。

代码

#include <cstdio>
#include <cstring>
#include <queue>
#include <cmath>
#include <vector>
#include <functional>
using std::queue;
using std::abs;
using std::priority_queue;
using std::vector;
using std::greater;
const int MAXN=100005,MAXHW=505;
int n,h,w,a,b,c;
int dirx[]={1,0,-1,0},diry[]={0,1,0,-1};
long long nearP[MAXHW][MAXHW];
struct node{
    int x,y;
    long long dis;
    node(int x=0,int y=0,long long dis=0):x(x),y(y),dis(dis){}
    friend bool operator> (const node &a,const node &b){
        return a.dis>b.dis;
    }
}p[MAXN];
inline bool inG(node &a){
    return 0<=a.x && a.x<=h && 0<=a.y && a.y<=w;
}
inline void BFS(){
    static queue<node> que;
    memset(nearP,0x7f,sizeof(nearP));
    nearP[p[n].x][p[n].y]=0;
    for(int i=1;i<n;++i){
        nearP[p[i].x][p[i].y]=0;
        que.push(node(p[i].x,p[i].y));
    }
    node u,v;
    int d;
    while(que.size()){
        u=que.front();
        que.pop();
        d=nearP[u.x][u.y]+1;
        for(int i=0;i<4;++i){
            v.x=u.x+dirx[i],v.y=u.y+diry[i];
            if(inG(v) && nearP[v.x][v.y]>d){
                nearP[v.x][v.y]=d;
                que.push(v);
            }
        }
    }
    for(int i=0;i<=h;++i){
        for(int j=0;j<=w;++j)
            nearP[i][j]*=c;
    }
}
inline long long hp_SPFA(){
    static long long dis[MAXHW][MAXHW];
    static bool inQ[MAXHW][MAXHW];
    static priority_queue<node,vector<node>,greater<node> > hq;
    memset(dis,0x7f,sizeof(dis));
    memset(inQ,false,sizeof(inQ));
    dis[p[1].x][p[1].y]=0;
    hq.push(p[1]);
    inQ[p[1].x][p[1].y]=true;
    node u,v;
    long long d;
    while(hq.size()){
        u=hq.top();
        hq.pop();
        inQ[u.x][u.y]=false;
        d=dis[u.x][u.y]+c;
        for(int i=0;i<4;++i){
            v.x=u.x+dirx[i],v.y=u.y+diry[i];
            if(inG(v) && dis[v.x][v.y]>d){
                v.dis=dis[v.x][v.y]=d;
                if(!inQ[v.x][v.y]){
                    hq.push(v);
                    inQ[v.x][v.y]=true;
                }
            }
        }
        v.y=u.y;
        for(v.x=0;v.x<=h;++v.x){
            d=dis[u.x][u.y]+(long long)a*abs(u.x-v.x)+b+nearP[v.x][v.y];
            if(dis[v.x][v.y]>d){
                v.dis=dis[v.x][v.y]=d;
                if(!inQ[v.x][v.y]){
                    hq.push(v);
                    inQ[v.x][v.y]=true;
                }
            }
        }
        v.x=u.x;
        for(v.y=0;v.y<=w;++v.y){
            d=dis[u.x][u.y]+(long long)a*abs(u.y-v.y)+b+nearP[v.x][v.y];
            if(dis[v.x][v.y]>d){
                v.dis=dis[v.x][v.y]=d;
                if(!inQ[v.x][v.y]){
                    hq.push(v);
                    inQ[v.x][v.y]=true;
                }
            }
        }
    }
    return dis[p[n].x][p[n].y];
}
int main(){
    freopen("express.in","r",stdin);
    freopen("express.out","w",stdout);
    scanf("%d%d",&h,&w);
    scanf("%d%d%d",&a,&b,&c);
    scanf("%d",&n);
    for(int i=1;i<=n;++i)
        scanf("%d%d",&p[i].x,&p[i].y);
    BFS();
    printf("%lld",hp_SPFA());
    return 0;
}

超越光速

思路

• 这题看数据量就知道和$n$没关系，于是DP之类的做法就不可行了，那么就贪心好了；
• 设快车站点为$stp_i$；
• 首先，每个中车站点$u$影响到的只有$u$~下一个快车站$stp_i$这一段，因为$time(stp_i)$肯定是这一段中最小的；
• 那么考虑枚举，从$stp_1$开始，每次从坐完快车到$stp_i+1$后坐慢车不超时的最远站的下一站开始，一直到下一个快车站之前，在这些站中枚举建中车站，直到坐中车也超时；
• 我们抽象一点考虑，总共可以再建多于$k-m$个中车站，但是维护一个小根堆，里面最多有$k$个元素，这些元素是在不同位置建站的贡献，我们不断更新堆顶，使其更大，这样就能贪心的求出最佳建站方案的贡献了；
• 为什么可以直接弹出堆顶更新？因为算每个位置建站时并没有更新后面点的信息，只是计算，不会影响后面的结果。

代码

#include <cstdio>
#include <algorithm>
#include <queue>
#include <vector>
#include <functional>
using std::min;
using std::priority_queue;
using std::vector;
using std::greater;
const int MAXN=3005;
int n,m,k,rest,a,b,c;
int stp[MAXN];
long long T;
inline int solve(){
    static priority_queue<int,vector<int>,greater<int> > hp;
    long long t,cnt,nowt;
    int ret=0;
    for(int i=1;i<m;++i){
        t=(long long)b*(stp[i]-1);
        if(t>T) break;
        ret+=(i!=1);
        cnt=min((long long)stp[i+1]-stp[i]-1,(T-t)/a);
        ret+=cnt;
        for(int now=cnt+stp[i]+1,nex=stp[i+1];now<nex;now+=cnt){
            nowt=t+(long long)c*(now-stp[i]);
            if(nowt>T) break;
            cnt=1+min((long long)nex-now-1,(T-nowt)/a);
            if(rest){
                --rest;
                hp.push(cnt);
            }
            else if(hp.top()<cnt){
                hp.pop();
                hp.push(cnt);
            }
            else break;
        }
    }
    if((long long)b*(stp[m]-1)<=T) ++ret;
    while(hp.size()){
        ret+=hp.top();
        hp.pop();
    }
    return ret;
}
int main(){
    freopen("ftl.in","r",stdin);
    freopen("ftl.out","w",stdout);
    scanf("%d%d%d",&n,&m,&k);
    scanf("%d%d%d",&a,&b,&c);
    scanf("%lld",&T);
    for(int i=1;i<=m;++i)
        scanf("%d",&stp[i]);
    rest=k-m;
    printf("%d",solve());
    return 0;
}