头像

戈好雨

南京大学


访客:8370

离线:7个月前


活动打卡代码 AcWing 796. 子矩阵的和

戈好雨
7个月前
N, M, Q = map(int, input().split())
matrix_int = [0] * N
for i in range(N):
    matrix_int[i] = (list(map(int, input().split())))
query = []
for i in range(Q):
    query.append(list(map(int, input().split())))


matrix_sum = [[0] * M for i in range(N)]
matrix_sum[0][0] = matrix_int[0][0]

for i in range(1, N):
    matrix_sum[i][0] = matrix_sum[i - 1][0] + matrix_int[i][0]
for i in range(1, M):
    matrix_sum[0][i] = matrix_sum[0][i - 1] + matrix_int[0][i]

for i in range(1, N):
    for j in range(1, M):
        matrix_sum[i][j] = matrix_sum[i][j - 1] + matrix_sum[i - 1][j] - matrix_sum[i - 1][j - 1] + matrix_int[i][j] 

matrix_sum.insert(0,[0] * M)   
for i in range(N + 1):
    matrix_sum[i].insert(0,0)

def minus(my_list):
    global matrix_sum
    x1, y1, x2, y2 = my_list[0], my_list[1], my_list[2], my_list[3]
    print(matrix_sum[x2][y2] + matrix_sum[x1 - 1][y1 - 1] - matrix_sum[x2][y1 - 1] - matrix_sum[x1 - 1][y2])

for i in query:
    minus(i)



活动打卡代码 AcWing 795. 前缀和

戈好雨
7个月前
N, M = map(int, input().split())
sequence = list(map(int, input().split()))
sequence.insert(0,0)
query = []
for i in range(M):
    query.append(list(map(int, input().split())))


sum = [0] * (N + 1)
sum[1] = sequence[1]
for i in range(2, N + 1):
    sum[i] = sum[i - 1] + sequence[i]

def minus(my_list):
    global sum
    l, r = my_list[0], my_list[1]
    print(sum[r] - sum[l - 1])

for i in range(M):
    minus(query[i])


活动打卡代码 AcWing 789. 数的范围

戈好雨
7个月前
N, Q = map(int, input().split())
sequence = list(map(int, input().split()))
query = []
for i in range(Q):
    query.append(int(input()))


def bi_search_left(target, my_list):
    left = 0
    right = len(my_list) - 1
    while left < right:
        mid = left + right >> 1
        if my_list[mid] < target:
            left = mid + 1
        else:
            right = mid
    if my_list[right] != target:
        right = -1
    return right

def bi_search_right(target, my_list):
    left = 0
    right = len(my_list) - 1
    while left < right:
        mid = left + right + 1 >> 1
        if my_list[mid] > target:
            right = mid - 1
        else:
            left = mid
    if my_list[left] != target:
        left = -1
    return left

for i in query:
    print(bi_search_left(i, sequence), bi_search_right(i, sequence))


活动打卡代码 AcWing 788. 逆序对的数量

戈好雨
7个月前
N = int(input())
sequence = list(map(int, input().split()))

res = 0
def merge_sort(my_list):
    global res
    if len(my_list) > 1:
        mid = len(my_list) >> 1
        L = my_list[:mid]
        R = my_list[mid:]
        merge_sort(L)
        merge_sort(R)
        i, j, k = 0, 0, 0
        while i < len(L) and j < len(R):
            if L[i] <= R[j]:
                my_list[k] = L[i]
                i += 1

            else:
                my_list[k] = R[j]
                j += 1
                res += len(L) - i
            k += 1
        while i < len(L):
            my_list[k] = L[i]
            i += 1
            k += 1
        while j < len(R):
            my_list[k] = R[j]
            j += 1
            k += 1

merge_sort(sequence)
print(res)


活动打卡代码 AcWing 787. 归并排序

戈好雨
7个月前
N = int(input())
sequence = list(map(int, input().split()))


def merge_sort(my_list):
    if len(my_list) > 1:
        mid = len(my_list) >> 1
        L = my_list[:mid]
        R = my_list[mid:]
        merge_sort(L)
        merge_sort(R)
        i, j, k = 0, 0, 0
        while i < len(L) and j < len(R):
            if L[i] < R[j]:
                my_list[k] = L[i]
                i += 1
            else:
                my_list[k] = R[j]
                j += 1
            k += 1
        while i < len(L):
            my_list[k] = L[i]
            k += 1
            i += 1
        while j < len(R):
            my_list[k] = R[j]
            k += 1
            j += 1

