yyd的比赛

T1

这道题根据性质连边，然后用拓扑判断就行了
首先是建图，对于等于的我们用并查集将他合并一下，然后就建好图了，然后我们进行拓扑，当发现在拓扑中同时出现两个点入度为零，就不能得到完整的，若不能进行拓扑，就会有冲突。

#include<bits/stdc++.h>
using namespace std;
#define int long long
int read() {int x=0,f=1;char ch=getchar();while(ch>'9'||ch<'0') {if(ch=='-') f=-1;ch=getchar();}while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();return x*f;
}
const int N=1e5+10;
struct node {int to,nxt;
} e[N*2];
int head[N],tot;
void add(int a,int b) {tot++;e[tot].to=b;e[tot].nxt=head[a];head[a]=tot;
}
int fa[N];
int get(int x) {if(x==fa[x]) return x;else return fa[x]=get(fa[x]);
}
int n,m;
int a[N],b[N],in[N];
char ss[N];
int cnt;
bool pan;
void tp() {queue<int> q;for(int i=1; i<=n; i++) {if(in[i]==0&&get(i)==i) q.push(i);}while(q.size()) {if(q.size()>1) pan=true;int x=q.front();q.pop();cnt--;for(int i=head[x]; ~i; i=e[i].nxt) {int y=e[i].to;in[y]--;if(in[y]==0) q.push(y);}}
}
signed main() {
//	freopen("005.in","r",stdin);while(scanf("%lld %lld",&n,&m)!=EOF) {cnt=n;tot=0;memset(e,0,sizeof e);memset(head,-1,sizeof head);memset(in,0,sizeof in);for(int i=1; i<=n; i++) {fa[i]=i;}for(int i=1; i<=m; i++) {int x,y;char s;x=read()+1;cin>>s;y=read()+1;a[i]=x;ss[i]=s;b[i]=y;if(s=='=') {cnt--;x=get(x),y=get(y);fa[x]=y;}}for(int i=1; i<=m; i++) {if(ss[i]=='=') continue;int x=get(a[i]),y=get(b[i]);if(ss[i]=='>') {add(y,x);in[x]++;} else {add(x,y);in[y]++;}}pan=false;tp();if(cnt>1) puts("fantasy");else if(pan) puts("dark");else puts("deep");}return 0;
}

多测不清空，含泪见祖宗

T2

先对原数列做一遍前缀和得到 $s_i$ , 设对空位全部填 $1$ 的前缀和序列为 $p_i$ , 全填 $-1$ 的前缀和为 $q_i$, $0$ 个数的前缀和为 $c_i$ 。

考虑枚举最大子段的开头 $l$ , 则若要使最大子段和最大, 后面 $k$ 个空都填 $1$ 。则此时有两种情况:

• 若取的右端点 $r$ 在 $k$ 个 $0$ 以内, 那么其最大子段和为 $s_r-s_{l-1}+c_r-c_{l-1}=p_r-p_{l-1}$ 。
• 若取的右端点在 $k$ 个 $0$ 以外, 则其最大子段和为 $s_r-s_{l-1}+2k-c_r+c_{l-1}=q_r-q_{l-1}+2k$ 。

于是我们维护 $q$ 的后缀最大值，然后 $p$ 使用单调队列维护区间最大值即可。
对于后缀最大值我们可以直接预处理出来

#include <bits/stdc++.h>
using namespace std;
#define int long long
int read(){int x=0,f=1;char ch=getchar();while(ch>'9'||ch<'0'){if(ch=='-') f=-1;ch=getchar();}while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();return x*f;
}const int N=1e7+10;
int c0[N],c1[N],c2[N];
int a[N],q[N];
int minn=1e9;signed main() {freopen("003.in","r",stdin);	int n=read(),k=read();int l=1,r=0,j=0;for(int i=1; i<=n; i++) {a[i]=read();c0[i]=c0[i-1];if(a[i]==1) {c1[i]=c1[i-1]+1;c2[i]=c2[i-1]+1;}else if(!a[i]){c1[i]=c1[i-1]+1;c2[i]=c2[i-1]-1;c0[i]++;} else {c1[i]=c1[i-1]-1;c2[i]=c2[i-1]-1;}}int ans=-1e9;
//	for(int i=1;i<=n;i++){
//		cout<<"OPO"<<c[i]<<endl;
//	}for(int i=1; i<=n; i++) {while(l<=r&&c0[i]-c0[q[l]-1]>k) l++;
//		while(l<=r) --r,l++;while(l<=r&&c1[i-1]<=c1[q[r]-1]) r--;q[++r]=i;
//		cout<<r<<endl;ans=max(ans,c1[i]-c1[q[l]-1]);while(c0[i]-c0[j-1]>=k) minn=min(minn,c2[j-1]),j++;ans=max(ans,c2[i]-minn+2*k);
//		cout<<ans<<endl;}printf("%lld",ans);return 0;
}

T3

