IT数码 购物 网址 头条 软件 日历 阅读 图书馆
TxT小说阅读器
↓语音阅读,小说下载,古典文学↓
图片批量下载器
↓批量下载图片,美女图库↓
图片自动播放器
↓图片自动播放器↓
一键清除垃圾
↓轻轻一点,清除系统垃圾↓
开发: C++知识库 Java知识库 JavaScript Python PHP知识库 人工智能 区块链 大数据 移动开发 嵌入式 开发工具 数据结构与算法 开发测试 游戏开发 网络协议 系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑 笔记本 显卡 显示器 固态硬盘 硬盘 耳机 手机 iphone vivo oppo 小米 华为 单反 装机 图拉丁
 
   -> 数据结构与算法 -> 「团队训练赛」ShanDong Multi-University Training #3 -> 正文阅读

[数据结构与算法]「团队训练赛」ShanDong Multi-University Training #3

A - Ant colony

题目描述:

给你n个数a[i],m次询问,每次询问给出一个l, r,问[l, r]中有多少个数a[i]不满足:a[i]可以被该区间所有数整除

思路:

分析一下就可以发现,如果区间内一个数可以被其他所有数整除,那这个数必须等于区间所有数求gcd后的结果

所以我们需要一个数据结构可以维护区间gcd,以及可以维护出区间gcd的数量

这里给出两种方法:

  • st表 + 二分,用st表维护区间gcd,查询数量的时候,我们可以用一个vector数组来存每个数出现位置,用二分来查就行,但是因为数字是1e9,不能用vector数组,所以可以用map<int, vector>或者是写个离散化再用vector数组存
  • 线段树维护区间gcd的值和区间gcd数量,就是一个简单的不带修改的普通线段树
#include <bits/stdc++.h>
using namespace std;

#define endl '\n'
#define inf 0x3f3f3f3f
#define mod 998244353
#define m_p(a,b) make_pair(a, b)
#define mem(a,b) memset((a),(b),sizeof(a))
#define io ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)

typedef long long ll;
typedef pair <int,int> pii;

#define MAX 300000 + 50
int n, m, k, op;
int l, r;
int tr[MAX];
int lg[MAX];
int gg[MAX][30];
map<int, vector<int>>mp;

int gcd(int a, int b){
    if(b) return gcd(b, a % b);
    else return a;
}

void init(){
    for(int i = 1; i <= n; ++i)gg[i][0] = tr[i];
    for(int i = 2; i <= n; ++i){
        lg[i] = lg[i / 2] + 1;
    }
    for(int j = 1; j <= lg[n]; ++j){
        for(int i = 1; i + (1 << j) - 1 <= n; ++i){
            gg[i][j] = gcd(gg[i][j - 1], gg[i + (1 << (j - 1))][j - 1]);
        }
    }
}

int getgcd(int l, int r){
    int len = lg[r - l + 1];
    return gcd(gg[l][len], gg[r - (1 << len) + 1][len]);
}

void work(){
    cin >> n;
    for(int i = 1; i <= n; ++i){
        cin >> tr[i];
        mp[tr[i]].push_back(i);
    }
    init();
    cin >> m;
    while(m--){
        cin >> l >> r;
        int x = getgcd(l, r);
        cout << r - l + 1 - (upper_bound(mp[x].begin(), mp[x].end(), r) - lower_bound(mp[x].begin(), mp[x].end(), l))<<endl;
    }
}


int main(){
    io;
    work();
    return 0;
}

#include <bits/stdc++.h>
using namespace std;

#define endl '\n'
#define inf 0x3f3f3f3f
#define mod 998244353
#define m_p(a,b) make_pair(a, b)
#define mem(a,b) memset((a),(b),sizeof(a))
#define io ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define ls (p<<1)
#define rs ((p<<1)|1)
typedef long long ll;
typedef pair <bool,int> pii;

