传送门

A 你也喜欢数学吗

B Middle

C 硬币游戏

D 松鼠回家

就是一个二分+最短路，二分答案，用二分的答案去跑最短路，跑最短路的时候要加限制条件，就是所经过的每个点所在的权值必须严格下于等于二分的答案，开个dis数组记录路径，最后判断终点 是否能够到达，记得把dis数组初始化为负无穷。

#include<bits/stdc++.h>
#define IOS ios::sync_with_stdio(false),cin.tie(nullptr), cout.tie(nullptr);
#define met_0(a) memset(a,0,sizeof a)
#define met_1(a) memset(a,-1,sizeof a)
#define met_x(a) memset(a,0x3f,sizeof a)
#define mpy(a,b) memcopy(a,sizeof b,b)
#define ll long long
#define ld long double
#define ull unsigned long long
#define fi first
#define se second
#define PII pair<int,int>
#define PDD pair<double,double>
#define PCI pair<char,int>
#define endl '\n'
const int N = 10100;
const int M = 110;
const int MOD = 1e9 + 7;
const int EPS = 1e-8;
const int INF = 0x3f3f3f3f;

using namespace  std;

int n, m, st, ed, h;
int a[N];
int dis[N];
bool vis[N];
vector<PII> g[N];

void dijskra(int x) {
    met_x(dis);
    met_0(vis);
    priority_queue<PII, vector<PII >, greater<PII>> pq;
    dis[st] = 0;
    pq.push({0, st});
    while (pq.size()) {
        auto t = pq.top();
        pq.pop();
        int node = t.se;
        if (vis[node])continue;
        vis[node] = true;
        for (auto i: g[node]) {
            if (dis[i.fi] > dis[node] + i.se && a[i.fi] <= x) {
                dis[i.fi] = dis[node] + i.se;
                pq.push({dis[i.fi], i.fi});
            }
        }
    }
}

void solve() {
    cin >> n >> m >> st >> ed >> h;
    for (int i = 1; i <= n; i++) cin>>a[i];
    while (m--) {
        int x, y, z;
        cin >> x >> y >> z;
        g[x].emplace_back(y, z);
        g[y].emplace_back(x, z);
    }
    int l = -1, r = 1e7 + 1;
    while (l < r) {
        int mid = l + r >> 1;
        dijskra(mid);
        if (dis[ed] <= h)r = mid;
        else l = mid + 1;
    }
    if (l == -1 || l == 1e7 + 1)cout << -1 << endl;
    else cout << l << endl;
}

int main() {
    IOS;
    int h_h = 1;
    //cin >> h_h;
    while (h_h--)solve();
    return 0;
}

E 动物朋友

求一段连续区间的和为给定的值，一眼就是双指针，但是总感觉我的这个双指针怪怪的，一个控制左边界，一个控制有边界，先预处理前缀和，当总和大于等于目标时，左边++，等于时将答案++，小于时把右边++，复杂度O(n)

#pragma GCC optimize(2)
#pragma GCC optimize(3)

#include<bits/stdc++.h>
#define IOS ios::sync_with_stdio(false),cin.tie(nullptr), cout.tie(nullptr);
#define met_0(a) memset(a,0,sizeof a)
#define met_1(a) memset(a,-1,sizeof a)
#define mpy(a,b) memcopy(a,sizeof b,b)
#define int long long
#define ld long double
#define ull unsigned long long
#define fi first
#define se second
#define endl '\n'
const int N = 1000100;
const int M = 110;
const int MOD = 1e9 + 7;
const int EPS = 1e-8;

using namespace  std;

int a[N], s[N];

void solve() {
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        s[i] = a[i] + s[i-1];
    }
    int ans = 0;
    //for(int i=1;i<=n;i++)cout<<s[i]<<' ';cout<<endl;
    for (int i = 1, j = 1; i <= n && j <= n; ) {
        int sum=s[j]-s[i-1];
        if(sum>m)i++;
        else if(sum==m)ans++,i++;
        else j++;
    }
    cout << ans << endl;
}

int32_t main() {
    //IOS;
    int h_h = 1;
    //cin >> h_h;
    while (h_h--)solve();
    return 0;
}

F 松鼠排序

以前记得做过类似的题，结论就是遇到和下标不一样的九八目标值交换过来，最后答案就是最优的，但其实这题应该使用并查集来做，并查集的板子题

赛事AC的代码

#pragma GCC optimize(2)
#pragma GCC optimize(3)

#include<bits/stdc++.h>
#define IOS ios::sync_with_stdio(false),cin.tie(nullptr), cout.tie(nullptr);
#define met_0(a) memset(a,0,sizeof a)
#define met_1(a) memset(a,-1,sizeof a)
#define mpy(a,b) memcopy(a,sizeof b,b)
#define ll long long
#define ld long double
#define ull unsigned long long
#define fi first
#define se second
#define endl '\n'
const int N = 200010;
const int M = 110;
const int MOD = 1e9 + 7;
const int EPS = 1e-8;

using namespace  std;

