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

2008noip提高组复赛题解
2008noip提高组复赛题解_学科竞赛_高中教育_教育专区 暂无评价|0人阅读|0次下载|举报文档2008noip提高组复赛题解_学科竞赛_高中教育_教育专区。NOIP2008 提高组...
2011noip提高组复赛题解
2011noip提高组复赛题解_学科竞赛_高中教育_教育专区。Noip 2011 提高组 (Day 1) 解题报告及程序 一、铺地毯 正着扫一遍 判断每个矩形是否覆盖询问的点,覆盖则...
NOIP2008提高组复赛试题及题解
NOIP2008提高组复赛试题题解 - 全国信息学奥林匹克联赛(NOIP2008)复赛 提高组 一、题目概览 中文题目名称 英文题目名称 可执行文件名 输入文件名 输出文件名 ...
NOIP2009提高组C++初赛试题与答案
NOIP2009提高组C++初赛试题与答案_学科竞赛_高中教育_教育专区。2009 第十五届...写在试卷纸上一律无效 一. 单项选择题 (共 10 题,每题 1.5 分,共计 15 ...

NOIP2015提高组解题报告
NOIP2015提高组解题报告_学科竞赛_高中教育_教育专区。NOIP2015提高组的解题报告,有详细的算法和代码 NOIP2015 提高组解题报告 T1 神奇的幻方【题目大意】 告诉你...
NOIP2010提高组复赛试题及解题报告
NOIP2010提高组复赛试题及解题报告 - NOIP2010 提高组复赛试题及解题报告 1.机器翻译 (translate.pas/c/cpp) 【问题描述】 小晨的电脑上安装了一个机器翻译软...
NOIP2016提高组复赛试题(Day1+Day2)
NOIP2016提高组复赛试题(Day1+Day2)_IT/计算机_...(earthworm) 【问题描述】本题中,我们将用符号 LcJ...2.09 7.46 7.86 5.77 7.44 8.24 6.72 ...
NOIP2014提高组复赛试题
CCF 全国信息学奥林匹克联赛(NOIP2014)复赛 提高组 day1 1.生活大爆炸版石头剪刀布 (rps.cpp/c/pas) 【问题描述】 石头剪刀布是常见的猜拳游戏:石头胜剪刀,...
NOIP2009提高组解题报告
NOIP2009提高组复赛题解 12页 1财富值 NOIP2008提高组解题报告 13页 免费 noip2009提高组解题报告(C... 10页 1财富值如要投诉违规内容,请到百度文库投诉中心;...