[最短路徑]USACO Silver09 找工作 jobhunt 解題報告

問題描述:
貝茜牛身無分文了，她正忙着找工作。農夫約翰知道這個情況，他想讓他的牛去周遊世界，於是他推行了一個規則：在他的牛到另 一個城市工作之前，她們只能在一個城市掙得 D （ 1 <= D <= 1,000 ）美元。不管怎樣，貝茜可以在別的城市工作過之後，再返回到某個城市，並在這個城市再掙 D 美元，她可以無限次數地這樣做。
貝茜牛的世界包括 P （ 1 <= P <= 150 ）條單向邊，這些邊連接着 C （ 2 <= C <= 220 ）個城市，城市按 1 到 C 的順序編號，貝茜牛目前正待在 S 城 (1 <= S <= C) 。單向邊 i 從城市 A_i 連到城市 B_i ，其中 1 <= A_i <= C; 1 <= B_i <= C ，在路上不花費任何代價。
爲了幫助貝茜，約翰授權它使用他的私人噴氣飛機服務。這項服務配置了 F 條航綫，每條航綫是由城市 J_i 到城市 K_i (1 <=J_i <= C; 1 <= K_i <= C) 的單向航綫，且在該航綫上的費用是 T_i( 1 <= T_i <= 50,000 ) 美元，如果貝茜牛手頭沒有現錢，它可以將來掙到錢之後再支付飛行費用。
只要它願意，貝茜可以隨時隨地選擇退出。不限時間，假定它所有去過的城市都能掙足 D 美元，最後貝茜最多能得到多少錢？如果這個數目沒有限制的話輸出 -1 。
程序名：jobhunt
輸入格式：
第1行：五個空格隔開的整數，D，P，C，F，S；
第2至P+1行：第i行包括兩個空格隔開的整數，表示從城市A_i到B_i有一條單向邊。
第P+2至P+F+1行：第P+i行包括三個空格隔開的整數，表示從城市J_i到T_i有一條單向航綫，費用是T_i。
輸入樣例：(jobhunt.in):
100 3 5 2 1
1 5
2 3
1 4
5 2 150
2 5 120
輸入樣例解釋：這個世界有5個城市，三條有向邊，和兩條飛行航綫，貝茜從城市1開始，在每個城市它能最多掙到100美元。
輸出格式：
只有一行，一個整數，表示在遵守規則的情況下，它最多能得到多少錢。
輸出樣例：(jobhunt.out):
250
輸出樣例解釋：貝茜能從城市1→城市5→城市2→城市3，最後共得到4*100 - 150 = 250美元。
「分析」
單源最短路問題，賺錢是負權，航費是正權，用SPFA處理負邊權即可。
「我的代碼」

#include "cstdio"
#include "iostream"
#include "cstdlib"
#include "queue"
using namespace std;
const int MAX=230;
int Map[MAX][MAX];
int dist[MAX];
int times[MAX];
bool flag[MAX];
const int MAXN=1000000000;
int D;//在每個城市最多掙得D美金
int P;//P條單向邊
int C;//C個城市
int F;//F個單項航線
int S;//源點
typedef queue QUEUE;
void init()
{
 scanf("%d %d %d %d %d\n",&D,&P,&C,&F,&S);
 for (int i=1;i<=C;i++)
  for (int j=1;j<=C;j++)
   Map[i][j]=MAXN;
 for (int i=1;i<=C;i++)
  Map[i][i]=0;
 for (int i=1;i<=P;i++)
 {
  int a,b;
  scanf("%d %d\n",&a,&b);
  Map[a][b]=-D;
 }
 for (int i=1;i<=F;i++)
 {
  int a,b,c;
  scanf("%d %d %d\n",&a,&b,&c);
  if(Map[a][b]==MAXN)
  {
   Map[a][b]=c-D;
  }
 }
 return;
}
QUEUE Q;
void SPFA()
{
 for (int i=1;i<=C;i++)
  dist[i]=MAXN,flag[i]=false,times[i]=0;
 dist[S]=-D;
 Q.push(S);
 int x;
 while(Q.size())
 {
  x=Q.front();
  Q.pop();
  flag[x]=false;
  for(int i=1;i<=C;i++)
  {
   int tmp=dist[x]+Map[x][i];
   if(tmpC)
     {
      printf("-1\n");
      return;
     }
    }
   }
  }
 }
 int Max=MAXN;
 for (int i=1;i<=C;i++)
  if(Max>dist[i])
   Max=dist[i];
 printf("%d\n",-Max);
 return;
}
int main()
{
 freopen("jobhunt.in","r",stdin);
 freopen("jobhunt.out","w",stdout);
 init();
 SPFA();
 return 0;
}

