Blackops

初心易得，始终难守

0%

CF #463 Div.1+Div.2 A B C D E

发表于 更新于 分类于 ，

A.Palindromic Supersequence

题意就是给你一个串$s$然后让你构造一个回文串$t$使得$s$是$t$的子序列

把$s$正反各输出一次就行了。

代码：

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
#include <bits/stdc++.h>
using namespace std;
#define INF 0x3f3f3f3f
#define LC(x) (x<<1)
#define RC(x) ((x<<1)+1)
#define MID(x,y) ((x+y)>>1)
#define CLR(arr,val) memset(arr,val,sizeof(arr))
#define FAST_IO ios::sync_with_stdio(false);cin.tie(0);
typedef pair<int, int> pii;
typedef long long LL;
const double PI = acos(-1.0);
const int N = 1100;
char s[N];

int main(void)
{
    while (~scanf("%s", s))
    {
        int len = strlen(s);
        printf("%s", s);
        reverse(s, s + len);
        puts(s);
    }
    return 0;
}

B.Recursive Queries

题意就是定义$f(n)$与$g(n)$函数，多组询问$[l,r]$中符合$g(x)=k$的$x$的个数。

由于$g(n)$最后的范围是$[1,9]$那么暴力打表记录$[1,9]$这些函数值由哪些$x$得到，把这些位置集合分别排序，然后询问的时候二分一下左右端点作差就是答案了。

代码：

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
45
46
47
48
49
50
51
52
53
#include <bits/stdc++.h>
using namespace std;
#define INF 0x3f3f3f3f
#define LC(x) (x<<1)
#define RC(x) ((x<<1)+1)
#define MID(x,y) ((x+y)>>1)
#define CLR(arr,val) memset(arr,val,sizeof(arr))
#define FAST_IO ios::sync_with_stdio(false);cin.tie(0);
typedef pair<int, int> pii;
typedef long long LL;
const double PI = acos(-1.0);
const int N = 1e6 + 5;
int f[N], g[N];
vector<int>pos[15];

int dfs(int x)
{
    if (x < 10)
        return x;
    return dfs(f[x]);
}
inline int G(int x)
{
    int r = 1;
    while (x)
    {
        int t = x % 10;
        if (t)
            r = r * t;
        x /= 10;
    }
    return r;
}
int main(void)
{
    int q, l, r, k, i;
    for (i = 1; i <= 1000000; ++i)
        f[i] = G(i);
    for (i = 1; i <= 1000000; ++i)
    {
        g[i] = dfs(i);
        pos[g[i]].push_back(i);
    }
    for (i = 1; i <= 9; ++i)
        sort(pos[i].begin(), pos[i].end());
    scanf("%d", &q);
    while (q--)
    {
        scanf("%d%d%d", &l, &r, &k);
        printf("%d\n", upper_bound(pos[k].begin(), pos[k].end(), r) - lower_bound(pos[k].begin(), pos[k].end(), l));
    }
    return 0;
}

C.Permutation Cycle

题意就是让你构造序列使得任意一个位置可以通过题目中的运算回到该位置，且运算次数只能是$a$或$b$，写几组数据可以很容易地发现如果把运算过程中出现的位置放到一起，那么这些位置的个数刚好等于运算次数，那么问题就变成了求$ax+by=n$是否有非负整数解，根据范围也不需要什么$exgcd$可以直接暴力判断一下，注意$x$或$y$可以为$0$（一开始起点为$1$就被hack了……），然后有解的话就说明把序列分成$x+y$段，前$x$段$a$个一组，后$y$段$b$个一组，那么组内的数字如何放置才能形成这样的循环呢？YY发现只要把这个区间循环右移一个位置就行了。还要注意随时更新起点，不然$O(n^2)$就超时了（太可惜了）

代码：

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
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
#include <bits/stdc++.h>
using namespace std;
#define INF 0x3f3f3f3f
#define LC(x) (x<<1)
#define RC(x) ((x<<1)+1)
#define MID(x,y) ((x+y)>>1)
#define CLR(arr,val) memset(arr,val,sizeof(arr))
#define FAST_IO ios::sync_with_stdio(false);cin.tie(0);
typedef pair<int, int> pii;
typedef long long LL;
const double PI = acos(-1.0);
const int N = 1e6 + 7;
int vis[N], arr[N];

