学了些DP
学校题库有\(BUG\)
首先要满足条件\(x,y\)的二进制有1的位必然包含\(a\),然后让\(s-2a\),也就是除去二进制包含\(a\)有1的位,然后\(<0\)肯定无解，其次是如果有与\(a\)同一级的含\(1\)二进制位也不合法
点击查看代码
#include <bits/stdc++.h>
#define speed() ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
#define ll long long
#define lid (rt<<1)
#define rid (rt<<1|1)
// #define endl '\n'
#define pii pair<int,int>
//#define int long long
#define pb push_back
#define ts cout<<"----------------"<<endl;
#define bs bitset<65>
using namespace std;
ll a,s;bool has[65];
int main()
{
freopen("and.in","r",stdin);
freopen("and.out","w",stdout);
// freopen("in.in","r",stdin);
// freopen("out.out","w",stdout);
int T;
cin>>T;
while(T--)
{
cin>>a>>s;
// cout<<bs(a)<<" "<<bs(s)<<endl;
bitset<65> x,y,t;
memset(has,0,sizeof has);
// memset(aa,0,sizeof aa);memset(bb,0,sizeof bb);
for(ll i=0;i<=60;i++)
{
if(a>>i&1ll)
{
x[i]=1;
has[i]=1;
y[i]=1;
s-=(1ll<<i);
s-=(1ll<<i);
}
}
if(s<0)
{
cout<<"No"<<endl;continue;
}else
{
// cout<<"Yes"<<endl;
bool f=1;
for(ll i=0;i<=60;i++)
{
if(s>>i&1ll)
{
if(has[i])f=0;
}
}
if(f)cout<<"Yes"<<endl;
else cout<<"No"<<endl;
}
}
return 0;
}
模拟退火立大功
点击查看代码
#include <bits/stdc++.h>
#define speed() ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
#define ll long long
#define lid (rt<<1)
#define rid (rt<<1|1)
// #define endl '\n'
#define pii pair<int,int>
#define ull unsigned long long
#define pb push_back
#define ts cout<<"----------------"<<endl;
#define bs bitset<65>
using namespace std;
const int N = 2e5+5;
int n,k;
mt19937 rnd(chrono::system_clock::now().time_since_epoch().count());
int rand(int l,int r)
{
uniform_int_distribution<int> range(l, r);
return range(rnd) ;
}
struct ac
{
int a,b;
}a[N];
bool cmp(ac a,ac b)
{
if(a.a==b.a)return a.b>b.b;
return a.a>b.a;
}
bool vis[N];
ll ans;
ll calc()
{
ll res=1;
for(int i=1;i<=k;i++)
{
res=res*a[i].a+a[i].b;
}
ans=max(ans,res);
return res;
}
void SA()
{
sort(a+1,a+1+n,cmp);
for(double t=3000;t>=1e-7;t*=0.998)
{
ll now=calc();
int u=rand(1,INT_MAX)%n+1,v=rand(1,INT_MAX)%n+1;
swap(a[u],a[v]);
ll nn=calc();
if(nn>now)continue;
if((double)exp((double)(nn-now)/t)>(double)rand(1,INT_MAX)/INT_MAX)continue;
swap(a[u],a[v]);
}
}
double Tm()
{
return (double)clock()/CLOCKS_PER_SEC;
}
int main()
{
speed();
// freopen("in.in","r",stdin);
// freopen("out.out","w",stdout);
freopen("func.in","r",stdin);
freopen("func.out","w",stdout);
cin>>n>>k;
for(int i=1;i<=n;i++)
{
cin>>a[i].a>>a[i].b;
}
random_shuffle(a+1,a+1+n);
while(Tm()<0.8)SA();
cout<<ans<<endl;
return 0;
}
正解,设\(A_1(A_2+B_2)+B_1>A_2(A_1+B_1)+B_2\)则\((A_1-1)B_2>(A_2-1)B_2\)
排个序，然后\(dp\)即可，记得处理边界啊
点击查看代码
#include <bits/stdc++.h>
#define speed() ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
#define ll long long
#define lid (rt<<1)
#define rid (rt<<1|1)
// #define endl '\n'
#define pii pair<int,int>
#define ull unsigned long long
#define pb push_back
#define ts cout<<"----------------"<<endl;
#define bs bitset<65>
using namespace std;
const int N = 2e5+5;
ll n,k,dp[15][N];
struct ac
{
ll a,b;
}a[N];
bool cmp(ac a,ac b)
{
return (b.a-1)*a.b>(a.a-1)*b.b;
}
int main()
{
speed();
freopen("func.in","r",stdin);
freopen("func.out","w",stdout);
// freopen("in.in","r",stdin);
// freopen("out.out","w",stdout);
cin>>n>>k;
for(int i=1;i<=n;i++)
{
cin>>a[i].a>>a[i].b;
}
sort(a+1,a+1+n,cmp);
dp[0][0]=1;//sb
for(int i=1;i<=n;i++)dp[0][i]=1;
for(int i=1;i<=k;i++)
{
for(int j=1;j<=n;j++)
{
dp[i][j]=max(dp[i][j-1],dp[i-1][j-1]*a[j].a+a[j].b);
// cout<<i<<" "<<j<<" "<<dp[i]
}
}
// for(int i=1;i<=n;i++)
// {
// for(int j=0;j<=k;j++)
// {
// dp[i][j]=dp[i-1][j];
// if(j)dp[i][j]=max(dp[i][j],dp[i-1][j-1]*a[i].a+a[i].b);
// }
// }
ll ans=0;
for(int i=1;i<=n;i++)ans=max<ll>(ans,dp[k][i]);
cout<<ans<<endl;
return 0;
}
预设性\(DP\)详见