A组
T1.dostavljac 餐馆
树形DP，怎么处理走回来呢？考场想了f[i][j][0/1]表示以i为根子树，用了j秒，并且选/不选当前点，不能转移，为什么呢？因为这个第三维完全没用，可以在一开始就考虑。
正解f[i][j][0/1]表示以i为根的子树，用了j秒，并且回到/不回到当前点，这样就可以分类转移了。
转移时考虑做到子树v，分三类讨论。
注意一个点只能选一次，倒序循环。
#include#include using namespace std;inline int rd(){ int ret=0,f=1;char c; while(c=getchar(),!isdigit(c))f=c=='-'?-1:1; while(isdigit(c))ret=ret*10+c-'0',c=getchar(); return ret*f;}const int MAXN=1005;struct Edge{ int next,to;}e[MAXN];int ecnt,head[MAXN],ind[MAXN];inline void add(int x,int y){ e[++ecnt].next = head[x]; e[ecnt].to = y; head[x] = ecnt;}int n,m;int f[MAXN][MAXN*2][2];int a[MAXN];int ans=0; void dfs(int x,int pre){ f[x][1][0]=f[x][1][1]=a[x]; int tmp=0,mx=0; for(int i=head[x];i;i=e[i].next){ int v=e[i].to; if(v==pre) continue; dfs(v,x); for(int j=m;j>=0;j--){ for(int k=m-j-1;k>=0;k--){ f[x][j+k+2][0]=max(f[x][j+k+2][0],f[x][j][0]+f[v][k][0]); f[x][j+k+2][1]=max(f[x][j+k+2][1],f[x][j][1]+f[v][k][0]); f[x][j+k+1][1]=max(f[x][j+k+1][1],f[x][j][0]+f[v][k][1]); } } }}void solve(){ dfs(1,0); cout<
T2.range 区间
分块维护块内前缀后缀积，块大小为k正好满足。
被一般套路限制了，这个分块不需要真的开新数组存，那样空间是n^2的（用vector可以少一些，但依旧很大）
正解是直接在原位置上维护这个位置在块内的前缀后缀，这样就可以啦。
这题卡空间(差评)
#include#include #include //#define int long longusing namespace std;inline int rd(){ int ret=0,f=1;char c; while(c=getchar(),!isdigit(c))f=c=='-'?-1:1; while(isdigit(c))ret=ret*10+c-'0',c=getchar(); return ret*f;}const int MAXN=20000005;int n,m,mod;int A,B,C,D;int a[MAXN];int num;int pre[MAXN],lst[MAXN];#define l(x) ((((x)-1)*m)+1)#define r(x) ((x)==num?n:((x)*m))#define bl(x) ((((x)-1)/m)+1)signed main(){ freopen("range.in","r",stdin); freopen("range.out","w",stdout); n=rd();m=rd();mod=rd(); A=rd();B=rd();C=rd();D=rd(); a[1]=A; long long tmp; for(int i=2;i<=n;i++) { tmp=1ll*(a[i-1]*1ll*B+C)%D; a[i]=(int) tmp; } num=n/m;if(n%m)num++; for(int i=1;i<=num;i++){ int L=l(i),R=r(i); pre[L]=a[L]; for(int j=L+1;j<=R;j++){ tmp=(pre[j-1]*1ll*a[j])%mod; pre[j]=(int)tmp; } lst[R]=a[R]; for(int j=R-1;j>=L;j--){ tmp=1ll*(lst[j+1]*1ll*a[j])%mod; lst[j]=(int)tmp; } } int ans=0; for(int i=1;i<=n-m+1;i++){ int j=i+m-1; if(bl(i)==bl(j)){ans^=pre[r(bl(i))];continue;} tmp=1ll*(lst[i]*1ll*pre[j])%mod; ans^=(int)tmp; } cout<