永世隔绝の理想乡

Garden of Avalon

0%

AcWing2022春季每日一题 | 第一周

发表于 分类于

AcWing2022春季每日一题，第一周题解

AcWing 3346. 你知道你的ABC吗—原题链接

题目标签：思维题 | 数学推理

思路：
由于7个数进行排序，第一个第二个数一定是a和b，第三个数有两种可能，要么是c，要么是a+b，如果是后者的话那么第四个数一定是c，也就是说进行一个小判断就行（某场cf的a题原题）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include <bits/stdc++.h>
using namespace std;

int main()
{
    int a[7];
    for(int i=0; i<7; i++) cin >> a[i];
    sort(a, a+7);
    cout << a[0] << " " << a[1] << " ";
    //判断第三个数是c还是a+b
    if(a[0] + a[1] == a[2]) cout << a[3];
    else cout << a[2];
    cout << endl;
    return 0;
}

AcWing 3358. 放养但没有完全放养—原题链接

题目标签：字符串 | 模拟 | 贪心(?)

思路1：
题目要求输出唱了多少遍，也就是一共需要听几遍才能按顺序听完目标字符串，那么：
Q：为什么需要再听一边
A：因为当前遍历到的字母之后不存在下一个字母，所以需要再听一遍
Q：什么时候需要再听一遍
A：当前字母出现的位置在之前字母的前边或者相同，因为如果在后边的话继续听下去是可以听到的
因此本题就是根据每个字母的位置进行比对

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
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;

unordered_map<char, int> mp;
string s, s0;

int main()
{
    cin >> s0 >> s;
    for(int i=1; i<=26; i++)
    {
        mp.insert({s0[i], i});
    }
    
    char flag = s[0];
    int cnt = 1;
    for(int i=1; i<s.size(); i++)
    {
        char c = s[i];
        int a = mp[flag], b = mp[c];
        if(a >= b) cnt++;
        flag = c;
    }
    cout << cnt << endl;
    // system("pause");
    return 0;
}

（标答）思路2：
对上述的思路进行优化，字母顺序的比对直接遍历一遍就可以了 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;

int p[26];
string s;

int main()
{
    cin >> s;
    for(int i=0; i<s.size(); i++) p[s[i] - 'a'] = i;
    
    cin >> s;
    int cnt = 1;
    for(int i=1; i<s.size(); i++)
    {
        if(p[s[i] - 'a'] <= p[s[i-1] - 'a']) cnt++;
    }
    cout << cnt << endl;
    return 0;
}

AcWing 3370. 牛年—原题链接

题目标签：（自以为是的）DFS | 模拟

思路1：
建图DFS， 虽然AC了但是是很绕弯子的思路拿到题的时候很自信的以为是图的深搜，结果敲了将近一个小时越来越觉得不对劲…虽说很别扭但是逻辑上可以说得通，并且很幸运的能够AC……坐等正解，看个乐子吧就当

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
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;

const int N = 110;
const int INF = 0x3f3f3f3f;
int n, cnt = 1, res;
int born[2 * N];
bool st[2 * N];
int h[N * N], w[N * N], e[N * N], ne[N * N], idx;
unordered_map<string, int> mp, day;
string dayy[12] = {"Ox", "Tiger", "Rabbit", "Dragon", "Snake", "Horse", "Goat", "Monkey", "Rooster", "Dog", "Pig", "Rat"};

void add(int a, int b, int u)
{
    e[idx] = b, ne[idx] = h[a], w[idx] = u, h[a] = idx++;
}

void dfs(int node, int sum)
{
    st[node] = true;
    if(node == mp["Bessie"])
    {
        res = sum;
        return;
    }

    for(int i=h[node]; i!=-1; i=ne[i])
    {
        int j = e[i];
        if(st[j] == false)
        {
            dfs(j, sum + w[i]);
        }
    }
}

