Unidirectional TSP
UVA116定义:$dp[i][j]$为从第$i$行第$j$列走到最后一列的最小整数和,$Road[i][j]$为在最优方案下第$i$行第$j$列的下一步的行数(记录路径),$Map[i][j]$表示第$i$行第$j$列的数。代码从0编号到$n-1$,而题目是1到$n$,所以会有些不一样。初始化:123456memset(dp, 0x0, sizeof(dp));memset(Road, 0x0, sizeof(Road));//从第i行第n列走到顶显然就是他本身。for (int i = 0; i < m; ++i) { dp[i][n - 1] = Map[i][n - 1];}转移方程:由题目可知,第i行第j列可由第j+1列的i+1行、i行以及i-1行转移得到(分别对应右上,右,右下)。因此,转移方程为:
dp[i][j]=min(dp[i-1][j+1],dp[i][j+1],dp[i+1][j])+Map[i][j]即为$j+1$列的结果在拼接上第$j$列本身。因为题目中的矩阵式循环的,因此方变为:
dp[i][j]=min(\\dp[(i-1+m) ...
Yet Another Multiple Problem(同余方程+BFS)
SP12810
There are tons of problems about integer multiples. Despite the fact that the topic is not original, the content is highly challenging. That’s why we call it “Yet Another Multiple Problem”. In this problem, you’re asked to solve the following question: Given a positive integer n and m decimal digits, what is the minimal positive multiple of n whose decimal notation does not contain any of the given digits?InputThere are several test cases.For each test case, there are two lines. The fir ...
coding关联QT项目(Git)
下载git
设置环境变量。
在coding上创建分支Branch
绑定QtCreator点击文件/新建文件或项目/Import Project/Git CloneRepository:https://e.coding.net/luoxiao23333/ChrtScript.git(仓库链接)Branch:Branch,即当前要同步的分支名Path:自己本地仓库要放在电脑哪里Dictory:本地仓库目录名当分支中没有.pro文件时,QtCreator是打不开这个项目的(非QT项目),但是可以在文件管理器中打开。可以在洛阳项目中测试,这个项目里有pro文件而且是废弃的,相应的仓库链接为https://e.coding.net/luoxiao23333/luoyang.git。
在QtCreator中,带点击工具/Git/Remote Repository/Pull可以将当前分支的所有代码拉去下来(仓库代码更新本地代码)。本地代码在修改前先Pull一下,使得两端同步。在本地代码编写完后,点击工具/Git/Local Repository/Commit左边的Description填写改动描述 ...
Semi-prime H-numbers
UVA11105
线性筛即可。
1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556#include <iostream>#include <algorithm>#include <cmath>#include <vector>using namespace std;const int MAXN = 1000001;bool IsNotHPrimer[MAXN + 1];bool IsSemiHPrimer[MAXN + 1];int sum[MAXN + 1];vector<int> HPrimer;void InitIsHPrimer() { for (int i = 5; i <= MAXN; i += 4) { if (IsNotHPrimer[i]) { continue; } HPrimer.push_ba ...
串折叠 Folding
UVA1630这是一个区间动态规划定义:$dp[i][j]$为$i$到$j$的字符串能压缩成的最小长度,$dps[i][j]$保存$i$到$j$的字符串能压缩成的最短字符串,$S[i]$表示第$i$个字符(从1开始编号)。初始化:
dp[i][i]=1\\dps[i][i]=S[i]转移方程:
dp[i][j]=min(dp[i][k]+dp[k+1][j])(i\leq k< j)经典的区间$dp$枚举中转点,那么相应的:if(dp[i][j]>dp[i][k]+dp[k+1][j]\\dps[i][j]=dps[i][k]+dps[k+1][j]
if(IsCircular(i,j,Len)\\dp[i][j]=min(dp[i][j],dp[i][i+Len-1]+2+Digit[Section/Len])(1\leq Len\leq Section)如果从$i$开始到$j$是一个循环节长度为$Len$的循环,那么$dp[i][j]$可以压缩,$dp[i][i+Len-1]$表示从i到第一个循环节结束,$+2$表示加上括号的长度,而$Section$为当前枚举的区间的长度,那么 ...
仓库守卫 Storage Keepers
UVA10163这道题需要两次dp
1. 求最小安全指数最大值定义:$dp[i][j]$为考虑前i个人看守前j个仓库最小安全指数最大值,$SafetyIndex[i]$为第$i$个人的能力值。初始化:$dp[i][0]=inf$(常数/0=无穷大)剩下的$dp=0$转移方程:
dp[i][j]=max(dp[i][j], min(dp[i - 1][x], SafetyIndex[i] / (j - x))),(0\leq x= 上一问求出的结果)\\dp[i][j] = min(dp[i][j], dp[i - 1][x] + SafetyIndex[i])AC代码1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768#include<iostream>#include<string>#include<cstring>#include<algo ...
代码编辑方式
讨论时间:2020年5月20日讨论内容:关于代码的显示和编辑方式
我们小组认为,对于代码的显示方式,不一定是文本的形式,也可以是可视化编程的形式,比如图形节点式的:理由如下:(1)我们的软件应该为非技术人员可以更轻松地通过有意义的方式进行数据分析处理。我们的软件功能重点在于对数据的可视化呈现,而这种方式能在提供相较于普通统计分析软件更大自由度的同时更容易使用。比如说很多的游戏开发完全靠UE4提供的图节点式编程来完成。(2)可视化编程适用于对各个高度封装的模块进行组合。这种图节点式的编程,我们可以: 融入函数式编程的思想,将一个复杂的流程封装成一个子节点进行调用。 通过这种方式,用户可以轻易的将自己用其他语言编写的程序变成可视化编程模块中的一个节点。我们可以通过定义一个简单的进程通信接口,或者为常用编程语言编写简单的库,用户就能够轻易的在自己的程序中选择输入输出的变量,然后将自己的程序导入成为一个节点.这样就能轻易的分析一个或多个程序的运行结果,同时拥有一定的多程序管理功能。 例如可以调用我们编写好的CS库:12345678int time = clock();//获取系统当 ...
佳佳的筷子 Chopsticks
UVA10271首先,将筷子逆序读入,即使得读入的$Chopsticks$数组中的元素时降序的。这样在考虑前$i$只筷子时可以选$i$和$i-1$,而第三只(最大那只)在$i-1$之前选一个没被用过的即可。定义:$dp[i][j]$为考虑前i个筷子并选了j个三元组后的最小权值和。初始化:$dp[i][0]=0$不选择任何筷子权值和当然是0转移方程:
dp[i][j] = min(dp[i - 1][j],dp[i - 2][j - 1] + Square(Chopsticks[i - 1] - Chopsticks[i]));决策为不选或者选择第$i$和$i-1$只作为$a$和$b$。AC代码:123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051#include<iostream>#include<string>#include<cstring>#include<algorithm>#include< ...
免费糖果 Free Candies
UVA10118定义:$dp[a][b][c][d]$为第0列取了$a$颗糖果,第1列$b$颗,第二列$c$颗,第三列$d$后剩下的糖果还能最多再装进口袋多少个。那么答案就是$dp[0][0][0][0]$,即考虑所有糖果。$Candies[i][j]$表示第$i$行第$j$列的糖果颜色。初始化:
dp=-1表示未计算过转移方程:
dp[a][b][c][d]=max(\\dp[a+1][b][c][d]+IsPair(0,a+1),\\dp[a][b+1][c][d]+IsPair(1,b+1),\\dp[a][b][c+1][d]+IsPair(2,c+1),\\dp[a][b][c][d+1]+IsPair(3,d+1)\\)$IsPair(Cow,Raw)$表示拿了$Candies[Col][Raw]$后是否能和篮子中的糖果配对,并放入口袋中。AC代码:代码中以$Raw[0]$表示$a$,$Raw[1]$表示$b$,$Raw[2]$表示$c$,$Raw[3]$表示$d$,以减少代码量。采用二进制压缩的方式表示当前篮子中的糖果集合。123456789101112131415161 ...
切蛋糕 Cake slicing
UVA1629定义:$UpperLeft$为矩形左上角,$LowerRight$为右下角。$dp[UpperLeft.x][UpperLeft.y][LowerRight.x][LowerRight.y]$为由两组坐标确定的矩形区域最少要切割多少长度才能满足要求。$PrefixSum[i][j]$为从(0,0)到(i,j)的矩形区域一共有多少樱桃。(用于O(1)计算出给定矩形区域内樱桃数量)。初始化:
dp=inf转移方程:
dp[UpperLeft.x][UpperLeft.y][LowerRight.x][LowerRight.y]=min(\\
dp[UpperLeft.x][UpperLeft.y][i][LowerRight.y]\\+dp[i+1][UpperLeft.y][LowerRight.x][LowerRight.y]\\+LowerRight.y-UpperLeft.y+1(UpperLeft.x\leq i