桂林电子科技大学第三届ACM程序设计竞赛 题解

 

题目链接：https://ac.nowcoder.com/acm/contest/558#question

 

 

 

A.串串

链接：https://ac.nowcoder.com/acm/contest/558/A
来源：牛客网
 

题目描述

小猫在研究字符串。

小猫在研究字串。

给定一个长度为N的字符串S，问所有它的子串Sl…r(1≤l≤r≤N)，去重后有多少种。

输入描述:

一行一个字符串S。

输出描述:

一行一个整数，表示答案。

示例1

输入

复制

ababa

输出

复制

9

备注:

1≤N≤105，字符都是小写字母

后缀数组

 

B.重复

链接：https://ac.nowcoder.com/acm/contest/558/B

来源：牛客网
 

题目描述

小猫在研究字符串。

小猫在研究重复。

给定N个长度为M的字符串，问这些字符串去重后有几种。

输入描述:

第一行两个正整数N,M，表示字符串的个数与长度。

接下来N行，每行一个长度为M的字符串。

输出描述:

一行一个整数，表示答案。

示例1

输入

复制

4 3
abc
abb
abb
cbc

输出

复制

3

备注:

1≤N≤105,1≤M≤100，字符都是小写字母

签到题

import java.util.HashSet;
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		int T = in.nextInt();
		int n = in.nextInt();
		HashSet<String> set = new HashSet<>();
		while(T-->0) 
			set.add(in.next());
		
		System.out.println(set.size());
	}

}

 

C.二元

链接：https://ac.nowcoder.com/acm/contest/558/C
来源：牛客网
 

题目描述

小猫在研究二元组。

小猫在研究最大值。

给定N个二元组(a1,b1),(a2,b2),…,(aN,bN)，请你从中选出恰好K个，使得ai的最小值与bi的最小值之和最大。

请输出ai的最小值与bi的最小值之和

输入描述:

第一行两个正整数N,K，表示二元组数量与需要选的数量。

接下来N行，第i行两个正整数ai,bi。

输出描述:

一行一个正整数，表示最大的a_i的最小值与b_i的最小值之和。

示例1

输入

复制

3 2
1 1
2 3
3 1

输出

复制

3

#include <stdio.h>
#include <queue>
#include <vector>
#include <algorithm>
 
using namespace std;
 
#define N 110000
 
struct Node {
    int a, b;
    bool operator < (const Node &u) const {
        return b > u.b;
    }
};
 
Node a[N];
 
int main() {
    int n, k;
    scanf("%d%d", &n, &k);
    for (int i = 0; i < n; ++i) scanf("%d%d", &a[i].a, &a[i].b);
    sort(a, a + n);
    int res = 0;
    priority_queue<int, vector<int>, greater<int> > q;
    for (int i = 0; i < n; ++i) {
        q.push(a[i].a);
        if (q.size() > k) q.pop();
        if (q.size() == k) res = max(res, q.top() + a[i].b);
    }
    printf("%d\n", res);
    return 0;
}

 

D.寻找

链接：https://ac.nowcoder.com/acm/contest/558/D
来源：牛客网
 

题目描述

小猫在研究树。

小猫在研究树上的距离。

给定一棵N个点的树，每条边边权为1。

Q次询问，每次给定a,b,c，请你输出a到b的路径上离c最近的点的编号。

输入描述:

第一行一个正整数N，表示节点数量。

接下来N−1行，第i行两个正整数ui,vi，表示第i条边连接节点ui,vi。

接下来一行一个正整数Q，表示询问数量。

接下来Q行，每行三个正整数a,b,c，表示一组询问。

输出描述:

Q行，每行一个正整数，表示每个询问的答案。

示例1

输入

复制

5
1 2
1 3
2 4
2 5
3
1 2 3
4 5 1
1 4 5

输出

复制

1
2
2

备注:

1≤N,Q≤105

通过率最低的一题 

 

E.区间

链接：https://ac.nowcoder.com/acm/contest/558/E
来源：牛客网
 

题目描述

小猫在研究序列。

小猫在研究单调性。

给定一个长度为N的序列a1,a2,…,aN，请你选出一个最长的区间[l,r](1≤l≤r≤N)，满足al≤al+1≤…≤ar。

如果有多个，请输出l最小的。

输入描述:

第一行一个正整数T，表示数据组数。

每组数据的第一行一个正整数N。

接下来一行N个正整数a1,a2,…,aN。

输出描述:

T行，每行两个正整数l,r，表示选出的区间。

示例1

输入

复制

4
5
1 2 3 4 5
5
5 4 3 2 1
5
5 3 4 1 2
5
3 4 5 1 2