int main(void)
{
    int n, a, b, i;
    while (~scanf("%d%d%d", &n, &a, &b))
    {
        int flag = 0;
        int kk = 0;
        for (int k1 = 0; a * k1 <= n; ++k1)
        {
            if ((n - (a * k1)) % b == 0)
            {
                flag = 1;
                kk = k1;
                break;
            }
        }
        if (!flag)
            puts("-1");
        else
        {
            int K1 = kk, K2 = (n - (a * K1)) / b;
            int lastpos = 1;
            while (K1--)
            {
                for (i = lastpos; i <= n; ++i)
                {
                    if (!vis[i])
                    {
                        vis[i] = 1;
                        arr[i] = i + a - 1;
                        int last = i + a - 1;
                        lastpos = last;
                        for (int j = i + a - 1; j > i; --j)
                            arr[j] = --last, vis[j] = 1;
                        break;
                    }
                }
            }
            while (K2--)
            {
                for (i = lastpos; i <= n; ++i)
                {
                    if (!vis[i])
                    {
                        vis[i] = 1;
                        arr[i] = i + b - 1;
                        int last = i + b - 1;
                        lastpos = last;
                        for (int j = i + b - 1; j > i; --j)
                            arr[j] = --last, vis[j] = 1;
                        break;
                    }
                }
            }
            for (i = 1; i <= n; ++i)
                printf("%d%c", arr[i], " \n"[i == n]);
        }
    }
    return 0;
}

D.Tree

题意就是给你一颗初始根为$1$的树和两种操作，一个是加边，一个是询问从点$R$开始向根走最长的点权和不超过$x$且路径点权为不降序列的最大长度。

比赛的时候完全没想法，赛后看别人代码发现是倍增，谁叫我学的是$RMQ$和$Tarjan$求的$LCA$，当时由于这个时间复杂度不如后两者就没学，实际上$RMQ$用的就是倍增的思想从$2^{j-1}$推到$2^j$次的信息，这里也是。

仔细分析可以发现加边的时候并不会影响已经存在的点，只要把加上去的这个点到根的这条链上的信息计算出来就行了。因此用$fa[i][j]$表示从点$i$开始第$2^j$个权值大于等于它的祖先，$S[i][j]$表示从点$i$跳到$fa[i][j]$的路径上的权值和，当新增点权值小于它父亲的时候可以直接令$fa[indx][0]=R$，$S[indx][0]=W[R]$；否则用倍增的思想从大到小找到最靠近$indx$且权值大于等于它的点$y$，令$fa[indx][0]=y$，$S[indx][0]=W[y]$。对于那些不存在的点，点权均设为$+\infty$；然后询问的时候跟加边一样，倒着贪心地向上跳就行了。

代码：

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
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
#include <bits/stdc++.h>
using namespace std;
#define INF 0x3f3f3f3f
#define LINF 0x3f3f3f3f3f3f3f3f
#define LC(x) (x<<1)
#define RC(x) ((x<<1)+1)
#define MID(x,y) ((x+y)>>1)
#define all(a) (a).begin(),(a).end()
#define CLR(arr,val) memset(arr,val,sizeof(arr))
#define FAST_IO ios::sync_with_stdio(false);cin.tie(0);
typedef pair<int, int> pii;
typedef long long LL;
const double PI = acos(-1.0);
const int N = 400010;
int fa[N][18];
LL S[N][18], W[N];
int indx = 1;

