Chieh's Blog

Because Of Coding

ZOJ Problem Set - 3563 Alice's Sequence II

飞机票:http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=4562

题意很清楚,构造矩阵matrix[][] 其中ai_j表示第i个数字给第j个数字提供了什么。那么就很清楚能写出矩阵,对于m个运算方案,运算k次,则需要运算k/m次全部的+k%m剩下的就是答案,所以这个题想清楚了很简单,直接矩阵快速幂m种方案的矩阵乘积为x,k%m种方案的矩阵乘积为c,初始矩阵为A,则答案矩阵为A*(x)^(k/m)*c,主要是trick!!!!搞死我了,(1)add 运算的话,可能两个值相同,那么对应的点就为2了,(2)transform 可能i和j又相同,这里的话必须执行前面的乘法再置0,如果反过来则错,其余没有什么trick点了,小心点就好了,反正我是被搞死了。//

//  main.cpp
//  zoj3563
//
//  Created by cfhaiteeh on 14/03/2018.
//  Copyright © 2018 cfhaiteeh. All rights reserved.
//
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#define  LL long long
using namespace  std;
const int MOD=10000007;
struct Matrix{
    LL  mat[26][26];
};
int n,m,k;
Matrix MUL(Matrix a,Matrix b){
    Matrix c;
    memset(c.mat,0,sizeof(c.mat));
    for(int i=1;i<=n;i++){
        for(int k=1;k<=n;k++){
            if(a.mat[i][k])
            for(int j=1;j<=n;j++){
                
                c.mat[i][j]=(c.mat[i][j]+a.mat[i][k]*b.mat[k][j])%MOD;
            }
        }
    }
    return c;
}
Matrix poww(Matrix a,int k){
    Matrix ans;
    memset(ans.mat,0,sizeof(ans.mat));
    for(int i=1;i<=n;i++)ans.mat[i][i]=1;
    while(k!=0){
        if(k%2==1){
            ans=MUL(ans,a);
        }
        a=MUL(a,a);
        k/=2;
    }
    return ans;
}
int ai[26];
int bi[11][26][26];
char ch[123];
void init(){
    for(int i=1;i<=n;i++)scanf("%d",&ai[i]);
    scanf("%d",&m);
    for(int i=1;i<=m;i++){
        for(int j=1;j<=n;j++){
            for(int k=1;k<=n;k++){
                if(j==k)bi[i][j][k]=1;
                else bi[i][j][k]=0;
            }
        }
        scanf("%s",ch+1);
        int u,v,w,x;
        if(ch[1]=='r'){
            scanf("%d",&u);
            bi[i][u][u]=0;
        }
        else if(ch[1]=='d'){
            scanf("%d",&u);
            bi[i][u][u]*=2;
        }
        else if(ch[1]=='a'){
            scanf("%d%d",&u,&v);
            bi[i][v][u]++;
        }
        else if(ch[1]=='s'){
            scanf("%d%d",&u,&v);
            bi[i][u][u]=0;
            bi[i][v][v]=0;
            bi[i][u][v]=1;
            bi[i][v][u]=1;
        }
        else if(ch[1]=='i'){
            scanf("%d%d",&u,&v);
            for(int j=u;j<=v;j++)bi[i][j][j]=0;
            w=u;
            for(int j=v;j>=u;j--){
                bi[i][j][w]=1;
                w++;
            }
        }
        else if(ch[1]=='t'){
            scanf("%d%d%d%d",&u,&v,&w,&x);
           
            bi[i][v][v]=u;
            bi[i][x][v]=w;
             bi[i][x][x]=0;
        }
    }
    scanf("%d",&k);
}
Matrix a,b,c;
LL ans[26];
void play(){
    
    int M=k%m;
    int F=k/m;
    memset(a.mat,0,sizeof(a.mat));
    memset(b.mat,0,sizeof(b.mat));
    
    for(int i=1;i<=n;i++){
        a.mat[i][i]=1;
    }
    
    for(int r=1;r<=m;r++){
        for(int i=1;i<=n;i++){
            for(int j=1;j<=n;j++){
                b.mat[i][j]=bi[r][i][j];
            }}
        a=MUL(a, b);
        if(r==M){
            c=a;
        }
    }
    Matrix x=poww(a,F);
    if(M!=0){
        x=MUL(x,c);
    }
    memset(ans,0,sizeof(ans));
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            ans[i]=(ans[i]+x.mat[j][i]*ai[j])%MOD;
        }
    }
}
void pri(){
    
    bool fir=1;
    for(int i=1;i<=n;i++){
       
        if(!fir)printf(" ");
        fir=0;
        printf("%lld",ans[i]);
    }
    printf("\n");
}
int main() {
    // insert code here...
    while(scanf("%d",&n)!=EOF){
        init();
        play();
        pri();
    }
    return 0;
}

