标签 - UVa

? 解题记录 ? ? UVa ? ? 动态规划 ?    2017-09-14 23:35:23    365    0    0
  这道题的DP其实可以换一个角度出发思考,因为我们可以随意调整一个块,所以每一个块有字母的种类个数肯定是该块的最优块数。接下来我们只需要确定它们的排布就可以了。我们这样建立状态。dp[i][j]表示第i个块的第一个字母为j时的最少联通个数,这样我们就可以通过dp[i - 1][0~25]推出dp[i][0 ~25]了。  #include<cstdio> #include<cstring> #include<algorithm> using namespace std; const int ma
? 解题记录 ? ? UVa ? ? 筛法 ?    2017-09-14 21:19:03    492    0    0
这是蓝书上一道很经典的数论题,位于P124页,只不过题意有一些细微偏差,但是不影响本题结论的正确性,做法可以看:洛谷P2398。我们只需要进行一次预处理,下底分块,保留SQRT(n)的查询就行了。虽然时间上Vjudge垫底,但是毕竟我弱啊……,下面是一段代码。#include<cstdio> #include<algorithm> using namespace std; const int maxn = 4e6 + 5; long long f[maxn]; int&n