[二分查找]NOIP2011提高組：聰明的質檢員 qc 解題報告

【問題描述】

試題檢視：GoogleDocs

小 T 是一名質量監督員，最近負責檢驗一批礦產的質量。這批礦產共有 n 個礦石，從 1 到 n 逐一編號，每個礦石都有自己的重量 wi 以及價值 vi。檢驗礦產的流程是：

1、給定 m個區間[Li，Ri]；

2、選出一個參數 W；

3、對於一個區間[Li，Ri]，計算礦石在這個區間上的檢驗值 Yi ： 

若這批礦產的檢驗結果與所給標準值 S 相差太多，就需要再去檢驗另一批礦產。小 T 不想費時間去檢驗另一批礦產，所以他想通過調整參數 W 的值，讓檢驗結果儘可能的靠近標準值 S，即使得 S-Y的絕對值最小。請你幫忙求出這個最小值。

【輸入】

輸入文件 qc.in。

第一行包含三個整數n，m，S，分別表示礦石的個數、區間的個數和標準值。

接下來的n 行，每行2 個整數，中間用空格隔開，第i+1 行表示i 號礦石的重量wi 和價值vi 。

接下來的m 行，表示區間，每行2 個整數，中間用空格隔開，第i+n+1 行表示區間[Li,Ri]的兩個端點Li 和Ri。注意：不同區間可能重合或相互重疊。

【輸出】

輸出文件名爲qc.out。

輸出只有一行，包含一個整數，表示所求的最小值。

【輸入輸出樣例】

qc.in

5 3 15

1 5

2 5

3 5

4 5

5 5

1 5

2 4

3 3

qc.out

10

【輸入輸出樣例說明】

當W 選4 的時候，三個區間上檢驗值分別爲20、5、0，這批礦產的檢驗結果爲25，此時與標準值S 相差最小爲10。

【數據範圍】

對於10%的數據，有1≤n，m≤10；

對於30%的數據，有1≤n，m≤500；

對於50%的數據，有1≤n，m≤5,000；

對於70%的數據，有1≤n，m≤10,000；

對於100%的數據，有1≤n，m≤200,000，0 < wi, vi≤10^6，0 < S≤10^12，1≤Li≤Ri≤n。

 【分析】

本題的正解是二分W，從0～MaxW+1二分。計算Y時要先預處理，把所有大於W的礦石記錄下來，然後再計算每個區間的值。

二分結束後，找出Min{Get(Right)，Get(Left)}輸出即可。

【我的代碼】

#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <algorithm>
using namespace std;
int N,M;
long long S;
const int MAXN=200001;
int W[MAXN];
int V[MAXN];
int L[MAXN];
int Sum[MAXN];
int R[MAXN];
long long TV[MAXN];
int TN[MAXN];
  
void init()
{
    Sum[0]=0;
    cin>>N>>M>>S;
    for (int i=1;i<=N;i++)
    {
        cin>>W[i]>>V[i];
        Sum[i-1]=W[i];
    }
    for (int i=1;i<=M;i++)
        cin>>L[i]>>R[i];
    sort(Sum,Sum+N);
    Sum[N]=Sum[N-1]+1;
}

