洛谷-算法1-1-模拟与高精度3

P1518 [USACO2.4] 两只塔姆沃斯牛 The Tamworth Two题目描述两只牛逃跑到了森林里。Farmer John 开始用他的专家技术追捕这两头牛。你的任务是模拟他们的行为牛和 John。追击在 10×10 的平面网格内进行。一个格子可以是空地一个障碍物两头牛它们总在一起或者 Farmer John。两头牛和 Farmer John 可以在同一个格子内当他们相遇时但是他们都不能进入有障碍的格子。一个格子可以是.空地*障碍物C两头牛FFarmer John。这里有一个地图的例子*...*..... ......*... ...*...*.. .......... ...*.F.... *.....*... ...*...... ..C......* ...*.*.... .*.*......牛在地图里以固定的方式游荡。每分钟它们可以向前移动或是转弯。如果前方无障碍地图边沿也是障碍它们会按照原来的方向前进一步。否则它们会用这一分钟顺时针转 90 度。 同时它们不会离开地图。Farmer John 深知牛的移动方法他也这么移动。每次每分钟Farmer John 和两头牛的移动是同时的。如果他们在移动的时候穿过对方但是没有在同一格相遇我们不认为他们相遇了。当他们在某分钟末在某格子相遇那么追捕结束。读入十行表示地图。每行都只包含 10 个字符表示的含义和上面所说的相同。保证地图中只有一个F和一个C。F和C一开始不会处于同一个格子中。计算 Farmer John 需要多少分钟来抓住他的牛假设牛和 Farmer John 一开始的行动方向都是正北即上。 如果 John 和牛永远不会相遇输出 0。输入格式输入共十行每行 10 个字符表示如上文描述的地图。输出格式输出一个数字表示 John 需要多少时间才能抓住牛们。如果 John 无法抓住牛则输出 0。输入输出样例输入 #1复制*...*..... ......*... ...*...*.. .......... ...*.F.... *.....*... ...*...... ..C......* ...*.*.... .*.*......输出 #1复制49说明/提示翻译来自NOCOWUSACO 2.4实现代码#include iostream #include algorithm using namespace std; char ch[15][15]; struct Node { int x, y; int fw; int c; }; int cnt 0; Node a[15][15]; void dfs_2(int fx, int fy, int cx, int cy) { if (a[cx][cy].fw 1) { if (cx - 1 0 || a[cx - 1][cy].c 4) { a[cx][cy].fw; a[cx][cy].fw--; a[cx][cy].fw % 4; a[cx][cy].fw; } else { swap(a[cx - 1][cy], a[cx][cy]); cx--; } } else if (a[cx][cy].fw 2) { if (cy 1 10 || a[cx][cy 1].c 4) { a[cx][cy].fw; a[cx][cy].fw--; a[cx][cy].fw % 4; a[cx][cy].fw; } else { swap(a[cx][cy 1], a[cx][cy]); cy; } } else if (a[cx][cy].fw 3) { if (cx 1 10 || a[cx 1][cy].c 4) { a[cx][cy].fw; a[cx][cy].fw--; a[cx][cy].fw % 4; a[cx][cy].fw; } else { swap(a[cx 1][cy], a[cx][cy]); cx; } } else if (a[cx][cy].fw 4) { if (cy - 1 0 || a[cx][cy - 1].c 4) { a[cx][cy].fw; a[cx][cy].fw--; a[cx][cy].fw % 4; a[cx][cy].fw; } else { swap(a[cx][cy - 1], a[cx][cy]); cy--; } } } void dfs(int fx, int fy, int cx, int cy) { cnt; bool flag false; if (a[fx][fy].fw 1) { if (fx - 1 0 || a[fx - 1][fy].c 4) { a[fx][fy].fw; a[fx][fy].fw--; a[fx][fy].fw % 4; a[fx][fy].fw; } else { if (a[fx - 1][fy].fw) { dfs_2(fx, fy, cx, cy); flag true; } swap(a[fx - 1][fy], a[fx][fy]); fx--; } } else if (a[fx][fy].fw 2) { if (fy 1 10 || a[fx][fy 1].c 4) { a[fx][fy].fw; a[fx][fy].fw--; a[fx][fy].fw % 4; a[fx][fy].fw; } else { if (a[fx][fy 1].fw) { dfs_2(fx, fy, cx, cy); flag true; } swap(a[fx][fy 1], a[fx][fy]); fy; } } else if (a[fx][fy].fw 3) { if (fx 1 10 || a[fx 1][fy].c 4) { a[fx][fy].fw; a[fx][fy].fw--; a[fx][fy].fw % 4; a[fx][fy].fw; } else { if (a[fx 1][fy].fw) { dfs_2(fx, fy, cx, cy); flag true; } swap(a[fx 1][fy], a[fx][fy]); fx; } } else if (a[fx][fy].fw 4) { if (fy - 1 0 || a[fx][fy - 1].c 4) { a[fx][fy].fw; a[fx][fy].fw--; a[fx][fy].fw % 4; a[fx][fy].fw; } else { if (a[fx][fy - 1].fw) { dfs_2(fx, fy, cx, cy); flag true; } swap(a[fx][fy - 1], a[fx][fy]); fy--; } } if (!flag) { dfs_2(fx, fy, cx, cy); } if (cnt 160000) { cnt 0; return; } if (fx cx fy cy) { return; } dfs(fx, fy, cx, cy); } int main() { int fx, fy, cx, cy; fx fy cx cy 0; for (register int i 1; i 10; i) { for (register int j 1; j 10; j) { cin ch[i][j]; a[i][j].x i; a[i][j].y j; if (ch[i][j] C || ch[i][j] F) { a[i][j].fw 1; } else { a[i][j].fw 0; } if (ch[i][j] C) { a[i][j].c 1; cx i; cy j; } else if (ch[i][j] F) { a[i][j].c 2; fx i; fy j; } else if (ch[i][j] .) a[i][j].c 3; else a[i][j].c 4; } } dfs(fx, fy, cx, cy); cout cnt endl; return 0; }P1067 [NOIP 2009 普及组] 多项式输出题目描述一元 n 次多项式可用如下的表达式表示f(x)an​xnan−1​xn−1⋯a1​xa0​,an​0其中ai​xi 称为 i 次项ai​ 称为 i 次项的系数。给出一个一元多项式各项的次数和系数请按照如下规定的格式要求输出该多项式多项式中自变量为 x从左到右按照次数递减顺序给出多项式。多项式中只包含系数不为 0 的项。如果多项式 n 次项系数为正则多项式开头不出号如果多项式 n 次项系数为负则多项式以-号开头。对于不是最高次的项以号或者-号连接此项与前一项分别表示此项系数为正或者系数为负。紧跟一个正整数表示此项系数的绝对值如果一个高于 0 次的项其系数的绝对值为 1则无需输出 1。如果 x 的指数大于 1则接下来紧跟的指数部分的形式为“xb”其中 b 为 x 的指数如果 x 的指数为 1则接下来紧跟的指数部分形式为 x如果 x 的指数为 0则仅需输出系数即可。多项式中多项式的开头、结尾不含多余的空格。输入格式输入共有 2 行。第一行 1 个整数n表示一元多项式的次数。第二行有 n1 个整数其中第 i 个整数表示第 n−i1 次项的系数每两个整数之间用空格隔开。输出格式输出共 1 行按题目所述格式输出多项式。输入输出样例输入 #1复制5 100 -1 1 -3 0 10输出 #1复制100x^5-x^4x^3-3x^210输入 #2复制3 -50 0 0 1输出 #2复制-50x^31说明/提示NOIP 2009 普及组 第一题对于 100% 数据0≤n≤100−100≤ 系数 ≤100。实现代码#includebits/stdc.h using namespace std; int main(){ int n, a; cin n; for(int in; i0; i--){ cin a; if(a){ if(ina0) cout ; if(abs(a)1||i0) cout a; if(a-1i) cout -; if(i0) cout x; if(i1) cout ^ i; } } return 0; }P1098 [NOIP 2007 提高组] 字符串的展开题目描述在初赛普及组的“阅读程序写结果”的问题中我们曾给出一个字符串展开的例子如果在输入的字符串中含有类似于d-h或者4-8的字串我们就把它当作一种简写输出时用连续递增的字母或数字串替代其中的减号即将上面两个子串分别输出为defgh和45678。在本题中我们通过增加一些参数的设置使字符串的展开更为灵活。具体约定如下遇到下面的情况需要做字符串的展开。在输入的字符串中出现了减号-减号两侧同为小写字母或同为数字且按照 ASCII 码的顺序减号右边的字符严格大于左边的字符。参数 p1​展开方式。p1​1 时对于字母子串填充小写字母p1​2 时对于字母子串填充大写字母。这两种情况下数字子串的填充方式相同p1​3 时不论是字母子串还是数字字串都用与要填充的字母个数相同的星号*来填充。参数 p2​填充字符的重复个数。p2​k 表示同一个字符要连续填充 k 个。例如当 p2​3 时子串d-h应扩展为deeefffgggh。减号两边的字符不变。参数 p3​是否改为逆序。p3​1 表示维持原来顺序p3​2 表示采用逆序输出。注意这时候仍然不包括减号两端的字符。例如当 p1​1、p2​2、p3​2 时子串d-h应扩展为dggffeeh。如果减号右边的字符恰好是左边字符的后继只删除中间的减号。例如d-e应输出为de3-4应输出为34。如果减号右边的字符按照 ASCII 码的顺序小于或等于左边字符输出时要保留中间的减号。例如d-d应输出为d-d3-1应输出为3-1。输入格式共两行。第 1 行为用空格隔开的 3 个正整数依次表示参数 p1​,p2​,p3​。第 2 行为一行字符串仅由数字、小写字母和减号-组成。行首和行末均无空格。输出格式共一行为展开后的字符串。输入输出样例输入 #1复制1 2 1 abcs-w1234-9s-4zz输出 #1复制abcsttuuvvw1234556677889s-4zz输入 #2复制2 3 2 a-d-d输出 #2复制aCCCBBBd-d说明/提示40% 的数据满足字符串长度不超过 5。100% 的数据满足1≤p1​≤31≤p2​≤81≤p3​≤2字符串长度不超过 100。NOIP 2007 提高组第二题。实现代码#includebits/stdc.h using namespace std; int p1,p2,p3,i0,k; char ch[300],be,af,f,j,p; int main() { scanf(%d%d%d%s,p1,p2,p3,ch); while(ch[i]){ bech[i-1];afch[i1];fch[i]; if(f-afbe(be0af9||beaafz)){ for(p31?jbe1:jaf-1; p31?jaf:jbe; p31?j:j--){ pj; if(p12) p(pa)?p-32:p; else if(p13) p*; for(k0; kp2; k) printf(%c,p); } } else printf(%c,f); i; } return 0; }P1065 [NOIP 2006 提高组] 作业调度方案题目描述我们现在要利用 m 台机器加工 n 个工件每个工件都有 m 道工序每道工序都在不同的指定的机器上完成。每个工件的每道工序都有指定的加工时间。每个工件的每个工序称为一个操作我们用记号j-k表示一个操作其中 j 为 1 到 n 中的某个数字为工件号k 为 1 到 m 中的某个数字为工序号例如2-4表示第 2 个工件第 4 道工序的这个操作。在本题中我们还给定对于各操作的一个安排顺序。例如当 n3,m2 时1-1,1-2,2-1,3-1,3-2,2-2就是一个给定的安排顺序即先安排第 1 个工件的第 1 个工序再安排第 1 个工件的第 2 个工序然后再安排第 2 个工件的第 1 个工序等等。一方面每个操作的安排都要满足以下的两个约束条件。对同一个工件每道工序必须在它前面的工序完成后才能开始同一时刻每一台机器至多只能加工一个工件。另一方面在安排后面的操作时不能改动前面已安排的操作的工作状态。由于同一工件都是按工序的顺序安排的因此只按原顺序给出工件号仍可得到同样的安排顺序于是在输入数据中我们将这个安排顺序简写为1 1 2 3 3 2。还要注意“安排顺序”只要求按照给定的顺序安排每个操作。不一定是各机器上的实际操作顺序。在具体实施时有可能排在后面的某个操作比前面的某个操作先完成。例如取 n3,m2已知数据如下机器号/加工时间工件号工序 1工序 211/32/221/22/532/21/4则对于安排顺序1 1 2 3 3 2下图中的两个实施方案都是正确的。但所需要的总时间分别是 10 与 12。方案 1用时 10时间12345678910机器 1 执行工序1-11-11-12-12-13-23-23-23-2无机器 2 执行工序3-13-1无1-21-22-22-22-22-22-2方案 2用时 12时间123456789101112机器 1 执行工序1-11-11-12-12-1无无3-23-23-23-2无机器 2 执行工序无无无1-21-23-13-12-22-22-22-22-2当一个操作插入到某台机器的某个空档时机器上最后的尚未安排操作的部分也可以看作一个空档可以靠前插入也可以靠后或居中插入。为了使问题简单一些我们约定在保证约束条件 (1.)(2.) 的条件下尽量靠前插入。并且我们还约定如果有多个空档可以插入就在保证约束条件 (1.)(2.) 的条件下插入到最前面的一个空档。于是在这些约定下上例中的方案一是正确的而方案二是不正确的。显然在这些约定下对于给定的安排顺序符合该安排顺序的实施方案是唯一的请你计算出该方案完成全部任务所需的总时间。输入格式第 1 行为两个正整数 m, n用一个空格隔开 其中 m(20) 表示机器数n(20) 表示工件数。第 2 行m×n 个用空格隔开的数为给定的安排顺序。接下来的 2n 行每行都是用空格隔开的 m 个正整数每个数不超过 20。其中前 n 行依次表示每个工件的每个工序所使用的机器号第 1 个数为第 1 个工序的机器号第 2 个数为第 2 个工序机器号等等。后 n 行依次表示每个工件的每个工序的加工时间。可以保证以上各数据都是正确的不必检验。输出格式1 个正整数为最少的加工时间。输入输出样例输入 #1复制2 3 1 1 2 3 3 2 1 2 1 2 2 1 3 2 2 5 2 4输出 #1复制10说明/提示NOIP 2006 提高组 第三题实现代码#include stdio.h int m, n; int list[501]; struct Information { int id; int cost; } a[21][21]; int mac[21][100001] {0}; int step[21] {0}; int las_time[21] {0}; int ans 0; int main(){ scanf(%d%d, m, n); for (int i 1; i m * n; i) { scanf(%d, list i); } for (int i 1; i n; i) { for (int j 1; j m; j) { scanf(%d, a[i][j].id); } } for (int i 1; i n; i) { for (int j 1; j m; j) { scanf(%d, a[i][j].cost); } } for (int i 1; i m * n; i) { int now list[i]; step[now]; int id a[now][step[now]].id, cost a[now][step[now]].cost; int s 0; for (int j las_time[now] 1; ; j) { if (mac[id][j] 0) { s; } else { s 0; } if (s cost) { for (int k j - cost 1; k j; k) { mac[id][k] 1; } if (j ans) ans j; las_time[now] j; break; } } } printf(%d, ans); return 0; }