记录一下在各个平台的刷题记录,以便总结

没有问题的但是是好题仍会放上去,太水了的就算了…

CodeForce 1328

A. Divisibility Problem

可以直接算出来

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include <iostream>

using namespace std;

int main(){
int t; cin >> t;
while(t--){
int a, b; cin >> a >> b;
int sum = 0;
if(a > b){
sum = (((a - a % b) / b) + 1) * b - a;
}
if(a < b) sum = b - a;
cout << sum << '\n';
}
return 0;
}

B. K-th Beautiful String

For the given integer n (n>2) let’s write down all the strings of length nn which contain n−2 letters ‘a’ and two letters ‘b’ in lexicographical (alphabetical) order.

首先理解题意,在n-2个a中和2个b的按字典序的全排列输出第kk个字符串,可以反过来分析b.先算出数组的前缀和,随后通过lower_bound求出下标,即可得到第一个b的pos,第二个b与k和前缀和的值有关.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#include <iostream>

typedef long long int ll;
using namespace std;
ll di[100005];

int main()
{
di[1] = 1;
for (int i = 2; i <= 100000; i++) di[i] = di[i - 1] + i;
int t; cin >> t;
while (t--)
{
ll n, k;
cin >> n >> k;
int x = lower_bound(di + 1, di + 100000, k) - di;
int pos1 = n - x;
int pos2 = n - (k - di[x - 1] - 1);
for (int i = 1; i <= n; i++)
{
if (i != pos1 && i != pos2) cout << "a";
else cout << "b";
}
cout << endl;
}
return 0;
}

C. Ternary XOR

Your task is to find such ternary numbers a and b both of length n and both without leading zeros that a⊙b=x and max(a,b) is the minimum possible.

如果遇到’1’了的话,势必有一个为0有一个为1,若字符串a为1,则字符串b永远小于a,所以我们只需要保证a后面的位数最小即可.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include<bits/stdc++.h>
#include <string>
using namespace std;

int main() {
int t; cin >> t;
while (t--) {
int n; cin >> n;
int flag = 1;
string num, a, b; cin >> num;
a = num, b = num;
for (int i = 0; i < n; i++) {
if (flag){
if (num[i] == '2') {
a[i] = '1', b[i] = '1';
}
else if (num[i] == '1') {
a[i] = '1', b[i] = '0';
flag = 0;
}
else {
a[i] = '0', b[i] = '0';
}
}
else{
a[i] = '0', b[i] = num[i];
}
}
cout << a << '\n' << b << '\n';
}
return 0;
}

D. Carousel

E. Tree Queries

F. Make k Equal

abc160

Find the minimum distance that needs to be traveled when you start at one of the houses and visit all the N houses.

找两点距离最大的弧减去周长即可,为啥就想不出来呢??😭

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include <iostream>
#include <algorithm>

using namespace std;

int main() {
int k, n; cin >> k >> n;
int a[200010];
int ans = 0, maxd = 0;
for (int i = 1; i <= n; i++)
cin >> a[i];
sort(a, a + n);
for (int i = 2; i <= n; i++){
maxd = max(maxd, a[i] - a[i - 1]);
}
cout << min(k - maxd, k - (k - a[n] + a[1]));
return 0;
}

panasonic2020

考虑范围和精度,特别考虑取最小的值, 最大的值, -1, 0, 1

1
2
3
4
5
6
7
8
9
10
11
12
13
#include <iostream>

using namespace std;

int main(){
long long int h, w; cin >> h >> w;
if (h == 1 || w == 1) {
cout << 1;
}else{
cout << (h * w + 1) / 2;
}
return 0;
}

注意浮点是有误差的

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include <iostream>
#include <cmath>

using namespace std;
typedef long long ll;

int main(void){
ll a,b,c;
cin >> a >> b >> c;

ll d = c - a - b;
if(d > 0 && d * d > 4 * a * b){
cout << "Yes" << endl;
} else {
cout << "No" << endl;
}
return 0;
}

51node

你别说,leve-1有些题还真打脑阔…

给出一个数k,求最小的n,使得n的阶乘后面0的数量>=k。

给出公式,设 n=5k+r,0r<5n = 5k+r,0 \leqslant r <5

n!=(5k+r)(5k+r1)54!=(5k)(5k1)(5)m=5k×k!×m\begin{aligned} n !&=(5 k+r)(5 k+r-1)\cdots5\cdots4! \\ &=(5k)(5k-1)(5)\cdot m \\ &=5^{k}\times k! \times m \end{aligned}

其中mm为不含55的因子式,那么k=n/5k = n/5,所以得到

f(n!)=k+f(n!)k=n/5f(n!) = k + f(n!) \quad k = n/5

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#include <iostream>
#include <algorithm>
#include <math.h>
using namespace std;
typedef long long int ll;
ll k;
bool check(ll n) {
ll ans = 0;
while (n) {
n = n / 5;
ans += n;
}
return ans >= k;
}
int main() {
cin >> k;
ll l = 1, r = 5 * k;
ll mid;
while (l < r) {
mid = (l + r) / 2;
if (check(mid))
r = mid;
else
l = mid + 1;
}
cout << l;
return 0;
}

