CodeForces - 1368
A - C+=
直接模拟
ll t
,a
,b
,n
;
int main()
{
scanf("%lld",&t
);
while(t
--)
{
int num
=0;
scanf("%lld%lld%lld",&a
,&b
,&n
);
while(a
<=n
&&b
<=n
)
{
ll minn
=min(a
,b
);
ll maxx
=max(a
,b
);
a
=minn
+maxx
;
b
=maxx
;
num
++;
}
W(num
);
}
return 0;
}
B - Codeforces Subsequences
一共10个字母，假设他们的个数分别为
a
0
,
a
1
.
.
.
a_0,a_1...
a0,a1... 则
k
=
a
0
a
1
.
.
.
a
9
k=a_0a_1...a_9
k=a0a1...a9 可以证明 个数越平均越好 直接枚举
int ans
[10];
ll k
;
ll
qpow(ll a
,ll b
){ll res
=1;while(b
){if (b
&1)res
*=a
;a
*=a
;b
>>=1;}return res
;}
int main()
{
scanf("%lld",&k
);
for (ll j
=1;j
<=100;j
++)
{
for (ll i
=10;i
>=0;i
--)
{
if (qpow(j
,i
)*qpow(j
+1,10-i
)>=k
)
{
rep(q
,0,i
-1)ans
[q
]=j
;
rep(q
,i
,9)ans
[q
]=j
+1;
rep(i
,1,ans
[0])printf("%c",'c');
rep(i
,1,ans
[1])printf("%c",'o');
rep(i
,1,ans
[2])printf("%c",'d');
rep(i
,1,ans
[3])printf("%c",'e');
rep(i
,1,ans
[4])printf("%c",'f');
rep(i
,1,ans
[5])printf("%c",'o');
rep(i
,1,ans
[6])printf("%c",'r');
rep(i
,1,ans
[7])printf("%c",'c');
rep(i
,1,ans
[8])printf("%c",'e');
rep(i
,1,ans
[9])printf("%c",'s');puts("");
return 0;
}
}
}
}
C - Even Picture
构造方法：用正方形去覆盖
例如n
=3
1 1
1 1 1
1 1 1
1 1 1
1 1
int n
;
int main()
{
scanf("%d",&n
);
W(4+3*n
);
rep(i
,0,n
+1)printf("%d %d\n",i
,i
);
rep(i
,0,n
)printf("%d %d\n",i
,i
+1);
rep(i
,0,n
)printf("%d %d\n",i
+1,i
);
return 0;
}
D - AND, OR and square sum
先观察几组例子：
4：
0100
9：
1001
操作之后得到：
0：
0000
13：
1101
3：
0011
5：
0101
操作之后得到
1：
0001
7：
0111
可以发现，操作相当于只是交换了某些位，但和是不变的，即x
+y
=K(定值
)
在坐标系中做图可以证明x
^2+y
^2在x
=y时取得最小，在x
=K或y
=K时取得最大值
因此贪心策略是尽量构造极端数字
先记录下位的位置为
1的数量，然后去构造“极端的数”，构造n个这样的数即可
int n
;
ll a
[maxn
],num
[30],ans
=0;
int main()
{
scanf("%d",&n
);
rep(i
,1,n
)
{
scanf("%lld",&a
[i
]);
rep(j
,0,20)if (a
[i
]&(1<<j
))num
[j
]++;
}
rep(i
,1,n
)
{
ll sum
=0;
for (int j
=20;j
>=0;j
--)
{
if (num
[j
])
{
num
[j
]--;
sum
+=(1<<j
);
}
}
ans
+=sum
*sum
;
}
WW(ans
);
return 0;
}
