解法一:
#include
#include
#include
#include
#include
using namespace std;
typedef __int64 ll;
typedef pair
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define sz(x) ((int)(x).size())
#define all(x) (x).begin(),(x).end()
#define de(x) cout << #x << " = " << x << endl
//-------
const int N = 200007;
int n, q, a[N], nxt[N];
int main() {
scanf("%d%d", &n, &q);
int i;
for (i = 1; i <= n; ++i)
scanf("%d", a + i);
nxt[n] = n + 1;
for (i = n - 1; i > 0; --i)
nxt[i] = (a[i] == a[i + 1] ? nxt[i + 1] : i + 1);
for (i = 0; i < q; ++i) {
int L, R, x;
scanf("%d%d%d", &L, &R, &x);
if (a[L] != x) {
printf("%d\n", L);
} else {
printf("%d\n", nxt[L] <= R ? nxt[L] : -1);
}
}
return 0;
}
解法二:
#include
#include
#include
#include
using namespace std;
const int maxn=200000+10;
int arr[maxn],nxt[maxn];
int main() {
int n,q,i,j,k;
scanf("%d%d",&n,&q);
for(i=1;i<=n;i++) scanf("%d",arr+i);
arr[++n]=-1;
for(i=1;i for(j=i+1;j<=n&&arr[j]==arr[i];j++); for(k=i;k i=j-1; } int l,r,x; while(q--){ scanf("%d%d%d",&l,&r,&x); if(arr[l]!=x) printf("%d\n",l); else if(nxt[l]<=r) printf("%d\n",nxt[l]); else printf("-1\n"); } return 0; } #include #include using namespace std; /*input:weights-权值数组,weightsSize-权值数组的长度,wayCount-树的分支数k output:耗费的总体力值*/ int buildHuffmanTree(int weights[],int weightsSize,const int wayCount){ int totalCost=0;//耗费的总体力 priority_queue //把所有节点全部加入最小堆中 for(int i=0;i pq.push(weights[i]); } while(pq.size() > 1){ int internalNodeWeight=0;//新建内节点的权值 for(int i=0;i int minNodeWeight=pq.top();pq.pop(); internalNodeWeight+=minNodeWeight; } pq.push(internalNodeWeight);//把新建内节点加入最小堆 totalCost+=internalNodeWeight; } return totalCost; } int main() { int n;//n个初始叶节点(n个箱子) int k;//k叉树(最多把k个箱子绑在一起) cin>>n>>k; //.判断是否需要补0,并计算补0个数 int m=(n-1)%(k-1); int extraZeroCount;//补0的个数 if(0==m){ extraZeroCount=0; }else{ extraZeroCount=k-m-1; } //.创建weights数组 int weightsSize=n+extraZeroCount; int* weights=new int[weightsSize];//各个叶节点的权值 for(int i=0;i cin>>weights[i]; } //补0 for(int j=0;j weights[n+j]=0; } //.构建Huffman树,计算耗费总体力的最小值 int totalCost=buildHuffmanTree(weights,weightsSize,k); cout< return 0; } #include #include int n,L,R; int data[31]; int cmp(const void *a, const void *b) { return *(int*)a - *(int*)b; } void out(int num) { printf("{"); bool isfirst = true; int i; for (i = n-1; i >= 0; i--) { if (num & (1< //printf("pos:%d ", i); if (isfirst) { printf("%d", data[i]); isfirst = false; } else printf(",%d",data[i]); } } printf("}\n"); } int main() { int i; scanf("%d", &n); for (i = 0; i < n; i++) scanf("%d", data + i); scanf("%d %d", &L, &R); qsort(data, n, sizeof(int), cmp); //for (int i = 0; i < n; i++) // printf("%d\n", data[i]); for (i = L - 1; i < R; i++) out(i); //system("pause"); return 0; } /* 3 3 4 1 1 5 */ #include #include const int N = 16; int n,V,x[N + N],i,j,l,r; int a[1 << N],b[1 << N],lg2[1 << N]; void bruteforce(int *a,int *x,int n){ for(i=1;i<(1< a[i]=a[i&(i-1)]+x[lg2[i&(-i)]]; if(a[i] > V) a[i] = V + 1; } std::sort(a,a+(1< } int main(){ scanf("%d%d",&n,&V); for(i=0;i<16;++i) lg2[1< for(i=0;i l=n>>1,r=n-l; bruteforce(a,x,l); bruteforce(b,x+l,r); int ans=V; for(i=0,j=(1< for(;~j&&a[i]+b[j]>V;--j); if(~j&&(V-a[i]-b[j]) ans=V-a[i]-b[j]; } printf("%d\n",ans); return 0; } 解法一: #include std::bitset int main(){ scanf("%d%d",&n,&V); f[0]=1; for(i=0;i scanf("%d",&x); f |= f << x; } for(i=V;i>=0;--i) if(f[i]){ printf("%d\n",V-i); break; } return 0; } 解法二: #include using namespace std; inline int max(int x, int y) { return x > y ? x : y; } int w[100]; int m[10001]; int main() { int n, v; int i; cin >> n >> v; for (i = 0; i < n; i++) cin >> w[i]; for (i = 0; i <= v; i++) m[i] = 0; /* * 对于第i轮循环 * 求出了前i个物品中当容量为v的最大体积组合 */ for (i = 0; i < n; i++) { /* * 内循环实际上讲m[0...v]滚动覆盖前一轮的m[0...V] * j从V至0逆序是防止有的物品放入车中多次 */ for (int j = v; j >= w[i]; j--) { m[j] = max(m[j], m[j - w[i]] + w[i]); } } cout << v - m[v]; return 0; } 《ACM算法与数据结构设计》课程大作业报告 题目:五位以内的对称素数 学生姓名 班级学号 学生学院计算机软件学院 学生专业计算机科学与技术 联系电话 电子邮 指导教师 指导单位计算机学院软件工程系 日期2011.5.24 注意事项 (1)课程大作业从《ACM算法与数据结构设计》课程实验二(2011年4月19日)或实验三(2011年5月10日)中任选一个课题完成。(2)课程大作业内容包括课题名称、课题内容和要求、课题分析、概要设计、详细设计、测试数据及其结果分析、调试过程中的问题、参考资料列表、课程小结等。 (3)课程报告可以打印,也可以手写,但前面两页内容、大作业撰写纲要、课程小结不可遗漏和更换。 (4)课程小结给出ACM程序设计过程的收获、遇到的问题,遇到问题解决问题过程的思考、程序调试能力的思考等,需要手写签字。(5)课程大作业提交时间为2011年5月24日(第14周星期二)晚19:00~20:00,地点:计算中心A机房。 一、课题名称: 五位以内的对称素数 二、课题内容和要求: 题目:判断一个数是否为对称且不大于五位数的素数。 要求:判断输入的一组数据(正整数)是否是五位以内的对称素数,逐个判断并输出“yes”或“no” 三、课题分析: 定义两个函数分别判断数据是否为素数(bool isprime(int n)),是否是对称数(bool issym(int n));在main()函数中利用if()语句来判断该数据是否是五位以内的数。只有同时满足三个条件,才能判断一个数据是五位以内的对称素数,输出“yes”;否则输出“no”。 输入输出方案: 输入: 输入数据含有不多于50个的正整数(0 习题1 1. 图论诞生于七桥问题。出生于瑞士的伟大数学家欧拉(Leonhard Euler ,1707—1783)提出并解决了该问题。七桥问题是这样描述的:一个人是否能在一次步行中穿越哥尼斯堡(现 在叫加里宁格勒,在波罗的海南岸)城中全部的七座桥后回到起点,且每座桥只经过一次, 图是这条河以及河上的两个岛和七座桥的草 图。请将该问题的数据模型抽象出来,并判断此问题是否有解。 七桥问题属于一笔画问题。 输入:一个起点 输出:相同的点 1, 一次步行 2, 经过七座桥,且每次只经历过一次 3, 回到起点 该问题无解:能一笔画的图形只有两类:一类是所有的点都是偶点。另一类是只有二个奇点的图形。 2.在欧几里德提出的欧几里德算法中(即最初的欧几里德算法)用的不是除法而是减法。请用伪代码描述这个版本的欧几里德算法 =m-n 2.循环直到r=0 m=n n=r r=m-n 3 输出m 3.设计算法求数组中相差最小的两个元素(称为最接近数)的差。要求分别给出伪代码和C++描述。 编写程序,求n 至少为多大时,n 个“1”组成的整数能被2013整除。 #include for(int n=1;n<=10000 ;++n) { value=value*10+1; if(value%2013==0) { cout<<"n至少为:"< 算法设计与分析(第二版)主编:吕国英 习题答案 第四章 1. #include for(i=1;i<=9;i++) { n=(n+2)*2; } printf("%d\n",n); return 0; } 3. #include 习题 1 1.图论诞生于七桥问题。出生于瑞士的伟大数学家欧拉(Leonhard Euler ,1707— 1783) 提出并解决了该问题。七桥问题是这样描述的:北区 一个人是否能在一次步行中穿越哥尼斯堡(现 东区在叫加里宁格勒,在波罗的海南岸)城中全部岛区 的七座桥后回到起点,且每座桥只经过一次, 图是这条河以及河上的两个岛和七座桥的草南区 图。请将该问题的数据模型抽象出来,并判断图七桥问题 此问题是否有解。 七桥问题属于一笔画问题。 输入:一个起点 输出:相同的点 1,一次步行 2,经过七座桥,且每次只经历过一次 3,回到起点 该问题无解:能一笔画的图形只有两类:一类是所有的点都是偶点。另一类是只有二个 奇点的图形。 2.在欧几里德提出的欧几里德算法中(即最初的欧几里德算法)用的不是除法而是减法。请用伪代码描述这个版本的欧几里德算法 =m-n 2.循环直到 r=0 m=n n=r r=m-n 3输出 m 3.设计算法求数组中相差最小的两个元素(称为最接近数)的差。要求分别给出伪代 码和 C++描述。 编写程序,求 n 至少为多大时, n 个“1”组成的整数能被2013 整除。 #include for(int n=1;n<=10000 ;++n) { value=value*10+1; if(value%2013==0) { cout<<"n 至少为 :"< 第一章作业 1.证明下列Ο、Ω和Θ的性质 1)f=Ο(g)当且仅当g=Ω(f) 证明:充分性。若f=Ο(g),则必然存在常数c1>0和n0,使得?n≥n0,有f≤c1*g(n)。由于c1≠0,故g(n) ≥ 1/ c1 *f(n),故g=Ω(f)。 必要性。同理,若g=Ω(f),则必然存在c2>0和n0,使得?n≥n0,有g(n) ≥ c2 *f(n).由于c2≠0,故f(n) ≤ 1/ c2*f(n),故f=Ο(g)。 2)若f=Θ(g)则g=Θ(f) 证明:若f=Θ(g),则必然存在常数c1>0,c2>0和n0,使得?n≥n0,有c1*g(n) ≤f(n) ≤ c2*g(n)。由于c1≠0,c2≠0,f(n) ≥c1*g(n)可得g(n) ≤ 1/c1*f(n),同时,f(n) ≤c2*g(n),有g(n) ≥ 1/c2*f(n),即1/c2*f(n) ≤g(n) ≤ 1/c1*f(n),故g=Θ(f)。 3)Ο(f+g)= Ο(max(f,g)),对于Ω和Θ同样成立。 证明:设F(n)= Ο(f+g),则存在c1>0,和n1,使得?n≥n1,有 F(n) ≤ c1 (f(n)+g(n)) = c1 f(n) + c1g(n) ≤ c1*max{f,g}+ c1*max{f,g} =2 c1*max{f,g} 所以,F(n)=Ο(max(f,g)),即Ο(f+g)= Ο(max(f,g)) 对于Ω和Θ同理证明可以成立。 4)log(n!)= Θ(nlogn)《ACM算法与数据结构设计》大作业
算法设计与分析习题答案1-6章
算法设计与分析 吕国英 习题答案第四章
算法设计与分析习题答案1-6章.docx
算法设计与分析习题解答