滚去学工分了，祝各位愉快

第十四届南京工程学院程序设计及应用竞赛校外同步赛 原创

A 最小半径

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include<bits/stdc++.h>
using namespace std;
int n, res, x1, x2;

int main()
{
    ios::sync_with_stdio(0), cin.tie(0);
    cin >> n;
    res = INT_MAX;
    for(int i = 1; i <= n; ++i)
    {
        // 读入每组数据,计算最小值
        cin >> x1 >> x2;
        res = min(abs(x1 - x2), res);
    }
    cout << res;
}

B 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
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
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 5;
typedef long long ll;

class Player
{
public:
    int nums, whole, id, rank;
} players[N];
int n, m;
int cmp1(Player p1, Player p2)
{
    return p1.nums == p2.nums ? p1.whole < p2.whole : p1.nums > p2.nums;
}
int cmp2(Player p1, Player p2)
{
    return p1.id < p2.id;
}
int main()
{
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    cin >> n >> m;
    int i, j;
    for(i = 1; i <= m; ++i)
    {
        players[i].nums = 0, players[i].whole = 0, players[i].id = i;
        for(j = 1; j <= n; ++j)
        {
            int x, y, z;
            cin >> x >> y >> z;
            if(z == 1)
            {
                players[i].nums++;
                players[i].whole += (x - 1) * 20 + y;
            }
        }
    }
    sort(players + 1, players + m + 1, cmp1);
    players[1].rank = 1;
    for(i = 2; i <= m; ++i)
    {
        if(players[i].nums == players[i - 1].nums && players[i].whole == players[i - 1].whole)
        {
            players[i].rank = players[i - 1].rank;
        }
        else
            players[i].rank = i;
    }
    //判相同
    //最后要变回去
    sort(players + 1, players + m + 1, cmp2);
    for(i = 1; i <= m; ++i) cout << players[i].rank << '\n' << players[i].nums << '\n' << players[i].whole << '\n';
}

C 李渊的准备

普通RMQ问题

线段树可以解决

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
#include <bits/stdc++.h>
#define int long long
#define LL long long
#define db double
#define ios                                                                                                            \
    ios::sync_with_stdio(0);                                                                                           \
    cin.tie(0);
#define endl '\n'
using namespace std;
 
const int N = 2e5 + 5;
const int INF = 0x3f3f3f3f3f3f3f3f;
 
typedef pair<int, int> PII;
 
int tr[N * 4];
int a[N];
int n, q, t;
 
int ls(int p)
{
    return p << 1;
}
int rs(int p)
{
    return p << 1 | 1;
}
 
void up(int p)
{
    tr[p] = max(tr[ls(p)], tr[rs(p)]);
}
 
void build(int p, int l, int r)
{
    if (l == r)
    {
        tr[p] = a[l];
        return;
    }
    int mid = l + r >> 1;
    build(ls(p), l, mid);
    build(rs(p), mid + 1, r);
    up(p);
}
 
int ques(int L, int R, int p, int l, int r)
{
    if (L <= l && r <= R)
        return tr[p];
    int mid = l + r >> 1;
    int ma = -INF;
    if (L <= mid)
        ma = max(ma, ques(L, R, ls(p), l, mid));
    if (R > mid)
        ma = max(ma, ques(L, R, rs(p), mid + 1, r));
    return ma;
}
 
void sol()
{
    cin >> n >> q >> t;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    build(1,1,n);
    while(q--)
    {
        int l,r;
        cin>>l>>r;
        int res=ques(l,r,1,1,n);
        cout<<res<<' ';
        if(res>=t)
        cout<<"YES"<<endl;
        else
        cout<<"NO"<<endl;
    }
}
 
signed main()
{
    ios;
    int T = 1;
    //cin >> T;
    while (T--)
        sol();
    return 0;
}

ST也可

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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 2e6 + 3;

int n, t, q ,arr[N][32];

int query(int l, int r)
{
    int k = (int)(log((r - l + 1) * 1.0) / log(2.0));
    return max(arr[l][k], arr[r - (1 << k) + 1][k]);
}

int main()
{
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    cin >> n >> t >> q;
    for (int i = 1; i <= n; ++i)
        cin >> arr[i][0];
    for (int j = 1; j <= (int)(log(n * 1.0) / log(2.0)); ++j)
    {
        for (int i = 1; i + (1 << j) - 1 <= n; ++i)
        {
            arr[i][j] = max(arr[i][j - 1], arr[i + (1 << (j - 1))][j - 1]);
        }
    }
    while (t--)
    {
        int l, r;
        cin >> l >> r;
        int res = query(l, r);
        string flag = res >= q ? "YES\n" : "NO\n";
        cout << res << " " <<  flag;
    }
}

E

相邻上下可以跳

还可以跳到相邻最近

因此只需要存图这样写bfs即可

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
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 5;
int n, arr[N], vis[N], dis[N];
vector<int> edge[N];
map<int, int> mp;
queue<int> qu;

int bfs()
{
    while (!qu.empty())
    {
        int now = qu.front();
        qu.pop();
        for (auto y : edge[now])
        {
            if (y == n)
                return dis[now] + 1;
            if (vis[y])
                continue;
            qu.push(y), vis[y] = 1, dis[y] = dis[now] + 1;
        }
    }
    return 0;
}

