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 ;
}

最新文章

  1. 【tornado】系列项目(二)基于领域驱动模型的区域后台管理+前端easyui实现
  2. SQL Server:数据库角色
  3. metinfo首页内容简介
  4. vs 2012 InstallShield Limited Edition Project 打包windows服务解析
  5. JS 排序算法
  6. 基于Jws的WebService项目
  7. C#加密算法汇总(转载)http://www.cnblogs.com/zengxiangzhan/archive/2010/01/30/1659687.html
  8. mongoDB global,startUplog
  9. HDU 5170 GTY&#39;s math problem
  10. DotNetCore跨平台~一起聊聊Microsoft.Extensions.DependencyInjection
  11. win7与centos虚拟机的共享文件夹创建
  12. Ubuntu 14.10下基于Nginx搭建mp4/flv流媒体服务器(可随意拖动)并支持RTMP/HLS协议(含转码工具)
  13. Django---ORM框架
  14. UVA11212-Editing a Book(迭代加深搜索)
  15. python 07
  16. .NET DLL 加密工具
  17. xdoj-1319 求树上任意一点的最大距离----利用树的直径
  18. C#使用WebService
  19. MongoTemplate基本操作
  20. vs code 写C#心得

热门文章

  1. EBCDIK,EBCDIC,ASCII,shift JIS間の変換
  2. PXE无人值守实现批量化自动安装Linux系统
  3. Failed to read candidate component class
  4. GlusterFS分布式文件系统概述
  5. 一文解读IBMS (转)
  6. Oracle忘记密码怎么办?
  7. unittest中的parameterized参数化
  8. 无线渗透之ettercap
  9. 找出crontab表达式内符合的下一次出发时间点(经典!!!)
  10. WDF驱动中KMDF与UMDF区别