D2. Construct an Array (Hard Version)题目链接Codeforces 2245D2算法标签图论、2-SAT 思想、贪心、构造思路把每条限制看成一条带类型的无向边类型 1 要求两端之和非负类型 2 要求两端之和为负。对于当前还没有处理的点如果它只连接一种类型的边就可以直接确定它的正负号只剩类型 1 边就赋一个较大的正数只剩类型 2 边就赋一个绝对值较大的负数。用队列不断删除这样的点并令最先删除的点绝对值最大依次取n,n-1,...,1。处理点u时它的绝对值大于所有尚未处理的相邻点因此它可以主导两数之和的符号正数一定满足剩余的类型 1 边负数一定满足剩余的类型 2 边。删点后更新邻点两类边的数量新出现的可删点继续入队。如果最后还有点没有删除那么剩余图中每个点都同时连接两种边。取绝对值最大的点若它为正与它相连的类型 2 边要求出现绝对值更大的负数若它为负其类型 1 邻点必须是绝对值不小于它的正数再沿这个正数的一条类型 2 边同样会要求更大的负数均矛盾。因此此时无解。时间复杂度为O(nm)空间复杂度为O(nm)。代码#includebits/stdc.husingnamespacestd;intmain(){ios::sync_with_stdio(false);cin.tie(nullptr);intt;cint;while(t--){intn,m;cinnm;vectorvectorintedge(n1);vectorarrayint,2d(n1);while(m--){into,u,v;cinouv;o--;edge[u].push_back(o?-v:v);edge[v].push_back(o?-u:u);d[u][o];d[v][o];}vectorintans(n1);vectorboolvis(n1);queueintq;for(intu1;un;u){if(!d[u][0]||!d[u][1]){q.push(u);vis[u]true;}}intcurn;while(!q.empty()){intuq.front();q.pop();ans[u](d[u][0]?1:-1)*cur--;for(intv:edge[u]){intov0;vabs(v);d[v][o]--;if(!vis[v](!d[v][0]||!d[v][1])){q.push(v);vis[v]true;}}}if(cur)coutNO\n;else{coutYES\n;for(inti1;in;i)coutans[i] \n[in];}}}E. Tom and Jerry题目链接Codeforces 2245E算法标签博弈论、树形 DP、DFS、树思路这道博弈的关键结论是第一步选择的路径为必胜路径当且仅当路径的两个端点度数为奇数所有内部点的度数为偶数。这个结论可以对后续游戏状态归纳得到直观上路径端点已经使用 1 条边、内部点已经使用 2 条边所以恰好要求路径上每个点剩余的出边数都是偶数。接下来只需统计这样的路径。将树以 1 为根dp[u]表示u的子树中有多少个奇度点可以沿着一条内部全为偶度点的链连接到u。若u的度数为奇数u只能作为路径端点不能作为内部点。每个儿子的dp[v]都能和u组成一条合法路径所以加入答案并令dp[u]1。若u的度数为偶数路径可以穿过u。从两个不同儿子子树中各取一个奇度端点即可组成合法路径因此累加所有dp[v]的两两乘积同时令dp[u]为所有儿子dp[v]之和继续向父亲传递。时间复杂度为O(n)空间复杂度为O(n)。代码#includebits/stdc.husingnamespacestd;vectorvectorintedge;vectorlonglongdp;longlongans;voiddfs(intu,intfa){longlongsum0;booloddedge[u].size()%2;for(intv:edge[u]){if(vfa){continue;}dfs(v,u);if(odd){ansdp[v];}else{ansdp[v]*sum;sumdp[v];}}dp[u]odd?1:sum;}intmain(){ios::sync_with_stdio(false);cin.tie(nullptr);intt;cint;while(t--){intn;cinn;edge.assign(n1,{});dp.assign(n1,0);for(inti1;in;i){intu,v;cinuv;edge[u].push_back(v);edge[v].push_back(u);}ans0;dfs(1,0);coutans\n;}}F. Familiar?题目链接Codeforces 2245F算法标签区间 DP、笛卡尔树思想、组合数学、单调栈、计数思路处理一个区间[l,r]设区间最小值出现在位置k。执行到k时它会把左半段最后留在单调栈中的元素全部弹出所以b[k]就等于左区间处理结束后的栈大小。最小值入栈后不会再被右半段弹出因此整个区间最终的栈大小等于右区间最终栈大小加一。定义dp[l][r][c]表示区间[l,r]满足已知限制并且最终栈大小为c的排列数g[l][r]表示不限制最终栈大小的排列数。枚举最小值位置k左边需要满足a[k]指定的栈大小右边决定最终栈大小。除最小值外还要从其余r-l个数中选择k-l个放到左边因此乘上组合数C(r-l,k-l)。当a[k]-1时左边可以取任意栈大小使用g[l][k-1]否则使用dp[l][k-1][a[k]]。计算g时右边使用g[k1][r]计算最终栈大小为c的dp时右边使用dp[k1][r][c-1]。代码令a[n1]-1所以最后答案就是g[1][n]。一次完整过程最多弹出n-1个元素因此已知弹出次数之和若不小于n可以直接输出 0。这个判断也保证了代码实际开出的dp状态总数为O(n^2)。总时间复杂度为O(n^3)空间复杂度为O(n^2)。代码#includebits/stdc.husingnamespacestd;constintmod998244353;intC[501][501];intmain(){ios::sync_with_stdio(false);cin.tie(nullptr);C[0][0]1;for(inti1;i500;i){C[i][0]C[i][i]1;for(intj1;ji;j){C[i][j](C[i-1][j-1]C[i-1][j])%mod;}}intt;cint;while(t--){intn;cinn;vectorinta(n2);intsum0;for(inti1;in;i){cina[i];summax(a[i],0);}if(sumn){cout0\n;continue;}a[n1]-1;vectorvectorvectorintdp(n2,vectorvectorint(n2));vectorvectorintg(n2,vectorint(n2));for(intr1;rn;r){if(a[r1]!-1){for(intl1;lr;l){dp[l][r].resize(a[r1]1);}}}for(inti1;in;i){if(a[i]0){if(a[i1]-1){g[i][i]1;}elseif(a[i1]0){dp[i][i][1]1;}}}for(intr2;rn;r){for(intlr-1;l1;l--){if(a[r1]-1){// g[l][r] sum(g[k1][r] * C[r-l][k-1])longlongcur0;for(intkl;kr;k){intleft,right;if(k!la[k]-1)leftg[l][k-1];elseif(k!la[k]!-1)leftdp[l][k-1][a[k]];elseif(kl)lefta[k]0;if(k!r)rightg[k1][r];elseif(kr)right1;cur1LL*C[r-l][k-l]*left%mod*right%mod;}g[l][r]cur%mod;}else{// have a[r 1]// dp[l][r][c] sum(dp[l][k-1][a[k]] * dp[k1][r][c-1] * C[r-l][k-l])for(intc1;ca[r1];c){longlongcur0;for(intkl;kr;k){intleft,right;if(k!la[k]-1)leftg[l][k-1];elseif(k!la[k]!-1)leftdp[l][k-1][a[k]];elseif(kl)lefta[k]0;if(k!r)rightdp[k1][r][c-1];elseif(kr)right(c1);cur1LL*C[r-l][k-l]*left%mod*right%mod;}dp[l][r][c]cur%mod;}}}}coutg[1][n]\n;}}