程序员经验分享-hwhale

百度之星2020 初赛第三场

2023-05-16

Discount

Accepts: 1432 Submissions: 2728
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)
Problem Description
学皇来到了一个餐馆吃饭。他觉得这家餐馆很好吃，于是就想办个会员。

一共有 nn 种会员充值卡套餐，假设学皇这餐饭的消费为 aa 元，选择第 ii 种套餐，需要充值 b[i] * ab[i]∗a 的钱，这次吃饭可以打 c[i]\times 10c[i]×10 折，由充值的钱支付（即这次吃饭只需要从充值金额中扣除 a\times c[i]a×c[i] 元）。以后用剩余的充值的钱吃饭不再打折。

请问学皇应该选择哪个套餐（必须选择恰好一个套餐），使得优惠的比例最大？

优惠比例的定义是把充的钱用完以后，(本来应该付的钱 - 实际付的钱) / 本来应该付的钱。在这个题目里，实际付的钱就是这次充值的花费。

Input
第一行一个整数 test(1 \leq test \leq 100)test(1≤test≤100) 表示数据组数。

对于每组数据，第一行一个正整数 n(1 \leq n \leq 100)n(1≤n≤100) 表示套餐的数目。

接下来 nn 行，每行一个正整数 b[i](1 \leq b[i] \leq 100)bi 和一个小数 c[i](0 \leq c[i] \leq 1c[i](0≤c[i]≤1，c[i]c[i] 最多包含两位小数)。

Output
对于每组数据，输出一个五位小数表示最大的优惠比例。如果小数点后超过五位，四舍五入到五位。

Sample Input
1
2
2 0.5
3 0.1
Sample Output
Copy
0.23077

样例解释
对于第一种套餐，优惠比例为 0.5a / (2a + 0.5a） = 0.2；
对于第二种套餐，优惠比例为 0.9a / (3a + 0.9a） = 9 / 39；

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
using namespace std;

int main() {
    int T,n; scanf("%d",&T);
    while(T--) {
        double b,c,Ans = 0;
        scanf("%d",&n);
        for(int i=1; i<=n; i++){
            scanf("%lf %lf",&b,&c);
            Ans = max(Ans,(1 - c) / (b + (1 - c)));
        }
        printf("%.5lf\n",Ans);
    }
    return 0;
}

Game

Accepts: 1381 Submissions: 2289
Time Limit: 4000/2000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)
Problem Description
Alice 和 Bob 在玩游戏。

桌面上有两堆金币，少的那堆有 xx 个金币，多的那堆有 2x2x 个金币。

假设金币可以被无限细分。Alice 和 Bob 事先都不知道 xx 是几，但是他们都知道 xx 是一个 (0, 1](0,1] 之间均匀分布的随机实数。

Alice 会等概率的被分配到其中的一堆金币，Bob 会得到另一堆。xx 的值和两堆金币的分配是相互独立的。

拿到金币以后，Alice 会马上数清自己拿到多少金币。然后 Alice 可以选择是否和 Bob 那堆换。

给定 Alice 拿到的金币数目，请问 Alice 要不要交换，使得她期望能得到的金币数目更多？

如果交换期望得到的金币数目多于不交换期望得到的金币数目，输出交换，否则不交换。

Input
第一行一个正整数 test~(1 \leq test \leq 200000)test (1≤test≤200000) 表示数据组数。

接下来每行一个小数 p~(0 < p \leq 2)p (0<p≤2)，pp 最多保留五位小数，表示 Alice 拿到的金币数目。

Output
对于每组数据，输出 Yes 表示需要交换，输出 No 表示不要交换。

Sample Input
1
1.00000
Sample Output
Yes

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
int main() {
    int T; scanf("%d",&T);
    while(T--) {
        double d;
        scanf("%lf",&d);
        if(d <= 1.00000) printf("Yes\n");
        else printf("No\n");
    }
    return 0;
}

Permutation

Accepts: 1201 Submissions: 3277
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)
Problem Description
一开始有 nn 个数，他们按 1…n1…n 的顺序排列，要求交换最多 mm 对数字（同一个数字可以参与多次交换），使得逆序对数目最大。

对于一个序列 AA，如果存在正整数 i, ji,j 使得 1 \leq i < j \leq n1≤i<j≤n 而且 A[i] > A[j]A[i]>A[j]，则 \lt A[i], A[j] \gt<A[i],A[j]> 这个有序对称为 AA 的一个逆序对。
Input
第一行一个正整数 test~(1 \leq test \leq 100000)test (1≤test≤100000) 表示数据组数。

对于每组数据，一行两个整数 n，m~(1 \leq n \leq 1000000, 0 \leq m \leq 1000000)n，m (1≤n≤1000000,0≤m≤1000000) 表示数字个数和最多可以交换的数字对数。

Output
对于每组数据，一行一个整数表示答案。

Sample Input
6
1 1
2 0
2 1
3 1
4 1
4 2
Sample Output
Copy
0
0
1
3
5
6

题目分析：
1……n的序列 交换一对 肯定是swap(1,n) 然后由n产生n-1个逆序对，又由于1在最后 在产生n-2个 逆序对， 然后自己推一个公式(n - 1) + (n - 2 * m)) * 2m / 2

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
using namespace std;
// 咱也不知道为什么，n、m的数据范围其实int足够足够的
// 但是不开long long 就挂 开了就A（因为这个没有1A）
// 辛亏昨天有个题就是因为这个这才让我斗胆改成long long 又教了一遍  不然又摸不着头脑了
int main() {
    int T;
    long long n,m;
    scanf("%d",&T);
    while(T--) {
        scanf("%lld %lld",&n,&m);
        if(m >= n / 2) printf("%lld\n",n * (n - 1) / 2);
        else {
            printf("%lld\n",((n - 1) + (n - 2 * m)) * m);
        }
    }
    return 0;
}

