1001
和 hx 推了半天，被 wjh 一眼看了出来（
令 $f_i$ 表示 $i$ 个点时的答案。
可以推得
于是便可以 $O(n\log n)$ 求出答案（调和级数）。
代码（赛时）
#include <bits/stdc++.h>
using namespace std;
const int mod = 998244353;
int n;
int f[1000010], g[1000010];
int main () {
// freopen ("1.txt", "r", stdin);
// freopen ("2.txt", "w", stdout);
scanf("%d", &n);
f[0]=1;
for(int i=1;i<=n;i++) {
g[i]=f[i-1];
for(int j=1;i*j<=n;j++) {
f[i*j]+=g[i];
if(f[i*j]>mod) f[i*j]-=mod;
}
}
for (int i = 1; i <= n; i ++)
printf ("%d ", f[i]);
return 0;
}1002（补）
赛时一直在想怎么启发式合并，一直到结束也没想出来。
题解用的是线段树合并。
直接贴了。
是可以用启发式合并来做的，之后再想想。
代码（线段树合并）
#include<bits/stdc++.h>
#define N 200010
#define Log 25
#define ll long long
using namespace std;
int T;
int n,c[N];
ll w[N];
vector<int> edge[N];
ll dp[N],sum;
int tot=0,root[N];
struct SegmentTree{
struct node{
ll val,lazy;
int lson,rson;
}nod[N*Log];
#define v(x) nod[x].val
#define la(x) nod[x].lazy
#define ls(x) nod[x].lson
#define rs(x) nod[x].rson
#define mid ((l+r)>>1)
void spread(int p) {
if(!la(p)) return ;
if(ls(p)) v(ls(p))+=la(p),la(ls(p))+=la(p);
if(rs(p)) v(rs(p))+=la(p),la(rs(p))+=la(p);
la(p)=0;
}
void change(int &p,int l,int r,int x,ll y) {
if(l>x||r<x) return ;
if(!p) p=++tot;
v(p)=max(v(p),y);
if(l==r) {
v(p)=max(v(p),y);
return ;
}
change(ls(p),l,mid,x,y),change(rs(p),mid+1,r,x,y);
}
int merge(int p,int q,int l,int r,ll &x) {
if(!p||!q) return p+q;
if(l==r) {
x=max(x,v(p)+v(q)+sum);
v(p)=max(v(p),v(q));
return p;
}
spread(p),spread(q);
v(p)=max(v(p),v(q));
ls(p)=merge(ls(p),ls(q),l,mid,x);
rs(p)=merge(rs(p),rs(q),mid+1,r,x);
return p;
}
}SMT;
void dfs(int u,int fa) {
int tsum=0;
for(auto v:edge[u]) {
if(v==fa) continue;
dfs(v,u);
tsum+=dp[v];
}
sum=tsum;
dp[u]=sum;
SMT.change(root[u],1,n,c[u],w[u]);
for(auto v:edge[u]) {
if(v==fa) continue;
SMT.v(root[v])-=dp[v];
SMT.la(root[v])-=dp[v];
root[u]=SMT.merge(root[u],root[v],1,n,dp[u]);
}
SMT.v(root[u])+=sum;
SMT.la(root[u])+=sum;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cin>>T;
while(T--) {
cin>>n;
for(int i=1;i<=n;i++) cin>>c[i];
for(int i=1;i<=n;i++) cin>>w[i];
for(int i=1;i<n;i++) {
int u,v;
cin>>u>>v;
edge[u].push_back(v);
edge[v].push_back(u);
}
dfs(1,1);
cout<<dp[1]<<endl;
for(int i=1;i<=n;i++) edge[i].clear();
for(int i=1;i<=n;i++) dp[i]=root[i]=0;
for(int i=1;i<=tot;i++) SMT.ls(i)=SMT.rs(i)=SMT.la(i)=SMT.v(i)=0;
tot=0;
}
return 0;
}1007
直接无脑上线段树即可。
sb错误WA了两发，演员实锤。
赛后发现大家基本上都是维护的差分数组，而我维护的是原数组，没脑子实锤。（虽然也不是很难写）
代码（赛时）
#include<bits/stdc++.h>
#define N 100010
#define ll long long
using namespace std;
int n,q;
ll a[N];
struct SegmentTree{
struct node{
ll lazy,lval,rval;
bool fup,fdown,fsame;
#define lv(x) nod[x].lval
#define rv(x) nod[x].rval
#define la(x) nod[x].lazy
#define fu(x) nod[x].fup
#define fd(x) nod[x].fdown
#define fs(x) nod[x].fsame
#define ls (p<<1)
#define rs (ls|1)
#define mid ((l+r)/2)
}nod[N<<2];
void update(int p) {
if(fu(ls)&&fu(rs)) fu(p)=(rv(ls)<lv(rs));
else fu(p)=false;
if(fd(ls)&&fd(rs)) fd(p)=(rv(ls)>lv(rs));
else fd(p)=false;
if(fs(ls)&&fs(rs)) fs(p)=(rv(ls)==lv(rs));
else fs(p)=false;
lv(p)=lv(ls),rv(p)=rv(rs);
}
void spread(int p,int l,int r) {
if(!la(p)) return ;
la(ls)+=la(p),la(rs)+=la(p);
lv(ls)+=la(p),lv(rs)+=la(p);
rv(ls)+=la(p),rv(rs)+=la(p);
la(p)=0;
}
void build(int p,int l,int r) {
if(l==r) {
lv(p)=rv(p)=a[l];
la(p)=0;
fu(p)=fd(p)=fs(p)=true;
return ;
}
build(ls,l,mid),build(rs,mid+1,r);
update(p);
}
void change(int p,int l,int r,int L,int R,ll x) {
if(l>R||r<L) return ;
if(l>=L&&r<=R) {
la(p)+=x;
lv(p)+=x;
rv(p)+=x;
return ;
}
spread(p,l,r);
change(ls,l,mid,L,R,x),change(rs,mid+1,r,L,R,x);
update(p);
}
bool check_same(int p,int l,int r,int L,int R) {
if(l>=L&&r<=R) return fs(p);
spread(p,l,r);
if(R<=mid) return check_same(ls,l,mid,L,R);
if(L>mid) return check_same(rs,mid+1,r,L,R);
if(rv(ls)!=lv(rs)) return false;
return check_same(ls,l,mid,L,R)&check_same(rs,mid+1,r,L,R);
}
bool check_up(int p,int l,int r,int L,int R) {
if(l>=L&&r<=R) return fu(p);
spread(p,l,r);
if(R<=mid) return check_up(ls,l,mid,L,R);
if(L>mid) return check_up(rs,mid+1,r,L,R);
if(rv(ls)>=lv(rs)) return false;
return check_up(ls,l,mid,L,R)&check_up(rs,mid+1,r,L,R);
}
bool check_down(int p,int l,int r,int L,int R) {
if(l>=L&&r<=R) return fd(p);
spread(p,l,r);
if(R<=mid) return check_down(ls,l,mid,L,R);
if(L>mid) return check_down(rs,mid+1,r,L,R);
if(rv(ls)<=lv(rs)) return false;
return check_down(ls,l,mid,L,R)&check_down(rs,mid+1,r,L,R);
}
}SMT;
int main() {
// freopen("1.txt","r",stdin);
ios::sync_with_stdio(false);
cin.tie(0);
cin>>n;
for(int i=1;i<=n;i++) cin>>a[i];
SMT.build(1,1,n);
cin>>q;
for(int i=1;i<=q;i++) {
int op,l,r;
ll x;
cin>>op>>l>>r;
if(op==1) {
cin>>x;
SMT.change(1,1,n,l,r,x);
}
else if(op==2) cout<<SMT.check_same(1,1,n,l,r)<<endl;
else if(op==3) cout<<SMT.check_up(1,1,n,l,r)<<endl;
else if(op==4) cout<<SMT.check_down(1,1,n,l,r)<<endl;
else if(op==5) {
int il=l,ir=r;
while(l<r) {
int md=(l+r+1)/2;
bool flag=SMT.check_up(1,1,n,l,md);
if(flag) l=md;
else r=md-1;
}
if(l==il||l==ir) cout<<0<<endl;
else cout<<SMT.check_down(1,1,n,l,ir)<<endl;
}
}
return 0;
}1008
发现只需要把 $1$ 和其他点连边，以及偶数点与其超集和子集连边，然后跑最短路即可。
1937ms 卡了过去（
过了之后 wjh 发现其实最多只用跳一次。
不过由于已经过了，就没改。
代码（赛时）
#pragma GCC optimize(2)
#include <bits/stdc++.h>
using namespace std;
struct Edge {
int Next, To;
long long val;
} edge[400010];
int Head[100010], NumEdge;
struct Node {
int x;
long long dis;
bool operator < (const Node & a) const {
return dis > a.dis;
}
};
void AddEdge(int x, int y, long long w) {
edge[++ NumEdge] = (Edge){Head[x], y, w};
Head[x] = NumEdge;
}
priority_queue<Node> q;
long long dis[100010];
bool vis[100010];
int T;
int n, m;
long long k;
int main () {
// freopen ("2.in", "r", stdin);
// freopen ("3.out", "w", stdout);
scanf ("%d", &T);
int x, y;
long long w;
while (T --) {
scanf ("%d%d%lld", &n, &m, &k);
NumEdge = 0;
for (int i = 1; i <= n; i ++) {
Head[i] = 0;
dis[i] = LONG_LONG_MAX / 2;
vis[i] = 0;
}
dis[1] = 0;
for (int i = 1; i <= m; i ++) {
scanf ("%d%d%lld", &x, &y, &w);
AddEdge (x, y, w);
AddEdge (y, x, w);
}
for (int i = 1; i <= n; i ++)
AddEdge (1, i, k * (1 | i));
q.push({1, 0});
int QS=1;
while(QS<=n) QS*=2;
QS--;
while (! q.empty()) {
x = q.top().x;
q.pop();
if (vis[x]) continue;
vis[x] = 1;
if (x % 2 == 0) {
for (int s = (x - 1) & x; s; s = (s - 1) & x) {
if (dis[x] + k * (x | s) < dis[s]) {
dis[s] = dis[x] + k * (x | s);
q.push({s, dis[s]});
}
}
for(int ss=(QS^x);ss;ss=(ss-1)&(QS^x)) {
int s=ss|x;
if(s>n) continue;
if(dis[x]+k*(x|s)<dis[s]) {
dis[s]=dis[x]+k*(x|s);
q.push({s,dis[s]});
}
}
}
for (int i = Head[x]; i; i = edge[i].Next) {
y = edge[i].To;
w = edge[i].val;
if (dis[x] + w < dis[y]) {
dis[y] = dis[x] + w;
q.push({y, dis[y]});
}
}
}
for (int i = 2; i <= n; i ++)
printf ("%lld ", dis[i]);
printf ("\n");
}
return 0;
}1011
题都没看。 wjh 写的。直接贴他代码
代码（赛时）
#pragma GCC optimize(2)
#include <bits/stdc++.h>
using namespace std;
int n;
struct Node {
long long x, y;
char c;
} a[200010];
long long f(long long t) {
long long minx = LONG_LONG_MAX;
long long maxx = - LONG_LONG_MAX;
long long miny = LONG_LONG_MAX;
long long maxy = - LONG_LONG_MAX;
for (int i = 1; i <= n; i ++) {
if (a[i].c == 'E') {
a[i].x += t;
maxx = max (maxx, a[i].x);
minx = min (minx, a[i].x);
maxy = max (maxy, a[i].y);
miny = min (miny, a[i].y);
a[i].x -= t;
}
if (a[i].c == 'W') {
a[i].x -= t;
maxx = max (maxx, a[i].x);
minx = min (minx, a[i].x);
maxy = max (maxy, a[i].y);
miny = min (miny, a[i].y);
a[i].x += t;
}
if (a[i].c == 'S') {
a[i].y -= t;
maxx = max (maxx, a[i].x);
minx = min (minx, a[i].x);
maxy = max (maxy, a[i].y);
miny = min (miny, a[i].y);
a[i].y += t;
}
if (a[i].c == 'N') {
a[i].y += t;
maxx = max (maxx, a[i].x);
minx = min (minx, a[i].x);
maxy = max (maxy, a[i].y);
miny = min (miny, a[i].y);
a[i].y -= t;
}
}
return 2 * (maxx - minx) + 2 * (maxy - miny);
}
int main () {
scanf ("%d", &n);
for (int i = 1; i <= n; i ++)
scanf ("%lld %lld %c", &a[i].x, &a[i].y, &a[i].c);
long long l = 0, r = 2e9, eps = 1;
while (r - l > eps) {
long long mid = (l + r) / 2;
long long lmid = mid - eps;
long long rmid = mid + eps;
if (f(lmid) < f(rmid))
r = mid;
else
l = mid;
}
printf ("%lld\n", f(l));
return 0;
}1012
同上，题都没看，wjh写的，直接贴他代码。
代码（赛时）
#include <bits/stdc++.h>
using namespace std;
int T;
int n, L, D;
int a[100010], b[100010];
int cnta, cntb;
int main () {
scanf ("%d", & T);
int x, A;
while (T --) {
scanf ("%d%d%d", &n, &L, &D);
cin >> A;
cnta = cntb = 0;
for (int i = 2; i <= n; i ++) {
scanf ("%d", &x);
if (x >= L)
a[++ cnta] = x;
else
b[++ cntb] = x;
}
sort (a + 1, a + cnta + 1);
sort (b + 1, b + cntb + 1);
if (A >= L) {
if (cntb >= 3 && A - b[1] > D) {
printf("Yes\n");
} else {
printf("No\n");
}
continue;
} else {
if (cnta >= 1 && cntb >= 2 && a[cnta] - min(b[1], A) > D) {
printf("Yes\n");
} else if (cntb >= 3 && b[cntb] - min(b[1], A) > D) {
printf("Yes\n");
} else {
printf("No\n");
}
continue;
}
}
}
