2021-team06-C210928

从 Trac 迁移的文章

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

原文章内容如下：

[/wiki/2021-team6 返回]

== Ranklist ==

[[Image(210928-standing.png,800px)]]

== submission ==

[[Image(210928-submission2.png,800px)]]
[[Image(210928-submission.png,800px)]]


== 概述 ==

solved: 6/13  dirt: 33.3%

rank: 69



==  ==

== 总结 ==

whn:
队伍状态较差
大家补了一天


== 题解 ==

A: 对位置i，贪心地取之前一个未被+1的位置j使sump[i]-sum[j-1]最大（用优先队列维护），对位置j进行+1的操作，即物理上把j~i的深度都+1，

B: 发现我们能做的操作正好是使得逆序对数-1或者-2，于是统计一下逆序对数看是不是3的倍数即可。

C: 构造，whn有空来补

D：分别考虑同一种颜色的三个盘子的位置情况，发现只有三个盘子都处于第二层或者底层的部分情况下，我们无法在6步之内将他们恢复；但考虑到对于一个没有全挪完的局面一定会有一个需挪的盘子在顶端（任意一端），于是每次都挪那个，就可以达到题目要求了。（数据很强，发现问题之后第一反应是随机复原顺序于是TLE43..不过有这么个性质才有构造的味道orz)

E：一个divisible by 3的区间，不可被3整除的数的个数必定<=1. 在此基础上随便dp一下即可。

F：待lxy写题解

G：待补

H：神题，并不是传统的按位考虑+乱搞，重点在于感性考虑And会把整个区间1的数量“越and越少”，Or会把区间1的数量“越Or越多 ”，因此一个区间要符合要求，一定是把1多的那部分And，少的那部分Or.因此主席树维护二进制表达1个数（0-30）意义下，每个区间里的数的区间and后缀和or前缀的值，（空区间and可以直接置2147483647）询问的时候，一个区间合法当且仅当对于某个i,0-i的or等于i+1-30的And，或者0-i的or=i-30的and且1个数为i的数多于1.

I：考虑合法地排列一定是一段递减的数结尾跟着2（否则不可能余数<2)，一段东西结尾跟着1，不妨将其分作两段，dp[i][j][k=0/1]表示填到第i个数（可以不开数组），非i+1的那边是是第k段且填的是j的方案数，转移枚举上一个数除以i可能的商（ln)和余数(0-2)转移即可。

J: 待补？

K: 有空来补

L: 待yja写题解

M: 签到，拓扑弄一下即可

[/wiki/2021-team6 返回]

Ranklist

submission

概述

solved: 6/13 dirt: 33.3%

rank: 69

总结

whn:

队伍状态较差

大家补了一天

题解

A: 对位置i，贪心地取之前一个未被+1的位置j使sump[i]-sum[j-1]最大（用优先队列维护），对位置j进行+1的操作，即物理上把j~i的深度都+1，

B: 发现我们能做的操作正好是使得逆序对数-1或者-2，于是统计一下逆序对数看是不是3的倍数即可。

C: 构造，whn有空来补

D：分别考虑同一种颜色的三个盘子的位置情况，发现只有三个盘子都处于第二层或者底层的部分情况下，我们无法在6步之内将他们恢复；但考虑到对于一个没有全挪完的局面一定会有一个需挪的盘子在顶端（任意一端），于是每次都挪那个，就可以达到题目要求了。（数据很强，发现问题之后第一反应是随机复原顺序于是TLE43..不过有这么个性质才有构造的味道orz)

E：一个divisible by 3的区间，不可被3整除的数的个数必定<=1. 在此基础上随便dp一下即可。

F：待lxy写题解

G：待补

H：神题，并不是传统的按位考虑+乱搞，重点在于感性考虑And会把整个区间1的数量“越and越少”，Or会把区间1的数量“越Or越多 ”，因此一个区间要符合要求，一定是把1多的那部分And，少的那部分Or.因此主席树维护二进制表达1个数（0-30）意义下，每个区间里的数的区间and后缀和or前缀的值，（空区间and可以直接置2147483647）询问的时候，一个区间合法当且仅当对于某个i,0-i的or等于i+1-30的And，或者0-i的or=i-30的and且1个数为i的数多于1.

I：考虑合法地排列一定是一段递减的数结尾跟着2（否则不可能余数<2)，一段东西结尾跟着1，不妨将其分作两段，dp[i][j][k=0/1]表示填到第i个数（可以不开数组），非i+1的那边是是第k段且填的是j的方案数，转移枚举上一个数除以i可能的商（ln)和余数(0-2)转移即可。

J: 待补？

K: 有空来补

L: 待yja写题解

M: 签到，拓扑弄一下即可

附加文件