A. Array and Peaks
思路：
构造个峰需要
个元素，所以如果
那么无法构成，否则可以
从第二个位置开始放最大的数，每隔一个位置再放一个差值为1的数，放满k个，然后从头往后依次将没有填数的位置填上，依次从剩余的中没有的取掉的数从小到大取。
MyCode:
#include <bits/stdc++.h>
using namespace std;
const int maxn=2e5+7,maxm=1e7,mod=1e9+7;
typedef long long int ll;
typedef unsigned long long ull;
int n,k;
int a[105];
inline void solve() {
cin>>n>>k;
if((2*k+1)>n) {
cout<<"-1\n";
return;
}
int l=1,r=n;
for(int i=0; i<n; ++i) {
if(k&&(i&1)) {
a[i]=r--;
k-=1;
} else a[i]=l++;
}
for(int i=0; i<n; ++i) cout<<a[i]<<' ';
cout<<'\n';
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int _;
cin>>_;
while(_--) solve();
return 0;
} B. AND Sequences
思路： 的值不大于
，如果
的值小于
，那么
的值一定不等于
同理，
假设有cnt个数等于，那么答案就是
MyCode:
#include <bits/stdc++.h>
using namespace std;
const int maxn=2e5+7,maxm=1e7,mod=1e9+7;
typedef long long int ll;
typedef unsigned long long ull;
int n,sum,cnt;
int a[maxn],pw[maxn];
inline void solve() {
cin>>n;
cin>>a[1];
sum=a[1],cnt=0;
for(int i=2;i<=n;++i) {
cin>>a[i];
sum&=a[i];
}
for(int i=1;i<=n;++i) if(a[i]==sum) cnt+=1;
int ans=1LL*cnt*(cnt-1)%mod*pw[n-2]%mod;
cout<<ans<<'\n';
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
pw[0]=pw[1]=1;
for(int i=2;i<maxn;++i) pw[i]=1LL*pw[i-1]*i%mod;
int _;
cin>>_;
while(_--) solve();
return 0;
} C. Add One
思路：
发现爆搜剪枝时间复杂度貌似不大，就冲了。
记忆化搜索，挺快的
MyCode:
#include <bits/stdc++.h>
using namespace std;
const int maxn=2e5+7,mod=1e9+7;
typedef long long int ll;
typedef unsigned long long ull;
int a[maxn],b[maxn];
void dfs(int m,bool s) {
if(s) {
if(a[m]) return;
if(m<9) {
a[m]=2;
return;
}
else {
dfs(m-9,s); dfs(m-9,false);
a[m]=(1LL*(a[m-9]+b[m-9]))%mod;
}
}
else {
if(b[m]) return;
if(!m) {
b[m]=1;
return;
}
else {
dfs(m-1,true);
b[m]=a[m-1];
}
}
}
string s;
int m,len,x;
inline void solve() {
cin>>s>>m;
len=s.size();
ll ans(0);
for(int i=0;i<len;++i) {
if(s[i]=='1'&&i+1!=len&&s[i+1]=='0') {
dfs(m,true);
ans+=a[m];
i+=1;
}
else {
x=10-(s[i]-'0');
if(x<=m) {
dfs(m-x,true);
ans+=a[m-x];
}
else ans+=1;
}
while(ans>=mod) ans-=mod;
}
cout<<ans<<'\n';
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
dfs(200000,true);
int _;
cin>>_;
while(_--) solve();
return 0;
} D. GCD and MST
思路：
构造一颗最小生成树，考虑用算法。
先默认生成树由条边权为
的边构成。每次都从图中拿一个最小的边替代默认边权为
的边，然后标记端点，直到剩下的边的边权不小于
。而图中剩余边的边权等于端点上两个值的最小值，所以先对数组排序，然后从小到大遍历每个点的每条边，由于图中剩余边的性质，该点所有剩余边连起来后会形成一个连通块，且点是连续的，所以不需要用并查集维护。
MyCode:
#include <bits/stdc++.h>
using namespace std;
const int maxn=2e5+7,maxm=2e5+7,mod=1e9+7;
typedef long long int ll;
typedef unsigned long long ull;
struct node{
int v,pos;
bool operator<(const node& a)const{
return v<a.v;
}
}a[maxn];
int n,p,pos[maxn];
bool vis[maxn];
ll ans;
inline void work(int x) {
int cnt(0);
for(int i=x-1;i&&pos[i]%pos[x]==0;--i) {
cnt+=1;
if(vis[i]) break;//左边的连通块，只要向它连一条边
vis[i]=true;
}
for(int i=x+1;i<=n&&pos[i]%pos[x]==0;++i) {
cnt+=1;
if(vis[i]) break;//右边的连通块，只要向它连一条边
vis[i]=true;
}
vis[x]=true;
ans-=1LL*cnt*p;
ans+=1LL*cnt*pos[x];
}
inline void solve() {
cin>>n>>p;
for(int i=1;i<=n;++i) {
cin>>a[i].v;
vis[i]=false;
pos[i]=a[i].v; a[i].pos=i;
}
sort(a+1,a+1+n);
ans=1LL*(n-1)*p;
for(int i=1;i<=n;++i) {
if(a[i].v>=p) break;
if(vis[a[i].pos]) continue;
work(a[i].pos);
}
cout<<ans<<'\n';
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int _=1;
cin>>_;
while(_--) solve();
} E. Cost Equilibrium
思路：
这题和F一样麻烦，不会详细证明，只能意会一下
小于平均数的全部放在大于平均数的右边，等于平均数的随意摆放，试着用试着证明，太复杂算了
涉及到组合数的问题，有重复的数的排列
MyCode:
#include <bits/stdc++.h>
using namespace std;
const int maxn=1e5+7,maxm=1e7,mod=1e9+7;
typedef long long int ll;
typedef unsigned long long ull;
int n,a[maxn],avg,x,y,m;
ll pw[maxn],inv[maxn];
ll qpow(ll a,int b) {
ll res=1;
while(b) {
if(b&1) res=res*a%mod;
a=a*a%mod;
b>>=1;
}
return res;
}
inline ll C(int n,int m) {
return pw[n]*qpow(pw[m]*pw[n-m]%mod,mod-2)%mod;
}
int num[maxn],to[maxn],tot;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
pw[0]=1;
for(int i=1; i<maxn; ++i) pw[i]=pw[i-1]*i%mod;
inv[maxn-1]=qpow(pw[maxn-1],mod-2);
for(int i=maxn-2; ~i; --i) inv[i]=inv[i+1]*(i+1)%mod;
cin>>n;
ll sum(0);
for(int i=1; i<=n; ++i) {
cin>>a[i];
sum+=a[i];
}
if(sum%n) return cout<<"0\n",0;
int cnt(1),cnt1(0),cnt2(0);
sort(a+1,a+1+n);
a[n+1]=-1;
for(int i=1; i<=n; ++i) {
if(a[i]==a[i+1]) ++cnt;
else {
num[++tot]=cnt;
to[tot]=a[i];
cnt=1;
}
}
int avg=sum/n;
for(int i=1; i<=n; ++i) cnt1+=(a[i]<avg),cnt2+=(a[i]>avg);
if(cnt1<=1||cnt2<=1) {
ll ans=pw[n];
for(int i=1; i<=tot; ++i) (num[i]>1)&&(ans=ans*inv[num[i]]%mod);
cout<<ans<<'\n';
} else {
ll res1=pw[cnt1],res2=pw[cnt2];
for(int i=1; i<=tot; ++i)
if(to[i]<avg) res1=res1*inv[num[i]]%mod;
else if(to[i]>avg) res2=res2*inv[num[i]]%mod;
int ans=1LL*res1*res2%mod*2%mod*C(n,cnt1+cnt2)%mod;
cout<<ans<<'\n';
}
return 0;
} F. Swapping Problem
思路：(不是很懂，只能看懂代码这么做的意义)
一、对，假设
，则
，交换
后：
1、 如果，
2、 如果，
即：
假设，那么只要取
内最大的
即可最小化
二、假设，则
，交换
后：
1、 如果，
1、 如果，
故这种情况交换交换后不会减少差值。
MyCode:
#include <bits/stdc++.h>
using namespace std;
const int maxn=2e5+7,maxm=1e7,mod=1e9+7;
typedef long long int ll;
typedef unsigned long long ull;
struct node{
int x,y; bool c;
bool operator<(const node&a)const{
return x<a.x;
}
}q[maxn];
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n,mx[2],res(0);
ll ans(0);
mx[0]=mx[1]=0;
cin>>n;
for(int i=1;i<=n;++i) cin>>q[i].x;
for(int i=1;i<=n;++i) {
cin>>q[i].y;
if(q[i].c=(q[i].x>q[i].y)) swap(q[i].x,q[i].y);
ans+=q[i].y-q[i].x;
}
sort(q+1,q+1+n);
for(int i=1,x,y;i<=n;++i) {
x=q[i].x,y=q[i].y;
res=max(res,min(y,mx[q[i].c^1])-x); mx[q[i].c]=max(mx[q[i].c],y);
}
cout<<ans-res*2<<'\n';
return 0;
} 
京公网安备 11010502036488号