这道题一看到以为是图论，但通过分析我们可以发现，这不只是图论那么简单，我们发现修改是修改的一个区间，查询也相当于查询的一个区间，我们发现进行区间查询和区间合并的可以通过线段树来完成，n个点和n-1条边，肯定是一棵树，那么我们思考如何将一棵树转化成一颗线段树。

我们采用中序遍历，记录dfs序（两次遍历到某个点的时间），在这段时间内的点构成一个区间，我们就可以用这个DFS序来建线段树。
因为可能会有重复的，所以我们可以用二进制来表示，可以用lowbit或者直接使用bitset来维护这棵线段树

只因你太美，考试居然理解错题意了
可以看到，题意说的是要直接将子树的点全部改成某个值，而不是加上。所以我们的蓝标记直接覆盖就行了

#include<bits/stdc++.h>
#define N 400010
#define int long longusing namespace std;
int read(){int x=0,f=1;char ch=getchar();while(ch>'9'||ch<'0'){if(ch=='-') f=-1;ch=getchar();}while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();return x*f;
}
struct node{                int v,nxt;
}e[N<<2];
int head[N],tot,tim;
int in[N],out[N],pos[N];int a[N];
int ans[N<<2],lazy[N<<2];        void dfs(int x,int fa){tim++;in[x]=tim;pos[tim]=x;for(int i=head[x];i;i=e[i].nxt){int y=e[i].v;if(y==fa) continue;dfs(y,x);}out[x]=tim;
}void add(int x,int y){tot++;e[tot].v=y;e[tot].nxt=head[x];head[x]=tot;
}void pushup(int rt){ans[rt]=ans[rt<<1]|ans[rt<<1|1]; 
}void pushdown(int 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(int l,int r,int rt){if(l==r){ans[rt]=1ll<<(a[pos[l]]);return;}int mid=(l+r)>>1;build(l,mid,rt<<1);build(mid+1,r,rt<<1|1);pushup(rt);
}void modify(int L,int R,int x,int l,int r,int rt){if(L<=l&&r<=R){ans[rt]=1ll<<x;  lazy[rt]=1ll<<x;return; }pushdown(rt);int mid=(l+r)>>1;if(L<=mid) modify(L,R,x,l,mid,rt<<1);if(R>mid) modify(L,R,x,mid+1,r,rt<<1|1);pushup(rt);
}int query(int L,int R,int l,int r,int rt){if(L<=l&&r<=R)return ans[rt];pushdown(rt);int mid=(l+r)>>1;int 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;
}int lowbit(int k){return k&(-k);
}int getsum(int x){int ans=0;for(int i=x;i>0;i-=lowbit(i))ans++;return ans;
}signed main(){int n,m,p,v,c;n=read(),m=read();for(int i=1;i<=n;i++) a[i]=read();for(int i=1;i<n;i++){int x=read(),y=read(); add(x,y);add(y,x);}dfs(1,0);build(1,n,1);for(int i=1;i<=m;i++){p=read();if(p==1){v=read(),c=read();modify(in[v],out[v],c,1,n,1);}else{v=read();int num=query(in[v],out[v],1,n,1);printf("%lld\n",getsum(num));}}return 0;
}

T4

这个题目考虑DP。
然后还是推式子，斜率优化：
首先考虑暴力，式子在这里式子
有点斜率优化的感觉, 试试：若从 a 转移而来（即 k=a ）比从 b 转移而来优，且 a>b （即 a 在 b 后面), 则:
$f_a+x_i-x_a-s_a\left(y_i-y_a\right)<f_b+x_i-x_b-s_b\left(y_i-y_b\right)$
化简得：
$\frac{\left(f_a-x_a+y_a{s}_a\right)-\left(f_b-x_b+y_b{s}_b\right)}{s_a-s_b}<y_i$

$\left(f_a-x_a+y_a{s}_a\right),s_a$ 与 $y_i$ 都是单调递增的, 可以斜率优化 dp 做,单调队列维护下凸壳即可。

#include<bits/stdc++.h>
using namespace std;
int n,k,h,r;
long long t[200010],q[200010];
long long s[200010];
double p[200010];
double f[60][200010];
double ans,tot;
double v(long long x,long long y,int i) {return (f[i-1][x]-s[x]*p[x]-f[i-1][y]+s[y]*p[y])*1./(s[y]-s[x]);
}
int main() {scanf("%d%d",&n,&k);for(int i=1; i<=n; i++) {scanf("%lld",&t[i]);s[i]=s[i-1]+t[i];p[i]=p[i-1]+1./t[i];tot+=s[i]*1./t[i];}for(int i=2; i<=k; i++) {h=0;r=0;for(int j=1; j<=n; j++) {while(h<r&&v(q[h],q[h+1],i)<p[j]) h++;while(h<r&&v(q[r-1],q[r],i)>v(q[r],j,i)) r--;f[i][j]=f[i-1][q[h]]+s[q[h]]*(p[j]-p[q[h]]);q[++r]=j;}}ans=tot-f[k][n];printf("%.10lf",ans);return 0;
}