A-赫式几何

问题描述

19世纪的德国数学家赫尔曼●明科夫斯基发现了一种非欧几里德几何空间，称作“出租车几何空间或者曼哈顿距离”。在这种神奇的空间中，定点T1(X1,Y1)与T2(X2,Y2)的距离表示为：
D(T1,T2)=|X1-X2|+|Y1-Y2|
其他的定义都同欧几里德几何相同，包括圆的定义：
圆是一个点集，其中的任意一个元素到平面上的一个定点（即圆心）的距离（即圆的半径）相同。
我们现在要研究在赫氏几何和欧氏几何中圆的面积的差别。现在这个重任交给了你。

输入格式

只有一个整数R，表示圆的半径。

输出格式

输出两行，分别表示圆在欧氏几何中的面积和在赫氏几何中的面积
注：答案精确到0.000001。

样例输入 1

1

样例输出 1

3.141593 
2.000000 

样例输入 2

21

样例输出 2

1385.442360
882.000000

样例输入 3

42

样例输出 3

5541.769441
3528.000000

提示

为保证精度，我们可以这样来表示圆周率Pi
double Pi=4.0*atan(1);
其中atan()为反正切函数，需要#include<cmath>包
因为tan(Pi/4)=1 所以Pi=4*atan(1);

分析

这道题很明显是一道水题，经过观察我们可以发现：

欧氏几何：r*r*pi
赫氏几何：r*r*2

然后代码就很好写了

Code

#include<bits/stdc++.h>
using namespace std;
const double pi=4.0*atan(1);
double r;
int main(){
    cin>>r;
    printf("%.6lf\n%.6lf",r*r*pi,r*r*2);
    return 0;
}

B-特技飞行

问题描述

神犇航空开展了一项载客特技飞行业务。
每次飞行长N个单位时间，每个单位时间可以进行(也可不进行)一项特技动作，可选的动作有K种，每种动作有一个刺激程度Ci。
如果连续进行相同的动作，乘客会感到厌倦，所以定义某次动作的价值为(距上次该动作的时间)*Ci，若为第一次进行该动作，价值为0。
安排一种方案，使得总价值最大。

输入格式

第一行，两个数，N和K，如上所述；
第二行，K个正整数，表示K种动作的Ci值。

输出格式

仅一行，一个整数，表示最大总价值。

样例输入 1

5 2
2 2

样例输出 1

12

样例输入 2

20 3
42 468 335

样例输出 2

15217

提示

对于10%的测试数据，N<=20，K<=3
对于全部的测试数据，1<=N<=1000，1<=K<=300，0<=Ci<=1000。

分析

一道很典型的贪心题。
每次将当前（没有表演过的）最大的在第i秒展示，保证最大的间隔时间长，即为最优解。

Code

#include<bits/stdc++.h>
using namespace std;
int n,k,a[1005];
bool cmp(int x,int y){return x>y;}
int main(){
    scanf("%d %d",&n,&k);
    for(int i=1;i<=k;i++)
        scanf("%d",&a[i]);
    sort(a+1,a+1+k,cmp);
    int m=k;
    long long ans=0;
    if(n<2*k)//不够展示完全部的动作
        m=n/2;
    for(int i=1,j=1;i<=m;i++,j+=2)
        ans+=a[i]*(n-j);
    printf("%lld",ans);
    return 0;
}

C-监狱

问题描述

TECH在执行刺杀计划的过程中被警方抓捕，被送到了一座监狱。
与TECH同时入狱的共有N位罪犯。这些罪犯有的是白人，有的是黑人。狱警要给他们分房间。 
但是，监狱为减少不必要的冲突，要求：要么保证整个房间都是同一肤色的罪犯，或者同一房间两种不同肤色罪犯的人数差不超过M。
另外，现在N个罪犯被锁链拴成成一排，狱警只会把连续一段的罪犯分进一个房间。狱警想知道，至少需要多少个房间。

输入格式

第一行包括N和M。
之后N行，每行一个整数，代表罪犯的肤色，1表示白色，2表示黑色。

输出格式

一个整数，表示最小需要房间的数量。

样例输入 1

12 1
1
1
1
1
2
1
2
1
1
2
2
2

样例输出 1

2

样例输入 2

10 2
1
1
1
2
1
2
1
1
2
2

样例输出 2

1

提示

对于30%的数据，有1 ≤ N ,M≤ 50；
对于60%的数据，有1 ≤ N ,M≤ 1000；
对于100%的数据，有1 ≤ N,M ≤ 2500。

分析

一道显而易见的dp，为啥显而易见呢？
因为是让我们选一段连续区间出来分一个房间。
那么我们可以用，来记录白人和黑人的数量的前缀和。
设定一个状态： ：表示从现在讨论到了i个人所需要的最小房间数。 ={}+1（）
条件：

