hihocoder65

http://hihocoder.com/contest/offers65/problems

题目1 : 真正的素数

• 1. 只能是2,3,5,7的组合，
• 2. 包括2的只有2,23；包括5的只有5,53
• 3. 3,7组合也只能交替来，不然33,77就是11 的倍数
     所以有限个，穷举一下

package l651;

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n=sc.nextInt();
        int[]a=new int[]{2,3,5,7,23,37,53,73,373};
        if(n>9) System.out.println(-1);
        else System.out.println(a[n-1]);
    }
}

题目2 : 最长子段
Map+running sum的套路，这里先要预先处理一下

package l652;

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

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n=sc.nextInt(),s=sc.nextInt();
        int[]a=new int[n];
        for(int i=0;i<n;i++)a[i]=sc.nextInt();
        TreeMap<Long, Integer>m1=new TreeMap<Long, Integer>();
        TreeMap<Long, Integer>m2=new TreeMap<Long, Integer>();
        long sum=0;
        m1.put((long)0, -1);
        for(int i=0;i<n;i++) {
            sum+=a[i];
            if(!m1.containsKey(sum)) m1.put(sum, i);
        }
        int min = n;
        for(long t:m1.descendingKeySet()) {
            min = Math.min(min, m1.get(t));
            m2.put(t, min);
        }
        
        int res = -1;
        sum=0;
        for(int i=0;i<n;i++) {
            sum+=a[i];
            Long t = m2.ceilingKey(sum-s);
            if(t==null) continue;
            res = Math.max(res, i-m2.get(t));
        }
        
        System.out.println(res);
    }
}

题目4 : 解方程
解的范围有限，数越大，平方和加起来越无法超过数本身
所以可以直接穷举

#include <iostream>
#include <vector>
#include <map>

using namespace std;

int digitSquareSum(long long x) {
  int sum=0;
  while (x) {
    sum+=(x%10)*(x%10);
    x/=10;
  }
  return sum;
}

int main() {
  long long k, a, b;
  cin >> k >> a >> b;
  int count=0;
  for (int i=1; i<18*9*9; i++) {
    if (k>=a/i && k<=b/i) if (i==digitSquareSum(k*i)) count++;
  }
  cout << count << endl;
}