#define MAX 500000 + 50
int n, m, k, op;
int tr[MAX];
int num[MAX];
int gg[MAX];

int gcd(int a, int b){
    if(b) return gcd(b, a % b);
    else return a;
}
struct ran{
    int gg, num;
};
void pushup(int p){
    gg[p] = gcd(gg[ls], gg[rs]);
    num[p] = (gg[ls] == gg[p] ? num[ls] : 0) + (gg[rs] == gg[p] ? num[rs] : 0);
}

void built(int p, int l, int r){
    if(l == r){
        gg[p] = tr[l];
        num[p] = 1;
        return;
    }
    int mid = (l + r) / 2;
    built(ls, l, mid);
    built(rs, mid + 1, r);
    pushup(p);
}

ran getans(int p, int l, int r, int s, int t){
    if(s <= l && r <= t){
        return {gg[p], num[p]};
    }
    ran ans = {0, 0};
    int mid = (l + r) / 2;
    if(mid >= s){
        ans = getans(ls, l, mid, s, t);
    }
    if(mid < t){
        ran a = ans;
        ran now = getans(rs, mid + 1, r, s, t);
        ans.gg = gcd(ans.gg, now.gg);
        ans.num = (a.gg == ans.gg ? a.num : 0) + (now.gg == ans.gg ? now.num : 0);
    }
    return ans;
}

void work(){
    cin >> n;
    for(int i = 1; i <= n; ++i)cin >> tr[i];
    built(1, 1, n);
    cin >> m;
    int l, r;
    while(m--){
        cin >> l >> r;
        ran ans = getans(1, 1, n, l, r);
        cout << r - l + 1 - ans.num << endl;
    }
}


int main(){
    io;
    work();
    return 0;
}

B - New String

题目描述:

重新给你26字母的先后顺序,按照这个顺序重新定义字典序,给你n个字符串,输出第k小的字符串

思路:

根据给出的26个字母用map映射一下,然后写一个字符串的比较函数sort一下再输出就行

#include <bits/stdc++.h>
using namespace std;

#define endl '\n'
#define inf 0x3f3f3f3f
#define mod 998244353
#define m_p(a,b) make_pair(a, b)
#define mem(a,b) memset((a),(b),sizeof(a))
#define io ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define ls (p<<1)
#define rs ((p<<1)|1)
typedef long long ll;
typedef pair <bool,int> pii;

#define MAX 300000 + 50
int n, m, k, op;
string s;
map<char, int>mp;
struct ran{
    string s;
    bool operator < (const ran &x)const{
        for(int i = 0; i < s.size() && i < x.s.size(); ++i){
            if(mp[s[i]] < mp[x.s[i]])return true;
            else if(mp[s[i]] > mp[x.s[i]])return false;
            else continue;
        }
        return s.size() < x.s.size();
    }
}tr[MAX];

void work(){
    cin >> s;
    for(int i = 0; i < s.size(); ++i){
        mp[s[i]] = i + 1;
    }
    cin >> n;
    for(int i = 1; i <= n; ++i){
        cin >> tr[i].s;
    }
    sort(tr + 1, tr + 1 + n);
    cin >> k;
    cout << tr[k].s << endl;
}


int main(){
    io;
    work();
    return 0;
}

C - Easy Problem

题目描述:

给你n * m的图,*是障碍物,.是空地

现在有两个人分别在ab的位置,二人移动的方向是一样的,都会同时向上、下、左、右四个方向移动,如果向某个方向移动的时候,遇到了障碍物或者遇到了边界,则这个人会原地不动,但是另一个人会正常行走,当然如果同一方向都遇到障碍物那就都不能朝那个东西移动,问二者什么时候可以相遇

思路:

观察一下可以发现n才50,满打满算跑满整个地图也才504的情况,很小,直接跑bfs就行

#include <bits/stdc++.h>
using namespace std;