long long Get(int w)
{
    long long res=0;
    TV[0]=0;
    TN[0]=0;
    for (int i=1;i<=N;i++)
    {
        if(W[i]>=w)
        {
            TV[i]=TV[i-1]+V[i];
            TN[i]=TN[i-1]+1;
            continue;
        }
        else
        {
            TV[i]=TV[i-1];
            TN[i]=TN[i-1];
        }
    }
  
    for (int i=1;i<=M;i++)
    {
        int tl=L[i];
        int tr=R[i];
        long long Temp=(TN[tr]-TN[tl-1])*(TV[tr]-TV[tl-1]);
        res+=Temp;
    }
  
    return res;
}

long long Abs(long long t)
{
    if(t>0)
        return t;
    else
        return -t;
}

void dichotomy()
{
    int Right;
    int Left;
    for (Left=0,Right=N;Left+1<Right;)
    {
        long long Temp=Get(Sum[(Right+Left)/2]);
        if(Temp>=S)
            Left=(Left+Right)/2;
        else
            Right=(Left+Right)/2;
    }
  
    long long TW1,TW2;
    TW1=Abs(Get(Sum[Right])-S);
    TW2=Abs(Get(Sum[Left])-S);
    if(TW2<TW1)
    {
        TW1=TW2;
    }
    cout<<TW1<<endl;
}  

int main()
{
    freopen("qc.in","r",stdin);
    freopen("qc.out","w",stdout);
    init();
    dichotomy();
    return 0;
}

動態規劃練習題：填加號 解題報告

【問題描述】
有一個由數字 1 ， 2 ， … ， 9 組成的數字串（長度不超過 200 ），問如何將 M(M<=20) 個加號 (“+”) 插入到這個數字串中，使所形成的算術表達式的值最小。請編一個程序解決這個問題。 注意： 加號不能加在數字串的最前面或最末尾，也不應有兩個或兩個以上的加號相鄰。 M 保證小於數字串的長度。 例如：數字串 79846 ，若需要加入兩個加號，則最佳方案為 79+8+46 ，算術表達式的值 133 。
【輸入格式】
數字串在輸入文件的第一行行首（數字串中間無空格且不折行），Ｍ的值在輸入文件的第二行行首。
【輸出格式】
輸出所求得的最小和的精確值。
【輸入輸出樣例】

輸入：
exam4.in
82363983742
3
輸出：
exam4.out
2170

【分析】
動態規劃，類似於『NOIP2000 乘積最大』。
狀態設定：
F[i,j] ：前i個數添加j個乘號的最小和
Num[i,j]：原數中第i個數到第j個數組成的新數。
邊界狀態：F[i,0]=Num[1,i]
狀態轉移方程： F[i,j]=Min{F[k,j-1]+Num[k+1,i]}
目標狀態：F[N,K]
由於數據比較大，所以需要高精度計算。

