2017-C05-team7
从 Trac 迁移的文章
这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。
原文章内容如下：
[[Image(Day5.png)]]
== zhhhplus ==
流水账：今天开场我没有按从后往前的顺序来看题，而是开始了随机看题，由于F题的标题看起来特别亲民，于是就看了F题。然后wyz就和我讲了E题的题意，听到了之后很快就得到了一个算法，跟wyz一讲，就让他上去写了，也很平稳地A掉了（'''E1y27'''），和wyz讲了F题的二分，觉得很容易写，估计能非常快地解决掉，但是比较奇怪的是后来wyz这题的代码过了百行，不清楚为什么。（听了A题之后提出了一个错误的DP方案，不提）然后听了H题，跟队友说了一下格雷码的规律，队友表示没有头绪，然后突然想起来我有一个生成格雷码的板子，掏出来一看，知道了这个公式：gary=(ith)＾(ith>>1)，觉得很好推，chy也这么觉得，打算让chy上去写这题，过了一分钟，我觉得可以用位运算来更简单地做（就是不断和右移一位的gray码异或（即类似裂项的方法？）），再过了一段时间，wyz的F题写好但是错了，让他打印出来然后让chy上机写一下二进制读写，随后让chy把位置让给我来（后来想的写起来比原来的快，所以可以节省时间），上去缓慢地敲了5行代码，跟chy说：好了。随后功成身退，完成了本场比赛的所有代码任务。chy测了两个数据之后表示这个做法是不是对的（我表示要处理两个点之间的点，只要减一就行），然后改了之后，没有生成就测了一发同数据，返回0，chy觉得没有问题，我觉得隐隐有些不妥，来不及制止，chy就已经交了。喜获WA，随后我和chy马上改了一下这里，交了上去，然而还是WA了，觉得有可能爆long long，改了一些点，但是并没有过自己出的大数据，最后发现是chy的读入写挂了。我表示这锅我不背。交了之后平稳AC（'''H3y80'''），然后wyz上场继续写F题，调了一会儿之后也过了（'''F1y85'''），大家看榜发现C题是个签到题，我跟着听了一下题意，觉得没什么花头，还是看别的题去，他们就在那边调C题了，其后看榜觉得I题可以做一下，A题也许可以做一下，就开始看看I看看A，但是迫于英语差，没怎么看懂I，A题倒是想了个状态函数，结果是和题解差不太多（但是觉得细节可能很多，自己也没很想清楚，到最后也没让队友上）。C题在莫名的WA了两发之后AC了（'''C3y116'''），没有参与这个过程的我表示没有wyz给我读题脑子有点混乱呢。大家对着I题沉默了很久，我想了一个BFS分层然后DP的做法，觉得不太行，队友们开始朝着网络流的方面想了，我看了榜觉得不太对，大概是比较简单的做法，回头闷想了一会儿，问了队友能不能O(n)做每个点到最近的AB类点距离，和wyz确定了可行之后，讲了一下各点BFS出来的做法（此前似乎有类似的方案被提出来，但是莫名消失了，也许是不正确的姿势？），就让chy上去写了，和wyz一起看别的题目去了。随后又是一阵沉默，大家对着ABJ题发呆，大概还在思考做法和做哪题的时候chy把I题过掉了（'''I1y164'''），我在一旁想A题，wyz和chy讨论J题，在讲用贪心过，听到贪心我觉得不太行啊，凑上去听了J题题意，搞清楚之后也没什么头绪，届时刚好听到别的队不知道在做什么题讲到了网络流，就想了想用网络流做这题，然后十几秒建了个我觉得非常朴素的模型，和队友讲了，在理解了一会儿之后，chy觉得可以（我对这种建模方法表示恐惧（尽管就是标答）），我们让wyz上去先敲网络流的板子，在我详细地给chy讲解这个模型的时候，wyz飞快地敲掉了板子，然后我再给wyz讲解了一遍模型，然后做起了撒手掌柜，心平气和地坐在一旁，以及去别的组溜达了一圈，顺便想想A题（越想越觉得难写）。在十几分钟的代码（可能更久）之后，帮助一起debug了一会儿，平稳交了J题，一发意料之中的AC（'''J1y251'''），队友们似乎也没什么要开新题的样子，我觉得A题在剩下50分钟的时间里应该写不完的样子，就决定做一点队长应该做的事情，比如帮忙买饮料，于是默默去了东教学楼带了雪碧回来。然后就在欢声笑语吃吃喝喝打打扫雷的状态下度过了整场比赛。
总结：这场比赛大家发挥还不错，H题WA的两发都是不太应该的，以及发现了自己的英语阅读能力亟需提高，网络流板子决定全权交给wyz来了，优势很大。最后结束的时候不再继续做题可能态度不太端正，仅此一次。以及中间有一段时间机器是没题敲的状态，怪我算法能力不够强，没有保证队伍每时每刻有代码在写，以及徘徊不知道开哪题的情况也应该尽量避免。
== hanyi0923 ==
今天就结果来说还算可以接受，大部分我们有能力写的题都写出来了，然而还是有很大可以改进空间，第一是刚开始的2小时我的心态没有调整好，导致了两个WA，而且看题丶解题时很大程度耽误了整体的进度，在解出第6题前一直落后。第二是应该更加有效运用最后1.5-1小时的时间，今天的A, B其实都是可以做的题目，其中B题其实在赛中已经想到正确算法，只是自己与队友都觉得来不及就没写。另外需要再加强自身的实力，让未来有这种情况是至少让自己与队友都认爲时间足够写完。
== zju_wyz ==
感觉今天发挥还是不错的，网络流的板子一如既往地稳。需要检讨的地方也有一些，比如 C 题 WA 掉的两发，第一发是没有看清题意，忽略了 x < 0 的情况，第二发则是用了愚蠢的 x / abs(x) 来求符号，出现了除零错误。现在回想起来，其实只要在二分的时候把 mi = 0 改成 mi = 0x80000000 就能解决这个问题。中期由于 F 题看错，没有理解 next to 的含义，误以为分到两排的要上下 next to 导致卡题，不过还好后来发现了，F 题也没有卡很久。敲完网络流建图 1A 后，还剩 50 分钟，此时看榜，没有人解决 A 题或 B 题，于是虽然 chy 和 zhh 各自有了非常接近正解的想法，但还是误以为这两题都是不可做题，遂放弃。最后 50 分钟在颓废的氛围中度过。
== other ==
补题：B(√)
附格雷码转原码的算法：
gray = x xor (x>>1)
=> gray xor (gray>>1) xor (gray>>2) xor ... xor 0 = x xor (x>>1) xor (x>>1) xor (x>>2) xor (x>>2) xor (x>>3) xor ... xor 0 = x
因此可以得到如下算法：
``
def g_to_o(gray):
ans = gray
gay = gray >> 1
while gay > 0:
ans = ans xor gay
gay = gay >> 1
return ans
``
附 JTJL 学长的 J 题贪心做法
void solve()
{
int q, s;
scanf("%d%d%d", &n, &q, &s);
for (int i = 1; i <= s; i++)
scanf("%d", &Q[i]);
for (int i = 1; i <= q; i++)
scanf("%d", &C[i]);
//C[i] 为第 i 个队列的容量
for (int i = 1; i <= n; i++)
{
scanf("%d", &d[i]);
//d[i] 为第 i 轮的窗口容量
for (int j = 1; j <= s; j++)
{
int x;
scanf("%d", &x);
F[i][Q[j]] += x;
F[0][Q[j]] += x;
//F[0][q] 为目前已经压到第 q 个队列的数据量
//F[i][q] 为第 i 轮进入第 q 个队列的数据量
//先全部入队，再处理容量不够的问题
}
for (int j = 1; j <= q; j++)
{
if (F[0][j] > C[j])
//队列容量不够
{
//检查有没有剩余的容量可用
for (int k = 1; k < i; k++)
if (F[0][j] > C[j])
for (int l = 1; l <= k; l++)
//进行到第 k 轮时，第 j 个队列中的数据量为 Sum[ f[l][j], {l, 1, k - 1} ]
//因此只要第 k 轮 pop 时保证对所有 l < k ,f[l][j] 非负，就能保证不会 pop 空队列。
if (d[k] > 0 && F[l][j] > 0)
{
int tmp = min(min(d[k], F[l][j]), F[0][j] - C[j]);
d[k] -= tmp;
F[l][j] -= tmp;
F[0][j] -= tmp;
//由于 tmp 保证 d[k] 非负，F[l][j] 非负，因此一定是合法的。
//由于 tmp 保证 F[0][j] >= C[j]， 因此一定不会浪费 d[k]， 是最优的。
}
//这样能保证留给后面的 d 最大，且用掉的 d 的时间尽可能早。
//由于两个队列之间只可能通过 d 来相互影响，因此可以保证正确性
if (F[0][j] > C[j])
{
puts("impossible");
return;
}
}
}
}
int info = 0;
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= q; j++)
info += F[i][j];
info = max(info - d[i], 0); // 将本轮的剩余容量用完
//info 是截至第 i 轮所有仍未传送的数据量之和
}
if (info == 0) puts("possible");
else puts("impossible");
}zhhhplus
流水账：今天开场我没有按从后往前的顺序来看题，而是开始了随机看题，由于F题的标题看起来特别亲民，于是就看了F题。然后wyz就和我讲了E题的题意，听到了之后很快就得到了一个算法，跟wyz一讲，就让他上去写了，也很平稳地A掉了（E1y27），和wyz讲了F题的二分，觉得很容易写，估计能非常快地解决掉，但是比较奇怪的是后来wyz这题的代码过了百行，不清楚为什么。（听了A题之后提出了一个错误的DP方案，不提）然后听了H题，跟队友说了一下格雷码的规律，队友表示没有头绪，然后突然想起来我有一个生成格雷码的板子，掏出来一看，知道了这个公式：gary=(ith)＾(ith>>1)，觉得很好推，chy也这么觉得，打算让chy上去写这题，过了一分钟，我觉得可以用位运算来更简单地做（就是不断和右移一位的gray码异或（即类似裂项的方法？）），再过了一段时间，wyz的F题写好但是错了，让他打印出来然后让chy上机写一下二进制读写，随后让chy把位置让给我来（后来想的写起来比原来的快，所以可以节省时间），上去缓慢地敲了5行代码，跟chy说：好了。随后功成身退，完成了本场比赛的所有代码任务。chy测了两个数据之后表示这个做法是不是对的（我表示要处理两个点之间的点，只要减一就行），然后改了之后，没有生成就测了一发同数据，返回0，chy觉得没有问题，我觉得隐隐有些不妥，来不及制止，chy就已经交了。喜获WA，随后我和chy马上改了一下这里，交了上去，然而还是WA了，觉得有可能爆long long，改了一些点，但是并没有过自己出的大数据，最后发现是chy的读入写挂了。我表示这锅我不背。交了之后平稳AC（H3y80），然后wyz上场继续写F题，调了一会儿之后也过了（F1y85），大家看榜发现C题是个签到题，我跟着听了一下题意，觉得没什么花头，还是看别的题去，他们就在那边调C题了，其后看榜觉得I题可以做一下，A题也许可以做一下，就开始看看I看看A，但是迫于英语差，没怎么看懂I，A题倒是想了个状态函数，结果是和题解差不太多（但是觉得细节可能很多，自己也没很想清楚，到最后也没让队友上）。C题在莫名的WA了两发之后AC了（C3y116），没有参与这个过程的我表示没有wyz给我读题脑子有点混乱呢。大家对着I题沉默了很久，我想了一个BFS分层然后DP的做法，觉得不太行，队友们开始朝着网络流的方面想了，我看了榜觉得不太对，大概是比较简单的做法，回头闷想了一会儿，问了队友能不能O(n)做每个点到最近的AB类点距离，和wyz确定了可行之后，讲了一下各点BFS出来的做法（此前似乎有类似的方案被提出来，但是莫名消失了，也许是不正确的姿势？），就让chy上去写了，和wyz一起看别的题目去了。随后又是一阵沉默，大家对着ABJ题发呆，大概还在思考做法和做哪题的时候chy把I题过掉了（I1y164），我在一旁想A题，wyz和chy讨论J题，在讲用贪心过，听到贪心我觉得不太行啊，凑上去听了J题题意，搞清楚之后也没什么头绪，届时刚好听到别的队不知道在做什么题讲到了网络流，就想了想用网络流做这题，然后十几秒建了个我觉得非常朴素的模型，和队友讲了，在理解了一会儿之后，chy觉得可以（我对这种建模方法表示恐惧（尽管就是标答）），我们让wyz上去先敲网络流的板子，在我详细地给chy讲解这个模型的时候，wyz飞快地敲掉了板子，然后我再给wyz讲解了一遍模型，然后做起了撒手掌柜，心平气和地坐在一旁，以及去别的组溜达了一圈，顺便想想A题（越想越觉得难写）。在十几分钟的代码（可能更久）之后，帮助一起debug了一会儿，平稳交了J题，一发意料之中的AC（J1y251），队友们似乎也没什么要开新题的样子，我觉得A题在剩下50分钟的时间里应该写不完的样子，就决定做一点队长应该做的事情，比如帮忙买饮料，于是默默去了东教学楼带了雪碧回来。然后就在欢声笑语吃吃喝喝打打扫雷的状态下度过了整场比赛。
总结：这场比赛大家发挥还不错，H题WA的两发都是不太应该的，以及发现了自己的英语阅读能力亟需提高，网络流板子决定全权交给wyz来了，优势很大。最后结束的时候不再继续做题可能态度不太端正，仅此一次。以及中间有一段时间机器是没题敲的状态，怪我算法能力不够强，没有保证队伍每时每刻有代码在写，以及徘徊不知道开哪题的情况也应该尽量避免。
hanyi0923
今天就结果来说还算可以接受，大部分我们有能力写的题都写出来了，然而还是有很大可以改进空间，第一是刚开始的2小时我的心态没有调整好，导致了两个WA，而且看题丶解题时很大程度耽误了整体的进度，在解出第6题前一直落后。第二是应该更加有效运用最后1.5-1小时的时间，今天的A, B其实都是可以做的题目，其中B题其实在赛中已经想到正确算法，只是自己与队友都觉得来不及就没写。另外需要再加强自身的实力，让未来有这种情况是至少让自己与队友都认爲时间足够写完。
zju_wyz
感觉今天发挥还是不错的，网络流的板子一如既往地稳。需要检讨的地方也有一些，比如 C 题 WA 掉的两发，第一发是没有看清题意，忽略了 x < 0 的情况，第二发则是用了愚蠢的 x / abs(x) 来求符号，出现了除零错误。现在回想起来，其实只要在二分的时候把 mi = 0 改成 mi = 0x80000000 就能解决这个问题。中期由于 F 题看错，没有理解 next to 的含义，误以为分到两排的要上下 next to 导致卡题，不过还好后来发现了，F 题也没有卡很久。敲完网络流建图 1A 后，还剩 50 分钟，此时看榜，没有人解决 A 题或 B 题，于是虽然 chy 和 zhh 各自有了非常接近正解的想法，但还是误以为这两题都是不可做题，遂放弃。最后 50 分钟在颓废的氛围中度过。
other
补题：B(√)
附格雷码转原码的算法：
gray = x xor (x>>1)
=> gray xor (gray>>1) xor (gray>>2) xor ... xor 0 = x xor (x>>1) xor (x>>1) xor (x>>2) xor (x>>2) xor (x>>3) xor ... xor 0 = x
因此可以得到如下算法：
``
def g_to_o(gray):
ans = gray
gay = gray >> 1
while gay > 0:
ans = ans xor gay
gay = gay >> 1
return ans
``
附 JTJL 学长的 J 题贪心做法
void solve()
{
int q, s;
scanf("%d%d%d", &n, &q, &s);
for (int i = 1; i <= s; i++)
scanf("%d", &Q[i]);
for (int i = 1; i <= q; i++)
scanf("%d", &C[i]);
//C[i] 为第 i 个队列的容量
for (int i = 1; i <= n; i++)
{
scanf("%d", &d[i]);
//d[i] 为第 i 轮的窗口容量
for (int j = 1; j <= s; j++)
{
int x;
scanf("%d", &x);
F[i][Q[j]] += x;
F[0][Q[j]] += x;
//F[0][q] 为目前已经压到第 q 个队列的数据量
//F[i][q] 为第 i 轮进入第 q 个队列的数据量
//先全部入队，再处理容量不够的问题
}
for (int j = 1; j <= q; j++)
{
if (F[0][j] > C[j])
//队列容量不够
{
//检查有没有剩余的容量可用
for (int k = 1; k < i; k++)
if (F[0][j] > C[j])
for (int l = 1; l <= k; l++)
//进行到第 k 轮时，第 j 个队列中的数据量为 Sum[ f[l][j], {l, 1, k - 1} ]
//因此只要第 k 轮 pop 时保证对所有 l < k ,f[l][j] 非负，就能保证不会 pop 空队列。
if (d[k] > 0 && F[l][j] > 0)
{
int tmp = min(min(d[k], F[l][j]), F[0][j] - C[j]);
d[k] -= tmp;
F[l][j] -= tmp;
F[0][j] -= tmp;
//由于 tmp 保证 d[k] 非负，F[l][j] 非负，因此一定是合法的。
//由于 tmp 保证 F[0][j] >= C[j]， 因此一定不会浪费 d[k]， 是最优的。
}
//这样能保证留给后面的 d 最大，且用掉的 d 的时间尽可能早。
//由于两个队列之间只可能通过 d 来相互影响，因此可以保证正确性
if (F[0][j] > C[j])
{
puts("impossible");
return;
}
}
}
}
int info = 0;
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= q; j++)
info += F[i][j];
info = max(info - d[i], 0); // 将本轮的剩余容量用完
//info 是截至第 i 轮所有仍未传送的数据量之和
}
if (info == 0) puts("possible");
else puts("impossible");
}
附加文件
- Day5.png by zhhhplus