Codeforces Round #647 (Div. 2) Codeforces Round #647 (Div. 2) - Thanks, Algo Muse!
codeforces-1362-A. Johnny and Ancient Computer
题意：
给你两个数a,b问是否可以通过*2 *4 *8 /2 /4 /8 把a变成b
思路：
因为是*2 *4 *8 /2 /4 /8 乘和除一起组合是没必要的，所以就是a大的话，通过除变成b，a小的话只能通过乘变成b
以乘为例，*4就等于乘了2个2，*8就相当于乘了3个2，所以YES的前提是大的要能被小的整除且除完的数是2的幂次
得到这个幂次之后优先分配给8 其次是4 2 计算总数就可以了
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define lowbit(a) ((a)&-(a))
#define clean(a,b) memset(a,b,sizeof(a))
const int mod = 1e9 + 7;
const int inf=0x3f3f3f3f;
const int maxn = 2e5+9;
int _;
//========================================================================
int main()
{
int n;
scanf("%d",&n);
while(n--)
{
ll a,b,cnt=0,flag=0,now;
scanf("%lld%lld",&a,&b);
if(a%2&&a>b||b%2&&b>a)
{
puts("-1");
continue;
}
if(a>=b)
{
ll c=a/b;
if(a%b==0)
{
cnt=0,now;
for(int i=0;i<=63;i++)
{
if(((c>>i)&1)==1) cnt++,now=i;
}
}
if(a%b!=0||cnt>=2) flag=1;
}
else
{
ll c=b/a;
if(b%a==0)
{
cnt=0,now;
for(int i=0;i<=63;i++)
{
if(((c>>i)&1)==1) cnt++,now=i;
}
}
if(b%a!=0||cnt>=2) flag=1;
}
if(flag) puts("-1");
else
{
int ans=0;
ans+=now/3;
now%=3;
ans+=now/2;
now%=2;
ans+=now;
printf("%d
",ans);
}
}
return 0;
}
codeforces-1362-B. Johnny and His Hobbies
题意：
给你一个集合，问是是否有一个数，与这个集合异或后形成的新集合相等
思路：
是不是一直在找异或前后的关系，是不是没有找到什么规律，找到了也写的乱七八糟
对，别写了，这题暴力，这个数最大的可能是1024，就枚举这1024个数就行了，惊不惊喜意不意外，我也挺意外的
也不知道之前咋算的一直觉得暴力是1e9的复杂度
很久很久了才看到 “It is guaranteed that the sum of n over all test cases will not exceed 1024.”
然后也没反应过来是排个序直接看是不是相等，太憨了，好好的cf打的稀巴烂，心态崩了还打个p了
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define lowbit(a) ((a)&-(a))
#define clean(a,b) memset(a,b,sizeof(a))
const int mod = 1e9 + 7;
const int inf=0x3f3f3f3f;
const int maxn = 2e5+9;
int _;
//========================================================================
int a[1500],b[1500];
int main()
{
for(scanf("%d",&_);_;_--)
{
int n;
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
}
sort(a+1,a+1+n);
int flag=0;
for(int i=1;i<=1024;i++)
{
for(int j=1;j<=n;j++)
{
b[j]=a[j]^i;
}
sort(b+1,b+1+n);
int cnt=0;
for(int j=1;j<=n;j++)
{
if(a[j]==b[j]) cnt++;
}
if(cnt==n)
{
flag=i;
break;
}
}
if(flag==0)
{
puts("-1");
}
else
{
printf("%d
",flag);
}
}
return 0;
}
codeforces-1362-C. Johnny and Another Rating Drop
题意：
给你一个数字(n)，现在把(0)~(n)全部化成二进制，相邻之间的位数不同的相加后得到的数是多少
思路：
感觉是好写的
一看就是有规律啊，打个表就明白了
1 1
2 3
3 4
4 7
5 8
6 10
7 11
8 15
9 16
10 18
11 19
12 22
13 23
14 25
15 26
16 31
17 32
18 34
19 35
20 38
21 39
22 41
23 42
24 46
25 47
26 49
27 50
28 53
29 54
30 56
31 57
32 63
33 64
他与前一项的差是 1 ((2^{0})) | 2((2^{1})) | 1 3((2^{2})) | 1 2 1 4((2^{3})) | 1 2 1 3 1 2 1 5((2^{4})) | 1 2 1 3 1 2 1 4 1 2 1 3 1 2 1 6((2^{5}))
然后我们发现，每一段以(k)为结尾的那一整段的和是(2^{k-1}) ，且(k)这个数都是数列的第(2^{k-1})项，包括(k)在内的从(1)~(k)的和是(2^{k}-1，)所以预处理出一个(2)的幂次的序列，每次二分查找要求的(n)在哪段，然后算这段的答案，再从(n)里把这段长度剪掉，循环的处理，直到长度为(0)
我看有的大佬找到规律是 ans[x]=x+ans[x/2]，递归处理，妙！
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define lowbit(a) ((a)&-(a))
#define clean(a,b) memset(a,b,sizeof(a))
const int mod = 1e9 + 7;
const int inf=0x3f3f3f3f;
const int maxn = 2e5+9;
int _;
//========================================================================
vector<ll>ve;
ll getid(ll x) { return upper_bound(ve.begin(), ve.end(), x) - ve.begin() ; }
int main()
{
for(int i=0;i<=63;i++)
{
ve.push_back((1ll<<i));
}
// for(int i=0;i<100;i++) printf("%d %lld
",i,ve[i]);
for(scanf("%d",&_);_;_--)
{
ll n,ans=0;
scanf("%lld",&n);
while(n)
{
ll k=getid(n);
ans+=(1ll<<(k))-1;
n-=(1ll<<(k-1));
}
printf("%lld
",ans);
}
return 0;
}
D没看懂
codeforces-1362-E. Johnny and Grandmaster
题意：
一个长度为n的序列k ， 将这些数分为两个集合A、B,使得两个集合差值的绝对值最小
思路：
这个题难就难在他的范围很大，平常的方法计算的时候是存不下的
正常的思路应该是：按从大到小排序，先往a里放一个，然后往b里放，直到超过a了再往a里放，这样才能保证差最小
但问题就是我们(k^{p_{i}})实在是太大了，没法判断是一个集合大于还是小于另一个集合，我也是在这里瞎写了一个然后wa4
其实再仔细审审题，(k^{p_{i}})不能给你就是为了把数扩大的呀，根据（类似于2进制吧）的规则，你从大到小排序之后，b集合的和想大于a集合，他首先要和a集合相等！！！！
对吧，我们只要判断是不是相等就行了，先往a里放，相等了就往b里放，然后继续往a里放……
只用他给的模数1e9+7误差就太大了，我们再多来几个模数对他取模，如果这些模数的结果都为0才是相等
我用的998244353还wa到了44……，这个就凭运气吧
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define lowbit(a) ((a)&-(a))
#define clean(a,b) memset(a,b,sizeof(a))
const int mod = 1e9 + 7;
const int inf=0x3f3f3f3f;
const int maxn = 1e6+9;
int _;
//========================================================================
ll a[maxn];
int cmp(ll a,ll b)
{
return a>b;
}
ll fpow(ll a,ll b,int c)
{
a%=c;
ll ans=1;
while(b)
{
if(b&1) ans=ans*a%c;
a=a*a%c;
b>>=1;
}
return ans%c;
}
//========================================================================
int main()
{
for(scanf("%d",&_);_;_--)
{
int n,p;
scanf("%d%d",&n,&p);
for(int i=1;i<=n;i++)
{
scanf("%lld",&a[i]);
}
sort(a+1,a+1+n,cmp);
ll sum=0,sum_=0;
int mod_=100001651;
int i=1;
while(i<=n)
{
if(sum_==0&&sum==0)
{
sum=(sum+fpow(p,a[i],mod))%mod;
sum_=(sum_+fpow(p,a[i],mod_))%mod_;
i++;
}
if(i>n) break;
sum=(sum-fpow(p,a[i],mod)+mod)%mod;
sum_=(sum_-fpow(p,a[i],mod_)+mod_)%mod_;
i++;
}
printf("%lld
",sum);
}
return 0;
}