【我的代碼】

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
using namespace std;
const int SIZE=201;
int K;
int N;
typedef unsigned short int usint;
struct hugeint
{
 usint len,num[SIZE];
};
hugeint Num[201][201];
hugeint F[201][21];
void print(hugeint a)
{
 int i;
 for (i=a.len;i>=1;i--)
  printf("%d",a.num[i]);
 printf("\n");
}
hugeint add(hugeint a,hugeint b)
{
 int i;
 hugeint ans;
 memset(ans.num,0,sizeof(ans.num));
 if (a.len>b.len)
  ans.len=a.len;
 else
  ans.len=b.len;
 for (i=1;i<=ans.len;i++)
 {
  ans.num[i]+=(a.num[i]+b.num[i]);
  ans.num[i+1]+=ans.num[i]/10;
  ans.num[i]%=10;
 }
 if (ans.num[ans.len+1]>0)
  ans.len++;
 return ans;
}
bool over(hugeint a,hugeint b)
{
 int i;
 if (a.len<b.len)
  return false;
 if (a.len>b.len)
  return true;
 for (i=a.len;i>=1;i--)
 {
  if (a.num[i]<b.num[i])
   return false;
  if (a.num[i]>b.num[i])
   return true;
 }
 return false;
}
void init()
{
 hugeint tmp;
 memset(tmp.num,0,sizeof(tmp.num));
 char str[201];
 scanf("%s\n%d\n",&str,&K);
 int len=strlen(str);
 tmp.len=len;
 N=len;
 for (int i=0;i<len;i++)
 {
  tmp.num[i+1]=str[i]-'0';
 }
 for (int i=1;i<=len;i++)
 {
  for (int j=i;j<=len;j++)
  {
   memset(Num[i][j].num,0,sizeof(Num[i][j].num));
   Num[i][j].len=j-i+1;
   int top=Num[i][j].len;
   for (int k=i;k<=j;k++)
   {
    Num[i][j].num[top]=tmp.num[k];
    top--;
   }
   /*
   printf("%d %d %d ",i,j,Num[i][j].len);
   print(Num[i][j]);
   */
  }
 }
}
void dynamic()
{
 for (int i=1;i<=N;i++)
  F[i][0]=Num[1][i];
 for (int j=1;j<=K;j++)
 {
  for (int i=1;i<=N;i++)
  {
   for (int k=1;k<=N;k++)
    F[i][j].num[k]=9;
   F[i][j].len=N;
   for (int k=1;k<=i-1;k++)
   {
    hugeint temp=add(F[k][j-1],Num[k+1][i]);
    if(over(F[i][j],temp) )
    {
     F[i][j]=temp;
    }
   }
  }
 }
 print(F[N][K]);
}
int main()
{
 freopen("exam4.in","r",stdin);
 freopen("exam4.out","w",stdout);
 init();
 dynamic();
 return 0;
}

[動態規劃]OI練習題：乘法問題 [chf] 解題報告

【問題描述】
設有一個長度為 N 的數字字元串，分成 K+1 個部分，使得 K+1 個部 分的乘積最大。 例如 N=6 ，且數字字元串為 ‘ 310143 ‘ ， K=3. 此時可能有的情況有以 下各種：
3 ＊ 1 ＊ 0 ＊ 143=0
3 ＊ 1 ＊ 01 ＊ 43=129
3 ＊ 1 ＊ 014 ＊ 3=126
3 ＊ 10 ＊ 1 ＊ 43=1290
3 ＊ 10 ＊ 14 ＊ 3=1260
3 ＊ 101 ＊ 4 ＊ 3=3636
31 ＊ 0 ＊ 1 ＊ 43=0
31 ＊ 01 ＊ 4 ＊ 3=372
310 ＊ 1 ＊ 4 ＊ 3=3720
問題：當 N ，數字串， K 給出之後，找出一種分法使其乘積最大。
【輸入格式】
輸入由兩行組成，第一行有兩個整數，n（1≤n≤30）、k（1≤n≤30）；n表示數字串長度、k表示乘號

個數。第二行是數字串。
【輸出格式】
輸出為一個整數，為乘積最大值。
【輸入樣例】
輸入文件名：chf.in
9 4
321044105
輸出文件名：chf.out
5166000
【分析】
動態規劃，和『NOIP2001 乘積最大』一樣。
狀態設定：
F[i,j]：前i個數字添加j個乘號時的最大值。
Num[i,j]：第i的數到第j個的數組成的數，可以在DP前用一個O(N^2)的預處理求出。
狀態轉移方程：
F[i,j]=Max(F[k,j-1]*Num[k+1][i])  (1<=k<=i-1)
目標狀態：  F[N,K]
時間複雜度：O(2*N^2)

【我的代碼】

