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

pat练习

news 来源：原创 2024/5/3 21:13:27

1093 Count Pats
这题也是我看了很久一直拖着不想写的题 那就一边写片博客一边写这题把，记录一下虽然我不会看我自己写的东西，太恶心了简直是一坨狗屎
The string APPAPT contains two PAT’s as substrings. The first one is formed by the 2nd, the 4th, and the 6th characters, and the second one is formed by the 3rd, the 4th, and the 6th characters.
Now given any string, you are supposed to tell the number of PAT’s contained in the string
1. The string AppApt contains two pat as substrings
2. 猜测一下大概要用到动态规划
3. 而且数字很可能过于巨大需要取模

     第一个朴素的想法是 从后往前找到第一个t，从t的位置从后往前找到第一个A ， 从A 扫描到0 有x个p

将x返回 时间要求高，估计只能使用C++
但是这样肯定不行， 能用到前缀和的思想吗
A 的前面有多少个p，t的前面有多少个p和a
因为我们发现，count（pat）和 p的个数 a的个数t的个数有关
所以我们可以分辨求出不同位置p的个数，a的个数，t的个数
然后使用这些信息也许可以求出最后的结果。
int [] P
int [] A
int [] T
好像还是差了点什么
那就是A 前面有多少个P，
T前面有多少个A
这样的两个信息好像才更加有用

  string s;
  cin>>s;
  int len = s.length();
  int pa[len];
  for(int i  = 0;i<n;i++){
    if(s[i] == 'P'){
        t++;
    }
    if(s[i] = 'A'){
       sum+=t;
    }
    if(s[i] == 'T'){
    ret+=sum;
    }
}


```java
#include<iostream>
using namespace std;
int main(){
    string s;
    cin>>s;
    long long sum = 0;
    long long ret = 0;
    long long t = 0;
    for(int i = 0;i<s.length();i++){
        if(s[i] == 'P'){
            t++;
        }
        if(s[i] == 'A'){
            sum+=t;
        }
        if(s[i] == 'T'){
            ret+=sum;
        }
    }
    long long temp = ret%1000000007;
    cout<<temp;
}

最后的答案就是这样
搞不懂，前几天为什么要一直拖着不肯写
哎
休息一会


          
1092 To Buy or Not to Buy

Eva would like to make a string of beads with her favorite colors so she went to a small shop to buy some beads. There were many colorful strings of beads. However the owner of the shop would only sell the strings in whole pieces. Hence Eva must check whether a string in the shop contains all the beads she needs. She now comes to you for help: if the answer is Yes, please tell her the number of extra beads she has to buy; or if the answer is No, please tell her the number of beads missing from the string.
1. Eva would like to make a string of breads with her favorite colors so she went to a small 
shop to buy some beads.  There were many colorful strings fo breads. Howeveer the owner of the shop would only sell the strings in whole pieces . 
 2. Hence Eva m mush check whether a string in the shopa contains all the beads she needs,
 3. She now comes to you for help 
 4. if  the answer is Yes Please tell her the number of extra beads she has to buy; or if the answer is No please tell her the number of beads missing from the string.
 5. b  jfhj
For the sake of simplicity, let's use the characters in the ranges [0-9], [a-z], and [A-Z] to represent the colors. For example, the 3rd string in Figure 1 is the one that Eva would like to make. Then the 1st string is okay since it contains all the necessary beads with 8 extra ones; yet the 2nd one is not since there is no black bead and one less red bead.
2. 读题：
3. 题目说的东西好多啊，不想仔细的读了，  大概就是两个字符串， 判断是否都在打字符串里面，小字符串是否都在大字符串里面， 如果不在缺失了几个，如果在要又多了几个
4. 对时间要求比较严格， 那又只能用C++了
  但是还是需要用心去思考这道题具体应该怎么去写
把大字符串里面的字符全部放到一个哈希表中，如果小字符串里面的字符在大字符串里面，
那就下一个不然miss++，如果miss == 0 那就让两个字符串长度相减去，如果miss大于0
那就返回 No+miss
少考虑了一个情况就是少了该怎么办
1可能错误的地方在于  miss==0 哪里返回的长度之差可能不符合题意，没有仔细看

先试着写出来把，大概只会差一点点
还是要使用计数法，可惜C语言 的map不太会，我得看一下


```java
#include<iostream>
#include<map>
using namespace std;
int main(){
    string s1;
    string s2;
    cin>>s1;
    cin>>s2;
    int miss =0;
    int len1 = s1.length();
    int len2 = s2.length();
     map<char,int> map1;
    for(int i = 0;i<len1;i++){
        map1[s1[i]]++;
    }
    for(int j  =0;j<len2;j++){
         if(map1[s2[j]] == 0){
             miss++;
         }else{
             map1[s2[j]]--;
         }   
    }
    if(miss == 0){
        cout<<"Yes "<< s1.length()-s2.length();
    }else{
        cout<<"No "<<miss;
    }
}

