求助昨晚 ABC E,玄关
  • 板块学术版
  • 楼主xz001
  • 当前回复0
  • 已保存回复0
  • 发布时间2024/4/14 12:49
  • 上次更新2024/4/14 15:13:27
查看原帖
求助昨晚 ABC E,玄关
674967
xz001楼主2024/4/14 12:49
/*
#pragma GCC optimize(1)
#pragma GCC optimize(2)
#pragma GCC optimize(3, "Ofast", "inline")
*/
#include<bits/stdc++.h>

using namespace std;

#define re			register
#define int			long long
#define fi			first
#define se			second
#define swap(a, b) 	a ^= b, b ^= a, a ^= b
#define pb 			push_back
#define all(x)		x.begin(), x.end()
#define max(a, b)	(a > b ? a : b)
#define min(a, b)	(a < b ? a : b)
#define il			inline
#define abs(x)		((x ^ (x >> 63)) - (x >> 63))

typedef pair<int, int> PII;

const int N = 1e6 + 10;
const int M = 1e6 + 10;
const int INF = 1e18, P = 998244353;
const double eps = 1e-6;

il int  read() { re int x = 0; re bool f = true; re char c = getchar(); while (c < 48 || c > 57) { if (c == '-') f = false; c = getchar(); } while (c >= 48 && c <= 57) x = (x << 3) + (x << 1) + c - 48, c = getchar(); return f ? x : -x; }
il void write(int x) { if (x < 0) putchar('-'), x = -x; if (x > 9) write(x / 10); putchar(x % 10 + 48); }
il void wel(int x) { write(x), putchar('\n'); }
il void wsp(int x) { write(x), putchar(' '); }

int a[4][4];

struct node {
	int a[4][4];
	bool operator < (const node b) const {
		for (int i = 1; i <= 3; ++ i )
		    for (int j = 1; j <= 3; ++ j )
		        if (a[i][j] < b.a[i][j])
		            return true;
		            
		return false;
	}
};

map <pair <node, pair <int, int> >, bool> p;

int f (node x) {
	for (int i = 1; i <= 3; ++ i )
	    if (x.a[i][1] == x.a[i][2] && x.a[i][2] == x.a[i][3] && x.a[i][1])
	        return x.a[i][1];
	        
	for (int i = 1; i <= 3; ++ i )
	    if (x.a[1][i] == x.a[2][i] && x.a[2][i] == x.a[3][i] && x.a[1][i])
	        return x.a[1][i];
	        
	if (x.a[1][1] && x.a[1][1] == x.a[2][2] && x.a[2][2] == x.a[3][3]) 
	    return x.a[1][1];
	    
    if (x.a[1][3] && x.a[1][3] == x.a[2][2] && x.a[2][2] == x.a[3][1])
        return x.a[1][3];
        
    return 3;
}

void dfs (node x, int i, int s1, int s2) {
	if (i > 9) {
		p[{x, {s1, s2}}] = s1 > s2;
		return;
	}
	if (i & 1) {	
	    bool is = false;
	    for (int ii = 1; ii <= 3; ++ ii ) 
	        for (int jj = 1; jj <= 3; ++ jj ) {
	        	node b = x;
	        	if (!x.a[ii][jj]) {
	        		b.a[ii][jj] = 1;
	        		if (f(b) == 2) continue;
	        		if (f(b) == 1) {
	        			is = true;
	        			break;
					}
	        		dfs (b, i + 1, s1 + a[ii][jj], s2);
	        		is |= p[{b, {s1 + a[ii][jj], s2}}];
				}
			}
		p[{x, {s1, s2}}] = is;
		return;
	} 
	bool is = true;
	for (int ii = 1; ii <= 3; ++ ii )
	    for (int jj = 1; jj <= 3; ++ jj ) {
	    	node b = x;
	    	if (!x.a[ii][jj]) {
	    		b.a[ii][jj] = 2;
	    		if (f(b) == 1) continue;
				if (f(b) == 2) {
					is = false;
					break;
				} 
	    		dfs (b, i + 1, s1, s2 + a[ii][jj]);
	    		is &= p[{b, {s1, s2 + a[ii][jj]}}];
			}
		}
	p[{x, {s1, s2}}] = is;
	return;
}

signed main() {
    node kdse;
    for (int i = 1; i <= 3; ++ i )
        for (int j = 1; j <= 3; ++ j )
            a[i][j] = read(), kdse.a[i][j] = 0;

    dfs (kdse, 1, 0, 0);
    if (p[{kdse, {0, 0}}]) {
    	puts("Takahashi");
	} else {
		puts("Aoki");
	}
    return 0;
}

样例过不了,不知道哪里错了。

2024/4/14 12:49
加载中...