#include <iostream> #include <cstdio> #include <cstdlib> #include <cstring> using namespace std; typedef long long LL; LL N,K; LL num[100][100]; LL F[100][100];   LL Max(LL a,LL b) { if (a>=b) return a; return b; }   LL myatoi(char *str) { LL ret=0; LL sign=1; if(*str=='-') sign=-1; else ret=ret*10+(*str-'0'); str++;   while(*str!= '\0') { ret=ret*10+(*str-'0'); str++; } return sign*ret; }   void init() { cin>>N>>K; char Temp[100]; cin>>Temp; char tmp[100]; for (unsigned int i=1;i<=strlen(Temp);i++) { for (unsigned int j=i;j<=strlen(Temp);j++) { unsigned int ti=i-1; unsigned int tj=j-1; memset(tmp,'\0',sizeof(tmp)); for (unsigned int k=ti;k<=tj;k++) tmp[k-ti]=Temp[k]; num[i][j]=myatoi(tmp); } } }   void dp() { for (int i=1;i<=N;i++) F[i][0]=num[1][i]; for (int j=1;j<=K;j++) { for (int i=1;i<=N;i++) { F[i][j]=0; for (int k=1;k<=i-1;k++) F[i][j]=Max(F[i][j],F[k][j-1]*num[k+1][i]); } } cout<<F[N][K]<<endl; }   int main() { freopen("chf.in","r",stdin); freopen("chf.out","w",stdout); init(); dp(); return 0; }

USACO Dec2011 Bronze: Escaping the Farm 翻譯+題解