Intersection

Accepts: 802 Submissions: 2323
Time Limit: 4000/2000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)
Problem Description
Mr. Left 来到了一个路口，这个路口只能右转，并且都是两车道。

现在在南北向车道上有 nn 辆车，他们都在线 xx 南边，这些车想要通过这个路口，到东边去，具体地说，他们要开到线 yy 东边。

一辆车一个时刻可以从东南西北中选一个方向移动一个位置，或者呆在原地不动。 同一时刻同一位置不能有超过一辆车。车不能开到路外面。

在任意时刻，所有车都同时移动。两辆相邻的车不能都移动到对方的格子上。在此基础上，只要所有车移动后不存在两辆车处于同一位置，移动就合法。

问最少要多少时间，这些车才可以都开到东边？

Input
第一行一个整数 test~(1 \leq test \leq 10)test (1≤test≤10)。

对于每组数据，第一行一个整数 n~(1 \leq n \leq 100000)n (1≤n≤100000)，表示车辆数目。

接下来 nn 行，每行两个整数 x，yx，y 表示车的位置，其中 xx 表示车道 idid（ x=1x=1 表示右车道，x=2x=2 表示左车道），y~(1 \leq y \leq 100000)y (1≤y≤100000) 表示车在路口前第几个位置。

数据保证没有两辆车初始在同一位置。

Output
对于每组数据，一行一个整数表示答案。

Sample Input
2
2
1 1
2 1
2
1 2
2 1
Sample Output
3
4

样例解释
第一组
time 0
…
…
CC
…
time 1
…
CC…
…
…
time2
…
.CC.
…
…
time3
…
…CC
…
…
第二组
time 0
…
…
C.
.C
time 1
…
C…
.C
…
time2
C…
.C…
…
…
time3
.C…
…C.
…
…
time4
…C.
…C
…
…

//狗儿字的丑代码  就是能A
#pragma GCC optimize(3,"Ofast","inline")
#include <bits/stdc++.h>
using namespace std;

typedef unsigned long long ull;
typedef long long LL;

