Tournament
题目思路
简单的贪心
显然一个选手在击败 所有由他击败的选手 之前不能被其他选手击败
那么我们为这次锦标赛设置一个时间，显然同一时间内一个选手只能击败一人（只能打一次比赛）
设 (t_i) 为一个选手最早能被击败的时间（即此时它被击败不会与条件冲突）
由于一个选手在同一时间内只能击败一人，我们直接贪心即可得到 (t_i) ，最后的答案就是 (t_1)
代码
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
int n,d[100005];
vector<int>g[100005];
bool cmp(int g1,int g2){
return d[g1]<d[g2];
}
void dfs(int u){
for(int i=0;i<g[u].size();i++){
int v=g[u][i];
dfs(v);
}
sort(g[u].begin(),g[u].end(),cmp);
int last=-1;
for(int i=0;i<g[u].size();i++){
int v=g[u][i];
if(d[v]<=last)last++;
else last=d[v];
}
d[u]=last+1;
}
int main(){
scanf("%d",&n);
for(int i=2;i<=n;i++){
int x;
scanf("%d",&x);
g[x].push_back(i);
}
dfs(1);
printf("%d",d[1]);
return 0;
}
Building Cubes with AtCoDeer
题目思路
玄学计数题（枚举）
一开始想着类似折半搜索一样的思路，每次枚举立方体的三个面，然后状压起来。但这样无法处理两次枚举到相同瓷砖的情况，放弃
考虑要枚举几个瓷砖，三个显然不行，四个时间爆炸，发现当我们枚举到上下两个面的瓷砖时已经可以确定立方体四个角的颜色了
因此我们枚举立方体上下两个面的瓷砖，分别确定另外四个面四个角的颜色，提前将他们状压起来，直接查询即可
实现判重时有些细节，注意代码；另外注意瓷砖旋转的情况，可以用画图3D画一画
代码
#include<iostream>
#include<unordered_map>
#define get(a,b,c,d) (a*1000000000ll+b*1000000ll+c*1000ll+d)
#define nxt(x) (x%1000ll*1000000000ll+x/1000ll)
using namespace std;
int n,c[405][4];
long long a[405];
unordered_map<long long,int>m;
void calc(long long x,int d) {
for(int i=0; i<4; i++) {
m[x=nxt(x)]+=d;
}
}
int main() {
scanf("%d",&n);
for(int i=1; i<=n; i++) {
for(int d=0; d<4; d++)scanf("%d",&c[i][d]);
a[i]=get(c[i][0],c[i][1],c[i][2],c[i][3]);
calc(a[i],1);
}
long long ans=0;
for(int i=1; i<=n; i++) {
calc(a[i],-1);
for(int j=i+1; j<=n; j++) {
calc(a[j],-1);
for(int d=0; d<4; d++) {
long long x0=get(c[j][1],c[j][0],c[i][(d+1)%4],c[i][d]);
long long x1=get(c[j][2],c[j][1],c[i][d],c[i][(d+3)%4]);
long long x2=get(c[j][3],c[j][2],c[i][(d+3)%4],c[i][(d+2)%4]);
long long x3=get(c[j][0],c[j][3],c[i][(d+2)%4],c[i][(d+1)%4]);
if(m[x0]==0||m[x1]==0||m[x2]==0||m[x3]==0)continue;
long long mul=1;
mul*=m[x0],calc(x0,-1);
mul*=m[x1],calc(x1,-1);
mul*=m[x2],calc(x2,-1);
mul*=m[x3],calc(x3,-1);
calc(x0,1);
calc(x1,1);
calc(x2,1);
calc(x3,1);
ans+=mul;
}
calc(a[j],1);
}
calc(a[i],1);
}
printf("%lld",ans/3);
return 0;
}
[HNOI2015]落忆枫音
第一眼想到矩阵树定理，然而数据范围过大，不能直接求解
我们考虑这样一件事情，对于未加边的有向无环图，我们按照dfs序给他们重新编号，这样求出来的矩阵一定是一个上三角矩阵
也就是说对于有向无环图来说，矩阵的行列式可以 (O(n)) 求解，这个值实际就是每个节点入度之积（对于一号节点，我们再建一个零号节点连向他）
也可以这么理解，即为每个节点选一个父亲
然而现在还多加了一条边，有可能构成环，怎么办呢？
我们发现，假如我们仍用上述方法求解，最后得出的生成树有一部分会带有环，设环上节点为 (a_1,a_2dots a_k)，这部份带有环的'生成树'的数量为 (frac{prodlimits_{i=1}^nd_i}{prodlimits_{i=1}^kd_{a_i}})（因为环上所有节点父亲已经确定）
因此我们考虑容斥，设 (d_i) 为节点 (i) 入度，答案即为 (prodlimits_{i=1}^nd_i-frac{prodlimits_{i=1}^nd_i}{prodlimits_{i=1}^kd_{a_i}})
考虑dp求解，若连边为 (x
ightarrow y)，则设 (f_u) 为若连边为 (x
ightarrow u) ，(num) 的值
那么 (f_u=frac{1}{d[u]}sum f_v)
直接求解即可
代码
#include<iostream>
#include<vector>
using namespace std;
const int mod=1e9+7;
int n,m,x,y,d[100005];
vector<int>g[100005];
long long fpow(long long x,int y) {
long long res=1;
while(y) {
if(y&1)res=res*x%mod;
x=x*x%mod;
y>>=1;
}
return res;
}
long long sum=1,f[100005];
bool vis[100005];
void dfs(int u) {
vis[u]=true;
if(u==x){
f[u]=sum*fpow(d[u],mod-2);
return;
}
for(int i=0; i<g[u].size(); i++) {
int v=g[u][i];
if(!vis[v])dfs(v);
f[u]=(f[u]+f[v])%mod;
}
f[u]=f[u]*fpow(d[u],mod-2)%mod;
}
int main() {
scanf("%d%d%d%d",&n,&m,&x,&y);
d[y]++;
for(int i=1; i<=m; i++) {
int u,v;
scanf("%d%d",&u,&v);
g[u].push_back(v);
d[v]++;
}
d[1]++;
for(int i=1; i<=n; i++) {
sum=sum*d[i]%mod;
}
dfs(y);
printf("%lld",(sum-f[y]+mod)%mod);
return 0;
}