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
",dis[id(n,m)]);
}
Encounter and Farewell
题目描述
有 ([0,2^n)) 这些点，给定一个长度为 (m) 的数组 (a)，如果两个点之间的异或值 (
ot= a_i)，就可以将这两个点连边，尝试构造出一棵合法的生成树，如果不存在这样的生成树输出-1。
(1leq nleq 18)
解法
我一开始想直接构造生成树发现做不动，正解需要考虑生成树存在的条件。
如果原图任意两点之间都可以到达，那说明存在生成树。尝试翻译这个条件，就相当于存在一条路径可以互相到达，设数组 (a) 关于全集的补集是 (b)，那么就相当于异或若干次 (b) 中的元素可以得到 ([0,2^n)) 的所有元素。
那么不就是看 (b) 的线性基是否满秩吗？
判断有无解之后怎么构造最终的答案呢？线性基里的数是若干个原数异或的结果，那么对于每个点我们只用考虑线性基里原数的边即可，暴力枚举每条边，时间复杂度 (O(nlog 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
",i,i^b[j]);
fa[find(i)]=find(i^b[j]);
}
}