ZOJ Problem Set - 2853 Evolution

飞机票:http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=1853

大致意思:(我是直接将0~n-1变为1~n)有m回合进化,每次进化有T个要求,就是i中有P(i,j)变为j,求最后n物种的数量,典型的矩阵快速幂的题目,令matrix[i][j]表示第i个物种有多少转化为第j个物种,即P(i,j),A[]为初始状态,则结果矩阵为A*(matrix)^m其中最后一列的和即为答案

//
//  main.cpp
//  zoj2853
//
//  Created by cfhaiteeh on 14/03/2018.
//  Copyright © 2018 cfhaiteeh. All rights reserved.
//

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#define  LL long long
using namespace  std;
struct Matrix{
    double  mat[234][234];
};
int n,m,k;
Matrix MUL(Matrix a,Matrix b){
    Matrix c;
    memset(c.mat,0,sizeof(c.mat));
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            for(int k=1;k<=n;k++){
                c.mat[i][j]=(c.mat[i][j]+a.mat[i][k]*b.mat[k][j]);
            }
        }
    }
    return c;
}
Matrix poww(Matrix a,int k){
    Matrix ans;
    memset(ans.mat,0,sizeof(ans.mat));
    for(int i=1;i<=n;i++)ans.mat[i][i]=1;
    while(k!=0){
        if(k%2==1){
            ans=MUL(ans,a);
        }
        a=MUL(a,a);
        k/=2;
    }
    return ans;
}
Matrix a;
LL ai[234];
double ci[234];
void init(){
    memset(a.mat,0,sizeof(a.mat));
    for(int i=1;i<=n;i++)scanf("%lld",&ai[i]);
    int t;
    scanf("%d",&t);
    for(int i=1;i<=n;i++)ci[i]=1;
    for(int i=1;i<=t;i++){
        int u,v;
    
        double c;
        scanf("%d%d%lf",&u,&v,&c);
            u++;v++;
        ci[u]-=c;
        a.mat[u][v]+=c;
    }
    for(int i=1;i<=n;i++)a.mat[i][i]=ci[i];
}
double ans;
void play(){
    Matrix c=poww(a,m);
    ans=0;
    for(int i=1;i<=n;i++){
        ans+=ai[i]*c.mat[i][n];
    }
}
void pri(){
    printf("%.0f\n",ans);
}
int main() {
    // insert code here...
    while(scanf("%d%d",&n,&m)!=EOF){
        if(n==0&&m==0)break;
        init();
        play();
        pri();
    }
    return 0;
}

ZOJ Problem Set - 3690 Choosing number

飞机票:http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=4973

题意很明显,就是相邻两个人如果一样,则一定要大于k

因为第i+1个人和第i个人的选择有关,一共有四种可能,就是i选择<=k i+1选择<=k ;i选择<=k i+1选择>k;i选择>k i+1选择<=k ;i选择>k i+1选择>k 。所以我们很容易想到矩阵,令mat[2][2]其中a i_j表示四种中得一种,则我们只要有一个A[k,m-k] ,则答案就为A*(mat)^(n-1);//