void read(int &x) {
    x = 0;
    char ch = getchar();
    while (ch < '0' || ch > '9') ch = getchar();
    while (ch >= '0' && ch <= '9') {x = x * 10 + ch - 48; ch = getchar();}
}

int n, c[N];
int cnt[3][N];
int pos[3][N];

void Work() {
    scanf("%d", &n);
    for(int i = 1; i <= n; ++i) {
        int x, y;
        scanf("%d%d", &x, &y);
        pos[x][y] = 1;
    }
    int ans = 0;
    for(int i = 1; i <= 100000; ++i) {
        if(pos[1][i]) 
            ans = max(ans, i + 1);
        if(pos[2][i]) {
            if(!pos[1][i+1]) ans = max(ans, i + 2);
            else ans = max(ans, i + 3);
            
        }
    }
    printf("%d\n", ans);

    memset(pos,0,sizeof(pos));
}

int main () {
    int t; read(t);
    for(; t--; ) Work();
    return 0;
}


// 又是Bug小王子加冕的一天，路过的大佬还是不要吝啬呀，不能A，
// 不能A就算了，对拍三千组没出错误
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#define Maxn 100005
using namespace std;
int a[Maxn],b[Maxn];
int main(int argc,char* argv[]) {
    int T,n; scanf("%d",&T);
    while(T--) {
        scanf("%d",&n);
        int suma = 0,sumb = 0;
        for(int id,p,i=1; i<=n; i++) {
            scanf("%d %d",&id,&p);
            if(id == 1) b[++sumb] = p;
            if(id == 2) a[++suma] = p;
        }
        sort(a + 1,a + suma + 1);
        sort(b + 1,b + sumb + 1);
        int Ans = -2147483647;
        if(a[suma] == b[sumb]) Ans = max(a[suma] + 3 - 1,Ans);
        else if(a[suma] - b[sumb] == -1 ) Ans = max(a[suma] - 1 + 4,Ans);
        else Ans = max(max(a[suma],b[sumb]) - 1 + 2,Ans);
        printf("%d\n",Ans);
    }


    return 0;
}

附上造数据和对拍代码

#include<cstdio>
#include<ctime>
#include<cstring>
#include<iostream>
#include<cstdlib>

using namespace std;
int vis[100005][2];
int main(int argc,char* argv[]) {
	freopen("1.in","w",stdout);
	srand(time(0));
	int T = 1; printf("%d\n",T);
	while(T--) {
		int n = rand() % 1000 + 1;
		printf("%d\n",n);
		memset(vis,0,sizeof(vis));
		int op = 1;
		while(n){
			int k = rand() % 1200 + 1; 
			while(vis[k][op]) k = rand() % 10000 + 1;
			printf("%d %d\n",op,k);
			vis[k][op] = 1;
			n--;
			if(op == 1) op = 2;
			else if(op == 2) op = 1;
		}
	} 
	
	
	return 0;
}

#include<cstdio>
#include<cstring>
#include<windows.h>

using namespace std;

int main(int argc,char* argv[]) {
	int T = 20000;
	while(T--) {
		system("data.exe");
		system("std.exe");
		system("main.exe" );
		if(system("fc 1.out 2.out"))   { printf("ERROE!"); break; }
	}
	
	
	return 0;
}

亲手写的Bug，而你在对岸等我勇敢，过了很久终于我愿抬头看，看了看还是没看见,

Fight

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 282 Accepted Submission(s): 68

Problem Description
Mr Left，Mr Mid，Mr Right 正在玩游戏。他们初始都有 1000 血，Mr Left，Mr Mid，Mr Right 的攻击力分别为 x，y，z。
对于每一轮，假设仍然剩下至少两个人的血量大于 0，那么选出两个血量大于 0 的人对打，他们的血量分别扣除和他们对打的另一个人的攻击力。

当有至少两个人的血量小于等于 0 时，游戏结束。
请问在最优情况下，这个游戏最少多少轮结束？
Input
第一行一个正整数 test (1≤test≤100) 表示数据组数。
接下来 test 行，每行三个正整数 x，y，z (1≤x，y，z≤1000) 表示 Mr Left, Mr Mid, Mr Right的攻击力。

