Journal de participation Atcoder Beginner Contest 146

C

Il s'avère que la recherche complète est plus difficile que la plage. Je pensais qu'il y avait une sorte de règle, mais je ne pouvais pas la résoudre.

Le point de ce problème est

  1. Notez que le cercle $ A × N + B × d (N) $ a une linéarité

  2. Notez que la dichotomie peut résoudre des problèmes linéaires Est.

  3. est explicite.

  4. Vous devez être conscient que les tableaux triés ascendants sont synonymes de fonctions linéaires

Je n'ai pas compris 2.

A , B , X = map(int,input().split())
ans = 10**9 // 2
diff = ans
digit_ans = len(str(ans))
while not A * ans + B * digit_ans <= X < A * (ans+1) + B * len(str(ans+1)):
    diff = max(diff // 2 , 1)
    if A * ans + B * digit_ans > X:
        ans -= diff
    else:
        ans += diff
    digit_ans = len(str(ans))
    #print(ans)
    if ans >= 10 ** 9:
        print(10**9)
        exit()
    elif ans <= 0:
        print("0")
        exit()
print(ans)

D Il peut être résolu en définissant un itinéraire et une coloration autre que la couleur utilisée. Méthode gourmande. TLE quand j'ai essayé de faire l'arrangement des couleurs et recherché avec une liste en deux dimensions. Est-ce un problème de mémoire parce qu'il a été résolu en utilisant le type de dictionnaire? On pense que. (Le gros commentaire au milieu est les vestiges de la spécification de liste bidimensionnelle)

from collections import deque
#Entrée, initialisation
N = int(input())
tree = [[] for _ in range(N)]
input_list = []
for _ in range(N - 1):
    a, b = map(int, input().split())
    a, b = a - 1, b - 1
    input_list.append([a, b])
    tree[a].append(b)
    tree[b].append(a)
 
 
#Stocker la couleur du nœud dans visité
# visited_edge = [[0] * N for _ in range(N)]
dict = {}
'''
#Couleur avec bfs
def bfs(now_node, max_val=0):
    queue = deque([[tree[now_node], -1, now_node]])
    while queue:
        next_nodes, before_color, now_node = queue.pop()
        now_color = 1
        for next_node in next_nodes:
            if visited_edge[now_node][next_node] != 0:
                continue
            if now_color == before_color:
                now_color += 1
            if max_val < now_color:
                max_val = now_color
            visited_edge[next_node][now_node] = now_color
            visited_edge[now_node][next_node] = now_color
            queue.appendleft([tree[next_node], now_color, next_node])
            now_color += 1
    return max_val
'''
def bfs(now_node, max_val=0):
    queue = deque([[tree[now_node], -1, now_node]])
    while queue:
        next_nodes, before_color, now_node = queue.pop()
        now_color = 1
        for next_node in next_nodes:
            key = tuple(sorted([now_node, next_node]))
            if not dict.get(key) is None:
                continue
            if now_color == before_color:
                now_color += 1
            if max_val < now_color:
                max_val = now_color
            dict[key] = now_color
            # visited_edge[now_node][next_node] = now_color
            queue.appendleft([tree[next_node], now_color, next_node])
            now_color += 1
    return max_val
 
ans = bfs(0)
print(ans)
for a, b in input_list:
    # print(visited_edge[a][b])
    print(dict[tuple(sorted([a,b]))])

Recommended Posts

Journal de participation Atcoder Beginner Contest 146
AtCoder Beginner Contest 181 Rapport de participation
AtCoder Beginner Contest 151 Rapport de participation
AtCoder Débutant Contest 176 Rapport de participation
AtCoder Beginner Contest 154 Rapport de participation
Note de participation au concours pour débutants AtCoder # 003
AtCoder Beginner Contest 166 Rapport de participation
AtCoder Beginner Contest 153 Rapport de participation
AtCoder Beginner Contest 145 Rapport de participation
AtCoder Débutant Contest 184 Rapport de participation
AtCoder Beginner Contest 165 Rapport de participation
Rapport de participation au concours AtCoder Débutant 160
AtCoder Beginner Contest 169 Rapport de participation
AtCoder Beginner Contest 178 Rapport de participation
AtCoder Beginner Contest 163 Rapport de participation
AtCoder Beginner Contest 164 Rapport de participation
Rapport de participation au concours AtCoder Débutant 150
Rapport de participation au concours AtCoder Débutant 180
AtCoder Beginner Contest 156 Rapport de participation
AtCoder Beginner Contest 162 Rapport de participation
AtCoder Débutant Contest 157 Rapport de participation
AtCoder Beginner Contest 167 Rapport de participation
AtCoder Débutant Contest 179 Rapport de participation
Concours AtCoder Débutant 182
AtCoder Beginner Contest 146 Rapport de participation
AtCoder Débutant Contest 155 Rapport de participation
AtCoder Beginner Contest 174 Rapport de participation
AtCoder Beginner Contest 171 Rapport de participation
AtCoder Beginner Contest 149 Rapport de participation
AtCoder Beginner Contest 148 Rapport de participation
AtCoder Débutant Contest 170 Rapport de participation
AtCoder Débutant Contest 183 Rapport de participation
Concours AtCoder Débutant 177
Concours AtCoder Débutant 179
Concours AtCoder Débutant 172
Concours AtCoder Débutant 180
Concours AtCoder Débutant 173
Concours Atcoder Débutant 153
Critique du concours AtCoder Beginner Contest 152
Concours AtCoder Débutant 181 Remarque
Critique du concours AtCoder Débutant 160
Critique du concours AtCoder Débutant 178
Concours AtCoder Débutant 180 Remarque
AtCoder Débutant Contest 167 Évaluation
Concours AtCoder Débutant 182 Remarque
Critique du concours AtCoder
AtCoder Débutant Contest 169 Évaluation
Critique du concours AtCoder Débutant 181
AtCoder Débutant Contest 171 Critique
Critique du concours AtCoder pour débutant 182
Critique du concours AtCoder Débutant 180
Concours AtCoder pour débutants 156 WriteUp
AtCoder Débutant Contest 168 Critique
Critique du concours AtCoder
Concours AtCoder pour débutants 167
Critique du concours AtCoder pour débutant 172
Concours AtCoder Débutant 183 Remarque
Critique du concours AtCoder