目錄

供水管線

黑客小碼哥

?逆序

來(lái)給單詞分類

?前k小數(shù)（進(jìn)階）

?前K小數(shù)

線段樹

?隊(duì)列安排

?一元多項(xiàng)式的加法

快排變形

供水管線

難度：鉆石
0時(shí)間限制：1秒
巴占用內(nèi)存：128M
在個(gè)城市之間原本要規(guī)劃修建許多條下水管道，管理人員發(fā)現(xiàn)這些管道會(huì)形成一條
回路，而下水道只要將城市聯(lián)通即可，所以回路會(huì)加大施工的成本。所以希望你來(lái)幫忙
找出多余的管道來(lái)進(jìn)行優(yōu)化。當(dāng)然管道和管道之間是有區(qū)別的，比如用s來(lái)表示i到
的管道管理費(fèi)用，S越小則表示該管道管理費(fèi)用越低。能否去除一些管線，使得總
管理成本最低。求出最低的管理成本（不存在自身與自身成為回路的管道）。

//
// Created by abner on 2023/5/10.
//
#include <bits/stdc++.h>
using namespace std;
const int N = 1e2 + 7;
struct NODE{
int i,j,c;
bool operator<(const NODE &t)const { return c < t.c;}
}p[N];
int fa[N],n,k,ans;
void init(){
    for (int i=1;i<N;i++)
        fa[i]= i;
}
int find(int x){return x == fa[x] ? x: (fa[x] = find(fa[x]));}
void mer(int x,int y) {
    x = find(x), y = find(y);
    if (x != y)
        fa[x] = y;
}
    int main(){
        init();
        cin >>n >> k;
        for (int i=1;i<=k;i++)
            cin >> p[i].i>>p[i].j>>p[i].c;
        sort(p + 1,p + 1 + k);
        for (int i=1;i<=k;i++)
            if (find(p[i].i)!=find(p[i].j)){
                ans += p[i].c;
                mer(p[i].i,p[i].j);
            }
        cout <<ans;
        return 0;
            }

黑客小碼哥

難度：黃金
時(shí)間限制：1秒
巴占用內(nèi)存：256M
小碼哥是一名黑客，他最近剛彩票中獎(jiǎng)，由于還沒(méi)兌換，小碼哥十分擔(dān)心彩票被盜（小
碼哥過(guò)分謹(jǐn)慎了)，他想為自己的保險(xiǎn)箱設(shè)新的密碼，順便他想讓你測(cè)試編碼。
現(xiàn)有兩種編碼方式：
1.對(duì)于己知字符串中的某種字符，全部變成另一種字符。如里面出現(xiàn)的A全部換成B;
2.對(duì)于當(dāng)前字符串，打亂字符順序。
先給你一個(gè)加密后的字符串和加密前的字符串，判斷加密前的字符串是否能得到加密后
的字符串。字符串中字符均為大寫字母。
格式
輸入格式：第一行加密后的字符串；
第二行加密前的字符串；
有多組數(shù)據(jù)輸入。?

/*
    MT2128 黑客小碼哥 
        
*/

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

const int LETERCNT = 26;

// 判斷兩個(gè)字符串是否有可能是經(jīng)過(guò)指定加密算法處理前后的兩串 
bool isSamePossiblely(string str1, string str2){
    
    // 長(zhǎng)度不同就一定不是
    int strlen = str1.length();
    if(strlen != str2.length()) return false; 
    
    // 否則進(jìn)一步判斷各字符的出現(xiàn)次數(shù)是否一致
    int ary1[LETERCNT]={0}, ary2[LETERCNT]={0};
    
    // 先統(tǒng)計(jì)各字符串中不同字符的出現(xiàn)次數(shù)（即認(rèn)為存在字符變換操作）
    for(int i=0; i<strlen; i++){
        ary1[str1[i]-'A']++;
        ary2[str2[i]-'A']++;
    }
    
    // 消除字符間的順序差異（即認(rèn)為存在字符順序變換操作）
    sort(ary1, ary1+LETERCNT); 
    sort(ary2, ary2+LETERCNT); 
    
    // 判斷是否可能是變換前后的兩字符串 
    for(int i=0;i<LETERCNT;i++)
        if(ary1[i] != ary2[i]) 
            return false;
            
    return true;
}

