头像

ziuch

江西财经大学




离线:20分钟前


最近来访(48)
用户头像
lxxxl
用户头像
acwing_陌路
用户头像
无名逸仙
用户头像
Bin.
用户头像
满庭
用户头像
俗世奇人
用户头像
Andy_xt
用户头像
Once.
用户头像
kunmy
用户头像
kfc2020
用户头像
qX
用户头像
acwing_zfw
用户头像
究极进化
用户头像
Acckno1
用户头像
wW
用户头像
AC_King
用户头像
XDP_CS
用户头像
hair++
用户头像
灭神堂乄德玛西亚之力
用户头像
zyn酱


ziuch
16天前

7-1 Prime Day (20 分)

wbfg.JPG

The above picture is from Sina Weibo, showing May 23rd, 2019 as a very cool “Prime Day”. That is, not only that the corresponding number of the date 20190523 is a prime, but all its sub-strings ended at the last digit 3 are prime numbers.

Now your job is to tell if a given date is a Prime Day.

Input Specification:

Each input file contains one test case. For each case, a date between January 1st, 0001 and December 31st, 9999 is given, in the format yyyymmdd.

Output Specification:

For each given date, output in the decreasing order of the length of the substrings, each occupies a line. In each line, print the string first, followed by a space, then Yes if it is a prime number, or No if not. If this date is a Prime Day, print in the last line All Prime!.

Sample Input 1:

20190523

Sample Output 1:

20190523 Yes
0190523 Yes
190523 Yes
90523 Yes
0523 Yes
523 Yes
23 Yes
3 Yes
All Prime!

Sample Input 2:

20191231

Sample Output 2:

20191231 Yes
0191231 Yes
191231 Yes
91231 No
1231 Yes
231 No
31 Yes
1 No

代码

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

bool is_prime(int x)
{
    if(x <= 1)
        return false;
    for (int i = 2; i <= x / i; i ++ )
        if(x % i == 0)
            return false;
    return true;
}

int main()
{
    string s;
    cin >> s;

    bool res = true;
    for(int i = 0; i < s.size(); i++)
    {
        int num = stoi(s.substr(i));
        cout << s.substr(i) << " ";

        if(is_prime(num))
        {
            cout << "Yes" << endl;
        }
        else
        {
            res = false;
            cout << "No" << endl;
        }
    }

    if(res)
        cout << "All Prime!" << endl;
    return 0;
}

7-2 The Judger (25 分)

A game of numbers has the following rules: at the beginning, two distinct positive integers are given by the judge. Then each player in turn must give a number to the judge. The number must be the difference of two numbers that are previously given, and must not be duplicated to any of the existed numbers. The game will run for several rounds. The one who gives a duplicate number or even a wrong number will be kicked out.

Your job is to write a judger program to judge the players’ numbers and to determine the final winners.

Input Specification:

Each input file contains one test case. For each case, the first line gives two distinct positive integers to begin with. Both numbers are in [1,$10^5$].

In the second line, two numbers are given: N (2≤N≤10), the number of players, and M (2≤M≤$10^3$), the number of rounds.

Then N lines follow, each contains M positive integers. The i-th line corresponds to the i-th player (i=1,⋯,N). The game is to start from the 1st player giving his/her 1st number, followed by everybody else giving their 1st numbers in the 1st round; then everyone give their 2nd numbers in the 2nd round, and so on so forth.

Output Specification:

If the i-th player is kicked out in the k-th round, print in a line Round #k: i is out.. The rest of the numbers given by the one who is out of the game will be ignored. If more than one player is out in the same round, print them in increasing order of their indices. When the game is over, print in the last line Winner(s): W1 W2 … Wn, where W1 … Wn are the indices of the winners in increasing order. All the numbers in a line must be separated by exactly one space, and there must be no extra space at the beginning or the end of the line. If there is no winner, print No winner. instead.

Sample Input 1:

101 42
4 5
59 34 67 9 7
17 9 8 50 7
25 92 43 26 37
76 51 1 41 40

Sample Output 1:

Round #4: 1 is out.
Round #5: 3 is out.
Winner(s): 2 4

Sample Input 2:

42 101
4 5
59 34 67 9 7
17 9 18 50 49
25 92 58 1 39
102 32 2 6 41

Sample Output 2:

Round #1: 4 is out.
Round #3: 2 is out.
Round #4: 1 is out.
Round #5: 3 is out.
No winner.

代码

#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <vector>

using namespace std;

const int N = 1e5 + 10;

bool fail[16], diff[N], st[N];
int a, b, n, m, g[16][1010];
vector<int> num;

int main()
{
    cin >> a >> b;
    num.push_back(a), num.push_back(b);
    diff[abs(a - b)] = true;
    st[a] = st[b] = true;

    cin >> n >> m;
    for (int i = 1; i <= n; i ++ )
        for (int j = 1; j <= m; j ++ )
            cin >> g[i][j];

    for (int j = 1; j <= m; j ++ )
    {
        for (int i = 1; i <= n; i ++ )
        {
            if(fail[i])
                continue;

            int x = g[i][j];
            if(!diff[x] || st[x])
            {
                fail[i] = true;
                printf("Round #%d: %d is out.\n", j, i);
                continue;
            }

            for(auto &s : num)
                diff[abs(s - x)] = true;

            st[x] = true;
            num.push_back(x);
        }
    }

    vector<int> ans;
    for (int i = 1; i <= n; i ++ )
        if(!fail[i])
            ans.push_back(i);

    if(ans.size() == 0)
        puts("No winner.");
    else
    {
        cout << "Winner(s):";
        for(auto &x : ans)
            cout << " " << x;
    }
    return 0;
}

7-3 Safari Park (25 分)

A safari park(野生动物园)has K species of animals, and is divided into N regions. The managers hope to spread the animals to all the regions, but not the same animals in the two neighboring regions. Of course, they also realize that this is an NP complete problem, you are not expected to solve it. Instead, they have designed several distribution plans. Your job is to write a program to help them tell if a plan is feasible.

Input Specification:

Each input file contains one test case. For each case, the first line gives 3 integers: N (0<N≤500), the number of regions; R (≥0), the number of neighboring relations, and K (0<K≤N), the number of species of animals. The regions and the species are both indexed from 1 to N.

Then R lines follow, each gives the indices of a pair of neighboring regions, separated by a space.

Finally there is a positive M (≤20) followed by M lines of distribution plans. Each plan gives N indices of species in a line (the i-th index is the animal in the i-th rigion), separated by spaces. It is guaranteed that any pair of neighboring regions must be different, and there is no duplicated neighboring relations.

Output Specification:

For each plan, print in a line Yes if no animals in the two neighboring regions are the same, or No otherwise. However, if the number of species given in a plan is not K, you must print Error: Too many species. or Error: Too few species. according to the case.

Sample Input:

6 8 3
2 1
1 3
4 6
2 5
2 4
5 4
5 6
3 6
5
1 2 3 3 1 2
1 2 3 4 5 6
4 5 6 6 4 5
2 3 4 2 3 4
2 2 2 2 2 2

Sample Output:

Yes
Error: Too many species.
Yes
No
Error: Too few species.

代码

#include <iostream>
#include <cstring>
#include <algorithm>
#include <unordered_set>
#include <vector>

using namespace std;

const int N = 510;

int n, r, k;
bool G[N][N];

bool judge(vector<int> &a)
{
    for (int i = 1; i <= n; i ++ )
        for (int j = i + 1; j <= n; j ++ )
            if(a[i] == a[j] && G[i][j])
                return false;
    return true;
}

int main()
{
    cin >> n >> r >> k;
    while(r--)
    {
        int a, b;
        cin >> a >> b;
        G[a][b] = G[b][a] = true;
    }

    int m;
    cin >> m;
    while (m -- )
    {
        vector<int> a(n + 1);
        unordered_set<int> s;
        for (int i = 1; i <= n; i ++ )
        {
            cin >> a[i];
            s.insert(a[i]);
        }

        if(s.size() == k)
            cout << (judge(a) ? "Yes" : "No") << endl;
        else if(s.size() > k)
            cout << "Error: Too many species." << endl;
        else
            cout << "Error: Too few species." << endl;
    }
    return 0;
}

