如何評價ZJOI2017 Day2？
瀉藥（是不是把我當驗題人了）
讀完題之後以期中為由拒掉了驗題的鍋，&進一步補充，我的確在開始評測後改過數據。原因是因為我發現倒著暴力可以直接通過2,3兩個點，因此我把這兩個點給重造了。
在整個過程中以及之前我手上沒有拿到任何選手的代碼，並不存在對著選手代碼卡的情況。這種事情在歷年也有發生過。
在評測結束後，我手上已經有了選手的代碼，選手也已經拿到了分數。原則上出題人在這種情況下是不能修改數據的。你可以認為這個規則就是為了選手的亂搞考慮。
關於數據，我不知道為什麼趙國治老師那邊沒有把數據公開。數據沒造好是事實，我這兒自然不會主動公開一些我覺得挺丟臉的數據..私下裡別人來找我要數據我基本都已經給出去了，如果你自己想要的話自己QQ上來找我要啊？
-------------------------------------------------------------------------------
真的.. 我手上還有五六個大作業沒做史綱論文沒寫，大好的假期我跑過來回應這種傻逼跳腳的匿名噴..真的挺沒意思的..
T3 的數據比較弱是事實，但是也沒有你們想像中的那麼弱..我這兒把我的gen給放出來..
數據分了四部分進行構造，這就是為什麼構造部分的 #include&
#include&
#include&
#include&
#include&
#include&
#include&
using namespace std;
int getrand(){
return (rand()&<&<8)+rand();
}
struct atom{
int pd,l,r,w;
void print(){
// pd=2;
if (pd==1) printf("%d %d %d %d
",pd,l,r,w);
else printf("%d %d %d
",pd,l,r);
}
};
vector&q;
int n=20000,m=10000,x[210000],pre;
void easyrand(){
while (q.size()&
q.push_back((atom){k1,l,r,w});
}
}
int y[1100000];
void killhash(int n,int m){
n=n-pre; if (n==0) return;
int len=1; y[1]=0;
while (len&<=n/2){
for (int i=1;i&<=len;i++) y[len+i]=y[i]^1;
len=len*2;
}
for (int i=1;i&<=n/2;i++) y[i+n/2]=y[i],y[i]=y[i-1]+1-y[i]*2;
for (int i=1;i&<=64;i++) y[n-i+1]=0;
for (int i=1;i&<=n;i++) x[i+pre]=y[i];
for (int i=1;i&<=m;i++){
int k1=getrand()%2+1,l=getrand()%n+1,r=getrand()%n+1,w=1-(getrand()%2)*2;
k1=2;
if (l&>r) swap(l,r);
q.push_back((atom){k1,l+pre,r+pre,w});
}
pre+=n;
}
void add1(int n,int m){
int len=1,now=1; y[1]=1;
while (len&<=n){
now++; y[len+1]=now;
for (int i=1;i&<=len;i++) y[len+1+i]=y[i];
len=len*2+1;
}
for (int i=1;i&<=n;i++) x[i+pre]=y[i];
for (int i=1;i&<=m;i++){
int k1=getrand()%2+1,l=getrand()%n+1,r=getrand()%n+1,w=1-(getrand()%2)*2;
if (i&<=m/2) k1=2;
if (l&>r) swap(l,r);
q.push_back((atom){k1,l+pre,r+pre,w});
}
pre+=n;
}
void add2(int n,int m,int K){
for (int i=1;i&<=n;i++) y[i]=0;
for (int i=1;i&<=K;i++) y[getrand()%n+1]=getrand()%K+1;
y[n]=1;
for (int i=1;i&<=n;i++) x[i+pre]=y[i];
for (int i=1;i&<=m;i++){
int k1=getrand()%2+1,l=getrand()%n+1,r=getrand()%n+1,w=1-(getrand()%2)*2;
if (i&<=m/2) k1=2,r=n; else if (i&<=m*3/4) k1=2;
if (l&>r) swap(l,r);
q.push_back((atom){k1,l+pre,r+pre,w});
}
pre+=n;
}
void add3(int n,int m){
for (int i=1;i&<=n;i++) y[i]=getrand()%2+1;
for (int i=1;i&<=n;i++) x[i+pre]=y[i];
for (int i=1;i&<=m;i++){
int k1=getrand()%2+1,l=getrand()%n+1,r=getrand()%n+1,w=getrand()%20-10;
if (i&<=m/2) w=1-(getrand()%2)*2;
if (l&>r) swap(l,r);
q.push_back((atom){k1,l+pre,r+pre,w});
}
pre+=n;
}
int main(){
// freopen("string3.in","w",stdout);
srand(time(0));
printf("%d %d
",n,m);
add1(60000,8000);
add2(60000,8000,4);
add3(40000,6000);
killhash(n,4000);
cerr&<& 會比隨機數據小。
- add1() 部分，這一部分構造了形如
的串，這樣的串從標算的角度來說是最優的，因為它有
個好的後綴。
- add2() 部分，這一部分是在全 1 串的基礎上，隨機放入了幾個大於 1 的數字，並把最後一個數字放大。這樣的話三方暴力無論是正著匹配還是倒著匹配都無法通過。你在回答中「任何兩個後綴的 lcp 是 O(1) 級別的」說法凈 tmd 在扯淡。
- add3() 部分，這一部分主要進行了一些隨機串和隨機詢問..因為這兩部分構造的性質太明顯，很難保證沒有什麼 corner case 沒有覆蓋到，所以一般都是要加上隨機的數據的。
- kill hash() 部分，卡了unsigned long long的hash。
- easyrand()，把剩下的操作用隨機修改填滿，和3中的考慮類似。
針對性的回應，這幾天很多人和我講 這樣的串就能卡掉他們的暴力..第一，從標算的角度來說，這個串是很 tmd 垃圾的，他的好的後綴就只有最後的 0 和 010，前面那麼長的東西屁用沒有。第二，出題人的確沒有考慮到你們把最小的字元給縮起來做。從這兩點來說，我沒有任何理由在我的數據里插入這樣的串。（到時候我寫一個把相鄰K個壓起來的暴力，還不是照樣水過去）
鑒於現在有些在知乎上指點江山的鍵盤俠出題經驗幾乎為 0。在正經的 OI 的比賽中原則上是要盡量避免捆綁測試的，因此我所有卡暴力的工作必須在單組數據內進行。因此唯一的方法是把這 20w 的長度和 3w 的詢問切開變成小塊，每一塊針對性的卡一些暴力。我從出題人的角度來說，我肯定是從標算的角度入手卡暴力，你們那些亂七八糟的有一萬種寫法的奇怪的三方暴力，有一些遺漏我也只能說很遺憾。
關於時限，為什麼時限放 3s，因為在標算的程序為了卡暴力是進行了徹底的常數優化的，哈希部分用單哈希代替了雙哈希，因此標算只要跑 0.6s 左右。tm 換成以前的我直接時限 1s 了。後來相信發現考慮到是大家的省選萬一有人努力寫了標算被我卡常數到絕望也很難受（清華集訓考場上當時妹茲茲就是這樣），我估算了一下你寫個雙哈希要慢一倍，分塊部分的常數寫的比我差一點又要慢一倍..於是我良心發現放了 3s。
早知道就放個 1s 拿來那麼多破事..對你們這群人太 tmd 仁慈了..以後出題學一學 wys 標程時間上取整為時限，管你們這幫選手的死活。
本來數據造弱心裡挺難受的..結果看到這一條消息真的是有點離奇憤怒了..md 第一見到亂搞搞不過別人罵出題人故意造弱數據..陰謀論也要有點限度。你自己看一下榜..絕大部分的人的暴力還是被卡到只有 30 分的。
題目是我出，數據是我造，出題費拿到手你們的比賽體驗怎麼樣和我 tmd 一點關係都沒有。卡掉暴力不卡常數不卡空間給大樣例這些都是我出題人自己 tmd 為了你們比的舒服一點成績好一點自覺給你們做的。亂搞就是 OI 比賽的一部分，這不是你 OI 生涯的第一次也不會是你 OI 生涯的最後一次（如果已經退役了當我沒說），不服就滾回去文化課，別學別人玩這傻逼比賽。
針對性的回應，一些具體的數據：
左列是所有詢問的長度和，右列是把初始串的height數組累加後得到的和。
我不知道你這樣的說法是怎麼來的，感覺你給出的數據就 tmd 是在扯淡..
不要以為匿名了就可以顛倒黑白血口噴人..
給你兩條路..要麼把評論給刪了，要麼取匿了給我道歉。
-------------------------------------------------------------------------------------
簡單的QA
Q：這場不是亂搞題選做嗎？
A：T1 有理有據的動態規劃，T2 簡單數據結構，T3 鏼爸爸牛逼的字元串。上一個噴這場比賽是亂搞題的 whx 墳頭草已經三丈高了。無腦噴之前先動動腦子。
Q：這個 T3 怎麼被亂搞水過去了？
A：懷念那段 ur 比賽時後台卡人的日子。你們要相信出題人已經很努力的構造數據了..（突然理解了CTSC2015 day1 出分時鐘皓曦的感受）
Q：你不是說 Day2 是 CTSC 難度的嗎，怎麼分比 Day1 看起來要高。
A：出門左轉 CTSC2015 day1.
行吧行吧我的鍋啊..
我去試試..一躍解千愁啊
我可能用生命證實了..鏼爸爸那套字元串理論..不能出在 OI 比賽里啊..
「即使人生再艱難也要相信」
「出題人是愛你們的」
人在做 天在看 杭二中 坦蕩蕩
我想起了吉老師他自己的話
&> 像戲台上的將軍身上插滿了旗
場外選手祝ZJOI Day2 辦的順利
UPD
………………………………2333333333333333333333333
幸好早生一年
還好自己出題出得早，要是noi2014 d1p2的數據放到現在命都沒了...
-----------------------------------------------------------------------------------------
補充一下。。那題驗題的時候@lyp 寫了一個複雜度關於樹高的半暴力過了，於是我就改了改數據把這個做法卡了，但忘了改了的數據太弱導致錯誤演算法也能通過_(:зゝ∠)_
利益相關：A隊
T2主席樹搗來搗去不小心就A掉了...Day1和Day2的T2我都A掉了...好怕啊
說到這大家都知道我是誰了吧...
一定是因為我沒帶雨傘。。。
感覺這場題出的很好啊。。。看得出來，出題人肯定心疼選手所以削了很多難度，不然T2怎麼會這麼簡單？感覺考掛的人應該反思自己，而不是吐槽題目是亂搞。
最後一天zzx講課的時候說了句「你們明天要瞎幾把搞搞搞不好就A掉了」
考前我日常敲的板子一個都沒用到，不開心
發題了之後感覺好像是三個不可做題啊...
一臉懵逼
發現T1出題人給了大樣例
就來瞎幾把找規律吧QAQ
然後1個小時後把T1的k=2的式子猜出來了，然後瞎幾把（閉眼）證明了下感覺有道理
式子大概是這樣子的
2*(2^n-1)+sigma([roll[i]]*(-1)^(sumroll[i-1])*(2^(n+2-i)-3))
然後試著搞搞k=3和4，感覺dp想不清楚，就棄療了
這個時候去上了個廁所，決定先寫個T2暴力然後去剛T3
T2的20分暴力好好寫的樣子，還有個20分是個點分，點分的先沒寫
然後看T3
這個n=2w,q=1w好謎啊，莫非是nq
然後直接卡死在這裡了...(mdzz這個最小表示這麼智障的東西我怎麼會想不到啊好鹹魚啊)
煩死了先寫個暴力在說
寫完跑大樣例5s
woc感覺搞搞事情以後能過隨機的6,7號點啊，搞起來
大樣例2.6s，然後自己造了點隨機數據都是2.6~2.8s
這個時候還有一個多小時，目前估分40+20+30=90
然後就慫了，有優勢心理了嘛就開始求穩，前前後後打了幾個暴力去拍，查出了一個T1的重要的錯誤然後就打出gg了QWQ
---------------------我是分割線----------------------------------
考完問本校選手好像都A了T2啊，好像T2是個大sb題啊，我好垃圾啊》。。。。
回到學校發現我標準分了（黑人問號.jpg）,一臉懵逼，這個T3 n^2q居然tmd過了。。。。
2333333333333333333333
---------------------我是分割線----------------------------------
我就是既得利益者，來咬我啊，上面和下面的連取匿都不敢的懦夫！
T3暴力打掛差10分進A，心態崩了
我曾經以為我鹹魚還是可能翻身的，後來發現鹹魚就是鹹魚。。單論題目。。T1T3都還是挺niubi的吧。。
場外選手表示T2不給 的部分分真的好嗎……
裸暴力和 都是10分，這樣的區分度真的好嗎……
為什麼副試場的代碼不測？
杭二：我憑本事轉的學，卡我三分之一算我輸
推薦閱讀：
※如何評價 Office 2016 for Mac Preview （首發測試版）？
※如何評價華工路由器群的存在？
※如何看待英國第二艘伊利莎白女王級航母「威爾士親王號」下水？
※如何評價弘一法師「遁入空門而拋妻棄子」的行為？
※如何看待 Windows 8 PDF 閱讀器被停用？