当前位置:首页 >> 企业管理 >>

2009noip提高组复赛题解


NOIP2009 提高組複賽試題解題報告
NOIP2009 提高組複賽試題解題報告

一、潛伏者(spy) 問題描述: 給出密文及對應明文,求字母的對應關係並破譯密文。 解題思路: 水題。只需把字符串掃描一遍,邊掃邊增加對應關係。並判斷既有之對應關 係是否正確。最後判斷是否每一個字母都有其對應字母。 需要注意不僅要判斷是否每一個密文字母都存在惟一對應的明文字母, 還要 判斷是否每一個明文字母都存在惟一對應的密文字母。 (去年我沒判斷這個,所 以測試點三 WA 了,九十分) 最後若失敗輸出“Failed”,否則按照對應字母輸出即可。 建議時間: 15-25 分鐘 題很簡單,就是要考慮全面一些,第一題的分不能錯過。盡量多調試一下。 二、Hankson 的趣味題 題目描述: 已知 x 和 a0 的最大公約數是 a1,x 和 b0 的最小公倍數是 b1。求 x 的解的 個數。 解題思路: 算法一: 最簡單的方式是枚舉,x 從 a1 取到 b1,然後判斷 x 是否為解。 這種方法能得到一少半分數,因為數很大。 優化:

由於x必是 a1 的倍數, 亦必是 b1 的約數,所以枚舉時可以枚舉 a1 的倍數, 判斷是否為 b1 的約數, 然後再輾轉相除驗證解。另外 b1/2 至(b1-1)之間沒必要 枚舉,可去除這段區間。 (我去年這樣得到了五十分) 算法二: 考慮素因數的性質:若 gcd(x,a0)=a1,x、a0 和 a1 含有某一素因數 p 的個 數分別為 r、s 和 t,則必有 t=min(r,s)。故 x 含有 p 的個數滿足: 若 s=t 則 r>=s; 若 s>t 則 r=s; 由最小公倍數亦可得到(設 u、v 分別為 b0、b1 含 p 的個數): 若 u=v 則 r<=v; 若 u<v 則 r=v; 如此便得到了 r 的取值範圍,進而得到 r 可取值的個數。 這樣的話,就可以將 a0 和 b1 分解質因數,並對每個質因數都計算一次 r 的解數。依乘法原理,將它們相乘即可得到答案。 這種方法可得到 80 分左右。 為了減少分解時的冗餘判斷,加快分解的速度,可以預處理出五萬以內的素 數表(約五千多個)。這樣就可以拿到滿分。 建議時間: 35-45 分鐘 這道題考察到數論知識,對數學和編程都是一大考驗。先寫個暴力再說,可 以先做做後面的題。 不要浪費太多時間,如果對高級算法把握不大就寫簡單算法 騙分吧。得分最重要。 三、最優貿易(trade) 題目描述: 給定一個有向圖,每個點都有一個價格。要求找一條從 1 到 n 的路,路上 有至多一次買進和賣出,使得所獲利潤最大。

解題思路: (我去年不會這道題,輸出 0 騙了十分) 可以搜索路徑,找最低的買價和最高賣價(先買後賣)。效率不高。 考慮到買和賣具有階段性,可以用動態規劃。 設 f(i)為從 1 到 i 的路徑中的最低買價,g(i)為從 i 到 n 的路徑中的最高 賣價。只要求出 f、g,那麼最大的(f(i)-g(i))或 0 就是答案。 那麼如何求 f 和 g 呢? 明顯在存在有向邊 i->j 時有 f(i)=min(f(i),f(j),price[j]),g(i)則反過 來,因此可以通過鬆弛操作來實現。分別以正、反兩個方向做一次 SPFA(相當 於優化了的寬搜,不是標準的最短路,故本題不可用 dijkstra+heap),找到最 大的(f(i)-g(i))即可。 另外標準的解法是將強連通分量縮為一點。再利用拓撲排序逐層求 f、g, 代碼量稍大。 建議時間: 40-50 分鐘 最好先寫個簡單程式。求 f、g 的方法是本題關鍵。由於後面的數獨比較容 易騙分,所以可以先把第四題騙了分,再來仔細做這個題。 四、靶形數獨(sudoku) 題目描述: 已知一數獨題目及每格的得分倍數,總得分為倍數乘這個格裡數的積,求出 最高的得分。 解題思路: 數獨的解法就是搜索。所以本題就是對搜索的優化。 (去年我直接深搜得四十分) 因此可見,本題得一些分其實是相對容易的。當把這些分得來先。 優化一: 搜索優化一般是剪枝,但這題不太容易得出剪枝的方法。