有N条鱼每条鱼的位置及大小均不同,他们沿着X轴游动,有的向左,有的向右。游动的速度是一样的,两条鱼相遇大鱼会吃掉小鱼。从左到右给出每条鱼的大小和游动的方向(0表示向左,1表示向右)。问足够长的时间之后,能剩下多少条鱼?

采用栈处理,当不为空的时候,循环检查是否被吃掉

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include<iostream>
#include <stack>

using namespace std;

const int maxn = 1e6 + 10;

struct fish {
int size, dic;
}f;

int main() {
int n; cin >> n;
stack<fish> sf;
int sum = n;
while (n--){
cin >> f.size >> f.dic;
if (f.dic) sf.push(f);
else {
while (!sf.empty()){
if (f.size > sf.top().size){
sum--;
sf.pop();
}
else{
sum--;
break;
}
}
}
}
cout << sum << endl;
}

定义旋转函数Left(S)=S[1…n-1]+S[0].比如S=”abcd”,Left(S)=”bcda”.一个串是对串当且仅当这个串长度为偶数,前半段和后半段一样。比如”abcabc”是对串,”aabbcc”则不是。现在问题是给定一个字符串,判断他是否可以由一个对串旋转任意次得到.

一个对串旋转后还是对串

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <iostream>
using namespace std;
int main(){
string n; cin >> n;
if (n.size() % 2 != 0) {
cout << "NO";
return 0;
}
else{
for (int i = 0; i < (n.size() / 2); i++){
if(n[i] != n[i + n.size() / 2]){
cout << "NO";
return 0;
}
}
}
cout << "YES";
return 0;

}

一个十进制整数被叫做权势二进制,当他的十进制表示的时候只由0或1组成。例如0,1,101,110011都是权势二进制而2,12,900不是。当给定一个n的时候,计算一下最少要多少个权势二进制相加才能得到n。

看每一位最大是多少,因为权势二进制都是由1和0构成的,假如某一位是9,那么要9个1,所以找到最大那一位即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <iostream>
using namespace std;
int main(){
int n, ans = 0;
cin >> n;
while(n){
ans = max(ans, n % 10);
n /= 10;
}
cout << ans;
}

给定 x 轴上 N(0<N<100)条线段 [ai,bi] i=1,2,……N,端点坐标都是区间(-999,999)内的整数。
请你编写一个程序,从给出的线段中去掉尽量少的线段,使得剩下的线段两两之间没有内部公共点。

选择不相交区间问题,坑的是他没说端点顺序…记一手读题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#include <iostream>
#include <algorithm>
#include <cstdio>
using namespace std;
typedef long long int ll;
const int maxn = 1e2 + 10;
int n;

struct block {
int x, y;
}b[maxn];

bool cmp(block l, block r) {
return l.y < r.y;
}

int main() {
cin >> n;
for (int i = 1; i <= n; i++){
int x, y; cin >> x >> y;
b[i].x = min(x, y);
b[i].y = max(x, y);
}
sort(b + 1, b + n + 1, cmp);
int pos = -1000, ans = 0;

for (int i = 1; i <= n; i++) {
if (pos <= b[i].x) {
pos = b[i].y;
ans++;
}
}
cout << ans;
return 0;
}

现在有N(1 <= N <= 1000)条绳子,
他们的长度分别为L1,L2,……,Ln(1 <= Li <= 10000),如果从他们中切割出K(1 <= K <= 1000)条长度相同的绳子,这K条绳子每条最长能多长?四舍五入保留小数点后两位

是二分答案的类型,但是数据是浮点型,真的烦啊.不过可以把数据乘一千倍,以为保留两位小数,即算到第三位,所以我们乘10^3,接下里就可以按照正常的整形去算了. 妙啊!

但是最后输出的时候也要注意精度,方法为把最后一位加上5,随后取整,这时已经进位了,然后转为浮点数即可

另一个方法为一位小数 + 0.005, 两位 + 0.0005…以此类推

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#include <iostream>

using namespace std;
const int maxn = 1e4 + 10;
const double hight = 1e5 + 0.001;
typedef long long int ll;

int n, m;
ll a[maxn];

bool check(double mid) {
ll sum = 0;
for (int i = 1; i <= n; i++) {
ll tmp = a[i];
while (tmp - mid > 0) {
sum++;
tmp -= mid;
}
}
return sum >= m;

}
int main() {
cin >> n >> m;
for (int i = 1; i <= n; i++){
double tmp; cin >> tmp;
tmp = tmp * 1000;
a[i] = (ll)tmp;
}
ll l = 0, r = hight, mid;
while (l + 1 < r) {
mid = (l + r) / 2;
if (check(mid))
l = mid;
else
r = mid;
}
printf("%.2lf", (r + 5) / 10 / 100.0);
return 0;
}

