千万恨 争不得 朝夕

考试经过

从秦皇岛回来就状态特别不好，晚上躺下就睡，白天身上基本没劲，想一会就容易犯困
开题发现T1一个\(log\)是显然的，但应该卡不过，然而没咋多想，直接上了，预计60pts，感觉脑子不好使就没想正解
T2应该可做，想了会发现不太好维护，然后就开始犯困，好不容易想出来\(n^2\)的换根，十分明显的意识到离正解只差数据结构，然而这时偶然看见旁边JYF在打主席树，感觉要完，感觉自己不能维护，于是直接上的暴力，对着部分分一通乱写
T3的dp已经没有能力思考了，直接状压走人，T4没多看骗10分跑路了
所以估分60+65+25+10=160，结果60+45+25+0=130
T2T4写挂不说，四个题都有人切，所以就又垫底了

T1.树上的数

正解看上去像暴力
对于每个修改直接dfs，标记途经的点，遇到标记的点就返回，所以是线性的

#include <bits/stdc++.h>
using namespace std;
const int N=5000050;
struct node{
	int from,to,next;
}a[2*N];
int head[N],mm=1;
inline void add(int x,int y)
{
	a[mm].from=x;a[mm].to=y;
	a[mm].next=head[x];head[x]=mm++;
}
int aa,bb,fa[N],q[N],xx,yy,ans,an;
bool v[N];int n,m;
void dfs(int x)
{
	v[x]=1;ans--;
	for(int i=head[x];i;i=a[i].next)
	{
		int y=a[i].to;
		if(v[y])continue;
		dfs(y);
	}
}
signed main()
{
	freopen("tree.in","r",stdin);
	freopen("tree.out","w",stdout);
	cin>>n>>m>>aa>>bb;
	fa[2]=1;add(1,2);ans=n;
	for(int i=3;i<=n;i++)
	{
		fa[i]=((1ll*fa[i-1]*aa+bb)^19760817)%(i-1)+1;
		add(fa[i],i);
	}
	cin>>q[1]>>xx>>yy;
	for(int i=2;i<=m;i++)q[i]=(((1ll*q[i-1]*xx+yy)^19760817)^(i<<1))%(n-1)+2;
	for(int i=1;i<=m;i++)
	{
		int x=q[i];
		if(!v[x])dfs(x);
		an^=ans;
	}
	cout<<an<<endl;
	return 0;
}

T2.时代的眼泪

我考场上竟然忘了还有线段树合并这个东西，更别提神仙的树状数组了
先求出以1为根的答案，每个点贡献就是到根节点路径上大于\(w_x\)的个数
用树状数组维护，在dfs结束时删除，保证了数据结构中只有一条链就能查询了
剩下的就是换根dp，如果把根从\(x\)换到它原本的儿子\(y\)，那么贡献相比原来多算了\(y\)子树内小于\(w_x\)的个数，少算了\(y\)子树外小于\(w_y\)的个数，对应加减
考虑怎么快速维护，线段树合并常数较大不容易卡过，积累一个树状数组的技巧
统计\(x\)子树中的答案时，先在进子树前统计一遍，再把子树全插进去，再查一遍二者相减就是答案
对于子树外的答案，可以用全局的查询减去子树内的答案