一個不錯的優化是改變一下搜索順序。因為有些格可填的數字少,先搜這些 格會使搜索樹小很多。 但是, 如果每一步搜索都要找一找下一個格子的話就太費 時間了,效率甚至會不如樸素的搜索。因此不能這樣來做。 所以,只能預處理一下順序。我們可以假設一個理想化的情況:假設一個格 子填入數字後, 必然對同一行、 同一列和同一大格中的空格造成影響。 也就是說, 不能做到精確的計算。但總能估計一個大概的「受影響程度」。 因此就可以讓每步填好的格子對其週圍的格子「影響」一次(即增加它們的 「受影響度」),然後選取下一步的格子。如此重複,直至選取完所有的空格。 按照這個順序來搜,大約可得七十五分。 優化二: 搜索現在還慢在每一步的判斷上。這裡也是可以優化的。 一般的判斷是看這一格子所在的行、 列和大格共二十個格子裡的數是否有與 該格的數相同的。如果能預先知道該行、該列或該大格已經填入了哪些數字,就 可以免掉很多時間。 仿照八皇后問題的優化算法。 可以建立三個 bool 數組: plr[i][k]、 plc[i][k] 及 plg[i][j][k], 分別表示第 i 行、第 i 列及從向第 i 個橫向第 j 個大格內數 k 有未被填過。 這樣搜索衹要看該數組判斷就可以了。注意遞迴和回溯時要更新這 幾個數組的狀態。 這樣的話應該就可以 AC 了。(最后一個數據我做到 1.95 秒) 另外,效法八皇后問題,這題也可以用位運算來解決,非常快。二十組數據 每組都能一秒內出解。 建議時間: 40-60 分鐘 簡單數據的分很易得, 樸素深搜一定要先寫出來。 優化不是很容易, 盡量做。 最好是多優化一下前面幾道題的程序,它們的優化比這道題容易一些,仍有時間 的話再來考慮這道題的優化。 總結: 這套題得高分不太容易, 但只要把程序都寫正確了,稍加些優化就能得大約 一半的分(我去年得一百九十分)。這也是很高的分數。因此,「正確」是關鍵 所在。這套題不必要冒太大險的。

程序範例: spy.cpp #include <iostream> #include <fstream> #include <string> using namespace std; ifstream fin("spy.in"); ofstream fout("spy.out"); string s1,s2,s3; char d1[26],d2[26]; int main(){ fin>>s1>>s2>>s3;

for(int i=0;i<s1.length();i++){ if(!d1[s1[i]-'A']){ if(!d2[s2[i]-'A']){ d1[s1[i]-'A']=s2[i]; d2[s2[i]-'A']=s1[i]; }else{ fout<<"Failed\n"; return 0; } }else if(d1[s1[i]-'A']!=s2[i]){ fout<<"Failed\n";

return 0; } }

for(int i=0;i<26;i++){ if(!d1[i]){ fout<<"Failed\n"; return 0; } }

for(int i=0;i<s3.length();i++){ fout<<d1[s3[i]-'A']; } fout<<'\n';

fin.close(); fout.close();

return 0; } son.cpp #include <iostream> #include <fstream>

#include <bitset> #include <cstdlib> using namespace std; ifstream fin("son.in"); ofstream fout("son.out"); int n; int a0,a1,b0,b1; int pri[6000]; int prn; int s; inline void init(){ bitset<50004> npr; for(int i=2;i<=50000;i++){ if(!npr[i]){ pri[prn++]=i; for(int j=i+i;j<=50000;j+=i){ npr[j]=1; } } } } inline bool judge(int x){ int ea0=0,ea1=0,eb0=0,eb1=0; while(a0%x==0){ea0++;a0/=x;}

