3169

huangbq
zhincra
wu_qing

Fლ

lwy911

ssy_
hhdd
ScytheLancer
nXhp99
Joyi
UoU

### 求 1 ~ n 中长度 >= f 的连续区间的最大和

    rep(i, 1, n) s[i] = s[i - 1] + a[i];

int _min = INT_MAX, ans = INT_MIN;
rep(i, f, n){
_min = min(_min, s[i - f]);
ans = max(ans, s[i] - _min);
}
cout << ans << '\n';

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<climits>
using namespace std;

#define rep(i, a, b) for(int i = a;i <= b;i ++)
#define per(i, a, b) for(int i = b;i >= a;i --)
typedef long long ll;
typedef double db;

int n, f;
int const N = 1e5 + 10;
db const eps = 1e-5;
db a[N], s[N];

bool check(db mid){
rep(i, 1, n) s[i] = s[i - 1] + (a[i] - mid);

db ans = INT_MIN, _min = INT_MAX;
rep(i, f, n){
_min = min(_min, s[i - f]);
ans = max(ans, s[i] - _min);
if(ans >= 0) return true;
}
return false;
}

int main(){
db l = 1, r = 0;
cin >> n >> f;
rep(i, 1, n) cin >> a[i], r = max(r, a[i]);

while(r - l > eps){
db mid = (l + r) / 2.0;
if(check(mid)) l = mid;
else r = mid;
}
cout << (int)(r * 1000) << '\n';

return 0;
}


#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

#define rep(i, a, b) for(int i = a;i <= b;i ++)
#define per(i, a, b) for(int i = b;i >= a;i --)
typedef long long ll;
typedef double db;

int n, m, res;
int const N = 5e3 + 10;
int s[N][N];

int op(int x1, int y1, int x2, int y2){
return (s[x2][y2] - s[x1 - 1][y2] - s[x2][y1 - 1] + s[x1 - 1][y1 - 1]);
}

int main(){
cin >> n >> m;
m = min(m, 5001);
rep(i, 1, n){
int x, y, v;
cin >> x >> y >> v;
s[++ x][++ y] += v;
}
rep(i, 1, 5001) rep(j, 1, 5001)
s[i][j] += (s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1]);
rep(i, m, 5001) rep(j, m, 5001)
res = max(res, op(i - m + 1, j - m + 1, i, j));
cout << res << '\n';

return 0;
}


b[1] = a[1];
b[2] = a[2] - a[1];
b[3] = a[3] - a[2];
......
b[n] = a[n] - a[n - 1]

1. l = 1, r = n 操作 : 没有意义
2. l = 1, r <= n - 1 ; b[1] += c, b[r + 1] -= c;
3. r = n, l >= 2; b[2 ~ n - 1] += c, b[n + 1] -= c;
4. l >= 2, r <= n - 1; b[l] += c, b[r + 1] -= c;

2 ~ n - 1
min{p, q} + |p - q| = max{p, q};
|p - q| + 1

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

#define rep(i, a, b) for(int i = a;i <= b;i ++)
#define per(i, a, b) for(int i = b;i >= a;i --)
typedef long long ll;
typedef double db;

int n;
int const N = 1e5 + 10;
ll a[N], b[N];

int main(){
cin >> n;
rep(i, 1, n) cin >> a[i], b[i] = a[i] - a[i - 1];

ll p, q;
p = q = 0;
rep(i, 2, n){
if(b[i] > 0) p += b[i];
else q += (-b[i]);
}
cout << max(p, q) << '\n' << abs(p - q) + 1;

return 0;
}


12天前
#include <bits/stdc++.h>
using namespace std;

#define fs first
#define sc second
#define rep(i, a, b) for(int i = a;i <= b;i ++)
typedef double db;
typedef long long ll;
typedef pair<ll, ll> pll;

