鱼C论坛

 找回密码
 立即注册
查看: 2480|回复: 9

[已解决]USACO2023.1铜级的第一道问题

[复制链接]
发表于 2023-1-30 09:12:00 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能^_^

您需要 登录 才可以下载或查看,没有账号?立即注册

x
题目如下:
农夫John有N头奶牛(2≤N≤105)。每头牛都有一个品种,不是根西岛就是荷斯坦岛。通常情况下,牛站成一排,按顺序从1到N编号。
在一天的过程中,每头奶牛都写下一份奶牛名单。具体来说,奶牛i的列表包含了从她自己(奶牛i)开始到并包括奶牛Ei (i≤Ei≤N)的奶牛的范围。
FJ最近发现每个品种的牛都有一个不同的领导者。FJ不知道领导者是谁,但他知道每个领导者必须有一个列表,包括他们品种的所有奶牛,或其他品种的领导者(或两者都有)。
帮助FJ计算可以成为领导者的奶牛对数。它保证至少有一个可能的对。
输入格式(输入从终端/ stdin到达):
第一行包含N。
第二行包含一个长度为N的字符串,第i个字符表示第i头奶牛的品种(G表示根西岛,H表示荷斯坦)。可以保证至少有一个根西岛和一个荷尔斯泰因岛。
第三行包含E1…EN。
输出格式(打印输出到终端/ stdout):
输出可能的领导对的数目。
样例输入:
4
GHHG
2 4 3 4
样例输出:
1
唯一有效的领导者对(1,2)。牛1的列表包含了其他品种的领导者(牛2)。牛2的列表包含了她的品种(荷斯坦)的所有奶牛。
没有其他对是有效的。例如,(2,4)无效,因为奶牛4的列表不包含其他品种的领导者,也不包含该品种的所有奶牛。
样例输入:
3
GGH
2 3 3
样例输出:
2
有两个有效的领导者对(1,3)和(2,3)。
得分

输入3 ~ 5:N≤100

输入6 ~ 10:N≤3000

输入11-17:无附加约束。
请会给个解法,谢谢。
最佳答案
2023-2-26 19:59:14
#include<bits/stdc++.h>
using namespace std;

const int maxn=1e5+10;
int n,k;
char s[maxn];
int e[maxn],is[maxn],ans[maxn];
int cnt[maxn][2],a[maxn][2];//记录字符串情况
int main(){
        scanf("%d",&n);                                                                
        scanf("%s",s+1);
        for(int i=1;i<=n;i++)scanf("%d",&e[i]);                                        //b
        for(int i=1;i<=n;i++){
                //printf("%c ",s[i]);
                if(s[i]=='G')cnt[i][0]++;
                else cnt[i][1]++;
        }
        //for(int i=1;i<=n;i++)printf("cnt = %d %d\n",cnt[i][0],cnt[i][1]);
        for(int i=1;i<=n;i++){
                a[i][0]=a[i-1][0]+cnt[i][0];
                a[i][1]=a[i-1][1]+cnt[i][1];
        }
        //for(int i=1;i<=n;i++)printf("a = %d %d\n",a[i][0],a[i][1]);
        for(int i=1;i<=n;i++){
                int l=0;
                if(s[i]=='H')l=1;
                if(a[e[i]][l]-a[i-1][l]==a[n][l])is[i]=1;
        }
        //for(int i=1;i<=n;i++)printf("is = %d\n",is[i]);
        for(int i=1;i<=n;i++)ans[i]=ans[i-1]+is[i];
        //for(int i=1;i<=n;i++)printf("ans = %d\n",ans[i]);
        for(int i=1;i<=n;i++)k=k+ans[e[i]]-ans[i];
        k=k+ans[n]*(ans[n]-1)/2;
        printf("%d\n",k);
        return 0;
}
如果答案对您有帮助,请设置最佳答案!
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

头像被屏蔽
发表于 2023-1-30 10:54:18 | 显示全部楼层
提示: 作者被禁止或删除 内容自动屏蔽
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

 楼主| 发表于 2023-1-30 11:30:36 | 显示全部楼层
你要发直发
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

头像被屏蔽
发表于 2023-1-30 14:29:14 | 显示全部楼层
提示: 作者被禁止或删除 内容自动屏蔽
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

 楼主| 发表于 2023-1-30 14:41:00 | 显示全部楼层
考完了
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

 楼主| 发表于 2023-1-30 14:41:30 | 显示全部楼层
就这道不会
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

 楼主| 发表于 2023-1-30 14:50:17 | 显示全部楼层
所以才来问问
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

 楼主| 发表于 2023-1-30 16:25:52 | 显示全部楼层
学习编程的采集 发表于 2023-1-30 14:29
你很可疑?你是不是还没考呢?

考完了,就这道不会,
所以才来问问
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2023-2-2 08:35:12 | 显示全部楼层
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2023-2-26 19:59:14 | 显示全部楼层    本楼为最佳答案   
#include<bits/stdc++.h>
using namespace std;

const int maxn=1e5+10;
int n,k;
char s[maxn];
int e[maxn],is[maxn],ans[maxn];
int cnt[maxn][2],a[maxn][2];//记录字符串情况
int main(){
        scanf("%d",&n);                                                                
        scanf("%s",s+1);
        for(int i=1;i<=n;i++)scanf("%d",&e[i]);                                        //b
        for(int i=1;i<=n;i++){
                //printf("%c ",s[i]);
                if(s[i]=='G')cnt[i][0]++;
                else cnt[i][1]++;
        }
        //for(int i=1;i<=n;i++)printf("cnt = %d %d\n",cnt[i][0],cnt[i][1]);
        for(int i=1;i<=n;i++){
                a[i][0]=a[i-1][0]+cnt[i][0];
                a[i][1]=a[i-1][1]+cnt[i][1];
        }
        //for(int i=1;i<=n;i++)printf("a = %d %d\n",a[i][0],a[i][1]);
        for(int i=1;i<=n;i++){
                int l=0;
                if(s[i]=='H')l=1;
                if(a[e[i]][l]-a[i-1][l]==a[n][l])is[i]=1;
        }
        //for(int i=1;i<=n;i++)printf("is = %d\n",is[i]);
        for(int i=1;i<=n;i++)ans[i]=ans[i-1]+is[i];
        //for(int i=1;i<=n;i++)printf("ans = %d\n",ans[i]);
        for(int i=1;i<=n;i++)k=k+ans[e[i]]-ans[i];
        k=k+ans[n]*(ans[n]-1)/2;
        printf("%d\n",k);
        return 0;
}
如果答案对您有帮助,请设置最佳答案!
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

小黑屋|手机版|Archiver|鱼C工作室 ( 粤ICP备18085999号-1 | 粤公网安备 44051102000585号)

GMT+8, 2024-12-25 12:38

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

快速回复 返回顶部 返回列表