Output
对于每组数据，一行一个整数表示答案。

Sample Input
2
1 1 1
1 2 3

Sample Output
1000
666

Source
2020 年百度之星·程序设计大赛 - 初赛三

题目分析：

  • 枚举两两之间打了多少次，取最小，注意细节
  • 官方题解：枚举Left 、Mid 和Left、Right之间打了多少轮，那么Right和Mid之间还要打多少轮是能算出来的，这样O（N^3） 直接O（N ^2）了，但是官方解法 我没写 😏
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>

using  namespace std;

inline int Read(int &x) {
    x = 0; char c = getchar(); int f = 1;
    while(c < '0' || c > '9') {
        if(c == '-') f = -1;
        c = getchar();
    }
    while (c >= '0' && c <= '9') { x = x * 10 + c - '0'; c = getchar(); }
}

int main(int argc,char* argv[]) {
    int T,n,m,a[3];
    scanf("%d",&T);
    while(T--) {
        for(int i=0; i<3; i++) scanf("%d",&a[i]);
        sort(a,a+3);
        int x = a[1],y = a[2],z = a[0];//
        int sx = 1000 / x + (1000 % x != 0),sy = 1000 / y + (1000 % y != 0),sz = 1000 / z + (1000 % z != 0);
        int Ans = 3000;
        for(int i=0; i<=min(sx,sy); i++){
            for(int j=0; j<=min(sx,sz); j++) { // ac 打j次
                int dama = y * i + j * z;
                for(int k=0; k<=min(sy,sz); k++){// bc 打k次
                    int damb = z * k + i * x;
                    int damc = j * x + k * y;
                    int cnt = 0;
                    if(dama >= 1000) cnt++;
                    if(damb >= 1000) cnt++;
                    if(damc >= 1000) cnt++;
                    if(cnt >= 2) {// 最后应该是能出现两个人同归于尽的情况
                        Ans = min(Ans,i + j + k);
                        break;
                    }
                }
                if(dama >= 1000) break;
            }
            if(i * x >= 1000) break;
        }
        printf("%d\n",Ans);
    }

    return 0;
}
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)

百度之星2020 初赛第三场 的相关文章

