牛客练习赛96比赛地址
A – 小y的平面
签到题,将所有的坐标按照左端点排序,然后遍历一遍查有没有纵坐标递减的情况,如果没有答案为YES, 有答案为NO (这题数据应该是出水了,不用排序也能过)
#include <iostream>
#include <algorithm>
#include <queue>
#include <cmath>
#include <cstring>
using namespace std;
typedef long long ll;
const int N = 1e6 + 10;
struct Node{
int x, y;
}a[N];
bool cmp(Node u, Node v)
{
if(u.x != v.x) return u.x < v.x;
else return u.y < v.y;
}
int main()
{
int n;
cin >> n;
for (int i = 1; i <= n; i ++ ){
cin >> a[i].x >> a[i].y;
}
sort (a + 1, a + 1 + n, cmp);
for (int i = 1; i < n; i ++ ){
if(a[i].y > a[i + 1].y){
cout << "NO" << endl;
return 0;
}
}
cout << "YES" << endl;
}
B – 小y的树
最容易想到的应该是按层枚举每层提供的权值,但是这样太复杂了。这里提供一种更简单的方法 – 计算每条边经过的次数,即位答案。
用最简单的四层满二叉树来举例子: 要计算一条边的经过次数, 即为 该边以下所有节点的个数 * 除了该边以下的所有节点的个数
例如 : 第二层所有边经过次数 = 7 * 8 * 2 = 112 第三层所有边经过次数 = 12 * 3 * 4 = 144 第四层所有边经过次数 = 1 * 14 * 8 = 112
用sum数组记录一个前缀和 表示前i层所有节点的个数 用cnt数组记录每一层的节点个数
而我们可以观察到 第i层的边以下所有的点就等于sum[n - i + 1] 所以每一层所有边提供的权值为 : cnt[i] * (sum[n] - sum[n - i + 1]) * sum[n - i + 1]
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;
const int N = 1e6 + 10, mod = 1e9 + 7;
ll cnt[N] ,sum[N];
int main()
{
int n, k;
cin >> n >> k;
cnt[1] = 1, sum[1] = 1;
for (int i = 2; i <= n; i ++ ){
cnt[i] = (cnt[i - 1] * k) % mod;
sum[i] = (sum[i - 1] + cnt[i]) % mod;
}
long long ans = 0;
for (int i = 2; i <= n; i ++ ){
ans += cnt[i] % mod * (sum[n] - sum[n - i + 1] + mod) % mod * sum[n - i + 1];
ans %= mod;
}
cout << ans << endl;
}
C – 小y的序列
一道RMQ二分查询的题目,将RMQ算法掌握之后这题就很简单
该题的一个性质:固定左端点后,右端点往后移,区间内最大值减最小值是单调递增的
我们遍历固定每个左端点 i,去查找从左端点开始, 二分查找最大值减最小值为k的右端点r,然后r - i就为区间个数
#include <iostream>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
const int N = 1e6 + 10;
int n, k;
int a[N];
int fx[N][30], fi[N][30];
void init()
{
for (int j = 1; j < 22; j ++ ){
for (int i = 1; i + (1 << j) - 1 <= n; i ++ ){
fx[i][j] = max(fx[i][j - 1], fx[i + (1 << (j - 1))][j - 1]);
fi[i][j] = min(fi[i][j - 1], fi[i + (1 << (j - 1))][j - 1]);
}
}
}
int check(int l, int r)
{
int p = log2(r - l + 1);
int s = max(fx[l][p], fx[r - (1 << p) + 1][p]) - min(fi[l][p], fi[r - (1 << p) + 1][p]);
return s;
}
int main()
{
cin >> n >> k;
for (int i = 1; i <= n; i ++ ){
cin >> a[i];
fx[i][0] = a[i], fi[i][0] = a[i];
}
init();
long long ans = 0;
for (int i = 1; i <= n; i ++ ){
int l = i, r = n;
while (l < r){
int mid = l + r >> 1;
if(check(i, mid) < k) l = mid + 1;
else r = mid;
}
int left = l;
if(check(i, left) != k) continue;
l = i, r = n;
while (l < r){
int mid = l + r + 1 >> 1;
if(check(i, mid) <= k) l = mid;
else r = mid - 1;
}
ans += l - left + 1;
}
cout << ans << endl;
}
|