A.全 1 子矩阵

题意:

给出一个n×m的矩阵,该矩阵是否存在有且仅有一个全为1的子矩阵

solution:

输入记录第一个为1的下标(x1,y1),从后往前遍历记录最后一个为1的下标(x2,y2),将俩个下标记为左上角和右下角,只需查找这个矩阵是否全为1,并且1的个数等于n×m的矩阵的1的个数


B.组合数

题意:

图片说明

solution:

题目用c++或者java都行,但是java比较慢,用c++的long double也能过

这是c++的做法:

#include <bits/stdc++.h>
using namespace std;
#define  ll unsigned long long
ll inf = 1e18;
ll n , k , i;
int main()
{
    while(~scanf("%lld%lld",&n,&k))
    {
        k = min(k, n-k);
        long double ans = 1;
        for(i=1;i<=k;i++)
        {
            ans = ans*(n-i+1)/i;
            if(ans > inf)
                break;
        }
        if(ans > inf){
            printf("%lld\n",inf);
            continue ;
        }
        printf("%lld\n",(long long)ans);
    }
    return 0;
}

这是java的做法:

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

public class Main {
   public static void main(String[] args) {
       Scanner input = new Scanner(System.in);
       BigInteger ans1 = new BigInteger("1000000000000000000");
       BigInteger one = new BigInteger("1");
       while(input.hasNext())
       {
           int n = input.nextInt();
           int k = input.nextInt();
           BigInteger nn = BigInteger.valueOf(n);
           if(n - k < k)
               k = n - k;
           int flag = 0;
           BigInteger ans = new BigInteger("1");
           for(long i=1;i<=k;i++)
           {
               BigInteger ii = BigInteger.valueOf(i); 
               ans = ans.multiply(nn.subtract(ii).add(one));
               ans = ans.divide(ii);
               if(ans.compareTo(ans1) == 1) {
                   flag = 1;
                   break;
               }
           }
           if(flag == 1){
               System.out.println(ans1);
               continue ;
           }
           System.out.println(ans);
       }
   }
}

E.Numbers

题意:

给出一个字符串,问你是否能将这个字符串拆成每个部分的数字都是[0,99]范围内的数字并且不重复,输出有多少种方案

solution:

深搜

#include <bits/stdc++.h>
using namespace std;
#define ll unsigned long long
int a[55],ans = 0,n;
int flag[105];
void dfs(int pos)
{
    if(pos >= n + 1){
        ans++;
        return ;
    }
    if(pos <= n){
        int k = a[pos];
        if(flag[k] == 0){
            //cout<<k<<endl;
            flag[k] = 1;
            dfs(pos+1);
            flag[k] = 0;
        }
    }
    if(pos + 1 <= n){
        int k = a[pos]*10 + a[pos + 1];
        if(flag[k] == 0 && k >= 10){
            //cout<<k<<endl;
            flag[k] = 1;
            dfs(pos+2);
            flag[k] = 0;
        }
    }
    return ;

}
int main()
{
    string s;
    while(cin>>s)
    {
        ans = 0;
        memset(flag,0,sizeof(flag));
        n = s.length();
        for(int i=1;i<=n;i++)
        {
            a[i] = s[i-1]-'0';
        }
        dfs(1);
        cout<<ans<<endl;
    }
    return 0;
}