2018.01.21【NOIP普及组】模拟赛D组

这是昨天做的。

JZOJ NO.1 【2011.12.31普及模拟】逃离洞穴

一看这道题就想到了floyd。

（1）最多有多少个人可以逃离 离出口的最短路径不超过时间的人数

（2）最慢游客离开要多少时间 离出口最远的游客。（有游客才求）

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int n,m,t,k,maxx,x,y,l,ans;
int f[501][501],a[501],b[501];
int main(){ 
    freopen("escape.in","r",stdin);
    freopen("escape.out","w",stdout);
    memset(f,0x7f,sizeof(f));
    scanf("%d%d%d",&n,&m,&t);
    for (int i=1;i<=m;i++) 
    scanf("%d%d%d",&x,&y,&l),
    f[x][y]=l,f[y][x]=l;
    scanf("%d",&k);
    for (int i=1;i<=k;i++) scanf("%d",&x),a[x]++;
    for (int k=1;k<=n;k++)
    for (int i=1;i<=n;i++)
    for (int j=1;j<=n;j++)
    if (f[i][j]>(long long)f[i][k]+f[k][j]) 
    f[i][j]=f[i][k]+f[k][j]; b[1]=0; b[n]=0;
    for (int i=2;i<=n-1;i++) b[i]=min(f[i][1],f[i][n]);
    for (int i=1;i<=n;i++) if (a[i]) maxx=max(b[i],maxx),ans+=(b[i]<=t)?a[i]:0;
    printf("%d\n%d",ans,maxx);
    return 0;
}

JZOJ NO.2 【2011.12.31普及模拟】抓捕嫌疑犯

思路：快排

#include <cstdio>
#include <algorithm>
#include <cmath>
using namespace std;
struct z{int x,y; double l;}a[30001]; int o(int x){return x*x;}
int r,c,n,m;
double make(int i){return sqrt((double)o(a[i].x-r)+o(a[i].y-c));}
bool cmp(z p,z q){
if (p.l!=q.l) return p.l>q.l; 
if (p.x!=q.x) return p.x<q.x;
return p.y<q.y;
}
int main(){
    freopen("suspect.in","r",stdin);
    freopen("suspect.out","w",stdout);
    scanf("%d%d",&r,&c);
    scanf("%d%d",&n,&m);
    for (int i=1;i<=n;i++) 
    scanf("%d%d",&a[i].x,&a[i].y),a[i].l=make(i);
    sort(a+1,a+1+n,cmp); int i;
    int s=0,head=0,tail=0; double mixn=2147483647;
    for (i=1;i<=n;i++){
        if (a[i].l<mixn) s++,mixn=a[i].l;
        if (s==m&&!head) head=i;
        if (s>m) break;
    } tail=i-1; if (!head) head=tail+1;
    printf("%d\n",tail-head+1);
    for (i=head;i<=tail;i++) printf("%d %d\n",a[i].x,a[i].y);
    return 0;
}

JZOJ NO.3 【2011.12.31普及模拟】堆箱子

思路：可以随意摆放但只有六种状态。

快排后递推就可以了。

代码如下

#include <cstdio>
#include <algorithm>
#define f1 (i-1)*6+1
#define f2 (i-1)*6+2
#define f3 (i-1)*6+3
#define f4 (i-1)*6+4
#define f5 (i-1)*6+5
#define f6 (i-1)*6+6
using namespace std;
struct g{int x,y,z,f;}a[601];
int n,manx;
void init(); 
bool cmp(g p,g q);
int main(){
    freopen("boxes.in","r",stdin);
    freopen("boxes.out","w",stdout);
    scanf("%d",&n);
    init(); n*=6;
    sort(a+1,a+1+n,cmp);
    for (int i=1;i<=n;i++)
    for (int j=i+1;j<=n;j++) 
    if (a[i].x>a[j].x&&a[i].y>a[j].y)
    a[j].f=max(a[j].f,a[i].f+a[j].z);
    for (int i=1;i<=n;i++) manx=max(manx,a[i].f);
    printf("%d",manx);
    return 0;
}
bool cmp(g p,g q){
    if (p.x!=q.x) return p.x>q.x;
    if (p.y!=q.y) return p.y>q.y;
    return p.z>q.z;
}
void init(){
    for (int i=1;i<=n;i++){
        scanf("%d%d%d",&a[f1].x,&a[f1].y,&a[f1].z);
        a[f2].x=a[f1].x; a[f2].y=a[f1].z; a[f2].z=a[f1].y;
        a[f3].x=a[f1].y; a[f3].y=a[f1].x; a[f3].z=a[f1].z;
        a[f4].x=a[f1].z; a[f4].y=a[f1].y; a[f4].z=a[f1].x;
        a[f5].x=a[f1].y; a[f5].y=a[f1].z; a[f5].z=a[f1].x;
        a[f6].x=a[f1].z; a[f6].y=a[f1].x; a[f6].z=a[f1].y;
        a[f1].f=a[f1].z; a[f2].f=a[f2].z; a[f3].f=a[f3].z;
        a[f4].f=a[f4].z; a[f5].f=a[f5].z; a[f6].f=a[f6].z;
    }
}

JZOJ NO.4 【东莞市选2014】能源大亨

一开始以为这道题很难，没想到竟然模拟。
就是减少2的个数。

代码如下

#include <cstdio>
#include <cstring>
using namespace std;
char s[100001];
int n,m; unsigned long long w,u,ans;
int main(){
    freopen("energy.in","r",stdin);
    freopen("energy.out","w",stdout);
    scanf("%d\n%s",&n,s);
    for (int i=0;i<strlen(s);i++){
        if (s[i]=='2'&&m+2<=n) w++,m+=2;//能放就放
        if (s[i]=='1'){
            if (m+1<=n) u++,m++;//能放就放
            else if (w) u++,w--,m-=1;//不能放，能拆2就放
        }
        ans+=w+u;（2和1的个数）
    }
    printf("%llu",ans);//int不够
}