7-4 Replacement Selection (30 分)

When the input is much too large to fit into memory, we have to do external sorting instead of internal sorting. One of the key steps in external sorting is to generate sets of sorted records (also called runs) with limited internal memory. The simplest method is to read as many records as possible into the memory, and sort them internally, then write the resulting run back to some tape. The size of each run is the same as the capacity of the internal memory.

Replacement Selection sorting algorithm was described in 1965 by Donald Knuth. Notice that as soon as the first record is written to an output tape, the memory it used becomes available for another record. Assume that we are sorting in ascending order, if the next record is not smaller than the record we have just output, then it can be included in the run.

For example, suppose that we have a set of input { 81, 94, 11, 96, 12, 99, 35 }, and our memory can sort 3 records only. By the simplest method we will obtain three runs: { 11, 81, 94 }, { 12, 96, 99 } and { 35 }. According to the replacement selection algorithm, we would read and sort the first 3 records { 81, 94, 11 } and output 11 as the smallest one. Then one space is available so 96 is read in and will join the first run since it is larger than 11. Now we have { 81, 94, 96 }. After 81 is out, 12 comes in but it must belong to the next run since it is smaller than 81. Hence we have { 94, 96, 12 } where 12 will stay since it belongs to the next run. When 94 is out and 99 is in, since 99 is larger than 94, it must belong to the first run. Eventually we will obtain two runs: the first one contains { 11, 81, 94, 96, 99 } and the second one contains { 12, 35 }.

Your job is to implement this replacement selection algorithm.

Input Specification:

Each input file contains several test cases. The first line gives two positive integers N (≤$10^5$) and M (<N/2), which are the total number of records to be sorted, and the capacity of the internal memory. Then N numbers are given in the next line, all in the range of int. All the numbers in a line are separated by a space.

Output Specification:

For each test case, print in each line a run (in ascending order) generated by the replacement selection algorithm. All the numbers in a line must be separated by exactly 1 space, and there must be no extra space at the beginning or the end of the line.

Sample Input:

13 3
81 94 11 96 12 99 17 35 28 58 41 75 15

Sample Output:

11 81 94 96 99
12 17 28 35 41 58 75
15

代码

#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
#include <vector>

using namespace std;

const int N = 1e5 + 10;

int n, m;
int a[N];
priority_queue<int, vector<int>, greater<int>> q, q1;

int main()
{
    while(cin >> n >> m)
    {
        while(q.size())
            q.pop();
        while(q1.size())
            q1.pop();

        for(int i = 0; i < n; i++)
            cin >> a[i]; 

        int k = m;
        for(int i = 0; i < m; i++)
            q.push(a[i]);

        while(q.size())
        {
            vector<int> ans;
            while(q.size())
            {
                int t = q.top();
                q.pop();
                ans.push_back(t);

                if(k >= n)
                    continue;

                if(a[k] > t)
                    q.push(a[k++]);
                else
                    q1.push(a[k++]);
            }

            for(int i = 0; i < ans.size(); i++)
                cout << ans[i] << (i == ans.size() - 1 ? '\n' : ' ');

            while(q1.size())
            {
                int t = q1.top();
                q1.pop();
                q.push(t);
            }
        }
    }

    return 0;
}



ziuch
16天前

7-1 Good in C(20分)

When your interviewer asks you to write “Hello World” using C, can you do as the following figure shows?

Input Specification:

Each input file contains one test case. For each case, the first part gives the 26 capital English letters A-Z, each in a 7×5 matrix of C’s and .’s. Then a sentence is given in a line, ended by a return. The sentence is formed by several words (no more than 10 continuous capital English letters each), and the words are separated by any characters other than capital English letters.

It is guaranteed that there is at least one word given.

Output Specification:

For each word, print the matrix form of each of its letters in a line, and the letters must be separated by exactly one column of space. There must be no extra space at the beginning or the end of the word.

Between two adjacent words, there must be a single empty line to separate them. There must be no extra line at the beginning or the end of the output.

Sample Input:

..C..
.C.C.
C...C
CCCCC
C...C
C...C
C...C
CCCC.
C...C
C...C
CCCC.
C...C
C...C
CCCC.
.CCC.
C...C
C....
C....
C....
C...C
.CCC.
CCCC.
C...C
C...C
C...C
C...C
C...C
CCCC.
CCCCC
C....
C....
CCCC.
C....
C....
CCCCC
CCCCC
C....
C....
CCCC.
C....
C....
C....
CCCC.
C...C
C....
C.CCC
C...C
C...C
CCCC.
C...C
C...C
C...C
CCCCC
C...C
C...C
C...C
CCCCC
..C..
..C..
..C..
..C..
..C..
CCCCC
CCCCC
....C
....C
....C
....C
C...C
.CCC.
C...C
C..C.
C.C..
CC...
C.C..
C..C.
C...C
C....
C....
C....
C....
C....
C....
CCCCC
C...C
C...C
CC.CC
C.C.C
C...C
C...C
C...C
C...C
C...C
CC..C
C.C.C
C..CC
C...C
C...C
.CCC.
C...C
C...C
C...C
C...C
C...C
.CCC.
CCCC.
C...C
C...C
CCCC.
C....
C....
C....
.CCC.
C...C
C...C
C...C
C.C.C
C..CC
.CCC.
CCCC.
C...C
CCCC.
CC...
C.C..
C..C.
C...C
.CCC.
C...C
C....
.CCC.
....C
C...C
.CCC.
CCCCC
..C..
..C..
..C..
..C..
..C..
..C..
C...C
C...C
C...C
C...C
C...C
C...C
.CCC.
C...C
C...C
C...C
C...C
C...C
.C.C.
..C..
C...C
C...C
C...C
C.C.C
CC.CC
C...C
C...C
C...C
C...C
.C.C.
..C..
.C.C.
C...C
C...C
C...C
C...C
.C.C.
..C..
..C..
..C..
..C..
CCCCC
....C
...C.
..C..
.C...
C....
CCCCC
HELLO~WORLD!

Sample Output:

C...C CCCCC C.... C.... .CCC.
C...C C.... C.... C.... C...C
C...C C.... C.... C.... C...C
CCCCC CCCC. C.... C.... C...C
C...C C.... C.... C.... C...C
C...C C.... C.... C.... C...C
C...C CCCCC CCCCC CCCCC .CCC.

C...C .CCC. CCCC. C.... CCCC.
C...C C...C C...C C.... C...C
C...C C...C CCCC. C.... C...C
C.C.C C...C CC... C.... C...C
CC.CC C...C C.C.. C.... C...C
C...C C...C C..C. C.... C...C
C...C .CCC. C...C CCCCC CCCC.

代码

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 26, W = 5, H = 7;

char s[N][H][W];

int main()
{
    for (int x = 0; x < N; x ++ )
        for (int i = 0; i < H; i ++ )
            for (int j = 0; j < W; j ++ )
                cin >> s[x][i][j];

    getchar();
    string str;
    getline(cin, str);

    bool flag = false;
    for (int i = 0, j = 0; i < str.size(); i = j + 1, flag = true)
    {
        while((str[i] < 'A' || str[i] > 'Z') && i < str.size())
            i++;

        j = i;
        while((str[j] >= 'A' && str[j] <= 'Z') && j < str.size())
            j++;

        if(i >= j)
            break;

        char all[H][24 * W];
        for(int x = 0; x < H; x++)
            for (int y = 0; y < 24 * W; y ++ )
                all[x][y] = ' ';

        for(int x = i, cnt = 0; x < j; x++, cnt++)
            for (int uh = 0 ; uh < H; uh ++ )
                for(int uw = 0; uw < W; uw++)
                    all[uh][5 * cnt + uw + cnt] = s[str[x] - 'A'][uh][uw];

        if(flag)
            cout << endl;
        for(int x = 0; x < H; x++)
        {
            for(int y = 0; y < (5 + 1) * (j - i) - 1; y++)
                cout << (char)all[x][y];
            cout << endl;
        }
    }
    return 0;
}

7-2 Block Reversing (25 分)

