現在說回我吧
關注我的blog的朋友可能發現 我這里已經好久沒更新了
這還要從CTSC&APIO說起
話說那兩次比賽考得很偽 究其原因 恐怕還是學習方法的問題
在這方面JL的oier有著得天獨厚的劣勢
所以 我經常說 作為一個弱省的oier 不要怕走彎路 這一定是必經的過程
在那次回來之后 我就再也沒有寫blog 原因大概就是對自己今年Au 失去了像CTSC之前那么強的信心 甚至怕省選落選 每天就做做各省省選題 心想Ag就不錯了
后來省選又結束了 我以第二名的成績進隊 其實也是情理之中的
之后就是做做NOI 好多題都不能AC 但是要是把力所能及的點都做上 還不Au線高不少 這讓我又有了一點點幻想 但我深知基本不會有人在NOI吧力所能及的點都答上的
這兩天去參加中考 其實就是考這玩 我上高中一定是要靠OI的成績的
參加中考見到了許多同學 半年沒見到這么多同學了 還是這些同學好
在那個圈子里 沒人會認為你是神牛 沒人會認為你可能進國家隊甚至IOI Au 也沒人把你當小朋友 即使相信也不會有不斷的orz 不會吝嗇批評和鄙視甚至是雞蛋里挑骨頭
雖然少了寫前輩與眾心腸的話 但是卻顯得特別的真實
由于我們班是最BT的班 所以我的同學們也就都選擇了最BT的高中 合適JL省太不重視OI了 所以我一定要去的Au才能保證高中也和他們在一起
為了同學們 為了不辜負當年手把手教我oi的lpq、給我講了無數題的zys、在我孤獨是陪伴我的wh 以及好多好多人
就讓我再修煉28天 在NOI取得Au吧
這將是我這個blog的最后一篇blog 這次NOI之前先不寫blog了 等這次NOI之后 重新開個blog
另外看了幾個我們同學的blog發現原來blog不止是寫解題報告的 尤其是這個寫的太NB了
不Au就要離開他們了 5555555555555555555
不過即使不在一起上學 哪個學校的oi老師都會歡迎我的 想見還是能見到 而且可以經常見
]]>
CTSC 主要失敗在day1 基礎分沒有拿到 還有一個文件提交錯了 導致day2 不得不奮力AC一題 但是我的實力有限 解決一個題很有風險 結果果然掛掉了
APIO 第二題讀錯 第三題寫掛了 結果只有銅牌
總結這兩次比賽 主要暴露出的問題有
1.經常犯一些低級失誤 比如文件提交錯誤｜讀錯題
2.寫題不準
3.答題策略有問題
4.實力不足
下一步要做的是：
A:隨即調整 模擬退火
B：DP 線段樹
C：省選 冬令營 CTSC
D:NOI 02-08
每天3題 首先5h 然后 請教｜看解體報告 AC掉
結束了
]]>
不敢奢望能取得什么太好的成績 但總不能讓我自己掏比賽費可車票(我們學校規定 Ag或以上成績可以報銷)
下面將寫下我的比賽成績由于事情還沒有發生 所以現在還不能寫 期望回來的時候不要讓我不好意思寫
]]>
他還鼓勵我今年進集訓隊 叫我自信
現在足以改變一切的3個月終于到來了
希望借何林神牛的吉言 用3個月 原了我的Au夢
]]>
但是由于我已經有至少6周沒正經寫程序了 不得不承認手生的 不過我堅信會找回手感的
介于此 從明天開始以考試的方式做CTSC WC
另外 在這里求CTSC 06 07 08? WC 05
聽說CTSC今年是E文 那我是不是可以不去了
]]>
后綴數組果然是一個很強大的東西 有關字符串的問題 只要學好自動機和后綴數組基本都能解決了
與其說是后綴數組強大 不如說height數組強大 后綴數組的作用也就是方便求解height數組
使用height數組 大致有如下你個常用方法
1、分組:將height值大于等于k的分置一組 使得同組內最長公共前綴>=k
2、二分:根據具體情況 一般都是二分答案
3、連接：將所有涉及到的字符串連在一起處理
還有一個神奇的性質:當循環節長度確定時 保證覆蓋是s[0],s[l],s[l*2]～～中的某連續兩個
]]>
#include<iostream>
#define?Rank(x)?rank[(x)<?(n+1)]
using?namespace?std;
char?a[100000],c[5000],b[5000],d[100000];
int?sa[5001],height[5001],rank[5001],n,sum[5001],h[5001],_sa[5001],_rank[5001],m,ans[20][5001],tr[5001],tl[5001],maxk,maxi,lft[100001],rght[100001],leftt[100001],rightt[100001];
struct?node
{
????int?th;
????char?s;
}r[10000];
int?cmps(const?void?*a,const?void?*b)
{
????return?(*(node?*)a).s-(*(node?*)b).s;
}
int?cmpth(const?void?*a,const?void?*b)
{
????return?(*(node?*)a).th-(*(node?*)b).th;
}
void?getsa()
{
????qsort(r+1,n,sizeof(node),cmps);
????int?p=0;
????for(int?i=1;i<=n;++i)
????????if(r[i].s!=r[i-1].s)
????????{
????????????rank[r[i].th]=++p;
????????????sa[i]=r[i].th;
????????}
????????else
????????{
????????????rank[r[i].th]=p;
????????????sa[i]=r[i].th;
????????}
?????qsort(r+1,n,sizeof(node),cmpth);
?????for(int?l=1;p<n;l<<=1)
?????{
?????????memset(sum,0,sizeof(sum));
?????????memset(h,0,sizeof(h));
?????????for(int?i=1;i<=n;++i)
?????????????++sum[rank[i]+1];
????????for(int?i=1;i<=p;++i)
????????????sum[i]+=sum[i-1];????
?????????for(int?i=n-l+1;i<=n;++i)
????????????_sa[sum[rank[i]]+(++h[rank[i]])]=i;
????????for(int?i=1;i<=n;++i)
?????????????if(sa[i]>l)
?????????????????_sa[sum[rank[sa[i]-l]]+(++h[rank[sa[i]-l]])]=sa[i]-l;
????????memcpy(sa,_sa,sizeof(_sa));
????????p=0;
????????for(int?i=1;i<=n;++i)
????????????_rank[sa[i]]=((rank[sa[i]]==rank[sa[i-1]])&&(Rank(sa[i]+l)==Rank(sa[i-1]+l)))?p:++p;
????????memcpy(rank,_rank,sizeof(_rank));????????????
?????}
}
void?getans()
{
????for(int?i=1;i<=n;++i)
????????ans[0][i]=height[i];
????for(int?i=1;1<<i<=n;++i)
????????for(int?j=1;j+i-1<=n;++j)
????????????ans[i][j]=ans[i-1][j]<?ans[i-1][j+(1<<(i-1))];
}
int?askRMQ(int?s,int?t)
{
????for(int?i=0;;++i)
????????if(t-s<1<<i)
????????????return?ans[i-1][s]<?ans[i-1][t-(1<<(i-1))+1];
}
void?getheight(bool?flag)?
{
????for(int?k=0,i=1,j;i<=n;height[rank[i++]-1]=k)
????????for(k?--k:0,j=sa[rank[i]-1];r[i+k].s==r[j+k].s;++k);
?????getans();
?????if(flag)
?????{
?????????tr[1]=m;
?????????for(int?i=2;i<=m;++i)
?????????????tr[i]=askRMQ(rank[1]<?rank[i-1],rank[1]>?rank[i-1]);
?????}
?????else
?????{
?????????tl[1]=m;
?????????for(int?i=2;i<=m;++i)
?????????????tl[i]=askRMQ(rank[1]<?rank[i-1],rank[1]>?rank[i-1]);????????????
?????}
}
int?main()
{
????scanf("%s",a);
????scanf("%s",b);
????m=strlen(a);
????n=strlen(b);
????for(int?i=0;i<n;++i)
????{
????????r[i+1].s=b[i];
????????r[i+1].th=i+1;
????}
????getsa();
????getheight(1);
????maxk=-1;
????for(int?i=0;i<m;++i)
????{
????????if(maxk<i)
????????{
????????????for(int?j=0;;++j)
????????????????if(j==n||i+j==m||a[i+j]!=b[j])
????????????????{
????????????????????maxk=i+j-1;
????????????????????maxi=i;
????????????????????rght[i]=j;
????????????????????break;
????????????????}
????????}
????????else
????????{
????????????if(tr[maxi-i+1]>=maxk-i+1)
????????????????for(int?j=maxk-i+1;;++j)
????????????????????if(j==n||i+j==m||a[i+j]!=b[j])
????????????????????{
????????????????????????maxk=i+j-1;
????????????????????????maxi=i;
????????????????????????rght[i]=j;????????????????????????
????????????????????}
????????????else
????????????????rght[i]=tr[maxi-i+1];
????????}
????}
????maxk=-1;
????for(int?i=0;i<n;++i)
????{
????????c[i]=r[i+1].s=b[n-i-1];
????????r[i+1].th=i+1;
????}
????getsa();
????getheight(0);
????for(int?i=0;i<m;++i)
????????d[i]=a[m-i-1];
????for(int?i=0;i<m;++i)
????{
????????if(maxk<i)
????????{
????????????for(int?j=0;;++j)
????????????????if(j==n||i+j==m||d[i+j]!=c[j])
????????????????{
????????????????????maxk=i+j-1;
????????????????????maxi=i;
????????????????????lft[i]=j;
????????????????????break;
????????????????}
????????}
????????else
????????{
????????????if(tl[maxi-i+1]>=maxk-i+1)
????????????????for(int?j=maxk-i+1;;++j)
????????????????????if(j==n||i+j==m||d[i+j]!=c[j])
????????????????????{
????????????????????????maxk=i+j;
????????????????????????maxi=i;
????????????????????????lft[i]=j;????????????????????????
????????????????????}
????????????else
????????????????lft[i]=tl[maxi-i+1];
????????}
????}
????for(int?i=m-1;i>=0;--i)
????????if(lft[i]==n&&i+n!=m)
????????????leftt[i]=lft[i]+leftt[i+n];
????????else
????????????leftt[i]=lft[i];
????for(int?i=m-1;i>=0;--i)
????????if(rght[i]==n&&i+n!=m)
????????????rightt[i]=rght[i]+rightt[i+n];
????????else
????????????rightt[i]=rght[i];
????int?maxl=0;
????for(int?i=0;i<m;++i)
????????maxl>?=rightt[i]+leftt[m-i];
????
????if(maxl<n)
????????puts("0");
????else
????????printf("%f\n",double(maxl)/m);
????return?0;
}
#define?Rank(x)?rank[(x)<?(n+1)]
using?namespace?std;
char?a[100000],c[5000],b[5000],d[100000];
int?sa[5001],height[5001],rank[5001],n,sum[5001],h[5001],_sa[5001],_rank[5001],m,ans[20][5001],tr[5001],tl[5001],maxk,maxi,lft[100001],rght[100001],leftt[100001],rightt[100001];
struct?node
{
????int?th;
????char?s;
}r[10000];
int?cmps(const?void?*a,const?void?*b)
{
????return?(*(node?*)a).s-(*(node?*)b).s;
}
int?cmpth(const?void?*a,const?void?*b)
{
????return?(*(node?*)a).th-(*(node?*)b).th;
}
void?getsa()
{
????qsort(r+1,n,sizeof(node),cmps);
????int?p=0;
????for(int?i=1;i<=n;++i)
????????if(r[i].s!=r[i-1].s)
????????{
????????????rank[r[i].th]=++p;
????????????sa[i]=r[i].th;
????????}
????????else
????????{
????????????rank[r[i].th]=p;
????????????sa[i]=r[i].th;
????????}
?????qsort(r+1,n,sizeof(node),cmpth);
?????for(int?l=1;p<n;l<<=1)
?????{
?????????memset(sum,0,sizeof(sum));
?????????memset(h,0,sizeof(h));
?????????for(int?i=1;i<=n;++i)
?????????????++sum[rank[i]+1];
????????for(int?i=1;i<=p;++i)
????????????sum[i]+=sum[i-1];????
?????????for(int?i=n-l+1;i<=n;++i)
????????????_sa[sum[rank[i]]+(++h[rank[i]])]=i;
????????for(int?i=1;i<=n;++i)
?????????????if(sa[i]>l)
?????????????????_sa[sum[rank[sa[i]-l]]+(++h[rank[sa[i]-l]])]=sa[i]-l;
????????memcpy(sa,_sa,sizeof(_sa));
????????p=0;
????????for(int?i=1;i<=n;++i)
????????????_rank[sa[i]]=((rank[sa[i]]==rank[sa[i-1]])&&(Rank(sa[i]+l)==Rank(sa[i-1]+l)))?p:++p;
????????memcpy(rank,_rank,sizeof(_rank));????????????
?????}
}
void?getans()
{
????for(int?i=1;i<=n;++i)
????????ans[0][i]=height[i];
????for(int?i=1;1<<i<=n;++i)
????????for(int?j=1;j+i-1<=n;++j)
????????????ans[i][j]=ans[i-1][j]<?ans[i-1][j+(1<<(i-1))];
}
int?askRMQ(int?s,int?t)
{
????for(int?i=0;;++i)
????????if(t-s<1<<i)
????????????return?ans[i-1][s]<?ans[i-1][t-(1<<(i-1))+1];
}
void?getheight(bool?flag)?
{
????for(int?k=0,i=1,j;i<=n;height[rank[i++]-1]=k)
????????for(k?--k:0,j=sa[rank[i]-1];r[i+k].s==r[j+k].s;++k);
?????getans();
?????if(flag)
?????{
?????????tr[1]=m;
?????????for(int?i=2;i<=m;++i)
?????????????tr[i]=askRMQ(rank[1]<?rank[i-1],rank[1]>?rank[i-1]);
?????}
?????else
?????{
?????????tl[1]=m;
?????????for(int?i=2;i<=m;++i)
?????????????tl[i]=askRMQ(rank[1]<?rank[i-1],rank[1]>?rank[i-1]);????????????
?????}
}
int?main()
{
????scanf("%s",a);
????scanf("%s",b);
????m=strlen(a);
????n=strlen(b);
????for(int?i=0;i<n;++i)
????{
????????r[i+1].s=b[i];
????????r[i+1].th=i+1;
????}
????getsa();
????getheight(1);
????maxk=-1;
????for(int?i=0;i<m;++i)
????{
????????if(maxk<i)
????????{
????????????for(int?j=0;;++j)
????????????????if(j==n||i+j==m||a[i+j]!=b[j])
????????????????{
????????????????????maxk=i+j-1;
????????????????????maxi=i;
????????????????????rght[i]=j;
????????????????????break;
????????????????}
????????}
????????else
????????{
????????????if(tr[maxi-i+1]>=maxk-i+1)
????????????????for(int?j=maxk-i+1;;++j)
????????????????????if(j==n||i+j==m||a[i+j]!=b[j])
????????????????????{
????????????????????????maxk=i+j-1;
????????????????????????maxi=i;
????????????????????????rght[i]=j;????????????????????????
????????????????????}
????????????else
????????????????rght[i]=tr[maxi-i+1];
????????}
????}
????maxk=-1;
????for(int?i=0;i<n;++i)
????{
????????c[i]=r[i+1].s=b[n-i-1];
????????r[i+1].th=i+1;
????}
????getsa();
????getheight(0);
????for(int?i=0;i<m;++i)
????????d[i]=a[m-i-1];
????for(int?i=0;i<m;++i)
????{
????????if(maxk<i)
????????{
????????????for(int?j=0;;++j)
????????????????if(j==n||i+j==m||d[i+j]!=c[j])
????????????????{
????????????????????maxk=i+j-1;
????????????????????maxi=i;
????????????????????lft[i]=j;
????????????????????break;
????????????????}
????????}
????????else
????????{
????????????if(tl[maxi-i+1]>=maxk-i+1)
????????????????for(int?j=maxk-i+1;;++j)
????????????????????if(j==n||i+j==m||d[i+j]!=c[j])
????????????????????{
????????????????????????maxk=i+j;
????????????????????????maxi=i;
????????????????????????lft[i]=j;????????????????????????
????????????????????}
????????????else
????????????????lft[i]=tl[maxi-i+1];
????????}
????}
????for(int?i=m-1;i>=0;--i)
????????if(lft[i]==n&&i+n!=m)
????????????leftt[i]=lft[i]+leftt[i+n];
????????else
????????????leftt[i]=lft[i];
????for(int?i=m-1;i>=0;--i)
????????if(rght[i]==n&&i+n!=m)
????????????rightt[i]=rght[i]+rightt[i+n];
????????else
????????????rightt[i]=rght[i];
????int?maxl=0;
????for(int?i=0;i<m;++i)
????????maxl>?=rightt[i]+leftt[m-i];
????
????if(maxl<n)
????????puts("0");
????else
????????printf("%f\n",double(maxl)/m);
????return?0;
}
這道題是03年饒向榮論文里的一道題 有一定難度
除了T數組的求解和論文中不同外 沒有什么不同
論文中說的方法沒看懂 期望有牛人能講一下
我的方法很簡單就是通過后綴數組完成的 但大大增加了代碼長度這好象是我寫oi題目寫的最長的一道了(我太弱了) 一個不錯的開始期望以后每天都能AC并且要多
]]>
其貪心、構造、調整法頗多 還有一些沒聽說過的 例如差分約束系統、最小限度生成樹、區間圖判定、最小表示法等等 還涉及到許多數論、幾何知識
除了前30題 后面的題 有許多都是NP問題 或者說是無法在要去時間內出解的問題 對提交答案式問題去頗幫助
其中一些搜索題目的技巧性很高 可以達到一想不到的效果 甚至比某些多項式算法的運行時間還快
多說無意畢竟這套資料是以前集訓隊留下來的 大家說的一定比我強
下面3周我將作一些專項訓練 大概會使用到WC論文和集訓隊作業 另外這次的訓練要多寫代碼 逢題必AC(雖然不一定是自己想的)
再下面的一周也就是CTSC前的一周我將計時完成以往的CTSC、WC、APIO 從而找到手感迎接即將到來的CTSC、APIO
]]>
差分約束系統
限制最小生成樹
調整法
區間圖判定
最小表示法
對構造、貪心有了更進一步的認識
還學了一點數論、幾何知識
另外 我發想 有些題實在不好證明就不要證明 尤其是貪心、構造、調整法 有時候即使是錯的也可能又不錯的收效
要嘗試 一個題寫多個程序 小數據搜索 大數據寫一個不太完善的算法 （當然要是能寫出完善的最好）
還有我的代碼能力實在有待提高
]]>
??? 癥狀界定有七項標準，其中一項量化的指標是平均每天連續使用網絡達到或超過6小時，而且這種癥狀達到或者超過3個月。
]]>
接下來的幾天oi的進展都不大 沒有狀態100book里的每一個題基本都要看解題報告 有的看解題報告都沒看懂 除非出原題 要是讓我自己做一定做不上
話又說回來這兩天看的題都挺偏的 坐不上也有情可原 多見一些沒準就會了
老師又想讓我參加吉大的ACM隊 其實我不想去 吉大的ACM很水 而且又不把我分到1隊 去了只是提高代碼能力(雖然我的代碼能力有待提高) 回頭再和老師商量一下
說了這么都希望能帶走不好的狀態 下一階段要全力以赴oi 離CTSC APIO就剩5周了
在這5周里 我希望能完成 100book剩下的30+ 以及以往的CTSC WC APIO 要是可能就再看一點集訓隊作業
]]>
限制如下
所有的大廳和通道都在同一水平面上。
沒有兩條通道相交。
有一些大廳位于山洞的外圈上，我們稱其為外廳。
其他所有位于外圈內部的大廳被稱為是內廳。
有且僅有一個外廳有著一個通向山洞的入口。
每一個大廳都恰好連接著三條通道，通向三個不同的另外的大廳。對于任意一個外廳，則有兩條通道通向外圈上另外兩個鄰接者的外廳，另一條通道連接著一個內廳。
連接外廳的通道稱作外通道，其他的稱作內通道。
通過這些限制我們可以提煉出如下信息以便我們解題:
1、將所有外邊刪掉 該圖就是一棵樹 而且是平衡二叉樹
2、將外廳按順時針序(逆時針同理)排序則可行路徑上的外廳一定是遞增的
這道題目的解法有很多種 我想到的就有3種
一：樹形動態規劃
不考慮外邊 設f[i]表示以i為根節點的子樹上的最小花費
先初始化每一條外邊 在兩端點的最近公共祖先上記錄在最近公共祖先上
開始動態規劃 對于每一個i枚舉記錄在它上的外邊 費用為兩端點的路徑上的費用+不在路徑上的f[u]
太晚了 其他的明天再說
]]>
IPSC這個比賽很有意思 所有題目都是提交答案式的 可惜我英文不好 還要組隊
有意與我組隊請與我聯系 我的郵箱：wwy250@gmail.com
還有通過這個比賽的排名還是看出中國的教育存在著巨大的問題
學生組具有壟斷地位 而成人組就不行了
言歸正傳
很容易想到的是二分圖最大匹配的問題 可以在比賽的時間內跑出來
還有一種更優的方法 對于每種S 可以在O(1)時間內接觸c
對于每一種S:{a1,a2,～～,a(n+1)/2} (a1<a2<～～<a(n+1)/2) c=a((a1+a2+～～+a(n+1)/2)%((n+1)/2))
這個可以用反證法證明：
若存在兩個方案刪數后的方案相同，設為
A
，
B
（集合），
另
a1<a2<
……
<am,b1<b2<
……
<bm
，
若
A
中刪去元素
ai
，
B
中刪去
bj
，不妨設
i<j
，顯然有
ai<bj
根據條件，
j-i=(bj-ai) mod m,
所以
bj
－
ai
＝
j-i
或者
j-i+m
?
若
bj
－
ai
＝
j
－
i
，因為
ai+1...aj=bi...bj-1,
所以
bj-ai-1>=j-i,
所以不可能
?
若
bj
－
ai
＝
j
－
i+m,
??
因為若
A
，
B
存在，則必滿足
(m-j)+(i-1)<=(n-bj)+(ai-1)
??
因為
n
＝
m
＋
m-1,
所以
bj-ai<=j-i+m-1,
該情況也不能
綜上所述，不可能存在兩個方案刪數后的方案相同。
]]>
周源：
貪心算法，也可以說成是構造算法吧，證明是我自己寫的，應該是對的吧。
本題可以理解為，給定頂點數N和每個定點的度，要求構造一個滿足要求的簡單圖。構造算法是這樣的：為了敘述方便，我們每次選擇剩余度數最大的點A（這是無所謂的，但是如果選擇最大的點，算法描述和證明要簡單一些）。讓這個點依次和度數次大，第3大……的點連線，如果最終不夠連了，那么顯然無解，否則連完之后，該點就可以不考慮了，然后繼續子問題的求解……，直到構造出解或者得到無解。
證明：設在某步構造的時候，將A和B連線，但是已知解中，A,B間卻沒有連線，相反的，A,C之間卻有邊相連，且D(B)>D(C) （D表示定點的度），正因為如此，一定至少有一個點Z滿足Z和B之間有邊但是與C卻沒有邊，這樣，將A,C邊改為C,Z，B,Z邊改為A,B仍然滿足條件，于是也滿足算法的要求，可以被算法構造出來。
]]>
對于這個題 設xi為第i時刻實際雇傭人數 numi為上限 si=si-1+xi，s0=0 ri題目中提到 則
numi>=si-si-1>=0
si-si-8>=ri （i>=8）
si+s24-si+16>=ri (i<8)
在第3個不等式中出現了3個未知數 但s24重復出現所以可以枚舉s24 還可以二分優化
下面是我的代碼
#include<iostream>
using?namespace?std;
int?n,m,dis[1000],num[25],r[25];
struct?
{
????int?u,v,d;
}e[1000];
inline?bool?relax(int?u,int?v,int?w)
{
????if(dis[v]>dis[u]+w)
????{
????????dis[v]=dis[u]+w;
????????return?true;
????}
????return?false;
}
inline?bool?getdis()
{
????for(int?i=1;i<=n;i++)??dis[i]=1<<30;
????dis[0]=0;
????for(int?i=1;i<=n;i++)
???????for(int?j=1;j<=m;j++)
???????????????relax(e[j].u,e[j].v,e[j].d);
????for(int?i=1;i<=m;i++)??
???????if(relax(e[i].u,e[i].v,e[i].d))
???????????return?false;
????return?true;????????
}
inline?void????adde(int?a,int?b,int?c)
{
????e[++m].u=a;
????e[m].v=b;
????e[m].d=-c;
}
int?main()
{
????freopen("input.in","r",stdin);
????freopen("output.out","w",stdout);
????n=24;
????for(int?i=1;i<=n;++i)
????????scanf("%d",r+i);
????int?g;
????scanf("%d",&g);
????for(int?i=1;i<=g;++i)
????{
????????int?p;
????????scanf("%d",&p);
????????++num[p+1];
????}
????int?s=g,ed=-1;
????for(;;)
????{
????????if(s==ed+1)
????????{
????????????printf("%d\n",s);
????????????return?0;
????????}
????????m=0;
????????int?t=(s+ed)/2;
????????for(int?i=1;i<=n;++i)
????????{
????????????adde(i,i-1,0);
????????????adde(i-1,i,-num[i]);
????????}
????????for(int?i=8;i<=n;++i)
???????????????adde(i,i-8,r[i]);
?????????for(int?i=1;i<8;++i)
?????????????adde(i,i+16,r[i]-t);
???????????if(getdis())
???????????????s=t;
????????else
????????????ed=t;
????}
}
using?namespace?std;
int?n,m,dis[1000],num[25],r[25];
struct?
{
????int?u,v,d;
}e[1000];
inline?bool?relax(int?u,int?v,int?w)
{
????if(dis[v]>dis[u]+w)
????{
????????dis[v]=dis[u]+w;
????????return?true;
????}
????return?false;
}
inline?bool?getdis()
{
????for(int?i=1;i<=n;i++)??dis[i]=1<<30;
????dis[0]=0;
????for(int?i=1;i<=n;i++)
???????for(int?j=1;j<=m;j++)
???????????????relax(e[j].u,e[j].v,e[j].d);
????for(int?i=1;i<=m;i++)??
???????if(relax(e[i].u,e[i].v,e[i].d))
???????????return?false;
????return?true;????????
}
inline?void????adde(int?a,int?b,int?c)
{
????e[++m].u=a;
????e[m].v=b;
????e[m].d=-c;
}
int?main()
{
????freopen("input.in","r",stdin);
????freopen("output.out","w",stdout);
????n=24;
????for(int?i=1;i<=n;++i)
????????scanf("%d",r+i);
????int?g;
????scanf("%d",&g);
????for(int?i=1;i<=g;++i)
????{
????????int?p;
????????scanf("%d",&p);
????????++num[p+1];
????}
????int?s=g,ed=-1;
????for(;;)
????{
????????if(s==ed+1)
????????{
????????????printf("%d\n",s);
????????????return?0;
????????}
????????m=0;
????????int?t=(s+ed)/2;
????????for(int?i=1;i<=n;++i)
????????{
????????????adde(i,i-1,0);
????????????adde(i-1,i,-num[i]);
????????}
????????for(int?i=8;i<=n;++i)
???????????????adde(i,i-8,r[i]);
?????????for(int?i=1;i<8;++i)
?????????????adde(i,i+16,r[i]-t);
???????????if(getdis())
???????????????s=t;
????????else
????????????ed=t;
????}
}
]]>
第一題是一道數學問題
學過數學競賽的人一定知道對于這個問題
分得的所有數一定不是2就是3
而且2的個數<3
證明如下
顯然分成含有1的顯然不是最優的
若含有p(p>3)則可將其分成由2、3的和組成的序列保證其不差于此當前方案
第二題 一道維護決策單調性的DP
定義f[i][j]在前i個點建j個站前i個點以及建站的費用最小為多上
s[i][j] 為f[i][j]的方案
顯然s[i-1][j]<=s[i][j]<=s[i][j+1]
剩下的就不說了
]]>
可能你會問ubuntu用的好好的為什么要卸呢 那就接著往下看吧
話說我讓我們老師個我刻了一張 ubuntu 8.10 想做一個ubuntu以使用NOI時要用的Manna
之前我連windows都沒自己裝過 但我還是硬著頭皮自己安裝了
安裝的還算順利 可是當我真正開始使用這個系統時 我發現 ubuntu 的漢化對于我這種一見到英文就暈的人來講實在是不能忍受 于是我就想卸掉ubuntu
俗話說上山容易下山難 我上網大概查了一下資料就開始了我的卸載工作
不知道怎么回事 我沒有格式化安裝ubuntu的分區而是刪除了那個分區 又不知為什么 我的那個存OI資料的分區也跟著沒了 又不知怎么回事我的XP也進不去了(具體的我也說不清楚 我要是清楚我也不會作出那樣的事)
ghost也不好使了 于是我找老師幫我了一個硬盤殼 把它在別的機器上格了 然后從做的XP 有花了好長時間裝了一些我常用的軟件以及找回我的OI資料(我的備份只到去年的11月)
然后我決定安裝NOI Linux
裝NOI Linux一開始很容易 就像ubuntu一樣
可是到了分區的時候 它的表示很不明確很容易給人造成誤解
于是我拿出了那張ubuntu在臺式機上安裝
在對照之下終于成功了
具體的細節我是說不清楚了 請大家諒解一個以oi為主業&丟失了他很多oi資料的人
]]>
其實那是我的blog中文章的鏈接(首頁顯示的都是隨筆)
由于我沒有選中發布 所以這個鏈接只有我能看得到
給大家帶來不便 請諒解
現已發布
從發布起此片隨筆將被置頂1周
]]>
這套題做的很囧
第一題 題目沒什么說的就是模擬 不過很麻煩
但是題目里的游戲很好玩 真的很好玩
第二題 一開始看像04年 ACM上海賽區的H題 田忌賽馬 記得集訓隊資料里的解法是O(n^2)
但是發現 n<=100000 后來發現這題與田忌賽馬是不一樣的
田忌賽馬 是求最大|小分差 那么怎么貪心呢
以求最高分為例 提出一個策略：
設我方的選手集為A? 對方為B
若Amax>Bmax
則A-=Amax,B-=Bmax? ans+=2
否則 A-=Amin,B-=Bmax 如果Amin==Bmax? ans+=1
下面是證明
若Amax>Bmax
假設有一種方案 使得Bmax不與Amax交戰&得分>當前方案
設于Bmax、Amax交戰的分別為a,b
則將Bmax與Amax交戰 a與b交戰? 其余與該方案相同 易證此方案不亞于 該方案&此方案得分=原方案
若Amax<=Bmax 同上述方法可證 這里就不多說了
值得一說的是第4題 我想了2天 實在沒有思路將一些想法記在下面并將它添加到未解決問題中
首先想到的是將它想LCA->RMQ一樣搞出一個歐拉序列 通過維護這個序列解題
那么借助什么數據結構好呢 線段樹？
這好像不可能 倒不是得到答案的問題
關鍵是每次更改都要不止更改一個或常數個
看來 搞成一個序列是沒戲 那么仍保持樹狀結構呢
這回 更改時好辦了 但怎么得到答案哪
我又標程 不過我這個人最不擅長就是讀程序 但可以看出標程用到平衡樹
實在是不會 等oibh好了到哪頂上問問應該會有結果
]]>
終于知道JLOI為什么是5題4h了 因為JSOI也是 而JS給JL出題 風格當然一樣
而且也會有一些比較偏的題目 還有一點是數據弱他還不告訴你 比如最后一題樸素快排就能90分 如果是NOI的會 一定會說90%的數據n<=?的而且不會是90%的 最多是40% 沒辦法省選又沒人贊助誰給你好好出題(好像今年NOI就沒有所以WC的題目所有'<='都打成了‘=’)
言歸正傳
這套題目好題還是有的
比如第一題 雖然我至今沒搞明白 但是我知道他要求的是：從A中選取最少的點 使得B中所有點都在A中選取點的凸包內? 這個變化十分巧妙
第二題 枚舉和牌和對子是必然的趨勢 那么剩下的判斷是否為和就只能在線性時間內解決了
也就是說題目只給了我們掃一次(或常數次)的機會 而且是能按n掃
這么近的時間不得讓我們想到貪心 如果對于一張牌 可以組成順子 也可以組成刻牌 這個時候一定要有一種固定的選擇
假設選擇順子 很顯然若是111234 本來可以和的牌 就不胡了
那如果是刻字呢 經反復試驗沒有找到反例 在時間緊張的比賽中 不一定一定要證明 于是我寫了一下
AC
看來我的感覺還可以 但光靠感覺是不行的 證明如下
若經過上訴貪心方法的到的答案是和牌則 這副牌一定是和牌
所以只需證明經上述算法得到的答案為非和時 這副牌一定非和 下面的證明均在經上述算法得到的答案為非和前提下進行
假設有一種方案能使這副牌和
則一定有至少一處 原方案為刻字而新方案為順子
將每個組合按最小、較小、最大3個關鍵字順次按有小到大排序
找到第一次這樣的地方
顯然之前的牌組合的方式兩種方案是一樣的
所以當將原方案中的刻字轉化為順子后 如果該方案為和牌則另兩張在原方案為刻字的牌也與其后面兩張組成順子 與組成3個刻字等效 所以假設不成立(這樣和在我們吉林打法還大呢)
第3題 我認為是一道比較偏的題目 看了解題報告仍覺得比較偏
一個被逼無奈的貪心 結果竟是AC 在這里我不想多說了 有興趣的同學看這里吧
第4題 比較常見的DP 好像在URAL上做過 就是搞一個f[i][j]表示前i個字符 后綴為前綴j(這里的j只在我們預先搞好的trie里的編號)不含有可識別單詞的個數 重點維護f 總之很麻煩 但好想 我就不想說了(我的表達能力容易把自己說糊涂了)
第5題 赤裸裸的后綴數組 只要將原串加倍即可 我的倍增可以AC而解題報告說這么做會超時 是不是他用string了 不超時才怪呢
]]>
由于是01年的題目
難度自然比較低
前3題都是搜索/模擬題 在這里就不多累述
第4題一開始被他數據小的特點蒙騙了
搜索|狀態壓縮的DP 好像都不行 一時間沒了頭緒
后來想到了二分圖 其實早應該想到二分圖
以橫向為例 顯然對于每一條線段 如果線段上沒有"墻" 則線段上對多只能有1個車
縱向同理
所以先遍歷一次這個矩形 求出所有上述線段 以及所有非墻格子所在的橫縱線段
將所有有相交的線段之間連一條邊 求二分圖最大匹配即可
對于某些所求為XX最多 每個XX影響兩個元素的題目 二分圖往往能夠起到作用
]]>
但是是江蘇給我們出省選試題 不做不行
各位游客如有江蘇試題希望能共享資源
]]>
對于這到題目很容易看出是一個多字符串匹配問題 顯然是要用到trie圖
不過這個題目要求將所有定式 一次trie恐怕是做不了了
難道要用其他的方法么 雖然單純的trie無法滿足題目要求 但是沒有比他再像的了
繼續思考trie圖可以完成的事將所有匹配成功的位置以及與誰匹配返回
但是每個匹配成功的位置只能返回一個 與其成功匹配的字符串 顯然這會有遺漏
比如
dd
bbdd
去匹配bbdd則最多只會有一個被記錄
顯然如果一個兩個串需要同時被記錄當且僅當一個串是另一個串的后綴并且較長串被匹配
所以每次記錄長度最長的字符串即可
在這次匹配之后建一顆trie將所有字符串的逆串插入
查找所有被記錄的字符串將路徑上所有的字符串記錄即可
]]>
其實JLOI的題目不怎么好 題目不是簡單就是偏 好題很少 但我畢竟是JL人 JLOI還是要做的
連續做了7年的JLOI 從中看出了JLOI的成長 這一點讓我很欣慰 畢竟整體水平的提高會帶動個人的提高 這叫做水漲船高
但是不得不說JLOI的導向不好 水題多&時間少
強烈建議加大難度 改成two day 5h3題 這樣才像NOI
以前的省選只要拿到基礎分就可以進省隊了 這個導向很不好 應該讓真正能做上難題的人進才對
不過做在不好的題目也會有收獲 下面是我的收獲：
08 05 ：通過這到題從新認識了一下AC自動機 原來他不是向treap一樣只要寫對了就沒事了
他有一些變化 所以我決定 明天看一下《多串匹配算法及其啟示》《Trie圖的構建、活用與改進》
05 03 ：知道了二分圖最小點覆蓋這個模型
另外還有了一些騙分、那部分分的心得 只可意會不可言傳
另外由于時間關系08 04、06 03沒有好好研究一下明天同一研究
]]>
雖然拿到了滿分 但是那是因為數據若 我用的是先想解決2—SAT問題貪心一個解在隨機化搜索的方法
這個題有沒有多項式算法？
沒看懂題題目中的"好"/"佳"沒搞明白什么意思
但感覺應該是一道值得一做的題目?
塊狀鏈表
這個大概思想知道 有沒有一個向講treap一樣詳細的資料把他的具體實現方式以及所有的功能詮釋
最小費用流 的負環情況的的處理方法
二維凸包?
上面兩個題我都有解題報告不幸的是沒看懂 大家可以去看看 看看會不會有什么啟示
]]>
]]>
越往前做題目就越簡單了 而且只有4道
通過省選試題難度的變化 看來JLOI這幾年確實進步了不少
這次的題目全都做上了
第一題是一道數學題 在這里就不多說了
第二題他讓你求的是一個點(x,y)使得sigema(wi*((x-xi)^2+(y-yi)^2))(1<=i<=n 以下同此)最小
初看這個式子里又有x 又有 y 很復雜不好權衡
可是乘法是符合結合率的
所以原式=sigema(wi*(x-xi)^2)+sigema(wi*(y-yi)^2)
所以當sigema(wi*(x-xi)^2)、sigema(wi*(y-yi)^2)都取道最小時既為所求
則就好辦了就是一個帶權平均數問題(這個好像有學名不過忘了)
以x為例x=sigema(wi*xi)/sigema(xi) y同理
第3題：
如果枚舉任意2個為c的方塊然再bfs或并查集找最長曲線顯然是要超時的(O((n*m)^3)，1<=n,m<=30)
發現由于只改動兩個方塊而每次都求一邊最長曲線會造成許多重復運算
如果現將整個矩陣先用并查集做一遍然后枚舉該邊哪兩個為c的方塊再算最長曲線就可以在常數時間內完成最長曲線的求解
如果你總是覺得用什么不對勁的地方 沒關系(其實我一開始也是這樣的)
我還有一種人那你放心的方法：先枚舉一個c然后做一次并查集然后再枚舉另一個c再用并查集求解 這回不亂了吧(能合并的最多有2條曲線) 這個方法只是將常數增大了 而讓算法清晰了 不失為一種不錯的選擇
第4題
想了好久差點放棄了 因為只想到了O((n+m)*(n*m)^2)的算法
但后來一看1<=n,m<=10這個時間復雜度是綽綽有余的
顯然任意一個被切下來的矩形都與其他矩形再無干系 這就使得這個模型沒有后效性
提到后效性不由得讓我們想到DP
狀態為f[x1][y1][x2][y2]表示把左上角為(x1,y1) 右下角為(x2,y2)的矩形分割成題目中要求的形態最少需要的切割長度 轉移只需要枚舉切割線就好了
]]>
這套題之前沒有做過 不過還是沒有NOI什么也做不上的感覺
1、2、4題居然全是DP
分別是以當前位置+路徑長度、以當前節點為根結點的子樹+使用機器數、當前節點+當前時間為狀態
其中2題的狀態轉移又是一次DP 方法類似背包問題
第5題 我只想到了m*n*logn^2的算法：枚舉m通過二分+樹狀數組查找下一步的位置 雖然不能AC但打表還是可以的(最大的點用時13s)
后來在OIBH上看到了一個n^m的解法：枚舉m 將問題劃歸成長度為n-（被刪除的城市個數）北京的位置隨之改變 這樣既可以忽略被刪除的城市
特別注意m不應定<=n
第3題 這道題總數后點收獲 二分圖最小點覆蓋問題 可惜我從來沒聽說過 現在聽說也不晚如果你還沒聽說過就去看看這個吧：http://www.matrix67.com/blog/archives/116
現在看來很簡單了 搞n+m各點表示每行/列 讀入01矩陣 若該點是1則將所在行與所在列連一條邊
剩下的工作就是求二分圖最小點覆蓋了 也就是它的最大匹配
]]>
我發現做雖然我是JL人但是做JLOI很沒有意義原因在于簡單&題目偏&我很多都做過
這樣好了 我就不限時做了 把認為在比賽中應該做的寫出來好了
這套題好象是170+就能進省隊 不過那是當年 現在300怎么也可以了吧
顯然2、4是可以拿200分的
那下一個100該怎么拿呢
由于第3題敘述不清+我的文學水平較差所以我沒看懂題
第5題我同樣沒看懂
可是第1題用2—SAT的方法初始化+隨機化搜索居然拿到了滿分 真是天無絕人之路
]]>
由于這套題很簡單并且做過就沒有一一去做只是把不會的做了一下
1：模擬
2：加分二叉樹
3：枚舉
4：數學題 維護一種平衡
當年AC的程序如下：
#include<fstream>
using?namespace?std;
ifstream?cin("smiley.in");
ofstream?cout("smiley.out");
double?y64(double?k)
{
????if(k<64)?return?k;
????else?return?y64(k/64);
}
int?main()
{
????double?i,n,m;
????int?ans;
????cin>>m>>n;
????ans=0;
????i=y64(n/m);
????if((1<=i)&&(i<2))ans=0;
????if((2<=i)&&(i<4))ans=2;
????if((4<=i)&&(i<8))ans=4;
????if((8<=i)&&(i<16))ans=8;
????if((16<=i)&&(i<32))ans=16;
????if(32<=i)ans=32;
????cout<<ans;
????return?0;
}
5.唯一的有一定難度的題using?namespace?std;
ifstream?cin("smiley.in");
ofstream?cout("smiley.out");
double?y64(double?k)
{
????if(k<64)?return?k;
????else?return?y64(k/64);
}
int?main()
{
????double?i,n,m;
????int?ans;
????cin>>m>>n;
????ans=0;
????i=y64(n/m);
????if((1<=i)&&(i<2))ans=0;
????if((2<=i)&&(i<4))ans=2;
????if((4<=i)&&(i<8))ans=4;
????if((8<=i)&&(i<16))ans=8;
????if((16<=i)&&(i<32))ans=16;
????if(32<=i)ans=32;
????cout<<ans;
????return?0;
}
其實也不難
搞一個小根堆
隊中的元素為一些線段 維護向這個線段注水從開始到溢出的時間 要求每個線段的左端擋板與右端擋板均為線段中最高的
每次取根結點將它與它將溢出方向上的第一個線段合并 直至該線段為最左或最又的線段
]]>
由于做過分高一點
1.模擬沒什么說的 得分100
2.動態規劃 得分100
令f[c][l]=為匹配部分為字符串c的前綴l使得后面的字符串有兩種分解方法的最小長度
這句話說的我自己都聽不懂請大家結合下圖看
所以答案即為min(f[i][0]|1<=i<=n)
轉移方程為：f[c][l]=min(min(getf(i,strlen(s[c])-l)+l|后綴l+1為i的子??? 串),min(getf(c,l+strlen(s[i]))|i為后綴l+1的子串))
至于輸出方案就不用我說了吧
3.按N皇后搜的 得分30
4.貪心+隨機化+卡時 得分54
每次對于能直接拓展的每個節點有一個權值既通過該節點可直接拓展的節點數×一個隨機數（0<rand()<1）
從小到大一次拓展全職由小到大的節點+上一個卡時就是這個分數
5.KMP做的 得分80分
想到 AC自動機可是我只能判斷字符串集里是否有棋局的子串 而如可將所有子串求出無從下手
]]>
所以只放出我搜索到的資料（大部分看了 還有一些沒看懂）
這是1月前我寫給自己看的 所以很亂 好多都是我硬盤里的地址
大家就將就著看吧
閱讀全文
]]>
由于以后還有機會用到就沒有一一測試
但思路一定是正確的
如果發現錯誤期望提出
里面 trie圖錯了
這樣就對了
#include<iostream>
using namespace std;
struct node
{
bool match;
node *faild,*chaild[26];
}*trie=new node(),*super=new node(),*q[100000];
int h,l;
void insert(node *t,char *c)
{
if(!*c)
{
t->match=1;
return ;
}
if(!t->chaild[*c-'a'])
t->chaild[*c-'a']=new node();
insert(t->chaild[*c-'a'],c+1);
}
void build()
{
for(int i=0;i<26;++i)
super->chaild[i]=trie;
trie->faild=super;
q[l=1]=trie;
for(;h++!=l;)
{
node *p=q[h];
for(int i=0;i<26;++i)
if(p->chaild[i])
{
p->chaild[i]->faild=p->faild->chaild[i];
p->chaild[i]->match|=p->chaild[i]->faild->match;
q[++l]=p->chaild[i];
}
else
p->chaild[i]=p->faild->chaild[i];
}
}
char c[1000];
int match(node *t,int th)
{
if(t->match)
cout<<th<<endl;
if(!c[th])
return 0;
return match(t->chaild[c[th]-'a'],th+1);
}
樹狀數組里ask的變量名打錯了using namespace std;
struct node
{
bool match;
node *faild,*chaild[26];
}*trie=new node(),*super=new node(),*q[100000];
int h,l;
void insert(node *t,char *c)
{
if(!*c)
{
t->match=1;
return ;
}
if(!t->chaild[*c-'a'])
t->chaild[*c-'a']=new node();
insert(t->chaild[*c-'a'],c+1);
}
void build()
{
for(int i=0;i<26;++i)
super->chaild[i]=trie;
trie->faild=super;
q[l=1]=trie;
for(;h++!=l;)
{
node *p=q[h];
for(int i=0;i<26;++i)
if(p->chaild[i])
{
p->chaild[i]->faild=p->faild->chaild[i];
p->chaild[i]->match|=p->chaild[i]->faild->match;
q[++l]=p->chaild[i];
}
else
p->chaild[i]=p->faild->chaild[i];
}
}
char c[1000];
int match(node *t,int th)
{
if(t->match)
cout<<th<<endl;
if(!c[th])
return 0;
return match(t->chaild[c[th]-'a'],th+1);
}
正確的應是
#include<iostream>
#define lowbit(x) ((x)&(-(x)))
using namespace std;
int c[1000001],n;
inline void add(int p,int v)
{
for(int i=p;i<=n;i+=lowbit(i))
c[i]+=v;
}
inline int ask(int p)
{
int r=0;
for(int i=p;i>0;i-=lowbit(i))
r+=c[i];
return r;
}
#define lowbit(x) ((x)&(-(x)))
using namespace std;
int c[1000001],n;
inline void add(int p,int v)
{
for(int i=p;i<=n;i+=lowbit(i))
c[i]+=v;
}
inline int ask(int p)
{
int r=0;
for(int i=p;i>0;i-=lowbit(i))
r+=c[i];
return r;
}
]]>
網絡流&二分圖
線段樹
DP
基礎代碼:treap、樹狀數組（1、2維）、后綴數組、有/無（上下界的）（費用）最大流、強聯通分量、kmp、AC自動機、LCA——RMQ、heep+dis、 塊狀鏈表 、高斯消元、leftheap+topsort+歐拉路 +以前寫過的
3h內不看答案? 最后寫出來? 每天3個題（可用基礎代碼）
100book
論文
集訓隊作業
sgu
ctsc
wc
預計用時：14week
熟練基礎代碼
預計用時：1week
第一遍 ：做題——每題記時做 4h內 記錄通過調試過樣例時間、通過初步測試時間、通過對拍時間 并分別保存測試記錄
第二遍 ：非AC 每題記錄 通過調試過樣例時間、通過初步測試時間 并分別保存測試記錄（時間×1.5，得分×70%）
第三遍 ：看解題報告
每天2個題
制定NOI2009方案
noi（不可用基礎代碼）
預計用時：4week
強化線段樹、dp&調整作息時間
預計用時：1week
我會在完成每項后放出所用到的資料名稱以及我的原創資料 最前面已經是一個月之前的事了我放不了那么全了
注釋：綠色為已完成
]]>
出生日期：1993.6.4
年齡：自己算
身高：1.86m
體重：50+kg(+很多很多)
現就讀于吉林省東北師范大學附屬中學初中部
聯系方式：Gmail|Gtalk|MSN=wwy250@gmail.com QQ=1061227912 （有意結交者請留言）
當前狀況：家里蹲
愛好：oi
曾獲獎項：
NOI 08 Cu
NOIP 09提高 1=（2nd in jl）（初中沒有正式證書|報送號）
當前目標：NOI Au
正在做 100book
]]>
正向我的Blog名所表示的一樣大家將在這里看到我的oi之路
出身在一個弱省的我更加能體會到一個人學習oi的不易
曾多次因無人輔導&找不到方向而苦惱
所以期望我的Blog能對廣大oi初學者有所幫助
如果對我Blog中的內容有疑議請給我留言|發送郵件給我
另注：在我的文章中可能常常在漢語描述中出現C++的邏輯運算符‘&’‘|’‘^’等字樣希望不要影響大家閱讀
由于我的文學水平有限難免出現語句不通|錯別字現象
另外我不喜歡用標點 基本以‘ ’換行代替
望大家見諒
]]>