while(a1%x==0){ea1++;a1/=x;} while(b0%x==0){eb0++;b0/=x;} while(b1%x==0){eb1++;b1/=x;} if(ea0==ea1){ if(eb0==eb1){ if(eb1>=ea1){ s*=eb1-ea1+1; return 1; }else{ return 0; } }else{ if(eb1<ea1){ return 0; } } }else{ if(eb0==eb1){ if(ea1>eb1){ return 0; } }else{ if(ea1!=eb1){ return 0;

} } } return 1; } inline int core(){ s=1; for(int i=0;pri[i]*pri[i]<=a0;i++){ if(a0%pri[i]==0&&!judge(pri[i]))return 0; } if(a0!=1){ if(!judge(a0))return 0; } for(int i=0;pri[i]*pri[i]<=b1;i++){ if(b1%pri[i]==0&&!judge(pri[i]))return 0; } if(b1!=1){ if(!judge(b1))return 0; } return s; } int main(){ init(); fin>>n;

for(int i=0;i<n;i++){ fin>>a0>>a1>>b0>>b1; fout<<core()<<'\n'; } return 0; } trade.cpp #include <iostream> #include <fstream> #include <cstring> using namespace std; ifstream fin("trade.in"); ofstream fout("trade.out"); struct Edge{ int v; Edge *next; }; int n,m; int price[100004]; Edge *path[100004],*rpath[100004]; int buy[100004],sell[100004]; inline void input(){ fin>>n>>m; for(int i=1;i<=n;i++){

fin>>price[i]; } int x,y,z; for(int i=1;i<=m;i++){ fin>>x>>y>>z; Edge *p=new Edge; p->v=y; p->next=path[x]; path[x]=p; p=new Edge; p->v=x; p->next=rpath[y]; rpath[y]=p; if(z==2){ p=new Edge; p->v=x; p->next=path[y]; path[y]=p; p=new Edge; p->v=y; p->next=rpath[x]; rpath[x]=p; } }

} int ma(int a,int b){ return a>b?a:b; } int mi(int a,int b){ return a<b?a:b; } void spfa(int st,int f[],Edge *pa[],int cmp(int,int)){ int q[200004]; bool inq[100004]; int be=0,en=1; for(int i=1;i<=n;i++){ f[i]=-1; inq[i]=0; } f[st]=price[st]; q[0]=st; inq[st]=1; while(be!=en){ int cv=q[be++]; if(be==n+1)be=0; for(Edge *p=pa[cv];p;p=p->next){ int tcm=cmp(f[cv],price[p->v]); if(f[p->v]==-1||cmp(tcm,f[p->v])!=f[p->v]){

f[p->v]=tcm; if(!inq[p->v]){ inq[p->v]=1; q[en++]=p->v; if(en==n+1)en=0; } } } inq[cv]=0; } } inline void output(){ int ans=0; for(int i=1;i<=n;i++){ if(buy[i]!=-1&&sell[i]!=-1){ if(sell[i]-buy[i]>ans){ ans=sell[i]-buy[i]; } } } fout<<ans<<endl; } int main(){ input();

spfa(1,buy,path,mi); spfa(n,sell,rpath,ma); output(); return 0; } sudoku.cpp #include <iostream> #include <fstream> using namespace std; ifstream fin("sudoku.in"); ofstream fout("sudoku.out"); int num[9][9]; int aff[9][9]; bool baf[9][9]; int ord[81][2]; int orn; bool plr[9][10]; bool plc[9][10]; bool plg[3][3][10]; int ans=-1; inline void input(){ for(int i=0;i<9;i++){ for(int j=0;j<9;j++){ fin>>num[i][j];

