1.1 二進制中一的個數
原題鏈接
#include <iostream>
#define lowbit(i)((i)&(-i))
using namespace std;
int main()
{
int n;
cin>>n;
while(n--)
{
int res=0,m;
cin>>m;
while(m)
{
m-=lowbit(m);
res++;
}
cout<<res<<" ";
}
return 0;
}
1.2 快速冪
原題鏈接
#include<iostream>
using namespace std;
int main()
{
int a,b,p;
cin>>a>>b>>p;
int res=1%p;
while(b)
{
if(b&1) res=(long long)res*a%p;
a=(long long)a*a%p;
b>>=1;
}
cout<<res<<endl;
return 0;
}
1.3 64位乘法
原題鏈接
#include <iostream>
using namespace std;
typedef unsigned long long ull;
int main()
{
ull a,b,p;
cin>>a>>b>>p;
ull res=0;
while(b)
{
if(b&1) res=(res+a)%p;
a=a*2%p;
b>>=1;
}
cout<<res<<endl;
return 0;
}
1.4 最短Hamilton路徑
原題鏈接
- 給定一張 n 個點的帶權無向圖，點從 0~n-1 標號，求起點 0 到終點 n-1 的最短Hamilton路徑， Hamilton路徑的定義是從 0 到 n-1 不重不漏地經過每個點恰好一次，
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N=1<<20,M=20;
int n;
int f[N][M],weight[M][M];
//N為當前哪些點被用過，用20位二進制表示每個點的狀態，1表示被訪問過，0表示沒有被訪問過
//M當前停在哪些點
int main()
{
cin>>n;
for(int i=0;i<n;i++)
for(int j=0;j<n;j++)
cin>>weight[i][j];
memset(f,0x3f,sizeof f);
f[1][0]=0;
for(int state=0;state<1<<n;state++)
{
for(int j=0;j<n;j++)//先列舉狀態
{
if(state>>j&1)//如果state集合中第j位是1，也就是到達過這個點
{
for(int k=0;k<n;k++)
{
if(state-(1<<j)>>k&1)//state_k==state-(1<<j),為state除掉j之后的集合,且狀態里面要包含k
f[state][j]=min(f[state][j],f[state-(1<<j)][k]+weight[k][j]);
}
}
}
}
cout<<f[(1<<n)-1][n-1];
return 0;
}
1.5 起床困難綜合癥
原題鏈接
給定 n,m以及n個數和該數所對應的運算，其中運算有 與、或、異或 三種，問在所有不大于m的非負整數中，對給定的n個數都按該數所對應的運算運算一遍后，能得到得最大的值是多少，
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cstdio>
#include<cstdlib>
using namespace std;
pair<string,int>a[100005];
int n,m;
int calc(int bit,int now)//假設引數為now值，填入，n次運算元的第bit位進行運算，回傳預計now值
{
for(int i=0;i<n;i++)
{
int x=a[i].second>>bit&1;//取第bit位
if(a[i].first=="AND")now&=x;
else if(a[i].first=="OR")now|=x;
else now^=x;
}
return now;
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=0;i<n;i++)
{
string str;
int x;
cin>>str;
scanf("%d",&x);
a[i]=make_pair(str,x);
}
int val=0,ans=0;
for(int bit=29;bit>=0;bit--)
{
int res0=calc(bit,0);
int res1=calc(bit,1);
if(res0<res1&&val+(1<<bit)<=m)//預計結果為0<1,且已經填好的更高位構成的數值加上1<<bit后不超過m，填1
{
val+=1<<bit;
ans+=res1<<bit;
}
else
ans+=res0<<bit;//其余情況，都填0
}
printf("%d",ans);
return 0;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/251497.html
標籤：其他
上一篇：紅黑樹添加洗掉
下一篇：2021寒假每日一題《貨幣系統》