大战 【WC2014】非确定机 记

· · 个人记录

目前进度 9/10。

1

看一眼发现是图的邻接矩阵。

2,3

分别是单源最短路（带权）和全源最短路（不带权）。后者直接输出所有矩阵为 1 的位置即可。前者将最短路排序构造一条链，因为有长度不超过 20000 的要求。

4

经过艰苦的奋斗发现是次短路，数组在 35000\sim 20000+\text{dis}(1) 之间取值。那么构造一个环，除了 1 以外的点都有 20000 的自环即可。最后随意补上一条边即可，不要让那条边连到 1。

5

发现是强联通分量的最小点的标号。

6

发现只和上面那个序列有关，直接爆搜即可。搜到了再把边补上。

7

仍然只和上面那个序列有关，不过这次比较难看出来。

经过艰苦的奋斗，发现空图答案是 n!-1。

再经过艰苦的奋斗，发现好像是个单射。

再经过艰苦的奋斗，发现这是使得最大值最小的线性的单射。

const int N=100;
ll rev[N];int a[N];
int main(){
    ios::sync_with_stdio(0);cin.tie(0);
    freopen("nm7.in","r",stdin);
    freopen("nm7.out","w",stdout);
    int n,m,k,p;cin>>n>>k>>p;m=0;
    ll t;cin>>t;
    rev[n]=1;
    for(int i=n-1;i;i--)rev[i]=rev[i+1]*(i+1);
    rep(i,1,n)a[i]=t/rev[i],t%=rev[i];
    rep(i,1,n)a[i]++;
    //rep(i,1,n)printf("%d ",a[i]);puts("");
    rep(i,1,n)if(a[i]!=i)m+=2;
    printf("%d %d %d\n",n,20,k);
    rep(i,2,n)if(a[i]!=i)printf("%d %d 1\n%d %d 1\n",i,a[i],a[i],i);
    rep(i,1,8)printf("%d %d %d\n",i,i,0);
    return 0;
}

8

看到 61\ 100 \ 6100 这样的输入，随机试了几个输入发现好像都是有出度的点，就直接构造前 61 个点往所有点连边即可。

9

随机试了几个，发现好像是出边中标号最小的。

这么做确实能得到 4 分。发现边数不够，遂再尝试。

经过艰苦的奋斗，发现是字典序最小的最大匹配，因此每个点可以往前面已经匹配的点连边，边数正好够。

10

不会。