HNFMS一个初二蒟蒻OIerの实验室

补发:2019年6月15日测试解题报告

1、攻击火星(lg P1416)——图论理论

[问题描述]

一群外星人将要攻击火星。火星的地图是一个n个点的无向图。这伙外星人将按照如下方法入侵,先攻击度为0的点(相当于从图中删除掉它),然后是度为1的点,依此类推直到度为n-1的点。

所有的点度统计是动态统计的。(一个点删掉后,与之相连的点的点度都会-1)。外星人攻击度为某个数的点时是同时攻击的。你需要设计这个图的边的方案来使得未被攻击的点最多。

[输入格式]

仅1行,一个正整数n。

[输出格式]

仅一行,一个整数,表示最多的最后未被攻击的点。

[样例输入1]

3

[样例输出1]

1

[样例解释]

①-②-③,这样首先删掉度为1的①和③,此时②度数为0,不会被删去。

[数据范围]

对于20% 的数据,n≤10。

对于100% 的数据,1≤n≤50000。

[算法分析]

度:即每个点所连边数

最优方案:即所有点全部连线后清除一条

最终剩下的点为n-2个
[代码]

#include<bits/stdc++.h>
using namespace std;
​
int main()
{
    int n;
    cin>>n;
    if(n>2)cout<<n-2<<endl;
    else cout<<0<<endl;
    return 0;
}

2、斐波那契数的拆分(lg P1755.cpp)——数学+贪心

[问题描述]

已知任意一个正整数都可以拆分为若干个斐波纳契数,现在,让你求出 n的拆分方法。

[输入格式]

一个数t,表示有t组数据。

接下来t行,每行一个数n。

[输出格式]

t行,每行一个字符串,表示拆分方法(格式:n=a1+a2+a3+..+an),要求从小到大输出。

若有多组数据,以个数最小的为准,若仍有多组,输出右边尽量大的一组。

[样例输入]

1

6

10

[样例输出]

1=1

[代码]

// 本程序用于打表
#include<bits/stdc++.h>
using namespace std;
int f[101];
​
int fib(int i)
{
    if(f[i]!=0)
    {
        return f[i];
    }
    if(i==1 || i==2)
    {
        f[i]=1;
        return 1;
    }
    f[i]=fib(i-1)+fib(i-2);
    return f[i];
}
​
int main()
{
    for(int i=1;i<=45;i++)
        cout<<fib(i)<<',';
}
// 得表如下:0,1,1,2,3,5,8,13,21,34,55,89,144,233,377,610,987,1597,2584,4181,6765,10946,17711,28657,46368,75025,121393,196418,317811,514229,832040,1346269,2178309,3524578,5702887,9227465,14930352,24157817,39088169,63245986,102334155,165580141,267914296,433494437,701408733,1134903170
// 提交代码
#include<bits/stdc++.h>
using namespace std;
int b[1000001],n;
int fib[46]={0,1,1,2,3,5,8,13,21,34,55,89,144,233,377,610,987,1597,2584,4181,6765,10946,17711,28657,46368,75025,121393,196418,317811,514229,832040,1346269,2178309,3524578,5702887,9227465,14930352,24157817,39088169,63245986,102334155,165580141,267914296,433494437,701408733,1134903170};
int main()
{
    int a;
    cin>>a;
    for(int i=0;i<a;i++)
    {
        cin >> n;
        int nbak=n,x=0;
        printf("%d=",n);
        for(int k=45;k>=1;k--)
        {
            if(fib[k]<=nbak && nbak>=0)
            {
                nbak-=fib[k];
                b[x]=fib[k];
                x++;
            }
        }
        for(int j=x-1;j>=0;j--)
        {
            if(j!=x-1)
                cout<<'+'<<b[j];
            else cout<<b[j];
        }
        cout<<endl;
    }
    return 0;
}

3、子集求和(lg P2415)——数学,统计

[问题描述]

给定一个集合s(集合元素数量<=30),求出此集合所有子集元素之和。

[输入格式]

集合中的元素(元素<=1000)

[输出格式]

所有子集元素之和。

[样例输入]

2 3

[样例输出]

10

[样例说明]

[]+[2]+[3]+[2 3]=2+3+2+3=10

[算法分析]

通过找规律可以得到,每个数字出现的次数是2n-1(n为数字个数)

[代码]

#include<bits/stdc++.h>
using namespace std;
long long a,sum=0,i=0;
​
int main()
{
    while(scanf("%lld",&a)!=EOF)
    {
        sum+=a;
        i++;
    }
    long long a=pow(2,i-1)*sum;
    printf("%lld",a);
    return 0;
}

