SGU150-159 Solution

更好的阅读体验戳此进入

题面链接

230. Weighings

题面

存在 $n$$n$ 个硬币，第 $i$$i$ 个重量为 $i$$i$ 克，要将每个硬币都不同地放入相同的 $n$$n$ 个盒子中的一个。一直 $m$$m$ 个重量关系，给定 $p,q$$p, q$ 表示盒子 $p$$p$ 的重量小于盒子 $q$$q$ 的重量。构造一个方案，输出每个盒子装了多少克的硬币，无解输出 No solution。

$1\le n\le 100,1\le m\le {10}^4$$1 \le n \le 100, 1 \le m \le 10^4$。

Examples

Input_1

xxxxxxxxxx
3
1
3 2
2
2 1
3
1 3

Output_1

xxxxxxxxxx
1
1
2 1 3

Solution

很显然的一个拓朴排序，没什么可说的。

Code

xxxxxxxxxx
71
1
#define _USE_MATH_DEFINES
2
#include <bits/stdc++.h>
3

4
#define PI M_PI
5
#define E M_E
6
#define npt nullptr
7
#define SON i->to
8
#define OPNEW void* operator new(size_t)
9
#define ROPNEW(arr) void* Edge::operator new(size_t){static Edge* P = arr; return P++;}
10

11
using namespace std;
12

13
mt19937 rnd(random_device{}());
14
int rndd(int l, int r){return rnd() % (r - l + 1) + l;}
15
bool rnddd(int x){return rndd(1, 100) <= x;}
16

17
typedef unsigned int uint;
18
typedef unsigned long long unll;
19
typedef long long ll;
20
typedef long double ld;
21

22
template < typename T = int >
23
inline T read(void);
24

25
int N, M;
26
struct Edge{
27
    Edge* nxt;
28
    int to;
29
    OPNEW;
30
}ed[21000];
31
ROPNEW(ed);
32
Edge* head[110];
33
int ind[110];
34
int ans[110];
35
int cnt(0);
36

37
int main(){
38
    N = read(), M = read();
39
    while(M--){
40
        int s = read(), t = read();
41
        head[s] = new Edge{head[s], t};
42
        ++ind[t];
43
    }queue < int > cur;
44
    for(int i = 1; i <= N; ++i)if(!ind[i])cur.push(i);
45
    while(!cur.empty()){
46
        int p = cur.front(); cur.pop();
47
        // ans[++cnt] = p;
48
        ans[p] = ++cnt;
49
        for(auto i = head[p]; i; i = i->nxt)
50
            if(!--ind[SON])cur.push(SON);
51
    }if(cnt < N)printf("No solution\n"), exit(0);
52
    for(int i = 1; i <= N; ++i)printf("%d%c", ans[i], i == N ? '\n' : ' ');
53
    fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
54
    return 0;
55
}
56

57
template < typename T >
58
inline T read(void){
59
    T ret(0);
60
    int flag(1);
61
    char c = getchar();
62
    while(c != '-' && !isdigit(c))c = getchar();
63
    if(c == '-')flag = -1, c = getchar();
64
    while(isdigit(c)){
65
        ret *= 10;
66
        ret += int(c - '0');
67
        c = getchar();
68
    }
69
    ret *= flag;
70
    return ret;
71
}

231. Prime Sum

题面

求 $n$$n$ 以内的，满足 $a,b,a+b$$a, b, a + b$ 均为质数，且 $a\le b$$a \le b$ 的二元组 $(a,b)$$(a, b)$ 的数量。并输出每个可能的二元组。

$1\le n\le {10}^6$$1 \le n \le 10^6$。

Examples

Input_1

xxxxxxxxxx
1
1
4

Output_1

xxxxxxxxxx
1
1
0

Solution

发现质数除了 $2$$2$ 均为奇数，而任意两个奇数的和又为偶数。故问题转化为求所有 $2+p$$2 + p$ 为质数的 $p$$p$ 的数量。筛一下然后枚举即可。最终复杂度 $O(n)$$O(n)$。

Code

xxxxxxxxxx
62
1
#define _USE_MATH_DEFINES
2
#include <bits/stdc++.h>
3

4
#define PI M_PI
5
#define E M_E
6
#define npt nullptr
7
#define SON i->to
8
#define OPNEW void* operator new(size_t)
9
#define ROPNEW(arr) void* Edge::operator new(size_t){static Edge* P = arr; return P++;}
10

11
using namespace std;
12

13
mt19937 rnd(random_device{}());
14
int rndd(int l, int r){return rnd() % (r - l + 1) + l;}
15
bool rnddd(int x){return rndd(1, 100) <= x;}
16

17
typedef unsigned int uint;
18
typedef unsigned long long unll;
19
typedef long long ll;
20
typedef long double ld;
21

22
template < typename T = int >
23
inline T read(void);
24

25
int N;
26
bool notPrime[1100000];
27
basic_string < int > Prime;
28
struct MyPair{int x, y;};
29
basic_string < MyPair > ans;
30

31
int main(){
32
    N = read();
33
    for(int i = 2; i <= N + 10; ++i){
34
        if(!notPrime[i])Prime += i;
35
        for(auto p : Prime){
36
            if(p * i > 1010000)break;
37
            notPrime[p * i] = true;
38
            if(p % i == 0)break;
39
        }
40
    }
41
    for(auto p : Prime)if(p + 2 <= N && !notPrime[p + 2])ans += MyPair{2, p};
42
    printf("%d\n", (int)ans.size());
43
    for(auto p : ans)printf("%d %d\n", p.x, p.y);
44
    fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
45
    return 0;
46
}
47

