CF377A Maze
題意：有一個地圖，有空地和墻，空地是一個連通塊，問要再添k堵墻，使得空地還是一個連通塊，輸出改變后的地圖，
解法：這題的思維很新穎，沒想到啊，如果正面搜索，需要考慮的情況比較多，所以逆向思維，先把所有’.‘變成’X’，然后，再找出一個大小為ans-k數量的連通塊，記得dfs的時候計數器要定義為全域變數，害，下次我還寫bfs，
代碼：
#include <algorithm>
#include <iostream>
#include <cstring>
#include <vector>
#include <cstdio>
#include <queue>
#include <cmath>
#include <set>
#include <map>
#define fio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define _for(n,m,i) for (register int i = (n); i < (m); ++i)
#define _rep(n,m,i) for (register int i = (n); i <= (m); ++i)
#define lson rt<<1, l, mid
#define rson rt<<1|1, mid+1, r
#define PI acos(-1)
#define eps 1e-8
#define rint register int
#define F(x) ((x)/3+((x)%3==1?0:tb))
#define G(x) ((x)<tb?(x)*3+1:((x)-tb)*3+2)
using namespace std;
typedef long long LL;
typedef pair<LL, int> pli;
typedef pair<int, int> pii;
typedef pair<double, int> pdi;
typedef pair<LL, LL> pll;
typedef pair<double, double> pdd;
typedef map<int, int> mii;
typedef map<char, int> mci;
typedef map<string, int> msi;
template<class T>
void read(T &res) {
int f = 1; res = 0;
char c = getchar();
while(c < '0' || c > '9') { if(c == '-') f = -1; c = getchar(); }
while(c >= '0' && c <= '9') { res = res * 10 + c - '0'; c = getchar(); }
res *= f;
}
const int ne[8][2] = {1, 0, -1, 0, 0, 1, 0, -1, -1, -1, -1, 1, 1, -1, 1, 1};
const int INF = 0x3f3f3f3f;
const int N = 1010;
const LL Mod = 1e9+7;
const int M = 1e6+10;
int in[N];
int main() {
int T; scanf("%d", &T);
int n, x, u, v;
while(T--) {
memset(in, 0, sizeof in);
scanf("%d%d", &n, &x);
_for(1, n, i) {
scanf("%d %d", &u, &v);
++in[u]; ++in[v];
}
if(n == 1 || in[x] == 1 || n%2 == 0) puts("Ayush");
else puts("Ashish");
}
return 0;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/yidong/154093.html
標籤：其他
上一篇：【Cocos2dx】如何將CocosCreator構建發布的Android平臺工程整合到已有的Android專案中