cf d4 1692 d1

初来乍到，用刚刚结束的div4试试编辑器

代码大部分都是给出的答案

原题题解：1692 Editorial

A 马拉松

A:Marathon

题目描述

考察单条件判断

给定四个代表马拉松距离的值，比对比第一个大的人数

解题思路

a和所有人比较，比较得出的结果直接代表了答案

题解

#include <iostream>
using namespace std;
int t;
int a,b,c,d;
int n;
int main(){
    cin >> t;
    while( t-- )
    {
        n = 0;
        cin >> a >> b >> c >> d;
        if (b > a) n++;
        if (c > a) n++;
        if (d > a) n++;
        cout << n << endl;
    }
    return 0;
}

B 不重复值

B All Distinct

题目描述

考察数据结构

给定一个数列，在数列中删除一个数对，保证正序的不重复且每次删除后数组长度最大

解题思路

先排序，再去重，如果剩下的元素和原来的数组奇偶性相同，两个两个减就不会有冲突，如果奇偶性不同，就说明有一组冲突，减去1。

题解

#include <bits/stdc++.h>
typedef long long  ll;
using namespace std;
void solve()
{
    int n, x;
    cin >> n;
    set<int> a;
    for(int i = 0; i < n; i++)
    {
        cin >> x;
        a.insert(x);
    }
    if((n-a.size())%2 == 0)
    {
        cout << a.size() << endl;
    }
    else
    {
        cout << a.size()-1 << endl;
    }
}

int32_t main(){
    int t = 1;
    cin >> t;
    while (t--) {
        solve();
    }
}

C 象棋找象（主教）

C:Where's the Bishop?

题目描述

考察广度优先搜索

给定一个棋盘和象的轨迹，找交叉点（也就是象所在的位置）

题目思路

宽搜找匹配模式

题解

#include <iostream>
#include <vector>
#include <queue>
#include <cstring>
using namespace std;
char map[8][8];
int dis[8][8];
int t;
int dx[] = {1,1,-1,-1};
int dy[] = {-1,1,-1,1};
struct p{int x;int y;};
bool judge(struct p t){
    struct p f[4];
    int d = 4;
    for(int i = 0;i < 4;i++)
        if(map[t.x + dx[i]][ t.y + dy[i]] == '#') --d;
    if(d == 0) return true;
    else return false;
}
void dfs()
{
    queue<struct p> q;
    for(int i = 0;i < 8;i++)
        for(int j = 0;j < 8;j++)
            if(map[i][j] == '#')
            {
                q.push({i,j});
                dis[i][j] = 1;
            }

    while(q.size())
    {
        auto head = q.front();
        q.pop();

        if(judge(head) == true) {
            printf("%d %d\n",head.x + 1,head.y + 1);
            return;
        }
        for(int i = 0;i < 4;i++)
        {
            int x = head.x + dx[i];
            int y = head.y + dy[i];
            if(x>=0 && x < 8 && y >= 0 && y < 8 && dis[x][y] == 0 && map[x][y] == '#')
            {
                dis[x][y] == 1;
                q.push({x,y});
            }
        }

    }

}
int main()
{
    cin >> t;
    while(t--)
    {
        for(int i = 0;i < 8;i++)
            for(int j = 0;j < 8;j++)
                cin >> map[i][j];
        dfs();
        memset(map,0,sizeof(map));
    }
}

D 回文钟表

D:The Clock

题目描述

考察模运算

给定一个时间区间，再该区间中找到回文时间

解题思路

一天1440分钟，符合条件的没几个，转换成数列然后直接匹配查找

题解

#include <bits/stdc++.h>
using namespace std;
int a[5] = {600, 60, 0, 10, 1};
int good[16] = {0, 70, 140, 210, 280, 350, 601, 671, 741, 811, 881, 951, 1202, 1272, 1342, 1412};
void solve() {
    string s;
    cin >> s;
    int x;
    cin >> x;
    int tot = 0;
    for (int i = 0; i < 5; i++) {
        tot += (int)(s[i] - '0') * a[i];
    }
    set<int> t;
    for (int i = 0; i < 2022; i++) {
        t.insert(tot);
        tot += x;
        tot %= 1440;
    }
    int res = 0;
    for (int i : t) {
        for (int j = 0; j < 16; j++) {
            if (good[j] == i) {res++;}
        }
    }
    cout << res << '\n';
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int tt; cin >> tt; for (int i = 1; i <= tt; i++) {solve();}
    // solve();
}

