A. Min Or Sum
思路：满足等式$a_i|a_j=x|y$,其中$a_i$换成$x$,$a_j$换成$y$,求操作后序列的和最小.
考虑所有数的二进制位如果为1,无论如何操作都必须在总和中加上该位的贡献.那么最合适的操作就是:
每个为一的二进制位只计算一次.
AC Code:
#include<bits/stdc++.h>
#pragma optimize(2)
#define endl '\n'
#define debug(x) cout<<#x<<":"<<x<<endl;
using namespace std;
typedef long long ll;
typedef pair<int,int>PII;
typedef unsigned long long ull;
const int M=2010;
const ll llinf=0x3f3f3f3f3f3f3f3f;
const int inf=0x3f3f3f3f;
const int mod=1e9+7;
const int N=2e6+10;
int dx[4]={0,1,0,-1};
int dy[4]={-1,0,1,0};
bool vis[32];
void solve()
{
int n;cin>>n;
memset(vis,false,sizeof vis);
vector<int>a(n+1);
for(int i=1;i<=n;i++)cin>>a[i];
for(int i=1;i<=n;i++)
{
for(int j=0;j<30;j++)
if(a[i]>>j&1)vis[j]=true;
}
int ans=0;
for(int i=0;i<30;i++)
if(vis[i])ans+=(1<<i);
cout<<ans<<endl;
return ;
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
// freopen("test.in","r",stdin);
int t;cin>>t;
while(t--)solve();
return 0;
}
B. Avoid Local Maximums
思路：
贪心的办法,从左往右考虑修改每一处极值点的右边的一个值.
观察式子$a_l < a_i > a_r$,此时修改$a_r$可以改变这个极值的同时,可以使得下一个可能和$a_r$构成极值的点无法构成极值.
即令$a_r=max(a_i,a_{i+2})$,为什么是$a_{i+2}$,因为$a_{i+2}$和$a_i$才能和$a_r$构成极值.
AC Code:
#include<bits/stdc++.h>
#pragma optimize(2)
#define endl '\n'
#define debug(x) cout<<#x<<":"<<x<<endl;
using namespace std;
typedef long long ll;
typedef pair<int,int>PII;
typedef unsigned long long ull;
const int M=2010;
const ll llinf=0x3f3f3f3f3f3f3f3f;
const int inf=0x3f3f3f3f;
const int mod=1e9+7;
const int N=2e6+10;
int dx[4]={0,1,0,-1};
int dy[4]={-1,0,1,0};
bool vis[32];
int a[N];
void solve()
{
int n;cin>>n;
for(int i=1;i<=n;i++)cin>>a[i];
int ans=0;
for(int i=2;i<=n-1;i++)
if(a[i]>a[i-1]&&a[i]>a[i+1])
{
ans++;
a[i+1]=max(a[i],a[i+2]);
}
cout<<ans<<endl;
for(int i=1;i<=n;i++)cout<<a[i]<<' ';
cout<<endl;
return ;
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
// freopen("test.in","r",stdin);
int t;cin>>t;
while(t--)solve();
return 0;
}
C. Differential Sorting
思路：
分类讨论一下.
1.$a_{n} < a_{n-1}$时,必定无法构造.因为最后两个数无法被操作.那么如果不满足no-decreaseing直接输出-1
2.$a_n>=a_{n-1}$时,有两种情况.
情况一：$a_n\geq 0$,必定可以构造成功,找到一种即可.
令$t$=$a_{n-1}-a_n\leq a_{n-1}$,式子写成{$t,t,t,t,t.....,a_{n-1},a_n$}.这是一个no-decreasing.
情况二:$a_n<0$,此时假如式子不是no-decreasing的,则必定无法构造成功.
假设某个位置上 出现$a_j>a_i$,$(j<i)$,将$a_j$修改成$a_y-a_z$而此时$a_y-a_z\geq a_y$.
即修改某个逆序对,以后又会出现新的逆序对.故逆序对永远不会因为修改而消失.
AC Code:
#include<bits/stdc++.h>
#pragma optimize(2)
#define endl '\n'
#define debug(x) cout<<#x<<":"<<x<<endl;
using namespace std;
typedef long long ll;
typedef pair<int,int>PII;
typedef unsigned long long ull;
const int M=2010;
const ll llinf=0x3f3f3f3f3f3f3f3f;
const int inf=0x3f3f3f3f;
const int mod=1e9+7;
const int N=2e6+10;
int dx[4]={0,1,0,-1};
int dy[4]={-1,0,1,0};
struct node{
int x,y,z;
};
void solve()
{
int n;cin>>n;
vector<int>a(n+1);
vector<node>ans(n+1);
for(int i=1;i<=n;i++)cin>>a[i];
if(a[n]<a[n-1])
{
cout<<"-1"<<endl;
return ;
}else//a[n]>=a[n-1]
{
if(a[n]>=0)
{
cout<<n-2<<endl;
for(int i=1;i<=n-2;i++)cout<<i<<' '<<n-1<<' '<<n<<endl;
}else
{
for(int i=1;i<=n-1;i++)
if(a[i]>a[i+1])
{
cout<<"-1"<<endl;
return;
}
cout<<0<<endl;
}
}
return ;
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
// freopen("test.in","r",stdin);
int t;cin>>t;
while(t--)solve();
return 0;
}
D. Infinite Set
斐波那契数列/DP
思路：
化简两个操作:
- 1.在二进制位后添加1
- 2.在二进制位后添加00
由分析我们可以知道数的二进制表示都是唯一的,而每一个新生成的数只能由其中一个操作得来.因此
不同数操作后所形成的新数都是不会重复的.
因此只需要统计出每一个独立的数所能产生多少种新数即可。
观察下式:
记t当前一共表示t位.
那么通过操作1和2后能生成的是 t+1,t+2.与此同时t+1,t+2.分别生成.t+2,t+3,t+3,t+4.
即t:1
t+1:1
t+2:2
t+3:3
t+4:5
t+5:8
....
很明显这是一个斐波那契数列.
因此对于一个独立数的统计是很容易的。而且每一种独立的数方案必定不会重复.因此只需要统计所有独立的数的方案数。
但是由于可能有些初始数组中的数,最开始的时候就可以由数组中的其他数生成,这样数组中的数就会出现.
一个数的方案,实际上是另一个数的子集,因此需要去重:
去重代码:
while(tmp)
{
if(tmp%2!=0)tmp>>=1;
else if(tmp%4==0)tmp>>=2;
else break;
if(mp[tmp])
{
ok=true;
break;
}
// cout<<i<<' '<<tmp<<endl;
}
最后统计和即可.
AC Code:
#include<bits/stdc++.h>
#pragma optimize(2)
#define endl '\n'
#define debug(x) cout<<#x<<":"<<x<<endl;
using namespace std;
typedef long long ll;
typedef pair<int,int>PII;
typedef unsigned long long ull;
const int M=2010;
const ll llinf=0x3f3f3f3f3f3f3f3f;
const int inf=0x3f3f3f3f;
const int mod=1e9+7;
const int N=2e6+10;
int dx[4]={0,1,0,-1};
int dy[4]={-1,0,1,0};
int F[N],s[N];
void init()
{
F[1]=1,F[2]=1;
for(int i=3;i<=2e5+10;i++)F[i]=(F[i-1]+F[i-2])%mod;
for(int i=1;i<=2e5+10;i++)s[i]=(s[i-1]+F[i])%mod;
}
void solve()
{
int n,p;
cin>>n>>p;
vector<int>a(n+1);
map<int,bool>mp;
for(int i=1;i<=n;i++)cin>>a[i],mp[a[i]]=true;
init();
int ans=0;
for(int i=1;i<=n;i++)
{
bool ok=false;
int tmp=a[i];
while(tmp)
{
if(tmp%2!=0)tmp>>=1;
else if(tmp%4==0)tmp>>=2;
else break;
if(mp[tmp])
{
ok=true;
break;
}
// cout<<i<<' '<<tmp<<endl;
}
if(ok)continue;
else
{
int res=0;
while(a[i])
{
a[i]>>=1;
res++;
}
ans=(ans+s[max(0,p-res+1)])%mod;//记得给ans取模
}
}
cout<<ans<<endl;
return ;
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
// freopen("test.in","r",stdin);
solve();
return 0;
}
