文章目录
- 前言
- 1362-A. Johnny and Ancient Computer
- 1362-B - Johnny and His Hobbies
- 1362-C - Johnny and Another Rating Drop
- 1361-A Johnny and Contribution
- 1361-B - Johnny and Grandmaster
- 1361-C - Johnny and Megan's Necklace
- 1361-D - Johnny and James
前言
比昨天的题恶心亿点点
最后D题死活调不出来了整了两个半小时
qwq
1362-A. Johnny and Ancient Computer
给定 a,b，你可以把 aaa 的值设为以下几种之一：
a⋅2
a⋅4
a⋅8
a÷2（如果它被 2 整除）
a÷4（如果它被 4 整除）
a÷8（如果它被 8 整除）
求出至少需要几次操作才能把 a 变成 b。如果无解，输出 -1，表示这是不可能的。
多组数据，数据组数 t ≤ 1000 , 1 ≤ a , b ≤ 1 0 18 t\leq 1000 ,1 \leq a,b\leq 10^{18} t≤1000,1≤a,b≤1018
解析
大水题
判断整除、除完一的个数后暴力数需要移动几位即可
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define debug(...) fprintf(stderr,__VA_ARGS__)
const int N=2e5+100;
const int mod=998244353;
inline ll read(){
ll x(0),f(1);char c=getchar();
while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
while(isdigit(c)){x=(x<<1)+(x<<3)+c-'0';c=getchar();}
return x*f;
}
int n,m,q;
int calc(ll x){return x?calc(x>>1)+1:0;}
signed main(){
#ifndef ONLINE_JUDGE
freopen("a.in","r",stdin);
freopen("a.out","w",stdout);
#endif
int T=read();
while(T--){
ll a=read(),b=read();
if(a<b) swap(a,b);
if(a%b) printf("-1\n");
else{
ll o=a/b;
if(o!=(o&-o)) printf("-1\n");
else printf("%d\n",(calc(o)+1)/3);
}
}
return 0;
}
1362-B - Johnny and His Hobbies
有一个大小为 n 的集合 S = { s 1 , s 2 , . . . , s n } S=\{s_1,s_2,...,s_n\} S={s1,s2,...,sn}。你需要求出一个最小的正整数 k，使得 { s 1 ⊕ k , s 2 ⊕ k , . . . , s n ⊕ k } = S \{s_1 \oplus k,s_2 \oplus k,...,s_n \oplus k\}=S {s1⊕k,s2⊕k,...,sn⊕k}=S。
如果不存在这样的 k，输出 −1。
t ≤ 1024 , 1 ≤ n ≤ 1024 , ∑ n ≤ 1024 , 0 ≤ s i < 1024 t \leq 1024,1 \leq n \leq 1024,\sum n \leq 1024,0 \leq s_i < 1024 t≤1024,1≤n≤1024,∑n≤1024,0≤si<1024
解析
注意到数据范围很小，n方可以通过
暴力枚举
a
i
a_i
ai映射的值判断合法再取最小即可
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define debug(...) fprintf(stderr,__VA_ARGS__)
const int N=1050;
const int mod=998244353;
inline ll read(){
ll x(0),f(1);char c=getchar();
while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
while(isdigit(c)){x=(x<<1)+(x<<3)+c-'0';c=getchar();}
return x*f;
}
int n,m,q;
int a[N],bac[N];
signed main(){
#ifndef ONLINE_JUDGE
freopen("a.in","r",stdin);
freopen("a.out","w",stdout);
#endif
int T=read();
while(T--){
int res=1e9;
n=read();
memset(bac,0,sizeof(bac));
for(int i=1;i<=n;i++) a[i]=read(),bac[a[i]]=1;
for(int i=2;i<=n;i++){
int o=a[1]^a[i],flag=1;
for(int j=1;j<=n;j++){
if(bac[a[j]^o]==0){
flag=0;break;
}
}
if(flag) res=min(res,o);
}
printf("%d\n",res<1e9?res:-1);
}
return 0;
}
1362-C - Johnny and Another Rating Drop
定义两个数的差异为它们在二进制下不同的位的数量（我们认为它们补充了足够的前导零）。
例如，0101 和 1110 的差异为 3
你需要求出 0 , 1 , 2 , . . , n − 1 , n 0,1,2,..,n-1,n 0,1,2,..,n−1,n 中相邻的数的差异之和。
t ≤ 10000 t \leq 10000 t≤10000， 1 ≤ n ≤ 1 0 18 1 \leq n \leq 10^{18} 1≤n≤1018
解析
如果你没什么思路，给你看看他的样例：
n=5:
000
001
010
011
100
101
谜底写在谜面上
按位考虑即可
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define debug(...) fprintf(stderr,__VA_ARGS__)
const int N=1050;
const int mod=998244353;
inline ll read(){
ll x(0),f(1);char c=getchar();
while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
while(isdigit(c)){x=(x<<1)+(x<<3)+c-'0';c=getchar();}
return x*f;
}
int n,m,q;
ll mi[100];
signed main(){
#ifndef ONLINE_JUDGE
freopen("a.in","r",stdin);
freopen("a.out","w",stdout);
#endif
int T=read();
mi[0]=1;
for(int i=1;mi[i-1]<=1e18;i++) mi[i]=mi[i-1]<<1;
while(T--){
ll a=read(),res(0);
for(int i=0;mi[i]<=a;i++){
res+=(a+1+mi[i]-1)/mi[i]-1;
}
printf("%lld\n",res);
}
return 0;
}
1361-A Johnny and Contribution
给定 n 个点 m 条边的无向图。第 i 点被要求标上一个大小在 [1,n] 之间的正整数 t i t_i ti。
在实际标数的过程中，操作者会按照一个特定的顺序 p 1 , p 2 , . . . , p n p_1,p_2,...,p_n p1,p2,...,pn 来标数。
当给一个点 x 标数的时候，操作者会找到一个(最小的，在已经被标上数且与 x 相连的点中没有出现过的,)正整数 v，并把点 x 标上 v。
你需要求出 p 1 , p 2 , . . . , p n p_1,p_2,...,p_n p1,p2,...,pn，这样操作者标数之后，第 iii 个点会被标上 t i t_i ti。
1 ≤ n , m ≤ 5 ⋅ 1 0 5 , 1 ≤ t i ≤ n 1 \leq n,m \leq 5\cdot 10^5,1 \leq t_i \leq n 1≤n,m≤5⋅105,1≤ti≤n 无重边无自环
解析
直接从小到大考虑标记点，标记完把与它相连的打个标记即可
如果该点在自己的第k轮被打了标记或者之前打的标记次数少于k-1，就是无解
实现用时间戳标记，具体见代码
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define debug(...) fprintf(stderr,__VA_ARGS__)
const int N=5e5+100;
const int mod=998244353;
inline ll read(){
ll x(0),f(1);char c=getchar();
while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
while(isdigit(c)){x=(x<<1)+(x<<3)+c-'0';c=getchar();}
return x*f;
}
int n,m;
struct node{
int to,nxt;
}p[N<<1];
int fi[N],cnt;
inline void addline(int x,int y){
p[++cnt]=(node){y,fi[x]};fi[x]=cnt;
return;
}
vector<int>v[N];
int du[N],tim,tag[N];
int ans[N],tot;
signed main(){
#ifndef ONLINE_JUDGE
freopen("a.in","r",stdin);
freopen("a.out","w",stdout);
#endif
memset(fi,-1,sizeof(fi));
n=read();m=read();
for(int i=1;i<=m;i++){
int x=read(),y=read();
addline(x,y);addline(y,x);
}
for(int i=1;i<=n;i++){
v[read()].push_back(i);
}
for(tim=1;tim<=n;tim++){
for(int i=0,o=v[tim].size();i<o;i++){
int x=v[tim][i];
if(tag[x]==tim||du[x]<tim-1){
printf("-1\n");return 0;
}
ans[++tot]=x;
for(int i=fi[x];~i;i=p[i].nxt){
int to=p[i].to;
if(tag[to]!=tim){
tag[to]=tim;du[to]++;
}
}
}
}
for(int i=1;i<=tot;i++) printf("%d ",ans[i]);
return 0;
}
1361-B - Johnny and Grandmaster
给定 n,p 和 n 个形如 p k i p^{k_i} pki的整数，要求将这 n 个数分为两个集合，最小化两个集合的各自的和的差的绝对值，答案对 1 0 9 + 7 10^9+7 109+7 取模。
∑ n ≤ 1 0 6 , 1 ≤ p ≤ 1 0 6 , 0 ≤ k i ≤ 1 0 6 \sum n\le 10^6,1\le p\le 10^6,0\le k_i\le 10^6 ∑n≤106,1≤p≤106,0≤ki≤106
解析
不太难但挺有意思的贪心题
贪心策略：
从高到低位取，每次都尽可能最小化当前的差值
证明：
假设当前在第k位，没有最小化当前的差值
那么当前差值会增大
2
∗
p
k
2*p^k
2∗pk
设[0,k-1]位的和为
s
u
m
sum
sum
- 若 s u m ≥ 2 ∗ p k sum\geq 2*p^k sum≥2∗pk，那么显然后面需要把这个差值先补上来，那么我们不如不要这个差值，让补上来的两个 p k p^k pk互相抵消，这样是不劣的
- 若 s u m ≤ 2 ∗ p k sum\leq 2*p^k sum≤2∗pk，那么答案就会至少是 p k − 1 p^{k-1} pk−1，但是不难看出，如果不要这个差值，不难发现答案不会超过 p k − 1 p^{k-1} pk−1，所以是不优秀的
比较感性，但凑和看吧
后面的实现就不是很难了主要你别和我一样伞兵换底公式倒错就行
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define debug(...) fprintf(stderr,__VA_ARGS__)
const int N=2e6+100;
const int mod=1e9+7;
inline ll read(){
ll x(0),f(1);char c=getchar();
while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
while(isdigit(c)){x=(x<<1)+(x<<3)+c-'0';c=getchar();}
return x*f;
}
int n,m;
ll p;
int tag[N],tim,num[N];
vector<int> v;
inline void add(int id){
if(tag[id]!=tim){
tag[id]=tim;v.push_back(id);num[id]=1;
}
else num[id]++;
return;
}
inline ll ksm(ll x,ll k){
ll res(1);
while(k){
if(k&1) res=res*x%mod;
x=x*x%mod;
k>>=1;
}
return res;
}
ll calc(int k){
ll res(0);
for(int i=k;i>=0;i--) (res+=num[v[i]]*ksm(p,v[i]))%=mod;
return res;
}
signed main(){
#ifndef ONLINE_JUDGE
freopen("a.in","r",stdin);
freopen("a.out","w",stdout);
#endif
int T=read();
for(tim=1;tim<=T;tim++){
v.clear();v.shrink_to_fit();
n=read();p=read();
for(int i=1;i<=n;i++){
int o=read();
add(o);
}
sort(v.begin(),v.end());
ll cnt(0);
int flag(0);
for(int i=v.size()-1;i>=0;i--){
int x=v[i];
if(num[x]>=cnt){
num[x]-=cnt;cnt=num[x]&1;
}
else cnt-=num[x];
if(i>0&&cnt){
int d=v[i]-v[i-1];
if(1.0*(log(n)-log(cnt))/log(p)<d){
flag=1;
printf("%lld\n",(cnt%mod*ksm(p,x)-calc(i-1)+mod)%mod);
break;
}
else cnt*=ksm(p,d);
}
}
if(!flag)
printf("%lld\n",cnt%mod*ksm(p,v[0])%mod);
}
return 0;
}
1361-C - Johnny and Megan’s Necklace
n 对珍珠由 n 条线所连起来，共 2n 颗。现在你可以在任意两个未被线连起来的珍珠之间连一条线，共可连 n 条，使得这 2n 颗珍珠形成一个环。
设一条线所连的两颗珍珠权值为 u,v，则该线的权值为最大的整数 k 满足 2 k ∣ u xor v 2^k∣u \operatorname{xor} v 2k∣uxorv 。如果 u=v，则 k=20。
求所有新连的线的权值最小值的最大值并给出方案，即 2n 颗珍珠所形成的的环。
解析
关于最值，不难想到二分答案
对于一个给定的答案k,两颗珍珠可以连接当且仅当二者的[0,k-1]位完全相同
考虑把每一个长度为k的后缀建一个点，每颗珍珠向自己的伴侣和自己的后缀连一条边
然后跑欧拉回路即可
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define debug(...) fprintf(stderr,__VA_ARGS__)
const int N=3e6+100;
const int mod=1e9+7;
inline ll read(){
ll x(0),f(1);char c=getchar();
while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
while(isdigit(c)){x=(x<<1)+(x<<3)+c-'0';c=getchar();}
return x*f;
}
int n,m;
struct node{
int to,nxt;
}p[N<<1];
int fi[N],cnt;
inline void addline(int x,int y){
//printf(" addline:%d->%d\n",x,y);
p[++cnt]=(node){y,fi[x]};fi[x]=cnt;
return;
}
int a[N],b[N];
int zhan[N],top;
bool jd[N];
int du[N];
void dfs(int x){
//printf("dfs:%d\n",x);
for(int i=fi[x];~i;i=fi[x]){
int to=p[i].to;
fi[x]=p[i].nxt;
jd[i^1]=1;
if(!jd[i]){
//printf("%d->%d\n",x,to);
dfs(to);
}
}
zhan[++top]=x;
}
bool check(int k){
int s=(1<<k)-1;
memset(fi,-1,sizeof(fi));cnt=-1;
memset(jd,0,sizeof(jd));
memset(du,0,sizeof(du));
for(int i=1;i<=n;i++){
addline(2*i-1,2*i);addline(2*i,2*i-1);
}
int mx(0);
for(int i=1;i<=n;i++){
int x=a[i]&s,y=b[i]&s;
++x;++y;
//printf("\ni=%d x=%d y=%d\n",i,x,y);
addline(2*i-1,2*n+x);addline(2*n+x,2*i-1);
addline(2*i,2*n+y);addline(2*n+y,2*i);
du[2*n+x]++;du[2*n+y]++;
mx=max(mx,max(x,y));
}
for(int i=1;i<=mx;i++){
if(du[i+2*n]&1) return false;
}
top=0;
dfs(1);
return top==3*n+1;
}
int main(){
#ifndef ONLINE_JUDGE
freopen("a.in","r",stdin);
freopen("a.out","w",stdout);
#endif
n=read();
for(int i=1;i<=n;i++){
a[i]=read();b[i]=read();
}
//printf("%d\n",check(3));
//while(top) printf("%d ",zhan[top--]);
//return 0;
int st=0,ed=20;
while(st<ed){
int mid=(st+ed+1)>>1;
if(check(mid)) st=mid;
else ed=mid-1;
}
check(st);
printf("%d\n",st);--top;
while(top){
if(zhan[top]<=2*n) printf("%d ",zhan[top]);
--top;
}
return 0;
}
1361-D - Johnny and James
平面上给定 n 个互不相同的点，其中一个点是原点
建一棵树，原点为根，一个不为原点的点的父亲为其到原点的线段上的第二个点，边长即为到父亲的欧几里得距离
求选出 k 个不同的点，这些点两两距离和最大值
2 ≤ k ≤ n ≤ 5 × 1 0 5 2 \le k \le n \le 5 \times 10^5 2≤k≤n≤5×105
解析
大毒瘤题…
是好几种方法都假掉了，又写了一堆bug
qwq
思路也不太好想
如果我们知道一条链上取的点的个数，我们应该取那些点呢？
对于前k/2个，由于链外的点更多，我们应该从下往上取，而对于超过k/2个，由于下方的点更多，我们应该从上往下取
所以我们可以分开来考虑增量
（设 x 到根的距离为
d
i
s
x
dis_x
disx ）
对于从下往上取的前k/2个：设其为从下往上第 i 个，那么它会往根连接
k
−
i
k-i
k−i 条边，产生
(
k
−
i
)
×
d
i
s
i
(k-i) \times dis_i
(k−i)×disi 的贡献；同时，由于下方的所有点计算到i的路径时，本来是连向根的，现在变成连向 i ，因此又将付出
(
i
−
1
)
×
d
i
s
i
(i-1) \times dis_i
(i−1)×disi的代价。总的价值就是
(
k
−
i
−
(
i
−
1
)
)
×
d
i
s
i
(k-i -(i-1)) \times dis_i
(k−i−(i−1))×disi
对于从上往下取的前k/2个：设其为从上往下第 i 个，那么它会往根连 k − k / 2 − ( i − 1 ) k-k/2-(i-1) k−k/2−(i−1)条边（k/2是第一种情况的点），产生 ( k − i ) × d i s i (k-i) \times dis_i (k−i)×disi的贡献；对于下方的点，和第一种情况类似的，也要付出 ( k / 2 ) × d i s i (k/2) \times dis_i (k/2)×disi；同时，它的祖先们往i连边本来是当成向根连边计算的，但现在变成了连向 i 变化值是 ∑ u ∈ a n c e s t o r i d i s i − d i s u − d i s u \sum_{u\in ancestor_i}dis_i-dis_u-dis_u ∑u∈ancestoridisi−disu−disu。因此，总的价值就是： ( k − k / 2 − k / 2 + i − 1 ) × d i s i (k-k/2-k/2+i-1) \times dis_i (k−k/2−k/2+i−1)×disi
算出选取每个点的贡献，sort一下后取前k个即可
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define debug(...) fprintf(stderr,__VA_ARGS__)
const int N=5e5+100;
const int mod=1e9+7;
const double eps=1e-9;
inline ll read(){
ll x(0),f(1);char c=getchar();
while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
while(isdigit(c)){x=(x<<1)+(x<<3)+c-'0';c=getchar();}
return x*f;
}
ll gcd(ll x,ll y){ return y?gcd(y,x%y):x;}
int n,m;
int rt;
map<int,map<int,int>>mp;
int bel[N],tot;
vector<int> v[N];
ll x[N],y[N];
double dep[N];
struct node{
int to,nxt;
double w;
}p[N<<1];
int fi[N],cnt;
inline void addline(int x,int y,double w){
p[++cnt]=(node){y,fi[x],w};
fi[x]=cnt;return;
}
bool cmp(int x,int y){return dep[x]>dep[y];}
bool vis[N];
double q[N];
int num;
int main(){
#ifndef ONLINE_JUDGE
freopen("a.in","r",stdin);
freopen("a.out","w",stdout);
#endif
memset(fi,-1,sizeof(fi));cnt=-1;
n=read();m=read();
for(int i=1;i<=n;i++){
x[i]=read();y[i]=read();
if(!x[i]&&!y[i]){
rt=i;continue;
}
dep[i]=sqrt(x[i]*x[i]+y[i]*y[i]);
int g=gcd(abs(x[i]),abs(y[i])),a=abs(x[i])/g,b=abs(y[i])/g;
if(x[i]<0){
//printf("ok a=%d\n",a);
a=-a;
}
if(y[i]<0) b=-b;
if(!x[i]) a=0,b=y[i]>0?1:-1;
if(!y[i]) b=0,a=x[i]>0?1:-1;
if(!mp[a][b]) mp[a][b]=++tot;
int o=mp[a][b];
bel[i]=o;v[o].push_back(i);
//printf("i=%d bel=%d dep=%lf g=%d a=%d b=%d x[i]=%lld y[i]=%lld\n",i,bel[i],dep[i],g,a,b,x[i],y[i]);
}
v[++tot].push_back(rt);num=0;
for(int o=1;o<=tot;o++){
//printf("o=%d\n\n",o);
int ww=v[o].size();
sort(v[o].begin(),v[o].end(),cmp);
for(int i=0;i<min(ww,m/2);i++){
int x=v[o][i];
q[++num]=(m-2*i-1)*dep[x];
//printf("down:x=%d dep=%lf add=%lf\n",x,dep[x],(m-2*i-1)*dep[x]);
}
double sum(0);
for(int i=ww-1;i>=m/2;i--){
int x=v[o][i];
q[++num]=(m-2*(m/2)-1)*dep[x]-2*sum;
//printf("up:x=%d dep=%lf add=%lf\n",x,dep[x],(m-2*(m/2)-1)*dep[x]-2*sum);
sum+=dep[x];
}
}
double ans(0);
sort(q+1,q+1+num);
//for(int i=1;i<=num;i++) printf("%lf\n",q[i]);
for(int i=num;m;i--,m--) ans+=q[i];
printf("%.8lf\n",ans);
return 0;
}