输出

复制

1 5
1 1
2 3
1 3

备注:

1≤T,N,ai≤1000

双指针

import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		int T = in.nextInt();
		while(T-->0) {
			int n = in.nextInt();
			int[] a = new int[n+5];
			for(int i=1;i<=n;i++)
				a[i] = in.nextInt();
			
			int x=1,y=1,i=1,j=2,len=1,sum=1;
			
			while(j<=n) {
				if(a[j]>=a[j-1]) {
					sum++;
					j++;
				}else {
					if(sum>len) {
						x = i;
						y = j-1;
						len = sum;
					}
					sum=1;
					i=j;
					j++;
				}
			}
			
			if(sum>len) {
					x = i;
					y = j-1;
					len = sum;
				}
		
			System.out.println(x+" "+y);
		}
		
	}

}

 

F.点对

链接：https://ac.nowcoder.com/acm/contest/558/F
来源：牛客网
 

题目描述

小猫在研究有向图。小猫在研究联通性。

给定一张N个点，M条边的有向图，问有多少点对(u,v)(u<v)，满足u能到达v且v也能到达u。

输入描述:

第一行两个正整数N,M，表示点数与边数。接下来M行，第i行两个正整数ui,vi，表示一条从ui到vi的边，保证ui≠vi。

输出描述:

一行一个整数，表示点对数量。

示例1

输入

复制

3 3
1 2
2 3
3 2

输出

复制

1

备注:

1≤N≤300,1≤M≤N(N−1)

题目讲的看起来是欧拉回路，但做法却是并查集，对并查集的应用不是很熟，联想到并查集有点难度

#include<iostream>
#include<cstdio>
using namespace std;

const int MAX = 305;

int f[MAX];

int find(int x){
    if(f[x]==x)
        return x;
    return f[x] = find(f[x]);
}

void Union(int x,int y){
    int a = find(x);
    int b = find(y);
    if(a!=b)
        f[a] = b;
}


int main(){
    int a,b,n,m;
    while(~scanf("%d%d",&n,&m)){
        int ans = 0;
        for(int i=1;i<=n;i++)
            f[i] = i;
        for(int i=1;i<=m;i++){
            scanf("%d%d",&a,&b);
            Union(a,b);
        }
    for(int i=1; i<=n;i++)
        for(int j=1; j<=n; j++)
            if(i != j && i < j)
                if(f[i] == f[j])
                    ans++;

        printf("%d\n",ans);
    }


	return 0;
}

G.路径

链接：https://ac.nowcoder.com/acm/contest/558/G
来源：牛客网
 

题目描述

小猫在研究树。

小猫在研究路径。

给定一棵N个点的树，每条边有边权，请你求出最长的一条路径，满足经过每个点最多一次，经过的边的条数为偶数，且边权和最大。

请输出这个最大的边权和。

输入描述:

第一行一个正整数N，表示节点个数。

接下来N−1行，第i行三个正整数

ui,vi,wi，表示第i条边连接点ui,vi，边权为wi。

输出描述:

一行一个正整数，表示最大的边权和。

示例1

输入

复制

5
1 2 5
1 3 5
2 4 5
2 5 1

输出

复制

10

备注:

1≤N≤105,1≤wi≤109，保证输入数据形成一棵树。

#include<bits/stdc++.h>
using namespace std;
#define int long long
typedef long long ll;
const int maxx=1e5+2;
struct S{
    int to;
    ll val;
};
vector<S> a[maxx];
int in[maxx],root;
ll dp[maxx][2];// 1 偶数 0 奇数
ll ans=0;
void dfs(int x,int fa){
    for(int i=0;i<a[x].size();i++){
        S t=a[x][i];
        if(t.to==fa) continue;
        dfs(t.to,x);
        if(dp[t.to][0]) ans=max(ans,dp[x][1]+dp[t.to][0]+t.val);
        if(dp[x][0]) ans=max(ans,dp[x][0]+dp[t.to][1]+t.val);
        if(dp[t.to][0]) dp[x][1]=max(dp[x][1],dp[t.to][0]+t.val);
        dp[x][0]=max(dp[x][0],dp[t.to][1]+t.val);
    }
}
int32_t main(){
    int n;
    cin>>n;
    for(int i=1;i<n;i++){
        int u,v;ll w;
        scanf("%lld%lld%lld",&u,&v,&w);
        a[u].push_back(S{v,w});
        a[v].push_back(S{u,w});
        in[v]++;
    }
    dfs(1,0);
    cout<<ans<<endl;
}

 

 

 

H.分离

链接：https://ac.nowcoder.com/acm/contest/558/H
来源：牛客网
 

