ISIJ2018 训练题 sequences 题解

xiaoh 2020-7-17

题意

给定一个长度为 $n$ 的序列 $x$ ，保证 $x_1$ 与 $x_2$ 互素且序列严格单调递增。若一个序列的首项为 $0$ ,单调递增且任意相邻两项差在集合 $x$ 中，则称其满足条件。求不被所有满足条件的序列包含的最大的数。

数据范围:

对于 40% 的数据， $1<n<6，x_1>1，x_n<1000$ ；

对于另外 30% 的数据， $n=2，x_n<10^9$ ；

对于另外 30% 的数据， $1<n<6，1<x_1<10^{6-n}，x_2>10^{n+11}，x_n<10^{n+12}$ 。

题解

注意到 $x_1\leq 10^5$ ,所以我们不妨以 $x_1$ 为模，将所有余数作为点建图。将所有 $i->(x_j+i)\mod x_1$ 作为边，边权为 $x_j$ ，那么每次给序列加上一个元素即为一条边的转移。显然，在以 $0$ 为起点跑单源最短路后，所有点的距离即为这个余数下能够构造出的最小的数。而由于可以加上任意多个 $x_1$ ，所以大于等于这个数的所有余数都会被某个序列包含。所以答案为 $\max \{dis_i-x_1\}$ 。

Code

#include<bits/stdc++.h>
using namespace std;
template<typename T>
inline void read(T &x)
{
	x=0;
	int f=1;
	char ch=getchar();
	while(ch<'0'||ch>'9')
	{
		if(ch=='-') f=-1;
		ch=getchar();
}
	while(ch>='0'&&ch<='9') x=x*10+(ch^48),ch=getchar();
	x*=f;
	return;
}	
template<typename T>
void write(T x)
{
	if(x<0) putchar('-'),x=-x;
	if(x>=10) write(x/10);
	putchar(x%10+'0');
	return;
}
const int MAXN=7,MAXM=100010;
const long long inf=1e18+7;
int n;
long long x[MAXN];
int tot=1;
int edge[MAXN*MAXM*2],nxt[MAXN*MAXM*2],hd[MAXN*MAXM*2];
long long w[MAXN*MAXM*2];
inline void add_edge(int u,int v,long long c)
{
    edge[tot]=v,w[tot]=c;
    nxt[tot]=hd[u],hd[u]=tot++;
}
struct node{
    int pos;
    long long val;
    friend bool operator < (node a,node b)
    {
        return a.val>b.val;
    }
};
priority_queue<node> q;
bool book[MAXM];
long long dis[MAXM];
inline void Dijkstra()
{
    for(int i=1;i<x[1];++i) dis[i]=inf;
    q.push({0,0});
    while(!q.empty())
    {
        int x=q.top().pos;q.pop();
        if(book[x]) continue;
        book[x]=1;
        for(int i=hd[x];i;i=nxt[i])
        if(dis[edge[i]]>dis[x]+w[i])
        {
            dis[edge[i]]=dis[x]+w[i];
            q.push({edge[i],dis[edge[i]]});
        }
    }
}
long long ans=0;
int main()
{
    read(n);
    for(int i=1;i<=n;++i) read(x[i]);
    if(n==2)
    {
        write(x[1]*x[2]-x[1]-x[2]),putchar('\n');
        return 0;
    }
    for(int i=0;i<x[1];++i)
    for(int j=2;j<=n;++j) add_edge(i,(i+x[j])%x[1],x[j]);
    Dijkstra();
    for(int i=0;i<x[1];++i) ans=max(ans,dis[i]-x[1]);
    write(ans),putchar('\n');
	return 0;
}