CSDN竞赛第33期（个人解答）

1、题目名称：奇偶排序

给定一个存放整数的数组，重新排列数组使得数组左边为奇数，右边为偶数。（奇数和偶数的顺序根据输入的数字顺序排列）

#include <stdio.h>
#include <stdlib.h>

void solution(int n, int arr[]){
// TODO: 请在此编写代码
	int temp[n];
	int i, j, k;
	for(i=0, j=0; i<n; i++){
		if(arr[i]%2!=0){
			temp[j++]=arr[i];
		}
	}
	for(i=0, k=0; i<n; i++){
		if(arr[i]%2==0){
			temp[j++]=arr[i];
		}
	}
	for(i=0; i<n; i++){
		printf("%d ", temp[i]);
	}
}

int main() {
	int n;
	scanf("%d", &n);
	int *arr;
	arr = (int*)malloc(n*sizeof(int));
	for (int i = 0; i < n; i++){
		scanf("%d", &arr[i]);
	}
	solution(n, arr);
	return 0;
}

2、题目名称：小艺改编字符串

已知字符串str. 添加至少多少字符可以使得str变成回文串。

#include <iostream>
#include <string>
#include <sstream>
#include <vector>
#include <cstring>
using namespace std;

int temp[1005][1005];
int solution(std::string s){
	int result;
	// TODO:
	memset(temp, 0x3f, sizeof temp);
	int n=s.size();
	int i, j, k;
	for(i=0; i<n; i++)
		temp[i][i]=0;
	for(j=1; j<n; j++)
		temp[j][j-1]=0;
	for(k=2; k<=n; k++){
		for(i=0; i<n; i++){
			j=i+k-1;
			if(j>n)
				continue;
			if(s[i]==s[j])
				temp[i][j]=min(temp[i][j], temp[i+1][j-1]);
			else
				temp[i][j]=min(temp[i][j-1], temp[i+1][j])+1;
		}
	}
	result=temp[0][n-1];
	return result;
}

int main() {
	std::string s;
	getline(std::cin, s);;
	int result = solution(s);
	std::cout<<result<<std::endl;
	return 0;
}

3、题目名称：公司新表

公司里为了凸显公司的特性。 安装了一个n进制表。 已知新的表的时间是”H:M”。 时间合法的定义为H<=23 && M<=59。 时间有多少种进制定义的方式，依次打印出来。 如果有无数种解输出”-1”，不存在输出”0”。

#include <iostream>
#include <string>
#include <sstream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;

int cton(char c){
	if(c>='0'&&c<='9')
		return c-'0';
	else
		return c-'A'+10;
}

std::vector<int> solution(std::string m){
	std::vector<int> result;
	// TODO:
	int temp=0;
	int len=m.size();
	int i, j, k, num;
	for(i=0; i<len; i++){
		if(m[i]==':')
			continue;
		temp=max(temp, cton(m[i]));
	}
	for(i=temp+1; i<=60; i++){
		int b[2]={0, 0};
		k=0;
		for(j=0; j<len; j++){
			if(m[j]==':'){
				k++;
				continue;
			}
			num=cton(m[j]);
			b[k]=b[k]*i+num;
		}
		if(b[0]>=24||b[1]>=60)
			break;
		else
			result.push_back(i);
	}
	if(!result.size()){
		return {0};
	}
	else if(result.back()==60)
		return {-1};
	return result;
}

int main() {
	std::string m;
	getline(std::cin, m);;
	std::vector<int> result = solution(m);
	for(auto it=result.begin();it!=result.end();++it){
		std::cout<<*it<<" ";
	}
	std::cout<<std::endl;
	return 0;
}

4、题目名称：选择客栈

丽江河边有 n 家很有特色的客栈，客栈按照其位置顺序从 1 到 n 编号。每家客栈都按照某一种色调进行装饰（总共 k种，用整数 0 ~ k-1 表示），且每家客栈都设有一家咖啡店，每家咖啡店均有各自的最低消费。 两位游客一起去丽江旅游，他们喜欢相同的色调，又想尝试两个不同的客栈，因此决定分别住在色调相同的两家客栈中。晚上，他们打算选择一家咖啡店喝咖啡，要求咖啡店位于两人住的两家客栈之间（包括他们住的客栈），且咖啡店的最低消费不超过 p 。 他们想知道总共有多少种选择住宿的方案，保证晚上可以找到一家最低消费不超过 p 元的咖啡店小聚。

#include <stdio.h>
#include <stdlib.h>

int t[500];
void solution(int n, int k, int p, int arr[][2]){
	// TODO: 请在此编写代码
	int ans=0;
	int i;
	for(i=0; i<n; i++){
		t[arr[i][0]]++;
	}
	for(i=0; i<n-1; i++){
		t[arr[i][0]]--;
		int x=t[arr[i][0]];
		if(arr[i][1]<=p){
			ans+=t[arr[i][0]];
			continue;
		}
		int cheap=0;
		int j;
		for(j=i+1; j<n; j++){
			if(arr[j][1]<=p)
				cheap=1;
			if(arr[j][0]!=arr[i][0]||j==i)
				continue;
			if(!cheap){
				t[arr[i][0]]--;
				continue;
			}
			ans+=t[arr[i][0]];
			t[arr[i][0]]=x;
			break;
		}
	}
	printf("%d\n", ans);
}

int main() {
	int temp_arr[3];
	for (int i = 0; i < 3; i++){
		scanf("%d", &temp_arr[i]);
	}
	int n = temp_arr[0];
	int k = temp_arr[1];
	int p = temp_arr[2];
	int (*arr)[2];
	arr = (int(*)[2])malloc(n * sizeof(int*));
	for(int i = 0; i < n; i++) {
		for(int j = 0; j < 2; j++) {
			scanf("%d", &arr[i][j]);
		}
	}
	solution(n, k, p, arr);
	return 0;
}