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; }