t1t2水
t3数学水,和我出的模拟赛的那道概率的思想是一样的
x<y<z,y-x=z-y --> x,y同奇/同偶
(x+z)(num[x]+num[z]) --> 记t[i][j]为颜色为i的编号奇偶性为j(0偶1奇)的格子个数,s[i][j]为颜色为i的编号奇偶性为j(0偶1奇)的所有格子的编号之和,所以格子i对ans的贡献为((t[cl[i]][i&1]-2)*i+s[cl[i]][i&1])*num[i](t[cl[i]][i&1]>1)
t4贪心
X=x时的最优解集合为U(x), last(U)为U中s最大的元素
1. v∈U(n)-U(x-1)且满足∀u∈U(n)-U(x-1)-{v}, s[v]+a[v]≥s[u]+a[u], U(x)=U(x-1)∪{v}
2. ans+=s[v]+a[v], 输出
3. 若v>last(U(x-1)), 则∀u∈U(n)-U(x):
a) s[u]改为0| u<v
b) s[u]减去s[v]-s[last(U(x-1))]| u>v
4. ++x, 若x>n结束, 否则跳至1
//还是看代码吧
贪心的最优性证明(瞎写, 请喷):
假设U(x)不是最优解, 即∃u∈U(n)-U(x),∃v∈U(x)使U'(x)=U(x)∪{u}-{v}优于U(x)
设r=last(U(x)), 由假设,有s[r]+a[r],s[v]+a[v]≥s[u]+a[u], v≤r
1. 选择顺序为r→v
s[u]+a[u]>s[v]+a[v], 矛盾
2. 选择顺序为v→r
有s[v]+a[v]≥s[r]+a[r]
a) u<v
a[u]>a[v]≥s[r]+a[r]-s[v]≥s[r]+a[r]-s[u]
a[u]+s[u]>a[r]+s[r], 矛盾
b) v<u<r
a[u]+s[u]>a[v]+s[v], 矛盾
c) r<u
a[u]>a[v]≥s[r]+a[r]-s[v]
a[u]+s[u]≥s[r]+a[r]+s[u]-s[v]≥s[r]+a[r], 矛盾
综上, U(x)为最优解
[code]//这个是priority_queue+O(n)预处理suffix维护最值.场上写的是segment tree维护最值, 100+行
#include <cstdio>
#include <cctype>
#include <algorithm>
#include <queue>
#define rep(i,x,y) for (int i=x; i<=y;++i)
#define repd(i,x,y) for (int i=x; i>=y;--i)
using namespace std;
const int N=100010;
char ch;
intret,n,s[N],a[N],suf[N],sp[N],fst=1,ans,mxs;
priority_queue<int> h;
inline int getint()
{
while (!isdigit(ch=getchar()));
for (ret=ch-48; isdigit(ch=getchar());ret=(ret<<3)+(ret<<1)+ch-48);
return ret;
}
int main()
{
n=getint();
rep(i,1,n)
s[i]=getint()<<1;
rep(i,1,n)
a[i]=getint();
repd(i,n,1)
if (suf[i+1]>s[i]+a[i])
suf[i]=suf[i+1],sp[i]=sp[i+1];
else
suf[i]=s[i]+a[i],sp[i]=i;
rep(i,1,n)
if (h.empty() || h.top()<suf[fst]-mxs)
{
printf("%d\n",ans+=suf[fst]-mxs);
rep(i,fst,sp[fst]-1)
h.push(a[i]);
fst=sp[fst]+1,mxs=s[fst-1];
}
else
printf("%d\n",ans+=h.top()),h.pop();
return 0;
}
最后一次pj, 希望不要跪
t3数学水,和我出的模拟赛的那道概率的思想是一样的
x<y<z,y-x=z-y --> x,y同奇/同偶
(x+z)(num[x]+num[z]) --> 记t[i][j]为颜色为i的编号奇偶性为j(0偶1奇)的格子个数,s[i][j]为颜色为i的编号奇偶性为j(0偶1奇)的所有格子的编号之和,所以格子i对ans的贡献为((t[cl[i]][i&1]-2)*i+s[cl[i]][i&1])*num[i](t[cl[i]][i&1]>1)
t4贪心
X=x时的最优解集合为U(x), last(U)为U中s最大的元素
1. v∈U(n)-U(x-1)且满足∀u∈U(n)-U(x-1)-{v}, s[v]+a[v]≥s[u]+a[u], U(x)=U(x-1)∪{v}
2. ans+=s[v]+a[v], 输出
3. 若v>last(U(x-1)), 则∀u∈U(n)-U(x):
a) s[u]改为0| u<v
b) s[u]减去s[v]-s[last(U(x-1))]| u>v
4. ++x, 若x>n结束, 否则跳至1
//还是看代码吧
贪心的最优性证明(瞎写, 请喷):
假设U(x)不是最优解, 即∃u∈U(n)-U(x),∃v∈U(x)使U'(x)=U(x)∪{u}-{v}优于U(x)
设r=last(U(x)), 由假设,有s[r]+a[r],s[v]+a[v]≥s[u]+a[u], v≤r
1. 选择顺序为r→v
s[u]+a[u]>s[v]+a[v], 矛盾
2. 选择顺序为v→r
有s[v]+a[v]≥s[r]+a[r]
a) u<v
a[u]>a[v]≥s[r]+a[r]-s[v]≥s[r]+a[r]-s[u]
a[u]+s[u]>a[r]+s[r], 矛盾
b) v<u<r
a[u]+s[u]>a[v]+s[v], 矛盾
c) r<u
a[u]>a[v]≥s[r]+a[r]-s[v]
a[u]+s[u]≥s[r]+a[r]+s[u]-s[v]≥s[r]+a[r], 矛盾
综上, U(x)为最优解
[code]//这个是priority_queue+O(n)预处理suffix维护最值.场上写的是segment tree维护最值, 100+行
#include <cstdio>
#include <cctype>
#include <algorithm>
#include <queue>
#define rep(i,x,y) for (int i=x; i<=y;++i)
#define repd(i,x,y) for (int i=x; i>=y;--i)
using namespace std;
const int N=100010;
char ch;
intret,n,s[N],a[N],suf[N],sp[N],fst=1,ans,mxs;
priority_queue<int> h;
inline int getint()
{
while (!isdigit(ch=getchar()));
for (ret=ch-48; isdigit(ch=getchar());ret=(ret<<3)+(ret<<1)+ch-48);
return ret;
}
int main()
{
n=getint();
rep(i,1,n)
s[i]=getint()<<1;
rep(i,1,n)
a[i]=getint();
repd(i,n,1)
if (suf[i+1]>s[i]+a[i])
suf[i]=suf[i+1],sp[i]=sp[i+1];
else
suf[i]=s[i]+a[i],sp[i]=i;
rep(i,1,n)
if (h.empty() || h.top()<suf[fst]-mxs)
{
printf("%d\n",ans+=suf[fst]-mxs);
rep(i,fst,sp[fst]-1)
h.push(a[i]);
fst=sp[fst]+1,mxs=s[fst-1];
}
else
printf("%d\n",ans+=h.top()),h.pop();
return 0;
}
最后一次pj, 希望不要跪