int main()
{
    memset(h, -1, sizeof h);
    for(int i=0; i<12; i++)
    {
        day.insert({dayy[i], i});
    }
    cin >> n;
    mp["Bessie"] = 0;
    born[0] = mp["Ox"];
    // scanf("%d",&n);
    for(int i=0; i<n; i++)
    {
        string str[8];
        for(int j=0; j<8; j++) cin >> str[j];
        string name1 = str[0], name2 = str[7], year = str[4], sta = str[3];
        
        if(mp[name1] == 0) mp[name1] = cnt++;
        if(mp[name2] == 0) mp[name2] = cnt++;

        born[mp[name1]] = day[year];
        int a = born[mp[name1]], b = born[mp[name2]], d;
        if(a == b) d = 12;
        else if(a > b && sta[0] == 'p')
        {
            d = 12 - a + b;
        }
        else if(a > b && sta[0] == 'n')
        {
            d = a - b;
        }
        else if(a < b && sta[0] == 'p')
        {
            d = b - a;
        }
        else if(a < b && sta[0] == 'n')
        {
            d = 12 - b + a;
        }

        if(sta[0] == 'p')
        {
            add(mp[name1], mp[name2], d);
            add(mp[name2], mp[name1], -1 * d);
        }
        else
        {
            add(mp[name2], mp[name1], d);
            add(mp[name1], mp[name2], -1 * d);
        }
    }

    dfs(mp["Elsie"], 0);
    cout << abs(res) << endl;
    // system("pause");
    return 0;
}

（标答）思路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
#include <bits/stdc++.h>
using namespace std;

unordered_map<string, int> id = {
    {"Ox", 0}, {"Tiger", 1}, {"Rabbit", 2},
    {"Dragon", 3}, {"Snake", 4}, {"Horse", 5}, 
    {"Goat", 6}, {"Monkey", 7}, {"Rooster", 8}, 
    {"Dog", 9}, {"Pig", 10}, {"Rat", 11}
};
unordered_map<string, int> p;
int n;
string s[8];

int main()
{
    cin >> n;
    p["Bessie"] = 0;
    
    while(n--)
    {
        for(int i=0; i<8; i++) cin >> s[i];
        if(s[3] == "previous")
        {
            int x = p[s[7]], y = id[s[4]];
            int t = ((x - y) % 12 + 12) % 12;
            if(t == 0) t = 12;
            p[s[0]] = x - t;
        }
        else
        {
            int x = p[s[7]], y = id[s[4]];
            int t = ((y - x) % 12 + 12) % 12;\
            if(t == 0) t = 12;
            p[s[0]] = x + t;
        }
    }
    
    cout << abs(p["Elsie"]) << endl;
    return 0;
}

AcWing 3745. 牛的学术圈 I—原题链接

题目标签：双指针 | 模拟 | 枚举

思路：
我愿称之为本周最难的题
当然难的部分在于对于既定答案的判断对错方法，尽管很抽象但是逻辑性还是很强的
首先我们知道可以最多改变l次，在排好序的基础上，我们希望能充分利用这l次+1的机会就必须在同一段上，并且加上这一段之后h可以有效的加一
顺着这个思路，假定我们遍历到了h，我们需要先定位到值为h-1的部分（i指针）。在定位到大于等于h-1的部分（j指针），此时区间被分为3部分：
1-j的部分：这部分的值恒大于等于h，也就是从j开始向左的所有数都不需要变化
j-i的部分：这部分的值都大于等于h-1，也就是从i开始到j（不包含j）的所有数是需要变化的数
i-n的部分：这部分就算加了1也达不到h，也就是不需要变化的部分
如果我们假定的h成立，在将(j, i]的数加一之后，前h个数一定能保证大于h，也就是这个h成立了 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <bits/stdc++.h>
using namespace std;

const int N = 1e5 + 10;
int n, k;
int q[N];

int main()
{
    cin >> n >> k;
    for(int i=1; i<=n; i++) cin >> q[i];
    sort(q+1, q+1+n, greater<int>());

    int res = 0;
    for(int i=1, j=n; i<=n; i++)
    {
        //假定当h等于i成立时
        while(j && q[j] < i) j--; //找到大于等于h的那个点（不需要改变的左端点）
        if(q[i] >= i - 1 && i - j <= k) res = i;//保证q(j, i]中加一能大于等于i，并且这个区间的长度长度等于k
    }

    cout << res << endl;
    return 0;
}

AcWing 1459. 奶牛体操—原题链接

题目标签：枚举

思路：
满足题意的条件是，任意两个数，在所有排名中的先后次序都是一样的，其中一方指向另一方的方向不会变，因此可以开一个二位数组，横坐标指向纵坐标表示一次排名。
遍历结束后，如果只有一方指向另一方而没有反过来的方向，则成立。

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 <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;

const int N = 25;
int n, k;
int a[N];
bool st[N][N];

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

        for(int i=1; i<=n-1; i++)
        {
            for(int j=i+1; j<=n; j++)
            {
                st[a[i]][a[j]] = true;
            }
        }
    }

    int res = 0;
    for(int i=1; i<=n; i++)
    {
        for(int j=i+1; j<=n; j++)
        {
            if(st[i][j]^ st[j][i]) res++;
        }
    }
    cout << res << endl;
    return 0;
}