Given a singly linked list L. Let us consider every K nodes as a block (if there are less than K nodes at the end of the list, the rest of the nodes are still considered as a block). Your job is to reverse all the blocks in L. For example, given L as 1→2→3→4→5→6→7→8 and K as 3, your output must be 7→8→4→5→6→1→2→3.

Input Specification:

Each input file contains one test case. For each case, the first line contains the address of the first node, a positive N (≤$10^5$) which is the total number of nodes, and a positive K (≤N) which is the size of a block. The address of a node is a 5-digit nonnegative integer, and NULL is represented by −1.

Then N lines follow, each describes a node in the format:

Address Data Next

where Address is the position of the node, Data is an integer, and Next is the position of the next node.

Output Specification:
For each case, output the resulting ordered linked list. Each node occupies a line, and is printed in the same format as in the input.

Sample Input:

00100 8 3
71120 7 88666
00000 4 99999
00100 1 12309
68237 6 71120
33218 3 00000
99999 5 68237
88666 8 -1
12309 2 33218

Sample Output:

71120 7 88666
88666 8 00000
00000 4 99999
99999 5 68237
68237 6 00100
00100 1 12309
12309 2 33218
33218 3 -1

代码

#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>

using namespace std;

const int N = 1e5 + 10;

int head, m, k;
int datas[N], ne[N];

int main()
{
    cin >> head >> m >> k;
    while (m -- )
    {
        int address, d, next;
        cin >> address >> d >> next;
        datas[address] = d, ne[address] = next;
    }

    vector<int> list;
    while(head != -1)
    {
        list.push_back(head);
        head = ne[head];
    }

    for (int i = 0, j = k; i < list.size(); i ++ , i = j, j = min(j + k, (int)list.size()))
        reverse(list.begin() + i, list.begin() + j);

    reverse(list.begin(), list.end());
    for (int i = 0; i + 1 < list.size(); i ++ )
        printf("%05d %d %05d\n", list[i], datas[list[i]], list[i + 1]);
    printf("%05d %d -1\n", list.back(), datas[list.back()]);
    return 0;
}

7-3 Summit (25 分)

A summit (峰会) is a meeting of heads of state or government. Arranging the rest areas for the summit is not a simple job. The ideal arrangement of one area is to invite those heads so that everyone is a direct friend of everyone.

Now given a set of tentative arrangements, your job is to tell the organizers whether or not each area is all set.

Input Specification:

Each input file contains one test case. For each case, the first line gives two positive integers N (≤ 200), the number of heads in the summit, and M, the number of friendship relations. Then M lines follow, each gives a pair of indices of the heads who are friends to each other. The heads are indexed from 1 to N.

Then there is another positive integer K (≤ 100), and K lines of tentative arrangement of rest areas follow, each first gives a positive number L (≤ N), then followed by a sequence of L distinct indices of the heads. All the numbers in a line are separated by a space.

Output Specification:

For each of the K areas, print in a line your advice in the following format:

if in this area everyone is a direct friend of everyone, and no friend is missing (that is, no one else is a direct friend of everyone in this area), print Area X is OK..

if in this area everyone is a direct friend of everyone, yet there are some other heads who may also be invited without breaking the ideal arrangement, print Area X may invite more people, such as H. where H is the smallest index of the head who may be invited.

if in this area the arrangement is not an ideal one, then print Area X needs help. so the host can provide some special service to help the heads get to know each other.

Here X is the index of an area, starting from 1 to K.

Sample Input:

8 10
5 6
7 8
6 4
3 6
4 5
2 3
8 2
2 7
5 3
3 4
6
4 5 4 3 6
3 2 8 7
2 2 3
1 1
2 4 6
3 3 2 1

Sample Output:

Area 1 is OK.
Area 2 is OK.
Area 3 is OK.
Area 4 is OK.
Area 5 may invite more people, such as 3.
Area 6 needs help.

代码

#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#include <unordered_set>

using namespace std;
const int N = 210;

int n, m, k;
bool G[N][N];
unordered_set<int> s;

bool judge(vector<int> a)
{
    for (int i = 0; i < a.size(); i ++ )
        for (int j = 0; j < a.size(); j ++ )
            if(!G[a[i]][a[j]])
                return false;
    return true;
}

int cal(vector<int> a)
{
    if(!judge(a))
        return -1;

    s.clear();
    for (int i = 0; i < n; i ++ )
        s.insert(a[i]);

    for(int i = 1; i <= n; i++)
    {
        if(s.count(i))
            continue;

        a.push_back(i);
        if(judge(a))
            return i;
        a.pop_back();
    }

    return 0;
}

void init()
{
    for (int i = 0; i < N; i ++ )
        G[i][i] = true;
}

int main()
{
    init();
    cin >> n >> m;
    while (m -- )
    {
        int a, b;
        cin >> a >> b;
        G[a][b] = G[b][a] = true;
    }

    cin >> k;
    for (int i = 1; i <= k; i ++ )
    {
        int m, x;
        cin >> m;
        vector<int> a;
        while(m--)
        {
            cin >> x;
            a.push_back(x);
        }

        int res = cal(a);
        if(res == 0)
            printf("Area %d is OK.\n", i);
        else if(res > 0)
            printf("Area %d may invite more people, such as %d.\n", i, res);
        else
            printf("Area %d needs help.\n", i);
    }
    return 0;
}

7-4 Cartesian Tree (30 分)

A Cartesian tree is a binary tree constructed from a sequence of distinct numbers. The tree is heap-ordered, and an inorder traversal returns the original sequence. For example, given the sequence { 8, 15, 3, 4, 1, 5, 12, 10, 18, 6 }, the min-heap Cartesian tree is shown by the figure.

Your job is to output the level-order traversal sequence of the min-heap Cartesian tree.

Input Specification:

Each input file contains one test case. Each case starts from giving a positive integer N (≤30), and then N distinct numbers in the next line, separated by a space. All the numbers are in the range of int.

Output Specification:

For each test case, print in a line the level-order traversal sequence of the min-heap Cartesian tree. All the numbers in a line must be separated by exactly one space, and there must be no extra space at the beginning or the end of the line.

Sample Input:

10
8 15 3 4 1 5 12 10 18 6

Sample Output:

1 3 5 8 4 6 15 10 12 18

代码

#include <iostream>
#include <cstring>
#include <algorithm>
#include <unordered_map>

using namespace std;
const int N = 36;

int n;
int a[N], q[N];
unordered_map<int, int> l, r;

int get_min(int il, int ir)
{
    int m = il;
    for (int i = il; i <= ir; i ++ )
        if(a[m] > a[i])
            m = i;
    return m;
}

int build(int i, int j)
{
    if(i == j)
        return a[i];

    int k = get_min(i, j);
    int root = a[k];

    if(i < k)
        l[root] = build(i, k - 1);
    if(k < j)
        r[root] = build(k + 1, j);

    return root;
}

void bfs(int root)
{
    int hh = 0, rr = 0;
    q[rr++] = root;

    while(hh < rr)
    {
        int t = q[hh++];
        if(l.count(t))
            q[rr++] = l[t];
        if(r.count(t))
            q[rr++] = r[t];
    }

    for (int i = 0; i < n; i ++ )
        cout << q[i] << (i == n - 1 ? '\n' : ' ');
}

int main()
{
    cin >> n;
    for (int i = 0; i < n; i ++ )
        cin >> a[i];

    int root = build(0, n - 1);
    bfs(root);

    return 0;
}



ziuch
21天前

2021/09/05 17:57
题意:给出斐波那契数列的第n项n <= 39
思路:递推,滚动数组,矩阵快速幂

经典老题,斐波那契数列
方法一:递归,时间复杂度O($2^n$), 只能计算到三十几位,舍弃

方法二:记忆化搜索,时间复杂度O(n),由于数组大小限制和递归层数限制,只能计算到$10^5$,可行

方法三:递推,时间复杂度O(n),由于数组大小限制,只能计算到$10^7$,可行

方法四:滚动数组,或者直接开三个变量,滚动数组会更好理解一些,时间复杂度O(n),空间复杂度O(1),此时瓶颈在时间上,只能计算到$10^8$,可行

方法五:矩阵快速幂,类似于普通的快速幂,能够把普通的指数运算从O(n)优化到O(logn),那么斐波那契数列和矩阵运算有什么关联呢?