大概是这样 就可以全队了

1163 Dijiestra sequence 迪杰斯特拉序列
这题看着挺有意思，可能需要查一下语法或者思路才能写出来，但是还是在能力范围内，应该不会过于繁琐。
1. 看题目分析一波
2. 应该是熟悉知识点可以很快做出来的题目属于

读题
Dijkstra’s algorithm is one of the very famous greedy algorithms.
It is used for solving the single source shortest path problem which gives the shortest paths from one particular source vertex to all the other vertices of the given graph. It was conceived by computer scientist Edsger W. Dijkstra in 1956 and published three years later.
key1： Dijestra’s algorithm is one of the very famous greedy algorithms
key2: it is used for solving the single source shortest path problem which gives the shortest paths from one particular source

In this algorithm, a set contains vertices included in shortest path tree is maintained. During each step, we find one vertex which is not yet included and has a minimum distance from the source, and collect it into the set. Hence step by step an ordered sequence of vertices, let’s call it Dijkstra sequence, is generated by Dijkstra’s algorithm.

On the other hand, for a given graph, there could be more than one Dijkstra sequence. For example, both { 5, 1, 3, 4, 2 } and { 5, 3, 1, 2, 4 } are Dijkstra sequences for the graph, where 5 is the source. Your job is to check whether a given sequence is Dijkstra sequence or not.

解题三步走还是：
读题： 搞清楚它再问什么》

  1. 猜测考察什么东西，首先应该不是需要写一个dijie算法
  2. 应该是需要考察dijie性质
  3. 应该需要建图
  4. 时间复杂度放的很宽，那就用java写吧 然后看别人的代码改成c
  5. 仔细读题发现还是有一种方法 还是需要用Dijie
  6. 将题目给的序列放到一个数组中或者 List中
  7. 然后检查到源点的距离是否是单调递增的non strict
  8. 我记得有一个算法可以通过边集合计算出全源最短路
  9. int [][] dis //表示两点之间的距离
    10.写一个方法来填充这个矩阵
  10. 查一下思想是什么
  11. 开始写吧
#include<iostream>
using namespace std;
int n;
int m;
int dis[400][400];
bool judge(int nums[]){  
    int r = nums[0];
    for(int i = 1;i<n;i++){
        if(dis[r][nums[i]] < dis[r][nums[i-1]]){
           return 0;
        }
    }
    return 1;
}
int main(){
    cin>>n;
    cin>>m;
    
        for(int i  =0;i<n+1;i++){
            for(int j  =0;j<n+1;j++){
                if(i == j){
                 dis[i][j] = 0;   
                }else{
                dis[i][j] = 100000;
                }
            }
        }
    for(int i = 0;i<m;i++){
        int u;int v;
        int w;
        cin>>u;
        cin>>v;
        cin>>w;
        dis[u][v] = w;
        dis[v][u] = w;
    }
    for(int i = 0;i<n+1;i++){
        for(int j = 0;j<n+1;j++){
            for(int k = 0;k<n;k++){
                dis[i][j] = min(dis[i][j],dis[i][k] + dis[k][j]);
            }
        }
    }
    int q;
    cin>>q;
    
    for(int  i = 0;i<q;i++){
         int nums[n];
        for(int i =0;i<n;i++){
           cin>>nums[i];
        }
      bool u = judge(nums);
        if(u == 1){
            cout<<"Yes"<<endl;
        }else{
            cout<<"No"<<endl;
        }
    }   
}

但是好像不是这样子写的呢？可能dijie的题目意思和我想的不一样

#include<iostream>
using namespace std;
int n;
int m;
int dis[1010][1010];
bool judge(int nums[]){  
    int r = nums[1];
    for(int i = 2;i<n+1;i++){

        if(dis[r][nums[i]] < dis[r][nums[i-1]]){
           return 0;
        }
    }
    return 1;
}
int main(){
    cin>>n;
    cin>>m;
        for(int i  =1;i<n+1;i++){
            for(int j  =1;j<n+1;j++){
                if(i == j){
                 dis[i][j] = 0;   
                }else{
                dis[i][j] = 11000000;
                }
            }
        }
    for(int i = 0;i<m;i++){
        int u;int v;
        int w;
        cin>>u;
        cin>>v;
        cin>>w;
        dis[u][v] = w;
        dis[v][u] = w;
    }
    for(int k= 1;k<n+1;k++){
        for(int j = 1;j<n+1;j++){
            for(int i = 1;i<n+1;i++){
                dis[i][j] = min(dis[i][j],dis[i][k] + dis[k][j]);
            }
        }
    }
    int q;
    cin>>q;
    for(int  i = 0;i<q;i++){
         int nums[n+1];
        for(int j =1;j<n+1;j++){
           cin>>nums[j];
        }
      bool u = judge(nums);
        if(u == 1){
            cout<<"Yes"<<endl;
        }else{
            cout<<"No"<<endl;
        }
    }
      
}

