Ⅰ 求程序设计大赛题目
一、行棋游戏:
这是一种只有一个棋子的游戏。棋盘被分为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。命题范围覆盖计算机专业知识，考试地点线下，获奖证书由组织方颁发。