//  main.cpp
//  zoj3690
//
//  Created by cfhaiteeh on 14/03/2018.
//  Copyright © 2018 cfhaiteeh. All rights reserved.
//

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#define  LL long long
using namespace  std;
const int MOD=1000000007;
struct Matrix{
   LL  mat[3][3];
};
int n,m,k;
Matrix MUL(Matrix a,Matrix b){
    Matrix c;
    memset(c.mat,0,sizeof(c.mat));
    for(int i=1;i<=2;i++){
        for(int j=1;j<=2;j++){
            for(int k=1;k<=2;k++){
                c.mat[i][j]=(c.mat[i][j]+a.mat[i][k]*b.mat[k][j])%MOD;
            }
        }
    }
    return c;
}
Matrix poww(Matrix a,int k){
    Matrix ans;
    memset(ans.mat,0,sizeof(ans.mat));
    for(int i=1;i<=2;i++)ans.mat[i][i]=1;
    while(k!=0){
        if(k%2==1){
            ans=MUL(ans,a);
        }
        a=MUL(a,a);
        k/=2;
    }
    return ans;
}
Matrix a;
LL ai[3];
void init(){
    memset(a.mat,0,sizeof(a.mat));
    ai[1]=k;
    ai[2]=m-k;
    int a1=k-1;
    if(a1<0)a1=0;
    a.mat[1][1]=a1;
    a.mat[1][2]=m-k;
    a.mat[2][1]=k;
    a.mat[2][2]=m-k;
}
LL ans[3];
void play(){
    Matrix c=poww(a, n-1);
    memset(ans,0,sizeof(ans));
    for(int i=1;i<=2;i++){
        for(int j=1;j<=2;j++){
            ans[i]=(ans[i]+ai[j]*c.mat[j][i])%MOD;
        }
    }
    
}
void pri(){
    printf("%lld\n",(ans[1]+ans[2])%MOD);
}
int main() {
    // insert code here...
    while(scanf("%d%d%d",&n,&m,&k)!=EOF){
        init();
        play();
        pri();
    }
    return 0;
}

ZOJ Problem Set - 2974 Just Pour the Water

飞机票:http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=1973

题意:有n个容器,在每秒每个容器同时向k_i个容器中分配当前的容量*1/k_i,求m秒后各容器中的容量

分析:易知第i+1秒和第i秒有关,所以可以想到矩阵快速幂。主要是构造矩阵,如果第i个向第j个容器分配,则mat i_j为1/k_i;注意如果第i个容器没有向任何一个容器分配,则mat i_i=1(这个使我wa了一发),原始矩阵A就是各个容器的原始容量,最后的A*(mat)^n就是各个容器的最终容量。