#include <bits/stdc++.h>
using namespace std;
const int N=1000050;
inline int read()
{
	int x=0;char ch=getchar();
	while(ch<'0'||ch>'9')ch=getchar();
	while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
	return x;
}
struct node{
	int from,to,next;
}a[2*N];
int head[N],mm=1;
inline void add(int x,int y)
{
	a[mm].from=x;a[mm].to=y;
	a[mm].next=head[x];head[x]=mm++;
}
int w[N],lsh[N],n,m,cnt;
int p[N],f[N],g[N];long long an[N];
struct bit{
	int b[N];
	inline int lowbit(int x){return x&(-x);}
	inline void add(int p,int v)
	{
		for(int i=p;i<=n;i+=lowbit(i))
			b[i]+=v;
	}
	inline int getsum(int p)
	{
		int s=0;
		for(int i=p;i;i-=lowbit(i))
			s+=b[i];
		return s;
	}
	inline int get(int l,int r)
	{	
		return getsum(r)-getsum(l-1);
	}
}tr;
void dfs1(int x,int fa)
{
	p[x]=tr.get(w[x]+1,cnt);
	tr.add(w[x],1);
	for(int i=head[x];i;i=a[i].next)
	{
		int y=a[i].to;
		if(y==fa)continue;
		dfs1(y,x);
	}
	tr.add(w[x],-1);
}
void dfs2(int x,int fa)
{
	tr.add(w[x],1);
	for(int i=head[x];i;i=a[i].next)
	{
		int y=a[i].to;
		if(y==fa)continue;
		int s1=tr.get(1,w[x]-1),s2=tr.get(1,w[y]-1);
		dfs2(y,x);
		f[y]=tr.get(1,w[x]-1)-s1;
		g[y]=tr.get(1,w[y]-1)-s2;
	}
}
void dfs3(int x,int fa)
{
	for(int i=head[x];i;i=a[i].next)
	{
		int y=a[i].to;
		if(y==fa)continue;
		an[y]=an[x]+g[y]-f[y];
		dfs3(y,x);
	}	
}
signed main()
{
	freopen("tears.in","r",stdin);
	freopen("tears.out","w",stdout);
	n=read(),m=read();
	for(int i=1;i<=n;i++)w[i]=read();
	for(int i=1;i<=n;i++)lsh[i]=w[i];
	sort(lsh+1,lsh+n+1);
	cnt=unique(lsh+1,lsh+1+n)-lsh-1;
	for(int i=1;i<=n;i++)w[i]=lower_bound(lsh+1,lsh+cnt+1,w[i])-lsh;
	for(int i=1;i<n;i++)
	{	
		int x=read(),y=read();
		add(x,y);add(y,x);
	}
	dfs1(1,0);
	for(int i=1;i<=n;i++)an[1]+=p[i];
	dfs2(1,0);
	for(int i=1;i<=n;i++)g[i]=tr.get(1,w[i]-1)-g[i];
	dfs3(1,0);	
	for(int i=1;i<=m;i++)
	{
		int x=read();
		printf("%lld\n",an[x]);
	}
	return 0;
}

思维一定不能僵化，不要特地贴标签

T3.传统艺能

其实光dp的话是原题，可以类比43场的那个，多亏我还写了那么长题解
一共只有\(f_1,f_2,f_3\)，那么每次转移可以写成矩阵形式
这样不是像原来一样应对极大的\(m\)轮数，而是为了便于支持修改，将动态问题静态化
那么对于修改就可以线段树每个节点维护一个矩阵，pushup的时候就是两个矩阵相乘
所以就可以直接线段树套过来，与之类似的似乎还有之前的那个斐波，不过比这个难

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pp tr[id].p
#define pl tr[id*2].p
#define pr tr[id*2+1].p
const int N=100050;
const int mod=998244353;
char c[N],s[3];int n,m,an[5],ss[5];
struct tree{
	int l,r;
	int p[5][5];
}tr[4*N],ans;
inline void qi(int id)
{
	memset(pp,0,sizeof(pp));
	for(int i=1;i<=4;i++) 
	 for(int k=1;k<=4;k++)
	  for(int j=1;j<=4;j++)
	   pp[i][j]=(pp[i][j]+pl[i][k]*pr[k][j]%mod)%mod;
}
void build(int id,int l,int r)
{
	tr[id].l=l;tr[id].r=r;
	if(l==r)
	{	
		memset(pp,0,sizeof(pp));
		pp[1][1]=pp[2][2]=pp[3][3]=pp[4][4]=1;
		if(c[l]=='A')pp[2][1]=pp[3][1]=pp[4][1]=1;
		if(c[l]=='B')pp[1][2]=pp[3][2]=pp[4][2]=1;
		if(c[l]=='C')pp[1][3]=pp[2][3]=pp[4][3]=1;
		return;
	}
	int mid=(l+r)>>1;
	build(id*2,l,mid);build(id*2+1,mid+1,r);
	qi(id);
}
void change(int id,int p,int v)
{
	if(tr[id].l==tr[id].r)
	{	
		memset(pp,0,sizeof(pp));
		pp[1][1]=pp[2][2]=pp[3][3]=pp[4][4]=1;
		if(v==1)pp[2][1]=pp[3][1]=pp[4][1]=1;
		if(v==2)pp[1][2]=pp[3][2]=pp[4][2]=1;
		if(v==3)pp[1][3]=pp[2][3]=pp[4][3]=1;
		return;
	}
	int mid=(tr[id].l+tr[id].r)>>1;
	if(p<=mid)change(id*2,p,v);
	else change(id*2+1,p,v);
	qi(id);
}
tree get(int id,int l,int r)
{
	if(l<=tr[id].l&&r>=tr[id].r)return tr[id];
	int mid=(tr[id].l+tr[id].r)>>1;
	if(r<=mid)return get(id*2,l,r);
	if(l>mid)return get(id*2+1,l,r);
	tree ans,an1=get(id*2,l,mid),an2=get(id*2+1,mid+1,r);
	memset(ans.p,0,sizeof(ans.p));
	for(int i=1;i<=4;i++) 
	 for(int k=1;k<=4;k++)
	  for(int j=1;j<=4;j++)
	   ans.p[i][j]=(ans.p[i][j]+an1.p[i][k]*an2.p[k][j]%mod)%mod;
	return ans;
}
signed main()
{
	freopen("string.in","r",stdin);
	freopen("string.out","w",stdout);
	cin>>n>>m;scanf("%s",c+1);
	build(1,1,n);
	for(int i=1;i<=m;i++)
	{
		int op;scanf("%lld",&op);
		if(op==1)
		{
			int p;scanf("%lld%s",&p,s+1);
			change(1,p,s[1]-'A'+1);
		}
		else
		{
			int l,r;scanf("%lld%lld",&l,&r);
			ans=get(1,l,r);
			memset(ss,0,sizeof(ss));
			an[1]=an[2]=an[3]=0,an[4]=1;
			for(int i=1;i<=4;i++)
			 for(int j=1;j<=4;j++)
			  ss[i]=(ss[i]+an[j]*ans.p[j][i]%mod)%mod;
			printf("%lld\n",(ss[1]+ss[2]+ss[3])%mod);
		}
	}
	return 0;
}