int main()
{
    string str1, str2; 
    while(cin>>str1>>str2) {
        if(isSamePossiblely(str1, str2)) cout<<"YES"<<endl;
        else cout<<"NO"<<endl;
    }
    
    return 0;
}

//
// Created by abner on 2023/5/10.
//
#include <bits/stdc++.h>
using namespace std;
string s1,s2;
int st1[30],st2[30];
int main(){
    while (cin >>s1 >>s2){
        memset(st1,0,sizeof(st1));
        memset(st2,0,sizeof(st2));
        if (s1.length()!=s2.length()){
            cout <<"NO"<<endl;
            continue;
        }
        for (int i=0;i<s1.length();i++)
            st1[s1[i]-'A']++,st2[s2[i]-'A']++;
        sort(st1,st1 +26);
        sort(st2,st2 + 26);
        bool flag = true;
        for (int i=0;i<26;i++){
            if (st1[i] != st2[i]){
                cout <<"NO"<<endl;
                flag = false;
                break;
            }
        }
        if (flag)
            cout <<"YES"<<endl;
    }
    return 0;
}

?逆序

號(hào)難度：鉆石
0時(shí)間限制：1秒
巴占用內(nèi)存：128M
給一個(gè)長(zhǎng)度為的排列p，找一個(gè)元素，使得從排列中取出這個(gè)元素以后排列
的
records
最多。
一個(gè)
record
是一個(gè)元素a,滿足：對(duì)于每個(gè)正整數(shù)1≤j<i,a>aj。
格式
輸入格式：第一行為n;
第二行為排列p。
輸出格式：一個(gè)整數(shù)即答案。
樣例1
輸入：5
復(fù)制

//
// Created by abner on 2023/5/10.
//
#include <bits/stdc++.h>
using namespace std;
const int N=1e5 + 7;
int n;
int c[N],chg [N];
int lowbit(int x){return x & -x;}
    void add(int x){
        for (;x < N;x += lowbit(x))
            c[x]++;
    }
    int sum(int x){
        int ret =0;
        for (;x> 0;x -= lowbit(x))
            ret += c[x];
        return ret;
    }
    int main(){
        cin >> n;
        int x=0,maxx =0;
        for (int i=1;i<=n;i++){
            cin >>x;
            maxx = max(maxx,x);
            int cnt = sum(x);
            if (cnt ==i-1)
                chg [maxx]--;
            else if (cnt ==i-2)
                chg [maxx]++;
            add (x);
        }
        int ans = 1;
        for (int i = 1;i <= n;i++)
        if (chg[i] > chg[ans])
        ans = i;
        cout <<ans <<endl;
        return 0;
    }

來(lái)給單詞分類

難度：鉆石
0時(shí)間限制：1秒
巴占用內(nèi)存：128M
現(xiàn)有如下單詞分類原則：兩個(gè)單詞可以分為一類當(dāng)且僅當(dāng)組成這兩個(gè)單詞的各個(gè)字母的
數(shù)量均相等。
現(xiàn)有n個(gè)單詞均由大寫字母組成，每個(gè)單詞長(zhǎng)度小于等于10。求單詞被分為幾類。
格式
輸入格式：第一行輸入單詞個(gè)數(shù)n;
以下n行每行一個(gè)單詞。
輸出格式：一個(gè)整數(shù)表示類數(shù)。
樣例1
輸入：3
復(fù)制?

