√复习记录

阅读量：7015 次

发布时间：2019-06-28

本文共 7078 字，大约阅读时间需要 23 分钟。

练习：

1.模拟

洛谷：

P1007 独木桥 https://www.luogu.org/problem/show?pid=1007　　http://www.cnblogs.com/gc812/p/6035097.html

第一次第二次成交 https://www.luogu.org/problem/show?pid=2637#sub

//为什么说是搜索！！不就是模拟吗……忍无可忍的丢到模拟的训练分类来了

#include
      
       #include
       
        #include
        
         #include
         
          #define maxn 200005using namespace std;int n,m;int a[maxn];int maxnn,pos;int main(){    cin>>m>>n;    for(int i=1;i<=n;++i)scanf("%d",&a[i]);    sort(a+1,a+1+n);    for(int i=1;i<=n;++i)    {        int sum=a[i]*(n-i+1);        if(sum>maxnn)        {            maxnn=sum;            pos=a[i];        }    }    cout<
          
           <<" "<

View Code

NOI题库：

18:等差数列末项计算 http://noi.openjudge.cn/ch0103/18/　　http://www.cnblogs.com/gc812/p/6035121.html

2.二分

洛谷：

P1258 小车问题　　https://www.luogu.org/problem/show?pid=1258　　http://www.cnblogs.com/gc812/p/6035174.html

NOI题库：

河口跳石子 http://noi.openjudge.cn/ch0111/10/

