【 수론 】 【 DP 】 【 LCM 】 2018 USP - ICMC 【 보충 대기 】
A. Nicoleta and the circle of kids
Description
모든 사람 은 가장 먼 곳 에서 제 (i + k)% n 명 까지 연결 할 수 있 습 니 다. 변 권 은 두 사람 사이 의 거리 이 고 최대 생 성 트 리 를 구 합 니 다.
Range
1 ≤ K
Solution
방안 1: LCM 은 모든 사람 이 가장 좋 은 연결 전략 을 선택한다. 만약 에 인원수 가 무한 확대 할 수 있 는 전제 에서 모든 사람 이 다음 k 개인 에 게 연결 할 수 있다 고 가정 하면 순환 절 을 쉽게 얻 을 수 있다. 길 이 는
lcm(n, k) 이 고 모든 절차 에 대해 연결 의 출발점 (왼쪽 에 점 이 없 음) 으로 할 수 있 는 점 은 모두 n * k / l 이다.개, 동시에 모든 출발점 에서 출발 하 는 노선 의 길 이 는 k 의 변 이 모두 l / k - 1 개 입 니 다.이러한 전략 적 연결 을 거 친 후에 n * k / l 개의 (즉, 이른바 시작 포인트) 독립 된 긴 사슬 이 형성 되 었 다. 그러면 이 긴 사슬 사이 에 두 개의 길이 가 k - 1 인 변 을 연결 하면 한 그루 의 나 무 를 형성 할 수 있다.방안 2: gcd 는 모든 사람 이 먼저 k 개인 에 게 연 결 됩 니 다. 나머지 는 k - 1 명 까지 연 결 됩 니 다. 이렇게 얻 은 변 권 과 반드시 가장 큰 것 입 니 다.
Code
#pragma GCC diagnostic error "-std=c++11"
#include
", ans);
}
return 0;
}
B. Ugly Number
Description
길이 가 n 인 숫자 를 보 여 줍 니 다. 회전 하 는 과정 에서 초기 상태 보다 작은 숫자 가 나타 나 는 지 물 어보 십시오.
Solution
이 문자열 에 대해 서 는 회전 과정 에서 나타 날 수 있 는 최소 표현 법 을 구 할 수 있 습 니 다. 최소 표현 법의 첫 번 째 문자 가 초기 문자열 의 첫 번 째 문자 가 아니라면 합 법 적 이지 않 습 니 다.
Code
#pragma GCC diagnostic error "-std=c++11"
#include
"); return 0; }
}
int l = 1, r = 2;
while(l <= n && r <= n) {
int k = 0;
while(k <= n && s[l+k] == s[r+k]) k++;
if(s[l+k] <= s[r+k]) r += k + 1;
else l += k + 1;
}
if(min(l, r) == 1) printf("Yes
");
else printf("No
");
return 0;
}
C. Two Cats
Description
Solution
Code
E. Loppinha, the boy who likes sopinha
Description
Solution
Code
G. Traffic Management
Description
한 직선 에서 n 대의 차 가 고 른 속도 로 달리 고 있 으 며, 모든 차 는 자신의 초기 위치 와 속 도 를 가지 고 있 으 며, 뒤의 차 가 앞의 차 와 충돌 할 때 뒤의 차 의 속 도 는 순식간에 앞 차 와 똑 같이 변 하여 마지막 충돌 시간 을 묻는다.
Solution
Code
#pragma GCC diagnostic error "-std=c++11"
#include
", ans);
return 0;
}
I. I Will Go
Description
한 게임 이 있 습 니 다. 지금 모두 n 명 이 있 습 니 다. n 개의 관 계 를 드 리 겠 습 니 다. 만약 에 i 명 이 가면 a [i] 개인 도 가 야 합 니 다.
Solution
i 번 째 사람 이 a [i] 에 가 려 면 개인 도 가 야 한다 면 하나의 관 계 를 형성 할 수 있다. 그러면 이런 점 간 의 관 계 를 이용 하여 숲 을 만 들 수 있 고 연 결 된 점 마다 표 시 를 하면 끝 이 없 는 점 은 숲 속 의 모든 나무의 뿌리 부분 으로 할 수 있다.
방안 1: LCA 는 가상 결점 을 만들어 이 나무의 뿌리 노드 와 연결 시 켜 나무 한 그루 를 형성 했다. 이 나무 에 대해 결점 u 가 결점 v 의 조상 인지 아 닌 지 를 조회 하면 된다.
방안 2: DFS 는 모든 나무의 뿌리 노드 로 dfs 순 서 를 한 번 달리 면 이 결점 u 의 dfs 순서 가 점 v 안에 있 는 지 여 부 를 판단 할 수 있 습 니 다.
Code
#pragma GCC diagnostic error "-std=c++11"
#include
");
else printf("No
");
// printf("%d
", LCA(u, v));
}
return 0;
}
// ：
/*
vector G[MaxN];
int ind[MaxN];
int l[MaxN], r[MaxN]; // dfs
int cur = 0;
void dfs(int x) {
l[x] = ++cur;
for(int i = 0; i < G[x].size(); i++) {
int u = G[x][i];
dfs(u);
}
r[x] = ++cur;
}
int main()
{
int n, q; scanf("%d %d", &n, &q);
for(int i = 0; i < n; i++) {
int v; scanf("%d", &v);
if(v == -1) continue;
G[v].push_back(i);
ind[i]++;
}
for(int i = 0; i < n; i++) {
if(!ind[i]) dfs(i);
}
while(q--) {
int u, v; scanf("%d %d", &u, &v);
if(l[v] <= l[u] && r[v] >= r[u]) cout << "Yes" << endl;
else cout << "No" << endl;
}
return 0;
}*/
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
124. 두 갈래 나무의 최대 경로와 leetcode비공 두 갈래 트리를 지정하고 최대 경로와 를 되돌려줍니다. 본고에서 경로는 나무의 임의의 노드에서 출발하여 임의의 노드에 도달하는 서열로 정의되었다.이 경로는 루트 노드를 거치지 않고 하나 이상의 노드를 포함합니다...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
