NOIP提高组模拟赛8
A. 队长快跑
完全没想到可以这样DP，一直在想排序然后怎么搞，中间因为理解有误打了个奇奇怪怪的线段树，发现错误已经过去2h了，看看实在没思路直接跑路，然后基本暴零。。。。。WTCL
因为\(A_{P_i}<=B_{p_i}\)就会爆炸，所以后摧毁的水晶的B一定小于前面已经摧毁的A的最小值
设\(f[i][j]\)表示前\(i\)个水晶\(a[i]\)最小值为j能摧毁的最多的水晶数
如果不摧毁当前水晶\(f[i][j]=f[i-1][j]\)
摧毁当前水晶\(f[i][min(j,a[i])]=max(f[i-1][j])+1\)
这样转移显然是\(O(N^2)\)的，考虑如何优化
我们将\(min\)展开，分情况讨论
原来DP可以写成
for (int j = 1; j <= tot; ++j)
f[i][j] = f[i - 1][j];
if (a[i].b > a[i].a)
for (int j = a[i].b + 1; j <= tot; ++j)
f[i][a[i].a] = max(f[i][a[i].a], f[i - 1][j] + 1);
else
{
for (int j = a[i].b + 1; j < a[i].a; ++j)
f[i][j] = f[i - 1][j] + 1;
for (int j = a[i].a; j <= tot; ++j)
f[i][a[i].a] = max(f[i][a[i].a], f[i - 1][j] + 1);
}
然后，就要用到OIER最喜欢的线段树了，继承操作就是啥都不做，取\(max\)就是区间最值，更新就是单点修改，还有个区间加，直接用线段树板子即可
由于\(Eafoo\)大佬的操作，马蜂有点诡异
#include
#include
#include
using namespace std;
const int maxn = 100005;
struct node
{
int a, b;
} a[maxn];
int ls[maxn << 1 | 1], tot;
void lsh(int n)
{
tot = n << 1;
for (int i = 1; i <= n; ++i)
ls[(i << 1) - 1] = a[i].a, ls[i << 1] = a[i].b;
sort(ls + 1, ls + tot + 1);
tot = unique(ls + 1, ls + tot + 1) - ls - 1;
for (int i = 1; i <= n; ++i)
{
a[i].a = upper_bound(ls + 1, ls + tot + 1, a[i].a) - ls - 1;
a[i].b = upper_bound(ls + 1, ls + tot + 1, a[i].b) - ls - 1;
}
}
int tree[maxn << 3], lazy[maxn << 3];
void push_down(int x, int l, int r)
{
int mid = (l + r) >> 1;
tree[x << 1] += lazy[x];
tree[x << 1 | 1] += lazy[x];
lazy[x << 1] += lazy[x];
lazy[x << 1 | 1] += lazy[x];
lazy[x] = 0;
}
void add(int x, int l, int r, int L, int R)
{
if (L <= l && r <= R)
{
++lazy[x];
++tree[x];
return;
}
if (lazy[x])
push_down(x, l, r);
int mid = (l + r) >> 1;
if (L <= mid)
add(x << 1, l, mid, L, R);
if (R > mid)
add(x << 1 | 1, mid + 1, r, L, R);
tree[x] = max(tree[x << 1], tree[x << 1 | 1]);
}
int ask(int x, int l, int r, int L, int R)
{
if (L <= l && r <= R)
return tree[x];
if (tree[x])
push_down(x, l, r);
int mid = (l + r) >> 1;
int ans = -1;
if (L <= mid)
ans = ask(x << 1, l, mid, L, R);
if (R > mid)
ans = max(ans, ask(x << 1 | 1, mid + 1, r, L, R));
return ans;
}
void update(int x, int l, int r, int d, int ne)
{
if (l == r)
{
tree[x] = max(tree[x], ne);
return;
}
if (tree[x])
push_down(x, l, r);
int mid = (l + r) >> 1;
if (d <= mid)
update(x << 1, l, mid, d, ne);
if (d > mid)
update(x << 1 | 1, mid + 1, r, d, ne);
tree[x] = max(tree[x << 1], tree[x << 1 | 1]);
}
int main()
{
int n;
scanf("%d", &n);
for (int i = 1; i <= n; ++i)
scanf("%d%d", &a[i].a, &a[i].b);
lsh(n);
for (int i = 1; i <= n; ++i)
{
if (a[i].b >= a[i].a)
{
int k = ask(1, 1, tot, a[i].b + 1, tot) + 1;
update(1, 1, tot, a[i].a, k);
}
else
{
int k = ask(1, 1, tot, a[i].a, tot) + 1;
update(1, 1, tot, a[i].a, k);
add(1, 1, tot, a[i].b, a[i].a - 1);
}
}
printf("%d\n", tree[1]);
return 0;
}
B. 影魔
又是一道我不会的题真的是太弱了
颜色分开考虑，该颜色对所在子树均有贡献，子树中有多个颜色贡献只算一次，用树上差分的思想，维护链并（又一个新名词？），在dfs序上对应结点+1，与相邻的同色结点的lca处-1，这样就保证贡献只有1，为了得到dfs序相邻的结点编号，使用set进行维护（set是有序的）。
然后所有颜色搞完时候，问题就变成了求子树权值和，因为还有深度所以使用主席树，每个深度对应的dfs序为一个新的版本
在对应版本查找对应子树即可。。。
由于本人太菜所以写不出什么东西了，不懂的看其他大佬的博客吧
代码完全仿fengwu学长的写法（因为我还不会主席树）
学了主席树以后再看有没有需要修正的吧。挖坑
#include
#include
#include
#include
using namespace std;
const int maxd=100005;
struct edge{
int net,to;
}e[maxd<<1|1];
int head[maxd],tot;
int n,m;
void add(int u,int v){
e[++tot].net=head[u];
head[u]=tot;
e[tot].to=v;
}
struct node{
int col,dep,dfsl,dfsr,id;
bool operator < ( node x)const{
return x.dfsl>dfsl;
}
}d[maxd];
setst[maxd];
bool cmp(node x,node y){
if(x.dep!=y.dep)return x.dep=0;--i)if(dep[fa[x][i]]>=dep[y])x=fa[x][i];
if(x==y)return x;
for(int i=20;i>=0;--i)if(fa[x][i]!=fa[y][i])x=fa[x][i],y=fa[y][i];
return fa[x][0];
}
struct president_tree{
int left_son[maxd*80],right_son[maxd*80];
int siz[maxd*80];
int tmp;
void pushup(int x){
siz[x]=0;
if(left_son[x])siz[x]+=siz[left_son[x]];
if(right_son[x])siz[x]+=siz[right_son[x]];
return;
}
void insert(int pre,int &x,int l,int r,int pos,int v){
if(!x){x=++tmp;siz[x]=siz[pre];left_son[x]=left_son[pre];right_son[x]=right_son[pre];}
if(l==r){siz[x]+=v;return;}
int mid=(l+r)>>1;
if(pos<=mid){
if(left_son[x]==left_son[pre])left_son[x]=0;
insert(left_son[pre],left_son[x],l,mid,pos,v);
}else{
if(right_son[x]==right_son[pre])right_son[x]=0;
insert(right_son[pre],right_son[x],mid+1,r,pos,v);
}
pushup(x);return;
}
int query(int x,int l,int r,int L,int R){
if(!x)return 0;
if(L<=l&&r<=R)return siz[x];
int mid=(l+r)>>1,ans=0;
if(L<=mid)ans+=query(left_son[x],l,mid,L,R);
if(R>mid)ans+=query(right_son[x],mid+1,r,L,R);
return ans;
}
}tree;
int main(){
//freopen(,r,stdin);
scanf("%d%d",&n,&m);
for(int i=1;i<=n;++i)scanf("%d",&d[i].col),d[i].id=i;
for(int i=2;i<=n;++i){int x;scanf("%d",&x);add(x,i);}
d[1].dep=1;dfs(1);
for(int i=1;i<=n;++i){
dep[i]=d[i].dep;
dfsl[i]=d[i].dfsl;
dfsr[i]=d[i].dfsr;
}
sort(d+1,d+n+1,cmp);
for(int i=1;i<=n;++i){
tree.insert(root[d[i].dep-1],root[d[i].dep],1,n,d[i].dfsl,1);
st[d[i].col].insert(d[i]);
int lca;
node nu;nu.id=0;
node pre=st[d[i].col].find(d[i])==st[d[i].col].begin()?nu:*--st[d[i].col].find(d[i]);
node nxt=((++st[d[i].col].find(d[i]))==st[d[i].col].end())?nu:*++st[d[i].col].find(d[i]);
if(pre.id){
lca=LCA(d[i].id,pre.id);
tree.insert(root[d[i].dep-1],root[d[i].dep],1,n,dfsl[lca],-1);
}
if(nxt.id){
lca=LCA(d[i].id,nxt.id);
tree.insert(root[d[i].dep-1],root[d[i].dep],1,n,dfsl[lca],-1);
}
if(pre.id&&nxt.id){
lca=LCA(pre.id,nxt.id);
tree.insert(root[d[i].dep-1],root[d[i].dep],1,n,dfsl[lca],1);
}
}
for(int i=1;i<=m;++i){
int u,d;scanf("%d%d",&u,&d);
printf("%d\n",tree.query(root[min(dep[u]+d,max_dep[u])],1,n,dfsl[u],dfsr[u]));
}
return 0;
}
C. 抛硬币
本次考试最水的题，然而他放到了T3
设\(f[i][j]\)表示后i个字符，以第i个字符开头，有多少长度为j的本质不同的子序列
可以发现如果i后面有多个相同的字母，因为后面相同字母开头的序列，前面的一定能得到，那么本质不同的个数就是第一个字母的方案数
\(f[i][j]=\sum_{k=1}^{26} f[pos[i][k]][j-1]\)
预处理出每个位置向后（不包括自身）a-z第一个字母出现的位置
然后记忆化搜索即可
#include
#include
using namespace std;
const int mod=998244353;
char c[3015];
int n;
int rem[3005][3005];
int flag[27],re[3005][27];
bool vis[3005][3005];
int ask(int x,int l){
if(vis[x][l])return rem[x][l];
vis[x][l]=1;
if(n-x+1==l)return rem[x][l]=1;
if(n-x+1=1;--i){
for(int j=1;j<=26;++j)re[i][j]=flag[j];
rem[i][1]=1;vis[i][1]=1;
flag[c[i]-'a'+1]=i;
}
long long ans=0;
for(int i=1;i<=n;++i)int k=ask(i,l);
for(int i=1;i<=26;++i){
int k=flag[i];
ans=(ans+rem[flag[i]][l])%mod;
}
printf("%lld\n",ans);
return 0;
}