这次的比赛是真心比较狗，我TM的写了30min的树剖ZZ地直接memset超时了
话说我既然想到差分就应该去写差分的啊！
好了不过这次Rank还挺高的，终于要打进前10了当然是假的了。
好了下面开始讲题。链接
A. 幻灯结界
一道非常基础的贪心题，我们只需要两次贪心即可解决。
首先是对于改变防御值的问题，我们可以用一个很显然并且正确的贪心：总是把机会给最小的并且这个最小值应该小于改变的值。否则就没有得到最大的利用。
然后对于下一步我们可以通过一个叫排序不等式的东西。说白了就是：大的对大的，小的对小的。这样就可以保证\(max(b_i-a_i)\)最小。
其实上面的东西只需要用正常人的思想感性理解一下即可。
然后我们就sort一下，然后扫一遍即可。
CODE
#include<cstdio>
#include<algorithm>
using namespace std;
const int N=200005;
int a[N],b[N],n,x,y,ans;
inline char tc(void)
{
static char fl[100000],*A=fl,*B=fl;
return A==B&&(B=(A=fl)+fread(fl,1,100000,stdin),A==B)?EOF:*A++;
}
inline void read(int &x)
{
x=0; char ch=tc();
while (ch<'0'||ch>'9') ch=tc();
while (ch>='0'&&ch<='9') x=x*10+ch-'0',ch=tc();
}
inline int max(int a,int b)
{
return a>b?a:b;
}
int main()
{
//freopen("A.in","r",stdin); freopen("A.out","w",stdout);
register int i; read(n); read(x); read(y);
for (i=1;i<=n;++i)
read(a[i]); sort(a+1,a+n+1);
for (i=1;i<=n;++i)
read(b[i]); sort(b+1,b+n+1);
for (i=1;i<=n&&x>0;++i)
{
if (a[i]>=y) break;
a[i]=y; --x;
}
sort(a+1,a+n+1);
for (i=1;i<=n;++i)
ans=max(ans,b[i]-a[i]);
printf("%d",ans);
return 0;
}
B. 时之终末
一道很不错的状压DP的题。
首先我们发现数据范围：\(a<=16\)，所以果断状压。
设\(f_{i,j}\)表示前\(i\)个数中末尾\(j\)个数的情况（\(j\)不足则在前面补0），其中\(j\)是一个二进制数
其每一位分别表示对应位置上的数是否被选，例如当\(j=6\)时：
代表的状态为\(110\)，即表示这个数位置\(x\)之前的\(a_{x-2}\)和\(a_{x-1}\)都被选择了（不足则补0）
所以我们就能比较轻易地写出转移方程：
- \(f_{i,k}=max(f_{i,k},f_{i-1,j}+i>=a?s_k:0)\)（表示不选\(i\)这个位置上的数）
- \(f_{i,k|1}=max(f_{i,k|1},f_{i-1,j}+a_i+i>=a?s_k:0)\)（表示选\(i\)这个位置上的数）
其中，\(k=j<<1\)。其实就是把之前的状态都往前1位然后把新的添加进来。
\(s_k\)表示当状态是\(k\)时，通过额外方式获得的奖励分数。
那么接下来就是如何枚举这个\(s_k\)的问题了。
我们可以先分别处理出所有状态的情况，然后通过经典的枚举子集方法来解决。
我们设\(t_i\)表示一种状态为\(i\)的奖励价值，则有：
for (i=0;i<=cnt;++i)
for (j=i;j!=0;j=(j-1)&i)
s[i]+=t[j];
以上预处理的复杂度为\(O(3^a)\)。然后我们滚存一下\(f_{i,j}\)即可
CODE
#include<cstdio>
#include<cstring>
using namespace std;
const int N=105,M=55,STATE=(1<<16)+5;
int f[2][M][STATE],v[N],c[STATE],t[STATE],n,m,a,b,x,y,z,cnt,s,ans;
inline char tc(void)
{
static char fl[100000],*A=fl,*B=fl;
return A==B&&(B=(A=fl)+fread(fl,1,100000,stdin),A==B)?EOF:*A++;
}
inline void read(int &x)
{
x=0; char ch=tc(); int flag=1;
while (ch<'0'||ch>'9') { if (ch=='-') flag=-1; ch=tc(); }
while (ch>='0'&&ch<='9') x=x*10+ch-'0',ch=tc(); x*=flag;
}
inline int min(int a,int b)
{
return a<b?a:b;
}
inline int max(int a,int b)
{
return a>b?a:b;
}
int main()
{
//freopen("B.in","r",stdin); freopen("B.out","w",stdout);
register int i,j,k;
read(n); read(m); read(a); read(b);
for (i=1;i<=n;++i)
read(v[i]);
for (i=1;i<=b;++i)
{
read(x); read(y); s=0;
for (j=1;j<=x;++j)
read(z),s|=1<<(a-z);
t[s]+=y;
}
cnt=(1<<a)-1;
for (i=0;i<=cnt;++i)
for (j=i;j!=0;j=(j-1)&i)
c[i]+=t[j];
memset(f[0],163,sizeof(f[0])); int INF=f[0][0][0]; f[0][0][0]=0;
for (i=1;i<=n;++i)
{
int now=i&1,lst=now^1; memset(f[now],163,sizeof(f[now]));
for (j=0;j<=min(i-1,m);++j)
for (k=0;k<=cnt;++k)
if (f[lst][j][k]!=INF)
{
s=(k<<1)&cnt;
f[now][j][s]=max(f[now][j][s],f[lst][j][k]+(i>=a?c[s]:0));
f[now][j+1][s|1]=max(f[now][j+1][s|1],f[lst][j][k]+v[i]+(i>=a?c[s|1]:0));
}
}
for (ans=INF,i=0;i<=m;++i)
for (j=0;j<=cnt;++j)
ans=max(ans,f[n&1][i][j]);
printf("%d",ans);
return 0;
}
C. 伪神
一道需要思考的题目，告诉我们有些东西是暴力树剖也剖不过去的。
首先这题目一眼就可以看出上树剖的可能性，然后我们根据题意直接主席树修改最后查询大于t的数有即可
其实这个是一个树上差分的板子题。
我们先来讲一下差分这个东西（注意这不是差分约束）。我们现在开始考虑一个问题，我们对线性上的一段区间实行全部+1的操作，然后这个数组的值的变化。
我们可以发现，操作的区间\(x,y\)之间的数它们之间的相对值是不变的。
然后我们再结合前缀和的思想，令一个前缀和数组\(sum_i\)。然后我们每次操作的时候只需要把\(sum_x+1\)然后\(sum_{y+1-1}\)即可
最后我们只需要累加这个\(sum\)数组的值即可
然后对于树上的操作其实也是一样的，我们只需要在树剖过后的序列上差分即可
但是注意最后这个统计的过程是\(O(n)\)的，那么复杂度就让人受不了了。
我们再次利用差分的重要性质：操作区间内的数之间的相对着不变，我们每一次也只需要把操作过的区间单独做一下即可。中间那些没有用的直接弹掉即可。
然后就可以用一种类似于离散化并去重的方法最后sort一下累加区间即可
不过这样由于sort的复杂度只能得96pts，AC需要更高级的离线基排，这里只写了sort的96分版
具体操作还是看CODE吧
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long LL;
const int N=100005;
struct edge
{
int to,next;
}e[N<<1];
int n,m,a,b,x,y,t,cnt,tot,ans,rt=1,num,sum[N],head[N],dep[N],son[N],size[N],father[N],top[N],id[N],q[N*5];
inline char tc(void)
{
static char fl[100000],*A=fl,*B=fl;
return A==B&&(B=(A=fl)+fread(fl,1,100000,stdin),A==B)?EOF:*A++;
}
inline void read(int &x)
{
x=0; char ch=tc(); int flag=1;
while (ch<'0'||ch>'9') { if (ch=='-') flag=-1; ch=tc(); }
while (ch>='0'&&ch<='9') x=x*10+ch-'0',ch=tc(); x*=flag;
}
inline void write(int x)
{
if (x/10) write(x/10);
putchar(x%10+'0');
}
inline void add(int x,int y)
{
e[++cnt].to=y; e[cnt].next=head[x]; head[x]=cnt;
}
inline void swap(int &a,int &b)
{
int t=a; a=b; b=t;
}
inline void modify(int x,int y)
{
q[++num]=x; q[++num]=y+1; ++sum[x]; --sum[y+1];
}
inline void DFS1(int now,int fa,int d)
{
father[now]=fa; dep[now]=d; size[now]=1; int res=-1;
for (register int i=head[now];i!=-1;i=e[i].next)
if (e[i].to!=fa)
{
DFS1(e[i].to,now,d+1);
size[now]+=size[e[i].to];
if (size[e[i].to]>res) res=size[e[i].to],son[now]=e[i].to;
}
}
inline void DFS2(int now,int topf)
{
id[now]=++tot; top[now]=topf;
if (!son[now]) return;
DFS2(son[now],topf);
for (register int i=head[now];i!=-1;i=e[i].next)
if (e[i].to!=father[now]&&e[i].to!=son[now]) DFS2(e[i].to,e[i].to);
}
inline void change(int x,int y)
{
while (top[x]!=top[y])
{
if (dep[top[x]]<dep[top[y]]) swap(x,y);
modify(id[top[x]],id[x]); x=father[top[x]];
}
if (dep[x]<dep[y]) swap(x,y);
modify(id[y],id[x]);
}
inline void updata(int x)
{
modify(id[x],id[x]+size[x]-1);
}
int main()
{
//freopen("C.in","r",stdin); freopen("C.out","w",stdout);
register int i; read(n); read(m);
memset(e,-1,sizeof(e));
memset(head,-1,sizeof(head));
for (i=1;i<n;++i)
read(x),read(y),add(x,y),add(y,x);
DFS1(rt,-1,0); DFS2(rt,rt);
while (m--)
{
read(a); read(b); read(t);
for (i=1;i<=a;++i)
read(x),read(y),change(x,y);
for (i=1;i<=b;++i)
read(x),updata(x);
q[++num]=1; q[++num]=n+1;
sort(q+1,q+num+1); num=unique(q+1,q+num+1)-q-1;
for (x=0,i=1;i<num;++i)
x+=sum[q[i]],ans+=x>=t?q[i+1]-q[i]:0;
write(ans); putchar('\n');
for (i=1;i<=num;++i)
sum[q[i]]=0; num=ans=0;
}
return 0;
}