P2662 牛场围栏

题目背景

小L通过泥萌的帮助，成功解决了二叉树的修改问题，并因此写了一篇论文，

成功报送了叉院（羡慕不？）。勤奋又勤思的他在研究生时期成功转系，考入了北京大学光华管理学院！毕业后，凭着自己积累下的浓厚经济学与计算机学的基础，成功建设了一个现代化奶牛场！

题目描述

奶牛们十分聪明,于是在牛场建围栏时打算和小L斗智斗勇！小L有N种可以建造围栏的木料，长度分别是l1,l2 … lN，每种长度的木料无限。

修建时，他将把所有选中的木料拼接在一起，因此围栏的长度就是他使用的木料长度之和。但是聪明的小L很快发现很多长度都是不能由这些木料长度相加得到的，于是决定在必要的时候把这些木料砍掉一部分以后再使用。

不过由于小L比较节约，他给自己规定：任何一根木料最多只能削短M米。当然，每根木料削去的木料长度不需要都一样。不过由于测量工具太原始，小L只能准确的削去整数米的木料，因此，如果他有两种长度分别是7和11的木料，每根最多只能砍掉1米，那么实际上就有4种可以使用的木料长度，分别是6， 7，10, 11。

因为小L相信自己的奶牛举世无双，于是让他们自己设计围栏。奶牛们不愿意自己和同伴在游戏时受到围栏的限制，于是想刁难一下小L，希望小L的木料无论经过怎样的加工，长度之和都不可能得到他们设计的围栏总长度。不过小L知道，如果围栏的长度太小，小L很快就能发现它是不能修建好的。因此她希望得到你的帮助，找出无法修建的最大围栏长度。

这一定难不倒聪明的你吧！如果你能帮小L解决这个问题，也许他会把最后的资产分给你1/8哦！

输入输出格式

输入格式：

输入的第一行包含两个整数N, M，分别表示木料的种类和每根木料削去的最大值。以下各行每行一个整数li(1< li< 3000),表示第i根木料的原始长度。

输出格式：

输出仅一行，包含一个整数，表示不能修建的最大围栏长度。如果任何长度的围栏都可以修建或者这个最大值不存在，输出-1。

输入输出样例

输入样例#1：

2 1

7 11

输出样例#1：

说明

40 % ：1< N< 10, 0< M< 300

100 % ：1< N< 100, 0< M< 3000

CaptainSlow的题解

规模较小，直接上可行解DP（有个叫_DYT大佬搞了一波分析证明这个解若存在是小于$9 \times 10^6$）当然我们要考虑更好的解法，如果是初中我也会写可行解DP，当然考场上实在写不出来我还是应该打个暴力骗骗满分的。

PART 1 无解？

问题确实可能无解，分两种情况：

存在数字1

如果有1这个数字，那么所有的数字都可以被表示出来，就不存在不能表示出的数了
所有数的gcd大于1

设这些数为$A_1, A_2,...,A_n$，设$q=gcd(A_1, A_2,...,A_n)$，则$q|A_1x_1+A_2x_2+...+A_nx_n$($x_1,x_2,...,x_n \in Z$)。这是一个很显然的结论，学习整除的时候是必回讲到的。所以，由于$q > 1$，必然存在不能表示出来的数，即$\forall q \nmid m$，都是不符合条件的数，显然这个$m$是可以到无穷大的。

这两者情况我们可以先特判出来，而剩下的就是$q=1$的情况了，这样的话是肯定存在最大的不能表示出来的数的。这个很显然。

PART 2 寻找

我们如何去寻找这个最大的不能被表示出来的数呢？我们考虑所有可以被表示出来的数构成的数集$S$，由最小数原理可知，$S$中一定存在最小的$s_0$。考虑模$s_0$的每一个剩余系，记为$K_i=\lbrace x|x \equiv i\pmod{s_0}\rbrace,i=0,1,2,...,s_0-1$。显然$s_0=min(A_i)$。对$\forall K_i$，由最小数原理，存在最小的能被表示出来的$t_i$，$t_i=s_0*p+i$，显然$p>0$，否则与$s_0$的最小性矛盾。那么对每一个$K_i$，最大不能被表示出来的数就是$s_0*(p-1)+i$。这样，问题就转化为了求每一个这样的$t_i$，这时候，我们就引入这个被称为剩余系最短路的算法了。我们可以把每个剩余系$K_i$抽象为图中的点，那么连接它们的边就是$A_i$中的那些数。然后就用普通的最短路更新方式就可以了。我选择了用Dijkstra算法。

#include <cstdio>

#include <cstring>

#include <algorithm>

const int ARSIZE = 4005;

const int INF = 0x7f7f7f7f;

int N, M, L[ARSIZE], tot_l = 0, Q[ARSIZE];

bool exist[ARSIZE] = {0}, used[ARSIZE] = {0};

inline int gcd(int a, int b) {

    for (a < b ? std::swap(a, b) : (void)0; b; std::swap(a, b)) a %= b;

    return a;

}

