Google Grad Test Second Round
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了Google Grad Test Second Round，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含4432字，纯文字阅读大概需要7分钟。
内容图文
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\n", iCase);
}else {
printf("Case #%d: No\n", 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\n");
}else {
printf("%d\n", 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. 最优解法
原文：http://www.cnblogs.com/zhouzhuo/p/3660768.html
内容总结
以上是互联网集市为您收集整理的Google Grad Test Second Round全部内容，希望文章能够帮你解决Google Grad Test Second Round所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。