exercise1 ACM
第一次作业
1、平面分割方法
设有n条封闭曲线画在平面上，而任何两条封闭曲线恰好相交于两点，且任何三条封闭曲线不相交于同一点，问这些封闭曲线把平面分割成的区域个数。
输入示例：
3
输出示例：
8
要求：
用两种方法：
（1）得到第n项与其之前已知项之间的关系，程序用递归实现
（2）得到第n项的通项公式，程序直接实现。
解：
每增加一条封闭曲线该曲线就会与之前的每条曲线产生两个交点，所以会增加2（n-1）个交点。
（1）递归关系：f(n)=f(n-1)+2(n-1)(增加几个交点就增加几个平面)，f(1)=2 （2）通项公式：f(n)=n(n-1)+2
//(1)
//平面分割方法
int countArea(int n)//递归法
{
if(n==1)
return 2;
else
return countArea(n-1)+2*(n-1);
}
//通项公式法an=2+n(n-1)
int countArea2(int n)
{
return 2+n*(n-1);
}
2、LELE的RPG难题
有排成一行的ｎ个方格，用红(Red)、粉(Pink)、绿(Green)三色涂每个格子，每格涂一色，要求任何相邻的方格不能同色，且首尾两格也不同色．求全部的满足要求的涂法.
输入示例：3
输出示例：6
解：递归分析：从f(n-1)增加到f(n)分两种情况：（1）一种是直接在所有已经排好了的f(n-1)序列中插入唯一一个第三色有f(n-1)种；（2）另外是在已经排好了的
f(n-2)序列中，插入与缝隙两边其中一个颜色相同的颜色，然后再插入第n个颜色且只需与第n-1种颜色不同有两种，故有2f(n-2)种；
递归关系：f(n)=f(n-1)+2f(n-2)，（n>=2）
//(2)LELE的RPG难题
int countColor(int n)
{
if(n==2)
return 6;
else if(n==3)
return 6;
else
return countColor(n-1)+2*countColor(n-2);
}
3、假设一个有序数组A[0], A[1], …, A[N-1]，编写一个函数int find(int A[], int x)，确定一个整数x是否在数组A中，如果在，则返回其位置，否则返回-1
//有序数组元素查找-二分查找
int find(int A[],int n)
{//sizeof(A)sizeof写进函数得不到数组所占的内存数，而仅是一个指针的内存大小 int length=0;//参数数组长度
for(int i=0;A[i]!=0;i++)
{
length++;
}
int left=0,mid,right=length-1;
while(left<=right)
{
mid=(left+right)/2;
if(n right=mid-1; else if(n>A[mid]) { left=mid+1; } else return mid; } return -1;} 4、假设数组a中的元素是按从小到大顺序排列的，函数find(int a[], int n, int &i, int &j, int x)利用二分搜索法确定x是否在含有n个元素的数组a中，如果不在，则参数i为小于x的最大元素的下标，参数j为大于x的最小元素的下标。如果x 在数组a中，则i与j相等，都为等于x的元素的下标。 //(4)二分查找定位 void find2(int a[],int n,int &i,int &j,int x) { int left=0,mid,right=n-1; while(left<=right) { mid=(left+right)/2; if(x>a[mid]) left=mid+1; else if(x right=mid-1; else { //找到了 i=j=mid; return; } } //没找到 i=right; j=left; } 5、百鸡问题：有一个人有一百块钱，打算买一百只鸡。到市场一看，公鸡三块钱一只，母鸡两块钱一个，小鸡一块钱三只。现在，请你编一程序，帮他计划一下，怎么样买法，才能刚好用一百块钱买一百只鸡？ //(5)百鸡问题-枚举法 void countChicken() { int i,j;double k;//公鸡、母鸡、小鸡 for(i=0;i<=33;i++) for(j=0;j<=50;j++) for(k=0;k<=300;k++) if(3*i+2*j+k/3.0==100) cout<<"公鸡"< "< } 6、水仙花数：水仙花数是指一个3位数，其各位数字的立方和等于它本身。例如：153是水仙花数，因为153=13+53+33。编程求所有的水仙花数。 //(6)三位水仙花数-枚举法 void countdaff() { int l,m,r,temp; for(int i=100;i<=999;i++) { r=i%10;//个位数 temp=i/10; m=temp%10;//十位数 l=i/100;//百位数 if(i==pow(r,3)+pow(m,3)+pow(l,3)) cout< } } 【一般不会考这个】 7、给定一个矩形，在该矩形中有3个固定的点，以这3个点为中心的气球先后膨胀：膨胀时触碰到矩形的边或其他气球时则停止膨胀。编写程序求以何种顺序膨胀气球时，才能使气球的横切面面积之和为最大。 解： （1）以矩形左下角为原点，建立直角坐标系，程序输入的参数为：三个固定点的坐标，矩形的长和宽，输出膨胀顺序； （2）程序对参数的初步处理是算得三点相互之间的距离以及三点分别与矩形的最近距离，然后穷举法列举所有的膨胀顺序，找到使三个圆半径的平方和最小的膨胀顺序； //(7)气球膨胀问题 double min(double a,double b,double c) { double min=a; if(b min=b; if(c min=c; return min; } void sortBall(double width,double height,double xA,double yA,double xB,double yB,double xC,double yC) { //点与点之间的距离 double distance[3]; distance[0]=sqrt(pow((xA-xB),2)+pow((yA-yB),2)); distance[1]=sqrt(pow((xA-xC),2)+pow((yA-yC),2)); distance[2]=sqrt(pow((xC-xB),2)+pow((yC-yB),2)); //点与矩形的最近距离 double minRect[3]; double minA_x=xA>width/2?(width-xA):xA; double minA_y=yA>height/2?(height-yA):yA; minRect[0]=minA_x double minB_x=xB>width/2?(width-xB):xB; double minB_y=yB>height/2?(height-yB):yB; minRect[1]=minB_x double minC_x=xC>width/2?(width-xC):xC; double minC_y=yC>height/2?(height-yC):yC; minRect[2]=minC_x int relative[3][2]={0,1,0,2,1,2}; bool stat[3]={true,true,true};//初始化三个气球状态都未膨胀 int array[3];//临时顺序 int terarray[3];//气球膨胀最终顺序 double rad[3];//膨胀后的气球半径 double powrad2=0;//半径平方和 //开始穷举 for(int i=0;i<3;i++) {//第一个膨胀的气球 stat[i]=false; rad[i]=min(minRect[i],distance[relative[i][0]],distance[relative[i][ 1]]);//第一个膨胀的气球的半径 distance[relative[i][0]]-=rad[i]; distance[relative[i][1]]-=rad[i]; array[0]=i+1;//第一个膨胀的气球编号 for(int j=0;j<3;j++) {//第二个膨胀的气球 if(stat[j]) { stat[j]=false; rad[j]=min(minRect[j],distance[relative[j][0]],distance[relative[j][ 1]]);//第二个膨胀的气球的半径 distance[relative[j][0]]-=rad[j]; distance[relative[j][1]]-=rad[j]; array[1]=j+1;//第二个膨胀的气球编号 for(int k=0;k<3;k++) {//第三个膨胀的气球 if(stat[k]) { rad[k]=min(minRect[k],distance[relative[k][0]],distance[relative[k][ 1]]);//第三个膨胀的气球的半径 array[2]=k+1;//第三个膨胀的气球编号 if((pow(rad[0],2)+pow(rad[1],2)+pow(rad[2],2))>powrad2) { powrad2=(pow(rad[0],2)+pow(rad[1],2)+pow(rad[2],2)); terarray[0]=array[0]; terarray[1]=array[1]; terarray[2]=array[2]; } cout< cout< cout< cout<<"-------------------"< } }//第三个膨胀的气球 //恢复第二个气球初始状态 //点与点之间的距离 distance[relative[j][0]]+=rad[j]; distance[relative[j][1]]+=rad[j]; stat[j]=true;//恢复第二个气球状态都未膨胀 } }//第二个膨胀的气球 //恢复初始状态 //点与点之间的距离 distance[0]=sqrt(pow(xA-xB,2)+pow(yA-yB,2)); distance[1]=sqrt(pow(xA-xC,2)+pow(yA-yC,2)); distance[2]=sqrt(pow(xC-xB,2)+pow(yC-yB,2)); stat[0]=true;//恢复三个气球状态都未膨胀 stat[1]=true; stat[2]=true; }//第一个膨胀的气球 cout<<"最佳膨胀顺序为："< "< } Problem Description Calculate A + B. Input Each line will contain two integers A and B. Process to end of file. Output For each case, output A + B in one line. Sample Input 1 1 Sample Output 2 #include 1001 #include Input The first line of the input contains an integer T(1<=T<=20) which means the number of test cases. Then T lines follow, each line consists of two positive integers, A and B. Notice that the integers are very large, that means you should not process them by using 32-bit integer. You may assume the length of each integer will not exceed 1000. Output For each test case, you should output two lines. The first line is "Case #:", # means the number of the test case. The second line is the an equation "A + B = Sum", Sum means the result of A + B. Note there are some spaces int the equation. Output a blank line between two test cases. Sample Input 2 1 2 112233445566778899 998877665544332211 Sample Output Case 1: 1 + 2 = 3 Case 2: 112233445566778899 + 998877665544332211 = 1111111111111111110 Author Ignatius.L #include 自己刷的题 这是我在杭电做题的记录，希望我的分享对你有帮助！！！ 1001 Sum Problem***********************************************************1 1089 A+B for Input-Output Practice (I)********************************2 1090 A+B for Input-Output Practice (II)********************************5 1091A+B for Input-Output Practice (III)****************************************7 1092A+B for Input-Output Practice (IV)********************************8 1093 A+B for Input-Output Practice (V)********************************10 1094 A+B for Input-Output Practice (VI)***************************************12 1095A+B for Input-Output Practice (VII)*******************************13 1096 A+B for Input-Output Practice (VIII)******************************15 How to Type***************************************************************16 1001 Sum Problem Problem Description Hey, welcome to HDOJ(Hangzhou Dianzi University Online Judge). In this problem, your task is to calculate SUM(n) = 1 + 2 + 3 + ... + n. Input The input will consist of a series of integers n, one integer per line. Output For each case, output SUM(n) in one line, followed by a blank line. You may assume the result will be in the range of 32-bit signed integer. 1111111杭电： 1000 A + B Problem (4) 1001 Sum Problem (5) 1002 A + B Problem II (6) 1005 Number Sequence (8) 1008 Elevator (9) 1009 FatMouse' Trade (11) 1021 Fibonacci Again (13) 1089 A+B for Input-Output Practice (I) (14) 1090 A+B for Input-Output Practice (II) (15) 1091 A+B for Input-Output Practice (III) (16) 1092 A+B for Input-Output Practice (IV) (17) 1093 A+B for Input-Output Practice (V) (18) 1094 A+B for Input-Output Practice (VI) (20) 1095 A+B for Input-Output Practice (VII) (21) 1096 A+B for Input-Output Practice (VIII) (22) 1176 免费馅饼 (23) 1204 糖果大战 (25) 1213 How Many Tables (26) 2000 ASCII码排序 (32) 2001 计算两点间的距离 (34) 2002 计算球体积 (35) 2003 求绝对值 (36) 2004 成绩转换 (37) 2005 第几天？ (38) 2006 求奇数的乘积 (40) 2007 平方和与立方和 (41) 2008 数值统计 (42) 2009 求数列的和 (43) 2010 水仙花数 (44) 2011 多项式求和 (46) 2012 素数判定 (47) 2014 青年歌手大奖赛_评委会打分 (49) 2015 偶数求和 (50) 2016 数据的交换输出 (52) 2017 字符串统计 (54) 2019 数列有序! (55) 2020 绝对值排序 (56) 2021 发工资咯：） (58) 2033 人见人爱A+B (59) 2037 今年暑假不AC (61) 2039 三角形 (63) 2040 亲和数 (64) 杭电ACM试题分类 枚举 1002 10041013 1015 1017 1020 1022 1029 1031 1033 1034 1035 1036 1037 1039 1042 10471048 1049 1050 1057 1062 1063 1064 1070 1073 1075 1082 1083 1084 1088 11061107 1113 1117 1119 1128 1129 1144 1148 1157 1161 1170 1172 1177 11971200 1201 1202 1205 1209 1212（大数取模）1216 （链表）1218 1219 1225 1228 12291230 1234 1235 1236 1237 1239 1250 1256 1259 1262 1263 1265 1266 1276 1279 1282 1283 1287 1296 1302 1303 1304 1305 1306 1309 1311 1314 搜索，递归求解 1010 1016 1026 1043（双广）1044 （BFS+DFS） 1045 1067 1072 1104 1175 1180 1195 1208 1226 1238 1240 1241 1242 1258 1271 1312 1317 动态规划 1003 1024 1025 1028 1051 1058 1059 1069 1074 1078 1080 1081 1085 1087 1114 1158 1159 1160 1171 1176 1181 1203 1224 1227 1231 1244 1248 1253 1254 1283 1300 数学，递推，规律 1005 1006 1012 1014 1018 1019 1021 1023 1027 1030 1032 1038 1041 1046 1059 1060 1061 1065 1066 1071（微积分）1097 1098 1099 1100 1108 1110 1112 1124 1130 1131 1132 1134 1141 1143 1152 1155（物理题）1163 1165 1178 1194 1196（lowbit） 1210 1214 1200 1221 1223 1249 1261 1267 1273 1290 1291 1292 1294 1297 1313 1316 数论 1164 1211 1215 1222 1286 1299 计算几何 1086 1115 1147 每个ACMer平时都是靠做题来训练的，现在就以杭州电子科技大学的OJ为例简单介绍一下如何使用OJ系统，在浏览器上输入杭电的网址https://www.sodocs.net/doc/d312463468.html, 首先，我们需要注册一个ID，点击Register new ID 填写好自己的个人信息之后，点击submit，就可以完成注册了，然后在主页右上角的登陆框输入ID，密码便可以登陆，这个时候点击主页上的 Problem Archive 打开OJ的题库 点击题号为 1000 的题目 A + B Problem Problem Description 一栏写的就是题目的描述，很多初学者一开始对全英文的题目会很不习惯，这是很正常的，多查查字典，很快就可以习惯了，而且也可以提高自己的英语阅读水平 Input 一栏写的是题目的输入要求，这里提示：每行将会有两个整数 A 和 B，输入进程一直延续到文件读完而结束（也就是要循环输入） Output 一栏写的是题目的输出要求，这里提示：对于每组数据，在一行中输入A+B的 值 接下来的 Sample Input 就是示例输入数据，而 Sample Output 就是相应的输出结果在读完题目之后，我们就可以在自己电脑上的编译器上编写代码，等编写好代码之后，点击页面中的Submit，接着把代码复制上去，再选择相应的语言 完成之后点击Submit，就可以看到OJ系统对我们的程序的判题结果了 这里返回了一个 Accepted，也就是说通过了OJ的判断，题目答对了！ 而OJ可能会返回的结果总共有： Accepted 通过 Wrong Answer 错误 Compilation Error 编译错误 Runtime Error 运行错误 Time Limit Exceeded 时间超出限制 Presentation Error 输出格式错误 Memory Limit Exceeded 内存超出限制 Output Limit Exceeded 输出了多余的东西 ACM入门（杭电oj） Hdu 1000 #include a[j]=a[j]+str2[i]-'0'; a[j+1]=a[j+1]+a[j]/10; a[j]=a[j]%10; } count++; printf("Case %d:\n",count); printf("%s + %s = ",str1,str2); int flag=0; for(i=1004;i>=0;i--) if(flag||a[i]) { printf("%d",a[i]); flag=1; } printf("\n"); if(ca!=0) printf("\n"); } } Hdu 1003 #include 【杭电ACM1000】 A + B Problem Problem Description Calculate A + B. Input Each line will contain two integers A and B. Process to end of file. Output For each case, output A + B in one line. Sample Input 1 1 Sample Output 2 # include Input The input will consist of a series of integers n, one integer per line. Output For each case, output SUM(n) in one line, followed by a blank line. You may assume the result will be in the range of 32-bit signed integer. Sample Input 1 100 Sample Output 1 5050 # include ACM部分习题答案： A + B Problem Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 100972 Accepted Submission(s): 33404 Problem Description Calculate A + B. Input Each line will contain two integers A and B. Process to end of file. Output For each case, output A + B in one line. Sample Input 1 1 Sample Output 2 # include 1000A + B Problem Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 158161 Accepted Submission(s): 50186 Problem Description Calculate A + B. Input Each line will contain two integers A and B. Process to end of file. Output For each case, output A + B in one line. Sample Input 1 1 Sample Output 2 Author HDOJ Statistic | Submit | Discuss | Note #include 1002A + B Problem II Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 84367 Accepted Submission(s): 15966 Problem Description I have a very simple problem for you. Given two integers A and B, your job is to calculate the Sum of A + B. Input The first line of the input contains an integer T(1<=T<=20) which means the number of test cases. Then T lines follow, each line consists of two positive integers, A and B. Notice that the integers are very large, that means you should not process them by using 32-bit integer. You may assume the length of each integer will not exceed 1000. Output For each test case, you should output two lines. The first line is "Case #:", # means the number of the test case. The second line is the an equation "A + B = Sum", Sum means the result of A + B. Note there are some spaces int the equation. Output a blank line between two test cases. Sample Input 2 1 2 112233445566778899 998877665544332211 Sample Output Case 1: 1 + 2 = 3 Case 2: 112233445566778899 + 998877665544332211 = 1111111111111111110 Author Ignatius.L Statistic | Submit | Discuss | Note hdu博弈，这些题都不难。 属于博弈简单题。 hdu1846巴什博弈，n%(m+1)==0先手必败。 #include #include 1. Problem Description 输入三个字符后，按各字符的ASCII码从小到大的顺序输出这三个字符。 Input 输入数据有多组，每组占一行，有三个字符组成，之间无空格。 Output 对于每组输入数据，输出一行，字符中间用一个空格分开。 Sample Input qwe asd zxc Sample Output e q w a d s c x z 方案： #include } } printf("%c %c %c\n",str[0],str[1],str[2]); } } 2. Problem Description 输入两点坐标（X1,Y1）,（X2,Y2）,计算并输出两点间的距离。 Input 输入数据有多组，每组占一行，由4个实数组成，分别表示x1,y1,x2,y2,数据之间用空格隔开。 Output 对于每组输入数据，输出一行，结果保留两位小数。 Sample Input 0 0 0 1 0 1 1 0 Sample Output 1.00 1.41 答案： #include 选修课考试作业 1001 Sum Problem ............................................................................................ 错误!未定义书签。1089 A+B for Input-Output Practice (I) .......................................................... 错误!未定义书签。1090 A+B for Input-Output Practice (II) ......................................................... 错误!未定义书签。1091 A+B for Input-Output Practice (III) ........................................................ 错误!未定义书签。1092 A+B for Input-Output Practice (IV) ........................................................... 错误!未定义书签。1093 A+B for Input-Output Practice (V) ......................................................... 错误!未定义书签。1094 A+B for Input-Output Practice (VI) ........................................................ 错误!未定义书签。1095 A+B for Input-Output Practice (VII) .......................................................... 错误!未定义书签。1096 A+B for Input-Output Practice (VIII) ...................................................... 错误!未定义书签。' 2000 ASCII码排序 ............................................................................................ 错误!未定义书签。2001计算两点间的距离.................................................................................. 错误!未定义书签。2002计算球体积 ............................................................................................. 错误!未定义书签。2003求绝对值 ................................................................................................. 错误!未定义书签。2004成绩转换 ................................................................................................. 错误!未定义书签。2005第几天 ..................................................................................................... 错误!未定义书签。2006求奇数的乘积 ......................................................................................... 错误!未定义书签。2007平方和与立方和...................................................................................... 错误!未定义书签。2008数值统计 ................................................................................................. 错误!未定义书签。2009求数列的和 ............................................................................................. 错误!未定义书签。~ 2010水仙花数 ................................................................................................. 错误!未定义书签。2011多项式求和 ............................................................................................. 错误!未定义书签。2012素数判定 ................................................................................................. 错误!未定义书签。2014青年歌手大奖赛_评委会打分................................................................ 错误!未定义书签。2015偶数求和 ................................................................................................. 错误!未定义书签。2016数据的交换输出...................................................................................... 错误!未定义书签。2017字符串统计 ............................................................................................. 错误!未定义书签。2019数列有序! ................................................................................................ 错误!未定义书签。2020绝对值排序.............................................................................................. 错误!未定义书签。2021发工资咯：）............................................................................................ 错误!未定义书签。: 2033人见人爱A+B .......................................................................................... 错误!未定义书签。2039三角形 ..................................................................................................... 错误!未定义书签。2040亲和数 ..................................................................................................... 错误!未定义书签。 姓名：郑春杰 班级：电商1001 杭电acm 1001这个就不用说了吧 1002简单的大数 1003DP经典问题，最大连续子段和 1004简单题 1005找规律（循环点） 1006感觉有点BT的题，我到现在还没过 1007经典问题，最近点对问题，用分治 1008简单题 1009贪心 1010搜索题，剪枝很关键 1011 1012简单题 1013简单题（有个小陷阱） 1014简单题 1015可以看作搜索题吧 1016经典的搜索 1017简单数学题 1018简单数学题 1019简单数学题 1020简单的字符串处理 1021找规律的数学题 1022数据结构的题（栈的应用） 1023特殊的数（CatalanNumber） 1024经典DP，最大M子段和 1025经典DP，最长递增子序列（要用NLogN的方法过）1026搜索 1027数学题（或用STL） 1028经典问题，整数拆分，用母函数做 1029简单题（一般方法容易超时） 1030简单题，可用模拟过 1031简单题 1032简单题 1033模拟题 1034CandySharingGame 1035模拟题 1036简单题 1037简单题，不是一般的简单 1038简单题 1039字符串处理 1040简单题，排序 1041简单题，用大数 1042大数 1043经典搜索题，八数码问题 1044稍微有点麻烦的搜索题 1045搜索题，可用匹配做 1046简单题 1047简单的大数 1048简单字符串处理 1049简单题 1050贪心 1051经典贪心，也可以用DP 1052贪心 1053贪心，关于Huffman编码 1054二分匹配 1055二分匹配 1056简单题 1057模拟题 1058经典问题，丑数，DP 1059经典问题，可以用母函数或DP（不针对题目优化都会超时）1060数学题 1061数学题 1062简单字符串处理 1063模拟大数 1064简单题 1065简单题 1066数学题，找规律 1067 1068经典二分匹配 1069经典DP 1070简单题 1071简单数学题 1072搜索 1073字符串处理 1074DP 1075字典树 1076简单题 1077 1078DP 1079博弈（DP） 1080DP 1081经典DP 1082简单题 1083二分匹配 1084简单题 1085母函数 1086简单几何题 1087简单DP(完整版)杭电acm部分答案
杭电ACM水题题目及代码
杭电acm部分题目及答案答案
整理出ACM所有题目及答案
杭电ACM试题详细分类,杭电oj详细分类,hdu详细分类,详细,ACM.doc
杭电OJ使用介绍
ACM入门十题(杭电oj)
完整word版杭电ACM试题答案
ACM部分练习题目答案
杭电ACM部分题答案
杭电ACM博弈题合集
杭电ACM2000-2019
杭电题目acm答案
杭电acm