当前位置：首页 -> 基础 -> c++编程基础

NOIP提高组 1999 & 2000 题解合集(二)

2014-11-24 12:38:42 · 作者: · 浏览: 1
标签: NOIP 提高 1999 & 2000 题解 合集
i].s); if (a[i^1].go==S) break; } for (int i=pre[T];i;i=pre[a[i^1].go]) { a[i].s-=sum; a[i^1].s+=sum; ans+=sum*a[i].w; if (a[i^1].go==S) break; } } void add(int u,int v,int s,int w) { a[++cnt].go=v;a[cnt].s=s;a[cnt].w=w;a[cnt].next=end[u];end[u]=cnt; a[++cnt].go=u;a[cnt].s=0;a[cnt].w=-w;a[cnt].next=end[v];end[v]=cnt; } int main() { scanf("%d",&n);S=T=0;cnt=1; for (i=1;i<=n;i++) for (j=1;j<=n;j++) scanf("%d",&map[i][j]),num[i][j][0]=++T,num[i][j][1]=++T; T++; for (i=1;i<=n;i++) for (j=1;j<=n;j++) { add(num[i][j][0],num[i][j][1],1,map[i][j]); add(num[i][j][0],num[i][j][1],INF,0); if (i

【2000.2】

描述

单词接龙是一个与我们经常玩的成语接龙相类似的游戏，现在我们已知一组单词，且给定一个开头的字母，要求出以这个字母开头的最长的“龙”（每个单词都最多在“龙”中出现两次），在两个单词相连时，其重合部分合为一部分，例如 beast和astonish，如果接成一条龙则变为beastonish，另外相邻的两部分不能存在包含关系，例如at 和 atide 间不能相连。

格式

输入格式

输入的第一行为一个单独的整数n (n<=20)表示单词数，以下n 行每行有一个单词，输入的最后一行为一个单个字符，表示“龙”开头的字母。你可以假定以此字母开头的“龙”一定存在.

输出格式

只需输出以此字母开头的最长的“龙”的长度

样例1

样例输入1 

5
at
touch
cheat
choose
tact
a

样例输出1 

23

限制

各个测试点1s

提示

连成的“龙”为atoucheatactactouchoose

来源

NOIP2000提高组第3题

【分析】开始还以为是DP，用f[i][j]表示连接了i个单词，且最后一个是j的最大长度，后来发现无法获知每个单词是否用过（状压DP ）。想了一会了，N<=20,果断搜索。先预处理两两单词的关系，然后爆搜~。1A。

【代码】

#include
              
               
#include
               
                 using namespace std; int sum[45][45],size[45],n,m,i,l,j,ans; bool flag[45]; char s[305],now[55],a[45][55]; int Do(int p,int q) { int ans=0; for (int i=1;i<=size[q];i++) { bool flag=1; for (int j=1;j<=i;j++) if (a[q][j]!=a[p][size[p]-i+j]) {flag=0;break;} if (flag) {ans=i;break;} } if (ans==size[q]) ans=0; return ans; } void solve(char *s,int l,int k) { char ss[305]; if (l>ans) ans=l; memcpy(ss,s,sizeof(s)); for (int i=1;i<=n*2;i++) if (!flag[i]&&sum[k][i]&&(sum[k][i]
                
                 【2000.3】 
                  
                  
                 
 背景
 
                 
NOIP2000 提高组第一题






 
                 
 描述
 
                 
我们可以用这样的方式来表示一个十进制数：将每个阿拉伯数字乘以一个以该数字所处位置的（值减1）为指数，以10为底数的幂之和的形式。例如，123可表示为1*10^2+2*10^1+3*10^0这样的形式。
 
                 
与之相似的，对二进制数来说，也可表示成每个二进制数码乘以一个以该数字所处位置的（值-1）为指数，以2为底数的幂之和的形式。一般说来，任何一个正整数R或一个负整数-R都可以被选来作为一个数制系统的基数。如果是以R或-R为基数，则需要用到的数码为0，1,....R-1。例如，当R=7时，所需用到的数码是0，1，2, 3，4，5和6，这与其是R或-R无关。如果作为基数的数绝对值超过10，则为了表示这些数码，通常使用英文字母来表示那些大于9的数码。例如对16进制数来说，用A表示10，用B表示11，用C表示12，用D表示13，用E表示14，用F表示15。在负进制数中是用-R作为基数，例如-15（＋进制）相当于110001（-2进制），
 并且它可以被表示为2的幂级数的和数：
 110001=1*(-2)^5+1*(-2)^4+0*(-2)^3+0*(-2)^2+0*(-2)^1+1*(-2)^0
 问题求解:
 设计一个程序，读入一个十进制数的基数和一个负进制数的基数，并将此十进制数转换为此负进制下的数：-R∈{-2，-3，-4,....-20}
 
                 
 格式
 
                 
输入格式
 
                 
输入文件有若干行，每行有两个输入数据。
 
                 
第一个是十进制数N（-32768<=N<=32767）; 第二个是负进制数的基数-R。
 
                 
输出格式
 
                 
输出此负进制数及其基数，若此基数超过10，则参照16进制的方式处理。【具体请参考样例】
 
                 
 样例1
 
                 
样例输入1 
 
                 
 
                  
30000 -2
-20000 -2
28800 -16
-25000 -16
 
                 
 
                 
样例输出1 
 
                 
 
                  
30000=1101101010111000(base -2)
-20000=1111011000100000(base -2)
28800=19180(base -16)
-25000=7FB8(base -16) 
 
                 
 
                 
 限制
 
                 
每个点1s。
 
                 
 提示
 
                 
每个测试数据不超过1000组。
 
                 
 来源
 
                 
From 玛维-影之歌
 NOIP2000原题
 
                 
【分析】说来惭愧，开始想的太复杂了=_=。当进制是负数时该怎么处理？开始想是枚举答案的位数，然后一步步的逼近~~真是麻烦。后来一拍脑袋，不是可以直接除吗？负数应该也满足整数的性质，只是除的时候要特判。1A。
 
                 
【代码】
 
                 
 
                 
#include
                  
                   
#include
                   
                     using namespace std; int DIV(int A,int B) { int ans=A/B; if (ans*B>A) (ans*B>0) ans--:ans++; return ans; } int main() { int a,p,n,t_a,i,ans[105]; while (scanf("%d%d",&a,&p)!=EOF) { n=0;printf("%d=",a); while (a!=0) { t_a=DIV(a,p); ans[++n]=a-t_a*p; a=t_a; } for (i=n;i;i--) printf("%c",(ans[i]<10) ans[i]+48:ans[i]+55); printf("(base %d)\n",p); } }