E 二进制队列

E. Binary Deque

题目描述

考察前缀和

给定一个二进制队列，通过多少次队列操作让队列里面的数目达到给定目标

解题思路

求前缀和，然后再数组中单调保存最小值，然后二分找到目标值

题解

#include "bits/stdc++.h"
using namespace std;
 
#define ll long long
 
#define       forn(i,n)              for(int i=0;i<n;i++)
#define          all(v)              v.begin(), v.end()
#define         rall(v)              v.rbegin(),v.rend()
 
#define            pb                push_back
#define          sz(a)               (int)a.size()
ll query(int l, int r, vector<ll>& p) {
    return p[r] - (l ? p[l - 1] : 0);
}

void solve() {  
    int n, s; cin >> n >> s;
    vector<ll> a(n), p(n);
    forn(i, n) {
        cin >> a[i];
        p[i] = a[i];
        if(i) p[i] += p[i - 1];
    }
    int ans = INT_MAX;
    for(int i = 0; i < n; ++i) {
        int l = i, r = n - 1, pos = -1;
        while(l <= r) {
            int mid = l + r >> 1;
            if(query(i, mid, p) <= s) {
                pos = mid;
                l = mid + 1;
            } else r = mid - 1;
        }
        if(pos == -1 || query(i, pos, p) != s) continue;
        ans = min(ans, n - (pos - i + 1));
    }

    cout << (ans == INT_MAX ? -1 : ans) << "\n";
} 
     
int32_t main() {
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    int t = 1;
    cin >> t;
    while(t--) {
        solve();
    }
}

F 三数相加

F. 3SUM

题目描述

考察优化

给定一个数列，找出数列中三个数相加个位是3的三个数。

解题思路

判断个位可以把其它位抛弃，多次出现重复数字可只取三个，0-9每个数字最多出现三次，因此再长的数列都可以用三十个以内的数组表示，此时再暴查

题解

#include <bits/stdc++.h>
using namespace std;
void solve() {
    int n;
    cin >> n;
    int cnt[10] = {};
    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;
        cnt[x % 10]++;
    }
    vector<int> v;
    for (int i = 0; i < 10; i++) {
        for (int j = 0; j < min(cnt[i], 3); j++) {
            v.push_back(i);
        }    
    }
    int m = v.size();
    for (int i = 0; i < m; i++) {
        for (int j = i + 1; j < m; j++) {
            for (int k = j + 1; k < m; k++) {
                if ((v[i] + v[j] + v[k]) % 10 == 3) {cout << "YES\n"; return;}
            }
        }
    }
    cout << "NO\n";
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int tt; cin >> tt; for (int i = 1; i <= tt; i++) {solve();}
    // solve();
}

G 指数权重

G. 2^Sort

题目描述

考察对数运算和序列化、前缀和、滑动窗口或者DP

在给定的数组中，找出加权之后还满足升序要求的字串个数

解题思路

对于任意合法排序：

math

上式都满足，这样就可以将指数问题转为差分问题，按先后来对比对结果进行序列化，转为顺序对和顺序错两个状态，然后再用状态数组的操作求得不同情况的最长子序列

题解

#include <bits/stdc++.h>

using namespace std;

const int MAX = 200007;
const int MOD = 1000000007;

void solve() {
    int n, k;
    cin >> n >> k;
    int a[n];
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    int ok[n];
    for (int i = 0; i < n - 1; i++) {
        ok[i] = (a[i] < 2 * a[i + 1]);
    }
    int tot = 0;
    for (int i = 0; i < k; i++) {
        tot += ok[i];
    }
    int res = 0;
    if (tot == k) {res++;}
    for (int i = k; i < n - 1; i++) {
        tot += ok[i];
        tot -= ok[i - k];
        if (tot == k) {res++;}
    }
    cout << res << '\n';
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int tt; cin >> tt; for (int i = 1; i <= tt; i++) {solve();}
    // solve();
}

H

H. Gambling

题目简介

考察线段数

给定数组，通过设定数组边界和初值的方法，来确定带有单调权重的数组的最大和值