#include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #define maxn 50005//#define pi acos(-1.0)using namespace std;int n,m,l;int a[maxn];bool check(int x)//判断所有的间隔都大于等于该值所需移走的石子数{    int last=0,ans=0;    for(int i=1;i<=n;++i)    {        if(a[i]-last
           
            m)return 0; return 1;}int main(){ scanf("%d%d%d",&l,&n,&m); int L=0,r=l,mid; for(int i=1;i<=n;++i) { scanf("%d",&a[i]); } a[++n]=l; while(L<=r) { mid=L+r>>1; if(check(mid))L=mid+1; else r=mid-1; } cout<

View Code

派 http://noi.openjudge.cn/ch0111/05/

注意π的精度

#include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #define maxn 10005#define pi M_PI#define eps 1e-5using namespace std;int n,f;double a[maxn];bool check(double x)//二分所分面积判断可以分成的数量即可//注意还要留给自己一块。{    int sum=0;    for(int i=1;i<=n;++i)    {        sum+=floor(a[i]/x);    }    return sum>=f+1;}int main(){//    freopen("data.txt","r",stdin);    scanf("%d%d",&n,&f);    double mid,l=0,r=0;    for(int i=1;i<=n;++i)    {        scanf("%lf",&a[i]);        a[i]=a[i]*a[i]*pi;        r=max(r,a[i]);    }    while(r-l>eps)//两个浮点数不能判相等     {        mid=(l+r)/2.0;        if(check(mid))l=mid;        else r=mid;    }    printf("%.3lf",l);    puts("");    return 0;}

派

月度开销 http://noi.openjudge.cn/ch0111/06/

不难猜想ans在[a[i]max,tot]里把总和当做r, 然后check, 即连续几个数的和<mid就可以分一组, 分完一组month++, 最后比较month和m即可

//数组记得开大！开大！开大！

#include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #define maxn 100005#define pi acos(-1.0)using namespace std;int n,m;int a[maxn],ans=0;bool check(int x){    int sum=0,month=1;    for(int i=1;i<=n;++i)    {        if(a[i]>x)return 0;        if(sum+a[i]>x)sum=a[i],month++;        else sum+=a[i];    }    if(month<=m)return 1;    return 0;}int main(){//    freopen("data.txt","r",stdin);    scanf("%d%d",&n,&m);    int mid,l=0,r=0;    for(int i=1;i<=n;++i)    {        scanf("%d",&a[i]);        r+=a[i];        l=max(a[i],l);    }    while(l<=r)    {        mid=l+r>>1;        if(check(mid))r=mid-1;        else l=mid+1;    }    printf("%d",l);    puts("");    return 0;}

View Code

3.贪心

4.搜索

vijos：

切蛋糕 https://vijos.org/p/1020

#include
      
       #include
       
        #include
        
         #include
         
          #define maxn 2005using namespace std;int mid;int n,m;int mouth[maxn],cake[maxn];int tot=0,space;int sum[maxn],fcake[maxn];int cmp(const void *a, const void *b){    return(*(int *)a-*(int *)b);}bool dfs(int deep,int pos){    if(deep<=0)return 1;    if(tot-space
          
           =mouth[deep])        {            fcake[i]-=mouth[deep];            if(fcake[i]
           
            >n; for(int i=1;i<=n;++i) { scanf("%d",&cake[i]); tot+=cake[i]; } cin>>m; for(int i=1;i<=m;++i) { scanf("%d",&mouth[i]); } qsort(cake+1,n,sizeof(int),cmp); qsort(mouth+1,m,sizeof(int),cmp); sum[0]=0; for(int i=1;i<=m;++i)sum[i]=sum[i-1]+mouth[i]; while(sum[m]>tot)--m;//剪枝 //以最小的嘴累加，与蛋糕总和比较，找到最多能满足的嘴数，就是二分上边界 int l=0,r=m; while(l<=r) { mid=l+r>>1; for(int i=1;i<=n;++i)fcake[i]=cake[i]; space=0; if(dfs(mid,1))l=mid+1; else r=mid-1; } cout<

View Code

扫雷游戏　　https://www.luogu.org/problem/show?pid=2670

//虽然洛谷给的标签是搜索但是好想把它扔到模拟去

#include
      
       #include
       
        #include
        
         #include
         
          #define maxn 205using namespace std;int n,m;char a[maxn][maxn];int lei[maxn][maxn];int main(){    cin>>n>>m;    memset(lei,0,sizeof(lei));    for(int i=0;i
          
           >a[i][j];            if(a[i][j]=='*')            {                ++lei[i-1][j+1];                ++lei[i-1][j];                ++lei[i-1][j-1];                ++lei[i][j-1];                ++lei[i][j+1];                ++lei[i+1][j];                ++lei[i+1][j-1];                ++lei[i+1][j+1];            }        }    }    for(int i=0;i

View Code

迷宫　　https://www.luogu.org/problem/show?pid=1605

终点有可能有障碍物，这时必须输出0，

#include
      
       #include
       
        #include
        
         #include
         
          #define maxn 200005using namespace std;int n,m,t;int sx,sy,fx,fy;bool a[10][10];int ans=0;bool check(int x,int y){    if(x==fx&&y==fy)    {        ++ans;        return 1;    }    if(a[x][y])return 1;    return 0;}void dfs(int x,int y){    a[x][y]=1;    if(x>1&&!check(x-1,y))dfs(x-1,y);    if(x
          
           1&&!check(x,y-1))dfs(x,y-1);    if(y
           
            >n>>m>>t>>sx>>sy>>fx>>fy; int x,y; for(int i=1;i<=t;++i) { scanf("%d%d",&x,&y); if(x==fx&&y==fy) { puts("0"); return 0; } a[x][y]=1; } dfs(sx,sy); cout<

View Code

*5.图论

寻找道路　　http://www.cnblogs.com/gc812/p/6024717.html

营救　　　　https://www.luogu.org/problem/show?pid=1396

通过spfa选边大于mid的都不选最后用spfa判断从起点s出发能否到达终点t 二分答案

#include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #define maxn 400005using namespace std;int n,m,s,t;int dis[maxn],cnt=0,h[maxn];bool vis[maxn];struct data{ int next,w,to;}e[maxn];queue
            
             q;void ins(int a,int b,int c){ e[++cnt].to=b; e[cnt].next=h[a]; h[a]=cnt; e[cnt].w=c;}bool check(int d){ memset(vis,0,sizeof(vis)); memset(dis,127/3,sizeof(dis)); dis[s]=0; vis[s]=1; q.push(s); while(!q.empty()) { int x=q.front();q.pop(); vis[x]=0; for(int i=h[x];i;i=e[i].next) { if(dis[e[i].to]>e[i].w) { dis[e[i].to]=e[i].w; if(!vis[e[i].to]&&dis[e[i].to]<=d) { vis[e[i].to]=1; q.push(e[i].to); } } } } return dis[t]<=d;}int main(){// freopen("data.txt","r",stdin);// cout<<"aaa"<
             
              >1; if(check(mid))r=mid; else l=mid+1; } printf("%d",l); puts(""); return 0;}

View Code

2016.11.14

//不知道为什么最近脑洞比较大写题莫名其妙的循环起了痒？。

//提交的时候真的不要手贱保留了freopen……不要问我怎么知道的

//已经手贱因为freopen一早上爆零7次了还有救吗急在线等TUT

2016.11.15

//二分上下界还很模糊 mid的判断全靠rp和样例调试+1-1 好蠢哦

//发现搜索已经忘光了？？？

转载于:https://www.cnblogs.com/gc812/p/6034907.html

你可能感兴趣的文章