Codeforces Round #772 (Div. 2) A B C D
A. Min Or Sum
思路: 一眼题,最好的情况就是二进制形式下出现过的数字最多保留1位。全部|起来即可。
- 参考代码:
#include<bits/stdc++.h>
using namespace std;
#define mp make_pair
#define int long long
#define re register int
#define pb emplace_back
#define lowbit(x) (x&-x)
#define fer(i,a,b) for(re i = a ; i <= b ; i ++)
#define der(i,a,b) for(re i = a ; i >= b ; i --)
#define snow ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
int gcd(int a,int b){return b?gcd(b,a%b):a;}
int lcm(int a,int b){return a*b/gcd(a,b);}
typedef pair<int,int>PII;
typedef pair<int,string>PIS;
signed main(){
int t;
cin>>t;
while(t--){
int n;
cin>>n;
int k=0;
for(int i=1;i<=n;i++){
int x;
cin>>x;
k|=x;
}
cout<<k<<endl;
}
return 0;
}
B. MEX and Array
思路: 贪心,从左到右扫描,如果碰到Local Maximums,那么改变右边的数使a[i+1]变成max(a[i],a[i+2])。为什么取max呢,因为如果a[i+2]比a[i]大,那么我们显然将a[i+1]变成a[i+2]更好,因为不但满足使得左边的Local Maximums消失,并且确保右边的a[i+2]一定无法构成Local Maximums,即是a[i+3]比a[i+2]小。反之如果a[i+1]变成a[i]那么左边确实保证了Local Maximums消失,但是如果a[i+3]比a[i+2]小,我们又要浪费一次机会去放大a[i+3],显然前者更优。
- 参考代码:
#include<bits/stdc++.h>
using namespace std;
#define mp make_pair
#define int long long
#define re register int
#define pb emplace_back
#define lowbit(x) (x&-x)
#define fer(i,a,b) for(re i = a ; i <= b ; i ++)
#define der(i,a,b) for(re i = a ; i >= b ; i --)
#define snow ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
int gcd(int a,int b){return b?gcd(b,a%b):a;}
int lcm(int a,int b){return a*b/gcd(a,b);}
typedef pair<int,int>PII;
typedef pair<int,string>PIS;
const int N=2e5+10;
int a[N];
signed main(){
int t;
cin>>t;
while(t--){
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]){
a[i+1]=max(a[i],a[i+2]);
ans++;
}
}
cout<<ans<<endl;
for(int i=1;i<=n;i++)cout<<a[i]<<' ';
cout<<endl;
}
return 0;
}
C. Differential Sorting
思路: 比赛时候C翻水水了,歪掉了。以为区间维护,一开始写了3个struct维护后缀区间最值。
后来wa掉了。正解:从性质出发:1.如果a[n−1]>a[n]必错,因为a[n−1]无法成为一个小于等于a[n]的数。2:如果a[n]是正数,那么在满足性质1情况下必然可以通过n−2次构造使得前n−2个数全部变成a[n−1]−a[n]。3:如果a[n]是负数,前面出现的数必然都是负数才行,一旦出现a[i]>a[i+1]的情况,那么必然无法使得a[i]<=a[i+1],因为小的负数-大的负数为大于等于0的整数,也必然>a[i+1],所以一旦有a[n]是负数,除非原数组本身是非降序,操作次数为0,否则一定是−1。
- 参考代码:
#include<bits/stdc++.h>
using namespace std;
const int N=2e5+10;
int a[N];
int main(){
int t;
cin>>t;
while(t--){
int n;
cin>>n;
for(int i=1;i<=n;i++)cin>>a[i];
int x=a[n-1]-a[n];
if(x>0){
cout<<"-1"<<endl;
continue;
}
if(a[n]<0){
bool ok=true;
for(int i=1;i<=n-1;i++){
if(a[i]>a[i+1])ok=false;
}
if(ok){
cout<<0<<endl;
continue;
}
cout<<"-1"<<endl;
}
else{
cout<<n-2<<endl;
for(int i=1;i<=n-2;i++){
cout<<i<<' '<<n-1<<' '<<n<<endl;
}
}
}
return 0;
}
D. Infinite Set
思路: 通过题目可知除了本身在a数组中出现过的数在S中,依次迭代的2∗a[i]+1和4∗a[i]也会依次出现在容器中。那么必定有k<=f(x)<k+1,k和k+1为n在log2()下的左右边界。例如22<=f(5)<23,那么k为2,k+1为3,那么显然f(x∗2+1)的左边界为k+1,f(x∗4)的左边界为k+2。那么我们很容易发现一个dp转移方程,左边界为k+2的方案数除了本身以外还可以从k和k+1处转移过来,分别通过方程f(x∗4)和f(x∗2+1)。并且在方程转移开始之前我们需要删掉无用的在a数组中重复出现的数,避免一个相同的数被多次重复计算。例如a[1]=5,a[2]=10,a[2]可以通过a[1]获得,所以a[2]我们没必要继续保留。那么这个操作的实现只需将数组从小到大排序,如果将一个数回溯的过程遇到了之前标记过的数说明这个数可以通过前面标记过的数获得而来,那么没必要继续保存。例如:35回溯过程是35,17,8,2。如果前面这个数出现任意,那么35即可被转移过来。那么接下去我们就可以进行dp转移,统计最终的总数小于2p的个数。还有一点,为什么进行dp转移过程中不会出现同样的数呢?因为我们前面已经将所有会被任意小数转移过来的大数全部删除,那么剩余留在数组中的数必然全是互相不可转移。并且转移路线唯一,什么意思呢?比如上面提到的35,回溯路径是唯一的,假使后期转移过程出现相同的数,那么说明这个数不断回溯到原数组中会出现a[j]可以被a[i]转移而来的情况,那么显然与我们已经删掉所有干扰数相矛盾。所以转移方案数中的数都是独一无二的。
- 参考代码:
#include<bits/stdc++.h>
using namespace std;
#define mp make_pair
#define int long long
#define re register int
#define pb emplace_back
#define lowbit(x) (x&-x)
#define fer(i,a,b) for(re i = a ; i <= b ; i ++)
#define der(i,a,b) for(re i = a ; i >= b ; i --)
#define snow ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
int gcd(int a,int b){return b?gcd(b,a%b):a;}
int lcm(int a,int b){return a*b/gcd(a,b);}
typedef pair<int,int>PII;
typedef pair<int,string>PIS;
const int N=2e5+10;
int a[N];
const int mod=1e9+7;
signed main(){
int n,p;
cin>>n>>p;
for(int i=1;i<=n;i++){
cin>>a[i];
}
unordered_map<int,int>hash;
sort(a+1,a+1+n);
vector<int>S;
for(int i=1;i<=n;i++){
int j=a[i];
bool ok=true;
while(j){
if(hash[j]==1)ok=false;
if(j&1)j>>=1;
else if(j&3)break;
else j>>=2;
}
if(ok){//如果无法转移过来那么放进S中
hash[a[i]]=1;
S.push_back(a[i]);
}
}
vector<int>sum(30),dp(p);
for(auto x:S){
sum[__lg(x)]++;
}
int ans=0;
for(int i=0;i<p;i++){
if(i<30){
dp[i]=sum[i];
}
if(i>=1){
dp[i]=(dp[i]+dp[i-1])%mod;
}
if(i>=2){
dp[i]=(dp[i]+dp[i-2])%mod;
}
ans=(ans+dp[i])%mod;
}
cout<<ans<<endl;
return 0;
}
%%%