山东省第一届ACM大学生程序设计竞赛

题目A Phone Number

题目链接

  知识点:字典树

code

题目B Balloons

题目链接

  知识点:图的连通性，并查集

code

题目C Clockwise

题目链接

  知识点:计算几何，动态规划

题意:
在二维平面上有N个点，从中选择一组点，将这些点连起来组成向量，要求这些向量顺时针或者逆时针
求满足顺时针或者逆时针条件下，最多可以选择多少点

code

题目D Shopping

题目链接
知识点:
code

题目E Emergency

题目链接

  知识点:最短路径 FLOYD算法 动态规划

题意:
在一个N*M矩阵中，两两之间可能存在道路，每个点初始都是无效的；
Q个操作，操作类型

• 1.将一个点设置为有效
• 2.求两点之间的最短路径

code

题目F Fairy tale

题目链接

  知识点:英语水平

题意:
在N*N的矩阵中，每个格子的值为EWSN之一，每个格子随时间按照EWSN的顺序变化;
在每个时间点

• 1.玩家根据自己所在位置和格子朝向，走一步(玩家在(x,y),格子值是E，则玩家走到(x,y+1),如果(x,y+1)超出矩阵，则原地不动);
• 2.玩家根据玩家和宝贝的直线距离，往宝贝走一个格子;
• 3.宝贝根据宝贝位置和格子朝向，走一步或者停在原地;

时间100内，判断玩家是否能得到宝贝或者判断不出来
code

题目G Greatest Number

题目链接

  知识点:DFS+剪枝

题意:从n个数中选出最多四个数求和，求不大于m的最大和

code

题目H Hello World!

题目链接

  知识点:排序 二分查找 动态规划

题意:在一个矩阵中有N个点被标记，求每个标记(x,y)的下一个标记点(xx,yy)
(xx,yy)需满足:

• 1.xx>x && yy >y
• 2.xx最小
• 3.yy最小

code 动态规划超时 嗯？

code

题目K Ivan comes again!

题目链接

  知识点:排序 二分查找 线段树 空间压缩

code