int t;
// n : 等级; m: 坐标，从0开始计数
pll pos(ll n, ll m){
if(!n) return {0, 0}; // 处理边界
ll len = 1ll << (n - 1); // 本等级内象限的边长
ll cnt = 1ll << ((n - 1) << 1); // 本等级象限容量

pll last = pos(n - 1, m % cnt); // 上一等级的坐标信息
ll x = last.fs, y = last.sc;

int z = m / cnt; // 位于第几象限
// 左上象限顺转 90°（y,-x）沿 y对称（-y,-x）更换原点（-y-len,-x+len）
if(!z) return {-y - len, -x + len};
// 右上象限更换原点（x+len,y+len）
else if(z == 1) return {x + len, y + len};
// 右下象限更换原点（x+len,y-len）
else if(z == 2) return {x + len, y - len};
// 左下象限逆转90°（-y,x）沿y对称（y,x）更换原点（y-len,x-len）
return {y - len, x - len};
}

int main(){
cin >> t;
while(t --){
ll n, p1, p2;
cin >> n >> p1 >> p2;
pll pos1 = pos(n, p1 - 1);
pll pos2 = pos(n, p2 - 1);

db delta_x = (db)(pos1.fs - pos2.fs);
db delta_y = (db)(pos1.sc - pos2.sc);
cout << fixed << setprecision(0) << (sqrt(delta_x * delta_x + delta_y * delta_y) * 5) << '\n';
}
}



16天前
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<map>
using namespace std;

#define fs first
#define sc second
#define rep(i, a, b) for(int i = a;i <= b;i ++)
#define per(i, a, b) for(int i = b;i >= a;i --)
typedef long long ll;
typedef double db;

ll a, b;
ll const MOD = 9901;
unordered_map<ll, ll> prim;

ll qmi(ll a, ll k);
ll sum(ll p, ll k);
void op(ll x);

ll res = 1;

void solution1(){
for(auto t : prim){
ll p = t.fs, k = t.sc * b;
res = res * sum(p, k + 1) % MOD;
}
}

void solution2(){
for(auto t : prim){
ll p = t.fs, k = t.sc * b;
if((p - 1) % MOD) res = res * (qmi(p, k + 1) - 1) % MOD * qmi(p - 1, MOD - 2) % MOD;
else res = res * (k + 1) % MOD;
}
}

int main(){
cin >> a >> b;
op(a);
solution1();
// solution2();

if(!a) cout << 0;
else cout << (res % MOD + MOD) % MOD << '\n';

return 0;
}

ll qmi(ll a, ll k){
ll res = 1;
while(k){
if(k & 1) res = (res * a) % MOD;
k >>= 1;
a = (a * a) % MOD;
}
return res;
}

// 求 p^0 + p^1 + ... + p^(k - 1)
ll sum(ll p, ll k){
if(k == 1) return 1LL;
if(k % 2 == 0) return (qmi(p, k / 2) + 1) * sum(p, k / 2) % MOD;
return (qmi(p, k - 1) + sum(p, k - 1)) % MOD;
}

void op(ll x){
for(ll i = 2;i <= x / i;i ++){
while(x % i == 0){
x /= i;
prim[i] ++;
}
}
if(x > 1) prim[x] ++;
}


21天前
#include<bits/stdc++.h>
using namespace std;

#define rep(i, a, b) for(int i = a;i <= b;i ++)

int n;
char q[10][10];
int dx[5] = {0, 0, 0, 1, -1};
int dy[5] = {0, 1, -1, 0, 0};

void change(int x, int y){
rep(i, 0, 4){
int a = x + dx[i], b = y + dy[i];
if(a >= 0 && a <= 4 && b >= 0 && b <= 4)
q[a][b] ^= 1;
}
}

void solve(){
int ans = INT_MAX;
rep(k, 0, (1 << 5) - 1){
char backup[10][10];
memcpy(backup, q, sizeof q);
int res = 0;
rep(i1, 0, 4) if(k >> i1 & 1) change(0, i1), res ++;
rep(i2, 0, 3) rep(j2, 0, 4)
if(q[i2][j2] == '0') change(i2 + 1, j2), res ++;

bool f = true;
rep(i3, 0, 4) if(q[4][i3] == '0') f = false;

if(f) ans = min(ans, res);
memcpy(q, backup, sizeof backup);
}

if(ans <= 6) cout << ans << '\n';
else cout << "-1\n";
}

void mycin(){
rep(i, 0, 4) cin >> q[i];
solve();
}

int main(){
cin >> n;
while(n --) mycin();

return 0;
}


