JZM 的套题（暴力，DP）

\rm JZM

JZM 即将奔赴

\rm NOI

NOI 考场，为了让同学们赶上自己的千分之一水平，刻意出了两道水题给同学们练练。

1.曾经的代码

\rm JZM

JZM 小学一年级的时候曾写过一份代码，来判断一个数是不是 3 的倍数，一般来说，只需要判断

x\%3

x%3 是多少，但是，

\rm JZM

JZM 精益求精，又求出了

x 每一位上的数字和

y ，观察

y\%3

y%3 的值……最终他把

x 和

y 加起来得到了

N 。

此时，灯突然黑了，意识到了不妙，

\rm JZM

JZM 马上按了一下 Ctrl + s ，顺便把

N 都记了下来。果然，下一秒，电脑屏幕就黑了，整栋楼停电。

\rm JZM

JZM 没法好好地在黑暗中演算，于是想你询问，对于每个

N ，能够得到它的最小

x 是多少，或者告诉他不存在。

一共

≤

5000

T\leq5000

T≤5000 组数据，每组数据一个数

∈

[

]

N\in [1,10^{18}]

N∈[1,1018] 。

题解

好熟悉啊，有一种见到

\rm ABC~T1

ABC T1 和

\rm Div2~T1

Div2 T1 的亲切感。

我们发现答案和

N 相差不超过

∗

9*18

9∗18 ，直接暴力枚举得了。

开了两秒时限，只要不是写的太烂都能过。

#include<set>

#include<queue>

#include<cmath>

#include<vector>

#include<cstdio>

#include<cstring>

#include<iostream>

#include<algorithm>

using namespace std;

#define MAXN 100005

#define ENDL putchar('\n')

#define LL long long

#define DB double

#define lowbit(x) ((-x) & (x))

LL read() {

	LL f = 1,x = 0;char s = getchar();

	while(s < '0' || s > '9') {if(s=='-')f = -f;s = getchar();}

	while(s >= '0' && s <= '9') {x=x*10+(s-'0');s = getchar();}

	return f * x;

}

int n,m,i,j,s,o,k;

LL sol(LL nm) {

	LL as = nm;

	while(nm) as += nm%10,nm /= 10;

	return as;

}

int main() {

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

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

	int T = read();

	while(T --) {

		LL N = read();

		bool flag = 0;

		for(LL i = max(1ll,N-18*9);i <= N;i ++) {

			LL as = sol(i);

			if(as == N) {

				printf("%lld\n",i);

				flag = 1; break;

			}

		}

		if(!flag) printf("-1\n");

	}

	return 0;

}

2.童年的积木

\rm JZM

JZM 在玩

N 块积木，每块有一个高度

a_i

ai ，两块积木能够拼接在一起，当且仅当

gcd

⁡

\gcd>1

gcd>1。

\rm JZM

JZM 一阵乱拼，竟拼出了最长的一个上升序列，现在问你它的长度是多少。

题解

如果把每个数向下一位能接的数连边，一定会是个

\rm DAG

DAG ，那么我们优化一下，把每个数的所有质因数处理出来，然后优化建图，从大的数开始进行

\rm DP

DP ，也是比较简单的。

#include<set>

#include<queue>

#include<cmath>

#include<vector>

#include<cstdio>

#include<cstring>

#include<iostream>

#include<algorithm>

using namespace std;

#define MAXN 100005

#define ENDL putchar('\n')

#define LL long long

#define DB double

#define lowbit(x) ((-x) & (x))

LL read() {

	LL f = 1,x = 0;char s = getchar();

	while(s < '0' || s > '9') {if(s=='-')f = -f;s = getchar();}

	while(s >= '0' && s <= '9') {x=x*10+(s-'0');s = getchar();}

	return f * x;

}

int n,m,i,j,s,o,k;

int a[MAXN];

int dp[MAXN];

int pr[MAXN],cp;

vector<int> p[MAXN];

bool f[MAXN];

int main() {

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

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

	for(int i = 2;i <= 100000;i ++) {

		if(!f[i]) {

			for(int j = i;j <= 100000;j += i) {

				p[j].push_back(i);

				if(j > i) f[j] = 1;

			}

		}

	}

	int T = read();

	while(T --) {

		n = read();

		for(int i = 1;i <= 100000;i ++) dp[i] = 0;

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

			a[i] = read();

		}

		sort(a + 1,a + 1 + n);

		int ans = 0;

		for(int i = n;i > 0;i --) {

			int dpp = 0,le = p[a[i]].size();

			for(int j = 0;j < le;j ++) {

				dpp = max(dpp,dp[p[a[i]][j]]);

			}

			dpp ++;

			ans = max(ans,dpp);

			for(int j = 0;j < le;j ++) {

				dp[p[a[i]][j]] = max(dp[p[a[i]][j]],dpp);

			}

		}

		printf("%d\n",ans);

	}

	return 0;

}

巴特西

JZM 的套题（暴力，DP）

1.曾经的代码

2.童年的积木

最新文章

热门文章