//
//  main.cpp
//  zoj2974
//
//  Created by cfhaiteeh on 14/03/2018.
//  Copyright © 2018 cfhaiteeh. All rights reserved.
//

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
int n,m;
struct Matrix{
    double mat[23][23];
    
};
double ai[23];
int T;
Matrix mat;
void init(){
    memset(mat.mat,0,sizeof(mat.mat));
    scanf("%d",&n);
    for(int i=1;i<=n;i++)scanf("%lf",&ai[i]);
    for(int i=1;i<=n;i++){
        int a,b;
        scanf("%d",&a);
        if(a==0){
            mat.mat[i][i]=1;
            continue;
        }
        for(int j=1;j<=a;j++){
            double t=1.0/a;
            scanf("%d",&b);
            mat.mat[i][b]=t;
        }
    }
    scanf("%d",&m);
}
Matrix MUL(Matrix a,Matrix b){
    Matrix c;
    memset(c.mat,0,sizeof(c.mat));
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            for(int k=1;k<=n;k++){
                c.mat[i][j]=c.mat[i][j]+a.mat[i][k]*b.mat[k][j];
            }
        }
    }
    return c;
}
Matrix poww(Matrix x,int k){
    Matrix ans;
    memset(ans.mat,0,sizeof(ans.mat));
    for(int i=1;i<=n;i++)ans.mat[i][i]=1;
    while(k>0){
        if(k&1)
            ans=MUL(ans, x);
        x=MUL(x,x);
        k/=2;
    }
    return ans;
}
double ans[23];
void play(){
    memset(ans,0,sizeof(ans));
    Matrix _a=poww(mat,m);
  
    for(int j=1;j<=n;j++){
        for(int k=1;k<=n;k++){
            ans[j]=ans[j]+ai[k]*_a.mat[k][j];
        }
    }
}
void pri(){
    bool fir=1;
    for(int i=1;i<=n;i++)
    {
        if(!fir)printf(" ");
        fir=0;
        printf("%.2f",ans[i]);
    }
    printf("\n");
}
int main(int argc, const char * argv[]) {
    // insert code here...
    
    scanf("%d",&T);
    
    while(T--){
        init();
        play();
        pri();
    }
    return 0;
}

ZOJ Problem Set - 2317 Nice Patterns Strike Back

飞机票http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=1317

题意很清楚,就是给你n*m矩阵,求其中不包括2*2一样颜色的方案数ans%P

因为n很大,m很小,所以很容易想到肯定要对n进行一种特殊的处理。因为第i行和第i-1行的状态有关。所以可以用第i-1行的状态来求第i行,容易想到矩阵快速幂,但是矩阵的构造有点复杂,因为一行一共有2^m=t种状态,所以可以用状态压缩,则我们可以t*t的矩阵,其中matrix i_j表示第k行的状态和k+1行在状态为i和j的时候是否符合题意。现在我们就可以矩阵快速幂了,令A=[1,1....1]表示初始状态,则A*matrix为第二种状态,其中所有元素所和即为答案,所以第n中状态就是A*(matrix)^(n-1) 对后者进行矩阵快速幂,求出答案(用到java大数

import java.math.BigInteger;
import java.util.*;
public class Main {
	
	public static BigInteger two;
	public static int len;
	public static int P;
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sca=new Scanner(System.in);
		int T=sca.nextInt();
		two=new BigInteger("2");
		while(T>0){
			T--;
			BigInteger n=sca.nextBigInteger();
			n=n.subtract(BigInteger.ONE);
			int m=sca.nextInt();
			 P=sca.nextInt();
			len=(int) Math.pow(2, m);
			if(n.compareTo(BigInteger.ZERO)==0){
				System.out.println(len);
				if(T!=0)
				System.out.println();
				continue;
			}
			Matrix a=new Matrix();
			for(int i=1;i<=len;i++){
				for(int j=1;j<=len;j++){
					int l=i-1;
					int r=j-1;
					String str1=Integer.toBinaryString(l);
					String str2=Integer.toBinaryString(r);
					while(str1.length()!=m)str1="0"+str1;
					while(str2.length()!=m)str2="0"+str2;
					str1="0"+str1;
					str2="0"+str2;
					boolean flag=true;
					for(int k=1;k<m;k++){
						int ok=1;
						if(str1.charAt(k)!=str1.charAt(k))ok=0;
						if(str1.charAt(k)!=str2.charAt(k))ok=0;
						if(str1.charAt(k)!=str1.charAt(k+1))ok=0;
						if(str1.charAt(k)!=str2.charAt(k+1))ok=0;
						if(ok==1){
							flag=false;
							break;
						}
						
					}
					if(flag){
						a.mat[i][j]=1;
					}
					else{
						a.mat[i][j]=0;
					}
				}
			}
			
				Matrix ans=Poww(a,n);
				int as=0;
				for(int i=1;i<=len;i++){
					for(int j=1;j<=len;j++){
						as=(as+ans.mat[i][j])%P;
					}
				}
				System.out.println(as);
				if(T!=0)
				System.out.println();
		}
	}
	public static Matrix MUL(Matrix a,Matrix b){
		Matrix c=new Matrix();
		for(int i=1;i<=len;i++){
			for(int j=1;j<=len;j++){
				for(int k=1;k<=len;k++){
					c.mat[i][j]=(c.mat[i][j]+a.mat[i][k]*b.mat[k][j])%P;
				}
			}
		}
		return c;
	}
	public static Matrix Poww(Matrix a,BigInteger b){
	    Matrix ans=new Matrix();
	    for(int i=1;i<=len;i++)ans.mat[i][i]=1;
	    while(b.compareTo(BigInteger.ZERO)!=0){
	        if(b.mod(two).compareTo(BigInteger.ONE)==0)
	        	ans=MUL(ans,a);
	        a=MUL(a, a);
	        b=b.divide(two);
	    }
	    return ans;
	}

}
class Matrix{
	public  int mat[][]=new int[35][35];
	public Matrix(){
		for(int i=1;i<=32;i++){
			for(int j=1;j<=32;j++){
				mat[i][j]=0;
			}
		}
	}
	 })

 

