书脊 | 这青苔碧瓦堆, 俺曾睡风流觉, 将五十年兴亡看饱.

Codeforces Round #725 (Div. 3)F. Interesting Function

给两个数字l和r, 求从l加到r中间digit的变化个数是多少.

这题用的方法和D一样,就是先求R的答案, 然后减去L的答案, 具体的求法是通过观察: 比如21这个数, 从1->9 是9个1位改变, 9->10是1个2位, 10->19是9个1位改变, 19->20是2个1位改变. 20->21 是1个1位改变, 所以加起来就是21+2, 有次可推,数字123是123+12+1.

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);  
    int t;
    cin >> t;
    while (t --)
    {
        int l,r;
        cin >> l >> r;
        auto count = [&](int n) -> int64_t {
            int base = 10;
            int digit = 1;
            int64_t res = 0;
            while (n)
            {
                res += n; 
                n /= base; 
            }            
            return res;
        };
        cout << count(r) - count(l) << endl;
    } 
    return 0;
}

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

#include <iostream>

#include <algorithm>

#include <vector>

using namespace std;

int main() {

ios::sync_with_stdio(0);

cin.tie(0),cout.tie(0);

int t;

cin >> t;

while (t --)

{

int l,r;

cin >> l >> r;

auto count = [&](int n) -> int64_t {

int base = 10;

int digit = 1;

int64_t res = 0;

while (n)

{

res += n;

n /= base;

}

return res;

};

cout << count(r) - count(l) << endl;

}

return 0;

}

Date June 11, 2021
Category Codeforces
Comments No Comments

Codeforces Round #725 (Div. 3)D. Another Problem About Dividing Numbers

给三个数,a,b,k, 问a和b是不是能在k次(exactly) 下通过整除相等.

这个题情况比较多, 比如a和b互质, 比如k大于a和b. 反正就是交一次就对的都是大神.

这题思路是, 反正a和b一直和某数做整除, 最后就是1, 肯定相等啊, 所以只需要计算有多少质因子在a和b的和中.即可, 剩下就是各种corner cases.

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);  
    int t;
    cin >> t;
    while (t --)
    {
        auto gcd = [&](auto wtf, int a, int b) -> int {
        if(b == 0)
            return a;
        return wtf(wtf, b, a % b);
        }; 
        auto fac = [&](int n) -> int {
            int res = 0;
            for (size_t i = 2; i * i <= n; i++)
            {
                while (n % i == 0)
                {
                    res++;
                    n /= i;
                }
            }
            if (n > 1) // if n is a prime, but not 1
            {
                res++;
            }
            return res;
        };
        int a,b,k;
        cin >> a >> b >> k;
      //  cout << fac(a) << endl;
      //  cout << fac(b) << endl;
        if (k == 1)
        { 
            int g = gcd(gcd, a, b);
            if ((g == a || g == b) && a != b)
            {
                cout << "YES" << endl;
            }
            else
            {
                cout << "NO" << endl;
            }
        }
        else if (k > 1)
        {
            if (k > fac(a) + fac(b))
            {
                cout << "NO" << endl;
            }
            else
            {
                cout << "YES" << endl;
            }
        }
    } 
    
  
    
    return 0;
}

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

41

42

43

44

45

46

47

48

49

50

51

52

53

54

55

56

57

58

59

60

61

62

63

64

65

66

#include <iostream>

#include <algorithm>

#include <vector>

using namespace std;

