当前位置: 首页 > news >正文

深圳网站建设怎么样旅游建设投资公司网站

深圳网站建设怎么样,旅游建设投资公司网站,上海松江区做网站的公司,花钱想贷款结果成了做网站题面翻译 题面描述 FJ 有 NNN 头奶牛,每一头奶牛的品种是根西岛 G 或荷斯坦 H 中的一种。 每一头奶牛都有一个名单,第 iii 头奶牛的名单上记录了从第 iii 头奶牛到第 EiE_iEi​ 头奶牛的所有奶牛。 每一种奶牛都有且仅有一位“领导者”,对…

题面翻译

题面描述

FJ 有 NNN 头奶牛,每一头奶牛的品种是根西岛 G 或荷斯坦 H 中的一种。

每一头奶牛都有一个名单,第 iii 头奶牛的名单上记录了从第 iii 头奶牛到第 EiE_iEi 头奶牛的所有奶牛。

每一种奶牛都有且仅有一位“领导者”,对于某一头牛 iii,如果它能成为“领导者”仅当它满足以下条件的至少一个

  • 其记录的名单上包含它的品种的所有奶牛。

  • 其记录的名单上记录了另一品种奶牛的“领导者”。

请求出有多少对奶牛可能成为两种奶牛的领导者,保证存在至少一种。

数据范围

对于 100%100\%100% 的数据:1≤N≤2×105,i≤Ei≤N1\leq N\leq 2\times 10^5,i\leq E_i\leq N1N2×105,iEiN

题目描述

Farmer John has NNN cows (2≤N≤105)(2 \le N \le 10^5)(2N105). Each cow has a breed that is either Guernsey or Holstein. As is often the case, the cows are standing in a line, numbered 1⋯N1 \cdots N1N in this order.

Over the course of the day, each cow writes down a list of cows. Specifically, cow iii
's list contains the range of cows starting with herself (cow iii) up to and including cow Ei(i≤Ei≤N)E_i(i \le E_i \le N)Ei(iEiN).

FJ has recently discovered that each breed of cow has exactly one distinct leader. FJ does not know who the leaders are, but he knows that each leader must have a list that includes all the cows of their breed, or the other breed’s leader (or both).

Help FJ count the number of pairs of cows that could be leaders. It is guaranteed that there is at least one possible pair.

输入格式

The first line contains NNN.

The second line contains a string of length NNN
, with the ith character denoting the breed of the iii-th cow (G meaning Guernsey and H meaning Holstein). It is guaranteed that there is at least one Guernsey and one Holstein.

The third line contains E1⋯ENE_1 \cdots E_NE1EN.

输出格式

Output the number of possible pairs of leaders.

样例 #1

样例输入 #1

4
GHHG
2 4 3 4

样例输出 #1

1

样例 #2

样例输入 #2

3
GGH
2 3 3

样例输出 #2

2

提示

Explanation for Sample 1

The only valid leader pair is (1,2)(1,2)(1,2). Cow 111’s list contains the other breed’s leader (cow 222). Cow 222’s list contains all cows of her breed (Holstein).

No other pairs are valid. For example, (2,4)(2,4)(2,4)
is invalid since cow 444’s list does not contain the other breed’s leader, and it also does not contain all cows of her breed.

Explanation for Sample 2

There are two valid leader pairs, (1,3)(1,3)(1,3) and (2,3)(2,3)(2,3).

Scoring

  • Inputs 3−53-535: N≤100N \le 100N100
  • Inputs 6−106-10610: N≤3000N \le 3000N3000
  • Inputs 11−1711-171117: N≤2×105N \le 2 \times 10^5N2×105

算法思想

本题核心就是分别求G和H的领导者个数,然后相乘得到最后答案。例如#2测试样例,G的领导者有两个,H的领导者有1个,那么他们的组合就有两对。

对于某一头牛来说,如果它能成为“领导者”仅当它满足以上述两个条件的至少一个。由于第二个条件依赖于第一个条件,因此我们可以先求出满足第一个条件的领导者。

暴力枚举(50分)

朴素做法就是两层循环,第一层循环枚举每一头奶牛iii,第二层循环枚举i到a[i]a[i]a[i],计算其本身品种的奶牛头数,判断其名单上是否记录了它的品种的所有奶牛。如果满足条件,就将第i头奶牛进行标记。

然后再标记第二种情况的领导者,也是两层循环,第一层循环枚举每一头奶牛iii,第二层循环枚举i到a[i]a[i]a[i],判断这之间是否存在另一种奶牛的领导者,如果存在则标记。

最后统计两种奶牛领导者的数量,将其相乘就是最终答案

时间复杂度

时间复杂度为O(n2)O(n^2)O(n2)

