7021

kai_35

AC别闹
cornelia.

sealt

Lqi
XZ916
zeng9999jian
kzyz
uboat2022

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <vector>

const int N = 1010;
const double eps = 1e-6, inf = 1e10;

typedef std::pair<double, double> PDD;

int n, d;
PDD seg[N];

int main()
{
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr); std::cout.tie(nullptr);

std::cin >> n >> d;
bool ok = true;

for(int i = 0;i < n;i ++)
{
double x, y;
std::cin >> x >> y;

if(y > d)
{
ok = false;
break;
}
double r = sqrt(d * d - y * y);
seg[i] = {x + r, x - r};
}

if(ok)
{
std::sort(seg, seg + n);
int res = 0;
double last = -inf;
for(int i = 0;i < n;i ++)
{
if(seg[i].second > last + eps)
{
res ++;
last = seg[i].first;
}
}

std::cout << res << '\n';
}
else puts("-1");

return 0;
}


#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

const int N = 11, M = 110;

int P;
int f[N][10][M];

int mod(int x, int y)
{
return (x % y + y) % y;
}

void init()
{
memset(f, 0, sizeof f);

for (int i = 0; i <= 9; i ++ ) f[1][i][i % P] ++ ;

for (int i = 2; i < N; i ++ )
for (int j = 0; j <= 9; j ++ )
for (int k = 0; k < P; k ++ )
for (int x = 0; x <= 9; x ++ )
f[i][j][k] += f[i - 1][x][mod(k - j, P)];
}

int dp(int n)
{
if (!n) return 1;

vector<int> nums;
while (n) nums.push_back(n % 10), n /= 10;

int res = 0;
int last = 0;
for (int i = nums.size() - 1; i >= 0; i -- )
{
int x = nums[i];
for (int j = 0; j < x; j ++ )
res += f[i + 1][j][mod(-last, P)];

last += x;

if (!i && last % P == 0) res ++ ;
}

return res;
}

int main()
{
int l, r;
while (cin >> l >> r >> P)
{
init();

cout << dp(r) - dp(l - 1) << endl;
}

return 0;
}


#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

const int N = 11;

int f[N][10];

void init()
{
for (int i = 0; i <= 9; i ++ ) f[1][i] = 1;

for (int i = 2; i < N; i ++ )
for (int j = 0; j <= 9; j ++ )
for (int k = 0; k <= 9; k ++ )
if (abs(j - k) >= 2)
f[i][j] += f[i - 1][k];
}

int dp(int n)
{
if (!n) return 0;

vector<int> nums;
while (n) nums.push_back(n % 10), n /= 10;

int res = 0;
int last = -2;
for (int i = nums.size() - 1; i >= 0; i -- )
{
int x = nums[i];
for (int j = i == nums.size() - 1; j < x; j ++ )
if (abs(j - last) >= 2)
res += f[i + 1][j];

if (abs(x - last) >= 2) last = x;
else break;

if (!i) res ++ ;
}

// 特殊处理有前导零的数
for (int i = 1; i < nums.size(); i ++ )
for (int j = 1; j <= 9; j ++ )
res += f[i][j];

return res;
}

int main()
{
init();

int l, r;
cin >> l >> r;
cout << dp(r) - dp(l - 1) << endl;

return 0;
}


## 超宝赛高

### 算法1

#### C++ 代码

#include <iostream>
#include <algorithm>
#include <cstring>

using LL = long long;

const int N = 100010;

int n, m;
int h[N], trmin[N], trmax[N];

int lowbit(int x)
{
return x & -x;
}

{
for(int i = x;i <= n;i += lowbit(i))
{
trmin[i] = std::min(trmin[i], c);
trmax[i] = std::max(trmax[i], c);
}
}

int get_max(int l, int r)
{
if(r > l)
{
if(r - lowbit(r) >= l) return std::max(trmax[r], get_max(l, r - lowbit(r)));
else return std::max(h[r], get_max(l, r - 1));
}

return h[l];
}

int get_min(int l, int r)
{
if(r > l)
{
if(r - lowbit(r) >= l) return std::min(trmin[r], get_min(l, r - lowbit(r)));
else return std::min(h[r], get_min(l, r - 1));
}

return h[l];
}

void solve()
{
scanf("%d%d", &n, &m);
memset(trmin, 0x3f, sizeof trmin);
for(int i = 1;i <= n;i ++)
{
scanf("%d", h + i);
}

while(m --)
{
int a, b;
scanf("%d%d", &a, &b);
printf("%d\n", get_max(a, b) - get_min(a, b));
printf("max = %d\n", get_max(a, b));
}
}

int main()
{
int t = 1;

while(t --) solve();

return 0;
}


### 算法2

RMQ yyds

#### C++ 代码

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cmath>

using LL = long long;

const int N = 100010, M = 17;

int n, m;
int f[N][M], g[N][M];
int h[N];