\begin{bmatrix}
1&1 \\
1&0
\end{bmatrix}

\begin{bmatrix}
F(n) \\
F(n - 1)
\end{bmatrix}

\begin{bmatrix}
F(n + 1) \\
F(n)
\end{bmatrix}

(不知道怎么才能不换行……麻烦大佬告知)

所以说我们从F(0),F(1)开始进行递推,需要计算到F(n),就对第一个矩阵进行n - 1次幂运算,最后再乘上初始矩阵就可以得到答案

这里给出滚动数组和矩阵快速幂写法

滚动数组

class Solution {
public:
    int Fibonacci(int n) {
        int f[3] = {0};
        f[1] = 1;

        for(int i = 2; i <= n; i++)
            f[i % 3] = (f[(i - 1) % 3] + f[(i - 2) % 3]);
        return f[n % 3];
    }
};

矩阵快速幂

class Solution {
public:
    int Fibonacci(int n) {
        Matrix a;
        a.m[0][0] = a.m[0][1] = a.m[1][0] = 1;
        a.m[1][1] = 0;

        a = quick_pow(a, n);
        int b[2][1], t[2][1] = {0};
        b[0][0] = 1, b[1][0] = 0;

        for(int i = 0; i < 2; i++)
            for(int j = 0; j < 1; j++)
                for(int x = 0; x < 2; x++)
                    t[i][j] += a.m[i][x] * b[x][j];

        return t[1][0];
    }

    struct Matrix
    {
        long long m[2][2];
    };

    Matrix mult(Matrix a, Matrix b)
    {
        Matrix c;
        c.m[0][0] = c.m[0][1] = c.m[1][0] = c.m[1][1] = 0;
        for(int i = 0; i < 2; i++)
            for(int j = 0; j < 2; j++)
                for(int x = 0; x < 2; x++)
                    c.m[i][j] += a.m[i][x] * b.m[x][j];
        return c;
    }

    Matrix quick_pow(Matrix m, int n)
    {
        Matrix ans;
        ans.m[0][0] = ans.m[1][1] = 1;
        ans.m[1][0] = ans.m[0][1] = 0;

        while(n)
        {
            if(n & 1)
                ans = mult(ans, m);
            n >>= 1;
            m = mult(m, m);
        }

        return ans;
    }
};



ziuch
23天前

7-1 Forever(20分)

“Forever number” is a positive integer A with K digits, satisfying the following constrains:

the sum of all the digits of A is m;
the sum of all the digits of A+1 is n; and
the greatest common divisor of m and n is a prime number which is greater than 2.
Now you are supposed to find these forever numbers.

Input Specification:

Each input file contains one test case. For each test case, the first line contains a positive integer N (≤5). Then N lines follow, each gives a pair of K (3<K<10) and m (1<m<90), of which the meanings are given in the problem description.

Output Specification:

For each pair of K and m, first print in a line Case X, where X is the case index (starts from 1). Then print n and A in the following line. The numbers must be separated by a space. If the solution is not unique, output in the ascending order of n. If still not unique, output in the ascending order of A. If there is no solution, output No Solution.

Sample Input:

2
6 45
7 80

Sample Output:

Case 1
10 189999
10 279999
10 369999
10 459999
10 549999
10 639999
10 729999
10 819999
10 909999
Case 2
No Solution

题意:给定一个k和一个m,求一个k位数a,a的各位数之和是m,a+1的各位数之和为n,并且m和n的最大公约数大于2并且是个质数,要求输出符合条件的n和a,先按照n升序,n相同按照a升序输出,如果无解输出No Solution
思路:dfs,剪枝,构造,素数,约数

一开始直接暴力15分,完美收获超时
可以看下为什么超时,极限情况每次k都是9,遍历所有的九位数,需要计算约10e10,那超时就不奇怪了
我们看下有什么性质可以用上,各位和这个性质可以用上
因为在遍历的时候,大部分情况都是各位之和是不等于m的,所以才造成极大的时间消耗
我们能不能根据各位之和构造一个k位数,这样就可以极大程度上避免无效的枚举

我们可以通过dfs去构造,每次选取每个位上的数字,要注意这里构造出来的数一定要是正数,所以说我们在枚举第一位的时候不能是零,并且如果不用上各位之和这个条件,我们通过dfs构造时间复杂度和直接遍历相差无几

那么怎么用呢,一个很简单的剪枝就是,如果在枚举过程中当前数的各位和已经超过m,那么再构造下去一定不能够找到答案的,还有就是如果当前各位和恰好等于m,但位数不足k或者大于k,这样也是不行的

但通过这两个剪枝我们仍然还是会超时,我们可以看下我们最先枚举出来的数字是什么(这里是每位数字按照从0-9枚举的),我们根据样例举例,需要构造一个6位数,各位和是45,我们最先枚举出来的就是100000,100001,100002……这些数字确实是六位数,但是我们会发现各位和距离45相差了十万八千里,我们能否为其加上一个剪枝呢

答案是可以的,比如我们枚举到10xxxx时(xxxx代表还未枚举),我们可以尝试,如果把还未枚举出的数字全填上最大的9,能否凑出来45呢,如109999,各位和是37,可以看到即使全填上最大数字也不能凑够45,说明我们之前枚举的数字太小了,我们接着往下枚举是必然不可能凑出来答案的,所以说我们直接返回,不往下进行枚举了

通过如上方法进行剪枝,最大数据也仅需5ms就能顺利通过(时限3000ms)
考试卡了很久因为没看到题目要求最大公约数还要满足是质数的条件,果然第一道题必考素数
排序输出的话直接用pair就行了,自定义排序都省了


2021/09/10 18:56
还可以用上a,b两数的最大公约数大于2这个条件,可以断定最后一位一定是9。
因为如果不是9,就无法进位,那么b == a + 1,此时最大公约数一定是1,不可能大于2

代码

#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>

using namespace std;
typedef pair<int, int> PII;

int t, n, m, k;
vector<PII> ans;

int sum(int x)
{
    int s = 0;
    while(x)
    {
        s += x % 10;
        x /= 10;
    }
    return s;
}

bool is_prime(int x)
{
    for(int i = 2; i <= x / i; i++)
        if(x % i == 0)
            return false;
    return true;
}

void dfs(int u, int s, int num)
{
    if(u == k && s == m)
    {
        int n = sum(num + 1), x = __gcd(m, n);
        if(x > 2 && is_prime(x))
            ans.push_back({n, num});
    }

    if(u >= k || s >= m || s + 9 * (k - u) < m)     //位数超过,总和超过,最大总和不足
        return ;

    for (int i = 0; i < 10; i ++ )
    {
        if(u == 0 && i == 0)
            continue;
        dfs(u + 1, s + i, num * 10 + i);
    }
}

int main()
{
    scanf("%d", &t);
    for (int x = 0; x < t; x ++ )
    {
        scanf("%d %d", &k, &m);

        ans.clear();
        dfs(0, 0, 0);

        printf("Case %d\n", x + 1);
        if(ans.size())
        {
            sort(ans.begin(), ans.end());
            for(auto &x : ans)
                printf("%d %d\n", x.first, x.second);
        }
        else
            puts("No Solution");
    }
    return 0;
}

7-2 Merging Linked Lists(25分)

Given two singly linked lists $L_1$ $=$ $a_1$ $\rightarrow$ $a_2$ $\rightarrow$ ···· $\rightarrow$ $a_{n-1}$ $\rightarrow$ $a_n$ and $L_2$ $=$ $b_1$ $\rightarrow$ $b_2$ $\rightarrow$ ···· $\rightarrow$ $b_{m-1}$ $\rightarrow$ $b_m$
. If n≥2m, you are supposed to reverse and merge the shorter one into the longer one to obtain a list like a $a_1$ $\rightarrow$ $a_2$ $\rightarrow$ $b_m$ $\rightarrow$ $a_3$ $\rightarrow$ $a_4$ $\rightarrow$ $b_{m-1}$ ···· For example, given one list being 6→7 and the other one 1→2→3→4→5, you must output 1→2→7→3→4→6→5.

Input Specification:

