发表于 | 分类于

  • 题目

    • C

      判断两线段是否相交，虽然计算几何不是现在主要训练的专题，但基础掌握不牢固。需要仔细看看比赛时是怎么WA的。

    • D Number

      仔细计算时间复杂度，此题只需要打出 $\sqrt{n}(7000)$ 以内的素数
      设函数 $p(x)$ 表示$x$以内的素数个数，暴力的时间复杂度为
      $$p(\sqrt{n})\times p(\sqrt[3]{n})\times p(\sqrt[4]{n})$$
      仅为$4e7$
      另外看清楚是多组数据还是一组数据，如果是一组数据就不要考虑预处理了

  • 总结

    如果碰到了不会搞的题目，如果可以一定要尝试暴力和打表找规律，D题时间复杂度没算对直接暴力也过了。L题实际就是打表找规律，但是没有去打表找规律，错失一题。

发表于 | 分类于

题目描述

qwb闲着无聊，就开始拆自己的电脑，他发现主板上某个元件可以视作如图所示无限长的电路。已知该电路由三种不同的电阻r1,r2,r3构成，他想要计算ab之间的电阻。

题解

设答案为$R$，因为图中电路是无限延伸的，去掉最左边的$r_1,r_2,r_3$，电路还是不变的。因此把除了最左边$r_1,r_2,r_3$的电路当作原电路，将图化简为如图只有两个并联电路的情况，得出下式
$$R=r_1+r_3+{ {R*r_2}\over{R+r_2} }$$
化简即可求得$R$

发表于 | 分类于

题解

现在一次必须合并 k 堆k∈[L,R]，也就是说合并的堆数不小于L，不大于R。
每次合并的耗费。依然是石子总重。
那么显然合并前。我们需要知道。有多少堆合并了。
对于堆数不在[L,R]的，不能合并。
令：$dp[k][l][r]$表示
区间$[l,r]$合并成k段的耗费。
$w[l,r]$表示，区间$[l,r]$石子总重。
所以：
$$dp[k][l][r]=\min_{t=l+k-2}^{r-1}(dp[k-1][l][t]+dp[1][t+1][r])$$
特别的当：
$$dp[1][l][r]=\min_{k=L}^R(dp[k][l][r]+w[l , r])$$

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#include <cstdio>
#include "iostream"
#include <cstring>
#include <algorithm>
#include <cmath>
#include <vector>
using namespace std;
#define FOP freopen("input.txt","r",stdin)
#define Met(x,y) memset(x,y,sizeof x)
typedef long long ll;
typedef unsigned long long ull;
const ll INF = 1e18;
const ll MAXN=110;
const ll MOD=1000000007;
ll dp[MAXN][MAXN][MAXN];
ll a[MAXN],s[MAXN];
int main(int argc, char const *argv[]) {
    ll n,L,R;
    while (cin>>n>>L>>R) {
        for(int i=1;i<=n;++i)
            scanf("%lld",&a[i]);
        s[0]=0;
        for(int i=1;i<=n;++i)
            s[i]=s[i-1]+a[i];
        Met(dp,0x3f);
        for(int k=1;k<=R;++k)
            for(int l=1;l<=n-k+1;++l)
                dp[k][l][l+k-1]=0;
        for(int len=L;len<=n;++len)
            for(int l=1;l<=n-len+1;++l)
                for(int k=2;k<=len && k<=R;++k)
                {
                    ll r=l+len-1;
                    for(int t=l+k-2;t<=r-1;++t)
                        dp[k][l][r]=min(dp[k][l][r],dp[k-1][l][t]+dp[1][t+1][r]);
                    if(k>=L && k<=R)
                    dp[1][l][r]=min(dp[1][l][r],dp[k][l][r]+s[r]-s[l-1]);
                }
        if(dp[1][1][n]>=dp[0][0][0])
            puts("0");
        else printf("%lld\n", dp[1][1][n]);
    }
    return 0;
}