void add(int R, int w)
{
    W[++indx] = w;
    if (W[R] >= w)
        fa[indx][0] = R, S[indx][0] = W[R];
    else
    {
        int r = R;
        for (int i = 17; i >= 0; --i)
            if (W[fa[r][i]] < w)
                r = fa[r][i];
        fa[indx][0] = fa[r][0];
        S[indx][0] = W[fa[indx][0]];
    }
    for (int i = 1; i <= 17; ++i)
    {
        fa[indx][i] = fa[fa[indx][i - 1]][i - 1];
        if (fa[indx][i] == 0)
            S[indx][i] = LINF;
        else
            S[indx][i] = S[indx][i - 1] + S[fa[indx][i - 1]][i - 1];
    }
}
int query(int R, LL X)
{
    if (X < W[R])
        return 0;
    LL res = X - W[R];
    int sz = 1;
    for (int i = 17; i >= 0; --i)
    {
        if (S[R][i] <= res)
        {
            res -= S[R][i];
            sz += (1 << i);
            R = fa[R][i];
        }
    }
    return sz;
}
int main(void)
{
    register int T, R, ops;
    register LL X;
    scanf("%d", &T);
    int last = 0;
    CLR(S, INF);
    CLR(W, INF);
    W[1] = 0;
    while (T--)
    {
        scanf("%d%d%I64d", &ops, &R, &X);
        R ^= last;
        X ^= last;
        if (ops == 1)
            add(R, X);
        else
            printf("%d\n", last = query(R, X));
    }
    return 0;
}

E.Team Work

题意就是给你$n$和$k$，求$\sum_{r=1}^n \times C_n^r \times r^k$，相信这个还是很容易看出来的，但是这个怎么求呢？

正解居然是多次求导+记忆化搜索，这脑洞题无敌2333。

首先这个等式由于$C_n^0 \times 0^k=0$，因此等式可以加上这一项使之变得完整：$\sum_{r=1}^n \times C_n^r \times r^k=\sum_{r=0}^n \times C_n^r \times r^k$

由二项式定理得到$(1+x)^n=\sum_{r=0}^n \times C_n^r \times x^r$，这玩意儿跟上面个式子有有一点像，然后对两边求导，得到$n \times (1+x)^{n-1}=\sum_{r=0}^n \times C_n^r \times r \times x^{r-1}$，两边同乘以，得到$n \times x^1 \times (1+x)^{n-1}=\sum_{r=0}^n\times C_n^r\times r\times x^r$

，这样就弄下来一个$r$，题目要我们弄下来$k$个$r$，那么我们要对这个式子做$k$次求导，左右两边乘以$k$次的$x$，但是这里又会发现$x$是不能随意取的，巧合的是当$x=1$的时候刚好左边乘的$k$个$x$都是$1$可以直接去掉，右边的$x^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
45
46
47
48
49
50
51
52
53
54
55
56
#include <bits/stdc++.h>
using namespace std;
#define INF 0x3f3f3f3f
#define LC(x) (x<<1)
#define RC(x) ((x<<1)+1)
#define MID(x,y) ((x+y)>>1)
#define all(a) (a).begin(),(a).end()
#define CLR(arr,val) memset(arr,val,sizeof(arr))
#define FAST_IO ios::sync_with_stdio(false);cin.tie(0);
typedef pair<int, int> pii;
typedef long long LL;
const double PI = acos(-1.0);
const int N = 5005;
const LL mod = 1e9 + 7;
LL dp[N][N];
LL n, k;

LL qpow(LL a, LL b)
{
    LL r = 1;
    while (b)
    {
        if (b & 1)
            r = r * a % mod;
        a = a * a % mod;
        b >>= 1;
    }
    return r;
}
LL dfs(int res, int b, int tot)
{
    if (dp[res][b])
        return dp[res][b];
    int c = tot - b;
    if (!res)
        return dp[res][b] = qpow(2LL, (LL)c);
    if (b)
    {
        LL s = 1LL * b * dfs(res - 1, b, tot);
        dp[res][b] = (dp[res][b] + s) % mod;
    }    
    if (c)
    {
        LL s = 1LL * c * dfs(res - 1, b + 1, tot);
        dp[res][b] = (dp[res][b] + s) % mod;
    }   
    return dp[res][b];
}
int main(void)
{
    while (~scanf("%I64d%I64d", &n, &k))
    {
        printf("%I64d\n", dfs(k, 0, n) % mod);
    }
    return 0;
}