当前位置:网站首页>(POJ - 3685) matrix (two sets and two parts)
(POJ - 3685) matrix (two sets and two parts)
2022-07-06 16:08:00 【AC__ dream】
Chinese question meaning : There is one N Square matrix The first i That's ok ,j The value of the column Aij =i^2 + 100000 × i + j^2 - 100000 × j + i × j, We need to find out the third part of this matrix M Small value .
Looking at this equation first, we can find ,Aij along with i To increase by , So we can pass two points x To find out , The content of every two points is to judge the ratio x Whether the number of small numbers is greater than or equal to m, If the number is greater than or equal to m, Then the current binary value is greater than or equal to the answer , On the contrary, the current binary value is less than the answer , The specific dichotomy process is as follows :
We enumerate columns violently , The number of each column is monotonically increasing , So for each column, we can enumerate in two , The total complexity is n*log(n)*log(q)(q Is the range size of the possible values of the answer ), There are quite a lot of details , The code is attached below
#include<cstdio>
#include<iostream>
#include<cstring>
#include<vector>
#include<algorithm>
#include<map>
#include<cmath>
#include<queue>
using namespace std;
typedef long long ll;
ll n,m;
ll cal(ll i,ll j)
{
return i*i+100000*i+j*j-100000*j+i*j;
}
bool check(ll x)// If it is less than or equal to x The number of is greater than or equal to m One returns true, Instead, return to false
{
ll cnt=0;
for(int i=1;i<=n;i++)// Enumerating columns
{
ll l=0,r=n,mid;// Binary enumeration, each column is less than x The number of numbers
if(l==r) return cal(1,1)<=x;
while(l<r)
{
mid=l+r+1>>1;
if(cal(mid,i)<=x) l=mid;// Find a value greater than or equal to x The last number of
else r=mid-1;
}
cnt+=l;
if(cnt>=m) return true;
}
return false;
}
int main()
{
int T;
cin>>T;
while(T--)
{
cin>>n>>m;
ll l=-9999999999,r=9999999999,mid;// Enumerator
while(l<r)
{
mid=l+r>>1;
if(check(mid)) r=mid;// explain mid Larger
else l=mid+1;
}
printf("%lld\n",l);
}
return 0;
}
边栏推荐
- 1005. Maximized array sum after K negations
- 树莓派4B安装opencv3.4.0
- Essai de pénétration (1) - - outils nécessaires, navigation
- 基于web的照片数码冲印网站
- Analyse du format protobuf du rideau en temps réel et du rideau historique de la station B
- The concept of C language array
- Vs2019 initial use
- 渗透测试 ( 7 ) --- 漏洞扫描工具 Nessus
- 【练习-8】(Uva 246)10-20-30==模拟
- Find 3-friendly Integers
猜你喜欢
7-1 懂的都懂 (20 分)
Penetration test (7) -- vulnerability scanning tool Nessus
TCP's three handshakes and four waves
渗透测试 ( 4 ) --- Meterpreter 命令详解
Essai de pénétration (1) - - outils nécessaires, navigation
Programmers, what are your skills in code writing?
信息安全-史诗级漏洞Log4j的漏洞机理和防范措施
Quick to typescript Guide
渗透测试 ( 5 ) --- 扫描之王 nmap、渗透测试工具实战技巧合集
628. Maximum product of three numbers
随机推荐
Data storage in memory & loading into memory to make the program run
China's peripheral catheter market trend report, technological innovation and market forecast
X-Forwarded-For详解、如何获取到客户端IP
Differential (one-dimensional, two-dimensional, three-dimensional) Blue Bridge Cup three body attack
mysql导入数据库报错 [Err] 1273 – Unknown collation: ‘utf8mb4_0900_ai_ci’
Find 3-friendly Integers
Opencv learning log 28 -- detect the red cup cover
MySQL grants the user the operation permission of the specified content
Essai de pénétration (1) - - outils nécessaires, navigation
nodejs爬虫
Pyside6 signal, slot
1323. Maximum number of 6 and 9
TCP's three handshakes and four waves
Luogu P1102 A-B number pair (dichotomy, map, double pointer)
“鬼鬼祟祟的”新小行星将在本周安全掠过地球:如何观看
Opencv learning log 27 -- chip positioning
【练习-2】(Uva 712) S-Trees (S树)
Frida hook so layer, protobuf data analysis
渗透测试 ( 2 ) --- 渗透测试系统、靶机、GoogleHacking、kali工具
921. Minimum additions to make parentheses valid