void solve() {
    int n;
    cin >> n;
    vector<int> a(n + 1);
    map<int, int> mp;
    for (int i = 1; i <= n; i++)cin >> a[i], mp[a[i]] = i;
    int ans = 0;
    for (int i = 1; i <= n; i++) {
        if (a[i] == i)continue;
        else {
            int x=a[i];
            swap(a[i], a[mp[i]]);
            mp[x]=mp[i];
            mp[i]=i;
            ans++;
        }
    }
    cout << ans << endl;
}

int32_t main() {
    IOS;
    int h_h = 1;
    //cin >> h_h;
    while (h_h--)solve();
    return 0;
}

正解使用并查集

G Reverse

贪心的来做，就找连续一的个数最大的，两个加起来即可，注意坑点，如果开动态的vector要注意可能会出现全是零的情况要特判，不然会出现段错误的情况

#pragma GCC optimize(2)
#pragma GCC optimize(3)

#include<bits/stdc++.h>
#define IOS ios::sync_with_stdio(false),cin.tie(nullptr), cout.tie(nullptr);
#define met_0(a) memset(a,0,sizeof a)
#define met_1(a) memset(a,-1,sizeof a)
#define mpy(a,b) memcopy(a,sizeof b,b)
#define int long long
#define ld long double
#define ull unsigned long long
#define fi first
#define se second
#define endl '\n'
const int N = 200010;
const int M = 110;
const int MOD = 1e9 + 7;
const int EPS = 1e-8;

using namespace  std;

void solve() {
    int n;
    string s;
    cin >> n >> s;
    int cnt = 0;
    vector<int> ans;
    for (auto i: s) {
        if (i == '1')cnt++;
        else {
            if (cnt == 0)continue;
            ans.push_back(cnt);
            cnt = 0;
        }
    }
    if (cnt)ans.push_back(cnt);
    //for (auto i: ans)cout << i << ' ';
    sort(ans.begin(), ans.end());
    int len=ans.size();
    if(len==0)cout<<0<<endl;
    else if (len == 1)cout << ans[len-1] << endl;
    else cout << ans[len-2] + ans[len-1] << endl;
}

int32_t main() {
    //IOS;
    int h_h = 1;
    //cin >> h_h;
    while (h_h--)solve();
    return 0;
}

H 迷宫探险

因为权值只有两种情况，所以可以使用点单的BFS即可遇到弹射器的和不遇到分两种情况扩展即可，要注意不一定一个点制备走一次，可能会被走多次，所以不能直走一次，要根据距离来过更新 dis数组

#include<bits/stdc++.h>
#define IOS ios::sync_with_stdio(false),cin.tie(nullptr), cout.tie(nullptr);
#define met_0(a) memset(a,0,sizeof a)
#define met_1(a) memset(a,-1,sizeof a)
#define met_x(a) memset(a,0x3f,sizeof a)
#define mpy(a,b) memcopy(a,sizeof b,b)
#define ll long long
#define ld long double
#define ull unsigned long long
#define fi first
#define se second
#define PII pair<int,int>
#define PDD pair<double,double>
#define PCI pair<char,int>
#define endl '\n'
const int N = 200010;
const int M = 110;
const int MOD = 1e9 + 7;
const int EPS = 1e-8;
const int INF = 0x3f3f3f3f;

using namespace  std;

void solve() {
    int n, m;
    cin >> n >> m;
    vector<vector<char>> g(n + 10, vector<char>(m + 10, 0));
    vector<vector<bool>> vis(n + 10, vector<bool>(m + 10, 0));
    vector<vector<int>> dis(n + 10, vector<int>(m + 10, INF));
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            cin >> g[i][j];
        }
    }
    map<PII, int> pos;
    int k;
    cin >> k;
    while (k--) {
        int x, y, cnt;
        cin >> x >> y >> cnt;
        pos[{x, y}] = cnt;
    }
    queue<PII > q;
    q.push({1, 1});
    int dx[4] = {0, 1, 0, -1};
    int dy[4] = {1, 0, -1, 0};
    vis[1][1] = true;
    dis[1][1] = 0;
    while (q.size()) {
        auto t = q.front();
        q.pop();
        int x = t.fi;
        int y = t.se;
        for (int i = 0; i < 4; i++) {
            int xx, yy;
            if (g[x][y] == '.') {
                xx = x + dx[i];
                yy = y + dy[i];
            } else if (g[x][y] == '*') {
                xx = x + dx[i] * pos[{x, y}];
                yy = y + dy[i] * pos[{x, y}];
            }
            if (xx >= 1 && xx <= n && yy >= 1 && yy <= m && g[xx][yy] != '#') {
                if (g[x][y] == '.'&&dis[xx][yy] > dis[x][y] + 1)dis[xx][yy] = dis[x][y] + 1, q.push({xx, yy});
                else if (g[x][y] == '*'&&dis[xx][yy] > dis[x][y])dis[xx][yy] = dis[x][y], q.push({xx, yy});;
            }
        }
    }
    if (dis[n][m] == INF)cout << -1 << endl;
    else cout << dis[n][m] << endl;
}

