NOIP提高組 1999 & 2000 題解合集

【序言】話說我在學神奇算法的時候，基礎應該也要鞏固，於是打算提前把NOIP提高組的刷完。

具體的題目描述和提交我就在VIJOS上完成。

【1999.1】

描述

給定一個信封，最多只允許粘貼N張郵票，計算在給定M（N+M<=10）種郵票的情況下（假定所有的郵票數量都足夠）,如何設計郵票的面值，能得到最大max ，使得1～max之間的每一個郵資值都能得到。

例如，N=3，M＝2，如果面值分別為1分、4分，則在l分～6分之間的每一個郵資值都能得到（當然還有8分、9分和12分）：如果面值分別為1分、3分，則在1分～7分之間的每一個郵資值都能得到。可以驗證當N=3，M＝2時，7分就是可以得到連續的郵資最大值，所以MAX=7，面值分別為l分、3分。

樣例輸入：共一行，兩個整數，分表為N與M的值。

格式

輸入格式

一行，分別為N,M。

輸出格式

兩行。

第一行為m種郵票的面值，按升序排列，各數之間用一個空格隔開。

第二行為最大值。

如果有多解，輸出字典序最大的一個。

樣例1

樣例輸入1

3 2

樣例輸出1

1 3
MAX=7

限制

各個測試點1s

來源

NOIP1999

【分析】似乎很早很早以前做到過~那時候因為不太懂各種算法，就亂搞搞過去了。但是現在思維復雜起來了，時間效率考慮的太多，反而難以下手。開始想的是貪心，發現是有問題的。數據范圍N+M<=10，那麼我們果斷爆搜。在爆搜的途中如何隨時更新值？只能用背包了。1A。

【代碼】

#include
#include
#include
using namespace std;
const int maxn=605;
int n,m,Max,i,a[15],ans[15],f[maxn];
int dp(int x)
{
  memset(f,63,sizeof(f));
  f[0]=0;int i,j;
  for (i=1;i<=maxn;i++)
  {
	for (j=1;j<=x;j++)
	  if (i-a[j]>=0) f[i]=min(f[i-a[j]]+1,f[i]);
	if (f[i]>n) break;
  }
  return i-1;
}
void dfs(int step)
{
  int now=dp(step);
  if (step==m)
  {
	if (now>Max) Max=now,memcpy(ans,a,sizeof(a));
	return;
  }
  for (int i=now+1;i>a[step];i--)
  {
	a[step+1]=i;
	dfs(step+1);
  }
}
int main()
{
  scanf("%d%d",&n,&m);
  a[1]=1;Max=0;
  dfs(1);
  for (i=1;i<=m;i++)
    printf("%d ",ans[i]);
  printf("\nMAX=%d",Max);
  return 0;
}

【1999.2】

描述

一個旅行家想駕駛汽車以最少的費用從一個城市到另一個城市(假設出發時油箱是空的)。給定兩個城市之間的距離d1、汽車油箱的容量c（以升為單位）、每升汽油能行駛的距離d2、出發點每升汽油價格p和沿途油站數n，油站i離出發點的距離d[i]、每升汽油價格p[i]。

計算結果四捨五入至小數點後兩位。

如果無法到達目的地，則輸出-1。

格式

輸入格式

輸入共n+1行，第一行為d1,c,d2,p,n，以下n行，每行兩個數據，分別表示該油站距出發點的距離d[i]和該油站每升汽油的價格p[i]。兩個數據之間用一個空格隔開。

輸出格式

1 <= n <= 100

樣例1

樣例輸入1

275.6 11.9 27.4 2.8 2
102.0 2.9
220.0 2.2

樣例輸出1

26.95

限制

1s

提示

0<=n<=100

【分析】開始還以為是DP，仔細一想是貪心。因為細節沒處理好，後來還下載數據調試= =。

策略：主要是采用搜索的框架（但是其實不是，每層只有一個點在操作）設當前到達的點是K。

①對於K能到的點中，找到第一個油費比K小的點P。若能找到，跳到②；否則跳到⑤。

②加上剛好去P的油，累加答案，並來到P這個狀態。跳到①。

③說明在能到達的點中，K的油費最小。跳到④。

④判斷K能否直接到達終點，若能累加答案並退出，否則跳到⑤。

⑤找到K能到達的點中油費最小的點，同時加滿油駛向P。若已經沒有點了，輸出-1，否則跳到①。

但是很遺憾，還有一個小的問題：我們還要記錄一下當前所剩的油量Q。以上過程都要涉及Q。

【代碼】

#include
using namespace std;
double dis,c,speed,cost[105],X,COST,x[105],ans;
int N,i,n;
bool flag;
void walk(int k,double now)
{
  if (x[k]+speed*c=x[i];i++)
    if (cost[i]=need) walk(i,now-need);
	  else ans+=(need-now)*cost[k],walk(i,0);
	  return;
    }
  if (x[k]+speed*c>=dis) 
  {
	flag=1;
	double need=(dis-x[k])/speed;
	if (now=x[i];i++)
    if (cost[i]

1999的其它兩題就不必說了吧~~~
【2000.1】





背景

JerryZhou同學經常改編習題給自己做。
這天，他又改編了一題。。。。。




描述

設有N*N的方格圖，我們將其中的某些方格填入正整數，

而其他的方格中放入0。
某人從圖得左上角出發，可以向下走，也可以向右走，直到到達右下角。
在走過的路上，他取走了方格中的數。（取走後方格中數字變為0）

此人從左上角到右下角共走3次，試找出3條路徑，使得取得的數總和最大。




格式

輸入格式

第一行:N (4<=N<=20)

接下來一個N*N的矩陣，矩陣中每個元素不超過80，不小於0

輸出格式

一行，表示最大的總和。





樣例1

樣例輸入1




4
1 2 3 4
2 1 3 4
1 2 3 4
1 3 2 4

樣例輸出1




39





限制

各個測試點1s




提示

多進程DP




【分析】其實原題是二取方格數，不過這樣更加可以練練手。DP的方法應該很熟練了，我就寫了些網絡流。太高興了，建圖自己就YY出來了。設超級源點S，與左上角連一條費用為0，流量為3的邊；設超級匯點T，與右下角連一條同樣的邊。能到達的兩點連一條流量為INF，費用為0的邊。然後把每個點拆成兩個，連一條流量為INF，費用為0的邊和一條流量為1，費用為權值的邊。流量的意義是路徑，費用的意義是價值。然後跑一遍最大費用最大流。
【代碼】

#include
#include
#include
#define N 45
#define V 1005
#define M 80005
#define INF 2139062144
using namespace std;
struct arr{int s,w,go,next;}a[M];
bool flag[V];
int f[V],q[M],pre[V],num[N][N][2],map[N][N],end[V];
int S,T,n,i,j,cnt,ans;
bool spfa()
{
  int h=0,t=1;
  memset(f,128,sizeof(f));
  memset(flag,0,sizeof(flag));
  f[S]=0;q[1]=S;flag[S]=true;
  while (hf[go])
      {
        f[go]=f[now]+a[i].w;pre[go]=i;
        if (!flag[go]) 
        {
          flag[go]=true;t++;q[t]=go;
        }
      }
    }
    flag[now]=false;
  }
  if (f[T]==-INF) return 0;return 1;
}
void cost()
{
  int sum=INF;
  for (int i=pre[T];i;i=pre[a[i^1].go])
  {
    sum=min(sum,a[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);
  }
}