#define endl '\n'
#define inf 0x3f3f3f3f
#define mod7 1000000007
#define mod9 998244353
#define m_p(a,b) make_pair(a, b)
#define mem(a,b) memset((a),(b),sizeof(a))
#define io ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define debug(a) cout << "Debuging...|" << #a << ": " << a << "\n";
typedef long long ll;
typedef pair <int,int> pii;
#define y1 y114514
#define MAX 300000 + 50
int n, m, k, x;

char tr[55][55];
bool vis[55][55][55][55];
int dx[] = {1, 0, -1, 0};
int dy[] = {0, 1, 0, -1};
int x1, y1, x2, y2;

struct ran{
    int x1, y1, x2, y2, d;
};

bool judge(int x, int y){
    if(x < 1 || x > n || y < 1 || y > n)return false;
    if(tr[x][y] == '*')return false;
    else return true;
}
void bfs(){
    queue<ran>q;
    ran now, nex;
    q.push({x1, y1, x2, y2, 0});
    vis[x1][y1][x2][y2] = 1;
    while(!q.empty()){
        now = q.front();q.pop();
        if(now.x1 == now.x2 && now.y114514 == now.y2){
            cout << now.d << endl;
            return;
        }
        for(int i = 0; i < 4; ++i){
            if(judge(now.x1 + dx[i], now.y114514 + dy[i])){
                nex.x1 = now.x1 + dx[i];
                nex.y114514 = now.y114514 + dy[i];
            }
            else {
                nex.x1 = now.x1;
                nex.y114514 = now.y114514;
            }
            if(judge(now.x2 + dx[i], now.y2 + dy[i])){
                nex.x2 = now.x2 + dx[i];
                nex.y2 = now.y2 + dy[i];
            }
            else{
                nex.x2 = now.x2;
                nex.y2 = now.y2;
            }
            if(vis[nex.x1][nex.y114514][nex.x2][nex.y2])continue;
            nex.d = now.d + 1;
            q.push(nex);

            vis[nex.x1][nex.y114514][nex.x2][nex.y2] = 1;
        }
    }
    cout << "no solution\n";
}

void work(){
    cin >> n;
    for(int i = 1; i <= n; ++i){
        for(int j = 1; j <= n; ++j){
            cin >> tr[i][j];
            if(tr[i][j] == 'a'){
                tr[i][j] = '.';
                x1 = i;y1 = j;
            }
            else if(tr[i][j] == 'b'){
                tr[i][j] = '.';
                x2 = i;y2 = j;
            }
        }
    }
    bfs();
}


int main(){
    io;
    work();
    return 0;
}

D - Maximum Value

题目描述:

给你n个数,选i, j,且满足a[j] >= a[i],问a[j] % a[i]的最大值

思路:

我们可以先对数组进行排序,排序以后,对于一个数字a[i],我们需要去找一个a[j],求a[j]%a[i]的最大值,a[j] = k * a[i] + x,x即余数,我们可以通过枚举k,然后二分找到数组中第一个大于等于k*a[i]的位置p,则p-1位置应该是(k-1)*a[i] 到 k * a[i]a[i]个数中余数最大的那个,对所有的k,我们都计算出余数求一个最大值,这就是对应的a[i]作为除数时能产生的余数,我们对每个i都这样求一遍就可以,复杂度应该是调和级数的,O(nlogn)

注意剪枝,即相同数字找一次就行

#include <bits/stdc++.h>
using namespace std;

#define endl '\n'
#define inf 0x3f3f3f3f
#define mod 998244353
#define m_p(a,b) make_pair(a, b)
#define mem(a,b) memset((a),(b),sizeof(a))
#define io ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)

typedef long long ll;
typedef pair <int,int> pii;

#define MAX 300000 + 50
int n, m, k, op;
int tr[MAX];

