广东哪里网站建设,有没有在线做动图的网站,桓台网站制作,银行官网登录入口《算法竞赛快冲300题》将于2024年出版#xff0c;是《算法竞赛》的辅助练习册。 所有题目放在自建的OJ New Online Judge。 用C/C、Java、Python三种语言给出代码#xff0c;以中低档题为主#xff0c;适合入门、进阶。 文章目录 题目描述题解C代码Java代码Python代码 “
平…《算法竞赛·快冲300题》将于2024年出版是《算法竞赛》的辅助练习册。 所有题目放在自建的OJ New Online Judge。 用C/C、Java、Python三种语言给出代码以中低档题为主适合入门、进阶。 文章目录 题目描述题解C代码Java代码Python代码 “
平方和” 链接
http://oj.ecustacm.cn/problem.php?id1754 题目描述
【题目描述】 存在n个变量xi现在告诉你每个变量的取值范围在[li, ri]中。 假设这n个数字的平方和为S求总共存在多少种不同的S。 【输入格式】 输入第一行为正整数n。(1≤n≤100) 接下来n行为两个整数li和ri。(1≤li,ri≤100)。 【输出格式】 输出一个数表示答案。 【输入样例】
5
1 2
2 3
3 4
4 5
5 6【输出样例】
26题解 如果暴力统计所有可能的S需要用对n个变量进行组合例如样例x1可选1或2x2可选2或3…等等最多可能有 2 5 2^5 25种组合。当n100li1ri100时可能有 10 0 100 100^{100} 100100种组合。 是否可以反过来思考判断某个平方和是否存在最小的平方和是n1liri1时平方和等于1最大是100个100平方和等于 100 × 10 0 2 1 0 6 100×100^210^6 100×1002106。最多只有 1 0 6 10^6 106个平方和。 定义dp[]若dp[i] 1表示平方和i存在。 处理到第i个取值范围[ll, rr]时新的平方和范围扩展到[mmin, mmax]mmin表示所有取值范围最小值的平方和、mmax表示所有取值范围最大值的平方和。 用k遍历[ll, rr]中的每个数然后判断dp[j]是否存在mmin≤j≤mmax。 1如果dp[j - k*k] 1说明以前算过i j - k*k这个平方和显然现在可以计算出i k*k j这个平方和。 2不过如果j - k*k比以前算出的最小值还小显然不对所以需要排除j - k*k mmin - ll*ll的情况。
【笔记】 简单DP 。
C代码 代码第12行j需要反过来循环请思考为什么。
#include bits/stdc.h
using namespace std;
const int N 1000000 10;
bool dp[N];
int main(){int n; cin n;int ll, rr, mmin 0, mmax 0;dp[0] 1;for(int i 1; i n; i) {cin ll rr;mmin ll * ll, mmax rr * rr; //计算最小平方和、最大平方和for(int j mmax; j mmin; j--) {dp[j] 0;for(int k ll; k rr; k) {if(j - k*k mmin - ll*ll) break; //如果j - k*k小于以前的最小平方和排除if(dp[j - k*k] 1){ dp[j] 1; break;}}}}int ans 0;for(int i mmin; i mmax; i) ans dp[i];coutansendl;return 0;
}Java代码
import java.util.*;
public class Main {static final int N 1000000 10;static boolean[] dp new boolean[N];public static void main(String[] args) {Scanner input new Scanner(System.in);int n input.nextInt();int ll, rr, mmin 0, mmax 0;dp[0] true;for(int i 1; i n; i) {ll input.nextInt();rr input.nextInt();mmin ll * ll;mmax rr * rr;for(int j mmax; j mmin; j--) {dp[j] false;for(int k ll; k rr; k) {if(j - k*k mmin - ll*ll) break;if(dp[j - k*k] true) { dp[j] true; break; }}}}int ans 0;for(int i mmin; i mmax; i) if(dp[i] true) ans; System.out.println(ans);input.close();}
}Python代码
N 1000000 10
dp [False] * N
n int(input())
mmin, mmax 0, 0
dp[0] True
for i in range(1, n1):ll, rr map(int, input().split())mmin ll * llmmax rr * rrfor j in range(mmax, mmin-1, -1):dp[j] Falsefor k in range(ll, rr1):if j - k*k mmin - ll*ll: breakif dp[j - k*k] True:dp[j] Truebreak
ans 0
for i in range(mmin, mmax1):if dp[i] True: ans 1
print(ans)
