CSDN竞赛第33期题解

CSDN竞赛第33期题解

1、题目名称：奇偶排序

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

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int N=1e3+5,M=2e4+5,inf=0x3f3f3f3f,mod=1e9+7;
const int hashmod[4] = {402653189,805306457,1610612741,998244353};
#define mst(a,b) memset(a,b,sizeof a)
#define db double
#define PII pair<int,int>
#define PLL pair<ll,ll>
#define x first
#define y second
#define pb emplace_back
#define SZ(a) (int)a.size()
#define all(a) a.begin(),a.end()
#define VI vector<int>
#define rep(i,a,b) for(int i=a;i<=b;++i)
#define per(i,a,b) for(int i=a;i>=b;--i)
#define IOS ios::sync_with_stdio(false),cin.tie(nullptr)
void Print(int *a,int n){
for(int i=1;i<n;i++)
printf("%d ",a[i]);
printf("%d\n",a[n]);
}
template <typename T> //x=max(x,y) x=min(x,y)
void cmx(T &x,T y){
if(x<y) x=y;
}
template <typename T>
void cmn(T &x,T y){
if(x>y) x=y;
}
int main(){
vector<int>a,b;
int n;cin>>n;
rep(i,1,n){
int x;cin>>x;
if(x&1) a.pb(x);
else b.pb(x);
}
for(auto x:a) printf("%d ",x);
for(auto x:b) printf("%d ",x);
puts("");
return 0;
}

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

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

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int N=1e3+5,M=2e4+5,inf=0x3f3f3f3f,mod=1e9+7;
const int hashmod[4] = {402653189,805306457,1610612741,998244353};
#define mst(a,b) memset(a,b,sizeof a)
#define db double
#define PII pair<int,int>
#define PLL pair<ll,ll>
#define x first
#define y second
#define pb emplace_back
#define SZ(a) (int)a.size()
#define all(a) a.begin(),a.end()
#define VI vector<int>
#define rep(i,a,b) for(int i=a;i<=b;++i)
#define per(i,a,b) for(int i=a;i>=b;--i)
#define IOS ios::sync_with_stdio(false),cin.tie(nullptr)
void Print(int *a,int n){
for(int i=1;i<n;i++)
printf("%d ",a[i]);
printf("%d\n",a[n]);
}
template <typename T> //x=max(x,y) x=min(x,y)
void cmx(T &x,T y){
if(x<y) x=y;
}
template <typename T>
void cmn(T &x,T y){
if(x>y) x=y;
}
ll ksm(ll a,ll n,ll m=mod){
ll ans=1;
while(n){
if(n&1) ans=ans*a%m;
a=a*a%m;
n>>=1;
}
return ans;
}
struct BIT{
#define lowbit(x) x&(-x)
#define il inline
ll s[N];
int n;
il void upd(int x,int v){
while(x<=n){
s[x]+=v;x+=lowbit(x);
}return;
}
il ll que(int x){
ll ans=0;
while(x){
ans+=s[x];x-=lowbit(x);
}return ans;
}
}T;
int fun(string s) {
int n = s.size();
string t(s.rbegin(), s.rend());
vector<vector<int>> f(n + 1, vector<int>(n + 1));
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= n; ++j) {
f[i][j] = max(f[i - 1][j], f[i][j - 1]);
if (s[i - 1] == t[j - 1]) {
f[i][j] = max(f[i][j], f[i - 1][j - 1] + 1);
}
}
}
return n - f[n][n];
}
int main(){
string s;
cin>>s;
cout<<fun(s);
return 0;
}

