1.位运算
1.位运算
链接: https://ac.nowcoder.com/acm/contest/996/A
1.A a^b
求 a 的 b 次方对 p 取模的值，其中 0≤a,b,p≤
输入描述:
三个用空格隔开的整数a,b和p。
输出描述:
一个整数，表示a^b mod p 的值。
输入
2 3 9
输出
8
思路:使用快速幂求解，注意mod的数值较大，要开long long
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll fastPow(ll base,ll n,ll mod){
ll res=1;
while(n){
if(n&1){
res=((res%mod)*(base%mod))%mod;
}
base=((base%mod)*(base%mod))%mod;
n=(n>>1);//左移一位
}
return res%mod;
}
int main()
{
ll a,b,p;
scanf("%lld %lld %lld",&a,&b,&p);
ll result=fastPow(a,b,p);
printf("%lld",result);
return 0;
} 2.B Raising Modulo Numbers
链接：https://ac.nowcoder.com/acm/contest/996/B
题目描述
People are different. Some secretly read magazines full of interesting girls' pictures, others create an A-bomb in their cellar, others like using Windows, and some like difficult mathematical games. Latest marketing research shows, that this market segment was so far underestimated and that there is lack of such games. This kind of game was thus included into the KOKODáKH. The rules follow:
Each player chooses two numbers Ai and Bi and writes them on a slip of paper. Others cannot see the numbers. In a given moment all players show their numbers to the others. The goal is to determine the sum of all expressions Ai Bi from all players including oneself and determine the remainder after division by a given number M. The winner is the one who first determines the correct result. According to the players' experience it is possible to increase the difficulty by choosing higher numbers.
You should write a program that calculates the result and is able to find out who won the game.
输入描述:
The input consists of Z assignments. The number of them is given by the single positive integer Z appearing on the first line of input. Then the assignements follow. Each assignement begins with line containing an integer M (1≤M≤45000). The sum will be divided by this number. Next line contains number of players H(1≤M≤45000). Next exactly H lines follow. On each line, there are exactly two numbers Ai and Bi separated by space. Both numbers cannot be equal zero at the same time.
输出描述:
For each assingnement there is the only one line of output. On this line, there is a number, the result of expression (A1^B1+A2^B2+...+AH^BH) mod M.
示例1
输入
3 16 4 2 3 3 4 4 5 5 6 36123 1 2374859 3029382 17 1 3 18132
输出
2 13195 13
思路: 使用快速幂求解
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll fastPow(ll base,ll n,ll mod){
ll res=1;
while(n){
if(n&1){
res=((res%mod)*(base%mod))%mod;
}
base=((base%mod)*(base%mod))%mod;
n=(n>>1);//左移一位
}
return res%mod;
}
int main()
{
int T;
ll M;
ll sum=0;
ll n;
ll a,b;
scanf("%d",&T);
while(T--){
scanf("%lld",&M);
scanf("%lld",&n);
sum=0;
for(ll i=1;i<=n;i++){
scanf("%lld %lld",&a,&b);
sum=(sum+fastPow(a,b,M))%M;
}
printf("%lld\n",sum);
}
return 0;
}
3.C 64位整数乘法
链接：https://ac.nowcoder.com/acm/contest/996/C
求 a 乘 b 对 p 取模的值，其中 1≤a,b,p≤10^18^。
输入描述:
第一行a，第二行b，第三行p。
输出描述:
一个整数，表示a×b mod p的值。
示例1
输入
2 3 9
输出
6
思路:类似于快速幂，只是将乘法转换成了加法，可以转换的原因,它们的取模性质类似
- （a*a)%mod=((a%mod)*(a%mod))%mod
- （a+b)%mod=((a%mod)+(b%mod))%mod
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll Mul64(ll a,ll b,ll mod){
ll ans=0;
while(b){
if(b&1) ans=(ans+a)%mod;
a=(a<<1)%mod;//右移一位
b=b>>1;//左移一位
}
return ans%mod;
}
int main()
{
ll a,b,p,ans=0;
scanf("%lld %lld %lld",&a,&b,&p);
ans=Mul64(a,b,p);
printf("%lld",ans);
return 0;
} 4.D 最短Hamilton路径
链接：https://ac.nowcoder.com/acm/contest/996/D
此题借鉴博客：https://www.cnblogs.com/Acapplella/p/13544964.html
给定一张 n(n≤20)个点的带权无向图，点从0∼n−1标号，求起点 0 到终点 n-1 的最短Hamilton路径。 Hamilton路径的定义是从 0 到 n-1 不重不漏地经过每个点恰好一次。
输入描述:
第一行一个整数n。 接下来n行每行n个整数，其中第i行第j个整数表示点i到j的距离（一个不超过10710^7107的正整数，记为a[i,j]）。 对于任意的x,y,z，数据保证 a[x,x]=0，a[x,y]=a[y,x] 并且a[x,y]+a[y,z]≥a[x,z]a[x,y]+a[y,z] \geq a[x,z]a[x,y]+a[y,z]≥a[x,z]。
输出描述:
一个整数，表示最短Hamilton路径的长度。
示例1
输入
4 0 2 1 3 2 0 2 1 1 2 0 1 3 1 1 0
输出
4
说明
从0到3的Hamilton路径有两条，0-1-2-3和0-2-1-3。前者的长度为2+2+1=5，后者的长度为1+2+1=4
思路：
以用一个二进制数表示当前经过的点集。其中第 i 位为 1/0 表示是/否经过了点 i。
状态表示：f[i][j]。其中 i 是一个二进制数，表示点集的方法如上述所示。
- 集合：经过的点集为 i ,且当前到了点 j 上的所有路径。
- 属性：路径总长度的最小值。
状态计算：假设当前要从点 k转移到 j。那么根据 Hamilton 路径的定义，走到点 k 的路径就不能经过点 j，所以就可以推出状态转移方程
f[i][j] = min{f[i][j],f[i-(1 << j)][k] + weight[k][j]}
其中weight[k][j]表示从点 k 到点 j 的距离。
所有状态转移完后，根据 f[i][j] 的定义，要输出 f[111⋯11((n−1)个1)][n−1]。
那么怎么构造 n - 1 个 1 呢，可以直接通过 1 << n 求出 100⋯0((n−1)个0)，然后减一即可。
怎样确保答案是一条通路而不是树呢？
因为，集合之中没有该元素才能联通，有该元素就不会连通，所以任意端点的入度不会大于1
#include<bits/stdc++.h>
using namespace std;
const int N=20,M=1<<20;//一共有2的20次方种情况
int f[M][N],weight[N][N];
int n;//
int Hamilton(){
memset(f,0x3f,sizeof(f));//初始化距离为无穷大
f[1][0] = 0;//初始化一个点的时候为权为0
for(int i=1;i<(1<<n);i++){//i表示已经选取的点的集合
for(int j=0;j<n;j++){//有j个点
if(i>>j&1){//如果存在该点j
for(int k=0;k<n;k++){
f[i][j]=min(f[i][j],f[i-(1<<j)][k]+weight[j][k]);
}
}
}
}
return f[(1 << n) - 1][n - 1];
}
int main()
{
scanf("%d",&n);
for(int i=0;i<n;i++){//输入图
for(int j=0;j<n;j++){
scanf("%d",&weight[i][j]);
}
}
int ans=Hamilton();//计算权值
printf("%d",ans);
return 0;
} 
投递阿里巴巴等公司10个岗位 >
查看4道真题和解析