当前位置:网站首页>Niuke monthly race - logarithmic sum in groups
Niuke monthly race - logarithmic sum in groups
2022-07-01 22:39:00 【A Fusu in the mountains】
Original link
Title Description
The children in Niuniu kindergarten are playing games .
Kindergarten co ownership n Two children , The first i Children have s i s_i si A digital , The first i The number in the hands of a child jj The number is recorded as a i j ( 1 ≤ j ≤ s i ) a_{ij}(1\leq j \leq s_i) aij(1≤j≤si).
Now teacher Niuniu wants to know how many different ways to take a number from two different children to make the sum of the numbers greater than or equal k ?
Because there may be many possible ways , So you just need to tell Niuniu about the numerical simulation of this scheme 998244353 Then the result will be ok ( The answers made up of the same number in the hands of the same child are regarded as different ).
sample input
3 7
4 2 3 1 5
2 4 1
2 8 2
sample output
9
Algorithm
( The principle of tolerance and exclusion + Two points search )
The first thing that comes to mind in this topic is pop search enumeration , Enumerate and search all the sum greater than k The possibility of , But it will obviously time out , It's a square level of complexity
therefore , We can think of , This topic k Already given , So we only ask for each number and k How many numbers are there that have a greater difference between , Then it's not difficult to think of sorting first and then using binary search .
Because each number search cannot contain this group of numbers , We can find two intervals each time , Subtract the number of cells from the number of large interval searches , Finally, accumulation is the answer .
C++ Code
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;
typedef long long ll;
const int N = 1e6 + 10;const ll mod = 998244353;
int main()
{
ll n,k,cnt;
cin >> n >> k;
vector<ll> v[N],all;
for (int i = 0;i < n;i ++ ) {
int m;
cin >> m;
for (int j = 0;j < m;j ++ ) {
int x;
cin >> x;
v[i].push_back(x);
all.push_back(x);
cnt ++;
}
sort(v[i].begin() , v[i].end());
}
sort(all.begin(),all.end());
ll res = 0,t1 = 0,t2 = 0;
for (int i = 0;i < n;i ++ ) {
for (int j = 0;j < v[i].size();j ++ ) {
t1 = 0,t2 = 0;
t1 = lower_bound(v[i].begin(),v[i].end(),k - v[i][j]) - v[i].begin();
t1 = (ll)v[i].size() - t1;
t2 = lower_bound(all.begin(),all.end(),k - v[i][j]) - all.begin();
t2 = cnt - t2;
//cout << t2 << ' ' << t1 << '\n';
res = (res + t2 - t1) % mod;
}
}
cout << res / 2 << '\n';
return 0;
}
边栏推荐
- Qtreeview+qabstractitemmodel custom model: the third of a series of tutorials [easy to understand]
- Wechat open platform scanning code login [easy to understand]
- A debugging to understand the slot mechanism of redis cluster
- RestTemplate 远程调用工具类
- 【MySQL】数据库优化方法
- Basic knowledge of ngnix
- Separate the letters and numbers in the string so that the letters come first and the array comes last
- YOLOv5.5 调用本地摄像头
- Mask wearing detection method based on yolov5
- Little p weekly Vol.11
猜你喜欢
Copy ‘XXXX‘ to effectively final temp variable
91.(cesium篇)cesium火箭发射模拟
Basic knowledge of ngnix
flink sql-client 使用 对照并熟悉官方文档
C#/VB.NET 给PDF文档添加文本/图像水印
Object memory layout
Kubernetes创建Service访问Pod
删除AWS绑定的信用卡账户
黑马程序员-软件测试--06阶段2-linux和数据库-01-08第一章-linux操作系统阶段内容说明,linux命令基本格式以及常见形式的说明,操作系统的常见的分类,查看命令帮助信息方法,
Recent public ancestor (LCA) online practices
随机推荐
地图其他篇总目录
Mask wearing detection method based on yolov5
MySQL中对于索引的理解
Dark horse programmer - software testing - stage 06 2-linux and database-01-08 Chapter 1 - description of the content of the Linux operating system stage, description of the basic format and common fo
Use of vscode
快乐数[环类问题之快慢指针]
从零开始学 MySQL —数据库和数据表操作
Airserver mobile phone third-party screen projection computer software
Recent public ancestor offline practice (tarjan)
Measurement of reference loop gain and phase margin
指标陷阱:IT领导者易犯的七个KPI错误
Slope compensation
详解Volatile关键字
Mysql——》Innodb存储引擎的索引
[STM32] stm32cubemx tutorial II - basic use (new projects light up LED lights)
Gaussdb (DWS) active prevention and troubleshooting
Easyexcel complex data export
#yyds干货盘点# 解决名企真题:扭蛋机
微信开放平台扫码登录[通俗易懂]
Indicator trap: seven KPI mistakes that it leaders are prone to make