随机推荐

  • 从头用脚分析FFmpeg源码 - avcodec_send_frame | avcodec_receive_packet

    avcodec send frame和avcodec receive packet 作用 相对应avcodec send packet avcodec receive frame而言 xff0c avcodec send frame xff

  • Debian系统解决中文乱码问题

    1 安装locales apt get install locales 2 设置语言选项 dpkg reconfigure locales 选择如下四项 xff1a zh CN GB2312zh CN GBK GBKzh CN UTF 8

  • raspbian-buster安装php7.3

    安装php sudo apt get install php7 3 fpm php7 3 curl php7 3 gd php7 3 mbstring php7 3 mysql php7 3 imap php7 3 opcache php7

  • Linux下查看服务器各硬件信息

    span class hljs comment 内存 span span class hljs preprocessor free m span span class hljs preprocessor cat proc meminfo s

  • Day2、Hive json_tuple性能比get_json_object更高吗？为什么？

    目录 一 执行过程 二 源码比较 三 实验论证 四 总结 在对离线任务进行优化时 xff0c 一般来说有两种思路 一是参数优化 xff0c 尽量提高CPU 内存利用率 xff0c 或者减少spill率 xff1b 二是SQL优化 xff0c

  • Ubuntu18.04下更改apt源

    任意版本的系统代号 xff1a Ubuntu 12 04 LTS 代号为precise Ubuntu 14 04 LTS 代号为trusty Ubuntu 15 04 代号为vivid Ubuntu 15 10 代号为wily Ubuntu

  • C语言中数的二进制、八进制、十进制以及十六进制表示及输出

    以十进制数163为例 xff1a 二进制的英文是Binary xff0c 简写为B或BIN xff0c 所以163 61 0b10100011 xff08 前面加上 0b 或 0B xff09 八进制的英文是Octal xff0c 简写为O

  • java-字符串数组排序

    问题 43 代码 xff1a 创建一个长度是8的字符串数组 使用8个长度是5的随机字符串初始化这个数组 对这个数组进行排序 xff0c 按照每个字符串的首字母排序 无视大小写 注1 xff1a 不能使用Arrays sort 要自己写 注2

  • python 装饰器

    1 装饰器 装饰器 Decorators 是Python的一个重要部分 简单地说 xff1a 他们是修改其他函数的功能的函数 他们有助于让我们的代码更简短 xff0c 也更Pythonic xff08 Python范儿 xff09 大多数初

  • Java的俩个list之间比较，判断是否一致的方法

    前文 我看了一篇博客 xff0c 是关于判断俩个list的 看完之后我觉得可能并不是很好 结合他的思路 xff0c 我重新整理了一下代码 同时也看了看String中的equals的实现 原文是 xff1a https blog csdn n

  • ARP地址解析过程（同一子网和不同子网）

    人们最熟悉的网络可以说是以太网 xff0c 而且人们都知道 xff0c 每块网卡都有一个编号 xff0c 也就是网卡地址 xff08 称为MAC地址 xff09 xff0c 代表计算机的物理地址 另外 xff0c 网络中的每一台计算机都分配

  • （2）树莓派3B连接隐藏wifi网络

    连接隐藏wifi可以使用nano编辑器打开wpa supplicant配置文件 xff1a sudo nano etc wpa supplicant wpa supplicant conf 在文件底部添加 xff1a network 61

  • 获取本地外网ip的api接口

    开发时偶尔会需要前端传客户端的ip地址 xff0c 以下方法可以获取客户端外网ip 1 新增加载js方法 export const loadScript 61 src 61 gt return new Promise resolve rej

  • Ubuntu 18.04 配置ibus中文拼音输入法

    Ubuntu 18 04系统想安装中文输入法 xff08 利用ibus输入法配置 xff09 只要三步 注意 xff1a 你的Ubuntu需要可以上网 xff01 xff01 xff01 因为要下载一系列安装包 第一步 xff1a 首先需要

  • VMware安装Kali后黑屏 只有左上角光标

    在安装过程中选择安装GRUB引导程序 xff0c 默认是否 xff0c 我们需要选择是

  • vCenter Server目录/storage/core，/storage/log 空间不足问题解决

    概述 xff1a VC是7 0的 xff0c 存储警告 storage core及 storage log目录空间不足 xff1b 且出现VC web管理页面运行缓慢 xff1b 用途概述 storage core xff1a 存储来自vC

  • C#反编译利器--dotPeek

    在开发项目的时候 xff0c 当项目数量变大 xff0c 源代码管理也是一件非常头疼的事 xff0c 如果没有专门的人员来管理代码 xff0c 没有code review机制的话 xff0c 代码很容易乱 xff0c 这就会导致现场的代码与

  • C/C++调用Rust编写的动态库

    目录 C C 43 43 调用Rust编写的动态库一 背景二 解决方案三 测试3 1 正确性检验3 2 内存安全检验 C C 43 43 调用Rust编写的动态库 一 背景 Rust通过大量的编译期检查能够有效避免程序运行时出现的各种内存问

  • 计蒜客习题-班长竞选 最小割 “二选一 方案不同有额外开销”模型

    设源点S xff0c 汇点T 对于所有赞成的人 从S连一条边到他们对应的点上 容量设为1 对于所有反对的人 从他们对应的点上连一条边到T 容量为1 对于所有有朋友 关系的a和b 在他们之间连一条无向边 容量为1 最小割可以用dinic跑出来

  • 百度之星2020 初赛第三场

    Discount Accepts 1432 Submissions 2728 Time Limit 2000 1000 MS Java Others Memory Limit 65536 65536 K Java Others Proble

热门标签