int main()
{
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    cin >> n;
    for (int i = 1; i <= n; ++i)
    {
        cin >> arr[i];
        if (i != n)
        {
            edge[i].push_back(i + 1);
            edge[i + 1].push_back(i);
        }
        if (mp.count(arr[i]))
            edge[mp[arr[i]]].push_back(i); // 能量值波动一样的
        mp[arr[i]] = i;
    }
    qu.push(1), vis[1] = 1, dis[1] = 0;
    cout << bfs();
}

F

模拟题（）

马蜂很好，很好理解

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
95
96
97
98
99
100
101
#include <bits/stdc++.h>
#define int long long
#define LL long long
#define db double
#define ios                                                                                                            \
    ios::sync_with_stdio(0);                                                                                           \
    cin.tie(0);
#define endl '\n'
using namespace std;

const int N = 2e5 + 5;
const int INF = 0x3f3f3f3f3f3f3f3f;

typedef pair<int, int> PII;

void sol()
{
    int n, m;
    cin >> n >> m;
    map<int, int> mp;
    vector<int> a, b;
    for (int i = 1; i <= n; i++)
    {
        int t;
        cin >> t;
        int f = 0;
        mp.clear();
        for (int j = 1; j <= t; j++)
        {
            int tt;
            cin >> tt;
            if(f) continue;
            mp[tt]++;
            if (mp[tt] > t / 2)
            {
                f = 1;
                a.push_back(tt);
            }
        }
        if (f == 0)
            a.push_back(5);
    }
    
    for (int i = 1; i <= m; i++)
    {
        int t;
        cin >> t;
        int f = 0;
        mp.clear();
        for (int j = 1; j <= t; j++)
        {
            int tt;
            cin >> tt;
            if(f) continue;
            mp[tt]++;
            if (mp[tt] > t / 2)
            {
                f = 1;
                b.push_back(tt);
            }
        }
        if (f == 0)
            b.push_back(5);
    }
    sort(a.begin(), a.end());
    for (auto aa : a)
        cout << aa << ' ';
    cout << endl;
    sort(b.begin(), b.end());
    for (auto bb : b)
    {
        cout << bb << ' ';
        a.push_back(bb);
    }
    cout << endl;
    sort(a.begin(), a.end());
    if((n+m)%2==0)
    {
    	int mid=a.size()/2;
    	int ans=a[mid]+a[mid-1]>>1;
    	cout<<ans<<endl;
    }
    else
    {
    	int mid = a.size() / 2;
    cout<<a[mid]<<endl;	
    }
    
    //cout << endl;
}

signed main()
{
    ios;
    int T = 1;
    // cin>>T;
    while (T--)
        sol();
    return 0;
}

G

单调栈问题

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
#include <bits/stdc++.h>
using namespace std;
int main() {
    cin.tie(nullptr)->sync_with_stdio(false);
     
    string s;
    cin >> s;
     
    int n;
    cin >> n;
     
    vector<int> stk;
    vector<int> a(n);
    for (auto &i : a) {
        cin >> i;
    }
     
    if (s[0] == 'f') {
        vector<int> sb(n);
        for (int i = 0; i < n; i++) {
            while (!stk.empty() && a[stk.back()] > a[i]) {
                stk.pop_back();
            }
            sb[i] = stk.size() + 1;
            stk.push_back(i);
        }
        for (auto &i : sb) {
            cout << i << ' ';
        }
    } else {
        vector<int> sb(n);
        for (int i = n - 1; i >= 0; i--) {
            while (!stk.empty() && a[stk.back()] > a[i]) {
                stk.pop_back();
            }
            sb[i] = stk.size() + 1;
            stk.push_back(i);
        }
        for (auto &i : sb) {
            cout << i << ' ';
        }
    }
}

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
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
#include <bits/stdc++.h>
using namespace std;
 
#define ll long long
#define pii pair<int, int>
const int INF = 1e9;
const int N = 2e5+10;
vector<pii> vec[N];
int dis[N];
int in[N];
 
void solve() {
    int n, m, i, j, u, v, w;
    cin>>n>>m;
    for (i = 1; i <= m; i++) {
        cin>>u>>v>>w;
        vec[u].push_back(pii(v, w));
        in[v]++;
    }
    queue<int> q;
    for (i = 1; i <= n; i++) {
        if (in[i] == 0) {
            q.push(i);
            dis[i] = 0;
        }
    }
    int num = 0; 
    while (!q.empty()) {
        u = q.front();
        q.pop();
         
        num++;
         
        for (i = 0; i < vec[u].size(); i++) {
            v = vec[u][i].first;
            w = vec[u][i].second;
            dis[v] = max(dis[v], dis[u]+w);
            if (--in[v] == 0) {
                q.push(v);
            }
        }
    }
    if (num < n) {
        cout<<"NOWAY"<<'\n';
        return;
    }
     
    int ans = -1;
    for (i = 1; i <= n; i++) {
        ans = max(ans, dis[i]);
    }
    cout<<ans<<'\n';
}
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int T = 1;
//  cin>>T;
    while (T--) {
        solve();
    }
    return 0;
}

I和D暂且开摆