想问一下为啥这种写法会wa
查看原帖
想问一下为啥这种写法会wa
1301050
ssk_e楼主2024/10/11 10:15
#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
int a[20],b[20];
int dp[1 << 20];//状态为i时是否合法
int n;
unordered_map<int,int>ma,mb;
bool check(int x)//检查是否还有符合条件的牌
{
    ma.clear();
    mb.clear();
    for(int i = 1;i <= n;i++)
    {
        int tmp = x & (1 << (i-1));
        if(tmp) continue;
        if(ma[a[i]] || mb[b[i]]) return false;
        ma[a[i]]++;
        mb[b[i]]++;
    }
    return true;
}
int count(int x)
{
    int ans = 0;
    while(x)
    {
        ans += x % 2;
        x /= 2;
    }
    return ans / 2;
}
void solve()
{
    cin >> n;
    for(int i = 1;i <= n;i++)
    {
        cin >> a[i] >> b[i];
    }
    dp[0] = 1;
    for(int i = 0;i < (1 << n);i++)
    {
        for(int j = 1;j <= n;j++)
        {
            int tmp = i & (1 << (j-1));
            if(tmp == 0)    continue;
            for(int k = j+1;k <= n;k++)
            {
                int ans = i & (1 << (k-1));
                if(ans == 0)    continue;
                if(a[j] == a[k] || b[j] == b[k])
                {
                    dp[i] |= dp[i ^ (1 << (j-1)) ^ (1 << (k-1))];
                }
            }
        }
    }
    for(int i = 0;i < (1 << n);i++)
    {
        if(check(i) && dp[i] && count(i) % 2 == 1)
        {
            cout << "Takahashi" << endl;
            return ;
        }
    }
    cout << "Aoki" << endl;
    return ;
}

signed main() 
{
    ios::sync_with_stdio(false),cin.tie(0);
    int tt = 1;
    while(tt--)
    {
        solve();
    }
    return 0;
}
2024/10/11 10:15
加载中...