void work(){
    cin >> n;
    for(int i = 1; i <= n; ++i){
        cin >> tr[i];
    }
    sort(tr + 1, tr + 1 + n);
    int ans = 0;
    for(int i = 1; i <= n; ++i){
        int x = tr[i];
        if(tr[i] == tr[i - 1])continue;
        if(x == 1)continue;
        while(x - tr[i] <= tr[n]){
            int p = (int)(lower_bound(tr + i + 1, tr + 1 + n, x) - tr);
            ans = max(ans, tr[p - 1] % tr[i]);
            x += tr[i];
        }
    }
    cout << ans << endl;
}


int main(){
    io;
    work();
    return 0;
}

E - Prefix Equality

题目描述:

给你两个数组ar[i], br[i],Q次询问,每次询问都给出a, b,问ar[1]到ar[a]的数组成的集合与br[1]到br[b]的数组成的集合是否相同

思路:

哈希一下就行,我搞了三种数组,一个数量数组,一个前缀和的数组,一个前缀积的数组,判断的时候三个都相同就相同

#include <bits/stdc++.h>
using namespace std;

#define endl '\n'
#define inf 0x3f3f3f3f
#define mod7 1000000007
#define mod9 998244353
#define m_p(a,b) make_pair(a, b)
#define mem(a,b) memset((a),(b),sizeof(a))
#define io ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define debug(a) cout << "Debuging...|" << #a << ": " << a << "\n";
typedef long long ll;
typedef pair <int,int> pii;

#define MAX 300000 + 50
int n, m, k, x, y;
ll ar[MAX], br[MAX];
ll sum1[MAX], sum2[MAX];
ll mul1[MAX], mul2[MAX];
ll num1[MAX], num2[MAX];

void work(){
    cin >> n;
    mul1[0] = mul2[0] = 1;
    for(int i = 1; i <= n; ++i)cin >> ar[i];
    for(int i = 1; i <= n; ++i)cin >> br[i];
    set<ll>se;
    for(int i = 1; i <= n; ++i){
        sum1[i] = sum1[i - 1];
        mul1[i] = mul1[i - 1];
        num1[i] = num1[i - 1];
        if(!se.count(ar[i])){
            ++num1[i];
            se.insert(ar[i]);
            sum1[i] += ar[i];
            (mul1[i] *= ar[i]) %= mod7;
        }
    }
    se.clear();
    for(int i = 1; i <= n; ++i){
        sum2[i] = sum2[i - 1];
        mul2[i] = mul2[i - 1];
        num2[i] = num2[i - 1];
        if(!se.count(br[i])){
            ++num2[i];
            se.insert(br[i]);
            sum2[i] += br[i];
            (mul2[i] *= br[i]) %= mod7;
        }
    }
    cin >> m;
    while (m--) {
        cin >> x >> y;
        if(num1[x] == num2[y] && sum1[x] == sum2[y] &&
           mul1[x] == mul2[y])cout << "Yes\n";
        else cout << "No\n";
    }
}


int main(){
    io;
    work();
    return 0;
}

G - Optimal Biking Strategy

题目描述:

你现在在0的位置,需要到达p米的位置

n个自行车站,你只能在自行车的车站站上下车,每花一块钱最多能骑s米,一米都不可以多骑,如果当前的车不能支持从该站点骑到下一个站点,则他不会骑的

问最少需要在地上走多少米

思路:

动态规划

dp[i][j]表示到i米的位置时,花了j元能骑行的最远距离

状态转移也很好想,就是枚举一下最后一次花k元到达的j

