\(\text{Permutation G}\)
思路点拨
再开始的局面显然是一个三角形 \((A_i,A_j,A_k)\) ，考虑新增一个节点在什么情况下合法，这里分两类讨论：
-
新增节点 \(A_l\) ，满足 \(A_l\) 在三角形 \((A_i,A_j,A_k)\) 的内部。
-
新增节点 \(A_l\) ，满足 \(A_i/A_j/A_k\) 在三角形 \((A_l,A_j,A_k)/(A_i,A_l,A_k)/(A_i,A_j,A_l)\) 的内部。
不然就容易画图证明画不出三个线条。并且我们的局面每时每刻会保持一个三角形的状态。
考虑动态规划，设 \(f[i][j][k][w]\) 表示目前考虑到以 \(A_i,A_j,A_k\) 三个节点为外围的三角形，目前三角形内部已经选择了 \(w\) 个节点。转移顺序可以由 \(w\) 从小到大转移，具体转移分两类：
-
选择的节点在三角形 \((A_i,A_j,A_k)\) 的内部
-
枚举一个新的节点 \(A_l\) 并且判断是否合法，可以转移。
相信容易写出转移式。现在还有一个细节，就是怎么判断一个节点 \(A_l\) 是否在 \((A_i,A_j,A_k)\) 中，我采取的方法是判断三角形 \((A_i,A_j,A_l),(A_i,A_k,A_l),(A_j,A_k,A_l)\) 的面积和是否等于 \((A_i,A_j,A_k)\) 的面积。对于单个三角形的面积因为保证三点不会共线，所以使用水平宽铅垂高求会比较简单。单次可以 \(O(1)\) 判断，但是因为涉及大量浮点数运算的原因常数较大，建议预处理出来。
时间复杂度分析发现对于每一个状态，我们枚举一个三角形外的节点 \(A_l\) 需要花费 \(O(n)\) 的时间，所以时间复杂度为 \(O(n^5)\) 。本题中 \(n \leqslant 40\) 所以可以轻松通过。
\(\text{Cowpatibility G}\)
思路点拨
考虑容斥，问题转换为了求包含 \(k\) 个给定的冰激凌的奶牛有多少个。将冰激凌的品种哈希之后放入 unordered_map 里面看出现次数即可。时间复杂度 \(O(n)\) ，但是 \(160\) 的常数。
代码比较短所以贴一个：
#include<bits/stdc++.h>
#define int unsigned long long
#define ll long long
using namespace std;
const int MAXN=5e4+5,base=1e6+5;
int n,a[MAXN][5];
long long ans;
unordered_map<int,int> cnt;
signed main(){
cin>>n;
for(int i=1;i<=n;i++){
for(int j=0;j<5;j++) cin>>a[i][j];
sort(a[i],a[i]+5);
for(int j=0;j<(1<<5);j++){
int popcount=0,hsh=0;
for(int k=0;k<5;k++)
if(j&(1<<k)){
popcount++;
hsh=hsh*base+a[i][k];
}
cnt[hsh]++;
if(popcount&1) ans=ans-cnt[hsh];
else ans=ans+cnt[hsh];
}
}
cout<<ans;
return 0;
}