import java.util.Scanner;
import java.util.*;
class Main {
 public static void main(String[] args) {

 Scanner input = new Scanner(System.in);
 int n= Integer.parseInt(input.next());

 Set<String> a=new HashSet<>();

 for (int i = 0; i < n; i++) {
 char[] ch=input.next().toCharArray();
 int[] b=new int[26];
 for (int j = 0; j < ch.length; j++) {
 b[ch[j]-'A']++;
 }
 a.add(Arrays.toString(b));
 }
 System.out.println(a.size());
 input.close();
 }
}

?前k小數(shù)（進(jìn)階）

難度：黃金
時(shí)間限制：1秒
巴占用內(nèi)存：128M
給你n個(gè)長(zhǎng)度為m的已知數(shù)列，你一次可以從每個(gè)數(shù)列中選出一個(gè)元素，共n個(gè)數(shù)，
將這n個(gè)數(shù)的和，放入a數(shù)組中，窮舉所有的選數(shù)可能，并且都放入a數(shù)組中。
小碼哥請(qǐng)你計(jì)算a數(shù)列中前k小數(shù)是多少？
格式
輸入格式：輸入n,m,k;
接下來(lái)n行，每一行m個(gè)數(shù)，空格分隔，一行表示一個(gè)數(shù)列，共n
行。
輸出格式：從小到大輸出前k小的數(shù)。

//
// Created by abner on 2023/5/10.
//
#include <bits/stdc++.h>
using namespace std;
const int N = 1e8 + 7;
int n,m,k,a[N],b[N],c[N];
struct NODE {
    int ida, idb, num;

    bool operator>(const NODE &a) const { return num > a.num; }
}tmp;
priority_queue<NODE,vector<NODE>,greater<NODE>>q;
int main(){
    cin>>n>>m>>k;
    for (int i=1;i <=m;i++)
        cin >>a[i];
    for (int i = 1;i<=m;i++)
    cin >>b[i];
    sort(a + 1,a + m + 1);
    sort(b+1,b+m+1);
    for (int i = 1;i<=m;i++)
    q.push({i,1,a[i]+b[1]});
    for (int i = 1;i<=k;i++) {
        tmp = q.top(), q.pop();
        c[i] = tmp.num;
        tmp.num = a[tmp.ida] + b[++tmp.idb];
        q.push(tmp);
    }
    n-=2;
    while (n--){
        while (!q.empty())
            q.pop();
    for (int i=1;i <= k;i++)
        a[i]=c[i];
    for (int i=1;i <=m;i++)
        cin >>b[i];
    sort(b+1,b+m+1);
    for (int i=1;i <=k;i++)
        q.push({i,1,a[i]+b[1]});
        for (int i=1;i <=k;i++) {
            tmp = q.top(), q.pop();
            c[i] = tmp.num;
            tmp.num = a[tmp.ida] + b[++tmp.idb];
            q.push(tmp);
        }
        }
        for (int i=1;i<=k;i++)
        cout <<c[i]<<" ";
        return 0;
               }

?前K小數(shù)

難度：黃金
?時(shí)間限制：1秒
巴占用內(nèi)存：128M
小碼哥現(xiàn)在手上有兩個(gè)長(zhǎng)度為n的數(shù)列a,b,(1≤i,j≤n)通過(guò)a,+b,可以構(gòu)造
出n*n個(gè)數(shù)，求構(gòu)造出的數(shù)中前k小的數(shù)。
格式
輸入格式：第一行2個(gè)數(shù)n,k;
第二行n個(gè)數(shù)，表示數(shù)列a;
第三行n個(gè)數(shù)，表示數(shù)列b。
輸出格式：從小到大輸出前飛小的數(shù)。
樣例1
輸入：33
復(fù)制
266

 #include<bits/stdc++.h>

 using namespace std;
 const int maxSize = 10100;
 int a[maxSize];
 int b[maxSize];
 struct Node{
 int sum,b;
 Node(int sum,int b):sum(sum),b(b){}
 bool operator < (const Node &b) const{
 return sum>b.sum;
 }
 };
 priority_queue<Node>minList;
 int main(){
 int n,k;
 cin>>n>>k;
 for(int i=0;i<n;i++){
 cin>>a[i];
 }
 for(int i=0;i<n;i++){
 cin>>b[i];
 }
 sort(a,a+n);
 sort(b,b+n);
 for(int i=0;i<n;i++){
 minList.push(Node(a[i]+b[0],0));
 }
 for(int i=0;i<k;i++){
 Node node=minList.top();
 minList.pop();
 cout<<node.sum<<" ";
 int tempB = node.b;
 if(tempB+1<n){
 minList.push(Node(node.sum-b[tempB]+b[tempB+1],tempB+1));
 }
 }

 return 0;
 }