我们假设花了k元,则我们需要知道从什么位置花了k元能走尽可能远的距离到达了j,将这个位置记做id,则dp[i][j] = max(dp[i][j - k] + tr[j] - tr[id];

而求id的方法是二分

注意别忘了加上dp[i][j] = min(dp[i][j], dp[i - 1][j])

#include <bits/stdc++.h>
using namespace std;

#define endl '\n'
#define inf 0x3f3f3f3f
#define mod7 1000000007
#define mod9 998244353
#define m_p(a,b) make_pair(a, b)
#define mem(a,b) memset((a),(b),sizeof(a))
#define io ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define debug(a) cout << "Debuging...|" << #a << ": " << a << "\n";
typedef long long ll;
typedef pair <int,int> pii;

#define MAX 300000 + 50
ll n, kk;
ll p, s;
ll tr[MAX];
ll id[MAX][7];
ll dp[MAX][7];
void work(){
    scanf("%lld%lld%lld", &n, &p, &s);
    for(int i = 1; i <= n; ++i){
        scanf("%lld", &tr[i]);
    }
    scanf("%lld", &kk);
    for(int i = 1; i <= n; ++i){
        id[i][0] = i;
        for(int j = 1; j <= kk; ++j){
            ll pos = tr[i] - j * s;
            id[i][j] = lower_bound(tr + 1, tr + 1 + n, pos) - tr;
        }
    }
    ll ans = 1e18;
    for(int i = 1; i <= n; ++i){
        dp[i][0] = 0;
        for(int j = 1; j <= kk; ++j){
            dp[i][j] = dp[i - 1][j];
            for(int k = 0; k <= j; ++k){
                dp[i][j] = max(dp[i][j], dp[id[i][k]][j - k] + tr[i] - tr[id[i][k]]);
            }
        }
    }
    for(int i = 1; i <= n; ++i){
        ans = min(ans, p - dp[i][kk]);
    }
    cout << ans << endl;
}

int main(){
    io;
    work();
    return 0;
}

I - 250-like Number

题目描述:

k = p * q * q * qp,q都是素数,问小于等于n中有多少个k

思路:

先用欧拉筛筛出1e6内的素数,再枚举每个p,通过二分去计算q的数量

需要注意的是判断p*q*q*q <= n时会爆long long,所以我们可以移项,即判断q*q*q <= n / p

#include <bits/stdc++.h>
using namespace std;

#define endl '\n'
#define inf 0x3f3f3f3f
#define mod 998244353
#define m_p(a,b) make_pair(a, b)
#define mem(a,b) memset((a),(b),sizeof(a))
#define io ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)

typedef long long ll;
typedef pair <int,int> pii;

#define MAX 300000 + 50
ll n, m, k, op;

int tot;
ll prim[MAX];
bool vis[1000050];
void init(){
    for(int i = 2; i <= 1000000; ++i){
        if(!vis[i])prim[++tot] = i;
        for(int j = 1; j <= tot && prim[j] * i <= 1000000; ++j){
            vis[prim[j] * i] = 1;
            if(i % prim[j] == 0)break;
        }
    }
}

void work(){
    init();
    cin >> n;
    int ans = 0;
    for(int i = 1; i <= tot && (ll)pow(prim[i], 4) <= n; ++i){
        int l = i + 1, r = tot;
        while(l <= r){
            int mid = (l + r) / 2;
            if(prim[mid] * prim[mid] * prim[mid] > n / prim[i])r = mid - 1;
            else l = mid + 1;
        }
        ans += l - i - 1;
    }
    cout << ans << endl;
}


int main(){
    io;
    work();
    return 0;
}

J - Wrapping Chocolate

题目描述:

n个巧克力,m个盒子,这里的巧克力和盒子都只有长和宽,问能不能把n个巧克力放在不同的盒子里面

思路:

我们将n+m个巧克力和盒子放在一起,按照宽从大到小,长从大到小进行排序,然后用一个multiset来维护盒子中没有被用过的宽大于等于当前巧克力的所有的长,遇到巧克力的时候,就去multiset中二分查找他的长,如果找到了就删掉,找不到就输出No,如果遇到了盒子,则把长赛到multiset中

#include <bits/stdc++.h>
using namespace std;

#define endl '\n'
#define inf 0x3f3f3f3f
#define mod 998244353
#define sd(n) scanf("%d",&n)
#define sdd(n,m) scanf("%d %d",&n,&m)
#define m_p(a,b) make_pair(a, b)
#define mem(a,b) memset((a),(b),sizeof(a))
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define io ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)