解题思路

由于题目特殊的减半和增倍，可以将猜中和猜不中转为指数运算，然后只在指数上做运算

题解

#include "bits/stdc++.h"
using namespace std;
 
#define ll long long
 
#define       forn(i,n)              for(int i=0;i<n;i++)
#define          all(v)              v.begin(), v.end()
#define         rall(v)              v.rbegin(),v.rend()
 
#define            pb                push_back
#define          sz(a)               (int)a.size()
 
struct DynamicMaxSubarraySum {
    struct node {
        ll pref, suf, val, sum;
    };  
    int N;
    ll neutral;
    vector<node> t;
    DynamicMaxSubarraySum(int _N, ll assign_value) {
        neutral = assign_value;
        N = _N;
        t.resize(4 * N);
        forn(i, 4 * N) t[i] = {0, 0, 0, 0};
        build(1, 0, N - 1); 
    }
    void build(int i, int l, int r) {
        if(l == r) {
            t[i].pref = t[i].suf = t[i].val = t[i].sum = neutral;
            return;
        }
        int mid = (l + r) >> 1;
        build(2 * i, l, mid);
        build(2 * i + 1, mid + 1, r);
        t[i] = merge(t[2 * i], t[2 * i + 1]);
    }
    node merge(node a, node b) {
        node c;
        c.pref = max(a.pref, a.sum + b.pref);
        c.suf = max(b.suf, b.sum + a.suf);
        c.val = max({a.val, b.val, a.suf + b.pref});
        c.sum = a.sum + b.sum;
        return c;
    }
 
    void modif(int i, int l, int r, int pos, ll val) {
        if(l > pos || r < pos) return;
        if(l == pos && r == pos) {
            t[i].pref = t[i].suf = t[i].val = t[i].sum = val;
            return;
        }
        int mid = (l + r) >> 1;
        modif(2 * i, l, mid, pos, val);
        modif(2 * i + 1, mid + 1, r, pos, val);
        t[i] = merge(t[2 * i], t[2 * i + 1]);
    }
    node query(int i, int l, int r, int tl, int tr) {
        if(l > tr || r < tl) return {0, 0, 0, 0};
        if(l >= tl && r <= tr) return t[i];
        int mid = (l + r) >> 1;
        return merge(query(2 * i, l, mid, tl, tr), query(2 * i + 1, mid + 1, r, tl, tr));
    }
 
    void modif(int pos, int val) {
        modif(1, 0, N - 1, pos, val);
    }
    node query(int l, int r) {
        return query(1, 0, N - 1, l, r);
    }
    node query(int pos) {
        return query(1, 0, N - 1, pos, pos);
    }
};
 
void solve() {  
    int n; cin >> n;
    vector<int> a(n);
    forn(i, n) cin >> a[i];
    map<int, vector<int>> vv;
    forn(i, n) {
        vv[a[i]].pb(i);
    }
    DynamicMaxSubarraySum st(n, -1);
 
    ll mx = 0, ans = -1;
    for(auto i: vv) {
        vector<int> v = i.second;
        for(auto x: v) st.modif(x, 1);
        if(mx < st.query(0, n - 1).val) {
            ans = i.first;
            mx = st.query(0, n - 1).val;
        }
        for(auto x: v) st.modif(x, -1);
    }  
    int ansl = -1, ansr = -1;
    for(int i = 0; i < n; ++i) {
        if(a[i] == ans) a[i] = 1;
        else a[i] = -1;
    }
    ll sum = 0, lastl = 0;
    mx = 0;
    for(int i = 0; i < n; ++i) {
        sum += a[i];
        if(sum > mx) {
            mx = sum;
            ansr = i;
            ansl = lastl;
        }
        if(sum <= 0) {
            lastl = i + 1;
            sum = 0;
        }
    }
 
    cout << ans << " " << ansl + 1 << " " << ansr + 1 << "\n"; 
}   
     
int32_t main() {
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    int t = 1;
    cin >> t;
    while(t--) {
        solve();
    }
}
137 views
Comments
登录后评论
Sign In
·

忘记加标签了，要怎么重新编辑

·

因为黑客说定位是话题型网站，社交交流功能，鼓励的内容偏向短内容，是 immutable 的。

·

建议开代码高亮