CSP-J 2021 入门简单题解

[CSP-J 2021] 分糖果

题意就不说的
我的做法是二分。
我们要找最大,那么就找n-1

a = kn-1
如果存在k 使得a >= L 且 a <= R
那么大答案就是n-1
如果不存在这样的k,那么只能R\%n
洛谷自测100分,时间复杂度O(30)

#include <iostream>
#include <cstdio>
#include <ctime>
#include <stack>
#include <queue>
#include <map>
#include <cstring>
#include <cstdlib>
#include <set>
#include <string>
#include <vector>
#include <algorithm>
#include <bitset>
#define endl '\n'
#define int long long
#define INF 2147483647
#define MOD 19260817
using namespace std;
int Max(int a,int b){return a>b?a:b;}
int Min(int a,int b){return a<b?a:b;}
int QPow(int a,int b){int res=1;while(b){if(b&1){res=(res*a)%MOD;}b>>=1;a=(a*a)%MOD;}return res%MOD;}
int Inv(int a,int Mod){return QPow(a,Mod-2);}
const int MAXR = 1e9+10;
int n,l,r;
signed main(void){
    cin >> n >> l >> r;
    int ll = 1;
    int rr = MAXR;
    int temp = n;
    while(ll < rr){
        int mid = (ll+rr)>>1;
        temp = n*mid-1;
        if(temp > r){
            rr = mid;
        }else if(temp >= l && temp <= r){
            cout << n-1;
            return 0;
        }else{
            ll = mid+1;
        }
    }
    cout << r%n;
    return 0;
    //  ios::sync_with_stdio(false);
    // cin.tie(0);
    // cout.tie(0);

}

[CSP-J 2021] 插入排序

O(N^2)可过,所以比较简单,注意的是排序的时候不仅要比对元素本身的大小关系,还要比对元素位置大小关系,也就是说,在元素大小相同的情况下,位置靠前的排在前面。
离散化一下记录每个元素的排序后的地点。
由于进行一次 1 操作,只改变了一个元素的有序性,所以直接向左向右扫一遍看看插在哪儿就完事了。
自测100分

#include <iostream>
#include <cstdio>
#include <ctime>
#include <stack>
#include <queue>
#include <map>
#include <cstring>
#include <cstdlib>
#include <set>
#include <string>
#include <vector>
#include <algorithm>
#include <bitset>
#define endl '\n'
#define int long long
#define INF 2147483647
#define MOD 19260817
using namespace std;
int Max(int a,int b){return a>b?a:b;}
int Min(int a,int b){return a<b?a:b;}
int QPow(int a,int b){int res=1;while(b){if(b&1){res=(res*a)%MOD;}b>>=1;a=(a*a)%MOD;}return res%MOD;}
int Inv(int a,int Mod){return QPow(a,Mod-2);}
const int MAXN = 1e4;
struct Node{
    int v,pos;
    bool operator < (const Node & x) const{
        return v < x.v;
    }
};
vector<Node> a;
vector<Node> b;
int aa[MAXN];
int ls[MAXN];
int ct[MAXN];
int n,q;
bool cmp1(Node x,Node y){
    if(x.v == y.v){
        return x.pos < y.pos;
    }
    return x.v < y.v;
}
bool cmp2(Node x,Node y){
    return x.pos < y.pos;
}
signed main(void){
    // scanf("%lld%lld",&n,&q);
    cin >> n >> q;
    Node nod;
    Node mmin;
    mmin.v = -INF;
    mmin.pos = 0;
    Node mmax;
    mmax.v = INF;
    mmax.pos = n+1;
    a.push_back(mmin);
    b.push_back(mmin);
    for(int i=1;i<=n;i++){
        cin >> nod.v;nod.pos = i;
        a.push_back(nod);
        b.push_back(nod);
        aa[i] = nod.v;
    }
    a.push_back(mmax);
    b.push_back(mmax);
    sort(aa+1,aa+1+n);
    int cnt = unique(aa+1,aa+1+n) - aa - 1;
    for(int i=1;i<=n;i++){
        ls[i] = lower_bound(aa+1,aa+1+cnt,b[i].v) - aa;
    }
    sort(a.begin(),a.end(),cmp1);
    for(int i=1;i<=n;i++){
        b[i].pos = lower_bound(a.begin(),a.end(),b[i]) - a.begin() + ct[ls[i]];
        ct[ls[i]]++;
    }
    int op,x;
    Node v;
    while(q--){
        scanf("%lld%lld",&op,&x);
        if(op==1){
            scanf("%lld",&(v.v));
            int pps = b[x].pos;
            int ppps;
            b[x].v = v.v;
            a[pps].v = v.v;
            for(int i=pps;i<n;i++){
                if(a[i].v > a[i+1].v){
                    b[a[i].pos].pos++;
                    b[a[i+1].pos].pos--;
                    Node temp = a[i];
                    a[i] = a[i+1];
                    a[i+1] = temp;
                }else if(a[i].v == a[i+1].v){
                    if(a[i].pos > a[i+1].pos){
                        b[a[i].pos].pos++;
                        b[a[i+1].pos].pos--;
                        Node temp = a[i];
                        a[i] = a[i+1];
                        a[i+1] = temp;
                    }
                }
            }
            for(int i=pps;i>=1;i--){
                if(a[i].v < a[i-1].v){
                    b[a[i].pos].pos--;
                    b[a[i-1].pos].pos++;
                    Node temp = a[i];
                    a[i] = a[i-1];
                    a[i-1] = temp;
                }else if(a[i].v == a[i-1].v){
                    if(a[i].pos < a[i-1].pos){
                        b[a[i].pos].pos--;
                        b[a[i-1].pos].pos++;
                        Node temp = a[i];
                        a[i] = a[i-1];
                        a[i-1] = temp;
                    }
                }
            }
        }else{
            printf("%lld\n",b[x].pos);
        }
    }
    return 0;
}