4、置换问题——置换理论、链表

[问题描述]

输入一个正整数n和1~n的一个排列,可以认为这是1~n的一种置换,求这个置换中有几个独立的子置换?

[输入格式]

第一行,一个正整数n(n≤1000)

第二行,1~n的一种排列

[输出格式]

独立子置换个数

[样例输入]

5

4 3 2 1 5

[样例输出]

3

[算法分析]
链表:数组当前位置上的数表示当前项目的下一位置

即演变为数圈问题。
[代码]

#include<bits/stdc++.h>
using namespace std;
int n,a[1001],ans;// a为储存,n为个数,ans答案
bool k[1001];// 记录位置是否走过
void dg(int i){//仍未走到已走过点,圈未闭合
    if(!k[i]){
        k[i]=1;
        dg(a[i]);
    }
    else{//走到已走过点,圈已闭合
        ans+=1;
        return ;
    }
}
int main(){
    cin>>n;
    for(int i=0;i<n;i++)
        cin>>a[i];//输入
    for(int i=0;i<n;i++)
        if(!k[i])
            dg(i);
    cout<<ans<<endl;
    return 0;
}

5、种树(lg P1250)——贪心

[问题描述]

一条街的一边有几座房子。因为环保原因居民想要在路边种些树。路边的地区被分割成块,并被编号成1..N。每个部分为一个单位尺寸大小并最多可种一棵树。每个居民想在门前种些树并指定了三个号码B,E,T。这三个数表示该居民想在B和E之间最少种T棵树。当然,B≤E,居民必须记住在指定区不能种多于区域地块数的树,所以T≤E-B+l。居民们想种树的各自区域可以交叉。你的任务是求出能满足所有要求的最少的树的数量。

[输入格式]

第一行包含数据N,区域的个数(0<N≤30000)

第二行包含H,房子的数目(0<H≤5000)

下面的H行描述居民们的需要:B  E T,0<B≤E≤30000,T≤E-B+1。

[输出格式]

只有一行写有树的数目

[样例输入]

9

4

1 4 2

4 6 2

8 9 2

3 5 2

[样例输出]

5

[算法分析]

原理:尽量从区间后往区间前种,以让区间的最后与下一区间最前重复,达到种树最少

[代码]

#include<bits/stdc++.h>
using namespace std;
int di[30005],sum=0,zong=0;
struct noi
{
    int b;
    int e;
    int t;
}bet[5005];
​
bool cmp(noi a,noi b)
{
    if(a.e<b.e)return true;
    else if(a.e>b.e) return false;
    else{
        if (a.b<b.b)
        {
            return false;
        }
        else
        {
            return true;
        }
    }
}
​
int main()
{
    ios::sync_with_stdio(false);
    int n,per;
    cin>>n>>per;
    for (int i = 0; i < per; i++)
    {
        cin>>bet[i].b>>bet[i].e>>bet[i].t;
        bet[i].b--;
        bet[i].e--;
    }
    sort(bet,bet+per,cmp);
    for (int i = 0; i < per; i++)
    {
        sum=0;
        for (int j = bet[i].b; j <= bet[i].e; j++)
        {
            if(di[j]==1)
                sum++;
        }
        if (sum>=bet[i].t)
        {
            continue;
        }
        else
        {
            for (int j = bet[i].e; j >= bet[i].b ; j--)
            {
                if(di[j]==0)
                {
                    di[j]=1;
                    zong++;
                    sum++;
                    if(sum==bet[i].t)break;
                }
            }
        }
    }
    cout<<zong<<endl;
    return 0; 
}

6、路障(lg P3395)——网格图BFS

[问题描述]

B君站在一个 n×n的棋盘上。最开始,B君站在(1,1)这个点,他要走到(n,n)这个点。

B君每秒可以向上下左右的某个方向移动一格,但是很不妙,C君打算阻止B君的计划。每秒结束的时刻,C君会在(x,y)上摆一个路障。B君不能走在路障上。B君拿到了C君准备在哪些点放置路障。所以现在你需要判断,B君能否成功走到(n,n)。保证不会走到某处,然后被一个路障砸死。

[输入格式]

首先是一个正整数T,表示数据组数。

对于每一组数据:

第一行,一个正整数n。

接下来2n-2行,每行两个正整数x和y,意义是在那一秒结束后,(x,y)将被摆上路障。

[输出格式]

对于每一组数据,输出Yes或No,回答B君能否走到(n,n)。

[样例输入]

2

2

1 1

2 2

5

3 3

3 2

