Sneaking

题目描述

点此看题

解法

不难看出是最短路，一开始人傻了，直接暴力建图卡了好久，但是最后草过去了。

复杂度瓶颈在于四类边，发现就是多了 \(1\) 的花费有点难搞。可以采用建虚点的思想，我们按 \(F\) 进入坦克模式，花费为 \(1\)，坦克模式开到上一个点的坦克模式花费也为 \(1\)，这样边数就是 \(O(nm)\) 的了。

让你们欣赏一下我暴力是怎么草过去的。

#include <cstdio>
#include <cstring>
#include <iostream>
#include <queue>
using namespace std;
const int M = 300005;
int read()
{
	int x=0,f=1;char c;
	while((c=getchar())<'0' || c>'9') {if(c=='-') f=-1;}
	while(c>='0' && c<='9') {x=(x<<3)+(x<<1)+(c^48);c=getchar();}
	return x*f;
}
int n,m,tot,f[M],dis[M];
struct edge
{
    int v,c,next;
}e[10*M];
struct node
{
    int u,c;
    bool operator < (const node &R) const
    {
        return c>R.c;
    }
};
int id(int x,int y)
{
    return (x-1)*m+y;
}
void add(int u,int v,int c)
{
    e[++tot]=edge{v,c,f[u]},f[u]=tot;
}
void dijk()
{
    priority_queue<node> q;
    memset(dis,0x3f,sizeof dis);
    q.push(node{1,0});dis[1]=0;
    while(!q.empty())
    {
        int u=q.top().u,t=q.top().c;q.pop();
        if(t>dis[u]) continue;
        for(int i=f[u];i;i=e[i].next)
        {
            int v=e[i].v,c=e[i].c;
            if(dis[v]>dis[u]+c)
            {
                dis[v]=dis[u]+c;
                q.push(node{v,dis[v]});
            }
        }
        int x=(u-1)/m+1,y=(u-1)%m+1;
        for(int i=1;i<x;i++)
        {
            int v=id(x-i,y),c=i+1;
            if(dis[v]>dis[u]+c)
            {
                dis[v]=dis[u]+c;
                q.push(node{v,dis[v]});
            }
        }
    }
}
signed main()
{
    n=read();m=read();
    for(int i=1;i<=n;i++)
        for(int j=1;j<m;j++)
        {
            int x=read();
            add(id(i,j),id(i,j+1),x);
            add(id(i,j+1),id(i,j),x);
        }
    for(int i=1;i<n;i++)
        for(int j=1;j<=m;j++)
        {
            int x=read();
            add(id(i,j),id(i+1,j),x);
        }
    dijk();
    printf("%d\n",dis[id(n,m)]);
}

Encounter and Farewell

题目描述

有 \([0,2^n)\) 这些点，给定一个长度为 \(m\) 的数组 \(a\)，如果两个点之间的异或值 \(\not= a_i\)，就可以将这两个点连边，尝试构造出一棵合法的生成树，如果不存在这样的生成树输出-1。

\(1\leq n\leq 18\)

解法

我一开始想直接构造生成树发现做不动，正解需要考虑生成树存在的条件。

如果原图任意两点之间都可以到达，那说明存在生成树。尝试翻译这个条件，就相当于存在一条路径可以互相到达，设数组 \(a\) 关于全集的补集是 \(b\)，那么就相当于异或若干次 \(b\) 中的元素可以得到 \([0,2^n)\) 的所有元素。

那么不就是看 \(b\) 的线性基是否满秩吗？

判断有无解之后怎么构造最终的答案呢？线性基里的数是若干个原数异或的结果，那么对于每个点我们只用考虑线性基里原数的边即可，暴力枚举每条边，时间复杂度 \(O(n\log n)\)

#include <cstdio>
const int M = 1000005;
int read()
{
	int x=0,f=1;char c;
	while((c=getchar())<'0' || c>'9') {if(c=='-') f=-1;}
	while(c>='0' && c<='9') {x=(x<<3)+(x<<1)+(c^48);c=getchar();}
	return x*f;
}
int n,m,k,cnt,a[M],b[M],fa[M],fb[M];
int find(int x)
{
	if(x!=fa[x]) return fa[x]=find(fa[x]);
	return fa[x];
}
signed main()
{
	n=read();m=read();
	while((2<<k)<n) k++;
	for(int i=1;i<=m;i++)
		fb[read()]=1;
	for(int i=1;i<n;i++)
	{
		if(fb[i]) continue;
		int x=i;
		for(int j=k;j>=0 && x;j--)
		{
			if((x&(1<<j)) && !a[j])
			{
				a[j]=x;b[j]=i;cnt++;
				break;
			}
			if(x&(1<<j)) x^=a[j];
		}
	}
	for(int i=0;i<n;i++) fa[i]=i;
	if(cnt<=k) {puts("-1");return 0;}
	for(int i=0;i<n;i++)
		for(int j=0;j<=k;j++)
			if(find(i)!=find(i^b[j]))
			{
				printf("%d %d\n",i,i^b[j]);
				fa[find(i)]=find(i^b[j]);
			}
}