时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 262144K，其他语言524288K
64bit IO Format: %lld

题目描述

小猫在研究字符串。

小猫在研究奇数的性质。

给定一个字符串S，请你输出将其奇数位的字符提出来以后得到的字符串。

输入描述:

第一行一个正整数T，表示数据组数。接下来T行，每行一个字符串S，表示每组数据。

输出描述:

T行，每行一个字符串，表示每组数据的答案。

示例1

输入

复制

2
abcdefg
ababab

输出

复制

aceg
aaa

备注:

1≤T,|S|≤100

签到题

#include<iostream>
#include<cstdio>
using namespace std;

int main(){
    string s;
    int T;
    cin>>T;
    while(T--){
        cin>>s;
        for(int i=0;i<s.size();i+=2)
            cout<<s[i];
        cout<<endl;
    }

	return 0;
}

 

 

 

I.选择

链接：https://ac.nowcoder.com/acm/contest/558/I
来源：牛客网
 

题目描述

小猫在研究序列。小猫在研究选择。

给定一个长度为N的序列a1,a2,…,aN，请你在这N个元素中选出一些（可以不选，可以全选），使得对于任意1≤i<N，ai与ai+1不被同时选，求选出的数的和最大是多少。

输入描述:

第一行一个正整数T，表示数据组数。每组数据的第一行一个正整数N。接下来一行N个正整数a1,a2,…,aN。

输出描述:

T行，每行一个整数，表示每组数据的答案。

示例1

输入

复制

3
5
1 100 101 100 1
4
1 2 3 4
3
51 100 51

输出

复制

200
6
102

备注:

1≤T,N,ai≤100

dp题

dp[i][0]是不取第i件时前i件的最大总和，dp[i][1]是取第i件时前i件的最大总和

转移方程

•             dp[i][0] = max(dp[i-1][1],dp[i-1][0]);
•             dp[i][1] = dp[i-1][0]+a[i];

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;

const int MAX = 105;
int a[MAX],dp[MAX][2];
bool vis[MAX];

int main(){
    int T,n;
    scanf("%d",&T);
    while(T--){
        memset(a,0,sizeof(a));
        memset(vis,0,sizeof(vis));
        scanf("%d",&n);
        for(int i=1;i<=n;i++){
            scanf("%d",&a[i]);
            dp[i][0] = dp[i][1] = 0;
        }

        for(int i=1;i<=n;i++){
            dp[i][0] = max(dp[i-1][1],dp[i-1][0]);
            dp[i][1] = dp[i-1][0]+a[i];
        }

        printf("%d\n",max(dp[n][0],dp[n][1]));
    }

	return 0;
}

 

J.相聚

链接：https://ac.nowcoder.com/acm/contest/558/J
来源：牛客网
 

题目描述

小猫在研究网格图。

小猫在研究联通性。

给定一张N×M的网格图，只含字符0和1，问1形成的联通块有多少个。

两个1是联通的，当且仅当其中一个位于另一个的上、下、左、右四个方向之一。

输入描述:

第一行一个正整数T，表示数据组数。

每组数据的第一行两个正整数N,M，表示矩阵的长和宽。

接下来N行，每行M个字符0或1。

输出描述:

T行，每行一个正整数，表示每组数据的答案。

示例1

输入

复制

2
3 5
10101
01110
10101
3 3
111
010
111

输出

复制

5
1

备注:

1≤T,N,M≤50

简单搜索，求联通块

import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		int T = in.nextInt();
		while(T-->0) {
			n = in.nextInt();
			m = in.nextInt();
			ch = new char[n][m];
			vis = new int[n][m];
			for(int i=0;i<n;i++)
				ch[i] = in.next().toCharArray();
			
			for(int i=0;i<n;i++)
				for(int j=0;j<m;j++) 
					vis[i][j] = 0;
				
			cnt = 0;
			for(int i=0;i<n;i++)
				for(int j=0;j<m;j++)
					if(ch[i][j]=='1' && vis[i][j]==0)
						dfs(i,j,++cnt);
			System.out.println(cnt);
		}
	}

	static int n,m,cnt=0;
	static char[][] ch;
	static int[][] vis;
	static int[] dx = new int[] {1,0,-1,0};
	static int[] dy = new int[] {0,1,0,-1};
	
	static void dfs(int x,int y,int t) {
		vis[x][y] = t;
		
		for(int i=0;i<4;i++) {
			int u = x + dx[i];
			int v = y + dy[i];
			if(u>=0 && u<n && v>=0 && v<m && ch[u][v]=='1' && vis[u][v]==0)
				dfs(u,v,t);
		}
		
		
	}

}