【PTA-训练day2】L2-013 红色警报 + L1-006 连续因子

L2-013 红色警报 - 并查集 

PTA | 程序设计类实验辅助教学平台

思路：

用并查集做

• 先将图联通 用父节点==自己 统计连通块数cnt
• 输入k个询问 每次要删除的点x标记为true
• 然后将非该点x的点连通 不访问已经打上标记的点
• 再次统计连通块数res
• 如果res>cnt+1 (因为被删除的x点也算一个连通块 如果删掉x的res比cnt+1大 说明图的连通性改变
• 此时更新图 也就是cnt=res

import java.util.*;
    
public class Main
{
    static int N=510,M=5001;
    static int[] f=new int[N];
    static int[][] e=new int[M][2];
    static boolean[] st=new boolean[N];
    
    static void init(int n)
    {
        for(int i=0;i
    }
    
    static int find(int x)
    {
        if(x!=f[x]) f[x]=find(f[x]);
        return f[x];
    }
    
    static void unite(int a,int b)
    {
        int x=find(a);
        int y=find(b);
        if(x!=y) f[x]=y;
    }
    
    public static void main(String[] args)
    {
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt(),m=sc.nextInt();
        init(n);
        //把每两个点连接起来
        for(int i=0;i
        {
            e[i][0]=sc.nextInt();
            e[i][1]=sc.nextInt();
            unite(e[i][0],e[i][1]);
        }
        int cnt=0;//连通块的数量
        for(int i=0;iif(f[i]==i) cnt++;
        int k,t;
        k=sc.nextInt();
        t=k;
        while(k-->0)
        {
            init(n);
            int x=sc.nextInt();
            st[x]=true; //把要删的点标记出来 然后把没有被标记的点联通起来 也就相当于删除已标记的点
            for(int i=0;i
            {
                int a=e[i][0],b=e[i][1];
                if(st[a]||st[b]) continue; //如果一条边里有一个点被标记 则不连接
                if(x!=a&&x!=b) unite(a,b); //如果两点都不是要删除的点 则连接
            }
            int res=0;
            for(int i=0;iif(f[i]==i) res++;
            //因为删掉该城市 这个城市也是一个单独的连通块 所以当前连通块>之前连通块+这个城市 说明删掉该城市 会改变图的连通性
            if(res>cnt+1) System.out.printf("Red Alert: City %d is lost!\n",x);
            else System.out.printf("City %d is lost.\n",x);
            cnt=res;//更新连通块
        }
        if(t==n) System.out.printf("Game Over.");
    }
}

 

L1-005 考试座位号 - 15

PTA | 程序设计类实验辅助教学平台

#include 
using namespace std;
 
struct stu
{
    string id;
    int a,b;
}p[1010];
 
int main()
{
    int n,k;
    cin>>n;
    for(int i=0;i>p[i].id>>p[i].a>>p[i].b;
    cin>>k;
    while(k--)
    {
        int x,idx=0;
        cin>>x;
        for(int i=0;i
            if(x==p[i].a)
            {
                idx=i;
                break;
            }
        cout<" "<
    }
}

L1-006 连续因子 - 20

PTA | 程序设计类实验辅助教学平台

思路：

• 两个循环 第一个控制首因子
• 第二个嵌套在第一个循环里 连乘 一旦不能被n整除则跳出 
• 每次跳出内部循环 更新最大连续因子长度
• 最后特判素数情况——只有1个因子 即它自己

import java.util.*;
 
public class Main
{
    public static void main(String[] args)
    {
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();
        int cnt,s,max=0,idx=0;
        for(int i=2;i//i为首个因子
        {
            s=1;
            cnt=0;
            for(int j=i;j
            {
                s*=j;
                if(n%s!=0) //一旦不连续跳出
                {
                    break;
                }
                cnt++;
            }
            if(max//更新最长的长度
            {
                max=cnt;
                idx=i;
            }
        }
        if(max==0) System.out.printf("1\n%d",n); //素数情况
        else 
        {
            System.out.println(max);
            for(int i=0;i
            {
                if(i!=0) System.out.print("*");
                System.out.printf("%d",idx++);
            }
        }
    }
}

 

L1-008 求整数段和 - 10

PTA | 程序设计类实验辅助教学平台

import java.util.*;
 
public class Main
{
    public static void main(String[] args)
    {
        Scanner sc=new Scanner(System.in);
        int a=sc.nextInt(),b=sc.nextInt();
        int cnt=0,sum=0;
        for(int i=a;i<=b;i++)
        {
            cnt++;
            System.out.printf("%5d",i);
            sum+=i;
            if(cnt%5==0) System.out.println();
        }
        if(cnt!=5) System.out.println();
        System.out.print("Sum = "+sum);
        
    }
}