指导书 习题
扫扫二维码，随身浏览文档
手机或平板扫扫即可继续访问
C实验指导书-（课后题答案！！！）
举报该文档含有违规或不良信息。
反馈该文档无法正常浏览。
举报该文档为重复文档。
推荐理由：
将文档分享至：
分享完整地址
文档地址：
粘贴到BBS或博客
flash地址：
支持嵌入FLASH地址的网站使用
html代码：
&embed src='/DocinViewer-4.swf' width='100%' height='600' type=application/x-shockwave-flash ALLOWFULLSCREEN='true' ALLOWSCRIPTACCESS='always'&&/embed&
450px*300px480px*400px650px*490px
支持嵌入HTML代码的网站使用
您的内容已经提交成功
您所提交的内容需要审核后才能发布，请您等待！
3秒自动关闭窗口2012年8月 随笔档案 - 魔鬼的惊叹 - 博客园
08 2012 档案
摘要: 这题用hash做。算法导论上面讲的很清楚 1 #include &cstdio& 2 #include &cstring& 3 4 char s[]; 5 int a[100000]; 6 int hash[]; 7 int main() 8 { 9 int n,10 11 memset(hash,0,sizeof(hash));12 memset(a,0,sizeof(a));13 scanf(&%d %d &,&n,&nc);14 scanf(&quo
摘要: 这道题很有意思大致题意：给定一些木棒，木棒两端都涂上颜色，求是否能将木棒首尾相接，连成一条直线，要求不同木棒相接的一边必须是相同颜色的。解题思路：可以用图论中欧拉路的知识来解这道题，首先可以把木棒两端看成节点，把木棒看成边，这样相同的颜色就是同一个节点问题便转化为：给定一个图，是否存在“一笔画”经过涂中每一点，以及经过每一边一次。这样就是求图中是否存在欧拉路Euler-Path。回顾经典的“七桥问题”，相信很多同学马上就明白了什么是 欧拉路 了，这里不多作解释。由图论知识可以知道，无向图存在欧拉路的充要条件为：① 图是连通的；② 所有节点的度为偶数，或者有且只有两个度为奇数的节点。其中①图的连
摘要: 这是一道关于搜索的题，hash，需要用到一个字符串散列函数 1 #include&stdio.h& 2 #include&string.h& 3 #include&stdlib.h& 4 #define M 100003 // 槽数，最好用素数 5 struct node{ 6 7 struct node * 8 }*link[M]={NULL}; 9 char word[],dialect[];10 11 12 int ELFhash(char *key)// UNIX 系统ELF字符串
摘要: 线段树原来遇到过了，不过自己写还是很容易出现问题，特别是递归的时候总是忘记返回，这样老是会爆栈还有，好像分析问题的能力很欠缺，而且宏观的概念不是很好，其实感觉写递归就两点，第一宏观上整体把握，第二细节上仔细认真这道题还是整了我很久，真的不太 清楚别人到底是怎么想出来的，反正我是无能为力了。还是先学习这把，突然让我心里升起了征服的欲望还是回头继续说这道题把，关于线段树的优点不言而喻了，把整个大区间分成了一个一个的小区间，这道题恰好利用了这个性质，更改的时候整个区间一块更改了这里的标记兼价值flag很有意思，这样来解释下把，初始化为1，当线段树中的父节点的所有子节点的flag都一样时，父节点的fl
摘要: 典型的线段树，很长时间没有写了，好多次都直接用的是模板，这次自己写了下，多多少少还是出了点问题 1 #include &iostream& 2 #include &stdio.h& 3 4 int a[1000005]; 5 int n,k; 6 struct node 7 { 8 9101112 };13 node tree[];14 int MIN[1000005],MAX[ 16 int Max(...
摘要: 这道题完全没有思路。唉，可悲看了大牛的思路才发现，人才啊，都是人才啊我拿过来学习下这道题大致分为三个步骤1 求最大公共子串(LCS),这个应该是比较简答的方法，主要是动态转移方程，这里设i,j是字符串a,b的下标,dp[i][j]表示a的0~i ，b的0~j的最大公共子串 动态转移方程分为两种情况： （1）a[i]==b[j] dp[i][j]=dp[i-1][j-1]+1; （2）a[i]!=[j] dp[i][j]=max(dp[i-1][j],dp[i][j-1]);2用两个变量last1[i][j], last2[i][j]来分别保存字符j(a的序号为0，b的序号为1，.....z的序
摘要: 关于最大公共子序列，自己写了个程序程序只要输入两个字符串就ok了一直不明白：最长公共子串和最长公共子序列的区别。 上网查了下，最长公共子串（Longest Common Substirng）和最长公共子序列（Longest Common Subsequence，LCS）的区别为：子串是串的一个连续的部分，子序列则是从不改变序列的顺序，而从序列中去掉任意的元素而获得新的序列；也就是说，子串中字符的位置必须是连续的，子序列则可以不必连续 1 #include 2 #include 3 #include 4 5 char a[2005]; 6 char...
摘要: 这道题个人觉得至少有三种解法，第一种背包，第二种dfs，第三种母函数这道题我用的是背包问题来求的，首先这个问题是多重背包问题，看了背包九讲，多重背包可以转化为01背包，这道题继续把他转化了，因为如果数据过大，效率就得不到保证，为了提高效率，采用了二进制拆分的方法，关于二进制拆分的方法简答来说是这样的：假设原来某一种类的珠宝数量为N，我们可以把N拆成1，2，4，8，……，2^(k-1)，N-2^k+1。这些拆分成的数字能够表示1~N之间的任何一个数。这样，我们就把物品数减小为logN（以2为底，向上取整）。这样把原来的物体转化为了一个一个的单位，以单位计算，这样就成功的把多重背包问题转化为了纯粹
摘要: 转自：http://blog.csdn.net/ronhou/article/details/7738014取模优化当输入样本特别大时，比如给出上百万件物品，这时候仅靠优化算法仍然不能使运行时间降到满意的范围。可考虑如何减少输入样本。poj1014的discussion上有一个非常巧妙的“取模优化”法。设价值为v(1&=v&=6)的物品共有n件，我们希望找到一个比较小的数s(s&n), 且将n件物品v减少到s或s-1件，问题的可分性不变。考虑不可分和可分两种情况：如果该问题不可分，那么n-2件v仍然不可分，依次类推，用s或 s-1替换n仍然不可分如果该问题可分，即可分成价值相
摘要: 转自：http://blog.csdn.net/lyy/article/details/6642572刻苦的训练我打算最后稍微提一下。主要说后者：什么是有效地训练？我想说下我的理解。很多ACMer入门的时候，都被告知：要多做题，做个500多道就变牛了。其实，这既不是充分条件、也不会是必要条件。我觉得一般情况下，对于我们普通学校的大学生，各方面能力的差距不会太大，在这种情况下，训练和学习的方法尤为重要。其实，500题仅仅是一个标志，而且仅仅表示你做ACM-ICPC有一定的时间，我们训练的目的是什么？我觉得有四点1、提高编程能力2、学习算法，（读书，读论文，包括做一些题目验证）3
摘要: 题意：在一块木板上，钉上钉子，排布成等边三角形。一个球从顶部开始，自由下落。每碰到一个钉子以后，等概率地向两边继续滚。现从该等边三角形的钉子中，拔去其中某些钉子。求这个球从顶部开始下落，滚到底部某个格子的概率。思路：DP模拟。逐步递推，分别计算每一层，滚到每一个口的概率。最后一层每个口的概率，就是对应底部每个格子的概率。每一个口的概率，若遇到一个钉子，则除以2后就是下一层对应两个口的概率；若没遇到钉子，则直接等于再下层的对应入口，即直接落下。一开始的初值，就是2^层数，即全部都是钉子时，第一个格子对应的概率。 1 #include &iostream& 2 #include &lt
摘要: 水题dp问题动态转移方程：初始化：sum[1][1]=a[1][1];其余全为0sum[i][j]=max(sum[i-1][j-1]+a[i][j],sum[i-1][j]+a[i][j]),这个的意思是根据图来的，把图好好看下，很容易就写出来了第一次自己写的dp，纪念下…… 1 #include &iostream& 2 3 4 int max(int a,int b) 5 { 6 return a&b?a:b; 7 } 8 int a[105][105]; 9 int sum[105][105];10 int main()11
摘要: 今天开始做dp，感觉dp比较考思维能力，关于那个动态转移方程，我一直很好奇人们是怎么推的呢？？有没有什么方法呢？？？题目大意：每种花有一个编号，有几个花瓶，花瓶也是有编号的，每种花放在不同的花瓶的艺术价值不一样，要你把这些花按某种策略放在这些花瓶里，得到艺术价值总值最大，并且，编号小的花所在的花瓶的编号要比编号大的花所在花瓶的编号小。 ans[i][j]表示前i朵花放进前j个瓶子中的艺术值a[i][j]表示第i多花放在第j个瓶子里面的艺术值动态转移方程：ans[i][j]=max(ans[i][j-1],ans[i-1][j-1]+a[i][j] 1 #include &iostream
摘要: 前面的的几篇关于网络流的我被坑了，原来我用的算法叫做EK下面总结下网络流的模板吧 1 #include &iostream& 2 #include &queue& 3 //#include &conio.h& 4 5 #define arraysize 201 6 int maxData = 0x7 7 int capacity[arraysize][arraysize]; //记录残留网络的容量 8 int flow[arraysize]; //标记从源点到当前节点实际还剩多少流量可用 9 int
摘要: sap算法详解与模板 [转]链接：1. Maximum Flow: Augmenting Path Algorithms Comparison /tc?module=Static&d1=tutorials&d2=maxFlowRevisited2. 刘汝佳《算法艺术与信息学竞赛》 P321 ( 注： 上面的代码似乎有误，retreat()部分未回退& 详见下文or 链接1. & )---------------------------------------------关键概念与性质：距离函数（distanc
摘要: 这道题跟我前面写的那两道网络流的题差不多，刚开始被题的描述吓到了，后来发现稍微变动下，原来的代码还可以继续用是这样的，原来的问题都是单源单汇问题，这题是多源多汇，关键在于把多源多汇问题转化为单源单汇，只要构造一个超级源点和一个超级汇点就ok了，把超级源点和各个源点之间加一条边，把各个汇点和超级汇点之间加一条边，这样就ok了，其实很简单关于最大流的问题我只会这一种方法，其他还有spa，ek ，以及spa算法的优化问题，这些最好都学习下 1 #include &cstdio& 2 #include &cstring& 3 #define Max 0x7f7f7f7f 4 i
摘要: 这道题跟poj1273是一模一样的，只略微改变了几个地方，就ok了,更正下，上面的算法不叫Ford_Fulkerson ,而是EK 1 #include &cstdio& 2 #include &cstring& 3 #define Max 0x7f7f7f7f 4 int n,m; 5 int path[100][100]; 6 int visited[100]; 7 int que[10000]; 8 int pre[100]; 9 int flow[100];10 int min(int a ,int b)11 {12 return a&b?b:a;13 }
摘要: 今天首次接触到网络流，看了半天有些地方还是不太理解，关于算法本身的理解可能还有点问题，所以在实现上还有点困难 1 #include &cstdio& 2 #include &cstring& 3 #define Max 0x7f7f7f7f 4 int n,m; 5 int path[205][205]; 6 int visited[205]; 7 int que[205]; 8 int pre[205]; 9 int flow[205];10 int min(int a ,int b)11 {12 return a&b?b:a;13 }14 int BFS()/
摘要: 还是自己总结下一些简答的东西吧，留着以后用long long gcd (long long a,long long b){ return b==0?a:gcd(b,a%b);}第一次调用的时候a是大于b的，因为这里会判断b==0?,所以第一步要先判断下
摘要: 关于BFS的题目，可以参考http://blog.csdn.net/cambridgeacm/article/category/1169182，比较多，我只做了一部分就做不下去了这几天一直在写BFS，算是二维，三维，优先，指定转弯次数……烦了，真的烦了，下次换个类型写吧题目要求转弯的次数不能超过k，BFS，从一个方向搜到底 1 #include &iostream& 2 #include &stdio.h& 3 #include &cstring& 4 #include &queue& 5 6 7 int
摘要: 三位的bfs，跟二维的差不多 1 #include &iostream& 2 #include &stdio.h& 3 #include &cstring& 4 5 6 char map[35][35][35]; 7 int ans[35][35][35]; 8 int visited[35][35][35]; 9 int x1,y1,z1; 10 int x2,y2,z2; 11 int l,r,c; 12 int dir[6][3]={{1,0,0},{-1,0,0},{0,-1,0},{0,1,0},{0,0,
摘要: 跟前面的几乎是一样的，不过这道题需要记录下路径输出的时候从后往前找，找到第一个时开始输出，所以要用到递归 1 #include &iostream& 2 #include &stdio.h& 3 #include &cstring& 4 #define Max 0x7f7f7f7f 5 6 7 8 int map[6][6]; 9 int visited[6][6];10 int dir[4][2]={{1,0},{-1,0},{0,-1},{0,1}};11 int ans[6][6];12 int pre[30]
摘要: 转自：/ffj/archive//2603632.html 1 #include&iostream& 2 #include&functional& 3 #include&queue& 4 #include&vector& 5 6 7 8 struct cmp1 9 { 10 bool operator () (int &a, int &b) 11 { 12 return a & // ...
摘要: 1 #include &iostream& 2 #include &stdio.h& 3 #include &cstring& 4 #include &queue& 5 #define Max 0x7f7f7f7f 6 7 struct node 8 { 9 10 11 12 friend bool operator & ( node a,node b) 13 { 14 return a.time&b.//开始错在这个...
摘要: 简答的BFS求“马”从一点到另一点的最短距离，马走日，BFS即可 1 #include &iostream& 2 #include &stdio.h& 3 #include &cstring& 4 #define Max 0x7f7f7f7f 5 6 7 int visited[10][10]; 8 int ans[10][10]; 9 char a[5],b[5];10 int dir[9][2]={{-2,1},{-2,-1},{2,1},{2,-1},{-1,2},{-1,-2},{1,2},{1,-2}};1
摘要: 今天第一次动手写BFS,原理都懂，只是原来一直没有实现过，实现起来感觉还是蛮简单的没有用队列，用的是数组这道题：求2个点到KFC的距离之和，使其最小，可用2次BFS，分别求出2个点到各个KFC的最短距离，然后找出和最小的即可 1 #include &stdio.h& 2 #include &cstring& 3 #define Max 0x7f7f7f7f 4 5 int visited1[205][205]; 6 int visited2[205][205]; 7 int ans1[205][205]; 8 int ans2[
摘要: 这个最短路径问题好，刚开始一直TLE,看了别人的结题报告后，突然感觉是自己笨了，不知道，灵活运用了，这道题用到了一个虚拟节点的问题本题中起始点有多个，如果按照正常的方法来做的话，可能要循环多次，求不同起点的最小值，这样时间就会话费的多些，采用虚拟节点后，把这个点到每个起始点的距离都设置为0，当有某个点到其余的点有相同的最短路径是，任选一条即可，这题就是运用的这点知识，好啊 1 #include&stdio.h& 2 #include&string.h& 3 #define inf
int map[]; //注意这道...
摘要: 最短路径的变形，刚开始用g++交，一直超时，后来改用c++交就过了，看来还是c++比较给力#include &stdio.h&#define max(e1,e2) ((e1)&(e2)?(e1):(e2))double safe[];int main(){ while(scanf(&%d&,&n)!=EOF) { //cin&&n; for(int i=1;i&=n;i++) { for(int j=1;j&=n;j++) { //c...
摘要: 跟前面一题一模一样，稍微改了点代码，直接一次AC 1 #include &cstring& 2 #include &stdio.h& 3 #define Max 0x7f7f7f7f 4 5 int map[205][205]; 6 int dis[205],visited[205]; 7 int n,start, 8 void Dijkstra() 9 {10 dis[1]=0;1112 for(int i=1;i&=n;i++)13 {14 int min=M15 ...
摘要: 贡献了一次wa，有重边，忘了考虑，看下discuss真好，要不然不知道这错误要找到什么时候这道题算是基础题吧 1 #include &cstring& 2 #include &stdio.h& 3 #define Max 0x7f7f7f7f 4 5 int map[205][205]; 6 int dis[205],visited[205]; 7 int n,start, 8 void Dijkstra() 9 {10 dis[start]=0;1112 for(int i=0;i&n;i++)
摘要: 原手册下载：http://www.codeblocks.org/docs/manual_en.pdf 译者：JGood(http://blog.csdn.net/Jgood) 译者言：工欲善其事，必先利其器。一个好的工具能事半功倍。写程序时，特别是写C++程序，大部分人脑子里想到的第一个工具就是VisualStudio。不可否认，VS很好很强大，用户体验非常好。但VisualStudio也是有缺点的：它非常庞大；只支持VC，不支持其他的编译器；VS只能在windows下跑，在其他os上就无用武之地；VS是要钱的，而且费用不非（Express版本免费）。Code::Blocks是一个非常优秀的工
摘要: 两个小小的细节，调试了半天啊，不过这次学了下在codeblocks里面的调试，原来我只会在vc里面调试阻断路径问题，Dijkstra算法，从起始点到终点，只要两个步骤，第一求距离起始点最短的点，把该点加入起点集后更新起点到其余个点的距离，知道把所有点都添加进来，所以外循环的次数就是点数 1 #include &stdio.h& 2 #include &cstring& 3 #include &stdlib.h& 4 #define MAX 0x7f7f7f7f 5 int map[155][155],visited[155],dis[155]; 6 char
摘要: 简单题吧，只要把多项式相乘的原理搞明白了，应该很容易想到思路，可能表达上还略微有点不太顺畅 1 #include &iostream& 2 #include &cstring& 3 4 int res[255][105];//第一个中括号表示金额，第二个中括号表示硬笔数量，值表示有多少种方法 5 int tmp[255][105]; 6 int main () 7 { 8 memset(res,0,sizeof(res)); 9 memset(tmp,0,sizeof(tmp));10 int value[]={0,1,5,10
摘要: 这一道题有一个需要考虑的东东，就是硬币的数量不可以超过100，如果没有这个条件的话，还真的是水题一枚所以这道题要用到二维数组，其中有一个来存硬币的 1 #include &iostream& 2 #include &cstring& 3 4 int res[255][105];//第一个中括号表示金额，第二个中括号表示硬笔数量，值表示有多少种方法 5 int tmp[255][105]; 6 int main () 7 { 8 memset(res,0,sizeof(res)); 9 memset(tmp,0,sizeof(tm
摘要: 转自：关于什么是母函数 ， 以及在现实生活中的应用 ， 请大家详看 或者 HDU 母函数 PPT：/MiYu/archive//122290.html对于给出的母函数模板 ， 让人理解起来比较费劲的！以下给出几种解释 ， 和自己理解！//made by syx //time 日 10:17:27//母函数例题/*//整数拆分模板#include &iostream&const int lmax=10000;//c1是用来存放展开式的系数的，而c2则是用来计算时保
摘要: 母函数原来学过一点，不过现在差不多是忘完了，再次学习，刚开始仍感觉不是那么好理解 1 #include &stdio.h& 2 3 int main() 4 { 5 6 int a[121],b[121]; 7 int i,j,k; 8 while(1) 9 {10 scanf(&%d&,&n);11 for(i=0;i&=n;i++){a[i]=1;b[i]=0;}12 for(i=2;i&=n;i++)//第几个多项式13 {14 ...
摘要: 这道题比较有意思，除了用并查集外，还可以用prim，k……（不记得怎么写了）来写 1 #include&iostream& 2 #include&stdio.h& 3 #include&string.h& 4 #include&algorithm& 5 6 7 int father[101]; 8 bool flags[101]; 9 10 struct country11 { }a[ bool cm
摘要: 1 #include &stdio.h& 2 3 4 5 int set[1005]; 6 7 void makeset(int n) 8 { 9 for(int i=1;i&=n;i++)10 {11 set[i]=i;12 }13 }14 15 16 int findset(int x)//查17 {18 if(x!=set[x])19 {20 set[x]=findset(set[x]);//之所以不可以直接返回是因为这里可能有多...
摘要: 1 #include &stdio.h& 2 #include &algorithm& 3 4 int set[]; 5 int num[]; 6 7 int cmp(int a,int b) 8 { 9 return a&b;10 }11 12 void makeset()13 {14 for(int i=1;i&;i++)15 {16 set[i]=i;17 num[i]=1;18 }19 }20 21 22 int ...
摘要: 已知有n个大学生，其中有m对宗教信仰相同的学生，请你估算这n个学生中最多有多少种宗教信仰。依旧是简单的并查集应用。宗教信仰的最大值为学生数n，因此一开始把n个学生作为n个集合，对给出的每对大学生 a 和 b ，如果他们在不同的集合，就合并他们，然后宗教数减一。 1 #include &stdio.h& 2 3 4 5 int set[50005]; 6 7 void makeset(int n) 8 { 9 for(int i=1;i&=n;i++)10 {11 set[i]=i;12 ...
摘要: 1 #include &stdio.h& 2 3 int set[30005]; 4 int num[30005]; 5 void makeset(int n) 6 { 7 for(int i=0;i&n;i++) 8 { 9 set[i]=i;10 num[i]=1;11 }12 }13 14 15 int findset(int x)16 {17 if(x!=set[x])18 {19 set[x]=findset(set[x]);//之所以不可以直接返回是因...
摘要: 1 #include &stdio.h& 2 #include &algorithm& 3 #include &cstring& 4 5 6 struct str 7 { 8 char s[30]; 910 };11 12 str a[ void init(int k)15 {16 for(int i=0;i&k;i++)17 {18 a[i].num=0;19 }20 }21 22 23 int cmp(str a , str b)24 {25 ...
摘要: 简单题已知前序遍历，中序遍历，求后序遍历思路，找到根，找到左子树，找到右子树 1 #include &stdio.h& 2 #include &cstring& 3 4 5 char a[30],b[30]; 6 7 8 void find(int start, int end) 9 {1011 if(start&end)12 {1314 }15 char root=a[count++];16 for( i=i&=end...
摘要: 状态设计： 1、dp[i][0]，表示在结点 i 没放置士兵的情况下，看住以结点 i 为根的子树的所有边所需的最少士兵； 2、dp[i][1]，表示在结点 i 放置士兵的情况下，看住以结点 i 为根的子树的所有边所需的最少士兵。状态转移： 1、dp[i][0]=∑dp[j][1]，j 是 i 的儿子结点；（根结点不放士兵时，与其相连的边必须由儿子结点来看守） 2、dp[i][1]=dp[i][1]+∑ ( MIN ( dp[j][0] , dp[j][1] ) )，j 是 i 的儿子结点。 （根结点放士兵时，儿子结点可放可不放）初始化： d[i][0]...
摘要: 这道题是说，给出一棵树，每个节点有一个权值，要求去掉一条边所能获得的两棵树的最小的权值差，其实不能说是dp因为除了最后一步涉及到了取最小之外，其他的地方都是在枚举而已，没有什么状态转移之类的东西存在，只能说是一道简单的树形的搜索如果你wa了，请检查1：abs（）函数必须要自己写，因为调用的int abs()型的，多以必错无疑2：是否输入输出的每个地方都已经改成了long long 或者__int64,输入的时候是scanf(&%I64d&，&a),输出的时候是printf(&%i64d&，a).我自己的就是某些地方没有全改成这样的输入输出wa了两
摘要: 感谢涛涛不解这道题着实花了很长时间才搞明白，对图的知识忘得太多了，看这道题之前最好先把图的邻接表表示方法看下，有助于对这道题的理解，这道题让我对深度优先遍历又有了进一步的了解这道题最好画个图，有助于理解，不过你要是画个错误的图此题就无解了其实就是一个求无向树的所有子树和的最大值树形dpdp[i][0]表示以i为根，不包括i结点的子树获得最大权dp[i][1]表示以i为根，包括i结点的子树获得的最大权dp[i][0] = max(dp[k][0], dp[k][1]) k为i的所有孩子结点dp[i][1] = i结点的权 + dp[k][1] 如果dp[k][1] & 0 1 #inclu
摘要: 刚开始我被这道题吓到了，心想这要移动这么多次，这不是要超时吗，后来又感觉是约瑟夫问题，唉，想起约瑟夫问题就想起了那个难记的公式，唉，直接放弃了，后来才发现，这道题原来是这么的easy，水题思路：认真观察即可发现，这道题是有规律的，不会让你去循环这么多次，拿个简单的的例子试下，你会发现，当移动r(题目中给的数)次时，数组又回到了原来的样子，所以可直接循环n%r次、 1 #include &iostream& 2 3 4 int a[55]; 5 int tmp[55]; 6 int main() 7 { 8 int C 9 ci...
摘要: 这道题我感觉应该用线段树来做，写了之后还是超时，别的优化方法想不到了，欢迎各位指教(补充一点优化的方法，第一求root digit的时候可以直接对9取余，如果是9的倍数，那么直接就是9，第二在build的时候在最后面加这样一句话：if(b[i].sum&9) b[i].sum-=9;) 1 #include &stdio.h& 2 #include &string.h& 3 #include &algorithm& 4 5 int a[100005]; 6 int res[]; 7 struct
摘要: 这里介绍另外一种解法，此题可以用线段树，可以用树状数组其实这题求的都是下面的和左面的，线段树这种数组结构刚好可以满足，为什么呢？这里稍微解释下吧，也有助于以后的复习看上面这个图，[1,1]，[2,2]这样的叶节点表示题目的的图中的最下一层，而[4,5],[1,3]这样节点的value值是是其子节点之和，多以可以理解为在二维坐标系中是高于下面的节点的，其子节点都在它的左面，可能说的比较模糊，我也是想一会就明白了 1 #include&iostream& 2 #include&fstream& 3 4 5 6 struct e{ 7
20:01:28第一道树状数组，赤裸裸的树状数组题目大意看了半天啊，曾一度想找个学英语的给我翻一下，原来看题都没有觉得这么难理解这里贴一个有翻译的链接：/p-.html其实这道题图的样子和树状数组的图的样子是一样的，都是求左边的和下面的之和，画个图或许可以帮助理解 1 #include &iostream& 2 #include &stdio.h& 3 4 int c[32005]; 5 int lowbit(int x) 6 { 7 return
摘要: 转自：/yykkciwei/archive//1452889.html#commentform（有删改）问题提出：已知数组a[],元素个数为n,现在更改a中的元素,要求得新的a数组中i到j区间内的和(1&=i&=j&=n).思考：对于这个问题,我们可以暴力地来解决,从a[i]一直累加到a[j],最坏的情况下复杂度为O(n),对于m次change&querry,合起来的复杂度为O(m*n),在n或m很大的情况下,这样的复杂度是让人无法忍受的.另外,如果没有元素的变更,我们完全可以存储sum[1,k](k=1
摘要: 线段树啊，有是线段树，有点东西老是搞不懂，build，update ，query，这三个函数到底怎么写，还是不太懂啊有时候看代码真的很抽象，画个图或许可以帮助理解 1 #include &iostream& 2 #include &string.h& 3 #include &cstring& 4 #include &stdio.h& 5 6 char b[1000005],f[1000005]; 7 int first,a,d; 8 int min(int a ,int b) 9 { 10 return
摘要: 确实是水题一道，今天早上没吃饭，看题看了好半天题意:有个卖玩具的店里有一种类似颜料盒的东东，颜料盒的颜色种数从3到12不等，每种颜料有50ml。有一种很特别的颜色叫做灰色，任何一种颜料盒里本来不存在这种颜色，但是可以用任意3种不同的颜色混合而成。现在你需要N种颜色的颜料盒，并且每种颜料的需求量也给定，包括灰色，让你求出需要的最少的该颜料盒的个数思路：如果有灰色，在前面的颜色中选择三种最小的，分别加1，灰色减一，直到灰色为零 1 #include &iostream& 2 #include &algorithm& 3 4 5 in
摘要: 1 #include &stdio.h& 2 int main() 3 { 4 int left[100005]; 5 int right[100005]; 6 int a[100005]; 7 int C 8 scanf(&%d&,&Case); 9 while(Case--)10 {11 int n,i;12 scanf(&%d&,&n);13 if(n==0)14 for(i=0;i&n;i++)15 {16 ...
摘要: 题目链接：http://poj.org/problem?id=2593动态规划大意：给你一个数列，求数列中两个不重叠的子序列的最大和。 从左向右求得left[]数组，left[i]表示0~i之间的最大连续子序列。再从右往做左求最大子序列，然后求0~i,i+1~n-1的两段子序列中的最大和。 1 1 #include &stdio.h& 2 2 int main() 3 3 { 4 4 int left[100005]; 5 5 int right[100005]; 6 6 int a[100005]; 7 7 8 8 while(1) 9 ...
摘要: 转自：/fzu_q_q/blog/static//sort和qsort使用差别 00:09:52|分类：默认分类|字号订阅一、对int类型数组排序int num[100];Sample:int cmp ( const void *a , const void *b ){return *(int *)a - *(int *)b;}qsort(num,100,sizeof(num[0]),cmp);二、对char类型数组排序（同int类型）char word[100];Sample:int cm
摘要: 转自：/skynet/archive//1760518.htmlMap是标准关联式容器（associativecontainer）之一，一个map是一个键值对序列，即（key ,value）对。它提供基于key的快速检索能力，在一个map中key值是唯一的。map提供双向迭代器，即有从前往后的（iterator），也有从后往前的（reverse_iterator）。map要求能对key进行&操作，且保持按key值递增有序，因此map上的迭代器也是递增有序的。如果对于元素并不需要保持有序，可以使用hash_map。map中ke
摘要: 水题一道啊，一次AC啊 1 #include &iostream& 2 #include &algorithm& 3 #include &cstring& 4 5 6 int main() 7 { 8 int a[105]; 9 int res[105];10 int n,q,m;11 int i,j;12 while(1)13 {14 cin&&n&&q;15 if(n==0 && q==0)16 memset(res,0,sizeof(r...
摘要: 水题一道，看清房间到底是怎么分布的看清了啊，我就是第一次没有看清这才wa的 1 #include &iostream& 2 #include &cstring& 3 #include &algorithm& 4 5 6 int cmp (int a,int b) 7 { 8 return a&b; 9 }10 int main()11 {12 int C13 cin&&C14 int from,15 int room[405];16 int i,j;17 while(Ca..
摘要: 这一题和前面做的一道题几乎是一样的，只不过是有个地方犯傻了，唉，wa了好几次说下思路，如果是=，则把每个值都赋为2000（这个数一定要比比较的次数大啊，我刚开始开了100，wa了好几次，唉，你说这能不让人窝火吗）如果是&，把左边的值不为2000的数减一，右边不为2000的数加1如果是&,则反过来最后查找不为2000的绝对值最大的数，则该数必为假币，至于是否会输出0这个结果，那就要看不为2000的绝对值最大的数知否只有一个，如果只有一个，那就是要求的结果，如果多个，那么就输出0 1 #include &iostream& 2 #include &stdlib.h&g
随笔 - 118