《挑战程序设计竞赛》全书共116个问题，不求速度，只求质量，认认真真地学❤
18.07.30
000.抽签
你的朋友建议玩一个游戏：将写有数字的 n 个纸片放入口袋中,你可以从口袋中抽取4次纸片，每次记下纸片上的数字后都将其放回口袋中。如果这4个数字的和是 m ，就是你赢，否则就是你朋友赢。你挑战了好几回，结果一次也没赢过，于是怒而撕破口袋，取出所有纸片，检查自己是否有赢的可能性。请你编程写一个程序，判断当纸片上所写的数字是k1，k2，k3……kn时，是否存在抽取4次和为m的方案。如果存在，输出Yes；否则输出No。
限制条件
1 ≤ n ≤50
1 ≤ m ≤108
1 ≤ ki ≤108
#include<cstdio>
const int Max_N = 50;
int main()
{
int m, n, k[Max_N];
int i;
scanf("%d %d", &n, &m);
for (i = 0; i < n; i++)
{
scanf("%d", &k[i]);
}
bool f = false;
for (int a = 0; a < n; a++)
{
for (int b = 0; b < n; b++)
{
for (int c = 0; c < n; c++)
{
for (int d = 0; d < n; d++)
{
if (k[a] + k[b] + k[c] + k[d] == m)
{
f = true;
}
}
}
}
}
if (f)
puts("Yes");
else
puts("No");
return 0;
}
int n,m,k[MAX];
int kk[MAX*MAX];
bool binary_search(int x){
int l=0,r=n*n;
while(r-l>=l){
int i=(l+r)/2;
if(kk[i]==x) return true;
else if(kk[i]<x) l=i+1;
else r=i;
}
return false;
}
viod solve(){
for(int c=0; c<n; c++){
for(int d=0; d<n; d++){
kk[c*n+d]=k[c]+k[d];
}
}
sort(kk,kk+n*n);
bool f=false;
for(int a=0; a<n; a++){
for(int b=0; b<n; b++){
if(binary_search(m-k[a]-k[b])){
f=true;
}
}
}
if(f) puts("Yes");
else puts("No");
}
001.三角形
有n根棍子，棍子i的长度为ai。想要从中选出三根棍子组成周长尽可能长的三角形。请输出最大的周长，若无法组成三角形则输出0。
限制条件
3 ≤ n ≤ 100
1 ≤ ai ≤ 106
#include<stdio.h>
int MAX(int a,int b)
{
return a > b ? a : b;
}
int main()
{
int a[10];
int i,j,k,n;
scanf("%d",&n);
for(i = 0; i < n; i++){
scanf("%d",&a[i]);
}
int ans = 0;
for(i = 0 ;i < n;i ++){
for(j = i + 1;j < n;j ++){
for(k = j + 1;k < n;k ++){
int l = a[i] + a[j] + a[k];
int max = MAX(a[i],MAX(a[j],a[k]));
int rest = l - max;
if(rest > max){
ans = MAX(ans,l);
}
}
}
}
printf("%d\n",ans);
return 0;
}
002.Ants
n只蚂蚁以每秒1cm的速度在长为Lcm的竿子上爬行。当蚂蚁爬到竿子的端点时就会掉落。由于竿子太细，两只蚂蚁相遇时，他们不能交错通过，只能各自反向爬回去。对于每只蚂蚁，我们知道它距离竿子左端的距离为Xi，但不知道它当前的朝向，请计算所有蚂蚁落下竿子所需的最短时间和最长时间。
限制条件
1<=L<=10^6
1<=n<=10^6
0<=Xi<=L
#include<iostream>
#include<cstdlib>
#include<algorithm>
using namespace std;
int main()
{
int L,n;
double pos;
cin>>L>>n;
double minT=0,maxT=0;
for(int i=0;i<n;i++)
{
cin>>pos;
double temp=min(pos,L-pos);
minT=max(minT,temp);
temp=max(pos,L-pos);
maxT=max(maxT,temp);
}
cout<<"min="<<minT<<endl;
cout<<"max="<<maxT<<endl;
return 0;
}
部分和问题
给定整数a1、a2、.......an，判断是否可以从中选出若干数，使它们的和恰好为K。
#include<cstdio>
#include<iostream>
using namespace std;
int n,k,a[22],b[22];
bool dfs(int x,int sum)
if(sum>k) return false;
if(x==n)
return sum==k;
if(dfs(x+1,sum)){
b[x]=0;
return true;
}
if(dfs(x+1,sum+a[x])){
b[x]=1;
return true;
}
return false;
}
int main(){
cin>>n;
for(int i = 0;i<n; i++)
scanf("%d",&a[i]);
cin>>k;
if(dfs(0,0)){
printf("YES\n");
for(int i=0;i<n;i++)
if(b[i])printf("%d ",a[i]);
printf("\n");
}
}
Lake Counting
迷宫的最短路径
硬币问题
区间调度问题
Best Cow Line
Saruman‘s Army
Fence Repair
01背包问题
最长公共子序列问题
完全背包问题
01背包问题之2
多重部分和问题
最长上升子序列问题
划分数
多重集组合数
Expedition
食物链
二分图判定
Roadblocks
Conscription
Layout
线段上格点的个数
...
未完待续
