算法竞赛入门经典写题笔记（第一章算法设计基础）

佚名 6年前 (2019-04-10) 随笔 1711人围观抢沙发百度已收录

可是我为什么要专门开一发写这个呢......

1.1 思维的体操

例题1 The Dragon of Loowater

贪心

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

#include<cstdio>
#include<algorithm>
using namespace std;
int n,m;
int x[20005],y[20005];
int main()
{

    while(~scanf("%d %d",&n,&m)&&(n||m))
    {
        for(int i=0;i<n;i++) scanf("%d",&x[i]);
        for(int i=0;i<m;i++) scanf("%d",&y[i]);
        sort(x,x+n);
        sort(y,y+m);
        int k=0;
        int num=0;
        for(int i=0;i<m;i++)
        {
            if(x[k]<=y[i])
            {
                num+=y[i];
                k++;
                if(k==n) break;
            }
        }
        if(k<n) printf("Loowater is doomed!\n");
        else printf("%d\n",num);
    }
    return 0;
}

例题2 Commando War

贪心

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#define MAXN 100010
using namespace std;
int n,cnt;
struct Node{int a,b;}node[MAXN];
inline bool cmp(struct Node x,struct Node y){return x.b>y.b;}
int main()
{
    #ifndef ONLINE_JUDGE
    freopen("ce.in","r",stdin);
    #endif
    while(scanf("%d",&n)!=EOF)
    {
        if(n==0) break;
        for(int i=1;i<=n;i++)
            scanf("%d%d",&node[i].a,&node[i].b);
        sort(&node[1],&node[n+1],cmp);
        long long ans=0,sum=0;
        for(int i=1;i<=n;i++)
        {
            sum+=node[i].a;
            ans=max(ans,sum+node[i].b);
        }
        cnt++;
        printf("Case %d: %lld\n",cnt,ans);
    }
    return 0;
}

例题3 Spreading the Wealth（中位数，贪心）

题目模型：给定数轴上的n个点，在数轴上的所有点中，中位数离所有的顶点距离之和最小。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#define MAXN 1000010
using namespace std;
int n;
long long a[MAXN],c[MAXN];
int main()
{
    #ifndef ONLINE_JUDGE
    freopen("ce.in","r",stdin);
    #endif
    while(scanf("%d",&n)!=EOF)
    {
        for(int i=1;i<=n;i++) scanf("%lld",&a[i]);
        long long tot=0;
        for(int i=1;i<=n;i++) tot+=a[i];
        long long M=tot/n;
        c[0]=0;
        for(int i=1;i<n;i++) c[i]=c[i-1]+a[i]-M;
        sort(&c[0],&c[n]);
        long long cur=c[n/2];
        long long ans=0;
        for(int i=0;i<n;i++) ans+=abs(cur-c[i]);
        printf("%lld\n",ans);
    }
    return 0;
}

例题4 Graveyard

坐标的放缩法qwq

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#define MAXN 1000010
using namespace std;
int n,m;
int main()
{
    #ifndef ONLINE_JUDGE
    freopen("ce.in","r",stdin);
    #endif
    while(scanf("%d%d",&n,&m)==2)
    {
        double ans=0.0;
        for(int i=1;i<=n;i++)
        {
            double pos=(double)(i*1.0/n)*(n+m);
            ans+=fabs(pos-1.0*floor(pos+0.5))/(n+m);
        }
        printf("%.4lf\n",ans*10000);
    }
    return 0;
}

例题5 Piotr's Ants

例题6 Image Is Everything

例题7 Even Parity