ZOJ Problem Set - 1842 Prime Distance

飞机票:http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=842

用素数快速筛选法,因为r-l<=1000000,所以只要筛选[l,r]之间的素数,对于1要特殊处理,我是直接当l=1时,l++,因为我的算法是筛[l,r),所以,对于给定的r,要r++;然后就是直接暴力求解了。

#include<iostream>
#include<stdio.h>
typedef long long ll;
using namespace std;
bool is_prime_small[1000009];
bool is_prime[1000009];
///对区间[a,b)内的整数进行筛选。 is_prime[i-a]=true <=> i是素数

void segment_sieve(ll a,ll b)
{
    for(int i=0;(ll)i*i<b;i++)
        is_prime_small[i]=true;
    for(int i=0;i<b-a;i++)
        is_prime[i]=true;
    for(int i=2;(ll)i*i<b;i++)
        if(is_prime_small[i])
        {
            for(int j=2*i;(ll)j*j<b;j+=i)
                is_prime_small[j]=false;
            for(ll j=max(2LL,(a+i-1)/i)*i;j<b;j+=i)
                is_prime[j-a]=false;
        }
}
int main()
{
    ll a,b,c;
    while(scanf("%lld%lld",&a,&b)!=EOF){
        b++;
        if(a==1)a++;
        segment_sieve( a, b);
        c=b-a;
        ll a1,a2,b1,b2,c1,c2;
        c1=1000000;
        c2=-1;
        ll bef=0;
        
        for(int i=0;i<c;i++)
        {
            if(is_prime[i]) {
                
                if(bef==0){
                    bef=a+i;
                    continue;
                }
                else{
                    ll p=i+a-bef;
                    if(p<c1){
                        c1=p;
                        a1=bef;
                        b1=i+a;
                    }
                    if(p>c2){
                        c2=p;
                        a2=bef;
                        b2=i+a;
                    }
                    bef=i+a;
                }
            }
        }
        if(c2==-1){
            printf("There are no adjacent primes.\n");
        }
        else{
            printf("%lld,%lld are closest, %lld,%lld are most distant.\n",a1,b1,a2,b2);
        }
    }
    return 0;
}

ZOJ Problem Set - 1505 Solitaire

飞机票:http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=505

直接进行BFS就行,需要注意的是状态转移,对四个点进行排序,然后按100,10000,1000000的系数来判断是否访问过(剪枝),因为一个点可以上下左右跳一格或两格如果一格可以则不进行两格(剪枝)//