Problem 3: Escaping the Farm [Brian Dean and Kalki Seksaria, 2011]
【英文原題】
The cows have decided on a daring plan to escape from the clutches of
Farmer John. They have managed to procure a small inflatable raft, and
during the cover of night, a group of cows will board the raft and row
across the river bordering the farm. The plan seems perfect, until the
cows realize that their small inflatable raft may not be able to hold
much weight!
The N cows (1 group of cows is light enough to avoid sinking the raft, the cows add up
all of the weights in the group. Unfortunately, cows are notoriously bad at
arithmetic, and if the addition of the weights of the cows in a group
causes any carries to occur (using standard base 10 addition), then the
cows give up and conclude that group must weigh too much to use the raft.
Any group whose weights can be added without any carries is assumed to be
light enough to fit on the raft.
Please help the cows determine the size of the largest group that they
believe can fit on the raft (that is, the largest group whose weights can
be added together with no carries).
PROBLEM NAME: escape
INPUT FORMAT:
* Line 1: The number of cows, N (1
* Lines 2..N+1: Each line contains the weight of one cow, an integer
in the range 1…100,000,000.
SAMPLE INPUT (file escape.in):
5
522
6
84
7311
19
INPUT DETAILS:
There are 5 cows, with weights 522, 6, 84, 7311, and 19.
OUTPUT FORMAT:
* Line 1: The number of cows in the largest group whose weights can be
added together with no carries.
SAMPLE OUTPUT (file escape.out):
3
OUTPUT DETAILS:
The three weights 522, 6, and 7311, can be added together with no carries:
522
6
+ 7311
——
7839

【中文翻譯】

Problem 3:逃離農場
譯by Freddy
【題目描述】
奶牛們做了一個魯莽的計劃：那就是逃離農場主Farmer John。她們已經獲得了一個可充氣的小型木筏，計劃在某天夜晚中，一群奶牛通過使用木筏渡而過位於農場邊界的河流。這個計劃似乎很完美，直到奶牛們意識到她們的小木筏可能不能承受住她們的體重。

這N頭奶牛(1<=N<=20)的體重w_1…w_N。為了計算出一群奶牛的體重能否避免木筏沉沒的悲劇，一群奶牛把她們的體重加在一起。
不幸的是，奶牛們在算術方面臭名遠揚，並且一群奶牛內的各奶牛體重相加的過程中如果出現了進位（標準的10進制），那麼這群奶牛只好放棄因為她們知道她們的體重對於小木筏來說太重了。

所有 那些群內奶牛體重相加不出現進位的奶牛群都被認為可以乘坐那個木筏而不發生沉沒。

請幫奶牛們找出能乘坐木筏而不沉沒的奶牛群的最大奶牛數。（也就是說，找出最多的奶牛使她們的體重相加而不出現進位。）

程序名：escape
輸入格式：
▪第1行：奶牛的數量，N(1<=N<=20)
▪第2…N+1行：每行包含一頭奶牛的體重，一個整數(1…100,000,000)。
輸入樣例(file escape.in)：
5
522
6
84
7311
19
輸入解釋：
有5只奶牛，她們的體重分別為522，6，84，7311和19。
輸出格式：
只有一行，表示一群使她們的體重相加而不出現進位的奶牛的最大奶牛數量。
輸出樣例（file escape.out）：
3
輸出解釋：



這三個奶牛的體重分別為：522，6，7311，它們相加不會出現進位：
    522
       6
+7311
 ——–
  7839

【分析】
搜索題目，可以用DFS。遞歸每頭牛的兩種狀態：要或者不要，每次遞歸判斷一下是否符合要求（沒有進位），然後更新最優值即可。
時間複雜度:
DFS遞歸：O(2^N)
判斷：O(KN) 『K是讀入的數字的平均長度，根據題意，可取5～6』

【我的代碼】

/*
ID:yeefan
LANG:C++
PROB:escape
website:http://yeefan.tk/
*/
#include <cstdio>
#include <iostream>
#include <cstdlib>
#include <cstring>
using namespace std;
int N;
int W[21];
int A=0;
int Q[21];
int Best=0;
void init()
{
 scanf("%d\n",&N);
 for (int i=1;i<=N;i++)
  scanf("%d\n",&W[i]);
 return;
}
void check()
{
 int T[11];
 memset(T,0,sizeof(T));
 for(int i=1;i<=A;i++)
 {
  int K=1;
  int tmp=W[Q[i]];
  while(tmp!=0)
  {
   T[K]+=tmp%10;
   tmp/=10;
   K++;
  }
 }
 for(int i=1;i<=10;i++)
 {
  if(T[i]>=10)
   return;
 }
 if(A>Best)
  Best=A;
}
void dfs(int num)
{
 if(num==N+1)
 {
  check();
  return;
 }
 Q[++A]=num;
 dfs(num+1);
 A--;
 dfs(num+1);
}
int main()
{
 freopen("escape.in","r",stdin);
 freopen("escape.out","w",stdout);
 init();
 dfs(1);
 printf("%d\n",Best);
 //printf("%d\n",clock());
 return 0;
}

【精華轉載】因為我們是OIer！

我們是OIer，

所以我們
不用在跑道上揮汗如雨；
不用在球場上健步如飛；
更不用在沒事的時候，
經受非人的體能訓練……
但是，
我們卻要把頭腦
高速運轉，
還要接受一大堆
大學生也只是
“瞭解即可”的知識，
把一個個抽象的問題
轉化為一篇篇
優美的代碼，
才能在F9按下以後
獲得歡呼。
不要以為我們
機房裡沒有風吹，
沒有日曬，
就比勤勞的體育生們輕鬆，
只不過是大腦和四肢
的區別罷了。
可是，
OIer的寂寞和委屈又有誰能懂？
自習課鏖戰機房，
卻被認為而是逃課上網；
為榮耀耽誤考試去比賽，
卻被認為是逃避。
體育的同學們雖然辛苦，
但在揮汗如雨的背後，
有人在喝彩鼓掌；
在風吹日曬的同時，
有粉絲在仰慕。
而我們呢？
與UnAC較勁的時候，
只有那一遍遍的運行窗口，
知道我們的不屈；
刷題的漫漫長夜，
只有陪伴我們的筆記本電腦，
知道我們的不懈；
在自習課別人學習的時候，
只有板磚般的算法導論，
知道我們的進取；
在機房泡得搶不上飯的時候，
只有五毛一包的乾脆面，
知道我們的執著……
沒有人會理解，
OIer見面，
除了程序、算法之外
別無他言。
我們的世界裡，
從來不會有遊戲、歌星的出現。
這不是被家長逼迫的“小三門”，
是我們的興趣，
我們的愛好，
乃至我們的事業。
每一個OIer都幻想著
自己脖子上可以
掛上一塊沉甸甸的金牌，
而不是
萬惡的應試教育的枷鎖。
沒準哪個OIer，
就是下一個艾倫•圖靈，
挑戰頭腦的極限，
去做最不平凡的自己。。。。。。