精华内容
下载资源
问答
  • 蓝桥杯 人物相关性分析

    千次阅读 2020-05-12 18:05:00
    这里写自定义目录标题题目:分析:AC代码: 题目: 20 This is a story about Alice and Bob. Alice wants to send a private message to Bob 分析: 字符串长度一百万,肯定不能挨个枚举。 所以,我们可以枚举...

    题目:

    在这里插入图片描述

    20
    This is a story about Alice and Bob. Alice wants to send a private message to Bob

    在这里插入图片描述

    分析:

    字符串长度一百万,肯定不能挨个枚举。
    所以,我们可以枚举区间,
    首先,我们找出所有的Alice放在Alice集合内
    然后,我们找出所有的Bob放在Bob集合内
    最后,我们只需要找出每个人名字前面k的区间内有几个另一个人的名字。
    区间内人名数量的和就是答案!

    为什么只算前面不算后边?

    距离是相互的,A到B的距离等于B到A的距离,如果前后计算就重复了。

    AC代码:

    package JC2019;
     
    import java.util.Scanner;
    import java.util.Vector;
     
    public class H {
    	static boolean check(char C){
    		if ((C>='a'&&C<='z')||(C>='A'&&C<='Z')) {
    			return false;
    		}
    		return true;
    	}
    	public static void main(String[] args) {
    		Vector<Integer> Alice = new Vector<Integer>();
    		Vector<Integer> Bob = new Vector<Integer>();
    		
    		Scanner sc = new Scanner(System.in);
    		int n = sc.nextInt();
    		String s = sc.nextLine();
    		s = sc.nextLine();
    		
    		for (int i = 0; i+5 <= s.length(); i++) {
    			if ((i==0 || check(s.charAt(i-1))) && (i+5==s.length() || check(s.charAt(i+5)))) {
    				if (s.substring(i, i+5).equals("Alice")) {
    					Alice.add(i);
    				}
    			}
    		}
    		for (int i = 0; i+3 <= s.length(); i++) {
    			if ((i==0 || check(s.charAt(i-1))) && (i+3==s.length() || check(s.charAt(i+3)))) {
    				if (s.substring(i, i+3).equals("Bob")) {
    					Bob.add(i);
    				}
    			}
    		}
    		int ans = 0;
    		for (int i = 0; i < Alice.size(); i++) {
    			int l =0,r=-1;
    			while(r+1 < Bob.size() && Alice.get(i) > Bob.get(r+1)  ) {
    				r++;
    			}
    			while (l<=r && Alice.get(i) >Bob.get(l)+n+3  ) {
    				l++;
    			}
    			ans += r-l+1;
    		}
    		
    		for (int i = 0; i < Bob.size(); i++) {
    			int l  =0,r=-1;
    			while(r+1 < Alice.size() && Bob.get(i) > Alice.get(r+1)  ) {
    				r++;
    			}
    			while (l<=r && Bob.get(i) >Alice.get(l)+n+5  ) {
    				l++;
    			}
    			ans += r-l+1;
    		}
    		System.out.println(ans);
    	}
    }
    
    
    展开全文
  • Java实现第十届蓝桥杯人物相关性分析

    万次阅读 多人点赞 2019-07-27 22:18:51
    试题 H: 人物相关性分析 时间限制: 1.0s 内存限制: 512.0MB 本题总分:20 分 【问题描述】 小明正在分析一本小说中的人物相关性。他想知道在小说中 Alice 和 Bob 有多少次同时出现。 更准确的说,小明定义 Alice 和 ...

    试题 H: 人物相关性分析
    时间限制: 1.0s 内存限制: 512.0MB 本题总分:20 分
    【问题描述】
    小明正在分析一本小说中的人物相关性。他想知道在小说中 Alice 和 Bob 有多少次同时出现。 更准确的说,小明定义 Alice 和 Bob“同时出现”的意思是:在小说文本 中 Alice 和 Bob 之间不超过 K 个字符。 例如以下文本: ThisisastoryaboutAliceandBob.AlicewantstosendaprivatemessagetoBob. 假设 K = 20,则 Alice 和 Bob 同时出现了 2 次,分别是”Alice and Bob” 和”Bob. Alice”。前者 Alice 和 Bob 之间有 5 个字符,后者有 2 个字符。 注意: 1. Alice 和 Bob 是大小写敏感的,alice 或 bob 等并不计算在内。 2. Alice 和 Bob 应为单独的单词,前后可以有标点符号和空格,但是不能 有字母。例如 Bobbi 並不算出现了 Bob。
    【输入格式】
    第一行包含一个整数 K。 第二行包含一行字符串,只包含大小写字母、标点符号和空格。长度不超 过 1000000。
    【输出格式】
    输出一个整数,表示 Alice 和 Bob 同时出现的次数。
    【样例输入】
    20 This is a story about Alice and Bob.Alice wants to send aprivate message to Bob.

    这道题最大的坑在于,你直接从PDF中复制下来, 他会没有空格,很多人做的时候会忽视这一点
    import java.util.Scanner;
    
    
    public class renwuxiangguanxing {
    	  public static void main(String[] args)  {
    	        Scanner reader=new Scanner(System.in);
    	        int res=0;    //save result
    	        int K=reader.nextInt();
    	        reader.nextLine();    //nextLine吸取回车键
    	        String str=reader.nextLine();
    	        String words[]=str.split("\\s+|\\.");    //以空格和.分割出来,注意.空格的组合存放为空字符串
    	        
    	        //    Alice------>Bob
    	        for(int i=0;i<words.length;i++){
    	            if(words[i].equals("Alice")){
    	                for(int j=i+1;j<words.length;j++){
    	                    if(words[j].equals("Bob")){
    	                        int sum=1;    //这里要等于1
    	                        for(int k=i+1;k<j;k++){
    	                            sum+=words[k].length()+1;
    	                        }
    	                        if(sum<=K){
    	                            res++;
    	                        }
    	                    }
    	                }
    	            }
    	        }
    	        
    	        //Bob--------->Alice
    	        for(int i=0;i<words.length;i++){
    	            if(words[i].equals("Bob")){
    	                for(int j=i+1;j<words.length;j++){
    	                    if(words[j].equals("Alice")){
    	                        int sum=1;    //这里要等于1
    	                        for(int k=i+1;k<j;k++){
    	                            sum+=words[k].length()+1;
    	                        }
    	                        if(sum<=K){
    	                            res++;
    	                        }
    	                    }
    	                }
    	            }
    	        }
    	        System.out.println(res);
    	    }
    
    }
    
    
    展开全文
  • 用string.find()直接枚举,能拿45分不知道是哪里错误了,如果请大佬指出,如果对string.find的时间复杂度有质疑,请问度娘 #include <bits/stdc++.h> using namespace std; int cnt,k; bool temp = true;...

    用string.find()直接枚举,能拿45分不知道是哪里错误了,如果请大佬指出,如果对string.find的时间复杂度有质疑,请问度娘

    #include <bits/stdc++.h>
    using namespace std;
    int cnt,k;
    bool temp = true;
    char f[2][20] = {"Alice", "Bob"};
    bool check(string &a, int &pa, int &pb)//pa指的是之前Alice出现的位置
    {
        bool flage = true;
        pa = a.find(f[0], ++pa);
        if (pa == -1)
            temp = false;
        if(temp&&abs((pa-1) - pb) < k&&pb)//这里加一条这个就是因为相对位置的关系
        cnt++;
        if (a[pa - 1] != ' ' && a[pa + 6] != ' ')
            flage = false;
        pb = a.find(f[1], ++pb);//++pb是因为不加的话会一直查找同一子串
        if (pb == -1)
            temp = false;
        if (a[pb - 1] != ' ' && a[pb + 6] != ' ')
            flage = false;
        return flage;
    }
    int main()
    {
        string a;
        cin >> k;
        getchar();//吃个回车
        getline(cin, a);//用cin会卡空格,getline就完全没有这些担忧
        int pa = 0, pb = 0;
        while (1)
        {
            if (check(a, pa, pb) && abs(pa - pb) < k && temp)
            {
                cnt++;
            }
            else if (!temp)//如果没查到任意一个我们就直接退出
                break;
        }
        cout << cnt;
        return 0;
    }
    

    下面我决定换个思路用滑动窗口做这题
    这边介绍一下滑动窗口,主要就是用来解决一些满足一定条件的连续区间性质的问题有兴趣的可以自己问问度娘

    #include <bits/stdc++.h>
    using namespace std;
    int len;
    string s;
    bool check(int i)
    {
        if (len - i < 5) return false;
        return s[i + 1] == 'l' && s[i + 2] == 'i' && s[i + 3] == 'c' && s[i + 4] == 'e';
    }
    bool check2(int i)
    {
        if (len - i < 3)
            return false;
        return s[i + 1] == 'o' && s[i + 2] == 'b';
    }
    int main()
    {
        int k;//这里绝对不能加关闭流读入,如果这加了getline会直接读不到
        cin >> k;
        getchar();
        getline(cin, s);
        len = s.length();
        vector<int> Alice, Bob;
        for (int i = 0; i < len; i++)
        {
            if (s[i] == 'A' && check(i))
            {
                Alice.push_back(i);
                i += 5;
            }
            else if (s[i] == 'B' && check2(i))
            {
                Bob.push_back(i);
                i += 3;
            }
        }
        int As = Alice.size(), Bs = Bob.size();
        int i = 0, j = 0;
        long long ans = 0;
        for (int q = 0; q < As; q++)
        {
            while (i < Bs && Bob[i] < Alice[q] - k - 3)
                i++; //左边界已经有些被排除的
            while (j < Bs && Bob[j] <= Alice[q] + k + 5)
                j++; //右边界
            ans += j - i;
        }
        cout << ans << "\n";
        return 0;
    }
    
    展开全文
  • 小明正在分析一本小说中的人物相关性。 他想知道在小说中 Alice 和 Bob 有多少次同时出现。 更准确的说,小明定义 Alice 和 Bob “同时出现”的意思是:在小说文本中 Alice 和 Bob 之间不超过 K 个字符。 例如以下...

    题目描述
    小明正在分析一本小说中的人物相关性。

    他想知道在小说中 AliceBob 有多少次同时出现。

    更准确的说,小明定义 AliceBob “同时出现”的意思是:在小说文本中 AliceBob 之间不超过 K 个字符。

    例如以下文本:

    This is a story about Alice and Bob. Alice wants to send a private message to Bob.

    假设 K = 20,则 AliceBob 同时出现了 2 次,分别是 Alice and BobBob. Alice

    前者 AliceBob 之间有 5 个字符,后者有 2 个字符。

    注意:

    1. AliceBob 是大小写敏感的,alicebob 等并不计算在内。
    2. AliceBob 应为单独的单词,前后可以有标点符号和空格,但是不能有字母。例如 Bobbi 並不算出现了 Bob

    输入格式
    第一行包含一个整数 K。
    第二行包含一行字符串,只包含大小写字母、标点符号和空格,长度不超过 1000000。

    输出格式
    输出一个整数,表示 Alice 和 Bob 同时出现的次数。

    数据范围
    1 ≤ K ≤ 106

    输入样例
    20
    This is a story about Alice and Bob. Alice wants to send a private message to Bob.

    输出样例
    2


    题解
    双指针:

    #include <iostream>
    #include <cstring>
    #include <vector>
    #include <cstdio>
    using namespace std;
    
    vector<int> Alice, Bob;
    
    bool check(char c)
    {
        return c >= 'a' && c <= 'z' || c >= 'A' && c <= 'Z';
    }
    
    int main()
    {
        int k;
        cin >> k;
        
        getchar();
        
        string s;
        getline(cin, s);
        
        for (int i = 0; i < s.size(); i ++)
        {
            if(s[i] == 'A')
            {
                if(s.substr(i, 5) == "Alice")
                    if((i - 1 == -1 || !check(s[i - 1])) && (i + 5 == s.size() || !check(s[i + 5])))
                        Alice.push_back(i);
            }
            else if(s[i] == 'B')
            {
                if(s.substr(i, 3) == "Bob")
                    if((i - 1 == -1 || !check(s[i - 1])) && (i + 3 == s.size() || !check(s[i + 3])))
                        Bob.push_back(i);
            }
        }
        
        long long ans = 0;
        for (int i = 0, L = 0, R = 0; i < Alice.size(); i ++)				// 统计 Alice 前面 Bob 出现了几次
        {
            while(R < Bob.size() && Alice[i] > Bob[R]) R ++;
            while(L < R && Alice[i] - Bob[L] > k + 3) L ++;
            ans += R - L;
        }
        
        for (int i = 0, L = 0, R = 0; i < Bob.size(); i ++)					// 统计 Bob 前面 Alice 出现了几次
        {
            while(R < Alice.size() && Bob[i] > Alice[R]) R ++;
            while(L < R && Bob[i] - Alice[L] > k + 5) L ++;
            ans += R - L;
        }
     
        cout << ans << endl;
        return 0;
    }
    
    展开全文
  • 人物相关性分析 【问题描述】 小明正在分析一本小说中的人物相关性。他想知道在小说中 Alice 和 Bob 有多少次同时出现。 更准确的说,小明定义 Alice 和 Bob“同时出现”的意思是:在小说文本 中 Alice 和 Bob ...
  • 蓝桥杯人物相关性分析 题解: 最容易想到的便是枚举遍历,但由于数量巨大必定会超时。 因此我们可考虑使用双指针来模拟滑动窗口解决该题。 首先我们创建两个数组用双指针查找分别存储出现的Alice和Bob的头部下标...
  • 小明正在分析一本小说中的人物相关性。他想知道在小说中Alice 和Bob 有多少次同时出现。 更准确的说,小明定义Alice 和Bob“同时出现”的意思是:在小说文本 中Alice 和Bob 之间不超过K 个字符。 例如以下文本: ...
  • 【问题描述】小明正在分析一本小说中的人物相关性。他想知道在小说中 Alice 和 Bob有多少次同时出现。更准确的说,小明定义 Alice 和 Bob“同时出现”的意思是:在小说文本中 Alice 和 Bob 之间不超过 K 个字符。...
  • 试题 H: 人物相关性分析 时间限制: 1.0s 内存限制: 512.0MB 本题总分:20 分 【问题描述】 小明正在分析一本小说中的人物相关性。他想知道在小说中 Alice 和 Bob 有多少次同时出现。 更准确的说,小明定义 Alice 和 ...
  • 小明 正在分析一本小说中的人物相关性。他想知道小说中Alice和Bob有多少次同时出现 更准确的说,小明定义Alice和Bob同时出现的意思是,在小说文本你中Alice和Bob之间不超过K个字符 注意 Alice和Bob是大小写敏感的,...
  • 题目描述题目描述小明正在分析一本小说中的人物相关性。他想知道在小说中 Alice 和 Bob 有多少次同时出现。更准确的说,小明定义 Alice 和 Bob“同时出现”的意思是:在小说文本 中 Alice 和 Bob 之间不超过 K 个...
  • Java试题 H: 人物相关性分析 【问题描述】 小明正在分析一本小说中的人物相关性。他想知道在小说中 Alice 和 Bob 有多少次同时出现。 更准确的说,小明定义 Alice 和 Bob“同时出现”的意思是:在小说文本 中 Alice ...
  • 希望以后别人会看到你背后的努力,而不是只会看到你外表所呈现和他自己想象的结果。 #include<iostream> #include<algorithm> #include<cstdio> #include<cmath> ...#
  • 小明正在分析一本小说中的人物相关性。他想知道在小说中 Alice 和 Bob 有多少次同时出现。 更准确的说,小明定义 Alice 和 Bob“同时出现”的意思是: 在小说文本 中 Alice 和 Bob 之间不超过 K 个字符。 例如以下...
  • 试题 H: 人物相关性分析时间限制: 1.0s 内存限制: 512.0MB 本题总分: 20 分【问题描述】小明正在分析一本小说中的人物相关性。他想知道在小说中 Alice 和 Bob有多少次同时出现。更准确的说,小明定义 Alice 和 Bob...
  • 1473: [蓝桥杯2019初赛]人物相关性分析 题目描述 输入 输出 样例输入 20 This is a story about Alice and Bob. Alice wants to send a private message to Bob. 样例输出 2 解题思路 根据字符串特性,...

空空如也

空空如也

1 2 3 4
收藏数 75
精华内容 30
关键字:

蓝桥杯人物相关性分析