//  main.cpp
//  zoj1505
//
//  Created by cfhaiteeh on 12/03/2018.
//  Copyright © 2018 cfhaiteeh. All rights reserved.
//

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <queue>
#include <map>
#include <algorithm>
using namespace std;
struct he{
    int ai[9];
    int val;
    int t;
};
int bi[9];
int ci[9];
map<int,int> _M;
int _map[9][9];
int rn[9];
int cn[9];
int toans;
bool getdir(int r,int c){
    if(r<1||r>8)return 0;
    if(c<1||c>8)return 0;
    if(_map[r][c]==1)return 0;
    return 1;
}
int cm[5];
int cr[]={-1,-2,1,2,0,0,0,0};
int cc[]={0,0,0,0,-1,-2,1,2};
int getcm(){
    sort(cm+1,cm+1+4);
    return cm[1]*1000000+cm[2]*10000+cm[3]*100+cm[4];;
}
bool BFS(){
    queue<he> Q;
    he ne;
    for(int i=1;i<=8;i++)ne.ai[i]=bi[i];
    for(int k=2;k<=8;k+=2){
        cm[k/2]=ne.ai[k-1]*10+ne.ai[k];
    }
    int ct=getcm();
    _M[ct]=1;
    ne.val=8;
    ne.t=ct;
    Q.push(ne);
   
    while(!Q.empty()){
        he c=Q.front();
        Q.pop();
        if(c.t==toans)return 1;
        if(c.val==0)continue;
    
        memset(_map,0,sizeof(_map));
        for(int i=1;i<=8;i+=2){
            int row=c.ai[i];
            int col=c.ai[i+1];
            _map[row][col]=1;
           
        }
        for(int i=1;i<=8;i+=2){
            int row=c.ai[i];
            int col=c.ai[i+1];
    
            int st=0;
            for(int j=0;j<8;j++){
                if(getdir(row+cr[j],col+cc[j])){
                    rn[++st]=row+cr[j];
                    cn[st]=col+cc[j];
                    if(j%2==0)
                    {
                        j++;
                    }
                }
            }
       
            for(int j=1;j<=st;j++){
                
                    he nex;
                    for(int k=1;k<=8;k++){
                        nex.ai[k]=c.ai[k];
                        
                    }
                    nex.ai[i]=rn[j];
                    nex.ai[i+1]=cn[j];
                    nex.val=c.val-1;
                for(int k=2;k<=8;k+=2){
                    cm[k/2]=nex.ai[k-1]*10+nex.ai[k];
                }
             
                int ct=getcm();
                if(_M[ct]==1)continue;
                nex.t=ct;
                _M[ct]=1;
                Q.push(nex);
            }
        }
       
    }
    return 0;
}
void init(){
    _M.clear();
    for(int i=2;i<=8;i++)scanf("%d",&bi[i]);
    for(int i=1;i<=8;i++)scanf("%d",&ci[i]);
    
    for(int k=2;k<=8;k+=2){
        cm[k/2]=ci[k-1]*10+ci[k];
    }
   
    int ct=getcm();
    toans=ct;
 
}
int ans;
void play(){
    ans=BFS();
}
void pri(){
    if(ans)printf("YES\n");
    else printf("NO\n");
}
int main() {
    // insert code here...
    while(scanf("%d",&bi[1])!=EOF){
        init();
        play();
        pri();
    }
    return 0;
}

ZOJ Problem Set - 2371 Three powers

飞机票:http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=1347

易知对于3^i次方 3^0+3^1+....3^(i-1)<3^i 且对于k项,一共有2^k-1(不包括空集,对空集进行特殊处理) 所以当n==2^k-1时,则前k项都包括,当n>2^k-1&&n<2^(k+1)-1时,包含第k+1项,将n-(2^k-1)后就是k+1项的事情了,领n1=n-(2^k-1),

n2=n1-1时,此时k+1已经处理了,则n2又变为原来的n,进行递归求解。

import java.math.BigInteger;
import java.util.*;

