Ⅰ 求程序設計大賽題目
一、行棋游戲:
這是一種只有一個棋子的游戲。棋盤被分為N行,M列的方格,某個位置被標記為終點T。在任何一個位置，棋子可以向左、右、上、下四個方向移動一格，記移動距離為1。
在棋盤上有一些特殊方格——飛行器，每個飛行器有一個飛行距離d，棋子達到後可以繼續在同方向再「飛」d格，且移動距離仍然為1。例如，如果棋子在位置（2，8），飛行器在位置（2，7），且飛行距離為5，那麼棋子向左走一格，將直接到達位置（2，2）且移動距離為1。如果飛行點落在棋盤外，則只能停在邊界上。例如，假若前個飛行器的飛行距離為10，那麼棋子的最終位置是（2，1）。
而且，如果飛行後的落點仍然是飛行器，則將連續飛行到目的地，且中間點不對當前棋子產生影響，當然也不算任何移動距離。例如，如果棋子位置在（2，8），飛行器在（2，7）、（2，5），且飛行距離都是5，此時棋子向左移動一格，則（2，5）的飛行器將不產生作用，移動距離仍然為1。
你的任務就是，編程計算出棋子達到終點的最短移動距離。
輸入：
輸入可以有多個測試用例。每個測試用例的第一行是兩個整數N、M（3<=N, M<=100)，表示棋盤的行列數。隨後是一個整數K，表示飛行器的個數。接著的K行每行有3個正整數x、y、d，分別表示飛行器的位置（x,y)(2 <= x <= N-1, 2 <= y <= M-1)及飛行距離d。最後的兩行第一行是棋子的初始位置S，第二行是終點位置T。你可以假設數據總是合法的，S與T、飛行器位置互不相同。輸入0 0時表示結束
輸出：
每個測試用例輸出一行，即達到終點的最短距離。如果不能達到，則輸出「Impossible」。
二、最少錢幣數：
（這個問題的輸入我感覺特別麻煩，希望給出比較好的輸入方法）
這是一個古老而又經典的問題。用給定的幾種錢幣湊成某個錢數，一般而言有多種方式。例如：給定了6種錢幣面值為2、5、10、20、50、100，用來湊15元，可以用5個2元、1個5元，或者3個5元，或者1個5元、1個10元，等等。顯然，最少需要2個錢幣才能湊成15元。
你的任務就是，給定若干個互不相同的錢幣面值，編程計算，最少需要多少個錢幣才能湊成某個給出的錢數。
輸入：
輸入可以有多個測試用例。每個測試用例的第一行是待湊的錢數值M（1 <= M <= 2000，整數），接著的一行中，第一個整數K（1 <= K <= 10）表示幣種個數，隨後是K個互不相同的錢幣面值Ki(1 <= Ki <= 1000)。輸入M=0時結束。
輸出：
每個測試用例輸出一行，即湊成錢數值M最少需要的錢幣個數。如果湊錢失敗，輸出「Impossible」。你可以假設，每種待湊錢幣的數量是無限多的。
樣例輸入：
15
6 2 5 10 20 50 100
1
1 2
0
樣例輸出：
2
Impossible 最佳答案第一題，典型的BFS找最短路
#include <iostream>
#define MAXN 105
using namespace std;
const int dir[4][2]={{0,1},{0,-1},{1,0},{-1,0}};
int m,n;
int map[MAXN][MAXN];
int head,tail;
int queue[MAXN*MAXN][3];
bool hash[MAXN][MAXN];
int tx,ty;
int main()
{
while (cin>>n>>m && n>0)
{
int i,j,k;
memset(map,0,sizeof(map));
cin>>k;
while (k--)
{
cin>>i>>j;
i--;
j--;
cin>>map[i][j];
}
memset(hash,true,sizeof(hash));
cin>>queue[0][0]>>queue[0][1];
queue[0][0]--;
queue[0][1]--;
queue[0][2]=0;
hash[queue[0][0]][queue[0][1]]=false;
head=0;
tail=1;
cin>>tx>>ty;
tx--;
ty--;
while (head<tail && hash[tx][ty])
{
for (k=0;k<4;k++)
{
i=queue[head][0]+dir[k][0];
j=queue[head][1]+dir[k][1];
while (i>=0 && i<n && j>=0 && j<m && map[i][j]>0)
{
i+=map[i][j]*dir[k][0];
j+=map[i][j]*dir[k][1];
if (i<0 || i>=n || j<0 || j>=m)
{
if (i<0) i=0;
if (i>=n) i=n-1;
if (j<0) j=0;
if (j>=m) j=m-1;
break;
}
}
if (i>=0 && i<n && j>=0 && j<m)
if (hash[i][j])
{
queue[tail][0]=i;
queue[tail][1]=j;
queue[tail][2]=queue[head][2]+1;
hash[i][j]=false;
if (i==tx && j==ty) cout<<queue[tail][2]<<endl;
tail++;
}
}
head++;
}
if (hash[tx][ty]) cout<<"impossible"<<endl;
}
return 0;
}
第二題是典型的DP
用f[i][j]表示用前i種幣值湊出總額為j的錢所需的最少錢幣個數
狀態轉移方程f[i][j]=min{f[i-1][j](i>0時),f[i][j-Ki]+1(j>=Ki時),無窮大};
#include <iostream>
#define MAXM 2010
#definme MAXK 15
using namespace std;
int m,k;
int K[MAXK];
int f[MAXK][MAXM];
int main()
{
while (cin>>m && m>0)
{
int i,j;
cin>>k;
for (i=1;i<=k;i++) cin>>K[i];
memset(f,-1,sizeof(f));
f[0][0]=0;
for (i=1;i<=k;i++)
for (j=0;j<=m;j++)
{
int min;
min=-1;
if (f[i-1][j]!=-1 && (min==-1 || f[i-1][j]<min)) min=f[i-1][j];
if (j>=K[i] && f[i][j-K[i]]!=-1 && (min==-1 || f[i][j-K[i]]+1<min)) min=f[i][j-K[i]]+1;
f[i][j]=min;
}
if (f[k][m]==-1) cout<<"impossible"<<endl;
else cout<<f[k][m]<<endl;
}
return 0;
}
Ⅱ 藍橋杯、PAT、CCF CSP、團體程序設計天梯賽、傳智杯、計算機能力挑戰賽、軟考等大學生編程比賽/考試介紹
適合普通大學生參加的編程比賽/考試有以下七種，每種比賽/考試都有其特定的報名時間、舉辦時間、報名費用、可選語言、參賽要求、分組說明、比賽時長、比賽地點、比賽題型、比賽賽制、獲獎詳情，以下是詳細介紹：
1. **藍橋杯**：報名時間一般為每年9月至12月，舉辦時間通常在次年3月進行省賽，6月進行決賽。比賽時長為4小時，包含5道填空題和5道編程題，滿分150分。比賽為OI賽制，報名費用300元，可選語言包括C/C++、Java、Python。比賽分為研究生組、大學A、B、C組，研究生只能參加研究生組，985、211本科生只能參加大學A組及以上，其餘本科生可自行選擇大學B組及以上，高職高專院校可自行選擇組別。往年真題和官方練習系統可在線查詢。獲獎證書由工業和信息化部人才交流中心及大賽組委會頒發。
2. **PAT（計算機程序設計能力考試）**：每年舉辦3次，一般在3月、9月和12月。報名時間緊隨上一次考試結束，報名費用為256元。可選語言有C/C++、Java、Python等。比賽分為頂級、甲級、乙級三個等級，滿分100分，各組時長為3小時，均為編程題。比賽地點線下，考點遍布全國26省/直轄市的51個城市。比賽賽制為IOI賽制，允許無限次提交，僅以最後一次提交為准。獲獎證書由浙江大學計算機學院與軟體學院頒發，部分企業對PAT成績優異者提供免機試、優先錄取等優惠政策。
3. **CCF CSP（CCF計算機軟體能力認證）**：每年舉辦3次，一般在3月、9月和12月，報名時間前一兩個月開始。報名費用非會員400元，會員200元，會員需支付50元開通會員服務（最近暫停）。可選語言為C/C++、Java和Python，時長為4小時，包含5道編程題。比賽地點線下，在全國有80多個認證點。比賽賽制為OI賽制。獲獎證書由CCF頒發，部分高校和企業將CSP成績作為招生或錄取條件。
4. **GPLT 團體程序設計天梯賽**：比賽時間通常安排在每年3月至5月，報名時間通常在比賽開始前10天截止。報名費用為競賽注冊費500元/隊，會務費150元/人。可選語言有C、C++和Java。比賽分為珠峰爭鼎（本科組）、華山論劍（本科組）、滄海競舟（專科組）三個組別。比賽時長3小時，包含基礎級、進階級和登頂級三部分題目。比賽地點線下，在全國有三四十個賽點。比賽賽制為IOI賽制，獲獎證書由組織方頒發。
5. **傳智杯**：每年舉辦一次，一般在3月或4月，2020年為第二屆。報名時間在前一年11月開始，免費報名。可選語言為C/C++、Java和Python。比賽時長為3小時，包含4題。比賽地點線上或北京線下（2020年改為線上）。比賽賽制為ACM-ICPC賽制，獲獎證書由組織方頒發。
6. **全國高校計算機能力挑戰賽**：2019年舉辦過一屆，初賽、決賽均在11月份。報名時間9月至11月，報名費用60元。可選語言為C/C++、Java和Python。比賽分為區域賽和決賽，包含選擇題、程序閱讀和程序設計題型。比賽地點線上。比賽賽制為OI賽制，獲獎證書由組織方頒發。
7. **軟考（計算機技術與軟體專業技術資格（水平）考試）**：每年5月和11月舉辦兩次，報名時間各省不同，一般上半年2-3月，下半年8-9月。報名費用各省不同，幾十元至一百多元。比賽時長上午和下午各2.5小時，包含選擇題和填空題。可選語言下午場必考C語言，選做C++或Java。命題范圍覆蓋計算機專業知識，考試地點線下，獲獎證書由組織方頒發。