这样就全对了 好累啊
我弟又发神经， 写代码还要带小孩
我真的有点累

我曹吃个其实还是可以使用dijie 做的 堆优化 的话 好像完美和这题匹配
我记得有一题使用dijie来写
那次我就用堆优化来做吧
不继续考虑了

1158 Telefraud Detection
一看名字就感觉是并查集或者键图+深度广度
让我们来分析一下把

Telefraud（电信诈骗） remains a common and persistent problem in our society. In some cases, unsuspecting victims lose their entire life savings. To stop this crime, you are supposed to write a program to detect those suspects from a huge amount of phone call records.
remains a common and presistent problem in our society . In some cases , unsuspecting victims lose their entire life savings. To stop this crme
unsuspecting victims lose their entire life savings. To stop this crime
you supposed to write a program to detect those suspects from a huge amount of phone call records.

A person must be detected as a suspect if he/she makes more than K short phone calls to different people everyday, but no more than 20% of these people would call back. And more, if two suspects are calling each other, we say they might belong to the same gang. A makes a short phone call to B means that the total duration of the calls from A to B is no more than 5 minutes.
A person must be detected as a suspect if
he/she makes more than K short phone calls
to different people everyday,
如果一个人打了超过⑦通电话
不超过百分之20 个这些人会打回去他就是嫌疑人
如果两个嫌疑人互相打 we say that they mgith belong to the same gang
A makes a short phone to B means that the total duration of the calls from A to B is no more than 5 minutes.

题目意思就是一个人打了超过k个短电话如果，那么他就是一个嫌疑人
如果两个嫌疑人 互相打电话，那么它们就是一个帮派的

首先判断一个人是不是嫌疑人用深度优先还是挺好判断的，
想一想使用并查集似乎需要分类很多次，而且不直观
1.并查集需要合并，寻找
如果用哈希表来判断是不是嫌疑 ，用并查集来合并帮派
用一个bool数组加哈希表判断是不是一个嫌疑人
2.好像第二个思路是可能可以的
3. 哈希表 int–对应一个额什么呢？ 对应一个List
4. 你还需要判断打回来的电话数量，（短电话）
5. 你需要判断比率，回拨比率
6.思路1 建图+深度
7哈希表需要收集过多信息我们可以用结构体进行思考
6. 顶一个一个结构体
struct{
int id;
HashSet set1;
HashSet set2;
double set2.size()/set1.size();
}
7. 如果遍历到大于5的就加入从set中删除
8. 如果遍历到小于5的就加入，但是又有一个问题，
9. 就是如果先遍历到小于5 后遍历到5
10. 想一想还是建图简单点好像
11 有没有可能建图之后再用并查集或者深度优先
12 深度优先就是需要排序
13 vector<vector> 双重排序
14 我觉这些方法应该都能做但是我不太能写出具体的做法，
15 我先把图键了把， 用 矩阵来建可能+java写可能会出问题，