int main() {

ios::sync_with_stdio(0);

cin.tie(0),cout.tie(0);

int t;

cin >> t;

while (t --)

{

auto gcd = [&](auto wtf, int a, int b) -> int {

if(b == 0)

return a;

return wtf(wtf, b, a % b);

};

auto fac = [&](int n) -> int {

int res = 0;

for (size_t i = 2; i * i <= n; i++)

{

while (n % i == 0)

{

res++;

n /= i;

}

if (n > 1) // if n is a prime, but not 1

{

res++;

}

return res;

};

int a,b,k;

cin >> a >> b >> k;

// cout << fac(a) << endl;

// cout << fac(b) << endl;

if (k == 1)

{

int g = gcd(gcd, a, b);

if ((g == a || g == b) && a != b)

{

cout << "YES" << endl;

}

else

{

cout << "NO" << endl;

}

else if (k > 1)

{

if (k > fac(a) + fac(b))

{

cout << "NO" << endl;

}

else

{

cout << "YES" << endl;

}

return 0;

}

Date June 11, 2021
Category Codeforces
Comments No Comments

Java神坑

一直听说Java的Arrays.sort()是O(n^2), 没有见识到它的厉害, 今天坑死了, 一直TLE…赶紧换了cpp

Date June 10, 2021
Category Others
Comments No Comments

Codeforces Round #725 (Div. 3)C. Number of Pairs

给一组数和l还有r, 求这组数中任意两个数的和在[L,R]中.

先排序, 然后求[0,R], 然后再求[0,L-1], 两个相减即可.

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    int t;
    cin >> t;
    while (t --)
    {
        int n,l,r;
        cin >> n >> l >> r;
        vector<int> v; 
        int k = n;
        while (k--)
        {
            int vv;
            cin >> vv;
            v.push_back(vv);
        }
        int res = 0;
        sort(v.begin(), v.end());
        auto count = [&](int r) -> long long{
            long long res = 0;
            int i = 0, j = n - 1;
            while(i < j) {
                while(i < j && v[i] + v[j] > r)
                {
                    j--;
                }
                res += (j - i);
                i++;
            }
            return res;
        };
        cout << count(r) - count(l - 1) << endl;
    }
    return 0;
}

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

41

#include <iostream>

#include <algorithm>

#include <vector>

using namespace std;

int main() {

ios::sync_with_stdio(0);

cin.tie(0),cout.tie(0);

int t;

cin >> t;

while (t --)

{

int n,l,r;

cin >> n >> l >> r;

vector<int> v;

int k = n;

while (k--)

{

int vv;

cin >> vv;

v.push_back(vv);

}

int res = 0;

sort(v.begin(), v.end());

auto count = [&](int r) -> long long{

long long res = 0;

int i = 0, j = n - 1;

while(i < j) {

while(i < j && v[i] + v[j] > r)

{

j--;

}

res += (j - i);

i++;

}

return res;

};

cout << count(r) - count(l - 1) << endl;

}

return 0;

}

Date June 10, 2021
Category Codeforces
Comments No Comments

Codeforces Round #725 (Div. 3)B. Friends and Candies

给一个n个数字的数组, 问最少可以取多少个数字, 使得分配给别的数字(包括自己),后让数组的值全相等.

一共n个数组, 那么全相等, 肯定就是sum % n == 0 才可能. 不然怎么分都分不出来.

然后因为要分给别的数, 所以只需要找到比sum/n大的数字, 即可., 因为反正这些大数都要分了才能变成sum/n, 是吧…..脑筋急转弯

   static class TaskB {
        public void solve(int testNumber, InputReader in, OutputWriter out) {
            int n = in.readInt();
            int[] ary = in.readIntArray(n);
            Arrays.sort(ary);
            int sum = 0;
            for (int a : ary)
                sum += a;
            if (sum % n != 0) {
                out.printLine(-1);
                return;
            }
            int count = 0;
            int t = 0;
            for (int i = 0; i < ary.length; i++) {
                ary[i] -= sum / n;
                if (ary[i] < 0)
                    t += ary[i];
            }
            for (int i = ary.length - 1; i >= 0; i--) {
                if (t >= 0)
                    break;
                t += ary[i];
                count++;
            }
            out.printLine(count);
        }
 
    }

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

static class TaskB {

public void solve(int testNumber, InputReader in, OutputWriter out) {

int n = in.readInt();

int[] ary = in.readIntArray(n);

Arrays.sort(ary);

int sum = 0;

for (int a : ary)

sum += a;

if (sum % n != 0) {

out.printLine(-1);

return;

}

int count = 0;

int t = 0;

for (int i = 0; i < ary.length; i++) {

ary[i] -= sum / n;

if (ary[i] < 0)

t += ary[i];

}

for (int i = ary.length - 1; i >= 0; i--) {

if (t >= 0)

break;

t += ary[i];

count++;

}

out.printLine(count);

}

Date June 10, 2021
Category Leetcode
Comments No Comments

Codeforces Round #725 (Div. 3)A. Stone Game

给一个数组, 可以从两端取数字, 取了就没了, 求最少多少步可以取了最大和最小值.

这题他妈的真费时间, 一共3种取法 (答案给的是四种), 反正我三种做的, 三种是: 从左往右取, 从右往左和两侧取.

这题给了最大值是n, 最小值是1, 所以1/2两种都很好做, 就是第三个, 需要找下两个值的坐标, 然后减去两端就行了.

static class TaskA {
        public void solve(int testNumber, InputReader in, OutputWriter out) {
            int maxIndex = -1;
            int minIndex = -1;
            int n = in.readInt();
            int[] ary = in.readIntArray(n);
            int left = 0, right = 0, both = 0;
            for (int i = 0; i < n; i++) {
                if (ary[i] == 1)
                    minIndex = i;
                else if (ary[i] == n)
                    maxIndex = i;
            }
            boolean one = false;
            boolean two = false;
            for (int i = 0; i < n; i++) {
                if (ary[i] == 1)
                    one = true;
                else if (ary[i] == n)
                    two = true;
                if (one && two) {
                    left = i + 1;
                    break;
                }
            }
            one = false;
            two = false;
            for (int i = n - 1; i >= 0; i--) {
                if (ary[i] == 1)
                    one = true;
                else if (ary[i] == n)
                    two = true;
                if (one && two) {
                    right = n - i;
                    break;
                }
            }
            both = Math.min(minIndex, maxIndex) + 1 + n - Math.max(minIndex, maxIndex);
            out.printLine(Math.min(Math.min(left, right), both));
        }
 
    }

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

41

42

static class TaskA {

public void solve(int testNumber, InputReader in, OutputWriter out) {

int maxIndex = -1;

int minIndex = -1;

int n = in.readInt();

int[] ary = in.readIntArray(n);

int left = 0, right = 0, both = 0;

for (int i = 0; i < n; i++) {

if (ary[i] == 1)

minIndex = i;

else if (ary[i] == n)

maxIndex = i;

}

boolean one = false;

boolean two = false;

for (int i = 0; i < n; i++) {

if (ary[i] == 1)

one = true;

else if (ary[i] == n)

two = true;

if (one && two) {

left = i + 1;

break;

}

one = false;

two = false;

for (int i = n - 1; i >= 0; i--) {

if (ary[i] == 1)

one = true;

else if (ary[i] == n)

two = true;

if (one && two) {

right = n - i;

break;

}

both = Math.min(minIndex, maxIndex) + 1 + n - Math.max(minIndex, maxIndex);

out.printLine(Math.min(Math.min(left, right), both));

}

Date June 10, 2021
Category Codeforces
Comments No Comments

方格取数

给一个2d矩阵, 里面有数字, 求取两个线上的数字,使得和最大, 只能往下和右走.

这个题我开始以为是greedy, 直接取一次, 再取一次就可以了, 然后感觉是不对的, 因为第一次走如果取了最大的值, 肯定会走过一些不是最大的值的路径, 而这些路径上的值是否就一定没有包含次大的值呢? 这个是不知道的. 所以要同时走才可以.

因为是同时, 相当于两个人在走A: (i1, j1),B: (i2,j2), 那么应该有 2*2四种情况. 所以应该是4维dp..然后看了讨论里,用的是压缩一维的方法, 即:

因为是n*n这么大的个子, 而且还只能往下往右走, 那么最多的步数就是2*n. 那么, 设k为当前步数, 就可以通过i找到j, 因为i+j=k, 比如极限情况下, 先走右到头然后下到头, 就是i=n, k=2*n, j = k-i = 2*n – n = n, 这样可以压缩一维, 四维变成三维

还有, 当计算数字的时候,如果两个人在同一格, 应该只取一次. 其他情况取各自格上的数.

#include <iostream>
#include <algorithm>
using namespace std;

int i,j,f;
const int N = 20; 
int m[N][N];
int dp[N*2][N][N];
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    int n;
    cin >> n; 
    while (cin >> i >> j >> f, i||j||f)
    {
        m[i][j] = f;
    }
    for (int k = 2; k <= 2*n; k++)
    {
        for (int i1 = 1; i1 <= n; i1++)
        {
            for (int i2 = 1; i2 <= n; i2++)
            {
                int j1 = k - i1;
                int j2 = k - i2;
                if (i1 < 1 || i2 < 1 || i1 > n  || i2 > n || j1 < 1 || j2 < 1 || j1 > n || j2 > n)
                {
                    continue;
                }
                int c = 0;
                if (i1 == i2 && j1 == j2)
                { 
                    c = m[i1][j1];// only pick once
                }
                else
                {
                    c = m[i1][j1] + m[i2][j2];
                }
                dp[k][i1][i2] = max(dp[k][i1][i2], dp[k - 1][i1][i2] + c)  ;
                dp[k][i1][i2] = max(dp[k][i1][i2], dp[k - 1][i1 - 1][i2] + c);
                dp[k][i1][i2] = max(dp[k][i1][i2], dp[k - 1][i1][i2 - 1] + c);
                dp[k][i1][i2] = max(dp[k][i1][i2], dp[k - 1][i1 - 1][i2 - 1] + c);
            }
        }
    }
    cout << dp[2*n][n][n] << endl; 
    return 0;
}

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

41

42

43

44

45

46

47

48

#include <iostream>

#include <algorithm>

using namespace std;

int i,j,f;

const int N = 20;

int m[N][N];

int dp[N*2][N][N];

int main() {

ios::sync_with_stdio(0);

cin.tie(0),cout.tie(0);

int n;

cin >> n;

while (cin >> i >> j >> f, i||j||f)

{

m[i][j] = f;

}

for (int k = 2; k <= 2*n; k++)

{

for (int i1 = 1; i1 <= n; i1++)

{

for (int i2 = 1; i2 <= n; i2++)

{

int j1 = k - i1;

int j2 = k - i2;

if (i1 < 1 || i2 < 1 || i1 > n || i2 > n || j1 < 1 || j2 < 1 || j1 > n || j2 > n)

{

continue;

}

int c = 0;

if (i1 == i2 && j1 == j2)

{

c = m[i1][j1];// only pick once

}

else

{

c = m[i1][j1] + m[i2][j2];

}

dp[k][i1][i2] = max(dp[k][i1][i2], dp[k - 1][i1][i2] + c) ;

dp[k][i1][i2] = max(dp[k][i1][i2], dp[k - 1][i1 - 1][i2] + c);

dp[k][i1][i2] = max(dp[k][i1][i2], dp[k - 1][i1][i2 - 1] + c);

dp[k][i1][i2] = max(dp[k][i1][i2], dp[k - 1][i1 - 1][i2 - 1] + c);

}

cout << dp[2*n][n][n] << endl;

return 0;

}

Date June 10, 2021
Category AcWing
Comments No Comments

摘花生

给一个2d矩阵, 只能往下往右走, 每个格上有数字, 求最大能拿多少数字.

#include <iostream>
#include <algorithm>
using namespace std;

const int N = 110;
int dp[N][N];
int m[N][N];
int main() {
    int t;
    cin >> t;
    while (t--)
    {
        int row,col;
        cin >> row;
        cin >> col;
        for (auto i = 1; i <= row; i++)
        {
            for (auto j = 1; j <= col; j++)
            {
                cin >> m[i][j];
            }
        } 
        for (auto i = 1; i <= row; i++)
        {
            for(auto j = 1; j <= col; j++) {
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]) + m[i][j]; // dp[1][1] = max(dp[0][1],dp[1][0]) + 
            }
        }
        cout << dp[row][col] << endl;
    }
}

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

#include <iostream>

#include <algorithm>

using namespace std;

const int N = 110;

int dp[N][N];

int m[N][N];

int main() {

int t;

cin >> t;

while (t--)

{

int row,col;

cin >> row;

cin >> col;

for (auto i = 1; i <= row; i++)

{

for (auto j = 1; j <= col; j++)

{

cin >> m[i][j];

}

for (auto i = 1; i <= row; i++)

{

for(auto j = 1; j <= col; j++) {

dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]) + m[i][j]; // dp[1][1] = max(dp[0][1],dp[1][0]) +

}

cout << dp[row][col] << endl;

}

Date June 10, 2021
Category AcWing
Comments No Comments

Determine Whether Matrix Can Be Obtained By Rotation

给两个nxn矩阵, 问是否能通过连续翻转90度得到另一个矩阵.

class Solution {
public:
    bool findRotation(vector<vector<int>>& m, vector<vector<int>>& t) {
        bool one = true;
        bool two = true;
        bool three = true;
        bool four = true;
        int n = m.size();
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < n; j++) {
                if(m[i][j] != t[i][j]) // orignal
                    one = false;
                if(m[i][j] != t[n - 1 - j][i]) // 90
                    two = false;
                if(m[i][j] != t[n - 1 - i][n - 1 - j]) // 180
                    three = false;
                if(m[i][j] != t[j][n - 1 - i])// 270
                    four = false;
            }
        }
        return one || two || three || four;
    } 
};

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

class Solution {

public:

bool findRotation(vector<vector<int>>& m, vector<vector<int>>& t) {

bool one = true;

bool two = true;

bool three = true;

bool four = true;

int n = m.size();

for(int i = 0; i < n; i++) {

for(int j = 0; j < n; j++) {

if(m[i][j] != t[i][j]) // orignal

one = false;

if(m[i][j] != t[n - 1 - j][i]) // 90

two = false;

if(m[i][j] != t[n - 1 - i][n - 1 - j]) // 180

three = false;

if(m[i][j] != t[j][n - 1 - i])// 270

four = false;

}

return one || two || three || four;

}

};

Date June 7, 2021
Category Leetcode
Comments No Comments

Codeforces Round #724 (Div. 2)B. Prinzessin der Verurteilung

给一个字符串s, 求字典序最小的字符串没有在s中出现.

这题就是bfs按个试..妈的, 比赛的时候想多了. 浪费时间

package readman;

import net.egork.io.InputReader;
import net.egork.io.OutputWriter;

import java.util.*;

public class TaskB {
    public void solve(int testNumber, InputReader in, OutputWriter out) {
        int n = in.readInt();
        String s = in.readString();
         List<String> list = new ArrayList<>();
         list.add("");
        while (true) {
            int size = list.size();
            for (int i = 0; i < size; i++){
                if (list.size() > 1 && list.get(i) == "")
                    continue;
                for (int j = 0; j < 26; j++) {
                    String ss = list.get(i) + (char) ('a' + j);
                     if (!s.contains(ss)){
                        out.printLine(ss);
                        return;
                    }
                     list.add(ss);
                }
            }
        }
    }
}

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

package readman;

import net.egork.io.InputReader;

import net.egork.io.OutputWriter;

import java.util.*;

public class TaskB {

public void solve(int testNumber, InputReader in, OutputWriter out) {

int n = in.readInt();

String s = in.readString();

List<String> list = new ArrayList<>();

list.add("");

while (true) {

int size = list.size();

for (int i = 0; i < size; i++){

if (list.size() > 1 && list.get(i) == "")

continue;

for (int j = 0; j < 26; j++) {

String ss = list.get(i) + (char) ('a' + j);

if (!s.contains(ss)){

out.printLine(ss);

return;

}

list.add(ss);

}

Date June 7, 2021
Category Codeforces
Comments No Comments

Codeforces Round #725 (Div. 3)F. Interesting Function

Codeforces Round #725 (Div. 3)D. Another Problem About Dividing Numbers

Java神坑

Codeforces Round #725 (Div. 3)C. Number of Pairs

Codeforces Round #725 (Div. 3)B. Friends and Candies

Codeforces Round #725 (Div. 3)A. Stone Game

方格取数

摘花生

Determine Whether Matrix Can Be Obtained By Rotation

Codeforces Round #724 (Div. 2)B. Prinzessin der Verurteilung

书脊

这青苔碧瓦堆, 俺曾睡风流觉, 将五十年兴亡看饱.

Categories

Tags