Chieh's Blog

Because Of Coding

关于Visual Studio 配置 opencv 出现的问题及解决方法

  1. 关于opencv库的导入 链接:https://blog.csdn.net/u011880112/article/details/79275501,其中的opencv_worldxxx.lib 改为下载opencv 下build/x64/v15下的opencv_worldxxx.lib
  2. 找不到opencv_world320d.dll的问题 链接:https://blog.csdn.net/lqtcsq/article/details/80314465 
  3. OpenCV 编译程序时未加载PDB文件 https://blog.csdn.net/xiao_yao_ke/article/details/71104687

Hadoop安装常见问题

两个standby 强制启动一个

出现0datanode 删除tmp文件夹,重新启动

zoo.cfg问题  关闭防火墙

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 - 1788 Quad Trees

根据题意模拟即可

//
//  main.cpp
//  zoj1788
//
//  Created by cfhaiteeh on 13/03/2018.
//  Copyright © 2018 cfhaiteeh. All rights reserved.
//

#include <iostream>
#include <cstring>
#include <cmath>
#include <cstdio>
#include <queue>
using namespace std;
const int maxn=1234567;
struct he{
    int x1,y1,x2,y2;
};
int ai[maxn];
int mat[513][513];
int T,n;
void init(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            scanf("%d",&mat[i][j]);
}
int st;
bool getCmp(int x1,int y1,int x2,int y2){
     int cmp=mat[x1][y1];
    for(int i=x1;i<=x2;i++){
        for(int j=y1;j<=y2;j++){
            if(mat[i][j]!=cmp)return 0;
        }
    }
    return 1;
}
queue<he> Q;
void pushQ(int x1,int x2,int y1,int y2){
  
    he c;
    c.x1=x1;
    c.x2=x2;
    c.y1=y1;
    c.y2=y2;
    Q.push(c);
}
void BFS(){
    he fir;
    fir.x1=1;
    fir.y1=1;
    fir.x2=n;
    fir.y2=n;
    st=0;
    Q.push(fir);
    while(!Q.empty()){
        he c=Q.front();
        Q.pop();
        bool flag=getCmp(c.x1, c.y1, c.x2, c.y2);
        if(flag){
            ai[++st]=0;
            ai[++st]=mat[c.x1][c.y1];
        }
        else{
            ai[++st]=1;
            int mid1=(c.x1+c.x2)/2;
            int mid2=(c.y1+c.y2)/2;
            pushQ(c.x1, mid1, c.y1, mid2);
            pushQ(c.x1,mid1,mid2+1,c.y2);
            pushQ(mid1+1, c.x2, c.y1, mid2);
            pushQ(mid1+1,c.x2,mid2+1,c.y2);
        }
       
    }
}
char ans[maxn];
int ci[]={1,2,4,8};
char getChar(int t){
    int s=0;
    for(int i=0;i<4;i++){
        s=s+ai[t]*ci[i];
        t--;
        if(t==0)break;
    }
    if(s>10){
        s-=10;
        return s+'A';
    }
    return s+'0';
}
int now;
void play(){
    if(!Q.empty()){
        Q.pop();
    }
    BFS();
    now=0;
    for(int i=st;i>=1;i-=4){
        ans[++now]=getChar(i);
        
    }
}
void pri(){
    for(int i=now;i>=1;i--)printf("%c",ans[i]);
    printf("\n");
}
int main() {
    // insert code here...
    scanf("%d",&T);
    while(T--){
        init();
        play();
        pri();
    }
    return 0;
}

ZOJ Problem Set - 2418 Matrix

//
//  main.cpp
//  zoj2418
//
//  Created by cfhaiteeh on 13/03/2018.
//  Copyright © 2018 cfhaiteeh. All rights reserved.
//

#include <iostream>
#include <cmath>
#include <queue>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define LL long long
#define  INF 1e9
using namespace  std;
int n;
int MIN;
int mat[8][8];
int ai[8][8];
void init(){
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            scanf("%d",&mat[i][j]);
    memset(ai,0,sizeof(ai));
}
void DFS(int depth){
    if(depth==n+1){
        int MAX=0;
        for(int i=1;i<=n;i++)
            MAX=max(ai[n][i],MAX);
        MIN=min(MIN,MAX);
        return;
    }
    for(int i=1;i<=n;i++){
        int st=1;
        int t=i;
        while(st<=n){
            ai[depth][st]=mat[depth][t];
            t++;
            st++;
            if(t==n+1)t=1;
        }
        for(int j=1;j<=n;j++){
            ai[depth][j]+=ai[depth-1][j];
        }
        DFS(depth+1);
    }
}
int ans;
void play(){
    MIN=1e9;
    DFS(1);
    ans=MIN;
}
void pri(){
    printf("%d\n",ans);
}

int main() {
    while(scanf("%d",&n)!=EOF){
        if(n==-1)break;
        init();
        play();
        pri();
    }
    return 0;
}