Each input file contains one test case. For each case, the first line contains the two addresses of the first nodes of $L_1$ and $L_2$, plus a positive N (≤$10^5$) which is the total number of nodes given. The address of a node is a 5-digit nonnegative integer, and NULL is represented by -1.

Then N lines follow, each describes a node in the format:

Address Data Next

where Address is the position of the node, Data is a positive integer no more than $10^5$, and Next is the position of the next node. It is guaranteed that no list is empty, and the longer list is at least twice as long as the shorter one.

Output Specification:

For each case, output in order the resulting linked list. Each node occupies a line, and is printed in the same format as in the input.

Sample Input:

00100 01000 7
02233 2 34891
00100 6 00001
34891 3 10086
01000 1 02233
00033 5 -1
10086 4 00033
00001 7 -1

Sample Output:

01000 1 02233
02233 2 00001
00001 7 34891
34891 3 10086
10086 4 00100
00100 6 00033
00033 5 -1

题意:给出两条链表,一条比另一条的两倍还要长,要求把短的逆序后,组成一条每两个长的再连上一个短的链表
思路:模拟,链表

又是一道老链表题了,每次的输出输出都差不多,但每次需要模拟问题有一些不一样
由于节点的地址不会超过$10^5$,所以我们可以直接通过地址去映射datanext,组成的链表就是用数组存的一系列节点的地址,一个循环就可以串起一个链表

值得注意的是,题目描述里,l1是长链表,但是举的例子里,l2又变成了长链表,说明哪个是长链表是不确定的,需要我们自己判断(默认l1是长链表能够得到22分),其实如果默认处理l1为长链表,发现l2比l1长,直接交换一下就行,或者是if判断写两遍相似的组合代码

注意在组合两个链表的时候,一定要先判断有没有越界,防止段错误

代码

#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>

using namespace std;
const int N = 1e5 + 10;

int h1, h2, m;
int datas[N], ne[N];

int main()
{
    cin >> h1 >> h2 >> m;
    while (m -- )
    {
        int adress, d, next;
        cin >> adress >> d >> next;
        datas[adress] = d, ne[adress] = next;
    }

    vector<int> l1, l2;
    while(h1 != -1)
    {
        l1.push_back(h1);
        h1 = ne[h1];
    }

    while(h2 != -1)
    {
        l2.push_back(h2);
        h2 = ne[h2];
    }

    if(l2.size() > l1.size())           //并没有说哪个链表是长的
        swap(l1, l2);

    reverse(l2.begin(), l2.end());
    vector<int> all;
    for(int i = 0, j = 0; i < l1.size();)
    {
        all.push_back(l1[i++]);
        if(i < l1.size())
            all.push_back(l1[i++]);
        if(j < l2.size())
            all.push_back(l2[j++]);
    }

    for (int i = 0; i + 1 < all.size(); i ++ )
        printf("%05d %d %05d\n", all[i], datas[all[i]], all[i + 1]);
    if(all.size())
        printf("%05d %d -1\n", all.back(), datas[all.back()]);
    return 0;
}

7-3 Postfix Expression(25分)

Given a syntax tree (binary), you are supposed to output the corresponding postfix expression, with parentheses reflecting the precedences of the operators.

Input Specification:
Each input file contains one test case. For each case, the first line gives a positive integer N (≤ 20) which is the total number of nodes in the syntax tree. Then N lines follow, each gives the information of a node (the i-th line corresponds to the i-th node) in the format:

data left_child right_child
where data is a string of no more than 10 characters, left_child and right_child are the indices of this node’s left and right children, respectively. The nodes are indexed from 1 to N. The NULL link is represented by −1. The figures 1 and 2 correspond to the samples 1 and 2, respectively.

infix1.JPG    infix2.JPG
$\qquad$$\qquad$$\qquad$Figure 1 $\qquad$$\qquad$$\qquad$$\qquad$$\qquad$$\qquad$ Figure 2

Output Specification:

For each case, print in a line the postfix expression, with parentheses reflecting the precedences of the operators.There must be no space between any symbols.

Sample Input 1:

8
* 8 7
a -1 -1
* 4 1
+ 2 5
b -1 -1
d -1 -1
- -1 6
c -1 -1

Sample Output 1:

(((a)(b)+)((c)(-(d))*)*)

Sample Input 2:

8
2.35 -1 -1
* 6 1
- -1 4
% 7 8
+ 2 3
a -1 -1
str -1 -1
871 -1 -1

Sample Output 2:

(((a)(2.35)*)(-((str)(871)%))+)

思路:给定每个节点左右儿子,要求输出其后缀表达式并为其添加括号
题意:树的遍历,模拟

其实这道题看懂题意才是最难的,一开始我以为直接后序遍历输出就是了,括号也就是每个节点都加上,但是交上去只得了1分,仔细观察才发现与样例的区别

比如说第一个样例的”-“号,正常的后序遍历,这个”-“号应该出现在c和d之后的,但是它却出现在了c和d之间??
因为是这样的,”+”号和”-“号不仅可以表示二元运算符的加号和减号,也可以用作单元运算符,表示正号和负号,如果一个运算符它只有右儿子,左儿子为空的话,说明这个运算符是单元运算符,所以说出现在c和d之间的”-“号代表-d

所以我们需要特殊处理这种情况,此时需要把二者作为整体,-和d,所以应该先遍历根节点,输出-,再遍历右子树
其余情况正常后序遍历即可

代码

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;
const int N = 25;

int n;
int l[N], r[N];
bool isChild[N];
string datas[N];

void post(int u)
{
    if(u == -1)
        return ;

    cout << "(";
    if(l[u] == -1 && r[u] != -1)            //处理+-号为单元操作符的情况
    {
        cout << datas[u];
        post(r[u]);
    }
    else
    {
        post(l[u]);
        post(r[u]);
        cout << datas[u];
    }

    cout << ")";
    return ;
}

int main()
{
    cin >> n;
    for (int i = 1; i <= n; i ++ )
    {
        cin >> datas[i] >> l[i] >> r[i];
        if(l[i] != -1)
            isChild[l[i]] = true;
        if(r[i] != -1)
            isChild[r[i]] = true;
    }

    int root = 1;
    while(isChild[root])
        root++;

    post(root);
    return 0;
}

7-4 Dijkstra Sequence(30分)

Dijkstra’s algorithm is one of the very famous greedy algorithms. It is used for solving the single source shortest path problem which gives the shortest paths from one particular source vertex to all the other vertices of the given graph. It was conceived by computer scientist Edsger W. Dijkstra in 1956 and published three years later.

In this algorithm, a set contains vertices included in shortest path tree is maintained. During each step, we find one vertex which is not yet included and has a minimum distance from the source, and collect it into the set. Hence step by step an ordered sequence of vertices, let’s call it Dijkstra sequence, is generated by Dijkstra’s algorithm.

On the other hand, for a given graph, there could be more than one Dijkstra sequence. For example, both { 5, 1, 3, 4, 2 } and { 5, 3, 1, 2, 4 } are Dijkstra sequences for the graph, where 5 is the source. Your job is to check whether a given sequence is Dijkstra sequence or not.

Input Specification:

Each input file contains one test case. For each case, the first line contains two positive integers $N_v$(≤$10^3$) and $N_e$(≤$10^5$), which are the total numbers of vertices and edges, respectively. Hence the vertices are numbered from 1 to $N_v$.

Then $N_e$lines follow, each describes an edge by giving the indices of the vertices at the two ends, followed by a positive integer weight (≤100) of the edge. It is guaranteed that the given graph is connected.

Finally the number of queries, K, is given as a positive integer no larger than 100, followed by K lines of sequences, each contains a permutationof the $N_v$vertices. It is assumed that the first vertex is the source for each sequence.

All the inputs in a line are separated by a space.

Output Specification:

For each of the K sequences, print in a line Yes if it is a Dijkstra sequence, or No if not.

Sample Input:

5 7
1 2 2
1 5 1
2 3 1
2 4 1
2 5 2
3 5 1
3 4 1
4
5 1 3 4 2
5 3 1 2 4
2 3 4 5 1
3 2 1 5 4

Sample Output:

Yes
Yes
Yes
No

题意:给定一无向图,再给出m个顶点序列,要求判断这些序列是否是合法的dijkstra的顶点选择序列
题意:模拟,dijkstra

