problem1 link
满足$a^{b}leq5000000,b>1$的数字不多,有2000多个，直接暴力计算能组成哪些数字即可。
import java.util.*;
import java.math.*;
import static java.lang.Math.*;
public class SumsOfPerfectPowers {
public int howMany(int lowerBound,int upperBound) {
boolean[] a=new boolean[upperBound+1];
a[0]=true;
if(upperBound>=1) {
a[1]=true;
}
for(int i=2;i*i<=upperBound;++i) {
if(a[i]) {
continue;
}
int k=i*i;
while(k<=upperBound) {
a[k]=true;
if(k>upperBound/i) {
break;
}
k=k*i;
}
}
int num=0;
for(int i=1;i<=upperBound;++i) {
if(a[i]) {
++num;
}
}
int[] b=new int[num];
num=0;
for(int i=1;i<=upperBound;++i) {
if(a[i]) {
b[num++]=i;
}
}
for(int i=0;i<b.length;++i) {
for(int j=i;j<b.length;++j) {
if(b[i]+b[j]>upperBound) {
break;
}
a[b[i]+b[j]]=true;
}
}
num=0;
for(int i=lowerBound;i<=upperBound;++i) {
if(a[i]) {
++num;
}
}
return num;
}
}
problem2 link
计算出每个点的值，bfs即可。长度大于顶点$n$时说明有环。
import java.util.*;
import java.math.*;
import static java.lang.Math.*;
public class StarsInGraphs {
public int starryPaths(String[] adjacencyMatrix,int C) {
final int n=adjacencyMatrix.length;
List<List> g=new ArrayList<>();
for(int i=0;i<n;++i) {
g.add(new ArrayList<>());
}
long[] d=new long[n];
for(int i=0;i<n;++i) {
for(int j=0;j<n;++j) {
if(adjacencyMatrix[i].charAt(j)=='1') {
g.get(i).add(j);
++d[i];
}
}
}
for(int i=0;i<n;++i) {
d[i]=(1l<<d[i])-1-d[i]-d[i]*(d[i]-1)/2;
}
int[] f=new int[n];
boolean[] inq=new boolean[n];
Queue<Integer> queue=new LinkedList<>();
for(int i=0;i<n;++i) {
if(1<=d[i]&&d[i]<=C) {
f[i]=1;
inq[i]=true;
queue.offer(i);
}
}
while(!queue.isEmpty()) {
int u=queue.poll();
inq[u]=false;
for(int i=0;i<g.get(u).size();++i) {
int v=(int)g.get(u).get(i);
if(d[u]<=d[v]&&d[v]<=C&&f[u]+1>f[v]) {
f[v]=f[u]+1;
if(f[v]>n) {
return -1;
}
if(!inq[v]) {
inq[v]=true;
queue.offer(v);
}
}
}
}
int result=0;
for(int i=0;i<n;++i) {
result=Math.max(result,f[i]);
}
return result;
}
}
problem3 link
求出所有交点，那么就是一个图。每条边看作两条有向边。对于每个封闭图形（必是凸包）逆时针找它的每条边。
import java.util.*;
import java.math.*;
import static java.lang.Math.*;
public class PlaneDivision {
static class Rational {
public BigInteger x;
public BigInteger y;
public int sign;
public Rational copy() {
return new Rational(new BigInteger(x.toString()),new BigInteger(y.toString()),sign);
}
public Rational() {
}
public Rational(BigInteger _x,BigInteger _y,int _sign) {
x=_x;
y=_y;
sign=_sign;
simple();
}
public Rational(long t) {
x=new BigInteger(Long.toString(t));
y=BigInteger.ONE;
sign=1;
simple();
}
public boolean equals(Rational a) {
if(x.equals(BigInteger.ZERO)) {
return a.x.equals(BigInteger.ZERO);
}
if(a.x.equals(BigInteger.ZERO)) {
return false;
}
return sign==a.sign&&x.equals(a.x)&&y.equals(a.y);
}
private Rational simple() {
if(x.equals(BigInteger.ZERO)) {
sign=1;
y=BigInteger.ONE;
}
else {
if(x.compareTo(BigInteger.ZERO)<0) {
x=x.negate();
sign=-sign;
}
BigInteger t=x.gcd(y);
if(!t.equals(BigInteger.ONE)) {
x=x.divide(t);
y=y.divide(t);
}
}
return this;
}
public Rational add(Rational a) {
if(a.x.equals(BigInteger.ZERO)) {
return copy();
}
if(x.equals(BigInteger.ZERO)) {
return a.copy();
}
BigInteger p=y.multiply(a.y);
BigInteger x1=x.multiply(a.y);
BigInteger x2=a.x.multiply(y);
Rational result=new Rational();
result.y=p;
if(sign==1) {
if(a.sign==1) {
result.x=x1.add(x2);
result.sign=1;
}
else {
result.x=x1.subtract(x2);
result.sign=1;
}
}
else {
if(a.sign==1) {
result.x=x2.subtract(x1);
result.sign=1;
}
else {
result.x=x1.add(x2);
result.sign=-1;
}
}
return result.simple();
}
public Rational substract(Rational a) {
return add(new Rational(a.x,a.y,-a.sign));
}
public Rational multiply(Rational a) {
if(x.equals(BigInteger.ZERO)) {
return new Rational(0);
}
if(a.x.equals(BigInteger.ZERO)) {
return new Rational(0);
}
Rational result=new Rational();
result.x=x.multiply(a.x);
result.y=y.multiply(a.y);
result.sign=sign*a.sign;
return result.simple();
}
public Rational divide(Rational a) {
if(x.equals(BigInteger.ZERO)) {
return new Rational(0);
}
return multiply(new Rational(a.y,a.x,a.sign));
}
public boolean lessThan(Rational a) {
if(a.x.equals(BigInteger.ZERO)) {
if(x.equals(BigInteger.ZERO)) {
return false;
}
return sign==-1?true:false;
}
if(x.equals(BigInteger.ZERO)) {
return a.sign==1?true:false;
}
if(sign<a.sign){
return true;
}
if(a.sign<sign) {
return false;
}
if(sign==1) {
return x.multiply(a.y).compareTo(a.x.multiply(y))<0;
}
else {
return x.multiply(a.y).compareTo(a.x.multiply(y))>0;
}
}
public double toDouble() {
return 1.0*Double.valueOf(x.toString())/Double.valueOf(y.toString())*sign;
}
public String toString() {
return Double.toString(toDouble());
}
}
static int DB(Rational x)
{
if(x.x.equals(BigInteger.ZERO)) {
return 0;
}
return x.sign;
}
static class point implements Comparable
{
public Rational x;
public Rational y;
public point(){}
public point(Rational _x,Rational _y) {
this.x=_x.copy();
this.y=_y.copy();
}
public point add(point a)
{
return new point(x.add(a.x),y.add(a.y));
}
public point substract(point a)
{
return new point(x.substract(a.x),y.substract(a.y));
}
public Rational crossMultiply(point a)
{
return x.multiply(a.y).substract(y.multiply(a.x));
}
public point multiply(Rational t)
{
return new point(x.multiply(t),y.multiply(t));
}
public Rational dotMultiply(point a)
{
return x.multiply(a.x).add(y.multiply(a.y));
}
public double getAng(point a)
{
return Math.atan2(crossMultiply(a).toDouble(),dotMultiply(a).toDouble());
}
public boolean equals(point a)
{
return x.equals(a.x)&&y.equals(a.y);
}
public point divide(Rational a) {
return new point(x.divide(a),y.divide(a));
}
@Override
public int compareTo(Object e) {
point t=(point)e;
if(DB(x.substract(t.x))!=0) {
return x.lessThan(t.x)?-1:1;
}
if(DB(y.substract(t.y))==0) {
return 0;
}
return y.lessThan(t.y)?-1:1;
}
public String toString() {
return x.toString()+","+y.toString();
}
}
static class pair {
public int first;
public int second;
public pair() {}
public pair(int first,int second) {
this.first=first;
this.second=second;
}
}
static final int N=85;
point[][] L=null;
List<List<point>> G=null;
List<point> p=null;
int m;
point x,y;
List<List<pair>> g=null;
boolean[] visit=null;
int n;
void init() {
L=new point[N][];
for(int i=0;i<N;++i) {
L[i]=new point[2];
}
G=new ArrayList<>();
for(int i=0;i<N;++i) {
G.add(new ArrayList<>());
}
p=new ArrayList<>();
g=new ArrayList<>();
for(int i=0;i<N*N*N;++i) {
g.add(new ArrayList<>());
}
visit=new boolean[N*N*N];
}
boolean isParal(point a,point b,point p,point q)
{
Rational x=(b.x.substract(a.x)).multiply(q.y.substract(p.y));
Rational y=(b.y.substract(a.y)).multiply(q.x.substract(p.x));
return DB(x.substract(y))==0;
}
point getCross(point a,point b,point p,point q)
{
Rational s1=(a.substract(p)).crossMultiply(b.substract(p));
Rational s2=(b.substract(q)).crossMultiply(a.substract(q));
return (p.multiply(s2).add(q.multiply(s1))).divide(s1.add(s2));
}
Rational cross(point a,point b,point p)
{
return (b.substract(a)).crossMultiply(p.substract(a));
}
class MyComparator implements Comparator {
public int compare(Object o1,Object o2) {
pair A=(pair)o1;
pair B=(pair)o2;
point a=p.get(A.first);
point b=p.get(B.first);
Rational xx=cross(x,y,a);
Rational yy=cross(x,y,b);
if(DB(xx)!=DB(yy)) {
return DB(xx)>DB(yy)?-1:1;
}
double dx=a.substract(y).getAng(x.substract(y));
double dy=b.substract(y).getAng(x.substract(y));
return dx<dy?-1:1;
}
}
int getindex(point t) {
for(int i=0;i<p.size();++i) {
if(p.get(i).equals(t)) {
return i;
}
}
assert false;
return -1;
}
void build()
{
int x=0;
for(int i=1;i<=n;++i)
{
for(int j=0;j+1<G.get(i).size();++j)
{
int k=getindex(G.get(i).get(j));
int t=getindex(G.get(i).get(j+1));
if(k==t) {
continue;
}
g.get(k).add(new pair(t,++x));
g.get(t).add(new pair(k,++x));
}
}
}
int result;
void DFS(int cur,int pre,int t)
{
if(cur==t) {
++result;
return;
}
x=p.get(pre);
y=p.get(cur);
Collections.sort(g.get(cur),new MyComparator());
for(int i=0;i<g.get(cur).size();++i)
{
int j=g.get(cur).get(i).first;
int k=g.get(cur).get(i).second;
if(j==pre||visit[k]) {
continue;
}
if(DB(cross(p.get(pre),p.get(cur),p.get(j)))<=0) {
return;
}
visit[k]=true;
DFS(j,cur,t);
return;
}
}
int cal()
{
result=0;
for(int i=0;i<m;++i)
{
for(int j=0;j<g.get(i).size();++j)
{
int k=g.get(i).get(j).first;
int t=g.get(i).get(j).second;
if(visit[t]||j!=0&&g.get(i).get(j-1).first==k) {
continue;
}
visit[t]=true;
DFS(k,i,i);
}
}
return result;
}
public int howManyFiniteParts(int[] x1, int[] y1, int[] x2, int[] y2) {
init();
n=x1.length;
for(int i=1;i<=n;++i)
{
L[i][0] = new point(new Rational(x1[i-1]),new Rational(y1[i-1]));
L[i][1] = new point(new Rational(x2[i-1]),new Rational(y2[i-1]));
for(int j=1;j<i;++j)
{
if(isParal(L[j][0],L[j][1],L[i][0],L[i][1])) {
continue;
}
point temp=getCross(L[j][0],L[j][1],L[i][0],L[i][1]);
int k=-1;
for(k=0;k<G.get(i).size();k++) {
point t=G.get(i).get(k);
if(t.equals(temp)) {
break;
}
}
if(k>=G.get(i).size()) {
G.get(i).add(temp);
}
for(k=0;k<G.get(j).size();k++) {
point t=G.get(j).get(k);
if(t.equals(temp)) {
break;
}
}
if(k>=G.get(j).size()) {
G.get(j).add(temp);
}
p.add(temp);
}
}
Collections.sort(p);
if(p.size()==0) {
m=0;
}
else {
m=1;
for(int i=1;i<p.size();++i) {
if(!p.get(m-1).equals(p.get(i))) {
p.set(m,p.get(i));
++m;
}
}
}
for(int i=1;i<=n;++i) {
Collections.sort(G.get(i));
}
build();
return cal();
}
}