int dijkstra();

int main() {

    scanf("%d%d", &N, &M);

    int j, li, gd = 0;

    for (int i = 0; i < N; i++) {

        scanf("%d", &li);

        gd = gcd(gd, li);

        for (j = 0; j <= M && j < li; j++) exist[li - j] = true, gd = gcd(li - j, gd);  // 很多人WA，半天查不出错，很可能就是只算了所有L[i]的gcd

    }

    if (exist[1] || gd > 1) puts("-1");

    else printf("%d\n", dijkstra());

    return 0;

}

int dijkstra() {

    memset(Q, 0x7f, sizeof(Q));

    int i, v, k;

    for (Q[0] = 0, i = 2; i <= 3000; i++)   // 初始化

        if (exist[i]) L[tot_l++] = i;

    int MOD = L[0];

    while (true) {

        for (i = 0, k = -1; i < MOD; i++)

            if (!used[i] && (k == -1 || Q[i] < Q[k])) k = i;

        if (k == -1) break;

        used[k] = true;

        for (i = 1; i < tot_l; i++)

            if (!used[v = (k + L[i]) % MOD]) Q[v] = std::min(Q[v], Q[k] + L[i]);    // 更新其他剩余系

    }

    int res = -1;

    for (i = 1; i < MOD; i++) res = std::max(res, Q[i] - MOD);

    return res;

}

数学题(num)

题目描述

老师给小C 布置了一道数学题作为家庭作业：

给定一个数k，写出k 的倍数中各位之和最小为多少？

小C 不会做，希望你能帮帮他。

输入描述

一行一个正整数k。

输出描述

一行一个正整数，表示答案。

输入样例& 输出样例

num1.in

6

num1.out

3

num2.in

41

num2.out

5

样例说明

当k = 6 时，6 * 2 = 12，1 + 2 = 3，可以证明最小答案为3。
当k = 41 时，41 * 271 = 11111，1 + 1 + 1 + 1 + 1 = 5，可以证明最小答案为5。

数据范围

1-6	$ \leq 20$
7-20	$\leq 10^5$

刘老爷算法

考虑建立模n意义下的n个点，用追加数字的方式建边，由于是枚举n的倍数，所以到0点的最短路即为答案。

起点为1-9，建边边权，0-9连向摸意义下的多一位的点。

时间复杂度$O(10 n \log n)$，注意n=1时要特判掉，不然根本就没建图，跑出来答案为INF。

#include<iostream>

#include<cstring>

#include<cmath>

#include<cstdio>

#include<set>

#include<map>

#include<queue>

#include<vector>

#include<algorithm>

#include<string>

template<class T>T read(T&x)

{

	T data=0;

	int w=1;

	char ch=getchar();

	while(!isdigit(ch))

	{

		if(ch=='-')

			w=-1;

		ch=getchar();

	}

	while(isdigit(ch))

	{

		data=data*10+ch-'0';

		ch=getchar();

	}

	return x=data*w;

}

using namespace std;

typedef pair<int,int> pii;

typedef long long ll;

const int INF=0x3f3f3f3f;

const int MAXN=1e5+7;

int n;

struct edge

{

	int nx,to,w;

}e[MAXN*10];

int head[MAXN],ecnt;

void addedge(int x,int y,int w)

{

	e[++ecnt].to=y,e[ecnt].w=w;

	e[ecnt].nx=head[x],head[x]=ecnt;

}

priority_queue <pii> H;

bool vis[MAXN];

int dis[MAXN];

int main()

{

	freopen("num.in","r",stdin);

	freopen("num.out","w",stdout);

	read(n);

	if(n==1) // edit 1

	{

		puts("1");

		return 0;

	}

	for(int i=1;i<n;++i)

		for(int j=0;j<10;++j)

			addedge(i,(i*10+j)%n,j);

	fill(dis,dis+n,INF);

	for(int i=1;i<=9;++i)

	{

		dis[i]=i;

		H.push(pii(-dis[i],i));

	}

	while(H.size())

	{

		int x=H.top().second;

		H.pop();

		if(vis[x])

			continue;

		vis[x]=1;

		for(int i=head[x];i;i=e[i].nx)

		{

			int y=e[i].to,w=e[i].w;

			if(dis[y]>dis[x]+w)

			{

				dis[y]=dis[x]+w;

				H.push(pii(-dis[y],y));

			}

		}

	}

	printf("%d\n",dis[0]);

	return 0;

}

标解

LG2662 牛场围栏和 test20181107 数学题-LMLPHP

围栏

LG2662 牛场围栏 和 test20181107 数学题

P2662 牛场围栏

题目背景

题目描述

输入输出格式

输入输出样例

说明

CaptainSlow的题解

PART 1 无解？

PART 2 寻找

数学题(num)

题目描述

输入描述

输出描述

输入样例& 输出样例

样例说明

数据范围

刘老爷算法

LG2662 牛场围栏和 test20181107 数学题