《简单算法.ppt》由会员分享，可在线阅读，更多相关《简单算法.ppt（73页珍藏版）》请在三一文库上搜索。
1、西安电子科技大学计算机学院 - School of Computer Science /存 放地图 int place; /当前序号 int m,n; /矩阵大小 int begin; /起始位置 n方法： 按照地图及初态移动机器人直到满足 结束条件：下一个要经过的点（row ，line）满足（row=m | line= n) 或 datarowline 0.用 place +标记刚走过的点。 如果走出地图输出：place 1 step(s) to exit 。 否则输出：datarowline-1 step(s) before a loop of place- datarow line st
2、ep(s) 欠 裳 座 呻 脱 咏 性 歌 巡 沤 霜 舜 去 恋 消 狱 册 桓 独 酪 剖 瘴 操 酵 涨 伍 疟 酉 迫 憎 迫 拌 简 单 算 法 简 单 算 法 西安电子科技大学计算机学院 - School of Computer Science int data100100; / 地图 int place; / 当前位置 int m,n,begin; / 地图大小，初始位置 void move(int row,int col)；/按要求移动机器人 int main() return 0; 贵 妙 狞 糙 土 弹 止 侥 提 让 粪 睫 他 象 毅 对 究 五 疤 秀 焰 琳 情 秧
3、 哲 单 社 俗 棚 嫡 凡 微 简 单 算 法 简 单 算 法 西安电子科技大学计算机学院 - School of Computer Science while( (cinmnbegin) for(int i=0;im;i+) for(int j=0;jch; switch (ch) /把字符转换成整数以便于统一处理 case N: dataij=-1; break; case S: dataij=-2; break; case W: dataij=-3; break; case E: dataij=-4; break; move(0,begin-1); /end of while retu
4、rn 0; /end of main 焚 陷 蜜 靖 遇 盘 归 谗 迭 盏 谦 咱 沙 繁 礁 妮 浊 峻 妆 季 后 舵 付 疥 未 恋 河 哩 税 凹 链 咱 简 单 算 法 简 单 算 法 西安电子科技大学计算机学院 - School of Computer Science while( notExit /end of while if(!notExit) coutplace-1 step(s) to exitendl; else coutdatarowline-1 step(s) before a loop of place-datarowline step(s)endl; /end
5、 of move 矿 渺 括 争 授 肘 瞻 榔 哑 垃 呀 渴 缀 豁 叮 鹰 衷 搅 卧 酷 何 栖 奇 狄 乌 沥 想 烯 盲 蝎 犀 污 简 单 算 法 简 单 算 法 西安电子科技大学计算机学院 - School of Computer Science int n; 思路：输入n后把digital中2*n 1 后剔除，并在奇 数位置按字典序枚举各种插入情况。对每种情况 如果表达式值为0，则输出之。 一 曼 里 颇 疹 赘 神 骚 戮 坤 堡 躁 窃 郸 桅 狱 脑 蘸 葫 仪 弊 晤 寞 艇 扁 博 零 疙 苦 矿 萄 沈 简 单 算 法 简 单 算 法 西安电子科技大学计算机学院
6、- School of Computer Science ifstream fin(zerosum.in); Ofstream fout(zerosum.out); string digital = 11223344556677889; int n; /问题规模 int check()；/ 检查表达式是否为0 void proc(int t)；/确定第t处应插入什么字符 int main() finn; /输入问题规模 digital.resize(2*n -1); /剔除2*n-1后边的元素 proc(0); return 0; 铡 惟 月 醒 痢 巴 花 菏 效 唉 办 烹 浆 幼 掐 绦
7、 蒸 友 寇 碘 佑 缮 随 沤 砾 草 闹 椰 满 坞 露 炙 简 单 算 法 简 单 算 法 西安电子科技大学计算机学院 - School of Computer Science return ; /确定要插入字母在digital中的位置 int i = 2 * t + 1; digitali = ; /插入 （依字母序） proc(t + 1); /在下一个位置插入 digitali = +; proc(t + 1); digitali = -; proc(t + 1); 恍 呐 疯 北 跃 短 东 迟 亲 钝 咋 澳 瓣 笔 勇 罐 浅 党 府 崔 郁 筒 壳 至 爷 敷 擦 欧 卯
8、酒 藤 徽 简 单 算 法 简 单 算 法 西安电子科技大学计算机学院 - School of Computer Science for(int i = 0; i digital.size(); i+) if(digitali != ) teamp += digitali; /*把teamp作为输入流 需要#include */ istringstream ssin(teamp); int sum; ssin sum; char ch; while(ssinch) int t; ssint; if(ch = -) sum -= t; else sum += t; return sum; 逞 欲
9、 尊 克 滦 亭 巾 鬃 锈 清 读 嵌 属 抬 箱 栈 潜 丑 宁 钧 午 涝 任 脏 剁 洽 敝 挎 赞 缉 肪 舒 简 单 算 法 简 单 算 法 西安电子科技大学计算机学院 - School of Computer Science ifstream fin(milk.in); ofstream fout(milk.out); struct IntPair IntPair(int a = 0, int b = 0) first = a, second = b; int first, second; ; /比较谓词 bool small(IntPair i1,IntPair i2) ret
10、urn i1.firsti2.first; int cost(vector vector v; v.reserve(5000); fin N M; for(int i = 0; iPA; v.push_back(IntPair(P,A); foutcost(v,M)endl; return 0; 倪 旋 蚕 葵 钟 谆 墨 阀 塔 滦 蔼 戍 匿 猖 寻 做 苑 汁 尸 君 搔 肃 佣 申 船 拴 豹 萌 膀 昧 榔 奠 简 单 算 法 简 单 算 法 西安电子科技大学计算机学院 - School of Computer Science /按价格排序 int result=0,i=0,area
11、dy=0; while(vi.second+aready 灭 或灭-亮) 现在给出了这个阵列的初始亮灭状态，找一种操作让灯全灭。 渐 矛 吠 毋 噎 烛 晾 懈 恰 亩 搜 膳 刺 豪 孕 则 柔 翼 溉 啤 婆 填 攫 住 是 职 傅 庙 扩 版 干 下 简 单 算 法 简 单 算 法 西安电子科技大学计算机学院 - School of Computer Science /求解的过程 void press(int,int);/处理按键的过程 void output();/输出结果 int lights56;/记录灯状态，0灭，1亮 int ans56;/记录结果，若在x行y列点击，ansx-
12、1y-1=1 int main() /主函数 int n; cinn; for(int i=1;i=n;i+) cout PUZZLE # i1，1-0 if(x0) lightsx-1y = 1-lightsx-1y; if(y0) lightsxy-1 = 1-lightsxy-1; if(x4) lightsx+1y = 1-lightsx+1y; if(y5) lightsxy+1 = 1-lightsxy+1; 厨 跪 考 蚁 返 塘 弯 锣 彤 邻 沈 溺 南 还 绚 葛 惮 诵 庙 胯 煤 菊 泥 赋 续 喇 们 坏 老 锦 百 十 简 单 算 法 简 单 算 法 西安电子科技大
13、学计算机学院 - School of Computer Science for(x=0;x5;x+) for(y=0;ytemp56; for(z=0; z64; z+) /外循环,枚举64个状态 memcpy(lights, temp, sizeof(lights); memset(ans, 0, sizeof(ans);/初始化 for(y=0; y6; y+) if (z /枚举第一行的64种操作。 for(x=1; x5; x+) for(y=0; y6; y+) if (lightsx-1y =1) press(x,y);/*就是刚才所说的规则*/ for(y=0;y=6) outp
14、ut(); break; /是,输出结果，结束搜索 膀 纲 冰 辐 梧 茨 涅 桂 花 迈 扫 藉 淹 楚 孪 王 鹊 戚 沦 恶 屯 款 击 涛 合 萨 佃 镊 奈 卧 页 鹿 简 单 算 法 简 单 算 法 西安电子科技大学计算机学院 - School of Computer Science for(x=0;x5;x+) for(y=0;ytemp56; for(z=0; z64; z+)/外循环，枚举64个状态 memcpy(lights,temp,sizeof(lights); memset(ans,0,sizeof(ans);/初始化 for(y=0; y6;y+) if(z /枚举
15、第一行的64种操作。 for(x=1;x5;x+) for(y=0;y6;y+) if(lightsx-1y=1) press(x,y);/*就是刚才所说的规则*/ for(y=0;y=6) output();break; 假设z=001010 当y=3,1左移3位等于 1000，两数按位求与: 001010 for(x=0;x5;x+) for(y=0;ytemp56; for(z=0;z64;z+)/外循环，枚举64个状态 memcpy(lights,temp,sizeof(lights); memset(ans,0,sizeof(ans);/初始化 for(y=0;y6;y+) if(z
16、 /枚举第一行的64种操作。 for(x=1;x5;x+) for(y=0;y6;y+) if(lightsx-1y=1)press(x,y);/*就是刚才所说的规则*/ for(y=0;y=6) output();break; 芹 抵 擅 蚊 末 尹 洗 孤 凯 渣 宴 骋 侮 确 锌 封 蹭 铸 皋 踞 橙 兔 膳 脊 识 纠 敏 吗 炮 叙 窝 懦 简 单 算 法 简 单 算 法 西安电子科技大学计算机学院 - School of Computer Science for(x=0;x5;x+) for(y=0;ytemp56; for(z=0;z64;z+)/外循环,枚举64个状态 me
17、mcpy(lights,temp,sizeof(lights); memset(ans,0,sizeof(ans);/初始化 for(y=0;y6;y+) if(z /枚举第一行的64种操作。 for(x=1;x5;x+) for(y=0;y6;y+) if(lightsx-1y=1)press(x,y);/*就是刚才所说的规则*/ for(y=0;y=6) output();break; /是,输出结果，结束搜索 园 渊 购 垫 戏 胰 般 幽 侣 秦 逐 繁 含 临 已 兆 乙 绿 露 捌 驰 乒 挨 酗 躺 壳 怔 恭 宙 熏 言 庸 简 单 算 法 简 单 算 法 西安电子科技大学计算
18、机学院 - School of Computer Science for(x=0;x5;x+) for(y=0;ytemp56; for(z=0;z64;z+)/枚举64个状态 memcpy(lights, temp, sizeof(lights); memset(ans, 0, sizeof(ans);/初始化 for(y=0;y6;y+) if(z /枚举第一行的64种操作。 for(x=1;x5;x+) for(y=0;y6;y+) if(lightsx-1y=1)press(x,y);/*就是刚才所说的规则*/ for(y=0;y=6) output();break; 技 盼 谷 苑
19、奖 目 圾 洞 毁 由 狄 渗 慌 面 旷 埔 徒 咒 美 羌 女 茶 流 悉 欺 讯 侍 搓 售 格 瞻 咽 简 单 算 法 简 单 算 法 西安电子科技大学计算机学院 - School of Computer Science for(x=0;x5;x+) coutansx0; for(y=1;y6;y+) cout ansxy; cout endl; 三 驱 炙 帖 白 轧 麦 妹 人 烽 擦 一 侗 豺 靛 久 架 妒 届 搏 则 俯 骗 介 叼 和 爪 竟 到 徐 筐 鸭 简 单 算 法 简 单 算 法 西安电子科技大学计算机学院 - School of Computer Scienc
20、e int people501;/每个人的book数 int books501; bool proc(long long t, int m, int k) /*对给定时间t寻找贪心方案: 从后 向前，寻找剩余书数m,不小于剩余 人数k，pages不大于t的最长区间 */ /输出结果 void print(int k) int j=0; for(int i=0; i k; i+) if (i) cout / ; for(; peoplei; peoplei-) cout 1 ) cout ; coutendl; 代码 篮 此 扶 瞎 置 瘸 漏 拼 茂 表 忧 距 辐 剿 橡 谋 珐 沫 镁 妓
21、 瞻 媳 榴 朝 炒 漫 甄 健 允 汗 抢 毛 简 单 算 法 简 单 算 法 西安电子科技大学计算机学院 - School of Computer Science ik; i+) peoplei = 0; for(-k; k; k-)/寻找一个slash long long pages=0; while(pages+booksm-1=t) if (m=k) break; pages += books-m; peoplek+; long long pages=0; while(m-) pages+=booksm; people0+; if (pages n; /测试数据组数n for(; n
22、; n-) cinmk; /书数m, 人数k for(int t=0;t bookst; /二分给定时间 t long long mid,down=0,up=5000000000LL; while( up-down1 ) mid = (up+down)/2; if ( proc(mid,m,k) ) up = mid; else down = mid; proc(up, m, k); print(k); return 0; 焉 澳 粕 瘫 沿 鱼 炔 估 驯 咀 恳 顾 窝 弗 播 邑 肃 饥 忆 寝 眉 道 役 垮 各 狼 尊 涂 氛 去 高 挫 简 单 算 法 简 单 算 法 西安电子科技
23、大学计算机学院 - School of Computer Science & Engineering, Xidian University, China 题目列表 nRobot motion (zju1708, 模拟） nZero sum（ USACO 36, 枚举） nMixing milk（usaco76, 贪心） nExtended Lights Out（ zju 1354, 枚举贪心） nGone fishing(北美中东部区域赛题目，枚举贪心） nCoping books（zju2002, 二分贪心） 图 谤 业 铆 氢 畅 况 钱 迪 循 忍 入 帧 薪 秤 溜 防 戎 人 摇 良
24、 谢 熊 栈 滞 凿 腰 饭 说 醉 勘 饱 简 单 算 法 简 单 算 法 西安电子科技大学计算机学院 - School of Computer Science & Engineering, Xidian University, China 几个不错的网站 n浙江大学(zju)： n北京大学(pku)： n美国中学信息学网站(usaco)：极力推荐 n西班牙信息学竞赛网站（UVA）: http:/acm.uva.es/problemset/ 焊 豫 饥 培 娠 丝 煽 捉 苍 桔 孺 俺 读 优 隆 群 洪 闭 挑 助 辗 楚 或 嚷 惯 像 哑 裂 逛 欲 弹 杠 简 单 算 法 简 单 算 法