感觉这题是最直接最简单的题目了,感觉是个趋势,很多题目都是判别是否合法
直接模拟即可,注意每个序列第一个给出的顶点就是起点(并不是每次都起点为1)
其次我们每次取出来的最小距离的顶点,我们都和给出的顶点判断,如果二者对应的距离起点的距离相等,那么我们就选择给出的那个顶点,反正必然不是合法的情况,如果能够正常执行完整个dijkstra算法,那么就是合法的顶点序列

点数小于$10^3$,直接用邻接矩阵存图即可,计算次数是100次dijkstra($10^6$),到达了$10^8$,时间2s足以,极限数据是489ms,如果对时间不放心还可以用堆优化版的dijkstra

代码

#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>

using namespace std;
const int N = 1010;

int n, m, k;
int G[N][N], dist[N];
bool vis[N];

bool dijkstra(vector<int> &path)
{
    memset(vis, 0, sizeof vis);
    memset(dist, 0x3f, sizeof dist);
    dist[path[0]] = 0;

    int k = 0;
    while(true)
    {
        int t = -1;
        for (int i = 1; i <= n; i ++ )
            if(!vis[i] && (t == -1 || (dist[t] > dist[i])))
                t = i;

        if(t == -1)
            break;

        if(dist[t] != dist[path[k]])
            return false;
        t = path[k++];
        vis[t] = true;

        for (int i = 1; i <= n; i ++ )
            dist[i] = min(dist[i], dist[t] + G[t][i]);
    }

    return true;
}

int main()
{
    memset(G, 0x3f, sizeof G);

    cin >> n >> m;
    while (m -- )
    {
        int a, b, c;
        cin >> a >> b >> c;
        G[a][b] = G[b][a] = min(G[a][b], c);
    }

    cin >> k;
    while(k--)
    {
        vector<int> path(n);
        for (int i = 0; i < n; i ++ )
            cin >> path[i];

        cout << (dijkstra(path) ? "Yes" : "No") << endl;
    }
    return 0;
}


活动打卡代码 AcWing 3784. 交换相邻元素

ziuch
23天前

2021/09/03 22:02
思路:思维题,双指针
题意:给定一个1~n的排列,在前n-1个数中有一些数是可以和它后一个数交换位置的,问能否通过一系列交换使得排列升序

先看如果只有一个可以交换的数,那么就只能两两交换,如果有两个连续的可以交换的数,那么就是三个数可以通过交换得到任意的排列,推而广之,如果有k个连续可以交换的数,并且这k + 1个数恰好都是原升序排列对应位置的另一种排列,那么我们就可以通过一系列的交换,使得这k + 1个数恢复成原升序排列的顺序

那么我们通过双指针算法每次找到连续的能够交换的数,随后对这一部分排序,最后判断整个数组是否是升序的即可

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;
const int N = 2e5 + 10;

int n, a[N];
bool st[N];
string s;

bool judge()
{
    for (int i = 1; i <= n; i ++ )
        if(a[i] != i)
            return false;
    return true;
}

int main()
{
    cin >> n;
    for (int i = 1; i <= n; i ++ )
        cin >> a[i];

    cin >> s;
    for (int i = 0; i < s.size(); i ++ )
        st[i + 1] = s[i] == '1';

    for (int i = 1, j = 1; i <= n; i ++ )
    {
        if(st[i])
        {
            j = i + 1;
            while(st[j] && j + 1 <= n)
                j++;

            sort(a + i, a + j + 1);
            i = j;
        }
    }

    cout << (judge() ? "YES" : "NO") << endl;
    return 0;
}


活动打卡代码 AcWing 3798. 幸运年份

ziuch
23天前

2021/09/03 13:42
题意:定义幸运年是年份内非零数只有一个,给出一个年份,问下一个幸运年还需要几年
思路:枚举,思维,构造

一开始直接暴力枚举的,1e9果断超时了
然后总结规律,发现如果一个年份是幸运年的话,那么它必然是一个几十,几百,几千等的数(个位数也是),所以我直接枚举这些数不就行了嘛
外层循环构造个十百千等,内层循环枚举最高位,一旦找到一个大于给定数的就是答案

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

int main()
{
    int t, n;
    cin >> t;
    while(t--)
    {
        cin >> n;

        bool flag = false;
        for(int i = 1; !flag ; i *= 10)
        {
            for (int j = 1; j < 10 && !flag; j ++ )
            {
                if(i * j <= n)
                    continue;
                cout << i * j - n << endl;
                flag = true;
            }
        }
    }
    return 0;
}



ziuch
24天前

7-1 Sexy primes(20分)

