题目链接:A、Johnny and Ancient Computer
题意:
给你两个数a,b。问你可不可以通过左移位运算或者右移位运算使得它们两个相等。可以的话输出操作次数,不可以输出-1
一次操作可以最多左移3次或者右移3次
题解:
首先找寻一下这两个数的二进制形式下最右边那个1在什么位置。然后看一下它们的差距是多少(设为x)
那么就让a,b中小的那个数左移x位。之后判断一下它们两个相等不相等就可以了
代码:
1 #include<stdio.h>
2 #include<algorithm>
3 #include<iostream>
4 #include<string>
5 #include<queue>
6 #include<deque>
7 #include<string.h>
8 #include<map>
9 #include <iostream>
10 #include <math.h>
11 using namespace std;
12 typedef long long ll;
13 const int maxn=500+10;
14 int main()
15 {
16 ll t;
17 scanf("%I64d",&t);
18 while(t--)
19 {
20 ll a,b,sum1=0,sum2=0,sum=0;
21 scanf("%I64d%I64d",&a,&b);
22 ll aa=a,bb=b;//printf("%I64d**%I64d\n",aa,aa&1);
23 while((aa&1)==0)
24 {
25
26 sum1++;
27 aa>>=1;
28 }
29 while((bb&1)==0)
30 {
31 sum2++;
32 bb>>=1;
33 }
34 if(a<b) swap(a,b);
35 //printf("%I64d****%I64d %I64d\n",sum1-sum2,sum1,sum2);
36 if(sum1<sum2) swap(sum1,sum2);
37
38 if((sum1-sum2)==0)
39 {
40 if(a==b)
41 printf("0\n");
42 else printf("-1\n");
43 }
44 else if((sum1-sum2)%3)
45 {
46
47 sum=(sum1-sum2)/3+1;
48 //printf("%I64d %I64d %I64d\n",sum1-sum2,b,b<<(sum1-sum2));
49 b<<=(sum1-sum2);
50
51 if(a==b)
52 printf("%I64d\n",sum);
53 else printf("-1\n");
54 }
55 else
56 {
57 sum=(sum1-sum2)/3;
58 b<<=(sum1-sum2);
59 if(a==b)
60 printf("%I64d\n",sum);
61 else printf("-1\n");
62 }
63 }
64 return 0;
65 }
题目链接:B、Johnny and His Hobbies
题意:
给你一个有n个元素的集合v,给你两个集合a,b(集合内元素都是int类型)。如果把a数组中元素和b中元素都分别按照从小到大排序。如果排序后两个集合一摸一样,那就说着a,b两个集合相等
现在你需要找到一个最小的k,使得v集合中每一个元素都与k进行异或操作,你需要保证异或后得到的那个集合和原集合相等。
如果你找不到这个k,那就输出-1
题解:
首先如果n为奇数那么肯定输出-1,因为如果要满足题意的话,那肯定是v[i]异或k之后这个值和v[i]相互对应,毕竟k被异或两个相当于没有被异或,即v[i]=v[i]^k^k
之后我还想着n为偶数情况也是找规律,没想到。。。
偶数方面就暴力,因为n本身就不大
如果v集合中两个元素x和y相对应,那么x^y这个值就满足题意(虽然可能不是最小的k),那么我们就先确定x为v集合中第一个元素v[1],对y就是暴力枚举。
找到x和y之后,我们这里设ans=x^y
那么v集合中其他元素与ans异或之后的元素肯定也在v集合中,如果有一个不在,那么ans就不满足题意
用一个变量 minn来保存那个满足题意得最小的ans就行
代码:
1 #include<stdio.h>
2 #include<algorithm>
3 #include<iostream>
4 #include<string>
5 #include<queue>
6 #include<deque>
7 #include<string.h>
8 #include<map>
9 #include <iostream>
10 #include <math.h>
11 using namespace std;
12 typedef long long ll;
13 const int maxn=1024+10;
14 const int INF=0x3f3f3f3f;
15 int w[maxn],v[maxn];
16 int main()
17 {
18 int t;
19 scanf("%d",&t);
20 while(t--)
21 {
22 int n;
23 memset(w,0,sizeof(w));
24 scanf("%d",&n);
25 for(int i=1;i<=n;++i)
26 {
27 scanf("%d",&v[i]);
28 w[v[i]]=1;
29 }
30 if(n%2)
31 {
32 printf("-1\n");
33 continue;
34 }
35 //sort(v+1,v+1+n);
36 int minn=INF;
37 for(int i=2;i<=n;++i)
38 {
39 int ans=v[1]^v[i],flag=0;
40 for(int j=2;j<=n;++j)
41 {
42 if(i==j) continue;
43 if(w[ans^v[j]]);
44 else
45 {
46 flag=1;
47 break;
48 }
49 }
50 if(flag==0)
51 {
52 minn=min(minn,ans);
53 }
54 }
55 if(minn==INF)
56 {
57 printf("-1\n");
58 }
59 else
60 {
61 printf("%d\n",minn);
62 }
63 }
64 return 0;
65 }
题目链接:C、Johnny and Another Rating Drop
题意:
给你一个n,然后找出来1,2,3…n中相邻得两个数中二进制形式下有多少位不相同
例如3和4
3二进制为011
4二进制为100
那么它们两个有3位不同
题解:
找规律,好多题解都说的找规律;没找规律的题解也没看太明白
F(n)=F(n/2)+n
代码:
1 #include<stdio.h>
2 #include<algorithm>
3 #include<iostream>
4 #include<string>
5 #include<queue>
6 #include<deque>
7 #include<string.h>
8 #include<map>
9 #include <iostream>
10 #include <math.h>
11 using namespace std;
12 typedef long long ll;
13 const int maxn=1024+10;
14 const int INF=0x3f3f3f3f;
15 int main()
16 {
17 int t;
18 cin>>t;
19 while(t--)
20 {
21 long long n,ans=0;
22 cin>>n;
23 while(n)
24 {
25 ans+=n;
26 n/=2;
27 }
28 cout<<ans<<endl;
29 }
30 }