当前位置:网站首页>牛客小白月赛52 E.分组求对数和(二分&容斥)
牛客小白月赛52 E.分组求对数和(二分&容斥)
2022-07-07 01:25:00 【Harris-H】
牛客小白月赛52 E.分组求对数和(二分&容斥)
先用数组存所有数,然后再用二维vector存每个组的数。
根据容斥思想,对于每个数就先二分找到所有满足的个数然后减掉自己组里的。
自己组里的就是在对应的vector里的二分。
时间复杂度: O ( m l o g m ) O(mlogm) O(mlogm)
#include <bits/stdc++.h>
using namespace std;
#define ll long long
int n, k;
vector<int> ve[1000009], a;
void solved() {
scanf("%d%d", &n, &k);
int m;
for(int i = 0; i < n; i ++) {
scanf("%d", &m);
int x;
while(m --) {
scanf("%d", &x);
ve[i].push_back(x);
a.push_back(x);
}
sort(ve[i].begin(), ve[i].end());
}
sort(a.begin(), a.end());
ll ans = 0;
for(int i = 0; i < n; i ++) {
m = ve[i].size();
for(int j = 0; j < m; j ++) {
int x = ve[i][j], y = k - x;
ans +=
(a.end() - upper_bound(a.begin(), a.end(), y - 1)) -
(ve[i].end() - upper_bound(ve[i].begin(), ve[i].end(), y - 1));
}
}
ans /= 2;
cout << ans % 998244353;
}
int main() {
// int ttx; cin >> ttx; while(ttx --)
solved();
return 0;
}
边栏推荐
- [cloud native] what is the microservice architecture?
- [daily training -- Tencent selected 50] 235 Nearest common ancestor of binary search tree
- 苹果cms V10模板/MXone Pro自适应影视电影网站模板
- 软件测试的几个关键步骤,你需要知道
- Introduction to the extension implementation of SAP Spartacus checkout process
- ML之shap:基于adult人口普查收入二分类预测数据集(预测年收入是否超过50k)利用shap决策图结合LightGBM模型实现异常值检测案例之详细攻略
- Senior programmers must know and master. This article explains in detail the principle of MySQL master-slave synchronization, and recommends collecting
- Qt多线程的多种方法之一 QThread
- 改变ui组件原有样式
- win系统下安装redis以及windows扩展方法
猜你喜欢
Interview questions and salary and welfare of Shanghai byte
Understand the deserialization principle of fastjson for generics
C note 13
yarn入门(一篇就够了)
一个简单的代数问题的求解
SAP Spartacus checkout 流程的扩展(extend)实现介绍
Find duplicate email addresses
外设驱动库开发笔记43:GPIO模拟SPI驱动
Convert numbers to string strings (to_string()) convert strings to int sharp tools stoi();
一名普通学生的大一总结【不知我等是愚是狂,唯知一路向前奔驰】
随机推荐
为不同类型设备构建应用的三大更新 | 2022 I/O 重点回顾
PTA TIANTI game exercise set l2-003 moon cake test point 2, test point 3 Analysis
postgresql 数据库 timescaledb 函数time_bucket_gapfill()报错解决及更换 license
How much do you know about clothing ERP?
SQL Server 2008 各种DateTime的取值范围
[cloud native] what is the microservice architecture?
SubGHz, LoRaWAN, NB-IoT, 物联网
【FPGA教程案例13】基于vivado核的CIC滤波器设计与实现
Rk3399 platform development series explanation (WiFi) 5.53, hostapd (WiFi AP mode) configuration file description
Vscode for code completion
JVM命令之 jstack:打印JVM中线程快照
Introduction to the extension implementation of SAP Spartacus checkout process
PTA 天梯赛练习题集 L2-004 搜索树判断
软件测试知识储备:关于「登录安全」的基础知识,你了解多少?
Financial risk control practice - decision tree rule mining template
Change the original style of UI components
3531. 哈夫曼树
Dc-7 target
云加速,帮助您有效解决攻击问题!
ML's shap: Based on the adult census income binary prediction data set (whether the predicted annual income exceeds 50K), use the shap decision diagram combined with the lightgbm model to realize the