枚举状态的化简
虽然我们不能枚举所有可能的情况，但是我们可以找到依赖关系，通过已知条件确定未知的方法来减少枚举的数量。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#define MAXN 50
using namespace std;
int T,n,cnt;
int a[MAXN][MAXN],cur[MAXN][MAXN];
inline int solve(int x,int y)
{
    int sum=0;
    if(x-2>=1) sum+=cur[x-2][y];
    if(y-1>=1) sum+=cur[x-1][y-1];
    if(y+1<=n) sum+=cur[x-1][y+1];
    return sum;
}
inline void print()
{
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
            printf("%d ",cur[i][j]|a[i][j]);
        printf("\n");
    }
    printf("\n");
}
inline int calc(int x)
{
    for(int i=0;i<n;i++)
    {
        if(x&(1<<i)) cur[1][i+1]=1;
        else if(a[1][i+1]==1) return 0x3f3f3f3f;
    }
    for(int i=2;i<=n;i++)
        for(int j=1;j<=n;j++)
        {
            if(solve(i,j)&1) cur[i][j]=1;
            else 
            {
                if(a[i][j]==1) return 0x3f3f3f3f;
                else cur[i][j]=0;
            }
        }
    int cur_ans=0;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            if(a[i][j]==0&&cur[i][j]==1)
                cur_ans++;
    // print();
    // printf("cur_ans=%d\n",cur_ans);
    return cur_ans;
}
int main()
{
    #ifndef ONLINE_JUDGE
    freopen("ce.in","r",stdin);
    #endif
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d",&n);
        cnt++;
        int jian=0;
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++)
                scanf("%d",&a[i][j]);
        int cur_ans=0x3f3f3f3f;
        for(int i=0;i<(1<<n);i++) memset(cur,0,sizeof(cur)),cur_ans=min(cur_ans,calc(i));
        if(cur_ans==0x3f3f3f3f) printf("Case %d: %d\n",cnt,-1);
        else printf("Case %d: %d\n",cnt,cur_ans);
    }
    return 0;
}

例题8 Colored Cubes

例题9 Chinese Mahjong

例题10 Help is needed for Dexter

给定正整数n，你的任务是用最少的操作次数把序列1,2,3...,n中的所有数都变成0，每次操作可以从序列中选择一个或者多个证书，同时减去一个相同的正整数。
f(n)=f(n/2)+1

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#define MAXN 100010
using namespace std;
int n;
inline int solve(int x)
{
    if(x==1) return 1;
    else return solve(x/2)+1;
}
int main()
{
    #ifndef ONLINE_JUDGE
    freopen("ce.in","r",stdin);
    #endif
    while(scanf("%d",&n)!=EOF)
        printf("%d\n",solve(n));
    return 0;
}

例题11 A Different Task

例题12 Assemble

二分+贪心

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<queue>
#include<map>
#include<ctime>
#include<vector>
#define MAXN 1010
using namespace std;
int T,n,m,cnt,ans;
struct Node{string fa,name;int price,value;}node[MAXN<<1];
struct Node2{int price,value;};
map<string,int>id;
vector<Node2>vec[MAXN];
inline bool check(int x)
{
    int cur_ans=0;
    for(int i=1;i<=cnt;i++)
    {
        int minn=2147483647;
        for(int j=0;j<vec[i].size();j++)
        {
            if(vec[i][j].value<x) continue;
            minn=min(minn,vec[i][j].price);
        }
        if(minn==2147483647) return false;
        cur_ans+=minn;
        if(cur_ans>m) return false;
        
    }
    return true;
}
int main()
{
    #ifndef ONLINE_JUDGE
    freopen("ce.in","r",stdin);
    #endif
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d%d",&n,&m);
        cnt=0;
        id.clear();
        for(int i=1;i<=n;i++) vec[i].clear();
        for(int i=1;i<=n;i++)
        {
            cin>>node[i].fa>>node[i].name;
            scanf("%d%d",&node[i].price,&node[i].value);
            if(!id.count(node[i].fa)) id[node[i].fa]=++cnt;
            vec[id[node[i].fa]].push_back((Node2){node[i].price,node[i].value});
        }
        int l=0,r=(int)1e9+1;
        while(l<=r)
        {
            int mid=(l+r)>>1;
            if(check(mid)==true) ans=mid,l=mid+1;
            else r=mid-1;
        }
        printf("%d\n",ans);
    }
    return 0;
}

