c++竞赛题目

78 阅读 0 评论 52 点赞

我是靠谱客的博主陶醉电脑，最近开发中收集的这篇文章主要介绍c++竞赛题目，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

一、极值问题(acme)

【问题描述】

已知 m、n 为整数，且满足下列两个条件：

① m、n∈{１，２，…，k}，即 1≤m，n≤k

②(n² - m*n - m²)²＝1

你的任务是：编程输入正整数k（1≤k≤109），求一组满足上述两个条件的m、n，并且使m2＋n2

的值最大。例如，从键盘输入k=1995，则输出：m=987 n=1597。

【输入样例】

1995

【输出样例】

m=987

n=1597

【解析】

∵ 原式 = 1

又∵m² +m*n - n² = (m+n)² - m* n - 2n² = (m+n)² - n*(m+n) - n²

且 |n² - m*n - m²| = | m² +m*n - n²|

∴ (n² - m*n - m²)² = ((m+n)² - n*(m+n) - n²)²

得到结论：n -> m+n, m -> n;

又∵ 当 n = 1， m = 0时 (n² - m*n - m²)² = 1；

即当m 与 n 符合斐波那契数列即可满足公式

所以只需求k下最大的两个斐波那契数的值即可。

#include<iostream>
using namespace std;
int main()
{
int k, i = 2;
cin >> k;
int *number = new int[k]();
number[0] = 0;
number[1] = 1;
number[2] = 1;
if(k == 1)
{
i = 2;
}
else
while (number[i] <= k)
{
i++;
number[i] = number[i-1] + number[i-2];
}
cout << "m=" << number[i-2]<<endl;
cout << "n=" << number[i-1]<<endl;
return 0;
}

二、简单背包问题

【问题描述】简单的背包问题。设有一个背包，可以放入的重量为 s。现有 n 件物品，重量分别为 w1,w2…，wn，（1≤i≤n）均为正整数，从 n 件物品中挑选若干件，使得放入背包的重量之和正好为 s。找到一组解即可。

【输入格式】第一行是物品总件数和背包的载重量，第二行为各物品的重量。

【输出格式】各所选物品的序号和重量。（按序号递增次序，所选物品个数越少越好，多组解输出字典序最小的）

【输入样例】

5 10

1 2 3 4 5

【输出样例】

number:1 weight:1

number:4 weight:4

number:5 weight:5

#include <iostream>
using namespace std;
int recursion(int s, int n,int weight[])
{
if(s==0)//如果背包满了，返回1
return 1;
if(s<0||(s>0&&n<1))//如果背包重量大于s或者待放入的物品没了
return 0;
if(recursion(s-weight[n-1],n-1,weight))
{
cout<<n<<weight[n-1]<<endl;
return 1;
}
else
return recursion(s,n-1,weight);
}
int main()
{
int s;//背包可承受重量
int n;//物件总数
cin >> n >> s;
int *weight = new int[n]();
for(int i = 0; i < n; i++)
{
cin >> weight[i];
}
if(!recursion( s, n, weight))cout << "not found";
return 0;
}

三、总结

要多多观察题目，找到规律才能更好的解答题目。

记住

if(recursion(s-weight[n-1],n-1,weight))
   {
       return 1;
   }
   else
       return recursion(s,n-1,weight);

对于需要同时求下标及总和的题目且数据是无序时的题目，能更好的求解