A.买礼物
Time Limit: 1000 MS Memory Limit: 524288 KB
题目描述
鱼大大为了给羊大大过生日，于是跑到了商城准备买一堆不同价格的礼物送给羊大大。
商城里礼物价格分别是 1元,2元4元,8元,16元....后面一个是前面的2倍。每个价格的商品只有1个，鱼大大可以随意挑选。
为了打肿脸充胖子，鱼大大觉得只有花至少A元买礼物才不会掉面子。然而鱼大大带的钱有是有限的，所以礼物的价格合计不能超过B元。
问鱼大大最多能买多少个礼物？
输入格式
多组测试。第一行一个整数T，表示测试组数量。
接下来T行，每行2个整数为一组，为鱼大大至少要花的钱和最多能花的钱。
输出格式
每行一个整数表示鱼大大最多能买多少礼物。
Input
2 16 25 4 8
4 3
数据范围
1≤T≤100000
1≤A≤B≤2^63−1
样例解释
对于第一组数据：
鱼大大可以买1元、2元、4元、16元这4个礼物共计23元；
对于第二组数据：
鱼大大可以买1元、2元、4元这3个礼物共计7元
（方案可能不唯一，只需输出最多数量）
∵题目要求买礼物的?≥A元且≤B元，而且后面一个礼物刚好是前面一个的2倍，∴可以先将A元转化成二进制数。
1的位置是肯定要选的。那么A元就有了。剩下还能买多少，只需要（B-A元）贪心策略。从小到大开始买，买了之后超不超过B元，超过了就终止。（这道题的核心是二进制）
1 #include<bits/stdc++.h> 2 using namespace std; 3 #define int long long 4 inline void solve(){ 5 int a,b; 6 cin>>a>>b; 7 int res=0; 8 for(int i=62;i>=0;i--){ 9 if(a>>i&1){ 10 res++; 11 } 12 } 13 for(int i=0;i<=62;i++){ 14 if(a>>i&1) continue; 15 else{ 16 int x=1; 17 a+=(x<<i); 18 if(a<=b) res++; 19 } 20 } 21 cout<<res<<"\n"; 22 } 23 signed main(){ 24 int T; 25 cin>>T; 26 while(T--){ 27 solve(); 28 } 29 return 0; 30 } 31 32 33 编译结果 34 compiled successfully 35 time: 150ms, memory: 3492kb, score: 100, status: Accepted 36 > test 1: time: 0ms, memory: 3396kb, points: 5, status: Accepted 37 > test 2: time: 1ms, memory: 3376kb, points: 5, status: Accepted 38 > test 3: time: 1ms, memory: 3400kb, points: 5, status: Accepted 39 > test 4: time: 1ms, memory: 3440kb, points: 5, status: Accepted 40 > test 5: time: 0ms, memory: 3388kb, points: 5, status: Accepted 41 > test 6: time: 0ms, memory: 3436kb, points: 5, status: Accepted 42 > test 7: time: 0ms, memory: 3436kb, points: 5, status: Accepted 43 > test 8: time: 1ms, memory: 3364kb, points: 5, status: Accepted 44 > test 9: time: 1ms, memory: 3404kb, points: 5, status: Accepted 45 > test 10: time: 1ms, memory: 3404kb, points: 5, status: Accepted 46 > test 11: time: 1ms, memory: 3440kb, points: 5, status: Accepted 47 > test 12: time: 1ms, memory: 3404kb, points: 5, status: Accepted 48 > test 13: time: 0ms, memory: 3376kb, points: 5, status: Accepted 49 > test 14: time: 0ms, memory: 3452kb, points: 5, status: Accepted 50 > test 15: time: 0ms, memory: 3476kb, points: 5, status: Accepted 51 > test 16: time: 41ms, memory: 3456kb, points: 5, status: Accepted 52 > test 17: time: 43ms, memory: 3400kb, points: 5, status: Accepted 53 > test 18: time: 10ms, memory: 3444kb, points: 5, status: Accepted 54 > test 19: time: 48ms, memory: 3376kb, points: 5, status: Accepted 55 > test 20: time: 0ms, memory: 3492kb, points: 5, status: Accepted
B.最大之或
Time Limit: 1000 MS Memory Limit: 524288 KB
题目描述
给定一个数组 A，有 n 个元素。现在需要你选定一个数 y，用 y 对数组 A 中 的每一个元素进行或运算，会得到一个新序列构成的数组 B，对于数组 B 中的元素 B[i]，有 B[i]=a[i] ∣ y。若限定你可以选定的数不超过某个值 x (y≤x)， 你能算出满足数组 B 至少有两个不同元素的 y 最大值么？
输入格式
有多组数据，第一行一个整数 T 表示数据组数。
每组数据：
第一行包含两个整数 n 和 x。
第二行 n 个整数 a1∼an。
输出格式
一个整数，表示能使得到的新数组的最大值。
Input1
3 3 5 1 1 2 5 10 4 5 2 3 5 3 3 1 1 3
Output1
5 10 1
数据范围
1≤T≤10^5,2≤n≤10^5, 0≤x, a[i]≤2^30
保证 n 之和 不超过 2∗10^5
这道题需要利用位运算，否则会超时（n log n）。可以用拆位贪心。
1 #include<bits/stdc++.h> 2 using namespace std; 3 #define int long long 4 const int N=1e5+10; 5 int ar[N]; 6 int n,x; 7 inline void solve(){ 8 cin>>n>>x; 9 for(int i=1;i<=n;i++){ 10 cin>>ar[i]; 11 } 12 int flag=0; 13 int res=0; 14 for(int i=30;i>=0;i--){ 15 if(!flag&&(x>>i&1)){ 16 res+=1<<i; 17 set<int> q; 18 for(int j=1;j<=n;j++){ 19 q.insert(ar[j]|res); 20 } 21 if(q.size()==1) res-=1<<i,flag=1; 22 }else if(flag==1){ 23 res+=1<<i; 24 set<int> q; 25 for(int j=1;j<=n;j++){ 26 q.insert(ar[j]|res); 27 } 28 if(q.size()==1) res-=1<<i; 29 } 30 } 31 cout<<res<<"\n"; 32 } 33 signed main(){ 34 int T; 35 cin>>T; 36 while(T--){ 37 solve(); 38 } 39 return 0; 40 } 41 42 编译结果 43 compiled successfully 44 time: 406ms, memory: 4288kb, score: 100, status: Accepted 45 > test 1: time: 1ms, memory: 3448kb, points: 10, status: Accepted 46 > test 2: time: 42ms, memory: 4168kb, points: 10, status: Accepted 47 > test 3: time: 38ms, memory: 4288kb, points: 10, status: Accepted 48 > test 4: time: 47ms, memory: 4104kb, points: 10, status: Accepted 49 > test 5: time: 44ms, memory: 4164kb, points: 10, status: Accepted 50 > test 6: time: 44ms, memory: 4248kb, points: 10, status: Accepted 51 > test 7: time: 47ms, memory: 4168kb, points: 10, status: Accepted 52 > test 8: time: 51ms, memory: 4160kb, points: 10, status: Accepted 53 > test 9: time: 41ms, memory: 4180kb, points: 10, status: Accepted 54 > test 10: time: 51ms, memory: 4172kb, points: 10, status: Accepted
C.亲和数
Time Limit: 1000 MS Memory Limit: 65536KB
某一天，tenshi看了一本趣味数学书，上面提到了亲和数：定义数对 (x,y) 为亲和数对当且仅仅当x、y为不同正整数，且x、y各自的所有非自身正因子之和等于另一个数。例如 (220,284) 和 (280,224) 都是亲和数对，因为：
220的所有非自身正因子之和为：1 + 2 + 4 + 5 + 10 + 11 + 20 + 22 + 44 + 55 + 110 = 284
284的所有非自身正因子之和为：1 + 2 + 4 + 71 + 142 = 220
数对 (x,y ) 跟 (y,x) 被认为是同一数对，所以我们只考虑 x任务：tenshi对某个范围内的亲和数对的数量非常感兴趣，所以希望你能帮她编写一个程序计算给定范围内的亲和数对的数量。
输入格式：
给定一个范围A到B，如果A≤ x ≤ B，则我们称 (x,y)在范围[A,B]内。
1 ≤ A ≤ B ≤ 10^8 且 B-A ≤ 10^5
输出格式：
输出文件只有一行，就是[A,B]内亲和数对的数量
样例输入：
样例输出：
1 #include<bits/stdc++.h> 2 using namespace std; 3 #define int long long 4 int a,b,sum; 5 map<int,int> mp; 6 inline void check(int mid){ 7 int res=1; 8 for(int i=2;i*i<=mid;i++){ 9 if(mid%i==0){ 10 if(mid/i==i) res+=i; 11 else{ 12 res+=i; 13 res+=mid/i; 14 } 15 } 16 } 17 int ans=1; 18 for(int i=2;i*i<=res;i++){ 19 if(res%i==0){ 20 if(res/i==i) ans+=i; 21 else{ 22 ans+=i; 23 ans+=res/i; 24 } 25 } 26 } 27 if(ans==mid&&mid<res){ 28 sum++; 29 mp[res]=1; 30 } 31 } 32 inline void solve(){ 33 cin>>a>>b; 34 for(int i=max(a,2ll);i<=b;i++){ 35 if(mp.count(i)) continue; 36 check(i); 37 } 38 cout<<sum<<"\n"; 39 } 40 signed main(){ 41 solve(); 42 return 0; 43 } 44 45 编译结果 46 compiled successfully 47 time: 2523ms, memory: 3484kb, score: 100, status: Accepted 48 > test 1: time: 1ms, memory: 3364kb, points: 10, status: Accepted 49 > test 2: time: 21ms, memory: 3448kb, points: 10, status: Accepted 50 > test 3: time: 0ms, memory: 3484kb, points: 10, status: Accepted 51 > test 4: time: 157ms, memory: 3444kb, points: 10, status: Accepted 52 > test 5: time: 16ms, memory: 3396kb, points: 10, status: Accepted 53 > test 6: time: 492ms, memory: 3436kb, points: 10, status: Accepted 54 > test 7: time: 64ms, memory: 3348kb, points: 10, status: Accepted 55 > test 8: time: 872ms, memory: 3436kb, points: 10, status: Accepted 56 > test 9: time: 742ms, memory: 3460kb, points: 10, status: Accepted 57 > test 10: time: 158ms, memory: 3380kb, points: 10, status: Accepted
D.异或算1
题目描述
鱼大大非常擅(tao)长(yan)运用位运算。这不人强是非多嘛，羊大大又找到了鱼大大以(yi)求(ci)帮(diao)忙(nan)，解决一个问题。
羊大大给了鱼大大一组数字A，和两个区间[L1,R1],[L2,R2]，要求在第一个区间内选一个数字Ai,再在第二个区间内选择一个数字Aj,使得Ai⊕Aj的结果第K位上为1的方案有几种，⊕⊕表示按位异或。
输入格式
第一行两个数字n, m；表示数字的个数以及询问的次数。
接下来一行是n个非负整数，表示{a1...an}。
接下来m行每行5个整数k, L1, R1, L2, R2。
输出格式
m行。每行一个数字，表示答案。
Input 1
5 1 1 2 4 3 2 2 1 2 3 5
Output 1
2
Input 2
6 2 3 5 6 13 12 20 1 1 4 5 6 3 2 3 4 6
Output 2
4 4
数据范围
2≤n≤105
1≤m≤105
0≤Ai<260
1≤L1≤R1<L2≤R2≤n
0≤k<60
样例解释
样例1中，准备运算的数字有 ｛1 ,2, 4, 3 ,2｝;
第一次询问中，
第一个区间L1~R1为 [1,2]，
第二个区间L2~R2为[3,5]；
分别有数字｛1,2｝和｛4,3,2｝;
k为2，则是问第2位上1的个数分别进行异或运算则有：最低位为第0位
1 ^ 4 = 5 = 0b 0101 第2位为1
1 ^ 3 = 2 = 0b 010 第2位为0
1 ^ 2 = 3 = 0b 011 第2位为0
2 ^ 4 = 6 = 0b 110 第2位为1
2 ^ 3 = 1 = 0b 001 第2位为0
2 ^ 2 = 0 = 0b 000 第2位为0
共2个1，输出2；
1 #include<bits/stdc++.h> 2 using namespace std; 3 #define int long long 4 const int N=1e5+10; 5 int n,m; 6 int f[N][60]; 7 inline void solve(){ 8 cin>>n>>m; 9 for(int i=1;i<=n;i++){ 10 int a; 11 cin>>a; 12 for(int j=0;j<60;j++){ 13 f[i][j]=f[i-1][j]; 14 if((a>>j)&1) f[i][j]++; 15 } 16 } 17 while(m--){ 18 int k,l1,r1,l2,r2; 19 cin>>k>>l1>>r1>>l2>>r2; 20 int a=f[r1][k]-f[l1-1][k],b=f[r2][k]-f[l2-1][k]; 21 int a1=r1-l1+1-a,b1=r2-l2+1-b; 22 int sum=a*b1+b*a1; 23 cout<<sum<<"\n"; 24 } 25 } 26 signed main(){ 27 solve(); 28 return 0; 29 } 30 31 编译结果 32 compiled successfully 33 time: 406ms, memory: 19384kb, score: 100, status: Accepted 34 > test 1: time: 1ms, memory: 3396kb, points: 5, status: Accepted 35 > test 2: time: 1ms, memory: 3384kb, points: 5, status: Accepted 36 > test 3: time: 1ms, memory: 3392kb, points: 5, status: Accepted 37 > test 4: time: 0ms, memory: 3300kb, points: 5, status: Accepted 38 > test 5: time: 0ms, memory: 3444kb, points: 5, status: Accepted 39 > test 6: time: 1ms, memory: 3408kb, points: 5, status: Accepted 40 > test 7: time: 1ms, memory: 3400kb, points: 5, status: Accepted 41 > test 8: time: 0ms, memory: 3376kb, points: 5, status: Accepted 42 > test 9: time: 34ms, memory: 16784kb, points: 5, status: Accepted 43 > test 10: time: 13ms, memory: 6828kb, points: 5, status: Accepted 44 > test 11: time: 37ms, memory: 6896kb, points: 5, status: Accepted 45 > test 12: time: 32ms, memory: 14620kb, points: 5, status: Accepted 46 > test 13: time: 32ms, memory: 8496kb, points: 5, status: Accepted 47 > test 14: time: 60ms, memory: 12792kb, points: 5, status: Accepted 48 > test 15: time: 42ms, memory: 3700kb, points: 5, status: Accepted 49 > test 16: time: 45ms, memory: 17356kb, points: 5, status: Accepted 50 > test 17: time: 29ms, memory: 5888kb, points: 5, status: Accepted 51 > test 18: time: 18ms, memory: 6780kb, points: 5, status: Accepted 52 > test 19: time: 42ms, memory: 19384kb, points: 5, status: Accepted 53 > test 20: time: 17ms, memory: 9912kb, points: 5, status: Accepted