A. Double Perspective
发现最优的情况 \(S\)，应满足 \(g(S)=0\)，所以答案为 \(f(S)\)。
考虑什么时候 \(g(S)=0\)，显然当没有环时 \(g(S)=0\)，这等价于所选的线段中没有一条是另一条的子集。
#include <bits/stdc++.h>
using namespace std;
const int kN = 3e3 + 7;
int n, a[kN], b[kN], vis[kN];
void solve(){cin >> n;for(int i = 1; i <= n; i++) cin >> a[i] >> b[i], vis[i] = 0;for(int i = 1; i <= n; i++){for(int j = 1; j <= n; j++){if(i != j && a[j] <= a[i] && b[i] <= b[j]){vis[i] = 1; break;}}}vector<int> ans;for(int i = 1; i <= n; i++){if(!vis[i]) ans.push_back(i);}cout << ans.size() << '\n';for(int i : ans) cout << i << ' '; cout << '\n';
}
signed main(){ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);int T = 1; cin >> T;while(T--) solve();return 0;
}
B. Stay or Mirror