【jzoj】2018.2.1 NOIP普及组——D组模拟赛

前言

懒…

正题

---

题1：牛车（jzoj1390）

有m条公路，有n头牛各开一辆车，如果有x辆车开在它前门，它速度就会降低d*x，路上速度至少为l。求有多少头牛可以上路。

---

输入

第1行: 4个空格隔开的整数N,M,D,L
第2..N+1行: 第i+1行描述第i头牛的起初车速。

输出

第一行: 输出一个整数表示最多可以在高速上行驶的牛车数量。

样例输入

3 1 1 5
5
7
5

样例输出

2

---

贪心，一行一行的从小到大塞牛

---

代码

#include<cstdio>
#include<algorithm>
using namespace std;
int n,m,d,l,a[50001],s,num[50001],j;
int main()
{
    scanf("%d%d%d%d",&n,&m,&d,&l);
    for (int i=1;i<=n;i++) scanf("%d",&a[i]);//输入
    sort(a+1,a+1+n);//排序
    for (int i=1;i<=n;i++)
    {
        for (j=1;j<=(n-1)/m+1;j++)//最多可以塞几头牛
        {
            if (a[i]-d*(j-1)>=l && num[j]<m)//寻找位置
              {num[j]++;break;}//塞
        }
        if (j<=(n-1)/m+1) s++;//塞入
    }
    printf("%d",s);//输出
}

---

题2：危险系数（jzoj1391）

有n个岛屿，要按顺序到达m个岛屿（可以重复或不连续），已知每个岛之间的危险系数。求最小危险系数。

---

输入

第1行: 两个数, N 和 M
第 2..M+1行: 第i+1行表示给定的序列中第i个岛屿A_i
第M+2..N+M+1行：每行N个整数，表示岛屿之间的危险系数，对角线上一定是0。

输出

输出满足要求的最小危险系数

样例输入

3 4
1
2
1
3
0 5 1
5 0 2
1 2 0

样例输出

7

---

最短路，因为要求每个点的所以用Floyd算法（反正数据小）

---

代码

#include<cstdio>
#include<iostream>
using namespace std;
int n,m,f[10001],a[101][101],s;
int main()
{
    scanf("%d%d",&n,&m);
    for (int i=1;i<=m;i++) scanf("%d",&f[i]);
    for (int i=1;i<=n;i++)
      for (int j=1;j<=n;j++)
        scanf("%d",&a[i][j]);
    for (int k=1;k<=n;k++)
      for (int i=1;i<=n;i++)
        for (int j=1;j<=n;j++)
          if (i!=j && i!=k && j!=k)
          {
            a[i][j]=min(a[i][j],a[i][k]+a[k][j]);
          }//Floyd算法
    for (int i=2;i<=m;i++)
    {
        s+=a[f[i-1]][f[i]];//计算距离
    }
    printf("%d",s);
}

---

题目3：前缀转后缀（jzoj1590）

输入一个前缀表达式，转成后缀表达式

---

输入

输入一个前缀表达式，运算符只有“+”和“-”，操作数都是只有1个位数字(0到9)，运算符和操作数之间都用一个空格隔开，表达式没有前导空格。每个表达式都是合法的，并且运算符不超过20个。

输出

输出对应的后缀表达式。

样例输入

1

样例输出

1

---

如图建立一颗树，求出他的后序遍历就好了。这里不难发现，只有符号后才有分支（两个）。

---

代码

#include<cstdio>
#include<cstring>
using namespace std;
struct point{
    int son1,son2;
};
point tree[201];
int m,n;
char c[201];
int buld(int x)//建树
{
    m++;//位置
    if (c[x]=='+' || c[x]=='-')//符号
    {
        tree[x].son1=buld(m+1);//分支
        tree[x].son2=buld(m+1);//分支
        return x;
    }
    else {
        tree[x].son1=-1;tree[x].son2=-1;//数字没有分支
        return x;
    }
}
int print(int x)//后序遍历输出
{
    if (tree[x].son1!=-1) print(tree[x].son1);
    if (tree[x].son2!=-1) print(tree[x].son2);
    printf("%c ",c[x]);
}
int main()
{
    //freopen("j4.in","r",stdin);
    //freopen("j4.out","w",stdout);
    n=0;char w;
    while ((c[++n]=getchar())!='\n') 
    {
      w=getchar();
      if (w=='\n') break;
    }//读入
    n--;
    buld(1);
    print(1);
}

---

题目4：游戏（jzoj1591）

有4种材料，ABCD。每种材料有一定数量，以下情况可以产生反应：
AABDD
ABCD
CCD
BBB
AD
两个人轮流取材料，直到有人无法产生反应为止就输了。两个人是聪明绝顶的人。
求胜者

---

输入

第一行输入一个整数N(1<=N<=100)，表示游戏次数，接下来N行，每行四个整数，分别表示游戏开始时A,B,C,D四种材料的数量。假设一开始每种材料的数量都在0到60之间。

输出

对于每次游戏输出赢者的名字。

样例输入

6
0 2 0 2
1 3 1 3
1 5 0 3
3 3 3 3
8 8 6 7
8 8 8 8

样例输出

Roland
Patrick
Roland
Roland
Roland
Patrick

---

这里用记忆化搜索模拟情况，然后用返回确定胜者。

---

代码

#include<cstdio>
using namespace std;
int w[5][4]={{2,1,0,2},{1,1,1,1},{0,0,2,1},{0,3,0,0},{1,0,0,1}};//预处理情况
int f[61][61][61][61],a,b,c,d,n;
int dfs(int a,int b,int c,int d)
{
    if (f[a][b][c][d]!=0) return f[a][b][c][d];//记忆化搜索
    for (int i=0;i<5;i++)
    {
        if (a>=w[i][0] && b>=w[i][1] && c>=w[i][2] && d>=w[i][3])//如果可以取
        {
            if (dfs(a-w[i][0],b-w[i][1],c-w[i][2],d-w[i][3])==2)//搜索
            {
                f[a][b][c][d]=1;//记忆
                return 1;
            }
        }
    }
    f[a][b][c][d]=2;//记忆
    return 2;
}
int main()
{
    //freopen("j5.in","r",stdin);
    //freopen("j5.out","w",stdout);
    scanf("%d",&n);
    for (int i=1;i<=n;i++)
    {
        scanf("%d%d%d%d",&a,&b,&c,&d);
        if (dfs(a,b,c,d)==2) printf("Roland\n");
        else printf("Patrick\n");//输出
    }
}