打的最离谱的一场,全错在特判。
A略
B
注意特判k=1
C
先排序,二分找到ai+aj>=n,注意算的时候a必须小于n,这样才能保证配对时另一个大于0。
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=2e5+10;
int T,n,m,a[N],ans,s[N];
void init()
{ans=0;
}
void solve()
{cin>>n>>m;init();for(int i=1;i<=m;i++){cin>>a[i];a[i]=min(a[i],n-1);}sort(a+1,a+m+1);for(int i=1;i<=m;i++) s[i]=s[i-1]+a[i];for(int i=1;i<m;i++){int k=lower_bound(a+1+i,a+m+1,n-a[i])-a;if(k>i){ans+=s[m]-s[k-1]+(a[i]+1-n)*(m-k+1);}}cout<<ans*2<<endl;
}
signed main()
{std::ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);cin>>T;while(T--) solve();
}
D
把x和y转化为二进制,除以2的k次向下取整的操作转化为去掉二进制的后k位后的其他一模一样。我们每次可以去掉1 2 3....位,代价是二的次幂,而且只能选一次,求最小代价。想到01背包
f[i][j]代表x去掉i位,y去掉j位后最小代价。f[i][j]=min(f[i][j],f[i-k][j]+1<<k,f[i][j-k]+1<<k),把这个当当作预处理,然后枚举x和y分别去掉了几位,判断剩下的是否相等,如果相等代入f值找最小。注意不一定x和y尽量去最位答案最小。
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=2e5+10;
int T,x,y,f[101][101],ans,ll;
void init()
{ans=0x3f3f3f3f3f3f3f;
}
void solve()
{cin>>x>>y;init();for(int i=0;i<=60;i++)for(int j=0;j<=60;j++){int xx=x>>i,yy=y>>j;if(xx==yy) ans=min(ans,f[i][j]);}cout<<ans<<endl;
}
signed main()
{std::ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);ll=1;for(int i=0;i<=60;i++)for(int j=0;j<=60;j++)f[i][j]=0x3f3f3f3f3f3f;f[0][0]=0;for(int i=1;i<=60;i++){for(int j=60;j>=0;j--)for(int k=60;k>=0;k--){if(j>=i) f[j][k]=min(f[j][k],f[j-i][k]+(ll<<i));if(k>=i) f[j][k]=min(f[j][k],f[j][k-i]+(ll<<i));}}cin>>T;while(T--) solve();
}