Code

#include<bits/stdc++.h>
using namespace std;
const int inf=1e9;
int n,m,a[2505],w[2505],b[2505],f[2505];
int main(){
    scanf("%d %d",&n,&m);
    for(int i=1;i<=n;i++){
        f[i]=inf;
        scanf("%d",&a[i]);
        w[i]=w[i-1]+(a[i]==1);
        b[i]=b[i-1]+(a[i]==2);
    }
    for(int i=1;i<=n;i++){
        for(int j=0;j<i;j++)
            if(abs((w[i]-w[j])-(b[i]-b[j]))<=m || !(w[i]-w[j]) || !(b[i]-b[j]))
                f[i]=min(f[i],f[j]);
        f[i]++;
    }
    printf("%d",f[n]);
    return 0;
}

D-体重

问题描述

近日，信竞班有人在散布谣言，说何老板体重超重，这有损何老板在同学们心中的完美形象，让何老板很是头疼。
何老板还了解到，散布该谣言的人号称自己拥有最合适的体重，体重值位于所有人的正中间，何老板决心找出这个家伙。

信竞班有n名同学，编号1到n，已知每名同学的体重都不相同。何老板想知道，哪个同学的体重位于正中间。
也就是如果将n名同学按体重由轻到重排序后，该名同学位于第(n+1)/2名，这名同学一定是谣言散布者。

但是同学们都不肯准确告诉何老板他的体重，何老板只好在暗中收集信息。

例如：n=5时，何老板搜集到了如下信息：

1号同学比2号同学轻

3号同学比4号同学轻　　

1号同学比5号同学轻　　

2号同学比4号同学轻　　

根据上面的情报，虽然何老板不能准确得出哪个同学具有中间体重，但他可以肯定4号和1号不可能具有中间体重，
因为，1、2、3比4轻，而2、4、5比1重，所以他可以排除到这两名同学。

写一个程序统计出目前我们最多能排除掉多少个同学。也就是确定有多少个同学肯定不会是中间体重。

输入格式

第一行:两个整数n和m，其中n为奇数表示学生总数，m表示何老板搜集到的信息条数。
接下来的m行,每行两个整数x和y，表示x号同学比y号同学重。

输出格式

若干个整数，按从小到大的顺序输出不可能是中间重量的学生的编号。
若一个也找不出来，输出0。

样例输入 1

5 4
2 1
4 3
5 1
4 2

样例输出 1

1 4

样例输入 2

11 5
1 2
3 4
5 6
7 8
9 10

样例输出 2

0

样例输入 3

31 29
2 1
3 1
4 1
5 1
6 1
7 1
8 1
9 1
10 1
11 1
12 1
13 1
14 1
15 1
16 1
17 1
18 1
19 1
20 1
21 1
22 1
23 1
24 1
25 1
26 1
27 1
28 1
29 1
30 1

样例输出 3

1

提示

1<=n<=100
1<=m<=5000

分析

这是一道能用水过去的题，我们将两者间的重量关系看成边，用两个二维数组来记录（保证）是否比重和轻。
然后跑一边统计出入度和出度，如果入度或出度>n*2，就能保证他不可能是中间体重。

Code

#include<bits/stdc++.h>
using namespace std;
int n,m;
bool z[105][105],q[105][105],ztcakioi=true;
int main(){
    scanf("%d %d",&n,&m);
    for(int i=1;i<=m;i++){
        int x,y;
        scanf("%d %d",&x,&y);
        z[x][y]=true;
        q[y][x]=true;
    }
    for(int k=1;k<=n;k++)
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++){
                if(!z[i][j] && z[i][k] && z[k][j])
                    z[i][j]=true;
                if(!q[i][j] && q[i][k] && q[k][j])
                    q[i][j]=true;
            }
    for(int i=1;i<=n;i++){
        int ru=0,chu=0;
        for(int j=1;j<=n;j++){
            if(z[i][j])
                ru++;
            if(q[i][j])
                chu++;
        }
        if(ru>(n>>1) || chu>(n>>1)){
            printf("%d ",i);
            ztcakioi=false;
        }
    }
    if(ztcakioi)
        puts("0");
    return 0;
}

E-钢铁侠

问题描述

何老板最近很钟意一款名为钢铁侠的飞行游戏。游戏中有n块木板悬浮在空中，不同的木板悬浮的高度可能不同，每块木板上都有一定的金币。
玩家可以任选一块木板作为钢铁侠飞行的起点，控制钢铁侠往右飞行。飞行时，钢铁侠会一直保持当前的飞行高度。当然，玩家可以选择让钢铁侠降落到比当前飞行高度低的木板上。每当钢铁侠降落到一块木板上，他就可以获得该木板上的金币。然后钢铁侠会以当前木板的高度继续往右飞行。
游戏中还有两种特殊的木板：
1.木板上有磁铁，只要钢铁侠从其上空经过便会被吸到该木板上,获得金币后以该木板的高度继续往右飞行(也就是从上方经过时必须降落在该木板);
2.木板上有弹簧，如果钢铁侠选择降落在上面，获得金币的同时会被向上弹起一定的高度t(假如该木板高度为h,钢铁侠降落后继续往右飞行的高度为h+t);
现在何老板已知所有木板的信息，问他最多能得到多少金币？

