A-牛牛的DRB迷宫I
题面：
解题思路：本题容易误导（本人觉得）使用BFS来写，求出全部的方法种数，但很可惜，超内存了，
正确的思路：采用简单DP处理，先用一个二维数组存储输入的字符矩阵。使用两层for循环，遍历整个数组，在遍历的同时，同属判断该位置上的字符是什么，根据题目要求，当为‘R’时，向右移动即可用，%25Max_n%3B)
，计算从该点到下一个点全部的方法数，同理，为‘D时，可用%25Max_n%3B)
求出‘，当为’B‘时，即将以上两个操作都进行一次即可。最后，输出dp[n][m]即可。
#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<stdio.h>
#include<math.h>
#include<string.h>
#include<vector>
#define ll long long
using namespace std;
int cmp(int a,int b){
return a>b;
}
ll read(){
ll x=0,w=1;
char ch=0;
while(ch<'0'||ch>'9'){
if(ch=='-')
w=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9'){
x=x*10+ch-'0';
ch=getchar();
}
return w*x;
}//快读算法
bool IsPrimeNumber(int n){//判断该数是不是素数
if (n==2){
return true;
}
if (n%2==0||n==1){
return false;
}
int sqrtn=(int)sqrt((double)n);
bool flag=true;
for (int i=3;i<=sqrtn;i+=2){
if (n%i==0){
flag=false;
}
}
return flag;
}//快速判断某个数是不是素数的算法
void reversea(int t[],int n){
int temp[n];
for(int i=0;i<n;i++){
temp[i]=t[i];
}
int r=0;
for(int i=n-1;i>=0;i--){
t[r++]=temp[i];
}
}//数组逆序函数
const int Max_n=1e9+7;
int main(){
/*简单DP来写*/
int n,m;
cin>>n>>m;
char ptr[511][511];
int dp[511][511];
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
cin>>ptr[i][j];
}
}
dp[1][1]=1;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
if(ptr[i][j]=='D'){
dp[i+1][j]=(dp[i+1][j]+dp[i][j])%Max_n;
}else if(ptr[i][j]=='R'){
dp[i][j+1]=(dp[i][j+1]+dp[i][j])%Max_n;
}else{
dp[i+1][j]=(dp[i+1][j]+dp[i][j])%Max_n;
dp[i][j+1]=(dp[i][j]+dp[i][j+1])%Max_n;
}
}
}
cout<<dp[n][m]<<endl;
return 0;
}
F-牛牛的Link Power I
题面：
解题思路：利用for循环遍历该字符串，同时，用变量num给1出现的次数计数，同时用当前1的个数作为贡献值，当遇到0时，该位置上的贡献值等于前面1的个数，元素值为1的位置上的贡献值的总和即为本题的正解。
#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<stdio.h>
#include<math.h>
#include<string.h>
#include<vector>
#define ll long long
using namespace std;
int cmp(int a,int b){
return a>b;
}
ll read(){
ll x=0,w=1;
char ch=0;
while(ch<'0'||ch>'9'){
if(ch=='-')
w=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9'){
x=x*10+ch-'0';
ch=getchar();
}
return w*x;
}//快读算法
bool IsPrimeNumber(int n){//判断该数是不是素数
if (n==2){
return true;
}
if (n%2==0||n==1){
return false;
}
int sqrtn=(int)sqrt((double)n);
bool flag=true;
for (int i=3;i<=sqrtn;i+=2){
if (n%i==0){
flag=false;
}
}
return flag;
}//快速判断某个数是不是素数的算法
//========================
const long N = 200000;
long prime[N] = {0},num_prime = 0;
void SE(){
int isNotPrime[N] = {1, 1};
for(long i = 2 ; i < N ; i ++){
if(! isNotPrime[i])//isNotPrime==0
prime[num_prime ++]=i;
for(long j = 0 ; j < num_prime && i * prime[j] < N ; j ++){
isNotPrime[i * prime[j]] = 1;
if( !(i % prime[j] ) ){
break;
}
}
}
}
//===========================欧拉筛，计算前 n 个素数
int b[100005];//存储的是数据 n 的全部因子
int z=0;
void app(int n){
int a=n;
memset(b,0,sizeof(b));
scanf("%d",&a);
z=0;
for(int i=1;i<=sqrt(a);i++) {
if(a%i==0) {
b[z]=i;
z++;
int g=a/i;
if(g!=i){
b[z]=g;
z++;
}
}
}
for(int i=0;i<z;i++) {
printf("%d ",b[i]);
}
}
const int mod=1e9+7;
int main(){
int n;
string ptr;
cin>>n;
cin>>ptr;
int now=0,a=0,y=0;
for(int i=0;i<n;i++){
if(ptr[i]=='1'){
a++;
now=now+y;
now=now%mod;
y=y+a;
y=y%mod;
}else if(ptr[i]=='0'){
y=y+a;
y=y%mod;
}
}
cout<<now%mod<<endl;
return 0;
}
H-牛牛的k合因子数
题面：
解题思路：利用“for”循环，遍历数字1-n，在遍历的同时，判断数字 i 是 几合因子数，并用num[i]作为记录，代表的是i合因子数的数量。
#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<stdio.h>
#include<math.h>
#include<string.h>
#include<vector>
#define ll long long
using namespace std;
const int MAXN = 1e6 + 10;
int cmp(int a,int b){
return a>b;
}
ll read(){
ll x=0,w=1;
char ch=0;
while(ch<'0'||ch>'9'){
if(ch=='-')
w=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9'){
x=x*10+ch-'0';
ch=getchar();
}
return w*x;
}//快读算法
//==============================================================
bool isPrime( ll num ){
return 1 ;
if(num %6!= 1&&num %6!= 5)
return 0 ;
int tmp =sqrt(num);
for(int i= 5; i <=tmp; i+=6 )
if(num %i== 0||num %(i+ 2)==0)
return 0 ;
return 1 ;
}
//============================================================
int num(ll n){//分解出这个数 (n) 的所有的因子
int num=0;//计算因子中所合合数的数量
if(!isPrime(n)){
num++;//本身是因子且本身是合数
}
for(int i=2;i<=sqrt(n);i++){
if(n%i==0){
if(i==sqrt(n)&&n/i==i&&!isPrime(i)){
num++;
}else{
if(!isPrime(i)){
num++;
}
if(!isPrime(n/i)){
num++;
}
}
}
}
return num;
}
ll cnt[MAXN];
int main(){
int n,m,x;
cin>>n>>m;
for(int i=1;i<=n;i++){
cnt[num(i)/*返回的是 i 这个数的因数中合数因子的个数*/]++;
}
for(int i=0;i<m;i++){
cin>>x;
cout<<cnt[x]<<endl;
}
return 0;
}
京公网安备 11010502036488号