3月23阿里笔试 2题ac附代码
1、直接快速幂
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <ctime>
#include <string.h>
#include <string>
#include <complex>
using namespace std;
typedef long long ll;
ll power(ll a, ll n, ll mod)
{ll p = 1;while (n > 0) {if(n%2) {p = p * a; p %= mod;} n >>= 1; a *= a; a %= mod;} return p % mod;}
//head
int main(){
ll n;
while(cin>>n)
{
cout<<n*power(2,n-1, mod)%mod<<endl;
}
return 0;
} 2、bfs搜一下
#阿里笔试2020##笔试题目##阿里巴巴##include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <ctime>
#include <string.h>
#include <string>
#include <complex>
using namespace std;
typedef pair<int, int> pii;
const int maxn = 1e5+10, mod = 1e9 + 7;
queue<pair<int,pair<int,int> > > qu;
string s;
int dx[4] = {1,0,-1,0};
int dy[4] = {0,1,0,-1};
int a[600][600];
int flag[6][600][600];
int n,m;
bool judge(int x, int y, int kn)
{
if(x<=n && x>=1 && y<=m && y>=1 && a[x][y] == 0 && flag[kn][x][y] == 0)
return true;
return false;
}
int main(){
//freopen("C-small-attempt0.in","r",stdin);
//freopen("C-small-attempt0.out","w",stdout);
while(cin>>n>>m)
{
int sn,sm,en,em;
while(!qu.empty())qu.pop();
memset(flag,0, sizeof(flag));
pair<int,pair<int,int> > dp, cur;
for(int i=1;i<=n;i++)
{
cin>>s;
for(int j=0;j<m;j++)
{
if(s[j] == 'S')
sn = i, sm = j +1 , a[i][j+1] = 0;
if(s[j] == 'E')
en = i, em = j+1, a[i][j+1] = 0;
if(s[j] == '.')
a[i][j+1] = 0;
if(s[j] == '#')
a[i][j+1] = 1;
}
}
dp.first = 0;
dp.second.first = sn;
dp.second.second = sm;
qu.push(dp);
flag[0][sn][sm] = 1;
int ans = -1;
while(!qu.empty())
{
dp = qu.front();
int cx = dp.second.first;
int cy = dp.second.second;
int knum = dp.first;
int bus = flag[knum][cx][cy];
qu.pop();
//cout<<cx<<" "<<cy<<" "<<knum<<" "<<bus<<endl;
if(cx == en && cy == em)
{
ans = bus - 1;
break;
}
for(int i=0;i<4;i++)
{
if(judge(cx + dx[i], cy + dy[i], knum))
{
cur.first = knum;
cur.second.first = cx + dx[i];
cur.second.second = cy + dy[i];
qu.push(cur);
flag[knum][cx + dx[i]][cy + dy[i]] = bus + 1;
}
}
if(knum < 5 && judge(n + 1 - cx , m + 1 - cy , knum + 1))
{
cur.first = knum + 1;
cur.second.first = n + 1 - cx;
cur.second.second = m + 1 - cy;
qu.push(cur);
flag[knum + 1][n + 1 - cx][m + 1 - cy] = bus + 1;
}
}
cout<<ans<<endl;
}
return 0;
} 