3、题目名称：公司新表

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

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int N=1e3+5,M=2e4+5,inf=0x3f3f3f3f,mod=1e9+7;
const int hashmod[4] = {402653189,805306457,1610612741,998244353};
#define mst(a,VV) memset(a,VV,sizeof a)
#define db double
#define PII pair<int,int>
#define PLL pair<ll,ll>
#define x first
#define y second
#define pb emplace_back
#define SZ(a) (int)a.size()
#define all(a) a.begin(),a.end()
#define VI vector<int>
#define rep(i,a,VV) for(int i=a;i<=VV;++i)
#define per(i,a,VV) for(int i=a;i>=VV;--i)
#define IOS ios::sync_with_stdio(false),cin.tie(nullptr)
void Print(int *a,int n){
for(int i=1;i<n;i++)
printf("%d ",a[i]);
printf("%d\n",a[n]);
}
template <typename T> //x=max(x,y) x=min(x,y)
void cmx(T &x,T y){
if(x<y) x=y;
}
template <typename T>
void cmn(T &x,T y){
if(x>y) x=y;
}
int get(char c) {
if (c >= '0' && c <= '9') return c - '0';
else return c - 'A' + 10;
}
ll ksm(ll a,ll n,ll s=mod){
ll ans=1;
while(n){
if(n&1) ans=ans*a%s;
a=a*a%s;
n>>=1;
}
return ans;
}
struct BIT{
#define lowbit(x) x&(-x)
#define il inline
ll s[N];
int n;
il void upd(int x,int v){
while(x<=n){
s[x]+=v;x+=lowbit(x);
}return;
}
il ll que(int x){
ll ans=0;
while(x){
ans+=s[x];x-=lowbit(x);
}return ans;
}
}T;
vector<int> fun(string s) {
vector<int> vec;
int t = 0;
int n = s.size();
for(int i = 0; i < n; i++) {
if(s[i] == ':') continue;
t = max(t, get(s[i]));
}
for(int i = t + 1; i <= 60; i++) {
int VV[2] = {0, 0};
int pos = 0;
for(int j = 0;j < n;j++) {
if(s[j] == ':') {
pos++;
continue;
}
int q = get(s[j]);
VV[pos] = VV[pos] * i + q;
}
if(VV[0] >= 24 || VV[1] >= 60) break;
else vec.push_back(i);
}
if (!vec.size()) {
return {0};
} else if(vec.back() == 60) return {-1};
return vec;
}
int main() {
std::string s;
getline(cin, s);;
vector<int> ans = fun(s);
for(auto it=ans.begin(); it!=ans.end(); ++it) {
cout<<*it<<" ";
}
puts("");
return 0;
}

4、题目名称：选择客栈

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

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int N=2e5+5,M=2e4+5,inf=0x3f3f3f3f,mod=1e9+7;
const int hashmod[4] = {402653189,805306457,1610612741,998244353};
#define mst(a,b) memset(a,b,sizeof a)
#define db double
#define PII pair<int,int>
#define PLL pair<ll,ll>
#define x first
#define y second
#define pb emplace_back
#define SZ(a) (int)a.size()
#define all(a) a.begin(),a.end()
#define VI vector<int>
#define rep(i,a,b) for(int i=a;i<=b;++i)
#define per(i,a,b) for(int i=a;i>=b;--i)
#define IOS ios::sync_with_stdio(false),cin.tie(nullptr)
void Print(int *a,int n){
for(int i=1;i<n;i++)
printf("%d ",a[i]);
printf("%d\n",a[n]);
}
template <typename T> //x=max(x,y) x=min(x,y)
void cmx(T &x,T y){
if(x<y) x=y;
}
template <typename T>
void cmn(T &x,T y){
if(x>y) x=y;
}
int n,k,p,b[N],m[N];
int ok,cost[60][N],value[60],L,R,MM;
ll res;
ll ksm(ll a,ll n,ll m=mod){
ll ans=1;
while(n){
if(n&1) ans=ans*a%m;
a=a*a%m;
n>>=1;
}
return ans;
}
struct BIT{
#define lowbit(x) x&(-x)
#define il inline
ll s[N];
int n;
il void upd(int x,int v){
while(x<=n){
s[x]+=v;x+=lowbit(x);
}return;
}
il ll que(int x){
ll ans=0;
while(x){
ans+=s[x];x-=lowbit(x);
}return ans;
}
}T;
int main()
{
scanf("%d%d%d",&n,&k,&p);
for (int i=1;i<=n;i++)
scanf("%d%d",&b[i],&m[i]);
ok=-1;
for (int i=1;i<=n;i++)
{
if (m[i]<=p) res+=(ll)value[b[i]];
else
{
L=1;
R=value[b[i]];
while (L<=R)
{
MM=(L+R)/2;
if (ok>=cost[b[i]][MM]) L=MM+1;
else R=MM-1;
}
res+=(ll)(L-1);
}
value[b[i]]++;
cost[b[i]][value[b[i]]]=i;
if (m[i]<=p) ok=i;
}
cout<<res;
return 0;
}