例题13 Pie

虽然不是“最小值最大”诸如此类的问题，但是采取二分答案的方法可以使得问题转化为判定性问题
double类型的二分，注意eps比要求的精度多个2位就可以了，太多的话，二分会T

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#define eps 1e-5
#define pi acos(-1.0)
#define MAXN 100010
using namespace std;
int n,f,T;
double l=0.0,r;
double R[MAXN];
inline bool check(double x)
{
    int cur_ans=0;
    for(int i=1;i<=n;i++)
    {
        double s=pi*R[i]*R[i];
        cur_ans+=floor(s/x);
    }
    if(cur_ans>=f) return true;
    else return false;
}
int main()
{
    #ifndef ONLINE_JUDGE
    freopen("ce.in","r",stdin);
    #endif
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d%d",&n,&f);
        l=r=0.0;
        for(int i=1;i<=n;i++)
        {
            int cur;
            scanf("%d",&cur);
            R[i]=1.0*cur;
            r=max(r,R[i]*R[i]*pi);
        }
        f++;
        while(l+eps<r)
        {
            double mid=(l+r)/2;
            if(check(mid)==true) l=mid;
            else r=mid;
        }
        printf("%.4lf\n",l);
    }
    return 0;
}

例题14 Fill the Square

例题15 Network

例题16 Beijing Guards

例题17 Age sort

桶排

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#define MAXN 110
using namespace std;
int n;
int cnt[MAXN];
int main()
{
    #ifndef ONLINE_JUDGE
    freopen("ce.in","r",stdin);
    #endif
    while(scanf("%d",&n)!=EOF)
    {
        if(n==0) break;
        memset(cnt,0,sizeof(cnt));
        int cur;
        for(int i=1;i<=n;i++) scanf("%d",&cur),cnt[cur]++;
        bool flag=false;
        for(int i=1;i<=100;i++)
        {
            if(cnt[i]==0) continue;
            for(int j=1;j<=cnt[i];j++)
            {
                if(flag==true) printf(" ");
                printf("%d",i);
                flag=true;
            }
        }
        printf("\n");
    }
    return 0;
}

例题18 Open Credit System

例题19 Calculator Conundrum

例题20 Metor

例题21 Subsequence

例题22 City Games

例题23 Distant Galaxy

例题24 Garbage Heap

例题25 Jurassic Remains

例题26 And Then There Was One

例题27 Prince ans Princess

例题28 Game of Sum

例题29 Hacker's Crackdown

例题30 Placing Lampposts

例题31 Robotruck

例题32 Sharing Chocolate

目前不知道哪里错了,交了13发也没过。。。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#define MAXN 110
#define LOG 16
using namespace std;
int n,X,Y,tim;
int a[MAXN],dp[MAXN][1<<LOG],done[MAXN][1<<LOG],sum[MAXN];
inline int calc(int x){return x==0?0:calc(x/2)+(x&1);}
inline int search(int x,int s)
{
    if(done[x][s]) return dp[x][s];
    done[x][s]=1;
    if(calc(s)==1) 
    {
        dp[x][s]=1;
        return 1;
    }
    for(int s1=(s-1)&s;s1;s1=(s1-1)&s)
    {
        int s2=s-s1;
        if(sum[s1]%x==0&&search(min(x,sum[s1]/x),s1)&&search(min(x,sum[s2]/x),s2))
        {
            dp[x][s]=1;
            return 1;
        }
        int y=sum[s]/x;
        if(sum[s1]%y==0&&search(min(y,sum[s1]/y),s1)&&search(min(sum[s2]/y,y),s2)) 
        {
            dp[x][s]=1;
            return 1;
        }
    }
    dp[x][s]=0;
    return 0;
}
int main()
{
    while(scanf("%d",&n)==1)
    {
        if(n==0) break;
        ++tim;
        memset(done,0,sizeof(done));
        memset(sum,0,sizeof(sum));
        memset(dp,0,sizeof(dp));
        int maxx=(1<<n)-1,tot=0;
        scanf("%d%d",&X,&Y);
        for(int i=1;i<=n;i++) scanf("%d",&a[i]);
        for(int i=0;i<=maxx;i++)
            for(int j=0;j<n;j++)
                if(i&(1<<j))
                    sum[i]+=a[j+1];
        int ans=0;
        if(sum[maxx]!=X*Y||sum[maxx]%X!=0) ans=0;
        else
        {
            ans=search(min(X,Y),maxx);
            printf("Case %d: %s\n",tim,ans==0?"No":"Yes");
        }
    }
    return 0;
}

