牛客练习赛72-C brz的序列 (下凸壳，斜率优化) 题面： 思路： 我们可以推理出如下规律： 选择任意，可以使变为首项为，尾项为的等差数列。 那么本题转化为了选择若干个，作为等差数列的首尾相，使总和最小。 为了更好的解决该问题，我们把数，转为二维平面中坐标为 的点， 那么根据等差数列的性质可以得知，等差数列的公差为数列中两项对应在二维平面上两点的斜率。 通过分析可以发现，将点集维护成下凸壳（凸包的下半部分，见下图）的形式可以使答案最优。 蓝色的点是下凸壳，红色的点是应该从点集中踢出的点。 那么我们用一个栈来维护递增的斜率即可。 代码： #include <iostream>...

牛客练习赛71 B-烙印 （几何） 题面： 思路： 设代表数据中给出的角的个数， 那么我们不妨对为进行分类讨论处理： 如果给出角度之和大于180，则答案为0. 当，即数据给定的是三个边的长度， 那么我们只需要判断三个边是否构成三角形即可，若构成则答案为1，否则答案为0. 判断的方法有很多种，比较好写的是判断三个边的和是否大于三个边中最大值的二倍。 当，即数据给定的是两个边的长度， 我们将给定的角转化为角， 如果角 的对边 的没有给出，那么两边夹一角唯一确定一个三角形。 否则对面给出了: 如果，即该角度为直角或钝角，根据大边对大角的性质，对边 要大于给出的另外一个边。 角的话，判断...

水逆退散

[Educational Codeforces Round 56 (Rated for Div. 2)] —G. Multidimensional Queries（二进制状压，线段树） G. Multidimensional Queries time limit per test 6 seconds memory limit per test 512 megabytes input standard input output standard output You are given an array aa of nn points in kk-dimensional sp...

哈尔滨理工大学软件与微电子学院程序设计竞赛（同步赛）(AK题解) A-Race 思路： 按照题意模拟一下即可。 代码： int v1, v2, t, s, l; int main() { #if DEBUG_Switch freopen("C:\\code\\input.txt", "r", stdin); #endif //freopen("C:\\code\\output.txt","r",stdin); cin >> v1 >> v2 >> t &...

P3400 仓鼠窝 题目描述 萌萌哒的Created equal是一只小仓鼠，小仓鼠自然有仓鼠窝啦。 仓鼠窝是一个由nm个格子组成的行数为n、列数为m的矩阵。小仓鼠现在想要知道，这个矩阵中有多少个子矩阵！（实际上就是有多少个子长方形嘛。）比如说有一个23的矩阵，那么11的子矩阵有6个，12的子矩阵有4个，13的子矩阵有2个，21的子矩阵有3个，22的子矩阵有2个，23的子矩阵有1个，所以子矩阵共有6+4+2+3+2+1=18个。 可是仓鼠窝中有的格子被破坏了。现在小仓鼠想要知道，有多少个内部不含被破坏的格子的子矩阵！ 题意： 给定一个\(n*m\)的01矩阵，让你计算有多少个子矩阵...

Codeforces Round #628 (Div. 2)] D-Ehab the Xorcist 题意： 给定两个整数\(u,v(0 \le u,v \le 10^{18})\) 让你构造一个长度\(\mathit n\)最小的数组\(arr\)，使其： 1、\(arr_1 \oplus arr_2 \oplus \dots \oplus arr_n=u\) 2、\(\sum_{i=1}^n arr_i= v\) 不存在这个数组就输出“-1”。 思路： 先考虑不存在的情况： 1、当\(u>v\)时，一定不存在，因为异或是不进位的加法，不可能一群数异或起来比加起来还大...

牛客练习赛65 - A 最值序列 (贪心) 链接：https://ac.nowcoder.com/acm/contest/5961/A来源：牛客网 题目描述 给一个长度为n的序列aia_iai，一开始你有一个数A = 0，每次可以从序列中选一个数b，令A = A + b或者A = A * b，每个数都要使用一次，加的次数要和乘的次数相同，要求最大化A，输出A对998244353取模的值 思路： 贪心思路： 将数组排序一下，前个一定是加起来，后个，如果大于1就乘，否则就加。 证明： 假设前个中有个数为乘骑来，那么一定会让后个中某个数是加起来， 因为那么，所以假设不是最优。 代码： int n...

牛客练习赛65 - C 二维动点 （几何，思维） 链接：https://ac.nowcoder.com/acm/contest/5961/C来源：牛客网 题目描述 一个二维平面上有n个点(ai,bi)(a_i,b_i)(ai,bi)，在一次移动中，你可以选择一个不和当前所在位置重叠的点，然后可以移动到当前所在位置和选择的点构成的直线上的任何一个位置；每次询问一个点(x,y)，求出从(0,0)到达(x,y)所需要的最少移动次数，无解输出-1 输入描述: 第一行为两个数n，q 接下来n行，每行两个数ai,bia_i,b_iai,bi，表示一个点的坐标 接下来q行，每行两个数xi,yix_i,y_...

牛客练习赛65 - C 二维动点 （几何，思维） 链接：https://ac.nowcoder.com/acm/contest/5961/C 来源：牛客网 题目描述 一个二维平面上有n个点(ai,bi)(a_i,b_i)(ai,bi)，在一次移动中，你可以选择一个不和当前所在位置重叠的点，然后可以移动到当前所在位置和选择的点构成的直线上的任何一个位置；每次询问一个点(x,y)，求出从(0,0)到达(x,y)所需要的最少移动次数，无解输出-1 输入描述: 第一行为两个数n，q 接下来n行，每行两个数ai,bia_i,b_iai,bi，表示一个点的坐标 接下来q行，每行两个数xi,yix...

[2015 HIAST Collegiate Programming Contest] 题解（AK） 简单的题或者我队友ac的题目没有写思路，只贴了代码， 自己ac的题目把题意和思路都说了一下，也贴上了代码。 [A - Who is the winner?] #include <bits/stdc++.h> using namespace std; typedef long long LL; const int N = 2e5 + 10; #define fi first #define se second #define pb push_back #define mp m...