Sexy primes are pairs of primes of the form (p, p+6), so-named since “sex” is the Latin word for “six”. (Quoted from http://mathworld.wolfram.com/SexyPrimes.html)

Now given an integer, you are supposed to tell if it is a sexy prime.

Input Specification:

Each input file contains one test case. Each case gives a positive integer N (≤10$^8$).

Output Specification:

For each case, print in a line Yes if N is a sexy prime, then print in the next line the other sexy prime paired with N (if the answer is not unique, output the smaller number). Or if N is not a sexy prime, print No instead, then print in the next line the smallest sexy prime which is larger than N.

Sample Input 1:

47

Sample Output 1:

Yes
41

Sample Input 2:

21

Sample Output 2:

No
23

题意:如果p是质数,p + 6也是质数的话,那么就称这两个数是Sexy primes,现在给出一个数,判断是否是Sexy primes,如果是,则输出Yes,并输出与其配对的另一个数,如果有多个配对,则输出最小的那个。如果不是的话,输出No,再输出大于这个数的最小Sexy primes
思路:质数,枚举

看不懂题目是硬伤,一开始我还以为两个数需要满足在(p, p + 6)内是两个仅有的素数,吓得我素数筛都差点掏出来了,一看范围10e8算了
pair 成对的
要特别注意,对于数p,不仅要和p + 6比较,还要和p - 6比较,因为是成对关系
这样就能很好得解释为什么会有多个配对关系,就是往前配对和往后配对
搞清楚了这些,代码直接信手拈来,O(sqrt(n))判断质数,随便枚举都可

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

bool is_prime(int x)
{
    if(x < 2)
        return false;
    for (int i = 2; i <= x / i; i ++ )
        if(x % i == 0)
            return false;
    return true;
}

int main()
{
    int x;
    cin >> x;
    if(is_prime(x) && is_prime(x - 6))
    {
        cout << "Yes" << endl << x - 6 << endl;
    }
    else if(is_prime(x) && is_prime(x + 6))
    {
        cout << "Yes" << endl << x + 6 << endl;
    }
    else
    {
        cout << "No" << endl;
        for (int i = x; ; i ++ )
        {
            if(is_prime(i) && (is_prime(i - 6) || is_prime(i + 6)))
            {
                cout << i << endl;
                break;
            }
        }
    }
    return 0;
}

7-2 Anniversary(25分)

Zhejiang University is about to celebrate her 122th anniversary in 2019. To prepare for the celebration, the alumni association (校友会) has gathered the ID’s of all her alumni. Now your job is to write a program to count the number of alumni among all the people who come to the celebration.

Input Specification:

Each input file contains one test case. For each case, the first part is about the information of all the alumni. Given in the first line is a positive integer N (≤10$^5$). Then N lines follow, each contains an ID number of an alumnus. An ID number is a string of 18 digits or the letter X. It is guaranteed that all the ID’s are distinct.

The next part gives the information of all the people who come to the celebration. Again given in the first line is a positive integer M (≤10$^5$). Then M lines follow, each contains an ID number of a guest. It is guaranteed that all the ID’s are distinct.

Output Specification:

First print in a line the number of alumni among all the people who come to the celebration. Then in the second line, print the ID of the oldest alumnus – notice that the 7th - 14th digits of the ID gives one’s birth date. If no alumnus comes, output the ID of the oldest guest instead. It is guaranteed that such an alumnus or guest is unique.

Sample Input:

5
372928196906118710
610481197806202213
440684198612150417
13072819571002001X
150702193604190912
6
530125197901260019
150702193604190912
220221196701020034
610481197806202213
440684198612150417
370205198709275042

Sample Output:

3
150702193604190912

题意:给出校友会的人的id,再给出与会者id,问与会者里有多少个校友会成员,如果个数不为零,则输出参加校庆的校友会成员年纪最大的,如果为零,则输出与会者年纪最大的,id就是身份证号码,第7-14位是出生日期
思路:哈希,字符串处理,模拟

这道题倒是一眼就看懂了,做法也比较简单,unordered_set存下所有校友会成员,然后对于每个与会成员都查询依次,查询的复杂度是O(1)的,所以不会超时,每次都更新一下年纪最大的id,substr(6,8)从第6位开始取8位出来,出生日期直接根据字符串比较即可,不难证明出生日期较前的对应的字符串字典序也较小,前提是都是不足位补好零的

恶心的是我没看到个数为零,也要输出年纪最大的与会者id,还好又看了一边题目

#include <iostream>
#include <cstring>
#include <algorithm>
#include <unordered_set>

using namespace std;

unordered_set<string> s;

int n, m;
string str;

int main()
{
    cin >> n;
    while (n -- )
    {
        cin >> str;
        s.insert(str);
    }

    cin >> m;
    int cnt = 0;
    string ans = "", ans1 = "";
    while (m -- )
    {
        cin >> str;
        if(s.count(str))
        {
            cnt++;
            if(ans == "" || ans.substr(6, 8) > str.substr(6, 8))
                ans = str;
        }
        else
        {
            if(ans1 == "" || ans1.substr(6, 8) > str.substr(6, 8))
                ans1 = str;
        }
    }

    if(cnt)
        cout << cnt << endl << ans << endl;
    else
        cout << 0 << endl << ans1 << endl;
    return 0;
}

7-3 Telefraud Detection(25分)

Telefraud(电信诈骗) remains a common and persistent problem in our society. In some cases, unsuspecting victims lose their entire life savings. To stop this crime, you are supposed to write a program to detect those suspects from a huge amount of phone call records.

A person must be detected as a suspect if he/she makes more than K short phone calls to different people everyday, but no more than 20% of these people would call back. And more, if two suspects are calling each other, we say they might belong to the same gang. A makes a short phone call to B means that the total duration of the calls from A to B is no more than 5 minutes.

Input Specification:

Each input file contains one test case. For each case, the first line gives 3 positive integers K (≤500, the threshold(阈值) of the amount of short phone calls), N (≤10&^3&, the number of different phone numbers), and M (≤10$^5$, the number of phone call records). Then M lines of one day’s records are given, each in the format:

caller receiver duration

where caller and receiver are numbered from 1 to N, and duration is no more than 1440 minutes in a day.

Output Specification:

Print in each line all the detected suspects in a gang, in ascending order of their numbers. The gangs are printed in ascending order of their first members. The numbers in a line must be separated by exactly 1 space, and there must be no extra space at the beginning or the end of the line.

If no one is detected, output None instead.

Sample Input 1:

5 15 31
1 4 2
1 5 2
1 5 4
1 7 5
1 8 3
1 9 1
1 6 5
1 15 2
1 15 5
3 2 2
3 5 15
3 13 1
3 12 1
3 14 1
3 10 2
3 11 5
5 2 1
5 3 10
5 1 1
5 7 2
5 6 1
5 13 4
5 15 1
11 10 5
12 14 1
6 1 1
6 9 2
6 10 5
6 11 2
6 12 1
6 13 1

Sample Output 1:

3 5
6

Note: In sample 1, although 1 had 9 records, but there were 7 distinct receivers, among which 5 and 15 both had conversations lasted more than 5 minutes in total. Hence 1 had made 5 short phone calls and didn’t exceed the threshold 5, and therefore is not a suspect.


Sample Input 2:

5 7 8
1 2 1
1 3 1
1 4 1
1 5 1
1 6 1
1 7 1
2 1 1
3 1 1

Sample Output 2:

None

题意:给出m条a给b打了c分钟的通话记录,要求找出哪些人是骗子。成为骗子的条件是,在这一天内给超过k个不同的人进行了短通话(所有a给b打的通话时长不超过5分钟),并且这些人只有不超过20%的人回拨了电话。如果两个人都是骗子,并且两个人都互相打过电话,就认为这两个骗子是一个组织的。最后输出各个组织里的人,组织内部按照id升序,组织输出顺序按照每个组织第一个人的id升序排列。如果一个组织都没有,则输出None
思路:建图,枚举,模拟,并查集

在没看到total duration之前,我是邻接表建图,有点东西,细节拉满
如果是总时长的话,那必然是邻接矩阵建图,这样很方便得能过找到任意两个人的通话时间
还有一个细节就是each other,就是说两个骗子需要互相都给对方打才认为是一个组织的

真是有点东西啊
直接模拟题意,标记好骗子,然后枚举任意两个骗子看是否能过合并,能够合并则合并,合并时把二者较小值作为父节点,随后用set找出所有父节点,再遍历set找出所有相同组织的成员,这里就已经保证了组织外部是有序的,组织内部也是有序的(set保证外部,顺序枚举保证内部),每个组织用vector来存,答案数组是vector嵌套vector,最后判断答案数组的size即可

#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#include <unordered_set>
#include <set>

using namespace std;
const int N = 1010;

bool st[N];
int k, m, n, G[N][N], f[N];

void init()
{
    for (int i = 0; i < N; i ++ )
        f[i] = i;
}

int find(int x)
{
    return f[x] = f[x] == x ? x : find(f[x]);
}

void merge(int x, int y)
{
    int fx = find(x), fy = find(y);
    if(fx > fy)
        swap(fx, fy);
    f[fy] = fx;
}

int main()
{
    init();
    cin >> k >> n >> m;
    while (m -- )
    {
        int a, b, c;
        cin >> a >> b >> c;
        G[a][b] += c;
    }

    for(int i = 1; i <= n; i++)
    {
        unordered_set<int> s;
        for(int j = 1; j <= n; j++)
        {
            if(G[i][j] && G[i][j] <= 5)
                s.insert(j);
        }

        if(s.size() > k)
        {
            int cnt = 0;
            for(auto &x : s)
            {
                if(G[x][i])
                    cnt++;
            }

            if(cnt <= (double)s.size() * 0.2)
                st[i] = true;
        }
    }

    for(int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= n; j ++ )
        {
            if(st[i] && st[j] && G[i][j] && G[j][i])
                merge(i, j);
        }
    }

    set<int> s;
    for(int i = 1; i <= n; i++)
    {
        if(st[i])
            s.insert(f[i]);
    }

    vector<vector<int>> ans;
    for(auto &x : s)
    {
        vector<int> t;
        for (int i = 1; i <= n; i ++ )
            if(st[i] && f[i] == x)
                t.push_back(i);
        ans.push_back(t);
    }

    if(ans.size())
    {
        for(auto &v : ans)
        {
            for (int i = 0; i < v.size(); i ++ )
                cout << v[i] << (i == v.size() - 1 ? '\n' : ' ');
        }
    }
    else
        cout << "None" << endl;

    return 0;
}

7-4 Structure of a Binary Tree(30分)

Suppose that all the keys in a binary tree are distinct positive integers. Given the postorder and inorder traversal sequences, a binary tree can be uniquely determined.

Now given a sequence of statements about the structure of the resulting tree, you are supposed to tell if they are correct or not. A statment is one of the following:

A is the root
A and B are siblings
A is the parent of B
A is the left child of B
A is the right child of B
A and B are on the same level
It is a full tree

Note:

Two nodes are on the same level, means that they have the same depth.
A full binary tree is a tree in which every node other than the leaves has two children.


Input Specification:

Each input file contains one test case. For each case, the first line gives a positive integer N (≤30), the total number of nodes in the binary tree. The second line gives the postorder sequence and the third line gives the inorder sequence. All the numbers in a line are no more than 10&^3&and are separated by a space.

Then another positive integer M (≤30) is given, followed by M lines of statements. It is guaranteed that both A and B in the statements are in the tree.

Output Specification:

For each statement, print in a line Yes if it is correct, or No if not.

Sample Input:

9
16 7 11 32 28 2 23 8 15
16 23 7 32 11 2 28 15 8
7
15 is the root
8 and 2 are siblings
32 is the parent of 11
23 is the left child of 16
28 is the right child of 2
7 and 11 are on the same level
It is a full tree

