img

算法竞赛进阶指南刷题篇之位运算

A.a^b

题目描述

求 a 的 b 次方对 p 取模的值，其中 0≤a,b,p≤109，p>0

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include<bits/stdc++.h>
using namespace std;
unsigned long long kmi(unsigned long long a,unsigned long long b,unsigned long long p)
{
    int ans=1;
    a = a % p;
    while(b)
    {
        if(b&1)ans=ans*a%p;
        a=a*a%p;
        b>>=1;
    }
    return ans%p;
}
int main()
{
    unsigned long long a,b,p;
    cin>>a>>b>>p;
    cout<<kmi(a,b,p);
    return 0;
}

B.Raising Modulo Numbers

分组快速幂

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#include<iostream>
#include<cstdio>
using namespace std;
typedef unsigned long long int ll;
int quick(int a,int b,int c)
{
   int ans=1;
   a=a%c;
   while(b!=0)
   {
     if(b&1) ans=(ans*a)%c;
     b>>=1;
     a=(a*a)%c;
  }
   return ans;
}
int main()
{
        int t;
        cin>>t;
        while(t--)
        {
            int m,n;
            int ans=0;
            cin>>m>>n;
            for(int i=0;i<n;i++)
            {
                int a,b;
                cin>>a>>b;
                ans+=quick(a,b,m);
                ans%=m;
            }
            cout<<ans<<endl;
        }
}

C.64位整数乘法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include<bits/stdc++.h>
using namespace std;
long long qc(long long a,long long b,long long p)
{
    long long ans=0;
     
    while(b)
    {
        if(b&1)ans=(ans+a)%p;
        a=(a*2)%p;
        b>>=1;
    }
    return ans%p;
}
int main()
{
    long long a,b,p;
    cin>>a>>b>>p;
    cout<<qc(a,b,p);
    return 0;
}

最短Hamilton路径

定义f[i] [j]：i为一个20位的整数，第k位表示是否经过了这个点，j表示最终停在那一点，初始状态，f[1] [0]=1

答案就是f[1<<n-1] [n-1]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#include<bits/stdc++.h>
using namespace std;

const int N=20,M=1<<N;
int f[M][N],w[N][N];

int main()
{
    int n;
    cin>>n;
    
    for(int i=0;i<n;i++)
        for(int j=0;j<n;j++)
            cin>>w[i][j];
    
    memset(f,0x3f,sizeof(f));
    f[1][0]=0;
    
    for(int i=0;i<1<<n;i++)
        for(int j=0;j<n;j++)
        {
            if(i>>j&1)
                //第j位出现过
            {
                for(int k=0;k<n;k++)
                {
                    if(i>>k&1) f[i][j]=min(f[i][j],f[i-(1<<j)][k]+w[k][j]);
                    //第k位出现，并转移到j
                }
            }
        }
    cout<<f[(1<<n)-1][n-1]<<endl;
    return 0;
}

起床困难综合症

本题可以先求出全0和全1经过这些操作后究竟怎么了

如果0变成1显然不需要我们花费任何m啊

那直接加上

如果1-1

那么也要选，有肉谁不选呢，虽然要花钱，就是要减去我们m中的一部分来计入这一部分答案

也就是为什么(1<<j)<=m的原因

就是可以选的意思

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include<bits/stdc++.h>
int n,m,ans,x,a1=0,a2=-1;
char str[5];
int main(){
	cin>>n>>m;
	while(n--){
		cin>>str>>x;
		if(str[0]=='A') a1&=x, a2&=x;
		if(str[0]=='X') a1^=x, a2^=x;
		if(str[0]=='O') a1|=x, a2|=x;
	}
	for(int j=29;~j;--j){
		if(a1>>j&1) ans+=1<<j;
		else if(a2>>j&1&&(1<<j)<=m) ans+=1<<j, m-=1<<j;
	} 
    cout<<ans;
	return 0;
}