3 1

1 2

1 3

1 4

1 5

2 2

[样例输出]

Yes

Yes

[还没做,先放个别人的题解]

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<queue>
#include<stack>
using namespace std;
int n,zx[2000],zy[2000],k,xx[4]={0,0,1,-1},yy[4]={1,-1,0,0};//n是矩阵的大小,zx,zy是障碍的坐标,k是数据组数,xx,yy是四个移动方向 
bool map[1001][1001],vis[1001][1001],flag;//map是地图,vis看是否被访问,flag看是否可以到达 
struct node
{
    int x,y,t;//记录坐标和现在的时间 
};
void bfs(int x,int y,int t)
{
    queue<node>q;//我喜欢用STL的队列,不喜欢手动模拟的,因为我懒啊 
    node now,net;
    now.x=x;now.y=y;now.t=t;
    q.push(now);
    while(!q.empty()) {
        now=q.front();//取出队头元素 
        q.pop();//出队 
        int a=now.x;int b=now.y;int c=now.t;//便于后面码代码 
        if(a==n && b==n) {//到了终点 
            flag=1;//改变标志 
            break;//直接退出循环 
        }
        map[zx[now.t-1]][zy[now.t-1]]=1;//要点,障碍降落,因为t是从0开始,所以要减1 
        for(int i=0;i<4;i++) {//枚举四个方向 
            int dx=a+xx[i];int dy=b+yy[i];
            if(dx>=1 && dx<=n && dy>=1 && dy<=n && map[dx][dy]==0 && vis[dx][dy]==0) {//在矩阵中,无障碍,无访问 
                net.x=dx;net.y=dy;net.t=c+1;//时间加加 
                vis[dx][dy]=1;
                q.push(net);//进入队列 
            }
        }
    }
}
int main()
{
    scanf("%d",&k);
    while(k--) {//一般是到0就结束
        scanf("%d",&n);
        memset(map,0,sizeof(map));//初始化!! 
        memset(vis,0,sizeof(vis));
        flag=0;//看是否可以到达终点的标志 
        for(int i=1;i<=2*n-2;i++)//输入障碍 
            scanf("%d%d",&zx[i],&zy[i]);
        vis[1][1]=1;//起点肯定被访问了
        bfs(1,1,0);//广搜 
        if(flag==1)//判断 
            printf("Yes\n");
        else
            printf("No\n");
    }
}

7、约数研究(lg P1403)——数论入门

[问题描述]

小联最近在研究和约数有关的问题,他统计每个正数N的约数的个数,并以f(N)来表示。

例如12的约数有1、2、3、4、6、12。因此f(12)=6。下表给出了一些f(N)的取值:

f(n)表示n的约数个数,现在给出n(n≤1000000),要求求出f(1)到f(n)的总和。

[输入格式]

输入一行,一个整数n。

[输出格式]

输出一个整数,表示总和

[样例输入]

3

[样例输出]

5

[算法分析]

本题有公式SUM=n+n/2+n/3+n/4+n/5+...+1

证明:即1-n中被1整除个数+被2整除个数+被3整除个数+...+被n整除个数

[代码]

#include<bits/stdc++.h>
using namespace std;
​
int main()
{
    int n,sum=0;
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        sum+=(n/i);
    }
    cout<<sum<<endl;
    return 0;
}

拓展训练

8、营救(lg P1396)——建图+二分答案+DFS or BFS

[问题描述]

妈妈下班回家,街坊邻居说小明被一群陌生人强行押上了警车!妈妈丰富的经验告诉她

小明被带到了t区,而自己在s区。

该市有m条大道连接n个区,一条大道将两个区相连接,每个大道有一个拥挤度。小明

的妈妈虽然很着急,但是不愿意拥挤的人潮冲乱了她优雅的步伐。所以请你帮她规划一条从

s至t的路线,使得经过道路的拥挤度最大值最小。

[输入格式]

第一行四个数字n,m,s,t。

接下来m行,每行三个数字,分别表示两个区和拥挤度。

(有可能两个区之间有多条大道相连。)

[输出格式]

输出题目要求的拥挤度。

[样例输入]

3 3 1 3

1 2 2

2 3 1

1 3 3

[样例输出]

2

[样例说明]

小明的妈妈要从1号点去3号点,最优路线为1->2->3。

[数据范围]

30% n<=10

60% n<=100

100% n<=10000,m<=2n,拥挤度<=10000

题目保证1<=s,t<=n且s≠t,保证可以从s区出发到t区。

还没做啦...

  

标签: 综合测试, 解题报告

Title - Artist
0:00