前言
懒…
正题
题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#include 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]
题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#include 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#include 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这里用记忆化搜索模拟情况，然后用返回确定胜者。
代码
#includeusing 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");//输出 }}