小b有一个01序列,她每次可以翻转一个元素,即将该元素从0变1或者从1变0。现在她希望序列不降,求最少翻转次数。

因为字符串总是00…111的形式所以分别计算 $1\sim x $ 全部置0和 $ x \sim n$全部置1的代价,维护最小值就可以了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <iostream>

using namespace std;

const int maxn = 200010;

int main(){
char num[maxn]; int n; cin >> n;
for (int i = 1;i <= n; i++)
cin >> num[i];
int ans = 0x3f3f3f3f;
for (int i = 1; i <= n; i++){
int sum1 = 0, sum0 = 0, sum;
for (int j = 1; j < i; j++)
if (num[j] == '1') sum1++;
for (int k = i + 1; k <= n; k++)
if (num[k] == '0') sum0++;
ans = min(ans, sum1 + sum0);
}
cout << ans;
return 0;
}

小b有n个关闭的灯泡,编号为1…n。小b会进行n轮操作,第i轮她会将编号为i的倍数的灯泡的开关状态取反,即开变成关,关变成开。求n轮操作后,有多少灯泡是亮着的。

理解题意, 求1-n有多少个奇数因子数,但只有完全平方数的因子数为奇数,求有多少个完全平方数即可(如果自己能想出来智商必120+)

1
2
3
4
5
6
7
8
9
#include <bits/stdc++.h>

using namespace std;

int main(){
int n; cin >> n;
cout << (int)sqrt(n) << endl;
return 0;
}

luogu

可以选择一段连续区间[L,R],填充这段区间中的每块区域,让其下陷深度减少1可以在最短的时间内将整段道路的下陷深度都变为 0.

例题: https://www.luogu.com.cn/problem/P5019

策略很关键!

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include<iostream>
#include <stack>

using namespace std;

const int maxn = 1e6 + 10;

int a[maxn];

int main(){
int n; cin >> n;
int sum = 0;
for (int i = 1; i <= n; i++) cin >> a[i];
for (int i = 2; i <= n; i++) if(a[i] > a[i - 1]) sum += a[i] - a[i - 1];
cout << sum + a[1];
return 0;
}

找出所有分组方案中分组数最少的一种,输出最少的分组数目。

例题: https://www.luogu.com.cn/problem/P1094

简单贪心,练一下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include<iostream>
#include <algorithm>

using namespace std;
const int maxn = 1e6 + 10;
int a[maxn];
int main(){
int w, n; cin >> w >> n;
for (int i = 1; i <= n; i++) cin >> a[i];
sort(a + 1, a + n + 1);
int l = 1, r = n, ans = 0;
while(l <= r){
if (a[l] + a[r] <= w){
l++, r--;
ans++;
}else{
r--;
ans++;
}
}
cout << ans;
return 0;
}

为了给小 F 展现你超级跳的本领,你决定跳到每个石头上各一次,并最终停在任意一块石头上,并且小跳蛙想耗费尽可能多的体力值

没错我就是来刷贪心的.ans要long long ,不然wa了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include<iostream>
#include <algorithm>

using namespace std;

const int maxn = 1e3 + 10;

int a[maxn];

int main(){
int n; cin >> n;
for (int i = 1; i <= n; i++) cin >> a[i];
sort(a + 1, a + n + 1); a[0] = 0;
int l = 0, r = n;
long long int ans = 0, result = 0;
while(l < r){
result = a[r] - a[l]; l++;
ans += result * result;
result = a[l] - a[r]; r--;
ans += result * result;
}
cout << ans;
}

每一次合并,多多可以把两堆果子合并到一起,消耗的体力等于两堆果子的重量之和。可以看出,所有的果子经过 n-1n−1 次合并之后, 就只剩下一堆了。多多在合并果子时总共消耗的体力等于每次合并所耗体力之和

有一说一这道题挺好的

采用冒泡排序而不是sort(a + i)是因为冒泡可以减少一些比较的次数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#include<iostream>
#include <algorithm>

using namespace std;

const int maxn = 1e4 + 10;

int a[maxn];

int main(){
int n; cin >> n;
for (int i = 1; i <= n; i++) cin >> a[i];
sort(a + 1, a + n + 1);
int ans = 0;
for (int i = 2; i <= n; i++){
ans += a[i] + a[i - 1];
a[i] += a[i - 1];
for (int j = i ; j <= n - 1; j++){
if (a[j] > a[j + 1])
swap(a[j], a[j + 1]);
else
break;
}
}
cout << ans;
return 0;

}

hdu

pid:6312

我们假设a先手,b后手.我们考虑 2-n的数, 因为取除1的任何一个数,都会变成2-n取数的问题

所以考虑2-n时, 存在某种策略使得先手胜利,则a胜利.若先手失败,则为后手胜利,另外意思是2-n已经为一个比败局,那么a取1即可把2-n的必败局转移给b,那么a胜利.

所以综上 先手的a胜利

评论