import java.util.*;
public class Main{
    static Scanner scan = new Scanner(System.in);
    static int [][] graph;
    static boolean isuspect[];
  static List<List<Integer>> res = new ArrayList<>();
   static List<Integer> gang = new ArrayList<>();
    static boolean visit[];
        static int k = 0;
        static int n = 0;
      static  int m = 0;
    public static void dfs(int cur){
          gang.add(cur); 
          visit[cur] = true;
        for(int j = 1;j<n+1;j++){
if(graph[cur][j] > 0&&isuspect[j] == true &&visit[j] == false&&graph[j][cur] >0){
                     dfs(j);
              }
         }
   }
    public static void main(String [] args){

        k =scan.nextInt();
        n = scan.nextInt();
        m = scan.nextInt();
        graph = new int[n+1][n+1];
        //建立一张图
        visit = new boolean[n+1];
        isuspect = new boolean[n+1];
        for(int i = 0;i<m;i++){
            int u = 0;
            int v = 0;
            u =scan.nextInt();
            v = scan.nextInt();
            int w = scan.nextInt();
            graph[u][v]+=w;
        }
        for(int i = 1;i<n+1;i++){
            int temp  =0;
            double help = 0.0;
            int temp1 = 0;
            for(int j = 1;j<n+1;j++){
                if(graph[i][j]<=5 && graph[i][j] >0){
                    temp++;
                    if(graph[j][i] > 0){
                        temp1++;
                    }
                }
              
            }
              if(temp != 0){
                help = (double)temp1/temp;
                }
               if(temp>k && help<=0.2 ){
                   isuspect[i] = true;
               }
        }
      // for(int  i =1;i<n+1;i++){
      //     System.out.println(isuspect[i]);
      // }
        for(int i = 1;i<n+1;i++){
             if(isuspect[i] == true&&visit[i] == false){
                 dfs(i);
             }
                 
            if(gang.size() > 0 ){
                  Collections.sort(gang);
                    res.add(new ArrayList<>(gang));
            }   
               gang = new ArrayList<>();
                  
        } 
        if(res.size() == 0){
            System.out.println("None");
            return;
        }
 
         for(int i = 0;i<res.size();i++){
             for(int j = 0;j<res.get(i).size();j++){
                 if(j!= res.get(i).size()-1){
                 System.out.print(res.get(i).get(j)+" ");
                 }else{
                     System.out.print(res.get(i).get(j));
                 }
             }
             System.out.println();
         }
        
    }
}

只能说掌握的不是恨透侧，所以不仔细些思路了，但是这个java 会超时该成c++估计不会超时
最后一个测试点

相关文章：

  • 计算建模之EM算法
  • Django-(2)
  • opencv remap inverse 这里的x,y是dst下的,所以我没法在知道src的x,y下得到该点在dst的位置.
  • 温故知新（十三）——CAN
  • 如何跳出forEach循环
  • 大咖论道｜银行核心系统国产分布式数据库选型思考
  • 简单5分钟，将lowcode低代码融入到你的中后台管理系统
  • token、cookie、session
  • 强大多云混合多K8S集群管理平台Rancher入门实战
  • 学习编程的第二十四天
  • 第五十一周总结——对象遍历方法
  • java计算机毕业设计民宿预订管理系统设计与实现源码+数据库+系统+lw文档+mybatis+运行部署
  • 渗透测试-微信小程序-公众号测试经验总结
  • innodb存储引擎学习–备份
  • 《nginx》二、nginx反向代理
  • [译]CSS 居中（Center）方法大合集
  • 《深入 React 技术栈》
  • C++类中的特殊成员函数
  • Git学习与使用心得（1）—— 初始化
  • JavaScript 事件——“事件类型”中“HTML5事件”的注意要点
  • javascript 总结（常用工具类的封装）
  • JavaScript的使用你知道几种？(上)
  • JavaScript工作原理（五）：深入了解WebSockets，HTTP/2和SSE，以及如何选择
  • JS创建对象模式及其对象原型链探究（一）：Object模式
  • Linux快速复制或删除大量小文件
  • log4j2输出到kafka
  • mysql innodb 索引使用指南
  • OSS Web直传 （文件图片）
  • QQ浏览器x5内核的兼容性问题
  • Redis中的lru算法实现
  • Redis字符串类型内部编码剖析
  • vue从创建到完整的饿了么（18）购物车详细信息的展示与删除
  • 程序员最讨厌的9句话，你可有补充？
  • 分布式任务队列Celery
  • 给自己的博客网站加上酷炫的初音未来音乐游戏？
  • 算法系列——算法入门之递归分而治之思想的实现
  • 我有几个粽子，和一个故事
  • 一文看透浏览器架构
  • ​​​​​​​sokit v1.3抓手机应用socket数据包： Socket是传输控制层协议，WebSocket是应用层协议。
  • #设计模式#4.6 Flyweight（享元） 对象结构型模式
  • #使用清华镜像源 安装/更新 指定版本tensorflow
  • #图像处理
  • $分析了六十多年间100万字的政府工作报告，我看到了这样的变迁
  • (Ruby)Ubuntu12.04安装Rails环境
  • （七）c52学习之旅-中断
  • (区间dp) (经典例题) 石子合并
  • （十） 初识 Docker file
  • (原創) 博客園正式支援VHDL語法著色功能 (SOC) (VHDL)
  • (转)Oracle存储过程编写经验和优化措施
  • (轉貼) 寄發紅帖基本原則(教育部禮儀司頒布) (雜項)
  • ****** 二 ******、软设笔记【数据结构】-KMP算法、树、二叉树
  • .gitattributes 文件
  • .Net 8.0 新的变化
  • .net 发送邮件
  • .NET连接数据库方式