public class Maintf {
	public static BigInteger fac[];
	public static ArrayList<Integer> al;
	public static void DFS(BigInteger x){
		if(x.compareTo(BigInteger.ZERO)==0)return;
		for(int i=1;i<64;i++){
			if(x.compareTo(fac[i])==0){
				for(int j=i;j>=1;j--){
					al.add(j);
				}
				return;
			}
			if(x.compareTo(fac[i])>0&&x.compareTo(fac[i+1])<0){
				x=x.subtract(fac[i]).subtract(BigInteger.ONE);
				al.add(i+1);
				DFS(x);
				return;
			}
		}
	}
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		fac=new BigInteger[123];
		fac[1]=BigInteger.ONE;
		BigInteger two=new BigInteger("2");
		for(int i=2;i<=64;i++){
			fac[i]=fac[i-1].multiply(two).add(BigInteger.ONE);
		
		}
		BigInteger pow3[]=new BigInteger[123];
		pow3[1]=BigInteger.ONE;
		BigInteger three=new BigInteger("3");
		for(int i=2;i<=64;i++){
			pow3[i]=pow3[i-1].multiply(three);
		}
		al=new ArrayList<>();
		Scanner sca=new Scanner(System.in);
		while(sca.hasNext()){
			
			BigInteger n=sca.nextBigInteger();
			if(n.compareTo(BigInteger.ZERO)==0)break;
			if(n.compareTo(BigInteger.ONE)==0){
				System.out.println("{ }");
				continue;
			}
			al.clear();
			n=n.subtract(BigInteger.ONE);
			
			DFS(n);
			
			System.out.print("{");
			for(int i=al.size()-1;i>=0;i--){
				System.out.print(" "+pow3[al.get(i)]);
				if(i!=0)System.out.print(",");
				else System.out.print(" ");
			}
			System.out.println("}");
		}
	}

}

 

ZOJ Problem Set - 2058 The Archaeologist's Trouble II

飞机票:http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=1058

题意:就是给你n行,第i行有i个字符,字符可以是'@','*','?',其中需要确定?的值,根据题目的4中限制,使得得到@最多,或则@最少,输出这个值。

分析:看一下这4种类型可以知道,假设为2行,第一行一个字符,第二行两个,所以我们可以知道无论第一行是什么,第二行都必须是@*或则*@,这样的话我们就知道,假设在第k行,有k个字符,如果第j个字符是@,那么第j-1是*,j+1也是*,然后根据j-1和j+1可以继续第k行剩下的数据。所以,假设第k行都是?,那么如果k%2==0,那么@和*只能平分。反之,设得到@最多为MAX,最少为MIN,那么,MAX多加个1,因为有k/2个*和k/2+1个@,MIN 的话就是k/2个@和k/2+1个*。如果第k行第i个是*,那么可知包含*的话,前面有i个字符,后面有af=k-i+1个字符,那么我们就可以知道MAX和MIN就都得有i/2个和af/2个,因为第i个是*,所以不用管是否奇偶。反之,一样MAX和MIN就都得有i/2个和af/2个,但是这里就得再考虑,如果i是奇数,那么我们得再加个1,因为i也是,如果af是奇数,同理,但是我们这里多记了1次i这个位置,所以都要减1。最后输出MAX和MIN就好了,啪啪啪就可以AC了

/*
Author:Chieh
Because Of Coding
*/
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <vector>
#include <queue>
#include <map>
#include <stack>
#define LL long long
#define INF 1e9
#define EPS 1e-9
using namespace std;
const int maxn=123;
char ch[maxn];
int n;
int MAX,MIN;
void init()
{
    MAX=0;
    MIN=0;
    for(int i=1; i<=n; i++)
    {
        scanf("%s",ch+1);
        bool flag=1;
        for(int j=1; j<=i; j++)
        {
            int af=i-j+1;
            if(ch[j]=='*')
            {
                flag=0;
            }
            if(ch[j]=='@')
            {
                if(j%2==1)
                {
                    MAX++;
                    MIN++;
                }
                if(af%2==1)
                {
                    MAX++;
                    MIN++;
                }
                MAX-=1;
                MIN-=1;
                flag=0;
            }
            if(!flag)
            {
                MAX+=j/2;
                MIN+=j/2;
                MAX+=af/2;
                MIN+=af/2;
                break;
            }
        }

        if(flag)
        {
            MAX+=i/2;
            MIN+=i/2;
            if(i%2==1)MAX++;
        }
    }
}