if(num[i][j]){ baf[i][j]=1; plr[i][num[i][j]]=1; plc[j][num[i][j]]=1; plg[i/3][j/3][num[i][j]]=1; } } } } inline void affe(int r,int c){ for(int i=0;i<9;i++){ aff[r][i]++; aff[i][c]++; } for(int i=0;i<3;i++){ for(int j=0;j<3;j++){ if((r/3)*3+i==r||(c/3)*3+j==c)continue; aff[(r/3)*3+i][(c/3)*3+j]++; } } } inline void init(){ for(int i=0;i<9;i++){ for(int j=0;j<9;j++){

if(!baf[i][j])continue; affe(i,j); } } for(;;){ int mi=-1,mj=-1; for(int i=0;i<9;i++){ for(int j=0;j<9;j++){ if(baf[i][j])continue; if(mi==-1||aff[i][j]>aff[mi][mj]){ mi=i; mj=j; } } } if(mi==-1)break; ord[orn][0]=mi; ord[orn][1]=mj; orn++; baf[mi][mj]=1; affe(mi,mj); } } inline int ab(int x){

return x>=0?x:-x; } inline int ma(int a,int b){ return a>b?a:b; } inline void update(){ int s=0; for(int i=0;i<9;i++){ for(int j=0;j<9;j++){ s+=num[i][j]*(10-ma(ab(i-4),ab(j-4))); } } if(s>ans){ ans=s; } } inline void dfs(){ #define CN(d) (num[ord[d][0]][ord[d][1]]) CN(0)=10; int d=0; while(d>=0){ CN(d)--; if(CN(d)==0){ d--;

plr[ord[d][0]][CN(d)]=0; plc[ord[d][1]][CN(d)]=0; plg[ord[d][0]/3][ord[d][1]/3][CN(d)]=0; continue; } if(plr[ord[d][0]][CN(d)]==1)continue; if(plc[ord[d][1]][CN(d)]==1)continue; if(plg[ord[d][0]/3][ord[d][1]/3][CN(d)]==1)continue; if(d==orn-1){ update(); }else{ plr[ord[d][0]][CN(d)]=1; plc[ord[d][1]][CN(d)]=1; plg[ord[d][0]/3][ord[d][1]/3][CN(d)]=1; d++; CN(d)=10; } } #undef CN } inline void output(){ fout<<ans<<endl; } int main(){

input(); init(); dfs(); output();

return 0; } 附:sudoku 位運算版 sudoku-bin.cpp #include <iostream> #include <fstream> using namespace std; ifstream fin("sudoku.in"); ofstream fout("sudoku.out"); int num[9][9]; int aff[9][9]; bool baf[9][9]; int ord[81][2]; int orn; int plr[9]; int plc[9]; int plg[3][3]; int ans=-1; inline void input(){

for(int i=0;i<9;i++){ for(int j=0;j<9;j++){ fin>>num[i][j]; if(num[i][j]){ baf[i][j]=1; plr[i]|=(1<<(num[i][j]-1)); plc[j]|=(1<<(num[i][j]-1)); plg[i/3][j/3]|=(1<<(num[i][j]-1)); } } } } inline void affe(int r,int c){ for(int i=0;i<9;i++){ aff[r][i]++; aff[i][c]++; } for(int i=0;i<3;i++){ for(int j=0;j<3;j++){ if((r/3)*3+i==r||(c/3)*3+j==c)continue; aff[(r/3)*3+i][(c/3)*3+j]++; } } }