Sample Output:

Yes
No
Yes
No
Yes
Yes
Yes

题意:给出一颗二叉树的后序遍历和中序遍历,要求重建二叉树并且判断m条语句的正确与否,比如说判断根节点,左右儿子,兄弟,父节点,是否再同一层以及是否为”满”二叉树,所有节点的权值是各不相同的正数,并且不超过1000
思路:树的遍历,重建二叉树,字符串处理

看到这个结构就知道这题稳了,做过两道类似的好像,二叉搜索树的结构和完全二叉树的结构应该是,都是一个类型的,给出遍历序列,重建二叉树之后,给定一些语句根据二叉树结构来判断正确与否
注意到每个节点的权值互不相同,所以我们可以直接通过节点的权值去映射其其他信息
比如节点的左右儿子,父节点,深度,并且这些信息都是可以在建树的时候完成赋值
最后坑的就是这个”满”二叉树的定义
看完这里加了引号你就知道并不是传统意义上的满二叉树了,如果是的话那就是每一层都是满的,只需要记录下最大层数和总结点个数比较一下就行
但是这里我们看Note,里面给出了”满”二叉树的定义,它只是保留了每个节点要么左右儿子都有,要么都没有,换句话来说就是这棵树没有一度点,这个也可以在建树的时候完成赋值,只要建树过程中有一度点存在,就给变量赋值成false
这个字符串,读入一行(记得吸收掉读入行数的回车),然后根据不同语句的特定词进入到不同的语句情况,用sscanf就行反向读入,从字符串读取输入并完成变量赋值

#include <iostream>
#include <cstring>
#include <algorithm>
#include <unordered_map>
#include <cmath>

using namespace std;
const int N = 1010;

int n, m;
bool isFull = true;
int in[N], post[N];
int l[N], r[N], deep[N], p[N], cnt;
unordered_map<int, int> mp;

int build(int il, int ir, int pl, int pr, int deepth, int parent)
{
    int root = post[pr];
    int k = mp[root];

    p[root] = parent;
    deep[root] = deepth;

    if(il < k)
        l[root] = build(il, k - 1, pl , pl + (k - 1 - il), deepth + 1, root);
    if(k < ir)
        r[root] = build(k + 1, ir, pl + (k - 1 - il) + 1, pr - 1, deepth + 1, root);

    if(l[root] + r[root] != 0 && l[root] * r[root] == 0)
        isFull = false;
    return root;
}

void judge(int x, int y)
{
    cout << (x == y ? "Yes" : "No") << endl;
}

int main()
{
    cin >> n;
    for (int i = 0; i < n; i ++ )
        cin >> post[i];

    for (int i = 0; i < n; i ++ )
    {
        cin >> in[i];
        mp[in[i]] = i;
    }

    build(0, n - 1, 0, n - 1, 1, -1);

    cin >> m;
    getchar();
    while (m -- )
    {
        int x, y;
        string str;
        getline(cin, str);

        if(str.find("root") != -1)
        {
            sscanf(str.c_str(), "%d is the root", &x);
            judge(deep[x], 1);
        }
        else if(str.find("siblings") != -1)
        {
            sscanf(str.c_str(), "%d and %d are siblings", &x, &y);
            judge(p[x], p[y]);
        }
        else if(str.find("parent") != -1)
        {
            sscanf(str.c_str(), "%d is the parent of %d", &x, &y);
            judge(x, p[y]);
        }
        else if(str.find("left") != -1)
        {
            sscanf(str.c_str(), "%d is the left child of %d", &x, &y);
            judge(x, l[y]);
        }
        else if(str.find("right") != -1)
        {
            sscanf(str.c_str(), "%d is the right child of %d", &x, &y);
            judge(x, r[y]);
        }
        else if(str.find("level") != -1)
        {
            sscanf(str.c_str(), "%d and %d are on the same level", &x, &y);
            judge(deep[x], deep[y]);
        }
        else
        {
            judge(isFull, true);
        }
    }
    return 0;
}



ziuch
24天前

2021/09/03 02:19
思路:排序,堆排序
题意:按返回一个数组的前k小的部分

方法一:开局sort一下,n是在1e3,是完全可以接受的,再返回前面那一部分即可
时间复杂度:O(logn)

方法二:大根堆,通过优先队列维护长度为k的大根堆(因为每次长度超过k了,就会把最大的数pop掉)
时间复杂度:O(nlogk)

方法三:小根堆维护(看到大家都是大根堆),实际上进行的还是堆排序,只不过只执行k次,每次把选出的最小值放在数组的最后面。由于给出的数组下标是从0开始的,所以一开始需要在最前面插入一个数占位,使得下标从1开始,随后O(n)建堆,随后进行k次的堆调整
时间复杂度:O(n + k*logn)


方法一:sort(19ms)

class Solution {
public:
    vector<int> getLeastNumbers_Solution(vector<int> input, int k) {
        sort(input.begin() , input.end());
        return vector<int>(input.begin(), input.begin() + k);
    }
};

方法二:大根堆(17ms)

class Solution {
public:
    vector<int> getLeastNumbers_Solution(vector<int> input, int k) {
        priority_queue<int> q;
        for(auto &x : input)
        {
            q.push(x);
            if(q.size() > k)
                q.pop();
        }

        vector<int> ans(k--);
        while(q.size())
        {
            ans[k--] = q.top();
            q.pop();
        }

        return ans;
    }
};

方法三:小根堆(15ms)

class Solution {
public:
    int size;
    vector<int> getLeastNumbers_Solution(vector<int> input, int k) {
        input.insert(input.begin(), 0);
        size = input.size() - 1;
        for(int i = size / 2; i; i--)
            down(input, i);

        while(k--)
        {
            swap(input[1], input[size--]);
            down(input, 1);
        }

        vector<int> ans(input.begin() + size + 1, input.end());
        reverse(ans.begin(), ans.end());
        return ans;
    }

    void down(vector<int> &h, int x)
    {
        int u = x;
        if(2 * x <= size && h[2 * x] < h[u])
            u = 2 * x;
        if(2 * x + 1 <= size && h[2 * x + 1] < h[u])
            u = 2 * x + 1;

        if(u != x)
        {
            swap(h[u], h[x]);
            down(h, u);
        }
    }
};


活动打卡代码 AcWing 3814. 矩阵变换

ziuch
24天前

2021/09/02 13:09
思路:贪心,哈希,思维
题意:给定一个01矩阵,可以选择若干列把这一列的0变成1,1变成0,最后输出操作后能够达到的全是1的行数最多有几行

我们可以把每一行当做一个字符串来去看,对于每一个字符串来说,使得它变成全1的方式有且只有一种,所以说我们只需要去统计每一种字符串出现的个数,出现次数最多的字符串,我们就贪心得都把他们变成全一即可

#include <iostream>
#include <cstring>
#include <algorithm>
#include <unordered_map>

using namespace std;

unordered_map<string, int> mp;

int main()
{
    int n;
    string s;

    cin >> n;
    while (n -- )
    {
        cin >> s;
        mp[s] ++;
    }

    int m = 1;
    for(auto &x : mp)
        m = max(m, x.second);

    cout << m << endl;
    return 0;
}



ziuch
25天前

2021/09/02 12:05

Day2

思路:链表,双指针
题意:输出倒数第k个链表节点,如果长度不足k个输出NULL

可以设置快慢指针,即快指针先移动k个,随后慢指针从头节点和快指针同时出发,快指针到达链表尾时,慢指针指向的就是倒数第k个节点

但是这里需要判断链表长度是否小于k,需要转个弯,考虑到双指针的时间复杂度是一样的只是长度不一样,所以采用最直接的思路,先遍历一遍求出链表长度,再遍历到n-k个节点输出即可,遍历之前需要判断长度是否大于等于k

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* findKthToTail(ListNode* pListHead, int k) {

        int n = 0;
        for(auto head = pListHead; head != NULL; head = head->next)
            n++;
        if(k > n)
            return NULL;

        ListNode *p = pListHead;
        for(int i = 0; i < n - k; i++)
            p = p->next;
        return p;
    }
};