前言

懶…

正題

---

題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");//輸出} }

總結

以上是生活随笔為你收集整理的【jzoj】2018.2.1 NOIP普及组——D组模拟赛的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。