看完二分法，做完例题

二分 三分 学习

最小生成树 题目描述 小 A 有一张 n 个点的带权无向图，这张无向图非常特别，首先第 i 个点有一个点权 ai，之后这张无向图是一张完全图，且边 (u,v) 的权值为 au+av 现在小 A 想找一个这张图的边权之和最小的生成树，需要你来帮帮他 可以用prim算法跑出来最小生成树，但是仔细想可以用贪心的思路： 将点权从小到大排序，a[1]和其他各点连接就是最小生成树 #pragma GCC optimize (3) #include<bits/stdc++.h> using namespace std; typedef long long ll; #define js ios::...

E题：「水」悠悠碧波 仔细读题后发现是一种求子串的题，可能会涉及KMP算法， 但是萌新表示不会KMP算法/(ㄒoㄒ)/~~ 又想很快解出这道题，试了试C++ string自带的find函数（经过查询资料得知find函数使用的不是KMP算法，而是低效的逐个匹配的算法，如有错误请更正） 我们只需要枚举子串的长度，然后处理即可，具体细节见代码 #include<bits/stdc++.h> using namespace std; int main(){ string s; cin>>s; string ans; int len=s.length(); //枚举子串的长度，最...

D题（绝地求生pubg）： 这题显然是要我们求x,y的最小公倍数，求最小公倍数的公式我们都知道，是x*y/gcd(x,y)，故直接套用公式即可 为了防止出现爆long long 问题，我在这次题中用了java的bigInteger类，当然C++的话处理得当也可以AC import java.math.BigInteger; import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner in=new Scanner(System.in); BigInteger x,y,...

题意：现在我们要把1…n这n个数字首尾连接组成一个环，使得相邻元素互质的对数尽可能多。请输出最大对数。 1-n的数字连成一个环，显然如果这些数字从小到大顺次排列，相邻数字之间只差1，则相邻数互质的可能性最大， 又因为1和任何数都互质，所以答案就是直接按顺序排列 #include<bits/stdc++.h> using namespace std; int main(){ int n; cin>>n; cout<<n; }

题目描述 你要买n件物品，其中有一些是凳子。 商场正在举行促销活动，如果购物车中有至少一个凳子，那么你可以半价购买这个购物车中最贵的一个物品。 你有m辆购物车，请最小化你的花费。 输入描述: 第一行一个整数t表示数据组数 (1 ≤ t ≤ 100)。 每组数据第一行两个整数n,m (1 ≤ n,m ≤ 1000)，接下来n行每行两个整数ai,bi，分别表示第i件物品的价格以及它是否是凳子 (1 ≤ ai ≤ 105, 0 ≤ bi ≤ 1)。输出描述: 每组数据输出一行一个实数表示最小花费，保留一位小数。输入 2 5 1 1 0 2 1 3 1 4 0 5 0 5 10 1 0 2 1 3 1...

https://ac.nowcoder.com/acm/contest/6173/D 题目描述 为了准备一个独特的颁奖典礼，组织者在会场的一片矩形区域（可看做是平面直角坐标系的第一象限）铺上一些矩形地毯。一共有n张地毯，编号从1到n。现在将这些地毯按照编号从小到大的顺序平行于坐标轴先后铺设，后铺的地毯覆盖在前面已经铺好的地毯之上。地毯铺设完成后，组织者想知道覆盖地面某个点的最上面的那张地毯的编号。注意：在矩形地毯边界和四个顶点上的点也算被地毯覆盖。 输入描述: 第一行，一个整数n，表示总共有n张地毯。 接下来的n行中，第i+1行表示编号i的地毯的信息，包含四个正整数a，b，g，k，每两个整数之...