線段樹

難度：鉆石
0時(shí)間限制：1秒
巴占用內(nèi)存：128M
線段樹模板題。已知一個(gè)數(shù)列，你需要進(jìn)行下面兩種操作：將某區(qū)間每一個(gè)數(shù)加上
,求出某區(qū)間每一個(gè)數(shù)的和。
格式
輸入格式：第一行包含兩個(gè)整數(shù)n,m(5≤n,m≤105)，分別表示該數(shù)列數(shù)字的
個(gè)數(shù)和操作的總個(gè)數(shù)；
第二行包含n個(gè)用空格分隔的整數(shù)(0-109)，其中第i個(gè)數(shù)字表
示數(shù)列第i項(xiàng)的初始值：
接下來(lái)行每行包含3或4個(gè)整數(shù)，表示一個(gè)操作，具體如下：
1xyk:將區(qū)間[X,y]內(nèi)每個(gè)數(shù)加上k。
2xy:輸出區(qū)間[x,y內(nèi)的數(shù)的和。
其中：1≤x≤y≤n,0≤k≤105。
輸出格式：輸出包含若干行整數(shù)，
即為所有操作2的結(jié)果。?

//
// Created by abner on 2023/5/10.
//
#include <bits/stdc++.h>
using namespace std;
const int N=1e5 + 7;
#define int long long//有時(shí)候覺(jué)得ll麻煩，就可以用。但記得改signed main
struct NODE {
    int l, r, val, lz;//lz為懶標(biāo)記
}tree[4 * N];
int a[N];

void build(int p,int l,int r){
    tree[p].l=l,tree[p].r=r;
    if(l==r){
        tree[p].val = a[l];
        return;
    }
    int mid =l + ((r-l)>>1);
    build(p *2,l,mid);
    build(p *2 + 1,mid + 1,r);
    tree[p].val = tree[p* 2].val + tree[p * 2+ 1].val;
}
void lazy(int p,int v) {
    int s = tree[p].l, t = tree[p].r;
    tree[p].val += (t - s + 1) * v, tree[p].lz += v;
}
    void pushdown(int p){
        lazy(2 * p,tree[p].lz);
        lazy(2 * p +1,tree[p].lz);
        tree[p].lz = 0;
}
        //帶懶標(biāo)記區(qū)間修改，[1，r]
//為修改區(qū)間，p為當(dāng)前節(jié)點(diǎn)編號(hào)，c為區(qū)間節(jié)點(diǎn)變化值，求和非求最值
        void update(int l,int r,int c,int p){
            int s =tree[p].l,t = tree[p].r;
            if (l <=s && t <=r)
                return lazy(p,c);
            if (tree[p].lz && s != t)
            pushdown(p);
            int mid = s +((t -s)>>1);
            if (l<=mid)
            update(l,r,c,p * 2);
            if (r > mid)
                update(l,r,c,p * 2+1);
            tree[p].val =tree[p * 2].val+ tree[p * 2 + 1].val;
        }
//帶懶標(biāo)記區(qū)間查詢（區(qū)間求和），[L,r】為修改區(qū)間，p為當(dāng)前節(jié)點(diǎn)編號(hào)
        int query(int l,int r,int p) {
            int s = tree[p].l, t = tree[p].r;
            if (l <= s && t <= r)
                return tree[p].val;
            if (tree[p].lz)
                pushdown(p);
            int mid = s + ((t - s) >> 1), sum = 0;
            if (l <= mid)
                sum = query(l, r, p * 2);
            if (r > mid)
                sum += query(l, r, p * 2 + 1);
            return sum;
        }
signed main(){
    int n,m;
    cin>>n>>m;
    for (int i=1;i<=n;i++)
        cin >>a[i];
    build(1,1,n);
    while (m--){
        int op,x,y,k;
        cin >>op;
        if (op ==1) {
            cin >> x >> y >> k;
            update(x, y, k, 1);
        }else{
            cin >>x >>y;
            cout <<query(x,y,1)<<endl;
        }
    }
    return 0;
}

?隊(duì)列安排

難度：黃金
時(shí)間限制：1秒
巴占用內(nèi)存：128M
一個(gè)學(xué)校里老師要將班上N個(gè)同學(xué)排成一列，同學(xué)被編號(hào)為1~N,他采取如下的方
法：
1.先將1號(hào)同學(xué)安排進(jìn)隊(duì)列，這時(shí)隊(duì)列中只有他一個(gè)人：
2.2一N號(hào)同學(xué)依次入列，編號(hào)為1的同學(xué)入列方式為：老師指定編號(hào)為1的同學(xué)站在
編號(hào)為1~（億一1）中某位同學(xué)（即之前已經(jīng)入列的同學(xué)）的左邊或右邊：
3.從隊(duì)列中去掉M(M<N)個(gè)同學(xué)，其他同學(xué)位置順序不變。
在所有同學(xué)按照上述方法隊(duì)列排列完畢后，老師想知道從左到右所有同學(xué)的編號(hào)。
格式
輸入格式：第1行為一個(gè)正整數(shù)N，表示了有N個(gè)同學(xué)；
第2一N行，第i行包含兩個(gè)整數(shù)k,p,其中k為小于i的正整數(shù)，
p為0或者1。若p為0，則表示將i號(hào)同學(xué)插入到k號(hào)同學(xué)的左邊，p
為1耒示活入右力·

#include<iostream>
#include<bits/stdc++.h>
#include<algorithm>
#include<math.h>
#include<string.h>
#include<string>
using namespace std;
const int N = 1e6+10;
struct line
{
	int pr, ne;
	bool mk;
}a[N]; 
int f[N];
int n , m;
int ans = 0;
int main()
{
	cin >> n;
	int i , j;
	int k , p;
	a[0].ne = 1;
	a[0].pr = 0;
	a[1].mk = 1;
	a[1].pr = 0;
	for(i = 2 ; i <= n ; i++)
	{
		cin >> k >> p;
		a[i].mk = 1;
		if(p == 0)
		{
			a[a[k].pr].ne = i;
			a[i].pr = a[k].pr;
			a[k].pr = i;
			a[i].ne = k;
		}
		else
		{
			a[a[k].ne].pr = i;
			a[i].pr = k;
			a[i].ne = a[k].ne;
			a[k].ne = i;
		}
	}
	cin >> m;
	int x;
	for(i = 1 ; i <= m ; i++)
	{
		cin >> x;
		if(!a[x].mk)
		{
			continue;
		}
		a[x].mk = 0;
		a[a[x].pr].ne = a[x].ne;
		a[a[x].ne].pr = a[x].pr;
	}
	printf("%d",a[0].ne);
	int now = a[0].ne;
	now = a[now].ne;
	while(now)
	{
		printf(" %d",now);
		now = a[now].ne;
	}
	cout << endl;
	return 0;
}

?一元多項(xiàng)式的加法

號(hào)難度：鉆石
0時(shí)間限制：1秒
巴占用內(nèi)存：128M
小碼哥給出兩個(gè)一元多項(xiàng)式工4和工B，請(qǐng)你將這兩個(gè)一元多項(xiàng)式相加，得到新的一元
多項(xiàng)式Lc。
如樣例：
L4=1-10x6+2x8+7x14
LB=-x4+10x6-3x19+8x14+4x18
LC=LA+LB=1-x4+2x8-3x19+15x14+4x18
格式
輸入格式：第一行兩個(gè)整數(shù)n和m,分別表示L4和LB的項(xiàng)數(shù)；
接下來(lái)n行，每行輸入工4的每一項(xiàng)的信息，兩個(gè)整數(shù)分別表示該項(xiàng)
的系數(shù)coef和次數(shù)expm,輸入保證次數(shù)遞增；
接下來(lái)m行，每行輸入LB的每一項(xiàng)的信息，兩個(gè)整數(shù)分別表示該項(xiàng)

//
// Created by abner on 2023/5/10.
//
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int N =2e6 +7;
struct NODE {
    ll nex, coef, expn;
}node [N];
int n,m,head,tail,pos;
ll coefA[N],expnA[N],coefB[N],expnB[N];
void insert(int curr,ll val1,ll val2){
    node[++pos].coef = val1;
    node[pos].expn = val2;
    node[pos].nex = node[curr].nex;
    node[curr].nex = pos;
    if (!node[pos].nex)
        tail = pos;
}
    int main(){
        scanf("%d%d",&n,&m);
        for (int i=1;i<=n;i++)
            scanf("%ld%lld",&coefA[i],&expnA[i]);
        for (int i=1;i<=m;i++)
            scanf("%lld%lld",&coefB[i],&expnB[i]);
        int l=1,r=1;
        while (l <=n &&r<=m) {
            if (expnA[l] == expnB[r]) {
                insert(tail, coefA[l] + coefB[r], expnA[l]);
                l++, r++;
            } else {
                if (expnA[l] < expnB[r]) {
                    insert(tail, coefA[l], expnA[l]);
                    l++;
                } else {
                    insert(tail, coefB[r], expnB[r]);
                    r++;
                }
            }
        }
                while (l <=n) {
                    insert(tail, coefA[l], expnA[l]);
                    l++;
                }
while (r <=m) {
    insert(tail, coefB[r], expnB[r]);
    r++;
}
for (int i=node[head].nex;i!=0;i=node[i].nex)
if (node[i].coef !=0)
printf("%lld %lld\n",node[i].coef,node[i].expn);
return 0;
}

快排變形

難度：黃金
0時(shí)間限制：1秒
巴占用內(nèi)存：128M
有”個(gè)數(shù)，問(wèn)如果通過(guò)每次交換鄰項(xiàng)的兩個(gè)數(shù)來(lái)使數(shù)組中的元素變?yōu)樯蚺帕小?br> eg:98765,
變?yōu)樯颍?br> 56789.
需要10次鄰項(xiàng)交換。
格式
輸入格式：第一行輸入一個(gè)整數(shù)n,表示序列長(zhǎng)度：
第二行輸入n個(gè)數(shù)。
輸出格式：輸出一個(gè)整數(shù)，表示最少的交換次數(shù)。?文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-471275.html

//
// Created by abner on 2023/5/10.
//
#include <bits/stdc++.h>
using namespace std;
const int N=2e5 +7;
int a[N],b[N],c[N],n;
long long ans;
int lowbit(int x){return x &-x;}
    void add(int i,int x){
        for (;i<=n;i+=lowbit(i))
            c[i]+=x;
    }
    int sum(int i){
        int ans =0;
        for (;i>0;i-=lowbit(i))
            ans +=c[i];
        return ans;
    }
    bool cmp(const int x,const int y){
        if (b[x]==b[y])
            return x >y;
        return b[x] > b[y];
    }
    int main(){
        cin >>n;
        for (int i=1;i<=n;i++) {
            cin >> b[i];
            a[i] = i;
        }
            sort(a +1,a +n+1,cmp);
            for (int i=1;i<=n;i++){
                add(a[i],1);
                    ans += sum(a[i]-1);
                    }
                    cout <<ans <<endl;
                    return 0;
                    }

到了這里，關(guān)于馬蹄集第四期oj的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！