大板子 —— 8
——— 算法技巧 ———
—— 思维 ——
区间GCD
int n, ans, a[maxn], l[maxn], v[maxn];
int main() {
scanf("%d", &n);
for(int i=1; i<=n; i++)
scanf("%d", a+i), v[i] = a[i], l[i] = i;
for(int i=1; i<=n; i++)
for(int j=i; j; j=l[j]-1) {
v[j] = __gcd(v[j], a[i]); // j ~ i的gcd值
while(l[j]>1 && __gcd(a[i], v[l[j]-1])==__gcd(a[i], v[j]))
l[j] = l[l[j]-1];
ans = (ans + 1LL * v[j] * (j-l[j]+1)) % mod;
}
printf("%d", ans);
}
第k小团
优先队列暴力枚举每个最小团
关键在于处理重复的情况
对于每种情况，只对最后一个
1
1
1 出现的位置之后加点
也就是新增点要在当前团的最后一个点之后
时间复杂度：
O
(
k
⋅
n
⋅
l
o
g
V
⋅
b
i
t
s
e
t
<
100
>
)
O(k \cdot n \cdot logV \cdot bitset<100>)
O(k⋅n⋅logV⋅bitset<100>)
int n, k, w[maxn];
bitset <maxn> mp[maxn], t;
char s[maxn];
struct Node{
ll v; bitset <maxn> u;
friend bool operator < (Node A, Node B){
return A.v > B.v;
}
} p;
priority_queue <Node> q;
int main() {
scanf("%d%d", &n, &k);
for(int i=0; i<n; i++) scanf("%d", w+i);
for(int i=0; i<n; i++){
scanf("%s", s);
int len = strlen(s);
for(int j=0; j<len; j++)
if(s[j]=='1') mp[i][j] = 1;
}
q.push({0, t});
while(q.size()){
p = q.top(); q.pop(); k--;
if(k==0) { printf("%lld", p.v); return 0; }
int pos = 0;
for(int i=0; i<n; i++) if(p.u[i]) pos = i + 1;
for(int i=pos; i<n; i++){
if((mp[i] & p.u) == p.u){
p.u[i] = 1;
q.push({p.v + w[i], p.u});
p.u[i] = 0;
}
}
}
puts("-1");
}
HDU多校第十场 1008 Coins
有
n
n
n 组硬币，每组硬币有两个
a
i
,
b
i
a_i, b_i
ai,bi
要求拿出
k
k
k 个硬币最大值为
f
(
k
)
f(k)
f(k)
限制一组硬币：
a
i
a_i
ai 未拿的时候不能拿
b
i
b_i
bi
求
f
(
1
)
、
f
(
2
)
、
.
.
.
f
(
k
)
f(1)、f(2)、...f(k)
f(1)、f(2)、...f(k)
解题思路：
因为有
b
i
b_i
bi 的限制，所以局部最优不是全局最优
但是仔细考虑一下，假设当前拿了
k
k
k 个硬币，且是最优的
考虑怎么拿下一个硬币：
①
：
①：
①：直接拿当前可以拿的最大值的那个硬币
②
：
②：
②：放回拿的第
k
k
k 个硬币，然后拿当前可以拿的最大的那一组硬币
经思考发现，没有第三种情况，第三种情况已经包含在上面的最优解里
所以记录一下各种可以拿的硬币及拿到了第几个
用优先队列维护一下即可
int T, n, ans[maxn], th2[maxn], th[maxn];
struct node1{
int x, id, th;
bool operator < (const node1 &A) const { return x < A.x; }
};
struct node2{
int x, y, id;
bool operator < (const node2 &A) const { return x + y < A.x + A.y; }
};
priority_queue <node1> q1;
priority_queue <node2> q2;
int main() {
scanf("%d", &T);
while(T--){
scanf("%d", &n);
while(!q1.empty()) q1.pop();
while(!q2.empty()) q2.pop();
for(int i=1, a, b; i<=n; i++){
scanf("%d%d", &a, &b);
th2[i] = b, th[i] = 0;
q1.push({a, i, 0});
q2.push({a, b, i});
}
int f = 0, prex, preid, a, b;
for(int i=1; i<=n*2; i++){
while(th[q1.top().id]!=q1.top().th && !q1.empty()) q1.pop();
while(th[q2.top().id]!=0 && !q2.empty()) q2.pop();
a = q1.top().x;
b = (f&&!q2.empty()) ? q2.top().x + q2.top().y - prex : 0;
if(a <= b){ // 取 2个
f = 0; ans[i] = ans[i-1] + b;
th[q2.top().id] = 2;
q1.push({prex, preid, --th[preid]});
q2.pop();
} else { // 取 1个
f = 1; ans[i] = ans[i-1] + a;
prex = q1.top().x, preid = q1.top().id;
q1.pop();
if(!th[preid]) q1.push({th2[preid], preid, 1});
++th[preid];
}
printf("%d%c", ans[i], " \n"[i==n*2]);
}
}
}
2020 wannafly camp day6 H 异或询问
解题思路：
如果只考虑
∑
i
=
1
n
f
(
i
)
\sum_{i=1}^n f(i)
∑i=1nf(i)，也就是一段连续的区间，预处理前缀即可
而
∑
f
(
i
x
o
r
x
)
\sum f(i\ xor\ x)
∑f(i xor x)，加上了一个异或后，区间就不连续了
根据异或性质，会分成最多
l
o
g
log
log 个连续区间
从高位到低位考虑，如果
n
n
n 的第
p
o
s
pos
pos 位为
1
1
1，若不考虑
n
n
n 的低位
若
x
x
x 的这一位为
0
0
0 ，则异或后是一段连续的区间:
（
0
,
2
p
o
s
−
1
）
（0, 2^{pos}-1）
（0,2pos−1）
若
x
x
x 的这一位为
1
1
1 ，则加上这一位，再计算新的区间
每一位考虑完之后，要加上这一位的影响，再去考虑低位
最后要清空影响，其实最后的影响就是
n
x
o
r
x
n\ xor\ x
n xor x 了
int n, q, a[maxn]; ll pre[maxn];
vector <int> v;
ll gao(ll x){
if(x < a[1]) return 0;
int pos = upper_bound(v.begin(), v.end(), x) - v.begin() - 1;
ll ret = pre[pos];
if(x == v[pos]) return ret;
ll num = upper_bound(a+1, a+1+n, x) - a - 1;
ret += 1ll * (x - v[pos]) * num % mod * num % mod;
return ret % mod;
}
ll query(int l, int r){
return (gao(r) - gao(l-1) + mod) % mod;
}
ll solve(int n, int x){
if(n < 0) return 0;
ll ret = 0; int cur = 0;
for(int i=30; ~i; i--){
int u = x >> i & 1;
if(n >> i & 1){
ret += query(cur|(u<<i), (cur|(u<<i)) + (1<<i)-1);
cur |= ((u ^ 1) << i);
} else cur |= (u << i);
}
ret = (ret + query(cur, cur)) % mod;
return ret;
}
int main() {
scanf("%d%d", &n, &q);
for(int i=1; i<=n; i++) scanf("%d", a+i), v.push_back(a[i]);
sort(a+1, a+1+n);
sort(v.begin(), v.end());
v.erase(unique(v.begin(), v.end()), v.end());
ll cnt = v.size(), num, lnum;
for(int i=0; i<cnt; i++){
num = upper_bound(a+1, a+1+n, v[i]) - a - 1;
if(i == 0) pre[i] = num * num % mod;
else pre[i] = pre[i-1] + num * num % mod + \
(v[i] - v[i-1] - 1) * lnum % mod * lnum % mod;
pre[i] %= mod; lnum = num;
}
while(q--){
int l, r, x;
scanf("%d%d%d", &l, &r, &x);
ll ans = solve(r, x) - solve(l-1, x);
printf("%lld\n", (ans + mod) % mod);
}
}
—— WQS二分 ——
模型：有 n n n 个物品，选择每一个都会有相应的权值，需要求出强制选 k k k 个物品时的最大/最小权值和
大致思路：
限制个数的最大/最小权值和可以用
n
2
n^2
n2 的
D
P
DP
DP 求出
根据
D
P
DP
DP 图像，可以画出
x
−
g
(
x
)
x - g(x)
x−g(x) 图像，发现是上凸
/
/
/下凸包，斜率单调
设用直线
y
=
k
x
+
b
y = kx + b
y=kx+b 去切这个图像，得到
f
(
x
)
=
b
=
g
(
x
)
−
k
x
f(x) = b = g(x) - kx
f(x)=b=g(x)−kx
使得截距
b
b
b 最大，即对于每个数的权值
h
(
x
)
−
=
k
h(x) -= k
h(x)−=k 后
求一遍任意个数情况下的最大
/
/
/最小
f
(
x
)
f(x)
f(x) ，
O
(
n
)
O(n)
O(n) 的
D
P
DP
DP 可以完成
注意事项：
①
：
①：
①：若在答案附近出现斜率相同的情况
则二分判断结果
n
u
m
<
=
k
num <= k
num<=k ，
n
u
m
num
num 为尽可能少选的数值
二分判断结果
n
u
m
>
=
k
num >= k
num>=k ，
n
u
m
num
num 为尽可能多选的数值
②
：
②：
②：权值
h
(
x
)
−
=
k
h(x) -= k
h(x)−=k 要根据实际意义转化，有时可以为
h
(
x
)
+
=
k
h(x) += k
h(x)+=k
③
：
③：
③：注意二分的结果是否为目标值
k
k
k 的截距，最终答案要加上
k
∗
m
i
d
k * mid
k∗mid
大意：无向带权连通图，每条边为白色或黑色，求一棵最小权的恰好有 n e e d need need 条白色边的生成树
根据
W
Q
S
WQS
WQS 二分，发现这个
x
−
g
(
x
)
x - g(x)
x−g(x) 是一个下凸包
二分斜率，每条白色边权
−
=
x
-= x
−=x
对答案
+
k
∗
m
i
d
+ k * mid
+k∗mid 即可
int n, m, k, f[maxn], ans, num;
struct edge {
int s, t, c, col;
} e[maxn], ed[maxn];
bool cmp(const edge A,const edge B) {
if(B.c == A.c) return A.col > B.col;
return A.c < B.c;
}
int getf(int x) {
return x == f[x] ? x : f[x] = getf(f[x]);
}
bool ck(int x) {
for(int i=1; i<=n; i++) f[i] = i;
for(int i=1; i<=m; i++) {
ed[i] = e[i];
if(!e[i].col) ed[i].c -= x;
}
sort(ed+1, ed+1+m, cmp);
ans = 0, num = 0;
for(int i=1; i<=m; i++) {
int fs = getf(ed[i].s), ft = getf(ed[i].t);
if(fs == ft) continue;
f[fs] = ft;
ans += ed[i].c;
num += !ed[i].col;
}
return num <= k;
}
int main() {
scanf("%d%d%d", &n, &m, &k);
for(int i=1; i<=m; i++) {
scanf("%d%d%d%d", &e[i].s, &e[i].t, &e[i].c, &e[i].col);
e[i].s++, e[i].t++;
}
int l = -1e5, r = 1e5, mid;
while(l <= r) {
mid = l + r >> 1;
if(ck(mid)) l = mid + 1;
else r = mid - 1;
}
ck(r);
printf("%d\n", ans + k * r);
}
—— 增值二分 ——
题目大意：
给定
a
i
a_i
ai，找到一组
b
i
b_i
bi，满足
0
≤
b
i
≤
a
i
0 \le b_i \le a_i
0≤bi≤ai，且
∑
b
i
=
k
\sum{b_i} = k
∑bi=k
使得
∑
b
i
×
(
a
i
−
b
i
2
)
\sum{b_i \times (a_i - b_i^2)}
∑bi×(ai−bi2) 最大
解题思路：
直接对增值进行二分，在上面我们说到使答案减少的值越来越大
其实等价于使答案增大的值越来越小，观察
f
′
(
x
)
=
−
3
x
2
+
a
f'(x) = -3x^2 + a
f′(x)=−3x2+a
f
′
(
x
)
f'(x)
f′(x) 在
x
＞
0
x＞0
x＞0 时单调递减，说明
f
(
x
)
f(x)
f(x) 在
x
＞
0
x＞0
x＞0 时增值越来越小，也就是使答案增大的值越来越小
当
b
i
b_i
bi 的增值大于二分的
x
x
x 时，就让它增加，也就减少了增值，这样一定保证答案的合理性
只是最后要处理一下
∑
b
i
≥
k
\sum{b_i} \ge k
∑bi≥k，选取最优的
∑
b
i
−
k
\sum{b_i} - k
∑bi−k 个
b
i
b_i
bi 使其减少
时间复杂度：
O
(
n
l
o
g
2
n
)
O(nlog^2n)
O(nlog2n)
int n; ll k, a[maxn], b[maxn];
struct node{
ll num; int id;
bool operator < (const node &A) { return num > A.num; }
} p[maxn];
bool ck(ll x){
ll all = 0, l, r, mid;
for(int i=1; i<=n; i++){
l = 0, r = a[i], mid;
while(l <= r){
mid = l + r >> 1;
ll tmp1 = mid * (a[i] - mid * mid);
ll tmp2 = (mid - 1) * (a[i] - (mid - 1) * (mid - 1));
if(tmp1 - tmp2 >= x) l = mid + 1;
else r = mid - 1;
}
b[i] = r; all += b[i];
}
return all >= k;
}
void gao(){
ll all = 0, cnt = 0;
for(int i=1; i<=n; i++) {
all += b[i];
if(b[i] == 0) continue;
p[++cnt].id = i;
ll tmp1 = 1ll * b[i] * (a[i] - b[i] * b[i]);
ll tmp2 = 1ll * (b[i] - 1) * (a[i] - 1ll * (b[i] - 1) * (b[i] - 1));
p[cnt].num = tmp2 - tmp1;
}
all -= k; if(all == 0) return;
sort(p+1, p+1+cnt);
for(int i=1; all; i++, all--) b[p[i].id]--;
}
signed main() {
scanf("%d%lld", &n, &k);
for(int i=1; i<=n; i++) scanf("%lld", a+i);
ll l = -4e18, r = 4e18, mid;
while(l <= r){
mid = l + r >> 1;
if(ck(mid)) l = mid + 1;
else r = mid - 1;
}
ck(r); gao();
for(int i=1; i<=n; i++) printf("%d ", b[i]);
}
—— 01分数规划 ——
给定
n
n
n 个二元组
(
v
a
l
u
e
i
，
c
o
s
t
i
)
(value_i，cost_i)
(valuei，costi)，分别表示价值和代价
设
x
i
∈
{
0
,
1
}
x_i∈\{0, 1\}
xi∈{0,1}，表示第
i
i
i 个二元组是否选取
要求最大(小)化下式：
r
=
∑
v
a
l
u
e
i
×
x
i
∑
c
o
s
t
i
×
x
i
r = \frac{ \sum{value_i} \times x_i } { \sum{cost_i} \times x_i }
r=∑costi×xi∑valuei×xi
二分
m
i
d
mid
mid ，若最优值
≥
m
i
d
:
≥ mid:
≥mid:
∑
v
a
l
u
e
i
×
x
i
∑
c
o
s
t
i
×
x
i
≥
m
i
d
\frac{ \sum{value_i} \times x_i } { \sum{cost_i} \times x_i } ≥ mid
∑costi×xi∑valuei×xi≥mid
∑
(
v
a
l
u
e
i
−
m
i
d
∗
c
o
s
t
i
)
×
x
i
≥
0
\sum{(value_i - mid * cost_i)} \times x_i ≥ 0
∑(valuei−mid∗costi)×xi≥0
也就是找到一组
{
x
i
}
\{x_i\}
{xi} 使得
∑
(
v
a
l
u
e
i
−
m
i
d
∗
c
o
s
t
i
)
\sum{(value_i - mid * cost_i)}
∑(valuei−mid∗costi) 最大
若找到的最大值
≥
0
≥ 0
≥0，也就是 最优值大于
m
i
d
mid
mid，反之就是小于
m
i
d
mid
mid
选取 n − k n-k n−k 个二元组使得 ∑ a i ∑ b i \frac{ \sum{a_i} } { \sum{b_i} } ∑bi∑ai 最大
int n, k, a[maxn], b[maxn]; double c[maxn];
bool ck(double x){
for(int i=1; i<=n; i++) c[i] = a[i] - x * b[i];
sort(c+1, c+1+n);
double res = 0;
for(int i=k+1; i<=n; i++) res += c[i];
return res >= eps;
}
signed main() {
while(scanf("%d%d", &n, &k) && n){
for(int i=1; i<=n; i++) scanf("%d", a+i);
for(int i=1; i<=n; i++) scanf("%d", b+i);
double l = 0, r = 1e5, mid;
while((r - l) >= eps){
mid = (l + r) / 2;
if(ck(mid)) l = mid + eps;
else r = mid - eps;
}
printf("%.0f\n", r * 100);
}
}
整体二分
整体二分：对所有的询问一起进行二分
满足前提：
①
：
①：
①：单组询问可以二分
②
：
②：
②：对于修改具有高效的数据结构维护
③
：
③：
③：贡献满足交换律，结合律，具有可加性
④
：
④：
④：可以离线
⑤
：
⑤：
⑤：具有类似决策单调性
大致过程：
每次对询问
(
x
,
y
)
(x, y)
(x,y) 并且答案在
(
l
,
r
)
(l, r)
(l,r) 进行处理
处理结束后，答案在
m
i
d
mid
mid 之前的询问放在左边
答案在
m
i
d
mid
mid 之后的询问减掉
(
l
,
m
i
d
)
(l,mid)
(l,mid) 的贡献，放在右边
递归处理
时间复杂度：
O
(
q
×
l
o
g
(
r
−
l
)
×
修
改
)
O(q \times log(r - l) \times 修改)
O(q×log(r−l)×修改)
大意：区间加，询问每个点达到指定数目的最少次数
题解：注意树状数组进行区间修改
int n, m, k, ans[maxn];
int L[maxn], R[maxn], A[maxn];
ll d[maxn];
vector <int> g[maxn];
struct node{
int nd, id;
} a[maxn], ta[maxn];
inline void add(int x, ll v){
for(int i=x; i<=m<<1; i+=(i&-i))
d[i] += v;
}
inline ll sum(int x){
ll ret = 0;
for(int i=x; i; i-=(i&-i))
ret += d[i];
return ret;
}
void solve(int l, int r, int x, int y){
if(l > r || x > y) return;
if(l == r){
for(int i=x; i<=y; i++) ans[a[i].id] = l;
return ;
}
int mid = l + r >> 1, tl = 0, tr = n;
for(int i=l; i<=mid; i++) add(L[i], A[i]), add(R[i]+1, -A[i]);
for(int i=x; i<=y; i++){
ll tmp = 0;
for(auto j : g[a[i].id]) {
tmp += sum(j) + sum(j+m);
if(tmp >= a[i].nd) break;
}
if(tmp >= a[i].nd) ta[++tl] = a[i];
else ta[++tr] = a[i], ta[tr].nd -= tmp;
}
for(int i=l; i<=mid; i++) add(L[i], -A[i]), add(R[i]+1, A[i]);
for(int i=1; i<=tl; i++) a[x+i-1] = ta[i];
for(int i=n+1; i<=tr; i++) a[x+tl+i-n-1] = ta[i];
if(tl) solve(l, mid, x, x+tl-1);
if(tr>n) solve(mid+1, r, x+tl, y);
}
int main() {
scanf("%d%d", &n, &m);
for(int i=1, x; i<=m; i++){
scanf("%d", &x);
g[x].push_back(i);
}
for(int i=1; i<=n; i++){
scanf("%d", &a[i].nd);
a[i].id = i;
}
scanf("%d", &k);
for(int i=1; i<=k; i++){
scanf("%d%d%d", L+i, R+i, A+i);
if(R[i] < L[i]) R[i] += m;
}
solve(1, k+1, 1, n);
for(int i=1; i<=n; i++)
if(ans[i] == k+1) puts("NIE");
else printf("%d\n", ans[i]);
}
2020 wannafly camp day3 F 社团管理
题目大意：
n
n
n 个数字，分为
k
k
k 段
使每段内相同数字的对数 的和最小
解题思路：
d
p
[
i
]
[
k
]
dp[i][k]
dp[i][k] 为以
i
i
i 为止，分为
k
k
k 段的最小值
发现随着
i
i
i 的增大，满足决策单调性
设区间
(
x
,
y
)
(x, y)
(x,y) 的答案位置在
(
l
,
r
)
(l, r)
(l,r)
则可以进行类似整体二分的转移
对于修改，可以用莫队处理，复杂度均摊
int n, k, a[maxn], nl = 1, nr;
ll dp[maxn][25], cnt[maxn], sum;
inline void add(int x){
x = a[x]; if(cnt[x]) sum -= cnt[x] * (cnt[x] - 1) / 2;
cnt[x]++; f(cnt[x]) sum += cnt[x] * (cnt[x] - 1) / 2;
}
inline void del(int x){
x = a[x]; if(cnt[x]) sum -= cnt[x] * (cnt[x] - 1) / 2;
cnt[x]--; if(cnt[x]) sum += cnt[x] * (cnt[x] - 1) / 2;
}
inline void gao(int ql, int qr){
while(ql < nl) add(--nl);
while(ql > nl) del(nl++);
while(qr < nr) del(nr--);
while(qr > nr) add(++nr);
}
void solve(int l, int r, int x, int y, int k){
if(l > r || x > y) return;
int mid = x + y >> 1, pos;
ll mi = 1e18;
for(int i=l; i<=min(mid, r); i++){
gao(i, mid);
ll tmp = dp[i-1][k-1] + sum;
if(tmp < mi){
dp[mid][k] = mi = tmp;
pos = i;
}
}
solve(l, pos, x, mid-1, k);
solve(pos, r, mid+1, y, k);
}
int main() {
scanf("%d%d", &n, &k);
for(int i=1; i<=n; i++) scanf("%d", a+i);
for(int i=1; i<=n; i++)
gao(1, i), dp[i][0] = sum;
for(int i=1; i<k; i++)
solve(1, n, 1, n, i);
printf("%lld\n", dp[n][k-1]);
}
—— RMQ ——
int dp_max[maxn][20], dp_min[maxn][20];
void ST(int n, int d[]) {
for (int i=1; i<=n; i++) {
dp_max[i][0] = d[i]; dp_min[i][0] = d[i];
}
for (int j=1; (1<<j) <= n; j++) {
for (int i=1; i+(1<<j)-1 <= n; i++) {
dp_max[i][j] = max(dp_max[i][j-1], dp_max[i + (1<<(j-1))][j-1]);
dp_min[i][j] = min(dp_min[i][j-1], dp_min[i + (1<<(j-1))][j-1]);
}
}
}
int RMQ_max(int l, int r) {
int k = log(r - l + 1.0) / log(2.0);
return max(dp_max[l][k], dp_max[r - (1<<k)+1][k]);
}
int RMQ_min(int l, int r) {
int k = log(r - l + 1.0) / log(2.0);
return min(dp_min[l][k], dp_min[r - (1<<k)+1][k]);
}
—— 启发式分治 ——
给定
n
n
n 个数，求满足某种条件的点对数目或最大权值，而这个最大权值与点对
(
a
,
b
)
(a,b)
(a,b) 的区间
[
a
,
b
]
[a,b]
[a,b] 的区间最大
/
/
/最小值有关。
那么这时就可以考虑分治，对于区间
[
L
,
R
]
[L,R]
[L,R]，找到最小
/
/
/大值所在位置
然后处理横跨最小/大值所在位置的点对，再递归处理子区间
对于一个区间，找到最大/最小值的位置
m
i
d
mid
mid 可以用
R
M
Q
RMQ
RMQ 预处理
然后枚举
[
l
,
m
i
d
]
[l, mid]
[l,mid] 与
[
m
i
d
,
r
]
[mid, r]
[mid,r] 的较小区间，查询处理出答案即可
大意：一个好的区间定义为
m
a
x
(
a
l
,
a
l
+
1
,
.
.
.
,
a
r
)
−
(
r
−
l
+
1
)
<
=
k
max(a_l, a_{l+1},...,a_r) - (r - l + 1) <= k
max(al,al+1,...,ar)−(r−l+1)<=k
并且区间内所有数互不相同，问有多少个好的区间？
题解：根据最大值进行启发式分治，
R
M
Q
RMQ
RMQ 预处理区间最大值位置
L
[
i
]
L[i]
L[i] 为以
a
[
i
]
a[i]
a[i] 往左满足数字互不相同的的最远位置，
R
[
i
]
R[i]
R[i] 为往右，用双指针
O
(
n
)
O(n)
O(n) 预处理即可
int T, n, k, a[maxn];
int L[maxn], R[maxn], vis[maxn];
ll ans;
void solve(int l, int r) {
if(l > r) return;
int mid = RMQ_max(l, r);
if(mid - l <= r - mid) {
for(int i=l; i<=mid; i++) {
int r1 = max(mid, a[mid] - k + i - 1);
int r2 = min(r, R[i]);
if(r1 <= r2) ans += r2 - r1 + 1;
}
} else {
for(int i=mid; i<=r; i++){
int l2 = min(mid, -a[mid] + k + i + 1);
int l1 = max(l, L[i]);
if(l1 <= l2) ans += l2 - l1 + 1;
}
}
solve(l, mid - 1), solve(mid + 1, r);
}
int main() {
scanf("%d", &T);
while(T--) {
scanf("%d%d", &n, &k);
for(int i=1; i<=n; i++) scanf("%d", a+i);
vis[a[1]] = 1;
for(int i=1, p=2; i<=n; i++) {
while(p<=n && !vis[a[p]]) vis[a[p++]] = 1;
vis[a[i]] = 0, R[i] = p - 1;
}
vis[a[n]] = 1;
for(int i=n, p=n-1; i; i--) {
while(p && !vis[a[p]]) vis[a[p--]] = 1;
vis[a[i]] = 0, L[i] = p + 1;
}
ans = 0; ST(n, a); solve(1, n);
printf("%lld\n", ans);
}
}
—— 莫队 ——
1、奇偶性排序 + 快速读入输出
int a[maxn], cnt[maxn], belong[maxn];
int n, m, size, bnum, now, ans[maxn];
struct query {
int l, r, id;
} q[maxn];
inline int cmp(query a, query b) {
return (belong[a.l] ^ belong[b.l]) ? belong[a.l] < belong[b.l] : \
((belong[a.l] & 1) ? a.r < b.r : a.r > b.r);
}
inline void add(int pos) {
if(!cnt[a[pos]]) ++now;
++cnt[a[pos]];
}
inline void del(int pos) {
--cnt[a[pos]];
if(!cnt[a[pos]]) --now;
}
int main() {
read(n);
size = sqrt(n);
bnum = ceil(1.0 * n / size);
for(int i=1; i<=bnum; ++i)
for(int j=(i-1)*size+1; j<=i*size; ++j)
belong[j] = i;
for(int i=1; i<=n; ++i) read(a[i]);
read(m);
for(int i=1; i<=m; ++i) {
read(q[i].l), read(q[i].r);
q[i].id = i;
}
sort(q+1, q+m+1, cmp);
int l = 1, r = 0;
for(int i=1; i<=m; ++i) {
int ql = q[i].l, qr = q[i].r;
while(l < ql) del(l++);
while(l > ql) add(--l);
while(r < qr) add(++r);
while(r > qr) del(r--);
ans[q[i].id] = now;
}
for(int i=1; i<=m; ++i)
print(ans[i]), putchar('\n');
}
2、带修改莫队
int a[maxn], cnt[maxc], ans[maxn], belong[maxn];
int cntq, cntc, n, m, size, bnum, now;
struct query {
int l, r, time, id;
} q[maxn];
struct modify {
int pos, color, last;
} c[maxn];
inline int cmp(query a, query b) {
return (belong[a.l] ^ belong[b.l]) ? belong[a.l] < belong[b.l] :\
((belong[a.r] ^ belong[b.r]) ? belong[a.r] < belong[b.r] : a.time < b.time);
}
inline void add(const int x){
if(++cnt[x] == 1) ++now;
}
inline void del(int x){
if(--cnt[x] == 0) --now;
}
int main() {
n = read(), m = read();
size = pow(n, 2.0 / 3.0);
bnum = ceil((double)n / size);
for(int i=1; i<=bnum; ++i)
for(int j=(i-1)*size+1; j<=i*size; ++j)
belong[j] = i;
for(int i=1; i<=n; ++i)
a[i] = read();
for(int i=1; i<=m; ++i) {
char opt[100];
scanf("%s", opt);
if(opt[0] == 'Q') {
q[++cntq].l = read();
q[cntq].r = read();
q[cntq].time = cntc;
q[cntq].id = cntq;
} else if(opt[0] == 'R') {
c[++cntc].pos = read();
c[cntc].color = read();
}
}
sort(q+1, q+cntq+1, cmp);
int l = 1, r = 0, time = 0; now = 0;
for(int i = 1; i <= cntq; ++i) {
int ql = q[i].l, qr = q[i].r, qt = q[i].time;
while(l < ql) del(a[l++]);
while(l > ql) add(a[--l]);
while(r < qr) add(a[++r]);
while(r > qr) del(a[r--]);
while(time < qt) {
++time;
if(ql <= c[time].pos && c[time].pos <= qr)
del(a[c[time].pos]), add(c[time].color);
swap(a[c[time].pos], c[time].color);
}
while(time > qt) {
if(ql <= c[time].pos && c[time].pos <= qr)
del(a[c[time].pos]), add(c[time].color);
swap(a[c[time].pos], c[time].color);
--time;
}
ans[q[i].id] = now;
}
for(int i = 1; i <= cntq; ++i) printf("%d\n", ans[i]);
}
—— 模拟退火 ——
如何生成新解
- 坐标系内：随机生成一个点，或者生成一个向量
- 序列问题： r a n d o m _ s h u f f l e random\_shuffle random_shuffle 或者随机交换两个数
- 网格问题：可以看做二维序列，每次交换两个格子即可
注意事项
这里的 新解与最优解的差为
Δ
E
\Delta E
ΔE，对应代码里的
d
e
l
del
del
如果新解更优，则直接更新，否则以一定概率接受它，概率为 exp(-del/T)*RAND_MAX > rand()
要注意这里的
d
e
l
del
del 前有没有负号要看能不能跑出正解，括号内的必须是负值
若接受这个不优解，不能更新答案，而是在这个不优解的影响下继续降温
while(1.0*clock()/CLOCKS_PER_SEC < 0.85) sa(); 可用来极限卡时间
给定一个要满足的椭球的方程
a
x
2
+
b
y
2
+
c
z
2
+
d
y
z
+
e
x
z
+
f
x
y
=
1
ax^2+by^2+cz^2+dyz+exz+fxy=1
ax2+by2+cz2+dyz+exz+fxy=1
求球面上一个点到原点
(
0
,
0
,
0
)
(0,0,0)
(0,0,0) 的距离最小
则可以随机一个点 ( x , y ) (x,y) (x,y)，然后求出 z z z，即可开始退火
const double eps = 1e-15;
double a, b, c, d, e, f;
double ansx, ansy, ansz, ans;
double cal(double x, double y, double z){
return sqrt(x*x + y*y + z*z);
}
double calz(double x, double y){
double A = c;
double B = d * y + e * x;
double C = a * x * x + b * y * y + f * x * y - 1.0;
double dlt = B * B - 4.0 * A * C;
if(dlt < 0) return 1e15;
double x1 = (-B + sqrt(dlt)) / (2.0 * A);
double x2 = (-B - sqrt(dlt)) / (2.0 * A);
if(cal(x, y, x1) < cal(x, y, x2)) return x1;
return x2;
}
void sa() {
double T = 66666, nowx = ansx, nowy = ansy, DT = 0.99;
while(T > eps) {
double tx = nowx + (rand()*2-RAND_MAX) * T;
double ty = nowy + (rand()*2-RAND_MAX) * T;
double tz = calz(tx, ty);
if(tz == 1e15) {T = T * DT; continue;}
double now = cal(tx, ty, tz);
double del = now - ans;
if(del < 0) {
ans = now;
ansx = tx, ansy = ty;
nowx = tx, nowy = ty;
} else if(exp(-del/T)*RAND_MAX > rand()) {
nowx = tx, nowy = ty;
}
T = T * DT;
}
}
signed main() {
srand(time(0));
while(~scanf("%lf%lf%lf%lf%lf%lf", &a, &b, &c, &d, &e, &f)) {
ansx = ansy = 0; ans = 1e15;
for(int i=1; i<5; i++) sa();
printf("%.5f\n", ans);
}
}