《挑战程序设计竞赛》学习笔记（18.07.30-）

《挑战程序设计竞赛》全书共116个问题，不求速度，只求质量，认认真真地学❤

18.07.30

000.抽签
       你的朋友建议玩一个游戏：将写有数字的 n 个纸片放入口袋中,你可以从口袋中抽取4次纸片，每次记下纸片上的数字后都将其放回口袋中。如果这4个数字的和是 m ，就是你赢，否则就是你朋友赢。你挑战了好几回，结果一次也没赢过，于是怒而撕破口袋，取出所有纸片，检查自己是否有赢的可能性。请你编程写一个程序，判断当纸片上所写的数字是k₁，k₂，k₃……k_n时，是否存在抽取4次和为m的方案。如果存在，输出Yes；否则输出No。
限制条件
1 ≤ n ≤50
1 ≤ m ≤10⁸
1 ≤ ki ≤10⁸

#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 ≤ 10⁶

#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
线段上格点的个数
...
未完待续