2021-team06-C211022

从 Trac 迁移的文章

这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。

原文章内容如下：

[/wiki/2021-team6 返回]

== Ranklist ==
[[Image(211022-standing.png,800px)]]

== submission ==
[[Image(211022-submission2.png,800px)]]
[[Image(211022-submission1.png,800px)]]


== 概述 ==

solved: 9/11  dirt: 

rank: 



==  ==

== 总结 ==


lxy睡过头+电脑出锅导致的whn&yja双打场
题目难度总体比较简单，除了I题外失误也不大。

== 题解 ==

A: 签到

B: 二分

C: 待yja

D：待lxy

E: 待补

F：把只有1，2，3个的字母按照传统nim游戏的规则异或起来并成一块石头，然后搜索即可。

G：显然这题的重点在于空间限制，因此需要考虑压缩状态至只考虑至少有一个沙漏为空或满的状态，同时重复利用dp数组记录。考虑全局变量维护四个沙漏当前的沙子数，一个状态由四个沙漏中的三个沙漏的沙子数，剩下一个沙漏的编号与满/空，当前时间组成，总状态数为21^3^*4*2*1440，用bitset压好。dfs(u,x,T)记录当前dfs到第u层,空或满沙漏为x,经过时间T的情况，全局变量维护flip[M],a[4]表示沙漏是否在某个时刻翻转过与沙漏沙子数，转移时先考虑翻转某个沙漏的转移并dfs(u+1,x,T)下去，再最后考虑等待当前最小沙漏漏完的转移dfs(u+1,id,T+a[id])，可以发现这样重复利用转移是没有互相影响的。

H：每次取🖊都会改变奇偶，因此直接判断奇偶即可。

I：大方向肯定是要尽可能匀称的二分，紧接着注意到除了开始要将正方形沿任意对角线切开之外，由于等腰直角三角形可以沿中线切开切成两个小等腰直角形，因此实现得当可以做到每次询问都是一个等腰直角三角形。但在格点当中，我们可能会碰到斜边平行坐标轴或与坐标轴成45度，对半分可以等大小分开或一边大一边边长小1几种情况，我们实现时是边长*2实现的。

J: 考虑构造：因为(x+1)^3^+(x-1)^3^-2x^3^ = (1+1-2)x^3^+(3-3)x^2^+6x, 又由于1，8，27，-1，-8，刚好对应模6的五个余数，所以大的情况可以直接将数除以6然后对应构造，小数情况随意特判即可。 

K: 每个数要么被一直向左换要么被一直向右换到属于它的位置，所以用树状数组维护每个数在左侧和在右侧产生的逆序对数l[i],r[i]，对每个位置i取li,ri的较小者即可，因为实际情况下，只要按照一定的顺序进行交换，一定可以做到每个一直向左或右换的操作路上都是有序数列。

[/wiki/2021-team6 返回]

Ranklist

submission

概述

solved: 9/11 dirt:

rank:

总结

lxy睡过头+电脑出锅导致的whn&yja双打场

题目难度总体比较简单，除了I题外失误也不大。

题解

A: 签到

B: 二分

C: 待yja

D：待lxy

E: 待补

F：把只有1，2，3个的字母按照传统nim游戏的规则异或起来并成一块石头，然后搜索即可。

G：显然这题的重点在于空间限制，因此需要考虑压缩状态至只考虑至少有一个沙漏为空或满的状态，同时重复利用dp数组记录。考虑全局变量维护四个沙漏当前的沙子数，一个状态由四个沙漏中的三个沙漏的沙子数，剩下一个沙漏的编号与满/空，当前时间组成，总状态数为213*4*2*1440，用bitset压好。dfs(u,x,T)记录当前dfs到第u层,空或满沙漏为x,经过时间T的情况，全局变量维护flip[M],a[4]表示沙漏是否在某个时刻翻转过与沙漏沙子数，转移时先考虑翻转某个沙漏的转移并dfs(u+1,x,T)下去，再最后考虑等待当前最小沙漏漏完的转移dfs(u+1,id,T+a[id])，可以发现这样重复利用转移是没有互相影响的。

H：每次取🖊都会改变奇偶，因此直接判断奇偶即可。

I：大方向肯定是要尽可能匀称的二分，紧接着注意到除了开始要将正方形沿任意对角线切开之外，由于等腰直角三角形可以沿中线切开切成两个小等腰直角形，因此实现得当可以做到每次询问都是一个等腰直角三角形。但在格点当中，我们可能会碰到斜边平行坐标轴或与坐标轴成45度，对半分可以等大小分开或一边大一边边长小1几种情况，我们实现时是边长*2实现的。

J: 考虑构造：因为(x+1)3+(x-1)3-2x3 = (1+1-2)x3+(3-3)x2+6x, 又由于1，8，27，-1，-8，刚好对应模6的五个余数，所以大的情况可以直接将数除以6然后对应构造，小数情况随意特判即可。

K: 每个数要么被一直向左换要么被一直向右换到属于它的位置，所以用树状数组维护每个数在左侧和在右侧产生的逆序对数l[i],r[i]，对每个位置i取li,ri的较小者即可，因为实际情况下，只要按照一定的顺序进行交换，一定可以做到每个一直向左或右换的操作路上都是有序数列。

附加文件