inline void init(){ for(int i=0;i<9;i++){ for(int j=0;j<9;j++){ if(!baf[i][j])continue; affe(i,j); } } for(;;){ int mi=-1,mj=-1; for(int i=0;i<9;i++){ for(int j=0;j<9;j++){ if(baf[i][j])continue; if(mi==-1||aff[i][j]>aff[mi][mj]){ mi=i; mj=j; } } } if(mi==-1)break; ord[orn][0]=mi; ord[orn][1]=mj; orn++; baf[mi][mj]=1; affe(mi,mj);

} } inline int ab(int x){ return x>=0?x:-x; } inline int ma(int a,int b){ return a>b?a:b; } inline void update(){ int s=0; for(int i=0;i<9;i++){ for(int j=0;j<9;j++){ s+=num[i][j]*(10-ma(ab(i-4),ab(j-4))); } } if(s>ans){ ans=s; } } inline int getnum(int x){ switch(x){ case 1:return 1; case 2:return 2; case 4:return 3;

case 8:return 4; case 16:return 5; case 32:return 6; case 64:return 7; case 128:return 8; case 256:return 9; } } #define CN num[ord[d][0]][ord[d][1]] void dfs_bin(int d){ int pos=(~((plr[ord[d][0]])|(plc[ord[d][1]])|(plg[ord[d][0]/3][ord[d][1]/ 3])))&((1<<9)-1); while(pos){ int p=pos&(-pos); CN=getnum(p); if(d==orn-1){ update(); }else{ plr[ord[d][0]]|=p; plc[ord[d][1]]|=p; plg[ord[d][0]/3][ord[d][1]/3]|=p; dfs_bin(d+1); plr[ord[d][0]]-=p;

plc[ord[d][1]]-=p; plg[ord[d][0]/3][ord[d][1]/3]-=p; } pos-=p; } } #undef CN inline void output(){ fout<<ans<<endl; } int main(){ input(); init(); dfs_bin(0); output();

return 0; }


赞助商链接
相关文章:
2011noip提高组复赛题解
2011noip提高组复赛题解_学科竞赛_高中教育_教育专区。Noip 2011 提高组 (Day 1) 解题报告及程序 一、铺地毯 正着扫一遍 判断每个矩形是否覆盖询问的点,覆盖则...
NOIP2008提高组复赛试题及题解
NOIP2008提高组复赛试题及题解_IT认证_资格考试/认证_教育专区。noip历届复赛试题...NOIP2006提高组复赛解题... NOIP2007提高组解题报告 NOIP2009提高组复赛题解 NO...
NOIP2015提高组解题报告
NOIP2015提高组解题报告_学科竞赛_高中教育_教育专区。NOIP2015提高组的解题报告,有详细的算法和代码 NOIP2015 提高组解题报告 T1 神奇的幻方【题目大意】 告诉你...
NOIP2009提高组解题报告
NOIP2009提高组复赛题解 12页 1财富值 NOIP2008提高组解题报告 13页 免费 noip2009提高组解题报告(C... 10页 1财富值如要投诉违规内容,请到百度文库投诉中心;...
历届noip提高组复赛试题
历届noip提高组复赛试题_学科竞赛_高中教育_教育专区...//drs.126.com 三小时完成 题一 神经网络 【问题...n<=1000 twostack.out acabbd 2009 年 潜伏者 R...
NOIP2009提高组C++初赛试题与答案
NOIP2009提高组C++初赛试题与答案_学科竞赛_高中教育_教育专区。2009 第十五届...写在试卷纸上一律无效 一. 单项选择题 (共 10 题,每题 1.5 分,共计 15 ...
NOIP2009提高组初赛试题及答案
NOIP2009提高组初赛试题及答案_学科竞赛_初中教育_教育专区。第十五届全国青少年...写在试卷纸上一律无效 一. 单项选择题 (共 10 题,每题 1.5 分,共计 15 ...
NOIP2016提高组复赛试题(Day1+Day2)
NOIP2016提高组复赛试题(Day1+Day2)_IT/计算机_...(earthworm) 【问题描述】本题中,我们将用符号 LcJ...2.09 7.46 7.86 5.77 7.44 8.24 6.72 ...
NOIP2009初赛试题及参考答案和解析(提高组)C++
在参加 NOI 系列竞赛过程中,下面哪些行为是被严格禁止的: A) 携带书写工具,...NOIP2009 初赛 提高组 C++ 3 三.问题求解(共 2 题,每空 5 分,共计 10 ...
NOIP历年复赛提高组试题(2004-2013)
NOIP历年复赛提高组试题(2004-2013)_学科竞赛_高中教育...输入文件 equal.in 的第一行给出的是题干中的...(NOIP2009)复赛试题(提高组 竞赛用时:3 小时) 一...
更多相关标签: