题目链接
A. Min Or Sum—思维
题意：给定一个数组，可执行的操作如下：
选定 a i , a j ai,aj ai,aj 让 a i = x , a j = y ai=x,aj=y ai=x,aj=y满足 a i ∣ a j = x ∣ y ai|aj=x|y ai∣aj=x∣y
进行若干操作后，使得数组所有元素的和最小，输出这个最小值。
思路：直接遍历或就行了
#include <iostream>
using namespace std;
#define int long long
const int N = 200010;
void solve()
{
int n;cin>>n;
int res=0;
for(int i=1;i<=n;i++)
{
int x;cin>>x;
res=res|x;
}
cout<<res<<'\n';
}
signed main()
{
int T;cin>>T;
while(T--)solve();
}
B. Avoid Local Maximums—贪心
题意：给定一个数组 ,求使得数组中没有局部最大值的最小步数，同时输出方案
思路：如果发现 a i a_i ai是局部最大值，根据贪心策略， a i a_i ai前边已经全部满足需求，后边的还不知道，所以改变 a i + 1 a_{i+1} ai+1显然比改变 a i a_i ai更优，同时使 a i + 1 a_{i+1} ai+1尽可能的大， a i + 1 a_{i+1} ai+1最大为 m a x ( a [ i ] , a [ i + 2 ] ) max(a[i],a[i+2]) max(a[i],a[i+2])
#include <iostream>
using namespace std;
#define int long long
const int N = 200010;
int a[N];
void solve()
{
int n;cin>>n;
for(int i=1;i<=n;i++)cin>>a[i];
int res=0;
for(int i=2;i<n;i++)
{
if(a[i]>a[i-1]&&a[i]>a[i+1])
{
a[i+1]=max(a[i],a[i+2]);
res++;
}
}
cout<<res<<'\n';
for(int i=1;i<=n;i++)cout<<a[i]<<" ";
cout<<'\n';
}
signed main()
{
int T;cin>>T;
while(T--)solve();
}
C. Differential Sorting—构造
题意：
给一个数组，进行 a x = a y − a z （ 1 < = x < y < z < = n ） a_x=a_y-a_z（1<=x<y<z<=n） ax=ay−az（1<=x<y<z<=n）使数组变为非严格单调递增的,输出步数和方案
思路：
可以发现数列必须满足 a n > = 0 且 a n > = a n − 1 a_n>=0且a_n>=a_{n-1} an>=0且an>=an−1才可能有解,因为最后两项无法通过操作变换，然后特判一下为0的情况。
把 a n − 1 a_{n-1} an−1前的数全变成 a n − 1 − a n a_{n-1}-a_n an−1−an就构造出来满足条件的数列了
#include <iostream>
using namespace std;
#define int long long
const int N = 200010;
int a[N];
void solve()
{
int n;cin>>n;
for(int i=1;i<=n;i++)cin>>a[i];
if(a[n-1]>a[n]){cout<<-1<<'\n';return ;}
if(a[n]<0)
{
for(int i=1;i<n;i++)if(a[i]>a[i+1]){cout<<-1<<'\n';return ;}
cout<<0<<'\n';return ;
}
cout<<n-2<<'\n';
for(int i=1;i<=n-2;i++)cout<<i<<" "<<n-1<<" "<<n<<'\n';
}
signed main()
{
int T;cin>>T;
while(T--)solve();
}
D. Infinite Set
题解转自：pzr—作者主页
#include <iostream>
#include <map>
using namespace std;
#define int long long
const int N = 200010,mod = 1e9+7;
int n,p;
int s[N],fib[N],a[N];
map<int,int>mp;
signed main()
{
cin>>n>>p;
for(int i=1;i<=n;i++)cin>>a[i],mp[a[i]]=1;
//预处理
fib[0]=fib[1]=1;s[0]=1,s[1]=2;
for(int i=2;i<=p;i++)
{
fib[i]=(fib[i-1]+fib[i-2])%mod;
s[i]=(s[i-1]+fib[i])%mod;
}
for(int i=1;i<=n;i++)
{
int x=a[i];
while(x)
{
if(x%2==0&&x%4)break;
if(x%4==0)x/=4;
else x/=2;
if(mp.count(x)){mp.erase(a[i]);break;}
}
}
int res=0;
for(auto [x,c] : mp)
{
int t = 64-__builtin_clzll(x);
if(t>p)continue;
res=(res+s[p-t])%mod;
}
cout<<res<<'\n';
}
E. Cars
题解转自：严格鸽—作者主页
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
#define int long long
const int N = 200010,mod = 1e9+7;
int n,m;
vector<int>g[N];
vector<tuple<int,int,int> >e;
bool vis[N],flag=true;
int col[N];
void dfs(int u,int color)
{
if(vis[u])
{
if(col[u]!=color)flag=false;
return ;
}
vis[u]=1;col[u]=color;
for(auto v : g[u])
dfs(v,color^1);
}
bool paint()
{
for(int i=1;i<=n;i++)
if(!vis[i])dfs(i,0);
return flag;
}
int din[N],res[N];
bool topsort()
{
for(int i=1;i<=n;i++)for(auto v : g[i])din[v]++;
queue<int>q;
for(int i=1;i<=n;i++)if(!din[i])q.push(i);
int cnt=0;
while(q.size())
{
auto t = q.front();
q.pop();
res[t]=++cnt;
for(auto v : g[t])
if(--din[v]==0)q.push(v);
}
return cnt==n;
}
signed main()
{
cin>>n>>m;
int c,a,b;
for(int i=1;i<=m;i++)
{
cin>>c>>a>>b;
e.push_back({c,a,b});
g[a].push_back(b);
g[b].push_back(a);
}
if(!paint()){cout<<"NO\n";return 0;}
for(int i=1;i<=n;i++)g[i].clear();
for(auto [type,u,v] : e)
{
if(col[u]==1)swap(u,v);
if(type==1)g[u].push_back(v);
else g[v].push_back(u);
}
if(!topsort()){cout<<"NO\n";return 0;}
cout<<"YES\n";
for(int i=1;i<=n;i++)cout<<(col[i]==0?"L ":"R ")<<res[i]<<'\n';
}