详细解题步骤

这道题涉及使魔与饲主之间的交互关系，需要我们确定哪些饲主是"有希望的"，哪些是"人生赢家"。

首先分析问题核心：

• 使魔可以互相攻击，当使魔乙对甲的饲主好感度高于对自己饲主时，乙会被甲的饲主拐走
• 攻击顺序结束时，没有使魔可以被拐走
• "有希望的"：存在某种攻击顺序，使饲主最终拥有至少一只使魔
• "人生赢家"：无论攻击顺序如何，饲主最终都拥有至少一只使魔

下面是具体实现：

#include <bits/stdc++.h>
using namespace std;
int cnt[505], cnt1[505];
int n, a[505][505], p, Ans[505];
bitset<505> kil[505];
// kil[i]表示饲主i能"拐走"的初始使魔集合

// 检查是否满足条件：饲主x能拥有至少一只使魔
inline bool check(int x, bitset <505> d) {
    // 情况1：d不包含x，但包含了其他所有使魔，说明x至少保留了自己
    if (!d[x] && d.count() == n - 1)
        return true;
    
    // 情况2：d包含了所有使魔，说明x成功拐走了至少一只
    if (d.count() == n)
        return true;
    
    return false;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> n;
    
    // 读入每个使魔对饲主的好感度排序
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= n; ++j)
            cin >> a[i][j];
    
    cin >> p;
    
    // 处理"人生赢家"的情况(p=1)
    if (p & 1) {
        // 人生赢家的条件：使魔i对自己饲主的好感度最高
        // 这样无论如何攻击，这只使魔都不会被拐走
        for (int i = 1; i <= n; ++i)
            if (a[i][1] == i)
                ++cnt1[i];
        
        int res = 0;
        for (int i = 1; i <= n; ++i)
            if (cnt1[i])
                ++res;
        
        cout << res << '\n';
        for (int i = 1; i <= n; ++i)
            if (cnt1[i])
                cout << i << " ";
    } 
    // 处理"有希望的"情况(p=2)
    else {
        // 预处理每个饲主能拐走哪些初始使魔
        for (int i = 1; i <= n; ++i) {
            int pos;
            // 找到使魔i对自己饲主的好感度位置
            for (int j = 1; j <= n; ++j)
                if (a[i][j] == i) {
                    pos = j;
                    break;
                }
            
            // 对于使魔i，好感度高于自己饲主的饲主都能拐走它
            for (int j = 1; j <= pos; ++j)
                kil[a[i][j]][i] = 1;
        }
        
        // 检查每个饲主是否有希望
        for (int i = 1; i <= n; ++i) {
            int pos;
            for (int j = 1; j <= n; ++j)
                if (a[i][j] == i) {
                    pos = j;
                    break;
                }
            
            bitset <505> qwq;
            qwq.reset();
            
            // 从后往前处理，维护能拐走的使魔集合
            for (int j = n; j > pos; --j)
                qwq |= kil[a[i][j]];
            
            // 检查是否能通过某种攻击顺序使饲主a[i][j]拥有至少一只使魔
            for (int j = pos; j >= 1; --j) {
                if (check(i, qwq))
                    ++cnt1[a[i][j]];
                qwq |= kil[a[i][j]];
            }
        }
        
        // 收集结果
        int tot = 0;
        for (int i = 1; i <= n; ++i)
            if (cnt1[i])
                Ans[++tot] = i;
        
        cout << tot << '\n';
        for (int i = 1; i <= tot; ++i)
            cout << Ans[i] << " ";
    }
    
    return 0;
}

算法解析

1. 对于"人生赢家"的判定：

   • 只有当某个使魔对自己饲主的好感度最高时，这个饲主才可能成为人生赢家
   • 因为无论其他使魔如何攻击，这只使魔都不会被拐走，保证了饲主至少拥有一只使魔

2. 对于"有希望的"判定：

   • 使用bitset高效维护每个饲主能拐走的使魔集合
   • 通过从后往前处理好感度列表，模拟不同的攻击顺序
   • 检查是否存在某种攻击顺序，使饲主最终能拥有至少一只使魔

3. 复杂度分析：

   • 时间复杂度：O(n²)，主要是两层循环处理n个使魔和n个饲主
   • 空间复杂度：O(n²)，使用了二维数组和bitset数组存储信息

这个算法通过巧妙地利用bitset和对攻击顺序的模拟，高效地解决了问题中两种不同判定条件的需求。