우 객 망 - 우 객 홀 리 데 이 단체 전 8
제목 링크:https://ac.nowcoder.com/acm/contest/1069/A/
제목: 신호 탑 과 인접 한 잔디 에서 신 호 를 받 을 수 있다 는 것 을 알 고 있다.N - 1 잔디 (A, B) 의 인접 관 계 를 드 리 겠 습 니 다. 최소 몇 개의 신호 탑 을 만들어 야 모든 잔디 에 신호 가 있 는 지 물 어보 세 요.사고방식: 욕심, 모든 잎 사 귀 노드 를 고려 하면 우 리 는 발견 할 수 있다.잎 노드 를 덮 으 려 면 가장 좋 은 방안 은 아버지 노드 에 신호 탑 을 만 드 는 것 이다.그래서 우 리 는 매번 노드 를 찾 을 때마다 이 노드 는 만족 합 니 다. 그의 서브 트 리 (잎 노드) 는 이미 완전히 덮 였 습 니 다.그리고 이 노드 의 아버지 노드 에 신호 탑 을 세우 고 인접 한 노드 를 덮는다.이상 의 조작 을 반복 합 니 다.우 리 는 나 무 를 지 을 때 거 슬러 올 라 간 후에 (또는 현재 점 이 잎 노드 일 때) 이 점 이 덮 였 는 지, 없 으 면 아버지 와 아버지의 인접 노드 를 덮 었 는 지 판단 할 수 있다.분명히 현재 노드 로 거 슬러 올 라 갈 때 그 하위 나 무 는 이미 완전히 덮 여 있 었 다.
Accepted Code:
#include
using namespace std;
const int MAXN = 20005;
typedef long long ll;
struct edge {
int u, v;
}e[MAXN << 1];
int n, t = 0, cnt = 0, res = 0;
int par[MAXN], f[MAXN];
bool vis[MAXN], visp[MAXN], vist[MAXN];
inline void Add(int u, int v) {
e[++t] = (edge){f[u], v};
f[u] = t;
}
inline void init() {
memset(f, 0, sizeof(f));
memset(par, 0, sizeof(par));
memset(vis, false, sizeof(vis));
memset(visp, false, sizeof(visp));
}
void DFS(int u) {
vis[u] = true;
for (int i = f[u]; i; i = e[i].u) {
int v = e[i].v;
if (!vis[v]) {
par[v] = u;
DFS(v);
}
}
if (!visp[u]) {
res++;
int p = par[u];
visp[p] = true;
for (int i = f[p]; i; i = e[i].u)
visp[e[i].v] = true;
}
}
int main() {
init();
int u, v;
scanf("%d", &n);
for (int i = 0; i < n - 1; i++) {
scanf("%d%d", &u, &v);
Add(u, v);
Add(v, u);
}
par[1] = 1;
DFS(1);
printf("%d
", res);
return 0;
} Problem B iCow
제목 링크:https://ac.nowcoder.com/acm/contest/1069/B/
제목: 현재 MP3 가 있 습 니 다. 재생 순서 와 규칙 은:
첫 번 째 부터 K 번 째 까지 재생 순 서 를 구 할 수 있 도록 초기 값 을 드 립 니 다.사고방식: 직접 시 뮬 레이 션.
Accepted Code:
#include
using namespace std;
const int MAXN = 1005;
typedef long long ll;
int p[MAXN];
int main() {
int n, t;
scanf("%d%d", &n, &t);
for (int i = 1; i <= n; i++)
scanf("%d", &p[i]);
while (t--) {
int max_ = 0, j = 1;
for (int i = 1; i <= n; i++)
if (p[i] > max_)
max_ = p[j = i];
printf("%d
", j);
int avg = p[j] / (n - 1);
for (int i = 1; i <= n; i++)
if (i != j)
p[i] += avg;
if (p[j] % (n - 1)) {
int rem = p[j] % (n - 1);
for (int i = 1; i <= n && rem; i++) {
if (i != j) {
p[i]++;
rem--;
}
}
}
p[j] = 0;
}
return 0;
} Problem C 곱셈 의 합
제목 링크:https://ac.nowcoder.com/acm/contest/1069/C/
제목: 1 ~ n 의 곱셈 의 합 을 구하 다.사고방식: 직접 대수 템 플 릿 에 올 라 갑 니 다.
Accepted Code:
#include
using namespace std;
const int MAXN = 100;
int s[MAXN], spt[MAXN], len = 1;
void Add(int a[], int la, int b[], int lb) {
int c = 0;
len = max(la, lb);
for (int i = 0; i < len; i++) {
a[i] += b[i] + c;
c = a[i] / 10;
a[i] %= 10;
}
if (c)
a[len++] = c;
}
int main() {
int n, t = 1, c = 0;
scanf("%d", &n);
s[0] = spt[0] = 1;
for (int i = 2; i <= n; i++) {
for (int j = 0; j < t; j++) {
s[j] = s[j] * i + c;
c = s[j] / 10;
s[j] %= 10;
}
while (c) {
s[t++] = c % 10;
c /= 10;
}
Add(spt, len, s, t);
}
for (int i = len - 1; i >= 0; i--)
printf("%d", spt[i]);
printf("
");
return 0;
} Problem D Artificial Lake
제목 링크:https://ac.nowcoder.com/acm/contest/1069/D/
제목: N 개의 연속 적 인 플랫폼 을 제시 합 니 다. 그들 은 각각 너비 가 있 고 높이 가 다 릅 니 다.먼저 높이 가 가장 낮은 플랫폼 에 물 을 주입 하고 넘 칠 때 까지 다른 플랫폼 으로 흘러 가 모든 플랫폼 이 덮어 질 때 까지 물 을 주입 합 니 다.분당 1 너비 1 의 물 을 주입 하고 플랫폼 마다 1 높이 의 물 로 덮 이 는 시간 을 구 하 는 것 으로 알려 져 있다.사고방식: 먼저 가장 낮은 플랫폼 을 찾 은 다음 에 물 을 주입 하기 시작한다.그 다음 에 가장 낮은 채 워 진 후에 물이 넘 치 는 것 은 이 플랫폼 이 사라 지 는 것 과 같 습 니 다. 좌우 플랫폼 을 업데이트 하고 다음 흐름 이 어느 플랫폼 으로 가 는 지 찾 습 니 다. 매번 에 가장 낮은 플랫폼 h 를 찾 은 다음 에 물 을 h 높이 로 채 웁 니 다.밖으로 확장 할 때 가끔 높이 가 점점 줄 어드 는 상황 을 만 날 수 있 습 니 다. 이 때 는 물 을 채 울 수 없 지만 이런 높이 를 모두 창고 에 기록 한 다음 에 수면 보다 높 은 플랫폼 h 를 만 났 을 때 물 을 붓 는 것 을 모 의 합 니 다. 물 은 가장 낮은 플랫폼 에 따라 물 에 잠 길 수 있 습 니 다. 즉, 창고 꼭대기 에서 한 번 씩 창고 에서 나 와 침수 시간 을 계산 하고 창고 꼭대기 플랫폼 의 높이 > h 까지 계산 해 야 합 니 다. 이때 h 는 창고 에 들 어 갑 니 다.반복 집행 하면 답 을 계산 할 수 있다.
Accepted Code:
#include
using namespace std;
const int MAXN = 100005;
const int inf = 0x3f3f3f3f;
struct edge {
int h, id;
long long w;
}sp[MAXN], stp[MAXN];
long long cnt[MAXN];
int main() {
int n, j, top, min_ = inf;;
scanf("%d", &n);
for (int i = 1; i <= n; i++) {
sp[i].id = i;
scanf("%lld%d", &sp[i].w, &sp[i].h);
if (min_ > sp[i].h)
min_ = sp[j = i].h;
}
top = 0;
sp[0].h = sp[n + 1].h = inf;
stp[top] = sp[0];
stp[++top] = sp[j];
long long t = 0;
int l = j, r = j, p;
for (int i = 1; i <= n; i++) {
long long w = 0;
if (sp[l - 1].h < sp[r + 1].h)
p = --l;
else p = ++r;
while (sp[p].h > stp[top].h) {
stp[top].w += w;
cnt[stp[top].id] = t + stp[top].w;
t += (min(sp[p].h, stp[top - 1].h) - stp[top].h) * stp[top].w;
w = stp[top].w;
top--;
}
sp[p].w += w;
stp[++top] = sp[p];
}
for (int i = 1; i <= n; i++)
printf("%lld
", cnt[i]);
return 0;
} Problem E Haybale Guessing
제목 링크:https://ac.nowcoder.com/acm/contest/1069/E/
제목: 일부 구간 의 최소 치 를 제시 하고 가장 먼저 어떤 문제 가 모순 되 고 출력 되 는 지 물 어보 세 요.사고: 구간 염색 문 제 는 집 을 찾 아 만 들 수 있다.먼저 2 분 모순 이 발생 하 는 곳 p 를 나 눈 다음 1 ~ p 의 문의 치 를 큰 것 에서 작은 것 으로 정렬 하고 최소 값 이 같은 구간 에서 교차 하지 않 는 두 구간 이 나타 나 면 모순 이 나타난다.그러면 합 법 적 인 경 우 는 이러한 최소 치가 같은 구간 이 반드시 두 개가 교차 하 는 것 이다. 그러면 가장 작은 왼쪽 점 L 과 가장 큰 오른쪽 점 R 을 기록 한 다음 에 [L, R] 과 L - 1 을 합병 하 는 것 이다.그래서 판단 할 때 현재 최소 치가 같은 구간 의 교 집합 이 이전에 있 었 는 지, 있 었 다 면 모순 을 판단 해 야 한다.
Accepted Code:
#include
using namespace std;
const int MAXN = 1000005;
struct node {
int l, r, num;
bool operator < (const node &s) const {
return s.num < num;
}
};
int n, q;
int father[MAXN];
node a[MAXN], tmp[MAXN];
int find(int x) {
while (father[x] != x)
x = father[x];
return x;
}
int cmp(node a, node b) {
return a.num > b.num;
}
bool check(int tot) {
for (int i = 1; i <= n; i++)
father[i] = i;
for (int i = 1; i <= tot; i++)
tmp[i] = a[i];
sort(tmp + 1, tmp + 1 + tot);
for (int i = 1, j; i <= tot; i = j + 1) {
j = i;
int l = tmp[i].l;
int r = tmp[i].r;
int L = tmp[i].l;
int R = tmp[i].r;
while (j < tot && tmp[j].num == tmp[j + 1].num) {
j++;
l = max(l, tmp[j].l);
r = min(r, tmp[j].r);
L = min(L, tmp[j].l);
R = max(R, tmp[j].r);
}
if (l > r || l > find(r))
return 0;
while (L <= R) {
if (find(R) == R) {
father[R] = find(L - 1);
R--;
} else
R = father[R];
}
}
return 1;
}
int main() {
while (~scanf("%d%d", &n, &q)) {
for (int i = 1; i <= q; i++)
scanf("%d%d%d", &a[i].l, &a[i].r, &a[i].num);
int l = 1, r = q, ans = 0;
while (l <= r) {
int mid = (l + r) / 2;
if (check(mid))
l = mid + 1;
else {
ans = mid;
r = mid - 1;
}
}
printf("%d
", ans);
}
return 0;
} Problem F Telephone Lines
제목 링크:https://ac.nowcoder.com/acm/contest/1069/F/
제목: p 개의 케이블 이 있 는데 그 목적 은 최소 비용 케이블 을 만들어 서 1 이 n 에 도착 할 수 있 도록 하 는 것 이다.그리고 공식 적 으로 당신 에 게 K 개의 케이블 을 제공 합 니 다. (무료 로 k 개의 변 을 만 들 라 고 합 니 다) 나머지 케이블 은 우리 가 직접 돈 을 내 고 우리 에 게 돈 중 에 가장 비 싼 케이블 이 가장 작은 것 이 얼마 인지 물 습 니 다.사고: 2 분 mid, 매번 1 에서 N 까지 의 경로 에서 K + 1 의 변 권 을 mid 보다 작 게 할 수 있 는 지 판단 합 니 다.그러면 업그레이드 가격 이 mid 보다 큰 변 권 치 를 1 로 부여 하고 나머지 권 치 는 0 으로 부여 하 며 최 단 로 를 달 려 dis [n] 와 K 를 비교 해 야 한다. 만약 에 K 보다 작 으 면 이 답 이 가능 하 다 는 것 을 설명 하고 r 를 계속 2 점 으로 축소 하지 않 으 면 l 을 축소 할 수 있다.
Accepted Code:
#include
using namespace std;
const int inf = 0x3f3f3f3f;
int n, p, k, cnt, tot;
int f[1005], dis[1005], s[100005];
bool vis[1005];
struct edge {
int u, v, s, nx;
} e[100005];
void Add(int x, int y) {
e[++cnt].u = x;
e[cnt].v = y;
e[cnt].nx = f[x];
f[x] = cnt;
}
void Spfa() {
for (int i = 1; i <= n; i++)
dis[i] = inf, vis[i] = 0;
vis[1] = 1, dis[1] = 0;
queue Q;
Q.push(1);
while (!Q.empty()) {
int x = Q.front();
Q.pop();
vis[x] = 0;
for (int i = f[x]; i; i = e[i].nx) {
int y = e[i].v, z = e[i].s;
if (dis[y] > dis[x] + z) {
dis[y] = dis[x] + z;
if (!vis[y]) {
vis[y] = 1;
Q.push(y);
}
}
}
}
}
int main() {
int u, v, w;
scanf("%d%d%d", &n, &p, &k);
for (int i = 1; i <= p; i++) {
scanf("%d%d%d", &u, &v, &w);
s[++tot] = w;
s[++tot] = w;
Add(u, v);
Add(v, u);
}
int ans = -1;
int l = 0, r = 1000000;
while (l <= r) {
int mid = (l + r) >> 1;
for (int i = 1; i <= cnt; i++) {
if (s[i] <= mid)
e[i].s = 0;
else e[i].s = 1;
}
Spfa();
if (dis[n] <= k) {
ans = mid;
r = mid - 1;
} else l = mid + 1;
}
printf("%d
", ans);
return 0;
} Problem G Election Time
제목 링크:https://ac.nowcoder.com/acm/contest/1069/G/
제목: n 마리 소 는 대통령 선거 에 출마 하여 2 차 투 표를 하고 1 차 는 K 위 권 으로 2 차 투 표를 하여 최고 자 를 대통령 으로 선출한다.사고: 구조 체 배열 에 대해 표 수 를 큰 것 에서 작은 것 으로 정렬 하고 앞의 k 항목 을 선택 한 다음 에 이 k 개의 정렬 을 하고 가장 큰 것 을 선택한다.
Accepted Code:
#include
using namespace std;
const int MAXN = 50005;
typedef long long ll;
struct edge {
ll first,second;
int id;
}s[MAXN];
bool cmp1(const edge &x, const edge &y){
return x.first > y.first;
}
bool cmp2(const edge &x, const edge &y){
return x.second > y.second;
}
int main() {
int n, k, ans;
scanf("%d%d", &n, &k);
for (int i = 0; i < n; i++){
scanf("%lld%lld", &s[i].first, &s[i].second);
s[i].id = i + 1;
}
sort(s, s + n, cmp1);
sort(s, s + k, cmp2);
printf("%d
", s[0].id);
return 0;
} Problem H Costume Party
제목 링크:https://ac.nowcoder.com/acm/contest/1069/H/
제목: 한 조 의 배열 n 이 있 는데 이 n 개의 두 조합 이 얼마나 많은 쌍 과 (ai + aj) 가 M 보다 작 거나 같은 조합 을 맞 출 수 있 는 지 요구 합 니 다.사고: 먼저 순 서 를 매 긴 다음 에 직접 폭력 을 행사 합 니 다.
Accepted Code:
#include
using namespace std;
const int MAXN = 20005;
typedef long long ll;
int p[MAXN];
int main() {
int n, m, ans = 0;
scanf("%d%d", &n, &m);
for (int i = 0; i < n; i++)
scanf("%d", &p[i]);
sort(p, p + n);
for (int i = 0; i < n - 1; i++) {
for (int j = i + 1; j < n; j++) {
if (p[i] + p[j] <= m)
ans++;
else break;
}
}
printf("%d
", ans);
return 0;
} Problem I Cantor 시계
제목 링크:https://ac.nowcoder.com/acm/contest/1069/I/
제목: 표 의 데이터 에 따라 N 항 을 구하 세 요.사고방식: 바로 잡 고 규칙 을 찾 아 라.
Accepted Code:
#include
using namespace std;
const int MAXN = 100;
int main() {
int n, i, ans;
scanf("%d", &n);
for (i = 1; i * (i + 1) / 2 < n; i++);
ans = n - i * (i - 1) / 2;
if (i & 1)
printf("%d/%d
", i - ans + 1, ans);
else printf("%d/%d
", ans, i - ans + 1);
return 0;
} Problem J Running
제목 링크:https://ac.nowcoder.com/acm/contest/1069/J/
제목: Bessie 는 스포츠 소 가 되 고 싶 습 니 다. 분당 달 리 는 거 리 는 Di 입 니 다. 처음에 피로 도 는 0 이 고 1 분 을 달 릴 때마다 1 피로 도 를 증가 하지만 피로 도 는 M 을 초과 해 서 는 안 됩 니 다.휴식 을 선택 할 때 피로 도 는 분당 1 씩 줄 어 들 지만 피로 도가 0 일 때 까지 쉬어 야 계속 뛸 수 있다.N 분 이 지나 면 피로 도 는 0 이 어야 한다. 그렇지 않 으 면 생활 을 유지 할 충분 한 에너지 가 없다.Bessie 가 달 릴 수 있 는 가장 먼 거 리 를 구하 세 요.사고: dp [i] [j] 를 i 분 의 피로 도가 j 일 때 달 릴 수 있 는 가장 먼 거리 로 정의 한다. 만약 에 i 분 의 피로 도가 j 가 0 이 아니라면 지난 분 에 달리 기 를 하고 있다 는 것 을 의미한다. 그래서 dp [i] [j] = dp [i - 1] + a [i]; 만약 에 i 분 의 피로 도가 0 이 라면 지난 1 분 의 피로 도 는 0 이거 나 j 분 동안 쉬 었 기 때문에 다음 과 같은 상태 로 방정식 을 옮 길 수 있다. dp [i] [0] = max (dp [1] [0], dp [i - j] [j]) dp[i][j]=dp[i-1][j-1]+a[i];
Accepted Code:
#include
using namespace std;
const int MAXN = 10005;
typedef long long ll;
int dp[MAXN][505], a[MAXN];
int main() {
int n, m;
scanf("%d %d", &n, &m);
for (int i = 1; i <= n; i++)
scanf("%d", &a[i]);
memset(dp, 0, sizeof(dp));
for (int i = 1; i <= n; i++) {
dp[i][0] = dp[i - 1][0];
for (int j = 1; j <= m; j++) {
if (j < i)
dp[i][0] = max(dp[i][0], dp[i - j][j]);
dp[i][j] = dp[i - 1][j - 1] + a[i];
}
}
printf("%d
", dp[n][0]);
return 0;
} Problem K Cow Contest
제목 링크:https://ac.nowcoder.com/acm/contest/1069/K/
제목: M 라운드 쌍 우 경기 결 과 를 제시 하여 결과 에서 등급 을 정확하게 정할 수 있 는 젖소 의 수 를 확정 합 니 다.i 가 j 에 도착 할 수 있 는 지, 즉 처음에 i 가 j 에 도착 할 수 있 는 지, 아니면 i 가 k 에 도착 할 수 있 는 지, k 가 j 에 도착 할 수 있 는 지 를 나타 낸다. 그러면 i 가 j 를 이 길 수 있 는 지 를 나타 낸다. floyed 로 모든 점 과 개의 관 계 를 구하 고 이 점 과 다른 n - 1 개의 점 의 관계 가 확정 되면 그의 순 위 를 확정 할 수 있다.
Accepted Code:
#include
using namespace std;
int f[105][105];
int main() {
int n, m, a, b, ans = 0;
scanf("%d%d", &n, &m);
for (int i = 1; i <= m; i++) {
scanf("%d%d", &a, &b);
f[a][b] = 1;
}
for (int k = 1; k <= n; k++)
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
f[i][j] |= f[i][k] & f[k][j];
for (int i = 1; i <= n; i++) {
int res = 1;
for (int j = 1; j <= n; j++)
if (i != j)
res &= f[i][j] | f[j][i];
ans += res;
}
printf("%d
", ans);
return 0;
} Problem L 차방
제목 링크:https://ac.nowcoder.com/acm/contest/1069/L/
제목: n 을 2 의 멱 차방 으로 바 꿉 니 다.
Accepted Code:
#include
using namespace std;
void f(int n) {
int i;
for (i = 20; i >= 0; i--)
if (n & (1 << i))
break;
printf("2");
if (i <= 2 && i != 1)
printf("(%d)", i);
if (i > 2) {
printf("(");
f(i);
printf(")");
}
if (n & ~(1 << i)) {
int temp = n & ~(1 << i);
printf("+");
f(temp);
}
return;
}
int main() {
int n;
scanf("%d", &n);
f(n);
return 0;
} 이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
Rails Turbolinks를 페이지 단위로 비활성화하는 방법원래 Turobolinks란? Turbolinks는 링크를 생성하는 요소인 a 요소의 클릭을 후크로 하고, 이동한 페이지를 Ajax에서 가져옵니다. 그 후, 취득 페이지의 데이터가 천이 전의 페이지와 동일한 것이 있...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
