题目链接：http://acdreamoj.sinaapp.com/
Acdream的这场比赛真真到达了“区域赛之手速赛”的水平。
不过还是略显自己的弱渣之水平。
A题。染色法判二分图，妥妥的。一开始读错题。。WA了一发。
对于这道题目的定位为：模板/经典题目。这也是所谓“区域赛手速题”吧。。
Code：
/*
* this code is made by creat2012
* Problem: 1056
* Verdict: Accepted
* Submission Date: 2014-08-08 19:40:43
* Time: 24MS
* Memory: 1824KB
*/
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <map>
#include <string>
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
#define CLR(arr, val) memset(arr, val, sizeof(arr))
const int N = 203;
bool vis[N];
int color[N];
vector<int> Map[N];
bool bfs(int s){
queue<int> q;
q.push(s);color[s]=1;
while(!q.empty()){
int now=q.front();
q.pop();
if(!vis[now]){
int len=Map[now].size();
for(int i=0;i<len;i++){
int des=Map[now][i];
q.push(des);
if(color[des]==-1)
color[des]=color[now]==0?1:0;
else {
if(color[des]==color[now]) return false;
else continue;
}
}
vis[now]=true;
}
}
return true;
}
int main(){
int T, k = 0;
scanf("%d", &T);
while(T --){
CLR(color,-1);CLR(vis,0);
CLR(Map,0);
map<string, int> m;
int n, no = 0, x, y;
string st1, st2;
scanf("%d", &n);
for(int i = 1; i <= n; i ++){
cin >> st1 >> st2;
if(m.count(st1) == 0) m[st1] = ++ no;
x = m[st1];
if(m.count(st2) == 0) m[st2] = ++ no;
y = m[st2];
Map[x].push_back(y);
Map[y].push_back(x);
}
// printf("%d\n", no);
// for(int i = 1; i <= no; i ++){
// for(int j = 0; j < Map[i].size(); j ++)
// printf("%d ", Map[i][j]);
// printf("\n");
// }
bool flag = true;
printf("Case #%d: ", ++k);
for(int i = 1; i <= no; i ++){
if(!vis[i]){
if(!bfs(i)) flag = false;
}
}
if(!flag) puts("No");
else puts("Yes");
for(int i = 1; i <= no; i ++) Map[i].clear();
}
return 0;
}
B题。说一个草坪（n*m的矩阵表示）初始时候全部为100m。一个割草机没次可以垂直进入割草，每次宽度为1m（也就是一个矩阵的一行/一列）。问一种状态是否可以是该割草机割的。
这道题的定位为，小型想法题。有好的想法，处理起来就很easy了。
对于该题的思路为：若一个位置的草的高度小于该位置的同行，同列的较小者。为不符合的状态。
Code：
/*
* this code is made by creat2012
* Problem: 1044
* Verdict: Accepted
* Submission Date: 2014-08-09 11:24:40
* Time: 8MS
* Memory: 1088KB
*/
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
const int N = 105;
int main(){
int T, k = 0;
scanf("%d", &T);
while(T --){
int n, m, map[N][N];
scanf("%d %d", &n, &m);
for(int i = 1; i <= n; i ++){
for(int j = 1; j <= m; j ++)
scanf("%d", &map[i][j]);
}
int l[N], c[N];
for(int i = 1; i <= n; i ++){
int lmax = -1;
for(int j = 1; j <= m; j ++)
lmax = max(map[i][j], lmax);
l[i] = lmax;
}
for(int i = 1; i <= m; i ++){
int cmax = -1;
for(int j = 1; j <= n; j ++)
cmax = max(map[j][i], cmax);
c[i] = cmax;
}
bool flag = true;
for(int i = 1; i <= n; i ++){
for(int j = 1; j <= m; j ++)
if(map[i][j] < min(l[i], c[j]))
flag = false;
}
printf("Case #%d: ", ++ k);
if(flag) puts("YES");
else puts("NO");
}
return 0;
C题：一个物理问题。可以得到一个公司。ans = asin((g * d) / (v * v) * 90.0 / PI)；
很easy 的一个题目。本来大家都以为1A，没有问题。
可以如果我们注意到数据范围的话：1 ≤ T ≤ 4500 1 ≤ V ≤ 300 1 ≤ D ≤ 10000
如果思考认真的话，我们可以看到，asin()；中的值是可以为>1的。但是，我们知道这是不合法的。
Code：
/*
* this code is made by creat2012
* Problem: 1118
* Verdict: Wrong Answer
* Submission Date: 2014-08-09 11:53:24
* Time: 4MS
* Memory: 1220KB
*/
#include <cstdio>
#include <cstring>
#include <cmath>
using namespace std;
const double PI = acos(-1);
const double g = 9.8;
int main(){
int T, k = 0;
scanf("%d", &T);
while(T --){
double v, d;
scanf("%lf %lf", &v, &d);
double ans = g * d / v / v;
ans = ans > 1.0 ? 1.0 : ans;
printf("Case #%d: %.7lf\n", ++ k, asin(ans) * 90.0 / PI);
}
return 0;
}
D题，稍后再更新。
E题，判断一个棋盘的状态。这也是我们常玩游戏的一部分的实现。
这道题目的定位：思路的全面性。考察你的思路是否全面。
根据邀请赛的经验，往往会有这方面的考察。一定要注意。。！！
处理的好了。很easy。
Code:
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
const int N = 5;
char map[N][N];
char Judge(){
char now ;
int cnt ;
for(int i = 1; i <= 4; i ++){
now = map[i][1];
cnt = 1;
for(int j = 2; j <= 4; j ++){
if(now == 'T') now = map[i][2];
if(map[i][j] == now ||map[i][j] == 'T') cnt ++;
}
if(cnt == 4 && now != '.') return now;
}
for(int i = 1; i <= 4; i ++){
now = map[1][i];
cnt = 1;
for(int j = 2; j <= 4; j ++){
if(now == 'T') now = map[2][i];
if(map[j][i] == now ||map[j][i] == 'T') cnt ++;
}
if(cnt == 4 && now != '.') return now;
}
now = map[1][1];
cnt = 1;
for(int i = 2; i <= 4; i ++){
if(now == 'T') now = map[2][2];
if(map[i][i] == now ||map[i][i] == 'T') cnt ++;
if(cnt == 4 && now != '.') return now;
}
now = map[1][4]; cnt = 1;
for(int i = 2; i <= 4; i ++){
if(now == 'T') now = map[2][3];
if(map[i][5 - i] == now ||map[i][5 - i] == 'T') cnt ++;
if(cnt == 4 && now != '.') return now;
}
for(int i = 1; i <= 4; i ++){
for(int j = 1; j <= 4; j ++)
if(map[i][j] == '.') return 'G';
}
return 'D';
}
int main(){
int T, k = 1;
scanf("%d", &T);
while(T --){
getchar();
for(int i = 1; i <= 4; i ++){
for(int j = 1; j <= 4; j ++)
scanf("%c", &map[i][j]);
getchar();
}
printf("Case #%d: ", k ++);
char c = Judge();
if(c == 'O') puts("O won");
else if(c == 'X') puts("X won");
else if(c == 'D') puts("Draw");
else puts("Game has not completed");
}
return 0;
}
代码写 的很挫。。。。。- - ！还需要多些代码.。。。。