Codeforces Round #624 (Div. 3)(题解)
2024-09-03 09:27:08
Codeforces Round #624 (Div.3)
题目地址:https://codeforces.ml/contest/1311
B题:WeirdSort
题意:给出含有n个元素的数组a,和m个元素的数组p,p中元素表示可调换(p=[3,2]表示a中下标为3和下标为3+1的元素可调换,2和2+1可调换),问能否使得原数组成为非降序数组
思路:暴力,模仿冒泡排序
AC代码:
#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
const int maxn = 2e5+;
int main()
{ int T;
cin>>T;
while(T--)
{
int node[];//记录原数组
int f[];//记录可调换下标
int n,m;
cin>>n>>m;
for(int i=;i<=n;i++) cin>>node[i];
for(int i=;i<=m;i++) cin>>f[i]; for(int i=;i<=n;i++)
{ for(int j = ;j<=m;j++)
{
if(node[f[j]]>node[f[j]+])//如果前边的大于后面的则调换
swap(node[f[j]],node[f[j]+]);
}
}
// 所有可调换位置均以成为非递减
if(is_sorted(node+,node++n)) // 判断是否和升序排序后的数组相同
puts("YES");
else
puts("NO");
}
return ;
}
C题:Perform the Combo
题意:判断字母出现次数,给定字符串,和m个数记录在数组中,记录字母出现次数时每次从第1位开始,直到数组中所给数又重新开始记录,最后在从第一位到最后一位记录一遍,输出每个字母出现的次数
思路:如果按照题意一一模拟遍历发现会超时,因为所给数组中的数可能相同,多次做相同遍历,浪费时间 可以用前缀和 * 相同数字出现次数
AC代码:
#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
const int maxn = 2e5+;
int main()
{ int T;
cin>>T;
while(T--)
{
int n,m;
string s;
int ans[]={};//每个字母出现次数
int sum[]={};//前缀和
int node[maxn]={};
cin>>n>>m>>s;
for(int i=;i<m;i++)
{
int t;
cin>>t;
node[t]++;//记录每个数的出现次数
} for(int i=;i<s.length();i++)
{
ans[s[i]-'a']++;
sum[s[i]-'a']++;
if(node[i+])//node中数是从1开始的而ans的下标是从0开始的
{
for(int j=;j<;j++)
{
ans[j]+= sum[j]*node[i+];
}
}
} for(int i=;i<;i++)
{
cout<<ans[i];
if(i!=) cout<<" ";
}
puts("");
}
return ;
}
最新文章
- 【tornado】系列项目(二)基于领域驱动模型的区域后台管理+前端easyui实现
- SQL Server:数据库角色
- metinfo首页内容简介
- vs 2012 InstallShield Limited Edition Project 打包windows服务解析
- JS 排序算法
- 基于Jws的WebService项目
- C#加密算法汇总(转载)http://www.cnblogs.com/zengxiangzhan/archive/2010/01/30/1659687.html
- mongoDB global,startUplog
- HDU 5170 GTY&#39;s math problem
- DotNetCore跨平台~一起聊聊Microsoft.Extensions.DependencyInjection
- win7与centos虚拟机的共享文件夹创建
- Ubuntu 14.10下基于Nginx搭建mp4/flv流媒体服务器(可随意拖动)并支持RTMP/HLS协议(含转码工具)
- Django---ORM框架
- UVA11212-Editing a Book(迭代加深搜索)
- python 07
- .NET DLL 加密工具
- xdoj-1319 求树上任意一点的最大距离----利用树的直径
- C#使用WebService
- MongoTemplate基本操作
- vs code 写C#心得