[CSP-J 2021] 小熊的果篮

题意略过
这题用 LIST 做,模拟每个块。如果当前块之后的那个块的元素相同,那么合并起来。然后删除后面那个块。如果当前块元素为空,那么直接删除本块。
由于 LIST 的合并( splice )和删除( erase 或者 pop\_front )操作时间复杂度都是 O(1) ,所以这个算法的整体时间复杂度为 O(N)
不要用 vector ,因为 vector 的合并( insert )和删除( erase )的时间复杂度都是 O(N),用了vector后的时间复杂度会退化到 O(N^2)

#include <iostream>
#include <cstdio>
#include <ctime>
#include <stack>
#include <queue>
#include <map>
#include <cstring>
#include <cstdlib>
#include <set>
#include <string>
#include <vector>
#include <algorithm>
#include <bitset>
#include <list>
#define endl '\n'
#define int long long
#define INF 2147483647
#define MOD 19260817
using namespace std;
int Max(int a,int b){return a>b?a:b;}
int Min(int a,int b){return a<b?a:b;}
int QPow(int a,int b){int res=1;while(b){if(b&1){res=(res*a)%MOD;}b>>=1;a=(a*a)%MOD;}return res%MOD;}
int Inv(int a,int Mod){return QPow(a,Mod-2);}
const int MAXN = 2e5+7;
int n;
struct Node{
    int v,pos;
    bool operator<(const Node &x) const{
        if(v==x.v){
            return pos < x.pos;
        }
        return v < x.v;
    }
}a[MAXN];
// vector<vector<Node> > p;
list<list<Node> > ls;
// void ptp(){
//     int len = p.size();
//     for(int i=0;i<len;i++){
//         int len2 = p[i].size();
//         for(int j=0;j<len2;j++){
//             printf("%lld ",p[i][j].v);
//         }
//         printf("\n");
//     }
// }
void ptls(){
    for(auto it = ls.begin();it != ls.end();it++){
        for(auto iit = (*it).begin();iit != (*it).end();iit++){
            printf("%lld ",iit->v);
        }
        printf("\n");
    }
}
signed main(void){
    // freopen("in.in","r",stdin);
    // freopen("res.out","w",stdout);
    scanf("%lld",&n);
    int pre = -1;
    int cnt = -1;
    int v;
    auto it = ls.begin();
    for(int i=1;i<=n;i++){
        scanf("%lld",&v);
        a[i].v = v;
        a[i].pos = i;
        if(a[i].v != pre){
            //不等于前面的,代表要创建一个新的块
            cnt++;
            vector<Node> temp;
            list<Node> tp;
            // p.push_back(temp);
            ls.push_back(tp);
            if(cnt == 0){
                it = ls.begin();
            }else{
                it++;
            }
        }
        // p[cnt].push_back(a[i]);
        it->push_back(a[i]);
        pre = a[i].v;
    }
    // ptls();
    // while(!p.empty()){
    //     // cout << "***" << endl;
    //     // ptp();
    //     // cout << "***" << endl;
    //     for(int i=0;i<=cnt;i++){
    //         if(!p[i].empty()){
    //             printf("%lld ",p[i][0].pos);
    //             while(i+1<=cnt){
    //                 if(p[i][0].v == p[i+1][0].v){
    //                     p[i].insert(p[i].end(),p[i+1].begin(),p[i+1].end());
    //                     p.erase(p.begin()+i+1);
    //                     cnt--;
    //                 }else{
    //                     break;
    //                 }
    //             }
    //             p[i].erase(p[i].begin());
    //             if(p[i].empty()){
    //                 p.erase(p.begin()+i);
    //                 i--;
    //                 cnt--;
    //                 continue;
    //             }
    //         }else{
    //             p.erase(p.begin()+i);
    //             i--;
    //             cnt--;
    //             continue;
    //         }
    //     }
    //     printf("\n");
    // }
    while(!ls.empty()){
        // cout << "***" << endl;
        // ptls();
        // cout << "***" << endl;
        for(auto i=ls.begin();i != ls.end();i++){
            if(!(i->empty())){
                auto itt = i;
                auto ttp = i;
                printf("%lld ",i->front().pos);
                while(++ttp != ls.end()){
                    if(itt->front().v == ttp->front().v){
                        itt->splice(itt->end(),*ttp,ttp->begin(),ttp->end());
                        ls.erase(ttp);
                        ttp = i;
                    }else{
                        break;
                    }
                }
                i->pop_front();
                if(i->empty()){
                    i = ls.erase(i);
                    i--;
                    continue;
                }
            }
        }
        printf("\n");
    }
    return 0;
}

第三题

题目太长,没做

©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容