神鹰中学
让你飞起来
1.拓扑排序
2.简单分析下题意：给出一些大小关系，问根据这些关系能不能确定排名，如果不能， 判断是信息不完全，还是信息冲突。
3.大概思路：
考虑出现冲突的情况： 当且仅当图中存在环，才会出现冲突，如：a > b, b > c, c > a， 则是冲突， 这种情况可在拓扑排序时确定。简要说一下拓扑排序：每次在有向图中找出一个入度为0的节点，加入队列，并删除该节点发出的所有边（在用队列实现的过程中，可直接把与之相连的节点的入度－1， 最后，如果还剩下节点未排序，则表示出现了环，因为环中没有节点入度为0。
考虑出现信息不完全的情况：如果某一时刻，有多个入度为0的点，那么信息肯定不完全，因为这样就没法确定这些入度为0的点之间的先后关系。
那么如何处理相等的情况：这种情况不能用拓扑排序来处理，因为，如果把a==b==c处理成a>b>c的话，那么有可能出现e<a, e > b是正确的情况， 所以，正确的方法是把相等的节点用并查集处理成一个节点。
the end...
#include<bits/stdc++.h>
using namespace std;
const int N=1e4+10;
int fa[N],in[N],A[N],B[N],n,m,sum;
char op[N];
vector<int> G[N];
int find(int x){
if(x!=fa[x]){
fa[x]=find(fa[x]);
}
return fa[x];
}
void topSort(){
queue<int> Q;
bool uncertain=false;
for(int i=0;i<n;i++){
if(in[i]==0&&find(i)==i) Q.push(i);
}
while(!Q.empty()){
if(Q.size()>1){
uncertain=true;
}
int now=Q.front();Q.pop();
sum--;
for(int i=0;i<G[now].size();i++){
if(--in[G[now][i]]==0){
Q.push(G[now][i]);
}
}
}
if(sum>0) puts("fantasy");
else if(uncertain) puts("dark");
else puts("deep");
}
int main(){
while(scanf("%d%d",&n,&m)!=EOF){
for(int i=0;i<n;i++){
fa[i]=i,in[i]=0;
G[i].clear();
}
sum=n;
for(int i=0;i<m;i++){
int a,b;
char s[3];
scanf("%d%s%d",&a,s,&b);
op[i]=s[0],A[i]=a,B[i]=b;
if(s[0]=='='){
int fx=find(a),fy=find(b);
if(fx!=fy){
fa[fx]=fy;
sum--;
}
}
}
for(int i=0;i<m;i++){
if(op[i] == '=') continue;
int a=find(A[i]),b=find(B[i]);
if(op[i]=='>'){
G[a].push_back(b);
in[b]++;
}
else{
G[b].push_back(a);
in[a]++;
}
}
topSort();
}
return 0;
}Inferno
1.贪心
2.题意：给一个仅包含 −1,0,1 的序列 a。在为 0 的位置中选 k 个更改为 1，其余更改为 −1，使得最大子段和最大，求最大子段和的最大值。
3.思路：
如果想让最大子段和最大，尽可能的把一串连续的 0 变为 1，插入一个 −1 一定很劣，因为会把一串前缀和单调增的序列变的不单调增，而子段和可以这样理解：画出一个前缀和的函数图像，可以认为子段和就是在函数上任取两点的函数值相减的绝对值。如果前缀和函数是单调增的，那最大子段和就很显然；倘若出现一个负数，前缀和必定会下降，把区间断成两部分，这样一定很劣。
可以去枚举最大子段和的左端点，然后往右边改 k 个 0。但又一个问题，不一定能改到 k 个 0 ，于是分类讨论右端点是否在这 k 个 0 内部。如果在的话那很简单，用单调队列维护前缀和加上前缀 0 的个数；如果不在就用前缀和减去前缀 0 的个数。
#include<bits/stdc++.h>
using namespace std;
const int N=1e7+10;
int n,k,a[N],lst[N],zero[N],cnt;
int sum1[N],sum2[N],mini[N];
void find_min(){
deque<pair<int,int> >dq;
for(int i=1;i<=n;++i){
while(!dq.empty()&&sum1[i]<=dq.front().first)dq.pop_front();
dq.push_front(make_pair(sum1[i],i));
while(!dq.empty()&&dq.back().second<zero[max(0,lst[i]-k+1)])dq.pop_back();
mini[i]=dq.size()?dq.back().first:0;
}
return;
}
int main(){
cin>>n>>k;
int lstt=0;
for(int i=1;i<=n;++i){
cin>>a[i];
sum1[i]=sum1[i-1];
sum2[i]=sum2[i-1];
if(a[i]==0){
sum1[i]++;
sum2[i]--;
zero[++cnt]=i;
lstt=cnt;
}
else{
sum1[i]+=a[i];
sum2[i]+=a[i];
}
lst[i]=lstt;
}
find_min();
int maxn=1,minii=0;
lstt=0;
for(int i=1;i<=n;++i){
int x=max(zero[max(0,lst[i]-k+1)]-1,0);
for(int j=lstt;j<=x;++j)minii=min(minii,sum2[j]);
lstt=x;
int ans=max(sum1[i]-mini[i],sum1[i]-sum1[max(0,zero[max(0,lst[i]-k+1)]-1)]+sum2[max(zero[max(0,lst[i]-k+1)]-1,0)]-minii);
maxn=max(maxn,ans);
}
cout<<maxn;
return 0;
}New Year Tree
1.线段树+dfs
2.要用到dfs序。本质上就是一棵树的先序遍历，所谓先序遍历就是先遍历根，然后遍历左子节点，最后遍历右子节点。需要把dfs序存在pos数组中，并把每个节点第一次遍历到的时间点和第二次遍历到的时间点存到in和out数组中，这样就成功地把一棵树转换为了线性结构。对一棵子树进行操作时，只需对这棵子树的根节点两次遍历到的时间戳中间的部分进行操作即可。
用dfs序，也就是pos数组对线段树进行操作，需要用到状态压缩，要把颜色压缩成二进制数到线段树中，所以要开long long。接下来基本上都是线段树区间修改，区间查询的模板了。需要注意的是，查询出来的值是一个经过状压后的数，我把它分解。可以借鉴树状数组的思想，即每次减去一个lowbit（一棵树上有数值的节点的最低位,不会的话可以先去学习一下树状数组，这里不再过多赘述）再让ans++，因为状压后只有0和1，有值的话一定是1。ans就是最后的答案。
#include<bits/stdc++.h>
using namespace std;
const int N=400010;
typedef long long ll;
struct node{
ll v,next;
}edge[N<<2];
ll head[N],tot,tim;
ll in[N],out[N],pos[N];
ll a[N];
ll ans[N<<2],lazy[N<<2];
void dfs(ll x,ll fa){
tim++;
in[x]=tim;
pos[tim]=x;
for(ll i=head[x];i;i=edge[i].next){
ll y=edge[i].v;
if(y==fa) continue;
dfs(y,x);
}
out[x]=tim;
}
void add(ll x,ll y){
tot++;
edge[tot].v=y;
edge[tot].next=head[x];
head[x]=tot;
}
void pushup(ll rt){
ans[rt]=ans[rt<<1]|ans[rt<<1|1];
}
void pushdown(ll rt){
if(lazy[rt]!=0){
lazy[rt<<1]=lazy[rt];
lazy[rt<<1|1]=lazy[rt];
ans[rt<<1]=lazy[rt];
ans[rt<<1|1]=lazy[rt];
lazy[rt]=0;
}
}
void build(ll l,ll r,ll rt){
if(l==r){
ans[rt]=1ll<<(a[pos[l]]);
return;
}
ll mid=(l+r)>>1;
build(l,mid,rt<<1);
build(mid+1,r,rt<<1|1);
pushup(rt);
}
void update(ll L,ll R,ll x,ll l,ll r,ll rt){
if(L<=l&&r<=R){
ans[rt]=1ll<<x;
lazy[rt]=1ll<<x;
return;
}
pushdown(rt);
ll mid=(l+r)>>1;
if(L<=mid) update(L,R,x,l,mid,rt<<1);
if(R>mid) update(L,R,x,mid+1,r,rt<<1|1);
pushup(rt);
}
ll query(ll L,ll R,ll l,ll r,ll rt){
if(L<=l&&r<=R)
return ans[rt];
pushdown(rt);
ll mid=(l+r)>>1;
ll res=0;
if(L<=mid) res|=query(L,R,l,mid,rt<<1);
if(R>mid) res|=query(L,R,mid+1,r,rt<<1|1);
return res;
}
ll lowbit(ll k){
return k&(-k);
}
ll getsum(ll x){
ll ans=0;
for(ll i=x;i>0;i-=lowbit(i))
ans++;
return ans;
}
int main(){
ll n,m,p,v,c;
scanf("%lld%lld",&n,&m);
for(ll i=1;i<=n;i++)
scanf("%lld",&a[i]);
for(ll i=1;i<n;i++){
ll x,y;
scanf("%lld%lld",&x,&y);
add(x,y);
add(y,x);
}
dfs(1,0);
build(1,n,1);
for(ll i=1;i<=m;i++){
scanf("%lld",&p);
if(p==1){
scanf("%lld%lld",&v,&c);
update(in[v],out[v],c,1,n,1);
}
else{
scanf("%lld",&v);
ll num=query(in[v],out[v],1,n,1);
printf("%lld\n",getsum(num));
}
}
return 0;
}Levels and Regions
1.斜率优化dp（也可以是李超线段树）
2.题意：将n个数分成k组，对于任意一组取其中第i个数的概率为t[k]/∑t[k]，求分组后取完所有数的最小期望。
3.f[i][j]表示把前j位分成i组所能最大优化的期望。
用s[i]记录t[i]前缀和，用p[i]记录t[i]倒数的前缀和。
于是得到DP方程：f[i][j]=max(f[i−1][k]+s[k]∗(p[j]−p[k]))
关于DP方程作出如下解释：
1.第ii组的状态只与第i−1组有关，需在第二维枚举k找最优解；
2.由于取第i组中第k个数的概率为t[k]/s[k],期望为s[k]/t[k],则分组后“被优化”的期望为s[k]∗(p[j]−p[k])
我们发现这样写肯定要超时，由于方程中仅有max函数，想到使用斜率优化加速。
考虑f[i][a]和f[i][b]的值，设f[i][a]>f[i][b]，
则可得到f[i−1][a]+s[a]∗(p[j]−p[a])>f[i−1][b]+s[b]∗(p[j]−p[b])
设f[i−1][a]−s[a]∗p[a]=y(a)，拆项移项得到y(a)−y(b)<(s[b]−s[a])∗p[j]。
#include<bits/stdc++.h>
#define int long long
#define inf 10000000000000000
using namespace std;
const int maxn=200005,maxm=55;
int i,j,k,m,n,l,r;
int a[maxn],suma[maxn],q[maxn];
double b[maxn],c[maxn],sumb[maxn],sumc[maxn],f[maxm][maxn];
inline int x(int p){
return suma[p];
}
inline double y(int p,int c){
return f[c-1][p]+1.0*suma[p]*sumb[p]-sumc[p];
}
inline double slope(int a,int b,int c){
if(x(a)==x(b))
return y(a,c)>y(b,c)? inf:-inf;
return 1.0*(y(a,c)-y(b,c))/(x(a)-x(b));
}
signed main(){
scanf("%lld%lld",&n,&m);
for(i=1;i<=n;i++){
scanf("%lld",&a[i]);
suma[i]=suma[i-1]+a[i];
b[i]=1.0/a[i],sumb[i]=sumb[i-1]+b[i];
c[i]=1.0*suma[i]/a[i],sumc[i]=sumc[i-1]+c[i];
}
for(i=1;i<=n;i++)
f[0][i]=inf;
for(i=1;i<=m;i++){
l=1,r=0;
q[++r]=0;
for(j=1;j<=n;j++){
while(l<r&&slope(q[l+1],q[l],i)<=sumb[j])
l++;
f[i][j]=f[i-1][q[l]]+sumc[j]-sumc[q[l]]-suma[q[l]]*(sumb[j]-sumb[q[l]]);
while(l<r&&slope(j,q[r-1],i)<=slope(q[r],q[r-1],i))
r--;
q[++r]=j;
}
}
printf("%.10lf\n",f[m][n]);
return 0;
}总之，有点难度，有的题目不好理解，有的题没写出暴力，还得练练
