# 2009noip提高组复赛题解

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

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; }

2009noip提高组复赛题解.doc
2009noip提高组复赛题解_企业管理_经管营销_专业资料。NOIP2009
NOIP2009提高组复赛题解.doc
NOIP2009提高组复赛题解 - NOIP2009 提高组复赛题解(1) 20
2008noip提高组复赛题解.doc
2008noip提高组复赛题解_学科竞赛_高中教育_教育专区 暂无评价|0人阅读|0次下载|举报文档2008noip提高组复赛题解_学科竞赛_高中教育_教育专区。NOIP2008 提高组...
2008年noip提高组复赛题解.ppt
2008年noip提高组复赛题解_学科竞赛_高中教育_教育专区。2008年noi
1999-2009NOIP提高组复赛试题汇编.pdf
1999-2009NOIP提高组复赛试题汇编_IT/计算机_专业资料。1999-
NOIP2010提高组复赛试题及解题报告.doc
NOIP2010提高组复赛试题及解题报告 - NOIP2010 提高组复赛试题及解题报告 1.机器翻译 (translate.pas/c/cpp) 【问题描述】 小晨的电脑上安装了一个机器翻译软...
noip2017提高组复赛解题报告.doc
noip2017 提高组复赛解题报告 定期推送帐号信息学新闻...注:本题中为了书写方便,在描述复杂度时,使用大 写...NOIP2004提高组解题报告 8页 免费 NOIP2009提高组...

noip2009提高组解题报告(C语言).doc
Hankson 的趣味题 (son.pas/c/cpp) 【问题描述】 Hanks 博士是 BT(Bio-...NOIP2009提高组解题报告 5页 1下载券 NOIP2009提高组复赛题解 12页 1下载券...
IthneaNOIP2009提高组解题报告.doc
[原创]NOIP2009 提高组解题报告{继续供大牛 BS} 2009-11-21 10:46 P.M. ...NOIP2009提高组复赛题解 12页 1下载券 Noip 2003 提高组 解题报... 12页...
NOIP2011提高组复赛试题与简解(转载).doc
NOIP2011提高组复赛试题与简解(转载)_中考_初中教育_教育专区。NOIP2011提高组...威锋上果然有完全题解啊,第 14 关果然是样例啊有木有!!!人类智力威武, Orz...
NOIP2009年提高组(C语言)及参考答案.doc
NOIP2009提高组(C语言)及参考答案 - 第十五届全国青少年信息学奥林匹克联赛初赛试题 ( 提高组 ●● C 语言 二小时完成 )●● 全部试题答案均要求写在答卷纸...
NOIP2008 提高组试题.doc
NOIP2009提高组复赛题解 12页 1财富值 NOIP2009高中复赛试题

QfhygeNOIP2009提高组解题报告.doc
| 回复 悲剧了,第二题枚举竟然写错了 qyjubriskxp 4 网友:Lc 2009-11-22 ...NOIP2011解题报告 3页 1下载券 noip2010提高组复赛试题 7页 免费 B_station...
2011noip提高组复赛题解.doc
2011noip提高组复赛题解_学科竞赛_高中教育_教育专区。Noip 2011
NOIP2009_提高答案.doc
NOIP2009_提高答案 - 第十五届全国青少年信息学奥林匹克联赛初赛试题 ( 提高组 Pascal 语言 二小时完成 )○○ 全部试题答案均要求写在答卷纸上,写在试卷纸上一律...
NOIP2008提高组复赛试题及题解.doc
NOIP2008提高组复赛试题题解 - 全国信息学奥林匹克联赛(NOIP200
NOIP2009提高组初赛试题答案.doc

NOIP2010复赛提高组题解加程序.pdf
NOIP2010复赛提高组题解加程序 - esiotrot o- ++g ml-