void init()
{
for(int j = 0;j < M;j ++)
for(int i = 1;i + (1 << j) - 1 <= n;i ++)
if(!j) f[i][j] = h[i];
else f[i][j] = std::max(f[i][j - 1], f[i + (1 << j - 1)][j - 1]);

for(int j = 0;j < M;j ++)
for(int i = 1;i + (1 << j) - 1 <= n;i ++)
if(!j) g[i][j] = h[i];
else g[i][j] = std::min(g[i][j - 1], g[i + (1 << j - 1)][j - 1]);
}

int query_max(int l, int r)
{
int len = r - l + 1;
int k = log(len) / log(2);
return std::max(f[l][k], f[r - (1 << k) + 1][k]);
}

int query_min(int l, int r)
{
int len = r - l + 1;
int k = log(len) / log(2);
return std::min(g[l][k], g[r - (1 << k) + 1][k]);
}

void solve()
{
scanf("%d%d", &n, &m);
for(int i = 1;i <= n;i ++) scanf("%d", h + i);

init();

while(m --)
{
int l, r;
scanf("%d%d", &l, &r);
printf("%d\n", query_max(l, r) - query_min(l, r));
}
}

int main()
{
int t = 1;

while(t --) solve();

return 0;
}


### 算法1

#### 时间复杂度 $O(nlogn)$

2.对于存储的树状数组，因为是排序去重后的结果，所以最坏的情况下，下标最大为2 * n，而不是n

#### C++ 代码

#include <iostream>
#include <algorithm>
#include <cstring>

using LL = long long;

const int N = 400010;

int n, m;
int a[N], b[N], x[N], y[N], tr[N], res[N];

int lowbit(int x)
{
return x & -x;
}

{
for(int i = x;i <= n * 2;i += lowbit(i)) tr[i] += c;
}

int sum(int x)
{
int res = 0;
for(int i = x; i;i -= lowbit(i)) res += tr[i];

return res;
}

void solve()
{
scanf("%d", &n);
for(int i = 1;i <= n;i ++) scanf("%d", a + i);
for(int i = 1;i <= n;i ++) scanf("%d", b + i);

for(int i = 1;i <= n;i ++)
{
x[i] = a[i] - b[i];
y[i] = b[i] - a[i];
res[++ m] = x[i], res[++ m] = y[i];
}

std::sort(res + 1, res + m + 1);
m = std::unique(res + 1, res + m + 1) - res - 1;
for(int i = 1;i <= n;i ++)
{
x[i] = std::lower_bound(res + 1, res + m + 1, x[i]) - res;
y[i] = std::lower_bound(res + 1, res + m + 1, y[i]) - res;
}

LL ans = 0;
for(int i = 1;i <= n;i ++)
{
ans += sum(x[i] - 1);
}

printf("%lld\n", ans);
}

int main()
{
int t = 1;
//scanf("%d", &t);

while(t --) solve();

return 0;
}


let fs = require('fs');
let buf = '';

if (chunk) buf += chunk.toString();
});

process.stdin.on('end', function() {
buf.split('\n').forEach(function(line) {
let tokens = line.split(' ').map(function(x) { return parseInt(x); });
if (tokens.length != 2) return;
console.log(tokens.reduce(function(a, b) { return a + b; }));
});
});


<!DOCTYPE html>
<html lang="en">

<meta charset="UTF-8">
<meta http-equiv="X-UA-Compatible" content="IE=edge">
<meta name="viewport" content="width=device-width, initial-scale=1.0">
<title>Document</title>

<style>
.container {
width: 50%;
height: 500px;
background-color: lightblue;
display: flex;
margin: 10px;
}

.container>* {
width: 120px;
height: 120px;
}

.container>*:nth-child(odd) {
background-color: lightsalmon;
}

.container>*:nth-child(even) {
background-color: lightgreen;
}

.container:nth-child(1) {
flex-wrap: wrap;
justify-content: space-between;
align-content: flex-start;
}

.container:nth-child(2) {
flex-direction: row-reverse;
flex-wrap: nowrap;
}

.container:nth-child(2)>*:nth-child(odd) {
flex-grow: 3;
flex-shrink: 3;
}

.container:nth-child(2)>*:nth-child(even) {
flex-grow: 1;
flex-shrink: 1;
}
</style>

<body>
<div class="container">
<div>1</div>
<div>2</div>
<div>3</div>
<div>4</div>
<div>5</div>
<div>6</div>
</div>

<div class="container">
<div>1</div>
<div>2</div>
<div>3</div>
<div>4</div>
<div>5</div>
<div>6</div>
</div>
</body>

</html>



<!DOCTYPE html>
<html lang="en">

<meta charset="UTF-8">
<meta http-equiv="X-UA-Compatible" content="IE=edge">
<meta name="viewport" content="width=device-width, initial-scale=1.0">
<title>Document</title>

<style>
.container {
height: 500px;
width: 500px;
background-color: lightblue;
}

.item {
height: 100px;
width: 100px;
margin: 10px;
background-color: lightcoral;
float: left;
}

.next-line {
width: 150px;
height: 150px;
background-color: rgba(0, 0, 255, 0.5);
clear: both;
}
</style>

<body>
<div class="container">
<div class="item"></div>
<div class="item"></div>
<div class="item"></div>
<div class="item"></div>
<div class="item"></div>
<div class="next-line"></div>
</div>
</body>

</html>