A
.
A
r
r
a
y
B
a
l
a
n
c
i
n
g
A.\ Array\ Balancing
A. Array Balancing
题意：
可以选择
i
i
i通过交换
a
i
,
b
i
a_i,b_i
ai,bi使相邻元素之间的差值之和最小。
这题猜了好长时间思路一直不对，但是其实很好想，运用宏观思维的话，因为这是两个序列，那肯定是小的和小的放在一起，大的与大的放在一起呀，
当然这样可能不太严谨，不过这只是个
A
A
A题QAQ
\令人头秃
#include
#define int long long
using namespace std;
const int N = 60;
int a[N],b[N];
int n;
void solve()
{
cin >> n;
for(int i=1;i<=n;i++) cin >> a[i];
for(int i=1;i<=n;i++) cin >> b[i];
for(int i=1;i<=n;i++){
if(a[i]>b[i]) swap(a[i],b[i]);
}
int res=0;
for(int i=1;i res+=abs(a[i]-a[i+1]); res+=abs(b[i]-b[i+1]); } cout << res << endl; } signed main(){ int t; cin >> t; while(t--) solve(); return 0; } 当然这里面的第一种方法我是没看懂的，但是第二种看起来很简单，那就是一对一对地比较交换前后的变化，如果交换之后绝对值之和变小了那就交换，就这样遍历完两个序列。 (感觉还是挺暴力的，我甚至马上排除了这种做法。。。) B . G e t t i n g Z e r o B.\ Getting\ Zero B. Getting Zero （这道题目好有趣！*…*) 又是一道有关位运算的题目！一生之敌！！！、 但是不得不说位运算真的很奇妙！但也很令人（我）头秃！ 这道题目： 首先我们可以发现题目给的模数非常特别！我没发现QAQ 众所周知 32768 32768 32768是 2 2 2的 15 15 15次方，对这个数取模就很怪（？） 32768 = ( 1000 0000 0000 0000 ) B 32768=(1000\ 0000\ 0000\ 0000)_B 32768=(1000 0000 0000 0000)B 当我们把给定的数都用二进制表示： 19 = ( 10011 ) B 19=(10011)_B 19=(10011)B 此时如果我们将他加 1 1 1，那么直观的，它变成了 20 20 20,不直观地，但也挺直观的，它变成了 ( 10100 ) B (10100)_B (10100)B,如果此时我们将他右移 15 − 2 = 13 15-2=13 15−2=13位，那么他将会以 1000 0000 0000 0000 1000\ 0000\ 0000\ 0000 1000 0000 0000 0000结尾，也就是说他能被这个数整除了，那取模就是 0 0 0了。 就是这么个思路，但是具体要加多少个 1 1 1和左移多少位合适，是要枚举一下的。 当然要看清数据范围， n n n取不到 0 0 0，但！ a a a可以取到，睁开眼睛啊！ 但是 0 0 0要特判一下，上述写法 0 0 0过不了QAQ（因为WA了） 还有 r e s res res记得每次都要更新。 #include using namespace std; int a; signed main(){ int n,res=20; cin >> n; while(n--) { res=20; cin >> a; if(a==0){ cout << 0 << ' '; continue; } for(int i=0;i<=15;i++) { int add=i,cnt0=0; for(int j=0;j<=15;j++){ if(((a+add)>>j)&1) break;//右移直到最低位是1就结束，这样结束的时候cnt0记录的是最低位的0地数量（也就是不再需要左移的位数） cnt0++; } res=min(res,add+15-cnt0);//加1的操作数与需要左移的操作数 } cout << res << ' '; } return 0; } 其实代码中的记录 0 0 0的数量那一步想用 l o w b i t lowbit lowbit来实现来着，感觉本质上差不多，但是暂时还没想要怎么写，先写过再说。。。
发表评论