T4.铺设道路

看着不太可做，但其实还是水题
把序列差分一下，那么每次相当于选择两个位置前面减一后面加一，尽快让所有数变成0
要使得操作数最小，那么选正的减负的加是最优的，所以可以贪心模拟
维护一个双端队列，每次遇见正数把他加进去，负数就考虑找正数和他配对然后删掉
代价最大就是找最左边的，否则是最右边，直接模拟即可

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N=300050;
const int mod=1e9+7;
int a[N],b[N],n,ans;
deque <pair<int,int> > q;
signed main()
{
	freopen("road.in","r",stdin);
	freopen("road.out","w",stdout);
	cin>>n;
	for(int i=1;i<=n;i++)scanf("%lld",&a[i]);
	for(int i=1;i<=n+1;i++)b[i]=a[i]-a[i-1];
	for(int i=1;i<=n+1;i++)ans+=max(b[i],(int)0);
	int sum1=0,sum2=0;
	for(int i=1;i<=n+1;i++)
	{
		if(!b[i])continue;
		if(b[i]>0)q.push_back(make_pair(i,b[i]));
		else
		{
			int x=b[i];
			while(q.size()&&q.front().second+x<=0)
			{
				sum1=(sum1+(i-q.front().first)*(i-q.front().first)%mod*q.front().second%mod)%mod;
				x+=q.front().second;q.pop_front();
			}
			if(x<0)
			{
				sum1=(sum1+(i-q.front().first)*(i-q.front().first)%mod*abs(x)%mod)%mod;
				int p=q.front().second+x,id=q.front().first;q.pop_front();
				q.push_front(make_pair(id,p));
			}
		}
	}
	assert(q.empty());
	for(int i=1;i<=n+1;i++)
	{
		if(!b[i])continue;
		if(b[i]>0)q.push_back(make_pair(i,b[i]));
		else
		{
			int x=b[i];
			while(q.size()&&q.back().second+x<=0)
			{
				sum2=(sum2+(i-q.back().first)*(i-q.back().first)%mod*q.back().second%mod)%mod;
				x+=q.back().second;q.pop_back();
			}
			if(x<0)
			{
				sum2=(sum2+(i-q.back().first)*(i-q.back().first)%mod*abs(x)%mod)%mod;
				int p=q.back().second+x,id=q.back().first;q.pop_back();
				q.push_back(make_pair(id,p));
			}
		}
	}
	cout<<ans<<endl<<sum2<<endl<<sum1<<endl;
	return 0;
}

考试总结

感觉之前犯的毛病还是在犯，考场犯困这个着实很痛苦，要尽量调整好状态
dp这方面差的太多了，接下来的dp不能再咕了，应该好好练一练
策略这块还是太草率，很多能拿的分没有拿到比较可惜，下次应该要好一点