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;
}
京公网安备 11010502036488号