srm 541

发表于   |   分类于   |  

250

Solution

水题，最暴力的方法枚举即可

Code

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
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
#define F first
#define S second
typedef long long LL;
typedef pair<int, int> pii;
map<char, int> s;
int dx[] = {0, 1, -1, 0};
int dy[] = {1, 0, 0, -1};
const int N = 55;
int f[N];
bool vis[N];
struct AntsMeet {
    int countAnts(vector <int> x, vector <int> y, string direction) {
        int n = x.size();
        s['N'] = 0, s['E'] = 1, s['W'] = 2, s['S'] = 3;
        for (int i = 0; i < n; ++i) x[i] <<= 1, y[i] <<= 1, f[i] = s[direction[i]], vis[i] = 1;
        for (int i = 1; i <= 4001; ++i) {
            for (int j = 0; j < n; ++j)
                if (vis[j]) {
                    for (int k = j + 1; k < n; ++k)
                        if (vis[k]) {
                            if (x[j] == x[k] && y[j] == y[k])   vis[j] = vis[k] = 0;
                        }
                }
            for (int j = 0; j < n; ++j)
                if (vis[j]) {
                    x[j] += dx[f[j]];
                    y[j] += dy[f[j]];
                }
        }
        int ans = 0;
        for (int i = 0; i < n; ++i) 
            if (vis[i]) ++ans;
        return ans;
    }
};

550

Description

给出串$A,B,C,S,F$和整数$k$。以及函数$f(x) = A+x+B+x+C$。求$f^k(x)$中以F为子串，出现了多少次。答案mod $10^{9}+7$。串的长度$\le 50$, $k\le 10^7$

Solution

注意到串长度$\le 50$,以及$k\le 10^7$，而且出现F的情况分为在A，B，C三个串中分别出现，以及在交界处出现。由于串的长度比较小，所以我们暴力50次以后，交界处包含F的次数就不再变化了（想一想，为什么）。于是后面的情况我们每次$ans = ans \times 2 + t$即可。。$t$是交界处的答案，$ans$是$A,B,C$中的答案。

Code

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
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
#define F first
#define S second
typedef long long LL;
typedef pair<int, int> pii;
const int M = 1e9 + 7;
struct AkariDaisukiDiv1 {
    int gao(const string &s, const string &t, int l = 0, int r = 100000000) {
        int tmp = 0;
        for (int i = l; i < s.size() - t.size() + 1 && i < r; ++i)
            if (s.substr(i, t.size()) == t) ++tmp;
        return tmp;
    }
    int countF(string A, string B, string C, string S, string F, int k) {
        int cnt = 0;
        for (; cnt < k && S.size() < F.size(); ++cnt)   S = A + S + B + S + C;
        if (S.size() < F.size())    return 0;
        int ans = gao(S, F), t = 0; 
        string p = S.substr(0, F.size()), q = S.substr(S.size() - F.size(), F.size());
        for (int i = 0; cnt < k && i < 50; ++cnt, ++i) {
            t = gao(A + p, F, 0, A.size()) + gao(q + B + p, F, 1, F.size() + B.size()) + gao(q + C, F, 1);
            ans = (ans + ans + t) % M;
            p = (A + p).substr(0, F.size()), q = (q + C).substr((q + C).size() - F.size(), F.size());
        }
        for (; cnt < k; ++cnt)  ans = (ans + ans + t) % M;
        return ans;
    }
};