Starry

发表于 更新于 分类于 本文字数： 152 阅读时长 ≈ 1 分钟

dp，注意数组索引(⁎⁍̴̛͂▿⁍̴̛͂⁎)✲ﾟ

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
#include <iostream>
#include <cstdio>
#define scan(x) scanf("%lld",&x)
#define f(i,a,b) for(int i=a;i<=b;i++)
#define pn(x,y) printf("###%lld:::%lld\n",x,y)
using namespace std;
typedef long long LL;
const LL N=1e4+1;
LL a[N],b[N],m,t,r[10000001],min1=1e8;
LL dyp(LL x) {
    if(x<min1||r[x])return r[x];
    LL q=0;
    f(i,0,m-1) {
        if(a[i]<=x) {
            q=q<b[i]+dyp(x-a[i])?b[i]+dyp(x-a[i]):q;
        }
    }
    r[x]=q;
    //pn(x,q);
    return q;
}

int main() {
    scan(t);
    scan(m);
    f(i,1,m) {
        scan(a[i-1]);
        min1=min1<a[i-1]?min1:a[i-1];
        scan(b[i-1]);
    }
    //pn(t,m);
    f(i,1,t) {
        dyp(i);
    }
    printf("%lld",dyp(t));
    return 0;
}

发表于 更新于 分类于 本文字数： 101 阅读时长 ≈ 1 分钟

认证点在南海校区，来回晕了两三个小时的车，过去那饭堂还关了…

这次水了180分，菜得一批菜鸡
A过了，B暴力给了70，C看不懂模拟不出来，D水了10（n=2的情况)，E本来想水10可惜没水到，按位异或竟不会…

南海校区

希望25号网络赛不要爆零

发表于 更新于 分类于 本文字数： 316 阅读时长 ≈ 1 分钟

参考字符串哈希中多项式 $Hash $函数定义：

$f(s) = \sum_{i=1}^{l} s[i] \times b^{l-i} \pmod M$
及其推论:

$f(s[l..r])=f_r(s)-f_{l-1}(s) \times b^{r-l+1}$

我们可以写出$Hash$的实现：

1
2
3
4
5
6
7
const LL M = 33951943;
const LL BA = 233;
    hash_at[1] = (sum[1] - sum[0]) % 3;
    for (int k = 2; k <= sum_0; k++)
    {
        hash_at[k] = ((sum[k] - sum[k - 1]) % 3 + hash_at[k - 1] * BA) % M;
    }

其中 hash_at[] 储存hash值
而又由推论，我们可以简易地借助快速幂来得到$[l,r]$的hash值

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
LL quikpower(LL b)
{
    LL ans = 1, base = BA;
    while (b > 0)
    {
        if (b & 1)
        {
            ans *= base;
            ans %= M;
        }
        base *= base;
        base %= M;
        b >>= 1;
    }
    return ans;
}
LL gethash(int l, int r)
{
    if (l == 1)
        return hash_at[r];
    return (hash_at[r] + M - hash_at[l- 1]] * quikpower(r- l+ 1) % M) % M;
    //加M防止hash值为负数
}

由于unsigned long long的特性，我们有自然溢出的做法:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#define LL long long
const LL B = 13331;
typedef unsigned long long ull;
ull hashs[200087], po[200087];/*hashs储存hash值，po数组储存B的n次方*/
void hash_init()
{
    int sum_0 = n - sum[n];
    po[0] = 1;
    po[1] = B;
    hashs[bk[1]] = (sum[bk[1]] - sum[0]) % 3; 
    for (int k = 2; k <= sum_0; k++)
    {
        hashs[k] = ((sum[k] - sum[k - 1]) % 3 + hashs[k - 1] * B);
        po[k] = po[k - 1] * B;
    }
}
LL gethash(int l, int r)
{
    if (l == 1)
        return hashs[r];
    return (hashs[r] - hashs[l- 1] * po[r - l+ 1]);
}

发表于 更新于 分类于 本文字数： 39 阅读时长 ≈ 1 分钟

终于a了,我的眼睛真得捐掉
a了

1
sum[1] = s[0] - '0';

竟然写成

1
sum[1] = s[1] - '0';

吐了，怪不得11过不去

发表于 更新于 分类于 本文字数： 1.3k 阅读时长 ≈ 5 分钟

Description

QwQ是所有`01`串的控制者，但因为`0`是虚的，`1`才是实的，所以QwQ的遥控器只能控制`1`而不能直接控制`0`。

不幸的是，QwQ的遥控器坏了，控制力有所衰减，只能必须是连续的三个1才能被QwQ所控制。

对于一个01串，可以对它实施这样一个操作：选择中三个连续的1，把这三位向前或向后移动任意多位。

比如说这样： 001110110010 000111110010

或者这样：001110110010 111000110010

如果串可以通过QwQ的若干次操作得到，QwQ就认为和是相等的。

有一天QwQ终于发现了宇宙的本质就是一个长度为的01串但大部分人并不能理解这个神奇的宇宙,于是他们向01串的造物主QwQ问了个问题，每个问题的形式如下：中的第位到第位所组成的子串是否等于中的第位到第位所组成的子串？

Input

第一行输入2个正整数,表示宇宙串的长度和询问次数

第二行输入1个长度为的01串表示QwQ对整个宇宙的理解。

接下来qq行每行四个正整数，表示每个询问。

题目保证对于每个询问，,且
​

Output

对于每个询问，输出一行`Yes`或`No`。
一开始的做法是先求前缀和然后找0的位置并用辅助数组jl[]记录当前k字符上一'0'的索引，若k字符为'0'则记录其本身的索引

然后7.8.9的测试点就爆掉了

最后AC的做法是用BKDR_hash来回应问询，加上快读到70ms

阅读全文 »
0%