美文网首页
《挑战程序设计竞赛》学习笔记(18.07.30-)

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

作者: chouette | 来源:发表于2018-07-30 17:56 被阅读0次

《挑战程序设计竞赛》全书共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
线段上格点的个数
...
未完待续


相关文章

  • 《挑战程序设计竞赛》学习笔记(18.07.30-)

    《挑战程序设计竞赛》全书共116个问题,不求速度,只求质量,认认真真地学❤ 18.07.30 000.抽签你的朋友...

  • 用快速幂运算求斐波那契,时间复杂度降到O(logn)

    思路来自《挑战程序设计竞赛》 可运行的C++代码如下

  • 面试高级算法梳理笔记

    归去来兮。 1.1 说明 本篇为《挑战程序设计竞赛(第2版)》读书笔记系列,旨在: 梳理算法逻辑 探索优化思路 深...

  • 2019-05-26 蓝桥杯个人经验

    一.考前复习的书籍: 《信息学竞赛一本通》,《挑战程序设计》,《算法笔记》 《信息学奥赛一本通》主要看了: 1.高...

  • 简介

    这是关于《挑战程序设计竞赛(第2版)》的刷题记录。因为POJ评测快,全英文,评测结果反馈与ICPC竞赛相同,所以选...

  • 1.0 推荐书籍与学习方法

    Chapter1: 位运算的奇技淫巧 1.0 推荐书籍与学习方法 推荐书籍 《程序员面试金典》 《挑战程序设计竞赛...

  • 挑战程序设计竞赛11.7

    今天读的挑战程序设计竞赛的图的最短路问题,只看了一个dijkstra算法,但没怎么看明白。 又把昨天的bellma...

  • 挑战程序设计竞赛11.4

    /* 今天读了一种叫做并查集的数据结构,以前做题做到了,但一些解题报告质量参差不齐, 自己只是理解个大概了,不知道...

  • 挑战程序设计竞赛11.2

    今天读了如何实现优先队列,及如何运用。可以用数组来表示二叉树,节点是从上到下从左到右的顺序紧凑排列,它最重要的性质...

  • 挑战程序设计竞赛11.3

    今天读了二叉搜索树的实现以及set和map的简单用法。 二叉搜索树实际上就是一颗二叉树,但它有一个特点,就是每个节...

网友评论

      本文标题:《挑战程序设计竞赛》学习笔记(18.07.30-)

      本文链接:https://www.haomeiwen.com/subject/pehfvftx.html