扫码关注我们

微信号：SRE实战

拒绝背锅运筹帷幄

赞 0 赏分享

转载请注明 : 文章转载自小翔博客算法竞赛入门经典写题笔记（第一章算法设计基础）

本文标题：算法竞赛入门经典写题笔记（第一章算法设计基础）

本文链接：https://www.liuyixiang.com/post/27891.html

上一篇 : [CTSC2010]珠宝商 SAM+后缀树+点分治

下一篇 : 『并发包入坑指北』之阻塞队列

评论列表暂无评论

发表评论

算法竞赛入门经典写题笔记（第一章算法设计基础）

1.1 思维的体操

例题1 The Dragon of Loowater

例题2 Commando War

例题3 Spreading the Wealth（中位数，贪心）

例题4 Graveyard

例题5 Piotr's Ants

例题6 Image Is Everything

例题7 Even Parity

例题8 Colored Cubes

例题9 Chinese Mahjong

例题10 Help is needed for Dexter

例题11 A Different Task

例题12 Assemble

例题13 Pie

例题14 Fill the Square

例题15 Network

例题16 Beijing Guards

例题17 Age sort

例题18 Open Credit System

例题19 Calculator Conundrum

例题20 Metor

例题21 Subsequence

例题22 City Games

例题23 Distant Galaxy

例题24 Garbage Heap

例题25 Jurassic Remains

例题26 And Then There Was One

例题27 Prince ans Princess

例题28 Game of Sum

例题29 Hacker's Crackdown

例题30 Placing Lampposts

例题31 Robotruck

例题32 Sharing Chocolate

选择打赏方式：

选择分享方式：

Petter

101481

12

121484300

« 2024年2月 »
一	二	三	四	五	六	日
			1	2	3	4
5	6	7	8	9	10	11
12	13	14	15	16	17	18
19	20	21	22	23	24	25
26	27	28	29

算法竞赛入门经典 写题笔记（第一章 算法设计基础）

1.1 思维的体操

例题1 The Dragon of Loowater

例题2 Commando War

例题3 Spreading the Wealth（中位数，贪心）

例题4 Graveyard

例题5 Piotr's Ants

例题6 Image Is Everything

例题7 Even Parity

例题8 Colored Cubes

例题9 Chinese Mahjong

例题10 Help is needed for Dexter

例题11 A Different Task

例题12 Assemble

例题13 Pie

例题14 Fill the Square

例题15 Network

例题16 Beijing Guards

例题17 Age sort

例题18 Open Credit System

例题19 Calculator Conundrum

例题20 Metor

例题21 Subsequence

例题22 City Games

例题23 Distant Galaxy

例题24 Garbage Heap

例题25 Jurassic Remains

例题26 And Then There Was One

例题27 Prince ans Princess

例题28 Game of Sum

例题29 Hacker's Crackdown

例题30 Placing Lampposts

例题31 Robotruck

例题32 Sharing Chocolate

选择打赏方式：

选择分享方式：

Petter

101481

12

121484300

User Login

帐号或密码错误,请重试.

算法竞赛入门经典写题笔记（第一章算法设计基础）