codeforces 496 div3(A-E1)(JAVA)

题目链接
A：水题代码

package codeforces496;

import java.util.Scanner;

public class testA {

	public static void main(String[] args) {
		Scanner sc=new Scanner(System.in);
		int n=sc.nextInt();//总数量
		int a[]=new int[n];
		int number=-1;
		int value[]=new int[1000];
		for(int i=0;i<n;i++)
		{
			a[i]=sc.nextInt();
			if(a[i]==1) {number++;}
			value[number]=a[i];
		}
		System.out.println(number+1);
		for(int i=0;i<number+1;i++)
		{
			if(i!=number)
			System.out.print(value[i]+" ");
			else
				System.out.print(value[i]);
		}	
	}
}

B：水

package codeforces496;

import java.util.Scanner;

public class testB {

	public static void main(String[] args) {
		Scanner sc=new Scanner(System.in);
		String a1=sc.next();
		String a2=sc.next();
		int min=a1.length()<a2.length()?a1.length():a2.length();
		for(int i=0;i<min;i++)
		{
			  
			 if(a1.charAt(a1.length()-1-i)!=a2.charAt(a2.length()-1-i))
				{
					a1=a1.substring(0,a1.length()-i);
					a2=a2.substring(0, a2.length()-i);
					System.out.println(a1.length()+a2.length());
					break;
				}
			 if(i==min-1) {	System.out.println((a1.length()>a2.length()?a1.length():a2.length())-min);}
		  
		}
	}
}

C：先打表储存数值。（足够大一点）。每次输入的数值先存起来（包过数量）。然后逐个比较。要充分考虑二的次幂的特性。找到比他大一点的那个2的次幂减去。查看是否在集合中。不要多想也不要少想。这个重要的是二的特性。

package codeforces496;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Scanner;
import java.util.Set;
import java.util.TreeMap;

public class testC {

	public static void main(String[] args) {		
        Scanner sc=new Scanner(System.in);
        Map<Integer,Integer>map=new TreeMap();
        Set<Integer>set=new HashSet();       
        long value[]=new long[32];
        value[0]=1;
        for(int i=1;i<32;i++)
        {
        	value[i]=2*value[i-1];
        }
        int n=sc.nextInt();      
        int a[]=new int[n];
        boolean jud[]=new boolean[n];
        for(int i=0;i<n;i++)
        {
        	a[i]=sc.nextInt();
        }
        for(int i=0;i<n;i++)
        {
        	
        	if(map.containsKey(a[i])) {map.put(a[i], map.get(a[i])+1);}
        	else
        		map.put(a[i], 1);
        	//judgel=a[i];
        }

        for(int i=n-1;i>=0;i--)
        {  
        	for(int j=31;j>0;j--)
        	{
        		if(value[j-1]<=a[i])
        		{
        			int team=(int) (value[j]-a[i]);
        			if(team==a[i]&&map.get(a[i])>=2) {set.add(team);break;}
        			else if(team!=a[i]&&map.containsKey(team)) {set.add(team);set.add(a[i]);break;}
        		}
        	}	
        }
    int count=0;
    for(int i:set)
    {
    	count+=map.get(i);
    }
        System.out.println(n-count);
	}
}

D:dp思想，判断当前的是否为0.0可以被整除，否则向上找（叠加数值）dp【j】小一市为临界点，如果可以被三整除，那么dp[i] 1；如果不。那么就dp和前一样dp[i]=dp[j]。

package codeforces496;

import java.util.Scanner;

public class testD {

	public static void main(String[] args) {
		Scanner sc=new Scanner(System.in);
		String s=sc.next();
		char num[]=s.toCharArray();
		int number[]=new int[num.length];
		for(int i=0;i<number.length;i++)
		{
			number[i]=num[i]-'0';
		}
		int dp[]=new int[number.length];
		if(number[0]%3==0)dp[0]=1;
		else dp[0]=0;
		for(int i=1;i<number.length;i++)
		{
			if(number[i]%3==0)dp[i]=dp[i-1]+1;
			else
			{
				dp[i]=dp[i-1];//预处理
				int team=number[i];
				for(int j=i-1;j>=0;j--)
				{	
					if(dp[j]!=dp[i]) {break;}
					else if(j>0) {
						if(dp[j]==dp[i]) {
							team+=number[j];
							if(team%3==0) {dp[i]=dp[j-1]+1;break;}
						}
					}	
					else if(j==0)
					{
						team+=number[j];
						if(team%3==0) {dp[i]=dp[j]+1;break;}
					}
				}
			}
		}
		
        System.out.println(dp[number.length-1]);
	}
}

E1:当初想的时候知道思路但是方法选的不对，复杂度太高。后来参考别人发现判断大于和小于的数量是很好的选择，大于就 1，小于就-1.先往左查找等于0的情况（0）时候中位数满足条件。在往右查找0时候，没找到一个0；number =左侧0数量。因为这个0可以和左侧0任意搭配。方法还是很巧妙的。

package codeforces496;

import java.util.Map;
import java.util.Scanner;
import java.util.TreeMap;

public class testE1 {

	public static void main(String[] args) {
		Scanner sc=new Scanner(System.in);
		int n=sc.nextInt();//总数量
		int m=sc.nextInt();
		int a[]=new int[n];
		int index=0;
		for(int i=0;i<n;i++)
		{
			int jud=sc.nextInt();
			a[i]=jud>m?1:-1;
			if(jud==m) {index=i;a[i]=0;}
		}
       int dp[]=new int[n];
       int left[]=new int[n];
       Map<Integer,Integer>map=new TreeMap();
       
       dp[index]=0;
       map.put(0, 1);
       for(int i=index+1;i<n;i++)
       {
    	   dp[i]+=dp[i-1]+a[i]; 
    	   if(map.containsKey(dp[i]))
    	   {
    		   map.put(dp[i], map.get(dp[i])+1);
    	   }
    	   else
    		   map.put(dp[i], 1);
       }
       long count =0;
       for(int i=index;i>=0;i--)
       {
    	   if(i==index) {dp[index]=0;}
    	   else dp[i]+=dp[i+1]+a[i];  
    	  if(map.containsKey(-dp[i]))
    	  {
    		  count+=map.get(-dp[i]);
    	  }
    	  if(map.containsKey(-dp[i]+1))
    	  {
    		  count+=map.get(-dp[i]+1);
    	  }
       }                
       System.out.println(count);
	}
}

最后

以上就是迷你黄豆为你收集整理的codeforces 496 div3(A-E1)(JAVA)的全部内容，希望文章能够帮你解决codeforces 496 div3(A-E1)(JAVA)所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。