21天前
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<climits>
using namespace std;

#define rep(i, a, b) for(int i = a;i <= b;i ++)
#define per(i, a, b) for(int i = b;i >= a;i --)
typedef long long ll;
typedef double db;

int n;
char q[10][10];

int dx[5] = {0, 0, 0, 1, -1};
int dy[5] = {0, 1, -1, 0, 0};

void change(int x, int y){
rep(i, 0, 4){
int a = x + dx[i], b = y + dy[i];
if(a >= 0 && a <= 4 && b >= 0 && b <= 4)
q[a][b] ^= 1;
}
}

void op(){
int ans = INT_MAX;
rep(k, 0, (1 << 5) - 1){
char backup[10][10];
memcpy(backup, q, sizeof q);
int res = 0;
rep(i1, 0, 4) if(k >> i1 & 1) change(0, i1), res ++;
rep(i2, 0, 3) rep(j2, 0, 4)
if(q[i2][j2] == '0') change(i2 + 1, j2), res ++;

bool f = true;
rep(i3, 0, 4) if(q[4][i3] == '0') f = false;

if(f) ans = min(ans, res);
memcpy(q, backup, sizeof backup);
}

if(ans <= 6) cout << ans << '\n';
else cout << "-1\n";
}

int main(){
cin >> n;
while(n --){
rep(i, 0, 4) cin >> q[i];
op();
}

return 0;
}


21天前
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

#define rep(i, a, b) for(int i = a;i <= b;i ++)
#define per(i, a, b) for(int i = b;i >= a;i --)
typedef long long ll;
typedef double db;

ll qadd(ll a, ll b, ll p){
ll res = 0;
while(b){
if(b & 1) res = (res + a) % p;
b >>= 1;
a = (a + a) % p;
}
return res;
}

int main(){
ll a, b, p;
cin >> a >> b >> p;

return 0;
}


27天前
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

#define rep(i, a, b) for(int i = a;i <= b;i ++)
#define per(i, a, b) for(int i = b;i >= a;i --)
typedef long long ll;
typedef double db;

int n, m;
int const N = 5e5 + 10;
ll a[N];

struct node{
int l, r;
ll sum, d;
}tr[N * 4];

ll gcd(ll a, ll b){
return b ? gcd(b, a % b) : a;
}

void pushup(node &u, node &lson, node &rson){
u.sum = lson.sum + rson.sum;
u.d = gcd(lson.d, rson.d);
}

void pushup(int u){
pushup(tr[u], tr[u << 1], tr[u << 1 | 1]);
}

void build(int u, int l, int r){
if(l == r){
ll b = a[l] - a[l - 1];
tr[u] = {l, r, b, b};
}else{
tr[u] = {l, r};
int mid = tr[u].l + tr[u].r >> 1;
build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);
pushup(u);
}
}

void modify(int u, int pos, ll val){
if(tr[u].l == tr[u].r){
ll t = tr[u].sum + val;
tr[u] = {pos, pos, t, t};
}else{
int mid = tr[u].l + tr[u].r >> 1;
if(pos <= mid) modify(u << 1, pos, val);
else modify(u << 1 | 1, pos, val);
pushup(u);
}
}

node query(int u, int l, int r){
if(tr[u].l >= l &&  tr[u].r <= r) return tr[u];
int mid = tr[u].l + tr[u].r >> 1;
if(r <= mid) return query(u << 1, l, r);
else if(l > mid) return query(u << 1 | 1, l, r);
else{
node res;
auto left = query(u << 1, l, r);
auto right = query(u << 1 | 1, l, r);
pushup(res, left, right);
return res;
}
}

int main(){
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);

cin >> n >> m;
rep(i, 1, n) cin >> a[i];
build(1, 1, n);

while(m --){
char ch;
int l, r;
ll x;
cin >> ch >> l >> r;
if(ch == 'C'){
cin >> x;
modify(1, l, x);
if(r + 1 <= n) modify(1, r + 1, -x);
}else{
ll res = query(1, 1, l).sum;
if(l != r) res = gcd(res, query(1, l + 1, r).d);
cout << abs(res) << '\n';
}
}

return 0;
}