48
template < typename T >
49
inline T read(void){
50
    T ret(0);
51
    int flag(1);
52
    char c = getchar();
53
    while(c != '-' && !isdigit(c))c = getchar();
54
    if(c == '-')flag = -1, c = getchar();
55
    while(isdigit(c)){
56
        ret *= 10;
57
        ret += int(c - '0');
58
        c = getchar();
59
    }
60
    ret *= flag;
61
    return ret;
62
}

232. Infinite Fraction

题面

给定 $n,k$$n, k$ 及长度为 $n$$n$ 的字符串 $S_{[0,n-1]}$$S_{[0, n - 1]}$。基于 $S$$S$ 构造出 $n$$n$ 个新的字符串 $A$$A$，其中 $A_{i,j}=S_{(i+j\times k)modn}$$A_{i, j} = S_{(i + j \times k) \bmod{n}}$，求字典序最大的 $A$$A$ 的前 $n$$n$ 位。

$1\le n\le 1.5\times {10}^5,0\le k\le {10}^9$$1 \le n \le 1.5 \times 10^5, 0 \le k \le 10^9$。

Examples

Input_1

xxxxxxxxxx
2
1
3 2
2
194

Output_1

xxxxxxxxxx
1
1
914

Input_2

xxxxxxxxxx
2
1
2 1
2
57

Output_2

xxxxxxxxxx
1
1
75

Input_3

xxxxxxxxxx
2
1
4 1
2
0000

Output_3

xxxxxxxxxx
1
1
0000

Solution

感觉这玩意有点像 X-mouse 那道题，不难发现一共有 $gcd(n,k)$$\gcd(n, k)$ 中本质不同的 $A$$A$ 串。对应到抓耗子那题就是有 $gcd(n,k)$$\gcd(n, k)$ 个环，每个环的点数均为 ${\displaystyle \frac{n}{gcd(n,k)}}$$\dfrac{n}{\gcd(n, k)}$，环中所有点对应的 $A_i$$A_i$ 串都是循环同构的。然后看到循环同构不难想到对于每个环中所有循环同构的串跑一遍最大表示法即可，复杂度是线性的，然后每个环都跑一遍取最大的即可。我愿称之为 X-mouse 的弱化弱化弱化版。

Code

xxxxxxxxxx
70
1
#define _USE_MATH_DEFINES
2
#include <bits/stdc++.h>
3

4
#define PI M_PI
5
#define E M_E
6
#define npt nullptr
7
#define SON i->to
8
#define OPNEW void* operator new(size_t)
9
#define ROPNEW(arr) void* Edge::operator new(size_t){static Edge* P = arr; return P++;}
10

11
using namespace std;
12

13
mt19937 rnd(random_device{}());
14
int rndd(int l, int r){return rnd() % (r - l + 1) + l;}
15
bool rnddd(int x){return rndd(1, 100) <= x;}
16

17
typedef unsigned int uint;
18
typedef unsigned long long unll;
19
typedef long long ll;
20
typedef long double ld;
21

22

23

24
template < typename T = int >
25
inline T read(void);
26

27
int N, K;
28
string S;
29
string ans("");
30

31
int main(){
32
    N = read(), K = read();
33
    cin >> S;
34
    int tot = __gcd(N, K), loop = N / tot;
35
    for(int s = 0; s < tot; ++s){
36
        string cur;
37
        cur += S.at(s);
38
        for(int tmp = (s + K) % N; tmp != s; tmp = (tmp + K) % N)cur += S.at(tmp);
39
        int i = 0, j = 1, k = 0;
40
        while(i < loop && j < loop && k < loop){
41
            char ci = cur.at((i + k) % loop), cj = cur.at((j + k) % loop);
42
            if(ci == cj)++k;
43
            else{
44
                ci > cj ? j = j + k + 1 : i = i + k + 1;
45
                if(i == j)++j;
46
                k = 0;
47
            }
48
        }ans = max(ans, cur.substr(min(i, j), loop - min(i, j) + 1) + cur.substr(0, min(i, j)));
49
    }string rans;
50
    while(tot--)rans += ans;
51
    cout << rans << endl;
52
    fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
53
    return 0;
54
}
55

56
template < typename T >
57
inline T read(void){
58
    T ret(0);
59
    int flag(1);
60
    char c = getchar();
61
    while(c != '-' && !isdigit(c))c = getchar();
62
    if(c == '-')flag = -1, c = getchar();
63
    while(isdigit(c)){
64
        ret *= 10;
65
        ret += int(c - '0');
66
        c = getchar();
67
    }
68
    ret *= flag;
69
    return ret;
70
}

233. The Greatest Angle

题面

阴间计算几何，跳！

题面

Solution

Code

xxxxxxxxxx
1
1

题面

Solution

Code

xxxxxxxxxx
1
1

题面

Solution

Code

xxxxxxxxxx
1
1

题面

Solution

Code

xxxxxxxxxx
1
1

题面

Solution

Code

xxxxxxxxxx
1
1

题面

Solution

Code

xxxxxxxxxx
1
1

UPD

update-2022_12_16 初稿