void play()
{
    printf("%d %d\n",MAX,MIN);
}

int main()
{
   
    while(scanf("%d",&n)&&n>0)
    {
        init();
        play();
    }
//    cout << "Hello world!" << endl;
    return 0;
}

ZOJ Problem Set - 2013 Labyrinth

飞机票:http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=1013

题意:起先看的很迷糊啊。就是给你C*R的矩阵,然后矩阵里面是#(不可走)或.(可走),然后Input最后一句话每两个点之间最多正好就一条路,所以说路径不包含圈,所以是棵树,然后Output说输出两个点之间最长的长度是多少。

分析:知道题意的话就很简单了。可以用树形DP ,假设当前的节点为fa,如果它没有子节点,那么它就是叶子节点,那么直接返回1,如果它有一个子节点,那么最长就是子节点返回的值,用这个值更新最大值,然后返回最大值+1到fa的父节点,如果它有多余两个子节点。那么从它的子节点选择2个最大子节点,然后相加,更新最大值,再把最大值的一个子节点+1返回到fa的父节点,这样最后的最大值就是我们要求的最大路径了。啪啪啪就可以AC了。

/*
Author:Chieh
Because Of Coding
*/
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <vector>
#include <map>
#include <stack>
#include <queue>
#define LL long long
#define INF 1e9
#define EPS 1e-9
using namespace std;
const int maxn=1234;
bool ai[maxn][maxn];
int T;
int n,m;
char ch[maxn];
void init()
{
    scanf("%d%d",&m,&n);
    memset(ai,0,sizeof(ai));
    for(int i=1; i<=n; i++)
    {
        scanf("%s",ch+1);
        for(int j=1; j<=m; j++)
        {
            if(ch[j]=='.')ai[i][j]=1;
        }
    }
}
bool cmp(int a,int b)
{
    return a>b;
}
bool vis[maxn][maxn];
int MAX;
int c1[]= {1,0,-1,0};
int c2[]= {0,1,0,-1};
int DFS(int x,int y)
{
    int l1=-1,l2=-1;
    for(int i=0; i<4; i++)
    {
        int nx=x+c1[i];
        int ny=y+c2[i];
        if(!ai[nx][ny])continue;
        if(vis[nx][ny])continue;
        vis[nx][ny]=1;
        int q=DFS(nx,ny);
        if(l1==-1){
            l1=q;

        }
        else{
            if(q>l1){
                l2=l1;
                l1=q;
            }
            else if(q>l2){
                l2=q;
            }
        }
    }
    if(l1==-1)
    {
        return 1;
    }
    if(l2==-1)
    {
        MAX=max(MAX,l1);
        return l1+1;
    }
    MAX=max(MAX,l1+l2);
    return l1+1;

}
void play()
{
    MAX=0;
    memset(vis,0,sizeof(vis));
    for(int i=1; i<=n; i++)
    {
        for(int j=1; j<=m; j++)
        {
            if(!vis[i][j])
            {
                vis[i][j]=1;
                if(!ai[i][j])continue;
                DFS(i,j);
            }
        }
    }
    printf("Maximum rope length is %d.\n",MAX);

}
int main()
{

    scanf("%d",&T);
    while(T--)
    {
        init();
        play();
    }
    //cout << "Hello world!" << endl;
    return 0;
}