A 牛牛的DRB迷宫I
思路：暴力dfs，时间复杂度O(2^n)超时，改dp。
定义状态：dp[i][j]表示起点(1,1)到坐标(i,j)的路径条数。
边界：因为只能向右或者向下走，所以dp[1][i]和dp[i][1]都可以计算出来，dp[1][1]=1。
状态转移方程：dp[i][j]=dp[i][j-1]+dp[i-1][j]; （不带约束，具体看代码）
代码：
#include<iostream>
using namespace std;
const int mod = 1e9 +7;
int n,m;
char maze[100][100];
int dp[100][100]={0};
/* dp[i][j]:从起点(1,1)到(i,j)的路径条数 */
int main(){
cin>>n>>m;
dp[1][1]=1;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
scanf(" %c",&maze[i][j]);
}
}
for(int i=2;i<=n;i++){
if(maze[i-1][1]=='B'||maze[i-1][1]=='D')dp[i][1]=dp[i-1][1];
}
for(int i=2;i<=m;i++){
if(maze[1][i-1]=='B'||maze[1][i-1]=='R')dp[1][i]=dp[1][i-1];
}
for(int i=2;i<=n;i++){
for(int j=2;j<=m;j++){
if(maze[i][j-1]=='B'||maze[i][j-1]=='R')
dp[i][j]=(dp[i][j]+dp[i][j-1])%mod;
if(maze[i-1][j]=='B'||maze[i-1][j]=='D')
dp[i][j]=(dp[i][j]+dp[i-1][j])%mod;
dp[i][j]=dp[i][j-1]+dp[i-1][j];
}
}
cout<<dp[n][m]%mod;
}
C 牛牛的数组越位
思路：题目虽然很长，但是仔细研究一下发现并不难，简单模拟一下即可。
代码：
#include<iostream>
#include<cstring>
using namespace std;
typedef long long int ll;
const int maxn = 1e3 + 10;
ll a[maxn][maxn];
int main(){
int t;cin>>t;
while(t--){
int n,m,p;cin>>n>>m>>p;
memset(a,0,sizeof(a));
bool ub=false,re=false;
while(p--){
int x,y,v;cin>>x>>y>>v;
if(x<0||y<0||x>=n||y>=m)ub=true;
int k=m*x+y;
int fx=k/m;
int fy=k%m;
if(fx<0||fy<0||fx>=n||fy>=m)re=true;
else a[fx][fy]=v;
}
if(re&&ub)cout<<"Runtime error"<<endl;
else{
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
cout<<a[i][j]<<" ";
}
cout<<endl;
}
if(ub)cout<<"Undefined Behaviour"<<endl;
else cout<<"Accepted"<<endl;
}
}
}
D 牛牛与二叉树的数组存储
思路：题目也很长但是也不难，模拟一下就行了。
代码:
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn = 1e5+10;
int n;
struct node{
int data,pos;
}a[maxn],b[maxn];
bool cmp(node a,node b){
return a.data<b.data;
}
int main(){
cin>>n;
int count=0,root=0;
memset(a,-1,sizeof(a));
memset(b,-1,sizeof(b));
for(int i=1;i<=n;i++){
cin>>a[i].data;
a[i].pos=i;
b[i].data=a[i].data;b[i].pos=a[i].pos;
if(i==1)root=a[i].data;
if(a[i].data!=-1)count++;
}
cout<<"The size of the tree is "<<count<<endl;
cout<<"Node "<<root<<" is the root node of the tree"<<endl;
sort(a+1,a+n+1,cmp);
int cnt=1;
for(int i=1;i<=n;i++){
if(a[i].data!=-1)
cout<<"The father of node "<<cnt++<<" is "<<b[a[i].pos/2].data<<", the left child is "<<b[a[i].pos*2].data<<", and the right child is "<<b[a[i].pos*2+1].data<<endl;
}
}
H 牛牛的k合因子数
思路：
先O(nlogn)筛法，求出prime[i]判断每个数是否是素数，然后枚举[1,n]求每个数因子直接用prime[i]判断该数是否是合数，时间复杂度O(n^2) --》 超时。
其实在求筛法的时候就可以求解答案，因为我们知道素数的因子为合数的个数是0(1本身，本身还是素数)，合数的因子为合数的个数起码是1因为1本身是因子，而本身又是合数，在筛法的时候我们每找到一个合数让他的倍数因子个数++(这里指因子为合数)，因为他的倍数一定可以由当前这个数组成，而当前这个数又是合数。。。。。具体看代码。
代码：
#include<iostream>
#include<cstring>
using namespace std;
typedef long long int ll;
int n,m;
const int maxn = 1e5+10;
bool prime[maxn];
int f[maxn],cnt[maxn];
/* cnt[i]:表示数字i的因子中为合数的数量 f[i]:[1,n]中各数字的因子为合数且数量为i的数量 */
void init(){
memset(prime,true,sizeof(prime));
for(int i=2;i<=n;i++){
if(prime[i]==true){
for(int j=i+i;j<=n;j+=i){
prime[j]=false;
}
}else{
for(int j=i;j<=n;j+=i)
cnt[j]++;
}
f[cnt[i]]++;//统计当前这个数的因子中为合数的数量
}
}
int main(){
cin>>n>>m;
init();
while(m--){
int k;cin>>k;
cout<<f[k]<<endl;
}
}
F 牛牛的Link Power I
思路：
cnt统计1的个数，sum统计前面所有的1同时移动到当前位置的距离，ans表示答案。
没找到一个1cnt++，然后sum每次移动cnt次，表示前面n个1同时向后面移动，每次又找到一个1更新答案，再把这个1加进来，继续扫描，时间复杂度O(n)。
代码：
#include<iostream>
using namespace std;
typedef long long ll;
const int maxn = 1e5 + 10;
char a[maxn];
int cnt,ans,sum;
const int mod = 1e9 + 7;
/* cnt:统计1的个数 sum:前面所有的1同时移动到当前位置的距离 */
int main(){
int n;cin>>n;
scanf("%s",a);
for(int i=0;i<n;i++){
sum=(sum+cnt)%mod;
if(a[i]=='1'){
cnt++;
ans=(ans+sum)%mod;
}
}
cout<<ans<<endl;
}
I 牛牛的汉诺塔
思路：
写一个正常的汉诺塔求出前面7项
通过找关系可以求出关系公式，然后代码就很好写了。
代码：
#include<iostream>
#include<math.h>
using namespace std;
long long int a,b,c,d,e,f;
int main(){
long long int n;cin>>n;
for(int i=1;i<=n;i++){
if(i&1){
b=a+d+1;
c=d+e;
f=a+e;
}else{
a=b+c;
d=b+c;
e=a;
}
}
cout<<"A->B:"<<a<<endl;
cout<<"A->C:"<<b<<endl;
cout<<"B->A:"<<c<<endl;
cout<<"B->C:"<<d<<endl;
cout<<"C->A:"<<e<<endl;
cout<<"C->B:"<<f<<endl;
cout<<"SUM:"<<((long long int)1<<n)-1<<endl;
}
京公网安备 11010502036488号