merge_sort(sequence)
print(' '.join(map(str, sequence)))


活动打卡代码 AcWing 786. 第k个数

戈好雨
7个月前
N, K = map(int, input().split())
sequence = list(map(int, input().split()))

def quick_sort(my_list, left, right, K):
    if left < right:
        i = left - 1
        j = right + 1
        mid = my_list[i + j >> 1]
        while i < j:
            while 1:
                i += 1
                if my_list[i] >= mid:
                    break
            while 1:
                j -= 1
                if my_list[j] <= mid:
                    break
            if i < j:
                my_list[i], my_list[j] = my_list[j], my_list[i]
        if j - left + 1 >= K:
            quick_sort(my_list, left, j, K)
        else:
            quick_sort(my_list, j + 1, right, K - j - 1 + left)

quick_sort(sequence, 0, N - 1, K)
print(sequence[K - 1])


活动打卡代码 AcWing 785. 快速排序

戈好雨
7个月前
N = int(input())
sequence = list(map(int, input().split()))


def quick_sort(my_list, left, right):
    if left < right:
        i = left - 1
        j = right + 1
        mid = my_list[i + j >> 1]
        while i < j:
            while 1:
                i += 1
                if my_list[i] >= mid:
                    break
            while 1:
                j -= 1
                if my_list[j] <= mid:
                    break
            if i < j:
                my_list[i], my_list[j] = my_list[j], my_list[i]

        quick_sort(my_list, left, j)
        quick_sort(my_list, j + 1, right)

quick_sort(sequence, 0, N - 1)

print(' '.join(map(str, sequence)))


活动打卡代码 AcWing 790. 数的三次方根

戈好雨
7个月前
N = float(input())
left = -10001
right = 10001

def lfg(target):
    global left, right
    while abs(left - right) > 1e-7:
        mid = (left + right) / 2
        if mid ** 3 > target:
            right = mid
        else:
            left = mid
    return left

print('%.6f' % lfg(N))



戈好雨
7个月前
import copy


def dfs(x, y, s):  # 对于第x行,第y列,第s个queen
    global N
    if s > N:
        return
    if y == N:
        y = 0
        x += 1
    if x == N:
        if s == N:
            ans.append(copy.deepcopy(graph))
        return
    dfs(x, y + 1, s)
    if state_row[x] == False and state_col[y] == False and state_dg[x + y] == False and state_bdg[N + x - y] == False:
        graph[x][y] = 'Q'
        state_row[x] = state_col[y] = state_dg[x + y] = state_bdg[N + x - y] = True
        dfs(x, y + 1, s + 1)
        state_row[x] = state_col[y] = state_dg[x + y] = state_bdg[N + x - y] = False
        graph[x][y] = '.'

N = int(input())
ans = []
state_row = [False] * N
state_col = [False] * N
state_dg = [False] * 2 * N
state_bdg = [False] * 2 * N
graph = [['.'] * N for i in range(N)]

dfs(0,0,0)

for i in range(len(ans)):
    for u in range(len(ans[i])):
        print(''.join(ans[i][u]))
    print('')



戈好雨
7个月前

为什么在if判断之前就可以直接dfs(x, y + 1, s),这样不是无限从头开始到dfs(x, y + 1, s)吗?下面的代码应该没有进入编译呀。dfs(x, y + 1, s)这句是不是应该放在if的else后面呢?

#include <iostream>

using namespace std;

const int N = 10;

int n;
bool row[N], col[N], dg[N * 2], udg[N * 2];
char g[N][N];

void dfs(int x, int y, int s)
{
    if (s > n) return;
    if (y == n) y = 0, x ++ ;

    if (x == n)
    {
        if (s == n)
        {
            for (int i = 0; i < n; i ++ ) puts(g[i]);
            puts("");
        }
        return;
    }

    g[x][y] = '.';
    dfs(x, y + 1, s);

    if (!row[x] && !col[y] && !dg[x + y] && !udg[x - y + n])
    {
        row[x] = col[y] = dg[x + y] = udg[x - y + n] = true;
        g[x][y] = 'Q';
        dfs(x, y + 1, s + 1);
        g[x][y] = '.';
        row[x] = col[y] = dg[x + y] = udg[x - y + n] = false;
    }
}

int main()
{
    cin >> n;

    dfs(0, 0, 0);

    return 0;
}