typedef long long ll;
typedef pair <int,int> pii;

#define MAX 500000 + 50
int n, m, k, op;
struct ran{
    int x, y;
    bool op;
    bool operator < (const ran &a)const{
        if(x != a.x)return x > a.x;
        else if(y != a.y)return y > a.y;
        else return op > a.op;
    }
}tr[MAX];

void work(){
    cin >> n >> m;
    for(int i = 1; i <= n; ++i){
        cin >> tr[i].x;
    }
    for(int i = 1; i <= n; ++i){
        cin >> tr[i].y;
    }
    for(int i = n + 1; i <= n + m; ++i){
        cin >> tr[i].x;
    }
    for(int i = n + 1; i <= n + m; ++i){
        cin >> tr[i].y;
        tr[i].op = 1;
    }
    sort(tr + 1, tr + 1 + n + m);
    multiset<int>se;
    for(int i = 1; i <= n + m; ++i){
        if(tr[i].op == 0){
            auto x = se.lower_bound(tr[i].y);
            if(x == se.end()){
                cout << "No\n";
                return;
            }
            se.erase(x);
        }
        else{
            se.insert(tr[i].y);
        }
    }
    cout << "Yes\n";
}


int main(){
    io;
    work();
    return 0;
}


K - Endless Walk

题目描述:

给你n个点,m条边,问存在多少个点满足以该点为起点可以走到一个环中

思路:

反向建图跑拓扑排序,输出没被塞到队列里面的点的数量即可

#include <bits/stdc++.h>
using namespace std;

#define endl '\n'
#define inf 0x3f3f3f3f
#define mod 998244353
#define sd(n) scanf("%d",&n)
#define sdd(n,m) scanf("%d %d",&n,&m)
#define m_p(a,b) make_pair(a, b)
#define mem(a,b) memset((a),(b),sizeof(a))
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define io ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)

typedef long long ll;
typedef pair <int,int> pii;

#define MAX 300000 + 50
int n, m, k, op;
int in[MAX];
int x, y;
vector<int>G[MAX];
bool vis[MAX];
void work(){
    cin >> n >> m;
    for(int i = 1; i <= m; ++i){
        cin >> x >> y;
        G[y].push_back(x);
        ++in[x];
    }
    queue<int>q;
    int ans = 0;
    for(int i = 1; i <= n; ++i){
        if(in[i] == 0){
            q.push(i);
            ++ans;
        }
    }
    while(!q.empty()){
        int u = q.front();q.pop();
        for(auto v : G[u]){
            --in[v];
            if(in[v] == 0){
                q.push(v);
                ++ans;
            }
        }
    }
    cout << n - ans << endl;
}

int main(){
    io;
    work();
    return 0;
}


L - Powerful array

题目描述:

给出n个数,m次询问,每次询问都给出l, r,假设区间内有k种数,值为a[k],且每种数出现num[k]次,则区间的价值为 ∑ i = 1 k n u m [ k ] ? n u m [ k ] ? a [ k ] \sum_{i=1}^{k}{num[k]*num[k] * a[k]} i=1k?num[k]?num[k]?a[k]

求每次查询的区间价值

思路:

莫队板子

简单推一下式子就行

#include <bits/stdc++.h>
using namespace std;

#define endl '\n'
#define inf 0x3f3f3f3f
#define mod 998244353
#define m_p(a,b) make_pair(a, b)
#define mem(a,b) memset((a),(b),sizeof(a))
#define io ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)

typedef long long ll;
typedef pair <int,int> pii;

#define MAX 300000 + 50
int n, m, k, op;
int block;
ll ar[MAX];

int get_block(int x){
    return x / block;
}

struct ran{
    int l, r, id;
    bool operator < (const ran &a)const{
        int x = get_block(l);
        int y = get_block(a.l);
        if(x != y)return x < y;
        else return r < a.r;
    }
}tr[MAX];

