Problem A Sudoku Checker
总结: 简单模拟题. 时间复杂度 o(n^4)
#include <iostream>
#include <stdio.h>
#include <memory.h>
#include <algorithm>
#include <vector>
#include <map>
#include <set>
#include <string>
#include <deque>
#define MIN(x,y) (x)<(y)?(x):(y)
using namespace std;
bool valid;
int matrix[1600][1600];
void initSet(set<int> &set_it, int n) {
for(int i = 1; i <= n*n; i++)
set_it.insert(i);
}
void smallPart(int x, int y, int n) {
set<int> tmp;
initSet(tmp, n);
for(int i = x; i < n; i ++) {
for(int j = y; j < n; j ++) {
if(tmp.count(matrix[i][j]) == 0) {
valid = false;
return;
}
tmp.erase(tmp.find(matrix[i][j]));
}
}
}
void bigPart(int n) {
for(int i = 0; i < n*n && valid; i ++) { /* for each line */
set<int> tmp;
initSet(tmp, n);
for(int j = 0; j < n*n && valid; j ++) {
if(tmp.count(matrix[i][j]) == 0) {
valid = false;
return;
}
tmp.erase(tmp.find(matrix[i][j]));
}
}
for(int j = 0; j < n*n && valid; j ++) {
set<int> tmp;
initSet(tmp, n);
for(int i = 0; i < n*n && valid; i ++) {
if(tmp.count(matrix[i][j]) == 0) {
valid = false;
return;
}
tmp.erase(tmp.find(matrix[i][j]));
}
}
for(int t = 0; t < n*n; t ++) {
int i = t / n;
int j = t % n;
smallPart(i*n, j*n, n);
}
}
int main() {
freopen("C:\Users\vincent\Dropbox\workplacce\joj\test.txt", "r", stdin);
int T, iCase = 0;
scanf("%d", &T);
while(T --) {
valid = true;
int n;
scanf("%d", &n);
for(int i = 0; i < n*n; i ++) {
for(int j = 0; j < n*n; j ++) {
scanf("%d", &matrix[i][j]);
}
}
bigPart(n);
if(valid) {
printf("Case #%d: Yes ", iCase);
}else {
printf("Case #%d: No ", iCase);
}
}
return 0;
}
Problem B Dragon Maze
思路:
1. 单源点最短路径变形题. 我用到了两个数组分别判断一个点是否已经被加入到队列中, 和是否还能够被更新该点获得的最大价值, 我觉得这是有些低效的, 应当有更优雅的解法
#include <iostream>
#include <stdio.h>
#include <memory.h>
#include <algorithm>
#include <vector>
#include <map>
#include <set>
#include <string>
#include <deque>
#define MIN(x,y) (x)<(y)?(x):(y)
using namespace std;
int value[200][200];
bool visited[200][200];
bool added[200][200];
int matrix[200][200];
int dir[4][2] = {0,1, 1,0, 0,-1, -1,0}; /* */
const int INF = 0X3F3F3F3F;
int sx, sy, ex, ey;
int n, m;
/* using more space for simplicity */
class Node {
public:
int x, y, dist;
Node() {
x = y = dist = 0;
}
Node(int _x, int _y, int _dist):x(_x), y(_y), dist(_dist) {}
};
int bfs() {
deque<Node> queue;
int minDist = INF;
memset(visited, 0, sizeof(visited));
memset(value, 0, sizeof(value));
memset(added, 0, sizeof(added));
queue.push_back(Node(sx, sy, 0));
added[sx][sy] = 1;
value[sx][sy] = matrix[sx][sy];
while(!queue.empty()) {
Node fath = queue.front();
queue.pop_front();
visited[fath.x][fath.y] = 1;
if(fath.x == ex && fath.y == ey) { /* give same level nodes opportunity*/
minDist = fath.dist;
}
if(fath.dist > minDist) {
break;
}
for(int i = 0; i < 4; i ++) {
int cx = fath.x + dir[i][0];
int cy = fath.y + dir[i][1];
if(cx < 0 || cy < 0 || cx > n-1 || cy > m-1)
continue;
if(matrix[cx][cy] < 0) { /* dangerous place */
continue;
}
if(!visited[cx][cy]) { /* update */
value[cx][cy] = max(value[cx][cy], value[fath.x][fath.y]+matrix[cx][cy]);
if(!added[cx][cy]) {
queue.push_back(Node(cx, cy, fath.dist+1));
added[cx][cy] = 1;
}
}
}
}
return value[ex][ey];
}
int main() {
freopen("C:\Users\vincent\Dropbox\workplacce\joj\test.txt", "r", stdin);
int T, iCase = 0;
scanf("%d", &T);
while(T --) {
scanf("%d%d", &n, &m);
scanf("%d%d%d%d", &sx, &sy, &ex, &ey);
iCase ++;
for(int i = 0; i < n; i ++) {
for(int j = 0; j < m; j ++) {
scanf("%d", &matrix[i][j]);
}
}
int res = bfs();
printf("Case #%d: ", iCase);
if(res == 0) {
printf("Mission Impossible ");
}else {
printf("%d ", res);
}
}
return 0;
}
Problem E Ignore All My Comments
思路:
1. 每次读取一行, 并且把每次读取的字符放到 string 里, 100kb 装的下
2. 查找符号 '/', 以此为根据向右扩展得到 /*, 向左扩展得到 */, 能使问题简化
3. 我最初用 scanf() 来移位, 结局只能说太惨了, 因为没有 look_back() 功能, //* 这种类型的就判断不出了
Problem C Hex
思路
1. 所有不正确的状态: a. 双方棋子相差 1 以上; b. 红方赢, 但蓝方的棋子更多. c. 红方赢, 但红方的棋子路径上没有关键点.
2. 这道题是相当难得, 师兄当初靠抱 ACMer 的大腿才弄过去
Problem B Meet and Party
1. 最简单的解法是枚举, 但只能过小数据.
2. 优化, 每次计算一个点到一块区域的长度之和.
3. 最优解法