int32_t main() {
    IOS;
    int h_h = 1;
    //cin >> h_h;
    while (h_h--)solve();
    return 0;
}

I 松鼠采松果

J 合唱比赛

去除一个最低分就是分数最高，去除一个最高分就是分数最低

#pragma GCC optimize(2)
#pragma GCC optimize(3)

#include<bits/stdc++.h>
#define IOS ios::sync_with_stdio(false),cin.tie(nullptr), cout.tie(nullptr);
#define met_0(a) memset(a,0,sizeof a)
#define met_1(a) memset(a,-1,sizeof a)
#define mpy(a,b) memcopy(a,sizeof b,b)
#define ll long long
#define ld long double
#define ull unsigned long long
#define fi first
#define se second
#define endl '\n'
const int N = 200010;
const int M = 110;
const int MOD = 1e9 + 7;
const int EPS = 1e-8;

using namespace  std;

void solve() {
    int n;
    cin >> n;
    ll sum = 0;
    int mx = INT_MIN;
    int mn = INT_MAX;
    for (int i = 0; i<n; i++) {
        int x;
        cin >> x;
        sum+=x;
        mx = max(mx, x);
        mn = min(mn, x);
    }
    printf("%.6f %.6f", (sum - mx) * 1.0 / (n - 1), (sum - mn) * 1.0 / (n - 1));
}

int32_t main() {
    //IOS;
    int h_h = 1;
    //cin >> h_h;
    while (h_h--)solve();
    return 0;
}

K 以撒和隐藏房间

按照题目意思模拟模拟就行注意只能有三个相邻房间

#pragma GCC optimize(2)
#pragma GCC optimize(3)

#include<bits/stdc++.h>
#define IOS ios::sync_with_stdio(false),cin.tie(nullptr), cout.tie(nullptr);
#define met_0(a) memset(a,0,sizeof a)
#define met_1(a) memset(a,-1,sizeof a)
#define mpy(a,b) memcopy(a,sizeof b,b)
#define ll long long
#define ld long double
#define ull unsigned long long
#define fi first
#define se second
#define endl '\n'
const int N = 200010;
const int M = 110;
const int MOD = 1e9 + 7;
const int EPS = 1e-8;

using namespace  std;

int n,m ;
char g[1000][1000];
int dy[4] = {0, 1, 0, -1};
int dx[4] = {1, 0, -1, 0};

bool check(int x,int y) {
    int cnt = 0;
    for (int i = 0; i < 4; i++) {
        int xx = x + dx[i];
        int yy = y + dy[i];
        if (xx < 0 || xx >= n || yy < 0 || yy >= m)continue;
        if (g[xx][yy] == '2')return false;
        if (g[xx][yy] == '1')cnt++;
    }
    if (cnt == 3)return true;
    return false;
}

void solve() {
    cin >> n >> m;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> g[i][j];
        }
    }
    int ans = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if(g[i][j]=='0') {
                if (check(i, j))ans++;
            }
        }
    }
    if (ans)cout << "YES" << endl << ans << endl;
    else cout << "NO" << endl;
}

int32_t main() {
    //IOS;
    int h_h = 1;
    //cin >> h_h;
    while (h_h--)solve();
    return 0;
}

L 中位数

实际上分析完题目以后就是求一个数前面有多少个数，本质上就是一个单点修改和区间修改，使用二分加树状数组或者线段树也行，但这个题好像也可以使用对顶堆去维护，分别维护中位数两边的数的个数

二分+树状数组

#include<bits/stdc++.h>
#define IOS ios::sync_with_stdio(false),cin.tie(nullptr), cout.tie(nullptr);
#define met_0(a) memset(a,0,sizeof a)
#define met_1(a) memset(a,-1,sizeof a)
#define met_x(a) memset(a,0x3f,sizeof a)
#define mpy(a,b) memcopy(a,sizeof b,b)
#define ll long long
#define ld long double
#define ull unsigned long long
#define fi first
#define se second
#define PII pair<int,int>
#define PDD pair<double,double>
#define PCI pair<char,int>
#define endl '\n'
const int N = 1000010;
const int M = 110;
const int MOD = 1e9 + 7;
const int EPS = 1e-8;
const int INF = 0x3f3f3f3f;

using namespace  std;

int tr[N];
int a[N];
int n, m;


int lowbit(int x) {
    return x & (-x);
}

void add(int x, int k) {
    for (int i = x; i < N; i += lowbit(i))tr[i] += k;
}

int query(int x) {
    int res = 0;
    for (int i = x; i; i -= lowbit(i))
        res += tr[i];
    return res;
}

void solve() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) cin >> a[i], add(a[i], 1);
    while (m--) {
        int p, x;
        cin >> p >> x;
        add(a[p], -1);
        a[p] = x;
        add(x, 1);
        int l = 1, r = 1e6;
        while (l < r) {
            int mid = l + r >> 1;
            if (query(mid) >= (n / 2 + 1))r = mid;
            else l = mid + 1;
        }
        cout << l << endl;
    }
}

int main() {
    IOS;
    int h_h = 1;
    //cin >> h_h;
    while (h_h--)solve();
    return 0;
}