ll ans[MAX];
ll num[1000005];
ll cnt;

void add(int id){
    cnt += ar[id] * (2 * num[ar[id]] + 1);
    ++num[ar[id]];
}
void del(int id){
    cnt += ar[id] * (1 - 2 * num[ar[id]]);
    --num[ar[id]];
}

void work(){
    cin >> n >> m;
    block = sqrt(n);
    for(int i = 1; i <= n; ++i)cin >> ar[i];
    for(int i = 1; i <= m; ++i){
        cin >> tr[i].l >> tr[i].r;
        tr[i].id = i;
    }
    sort(tr + 1, tr + 1 + m);
    int l = 1, r = 0;
    for(int i = 1; i <= m; ++i){
        int s = tr[i].l, t = tr[i].r;
        while(r < t)add(++r);
        while(r > t)del(r--);
        while(l < s)del(l++);
        while(l > s)add(--l);
        ans[tr[i].id] = cnt;
    }
    for(int i = 1; i <= m; ++i){
        cout << ans[i] << endl;
    }
}


int main(){
    io;
    work();
    return 0;
}


总结

这次比赛有4个abc的题,其中有俩签到题我都做过,就直接写了交了,剩下俩都见过,但是当时没写,正好趁这次比赛补一下

中间写G题的dp的时候写了半天都是wa,换了个姿势就过了,下午对拍研究了一下,发现按照自己的dp的定义来说,应该写一句dp[i][j] = dp[i - 1][j] ,但是比赛的时候没写,所以开始一直wa,后来换个姿势以后就过了

K题确实没想到这么简单,我还在想怎么dfs能少花点时间更新,yj说反向建图跑个拓扑排序就行,一点就通我只能说是

L题赛时看了一眼,知道是个莫队,但是因为我不怎么写数据结构题,没怎么写过莫队,开始就没写,后来9个题的时候就直接下班了,就忘了这个题,刚刚补了一下发现就是sb题

J题巧克力的题确实很妙很妙,虽然我看一眼就知道是排个序然后二分去找找,但是不知道该怎么写,在我和djk写C的时候yj写了一下就过了

C题看的第一眼就想暴力跑bfs,但是刚开始没细想,最后才发现是sb题

A题djk说可以写线段树,但是当时我一看维护区间gcd,直接上st表了,难得遇到一个可以用st表的题,不能浪费了

  数据结构与算法 最新文章
【力扣106】 从中序与后续遍历序列构造二叉
leetcode 322 零钱兑换
哈希的应用:海量数据处理
动态规划|最短Hamilton路径
华为机试_HJ41 称砝码【中等】【menset】【
【C与数据结构】——寒假提高每日练习Day1
基础算法——堆排序
2023王道数据结构线性表--单链表课后习题部
LeetCode 之 反转链表的一部分
【题解】lintcode必刷50题<有效的括号序列
上一篇文章      下一篇文章      查看所有文章
加:2022-06-29 19:19:22  更:2022-06-29 19:22:59 
 
开发: C++知识库 Java知识库 JavaScript Python PHP知识库 人工智能 区块链 大数据 移动开发 嵌入式 开发工具 数据结构与算法 开发测试 游戏开发 网络协议 系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑 笔记本 显卡 显示器 固态硬盘 硬盘 耳机 手机 iphone vivo oppo 小米 华为 单反 装机 图拉丁

360图书馆 购物 三丰科技 阅读网 日历 万年历 2024年3日历 -2024/3/29 22:07:46-

图片自动播放器
↓图片自动播放器↓
TxT小说阅读器
↓语音阅读,小说下载,古典文学↓
一键清除垃圾
↓轻轻一点,清除系统垃圾↓
图片批量下载器
↓批量下载图片,美女图库↓
  网站联系: qq:121756557 email:121756557@qq.com  IT数码