代码实现

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 2e5 + 10;
char s[N];
int a[N], g[N], h[N];
int main()
{int n;cin >> n;cin >> s + 1;int s1 = 0, s2 = 0;for(int i = 1; i <= n; i ++){if(s[i] == 'G') s1 ++;else s2 ++;}for(int i = 1; i <= n; i ++) cin >> a[i];//处理第一种领导者:其记录的名单上包含它的品种的所有奶牛for(int i = 1; i <= n; i ++){int gg = 0, hh = 0;for(int j = i; j <= a[i]; j ++){if(s[j] == 'G') gg ++;else hh ++;}if(s[i] == 'G' && gg == s1) g[i] = 1; //标记为领导者else if(s[i] == 'H' && hh == s2) h[i] = 1; //标记为领导者}//处理第二种领导者:其记录的名单上记录了另一品种奶牛的“领导者”。for(int i = 1; i <= n; i ++){for(int j = i; j <= a[i]; j ++){if(s[i] == 'G' && h[j] == 1){g[i] = 1;break;}else if(s[i] == 'H' && g[j] == 1){h[i] = 1;break;}}}int c1 = 0, c2 = 0;for(int i = 1; i <= n; i ++)if(g[i]) c1 ++;for(int i = 1; i <= n; i ++)if(h[i]) c2 ++;cout << c1 * c2 << endl;
}

前缀和优化(100分)

朴素做法的问题在于使用了两层循环,其实第二层循环可以使用前缀和进行优化,用空间换时间。

  • s1[]前缀和数组,s1[i]表示前i个字符中字符G的个数
  • s2[]前缀和数组,s2[i]表示前i个字符中字符H的个数
  • gs[]前缀和数组,gs[i]表示前i头牛中第一类G品种领导者的数量
  • hs[]前缀和数组,hs[i]表示前i头牛中第一类H品种领导者的数量

时间复杂度

朴素做法的时间复杂度为O(n)O(n)O(n)

代码实现

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 2e5 + 10;
char s[N];
int e[N], s1[N], s2[N], g[N], h[N], gs[N], hs[N];
int main()
{int n;cin >> n;cin >> s + 1;for(int i = 1; i <= n; i ++) cin >> e[i];//s1[i]前缀和, 表示前i个字符中字符G的个数//s2[i]前缀和, 表示前i个字符中字符H的个数for(int i = 1; i <= n; i ++){s1[i] = s1[i - 1], s2[i] = s2[i - 1];if(s[i] == 'G') s1[i] ++;else s2[i] ++;}//处理第一种领导者:其记录的名单上包含本身的品种的所有奶牛for(int i = 1; i <= n; i ++){//gg表示从i到e[i]位置所有G的个数//hh表示从i到e[i]位置所有H的个数int gg = s1[e[i]] - s1[i - 1], hh = s2[e[i]] - s2[i - 1];//其记录的名单上包含本身的品种的所有奶牛if(s[i] == 'G' && gg == s1[n]) g[i] = 1; //将i位置标记为'G'的领导者else if(s[i] == 'H' && hh == s2[n]) h[i] = 1;//将i位置标记为'H'的领导者}//gs[i]前缀和,表示前i个奶牛中G的第一种领导者个数//hs[i]前缀和,表示前i个奶牛中H的第一种领导者个数for(int i = 1; i <= n; i ++){gs[i] = gs[i - 1], hs[i] = hs[i - 1];if(g[i]) gs[i] ++;if(h[i]) hs[i] ++;}//ga表示G的第一种领导者个数,ha表示H的第一种领导者个数int ga = gs[n], ha = hs[n];//处理第二种领导者:其记录的名单上记录了另一品种奶牛的“领导者”。for(int i = 1; i <= n; i ++){  //其记录的名单上记录了另一品种奶牛的领导者if(s[i] == 'G' && (hs[e[i]] - hs[i - 1]) != 0) ga ++;else if(s[i] == 'H' && (gs[e[i]] - gs[i - 1]) != 0) ha ++;}cout << ga * ha << endl;
}
http://www.yayakq.cn/news/806392/

相关文章:

  • 网站友情链接交易平台网站前台后台模板
  • wordpress动静分离七牛太原seo培训
  • 有一个网站 人物模型可以做各种动作新兴县城乡建设局网站
  • 做a 免费网站原墨网站建设
  • 购买天猫店铺网站深圳做微商网站制作
  • 为传销做网站铜川矿业公司网站
  • 密山网站金蝶软件怎么打印凭证
  • 广州网站建设公司有哪些网络营销策划师
  • 建设个人网页登陆网站天津做胎儿鉴定网站
  • thinkphp微网站开发wordpress 知识 管理系统
  • 常州微信网站建设咨询北京网站建设问问q778925409霸屏
  • 佛山外贸网站建设渠道优势的seo网站优化排名
  • 建立网站需要多少钱多少钱28湖南岚鸿wordpress仿搞笑
  • 厦门成交型网站建设公司广州网络营销产品代理
  • 如何仿造一个网站做专业的网站建站公司
  • 顺义区网站建设wordpress修改文章默认排序
  • 网站公司建设石家庄建设银行营业网点
  • 一个主机可以做几个网站安徽津城建设工程有限公司网站
  • 手机模板网站生成制作软件怎么搭建个人网站电脑做服务器
  • 怎么做网站xml地图动态电商网站怎么做
  • 深圳三站合一网站建设建筑公司网站设计模板
  • 网站建设读书笔记温州 网站 公司
  • 学校加强网站建设买微单的网站建设
  • 广州网站注销备案公司网络推广怎么做
  • nas 可以做网站吗商标怎么设计才好看
  • 网站模板代码怎么写免费网站域名cn
  • 广告宣传页怎么制作公司搜索seo
  • 陕西交通建设集团西商分公司网站微信api接口
  • 建筑工程类网站齐齐哈尔做网站公司
  • 营销型网站的价格东莞常平牙科