输入格式

第一行，一个整数n
接下来n行，从左往右依次描述每块木板的情况。
第i行描述第i块木板，首先是三个整数h,g,v,其中h表示木板的高度，g表示该木板上金币的数量，v表示木板的种类。
v=0,表示这是一块普通木板，
v=1,表示这块木板上有磁铁，
v=2,表示这块木板有弹簧，接下来一个整数t，表示向上弹起的高度。

输出格式

一个整数，表示能够得到的最多金币数。

样例输入 1

7
14 25 0
1 15 0
12 20 2 20
5 21 0
20 18 1
27 28 0
23 30 0

样例输出 1

66

样例输入 2

10
26 17 0
2 4 2 28
2 11 0
12 24 2 27
21 27 1
26 3 0
28 1 2 9
10 12 0
14 3 1
3 13 1

样例输出 2

97

样例输入 3

7
7 29 2 29
18 26 0
11 9 0
21 16 1
1 7 0
25 5 0
29 28 2 25

样例输出 3

71

提示

样例1说明：
钢铁侠从1号板起飞，在3号和4号板降落。获得的金币为25+20+21=66
数据范围:
1<=n<=3000
1<=h<=50000
0<=g<=10000
1<=t<=50000

分析

：表示以i号板为终点所能得到的最大金币数。 ={}
条件： &&

Code

#include<bits/stdc++.h>
using namespace std;
const int N=3005;
const int inf=1e9;
int n,h[N],a[N],v[N],t[N],f[N],ans=-inf;
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%d %d %d",&h[i],&a[i],&v[i]);
        if(v[i]==2)
            scanf("%d",&t[i]);
    }
    for(int i=1;i<=n;i++){
        f[i]=a[i];
        int dep=inf;
        for(int j=i-1;j>=1;j--){
            if(h[j]+t[j]<=dep && h[i]<h[j]+t[j])
                f[i]=max(f[i],f[j]+a[i]);
            if(v[j]==1)
                dep=min(dep,h[j]);
        }
        ans=max(ans,f[i]);
    }
    printf("%d",ans);
    return 0;
}

F-旗帜染色

问题描述

N个旗帜排成一排，初始每种旗帜有一种颜色，现在要把其中的一些旗帜改变颜色，使得任意相邻的两个旗帜颜色不同，求至少要改变多 少个旗帜的颜色。

输入格式

第一行两个数 N，M，表示旗帜个数和颜色数。
接下来一行一个长度为N的字符串，第i个字符表示第i个旗帜的颜 色，保证为前M个大写字母之一。

输出格式

一个数，表示最少要改变的旗帜数。

样例输入 1

6 3 
ABBACC

样例输出 1

2

样例输入 2

20 7
EEFCEGFCFEGAGGACEADB

样例输出 2

2

提示

改变后的颜色不能是前M 个大写字母所表示颜色之外的颜色
对于 100%的数据，N≤10^5,1≤M≤26.

分析（贪心）

这道题感觉比B题还要水，但居然没有其他人做出来！！
每次判断是否与相等，相等++，将变成不等于小于m的字母。（这里规定A为1，B为2·····以此类推）
然后瞎jb写了个暴力就过了

Code

#include<bits/stdc++.h>
using namespace std;
int n,m,ans=0;
char a[100005];
int main(){
    scanf("%d %d",&n,&m);
    for(int i=1;i<=n;i++)
        cin>>a[i];
    for(int i=1;i<=n;i++){
        if(a[i]==a[i-1]){
            ans++;
            for(int j=1;j<=m;j++){
                char s=j+64;
                if(s!=a[i+1] && s!=a[i-1]){
                    a[i]=s;
                    break;
                }
            }
        }
    }
    printf("%d",ans);
    return 0;
}

其实还有一种更简洁的写法：

#include<bits/stdc++.h>
using namespace std;
int n,m,ans=0;
char a[100005];
int main(){
    scanf("%d %d",&n,&m);
    for(int i=1;i<=n;i++)
        cin>>a[i];
    for(int i=1;i<=n;i++){
        if(a[i]==a[i-1]){
            ans++;
            i++;
        }
    }
    printf("%d",ans);
    return 0;
}

总的来说，这次比赛除了C，E题要耗费点脑子（当然大佬比赛都不需要带脑子的），其他的题总结出来:

#水的一批