2017-Sp84-team2

从 Trac 迁移的文章

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

原文章内容如下：

 [[Image(1.png,500px)]]
== 流水账 ==
开场各自看题，cjb读了C，很快就秒了，便让yzc上机敲NTT板子。之后发现有人过B，sub读了之后丢给yzc，yzc上机'''B1y28'''。sub之前读了H，实在太sb，cjb上机敲了lct板子，yzc随便写了几行就交了，结果忘记fflush炸了一发，'''H2y43'''。cjb此前丢了几何题F给sub，sub酝酿了一会儿，上机写F，'''F1y60'''。sub继续上机写C，NTT获得tle，cjb敲了FFT，结果MLE一发，'''C3y118'''。sub去搞A和E，cjb和yzc搞G，理论了一个分块，yzc挣扎地上机写，cjb之后想到了优美的性质，给yzc讲了一个清真的做法，获得了sub的认可，yzc上机wa了一发后cjb很快艹出了问题，修改后'''G2y188'''。之后sub上机写A的迭代，然后疯狂tle，疯狂调参，'''reku路过给了个分块矩乘的建议，没有人鸟他'''，最后把语言从c++14改成了c++，居然过了，还跑得贼快，'''A10y230'''晕。最后yzc上机写E的暴力，sub上机写E，调了一段时间，'''E1y283'''。最后三个人把D题意读了，理论了一下比赛就结束了。
== 总结 ==
=== chenjb ===
惊了，这个A的常数????? C++14和C++??????? 下一场训final了，有点小激动。
=== oipotato ===
楼上训final失败
=== subconscious  ===
== 题解 ==
 * D:
  * 题意：交互，N维空间内N个线性无关的向量Ai和数组C[N][M]，有C每行单调上升且有一位置为零，每次查询P[N](1<=P[i]<=M)，返回向量sigmaC[i][P[i]]*Ai,  要求120次内得到零向量。 N,M<=100.
  * 题解：用N+1次得到Ai的单位向量，用高斯消元求得逆矩阵，随后每次查询时就能O(N^2^)得到每个C[i]的sgn，一同二分即可。
 * [https://wiki-wood-cube.icpc-camp.org/Petrozavodsk%20Winter-2015%20Nizhny%20Novgorod%20SU WoodCube]
 * [https://wiki.icpc-camp.org/twsf/2015-2016%20Petrozavodsk%20Winter%20Training%20Camp,%20Nizhny%20Novgorod%20SU%20Contest The Way So Far]
 * [https://wiki.icpc-camp.org/dreadnought/Nizhny%20Novgorod%20SU%20Contest Dreadnought]
== 补题 ==

流水账

开场各自看题，cjb读了C，很快就秒了，便让yzc上机敲NTT板子。之后发现有人过B，sub读了之后丢给yzc，yzc上机B1y28。sub之前读了H，实在太sb，cjb上机敲了lct板子，yzc随便写了几行就交了，结果忘记fflush炸了一发，H2y43。cjb此前丢了几何题F给sub，sub酝酿了一会儿，上机写F，F1y60。sub继续上机写C，NTT获得tle，cjb敲了FFT，结果MLE一发，C3y118。sub去搞A和E，cjb和yzc搞G，理论了一个分块，yzc挣扎地上机写，cjb之后想到了优美的性质，给yzc讲了一个清真的做法，获得了sub的认可，yzc上机wa了一发后cjb很快艹出了问题，修改后G2y188。之后sub上机写A的迭代，然后疯狂tle，疯狂调参，reku路过给了个分块矩乘的建议，没有人鸟他，最后把语言从c++14改成了c++，居然过了，还跑得贼快，A10y230晕。最后yzc上机写E的暴力，sub上机写E，调了一段时间，E1y283。最后三个人把D题意读了，理论了一下比赛就结束了。

总结

chenjb

惊了，这个A的常数????? C++14和C++??????? 下一场训final了，有点小激动。

oipotato

楼上训final失败

subconscious

题解

  • D:
    • 题意：交互，N维空间内N个线性无关的向量Ai和数组C[N][M]，有C每行单调上升且有一位置为零，每次查询P[N](1<=P[i]<=M)，返回向量sigmaC[i][P[i]]*Ai, 要求120次内得到零向量。 N,M<=100.
    • 题解：用N+1次得到Ai的单位向量，用高斯消元求得逆矩阵，随后每次查询时就能O(N2)得到每个C[i]的sgn，一同二分即可。
  • WoodCube
  • The Way So Far
  • Dreadnought

补题

附加文件