阿里暑期实习笔试3.15

位运算贪心

#include
#include
#include
#include
using namespace std;
int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        int a,b,c;
        cin>>a>>b>>c;
        vector a2(30,0);
        vector b2(30,0);
        vector c2(30,0);
        for(int i=0;i<30;i++)
        {
            if(a&(1<<i))a2[i]=1;
            if(b&(1<<i))b2[i]=1;
            if(c&(1<<i))c2[i]=1;
        }
        int res = 0;
        for(int i=0;i<30;i++)
        {
            if(c2[i]==0)
            {
                if(a2[i]==1)res++;
                if(b2[i]==1)res++;
            }
            else
            {
                if(a2[i]==1 || b2[i]==1)continue;
                else res++;
            }
        }
        cout<<res<<endl;
    }
    return 0;
}

带递归次数约束的期望dp

#include
#include
#include
#include
#include
using namespace std;
const int N=10010;
double f[N];
int dp(int n,int d)
{
    if(d==0)return n;
    if(f[n])return f[n];
    double res = 0.0;
    for(int i=1;i<=n-1;i++)
    {
        double maxi = max(i,n-i);
        double mini = min(i,n-i);
        if(maxi-mini>=2&&d>0)res+=(mini+dp(maxi-mini,d-1))/(n-1);
        else res+=maxi/(n-1);
    }
    f[n]=res;
    return res;
}
int main()
{
    memset(f,0,sizeof f);
    int n;
    cin>>n;
    f[1]=1;
    f[2]=1;
    vector res;
    dp(n,2);
    int tmp=f[n]*10000;
    while(tmp)
    {
        res.push_back(tmp%10);
        tmp/=10;
    }
    reverse(res.begin(),res.end());
    for(int i=0;i<5;i++)
    {
        cout<<res[i];
        if(i==0)cout<<".";
    }
    // printf("%.",f[n]);
    return 0;
}