A. Candies
题意:当k>1时输出满足题中所给数列的x值
解题思路：等比数列得(2^k-1)x=n,枚举k值即可、
Code:
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll t,n;
int main(){
cin>>t;
while(t--){
cin>>n;
ll k=3;
while(1){
if(n%k==0){
cout<<n/k<<endl;
break;
}
k=k*2+1;
}
}
return 0;
}
B. Balanced Array
题意：构建一个长度为n的序列，前n/2全为偶数，后半部分全为奇数，且前后两部分相等
解题思路：当n/2为奇数时，前后两部分和奇偶不同，显然不成立，所以n/2为偶数，其他数从小到大排，最后一个数特别构造即可。
Code:
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll t,n;
int main(){
cin>>t;
while(t--){
cin>>n;
ll k=n/2;
if(k&1) puts("NO");
else {
puts("YES");
for(int i=2,j=1;j<=k;i+=2,j++){
cout<<i<<' ';
}
for(int i=1,j=1;j<k;i+=2,j++){
cout<<i<<' ';
}
cout<<(n-1)+k<<endl;
}
}
return 0;
}
C. Alternating Subsequence
题意：在序列中找到最长的奇偶相间的子序列，并且该子序列在最长序列中值最大
思路：首先长度优先，其次在每段长度相同的序列中取最大值
Code：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 2e5+5;
ll t,n;
ll a[N];
int main(){
cin>>t;
while(t--){
cin>>n;
for(int i=0;i<n;i++) cin>>a[i];
ll tmp=a[0],ans=0;
for(int i=1;i<n;i++){
if(tmp*a[i]<0){
ans+=tmp;
tmp=a[i];
}
else{
tmp=max(tmp,a[i]);
}
}
cout<<ans+tmp<<endl;
}
return 0;
}
D. Constant Palindrome Sum
题意：对序列中的元素可以用[1,k]中的数来替换，使1~n/2的所有i都有a[i]+a[n-i+1]=x且x值相等
解题思路：可以假设对于每个x值都需要n次替换，而a[i]+a[n-i+1]取值范围在[2,2*k],计算每对替换一次能得到的最大值最小值；
因此对于x值介于最大值最小值之间的只需替换一次，对于其他范围需要替换两次，这时我们可以运用差分将最大值最小值之间的x值
替换的次数都减1，而对于不用变换就能得到的也需要减1
Code：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 2e5+100;
ll a[N],cnt[N*2],sub[N*2];
ll t,n,k;
int main(){
cin>>t;
while(t--){
cin>>n>>k;
for(int i=1;i<=n;i++) cin>>a[i];
for(int i=2;i<=2*k;i++) cnt[i]=n,sub[i]=0;//每一对都初始化为2次，初始化差分数组
for(int i=1;i<=n/2;i++){
ll x=a[i],y=a[n-i+1];
ll mi=min(x,y)+1,mx=max(x,y)+k;
cnt[x+y]--;//不用变换的值减1
sub[mi]--;sub[mx+1]++;//对区间[mi,mx]之间的x值都减1
}
ll ans=0x3f3f3f3f;
for(int i=2;i<=2*k;i++){
sub[i]+=sub[i-1];//前缀和
cnt[i]+=sub[i];
ans=min(ans,cnt[i]);
}
cout<<ans<<'
';
}
return 0;
}
E. Weights Distributing
题意：找到a->b->c的最短花费
解题思路：找中间点a->x->b->x->c，可以看出b->x这条边计算两次，所以它的权值应该最小。
从1~n枚举x，然后计算a,b,c到x点的边数，最后找最小值即可
Code：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 2e5+100,INF=0x3f3f3f3f;
ll p[N],sum[N];
int t,n,m,a,b,c;
vector<int>g[N];
void bfs(int x,vector<int>&d){
d[x]=0;
queue<int>q;
q.push(x);
while(!q.empty()){
int p=q.front();
q.pop();
for(int i=0;i<g[p].size();i++){
int v=g[p][i];
if(d[v]==INF){
d[v]=d[p]+1;
q.push(v);
}
}
}
}
int main(){
cin>>t;
while(t--){
cin>>n>>m>>a>>b>>c;
for(int i=1;i<=n;i++) g[i].clear();
for(int i=1;i<=m;i++) cin>>p[i];
sort(p+1,p+m+1);
for(int i=0;i<m;i++){
int x,y;
cin>>x>>y;
g[x].push_back(y);
g[y].push_back(x);
}
vector<int>da(n+1,INF),db(n+1,INF),dc(n+1,INF);
bfs(a,da);bfs(b,db);bfs(c,dc);//da表示a到每个点的边数
memset(sum,0,sizeof(sum));
for(int i=1;i<=m;i++){//前i条边的和
sum[i]=sum[i-1]+p[i];
}
ll ans=1e18;
for(int i=1;i<=n;i++){
// cout<<da[i]+db[i]+dc[i]<<endl;
if(da[i]+db[i]+dc[i]<=m){
ans=min(ans,sum[db[i]]+sum[da[i]+db[i]+dc[i]]);
}
}
cout<<ans<<'
';
}
return 0;
}