비고정 상호 테스트 #0 t3
Case 1 제목
다음 코드의 답안을 제시하고 입력을 구성할 것을 요구합니다.그림, n 개 점 m 줄 q 회 질문, 모든 점 대 사이의 최대 권한 값 최소 경로를 출력합니다.
문제풀이
모든 질문의 출력을 하나의 변으로 보고 가장 작은 생성 나무를 세우세요.
Case 3 문제
출력에, 주어진 코드로 실행된 출력과 주어진 출력이 같도록 구조 입력을 요구합니다.주어진 코드: n회 Dijkstra에서 두 점 사이의 최단로를 구합니다
분석하다.
욕심을 생각해봐.
문제풀이
우선 모든 가장 짧은 질문의 결과를 한 변으로 보고 우리는 이 변들을 정렬한다.각 모서리에 대해 두 점의 현재 거리가 이 모서리의 가중치보다 크면 모서리를 추가하여 모든 점 쌍의 거리를 업데이트합니다.정확성이 뚜렷하다.현재 이렇게 하면 변수가 가장 짧다는 것을 증명한다. 이렇게 얻어진 구조 방안이 A라고 가정하고 또 하나의 구조 방안이 B라고 가정하면 변수가 더욱 적다.그러면 A에는 틀림없이 한 변이 존재하고 B에는 존재하지 않는다.따라서 B에서 이 모서리의 두 끝점 사이의 거리는 A에서 이 모서리의 모서리 권한보다 클 것이다.그렇지 않으면 A에서 이 모서리를 선택하지 않습니다.따라서 B라는 방안은 틀림없이 불법이다. 즉, A는 변수가 가장 적은 구조 방안이다.
#include <bits/stdc++.h>
using namespace std;
namespace one {
const int N=1015, M=1000015;
struct E {
int x, y, w;
}e[M];
int p[N], n, tot, m;
bool cmp(const E &a, const E &b) {
return a.w<b.w;
}
int find(int x) {
return x==p[x]?x:p[x]=find(p[x]);
}
void work() {
scanf("%d%d", &n, &m);
printf("%d %d
", n, m);
int cnt=0;
for(int i=1; i<=n; ++i) {
for(int j=i+1; j<=n; ++j) {
e[cnt].x=i;
e[cnt].y=j;
scanf("%d", &e[cnt].w);
++cnt;
}
}
for(int i=1; i<=n; ++i) {
p[i]=i;
}
sort(e, e+cnt, cmp);
for(int i=0; i<cnt; ++i) {
int x=e[i].x, y=e[i].y, fx=find(x), fy=find(y), w=e[i].w;
if(fx!=fy) {
p[fx]=fy;
++tot;
printf("%d %d %d
", x, y, w);
}
}
for(; tot<=m; ++tot) {
printf("%d %d %d
", 1, 1, 0);
}
}
}
namespace two {
const int mo1=9999991, mo2=3333331;
typedef long long ll;
int ipow(int a, int b, int mo) {
int x=1;
for(; b; b>>=1, a=(ll)a*a%mo) if(b&1) x=(ll)x*a%mo;
return x;
}
void work() {
int n;
scanf("%d", &n);
printf("%d
", n);
for(int i=1; i<=n; ++i) {
static char s[100005];
scanf("%s", s+1);
int now1=0, now2=0, len=strlen(s+1);
for(int i=1; i<=len; ++i) {
now1=(now1*10+s[i]-'0')%mo1;
now2=(now2*10+s[i]-'0')%mo2;
}
for(int x=1; x<=10000; ++x) {
int h1=ipow(x, x, mo1), h2=ipow(x, x, mo2);
if(h1==now1 && h2==now2) {
printf("%d ", x);
break;
}
}
}
}
}
namespace three {
int d[1005][1005];
struct E {
int x, y, w;
}e[1000005];
bool cmp(const E &a, const E &b) {
return a.w<b.w;
}
void work() {
int n, m, cnt=0, tot=0;
scanf("%d%d", &n, &m);
printf("%d %d
", n, m);
for(int i=1; i<=n; ++i) {
for(int j=i+1; j<=n; ++j) {
e[cnt].x=i;
e[cnt].y=j;
scanf("%d", &e[cnt].w);
cnt++;
}
}
memset(d, 0x3f, sizeof d);
for(int i=1; i<=n; ++i) {
d[i][i]=0;
}
sort(e, e+cnt, cmp);
for(int it=0; it<cnt; ++it) {
int x=e[it].x, y=e[it].y, w=e[it].w;
if(w<d[x][y]) {
++tot;
printf("%d %d %d
", x, y, w);
d[x][y]=d[y][x]=w;
for(int i=1; i<=n; ++i) {
for(int j=1; j<=n; ++j) {
d[i][j]=min(d[i][j], min(d[i][x]+d[x][j], d[i][y]+d[y][j]));
}
}
}
}
for(; tot<=m; ++tot) {
printf("%d %d %d
", 1, 1, 1);
}
}
}
namespace four {
const int N=55005;
vector<int> a[N];
void work() {
int n, root;
scanf("%d%d", &n, &root);
printf("%d %d
", n, root);
int csz=0, sz=pow(n, (double)2/3);
for(int i=1; i<=n; ++i) {
int blc;
scanf("%d", &blc);
csz+=a[blc].empty();
a[blc].push_back(i);
}
int j, rt, na;
for(j=0, na=a[csz].size(); j<na; ++j) {
if(a[csz][j]==root) {
swap(a[csz][j], a[csz][0]);
break;
}
}
for(int i=csz; i>=1; --i) {
rt=a[i][0], j=1, na=a[i].size();
for(; j<sz-1 && j<na; ++j) {
printf("%d %d
", a[i][j-1], a[i][j]);
}
if(j<na) {
printf("%d %d
", a[i][j++], root);
}
for(; j<sz*2-1 && j<na; ++j) {
printf("%d %d
", a[i][j-1], a[i][j]);
}
if(j<na) {
printf("%d %d
", a[i][j++], root);
}
for(; j<na; ++j) {
printf("%d %d
", a[i][j-1], a[i][j]);
}
if(root!=rt) {
printf("%d %d
", root, rt);
}
}
}
}
namespace five {
const int N=100015;
struct E {
int l, r, k, w;
}e[N];
bool cmp(const E &a, const E &b) {
if(a.w==-1) {
return 0;
}
if(b.w==-1) {
return 1;
}
return a.w<b.w;
}
int a[N], K[N], vis[N], left, right;
void work() {
int n, t;
scanf("%d%d", &n, &t);
printf("%d %d
", n, t);
left=1;
right=n;
int len=n/t, tot=0;
for(int i=0; i<t; ++i) {
int w;
scanf("%d%d", &K[i], &w);
if(w==-1) {
continue;
}
e[tot].l=i*len+1, e[tot].r=i*len+len;
e[tot].k=len-K[i]+1;
e[tot].w=w;
++tot;
}
sort(e, e+tot, cmp);
for(int i=0; i<tot; ++i) {
int l=e[i].l, k=e[i].k, w=e[i].w;
for(int j=1; j<k; ++j, ++l) {
while(vis[left]) {
++left;
}
a[l]=left;
vis[left]=1;
++left;
}
a[l]=w;
vis[w]=1;
}
for(int i=tot-1; i>=0; --i) {
int r=e[i].r, k=e[i].k;
for(int j=0; j<(len-k); ++j, --r) {
while(vis[right]) {
--right;
}
a[r]=right;
vis[right]=1;
--right;
}
}
for(int i=1; i<=n; ++i) {
if(a[i]) {
continue;
}
while(vis[right]) {
--right;
}
a[i]=right;
--right;
}
for(int i=1; i<=n; ++i) {
printf("%d ", a[i]);
}
for(int i=0; i<t; ++i) {
printf("%d ", K[i]);
}
}
}
int main() {
int C;
scanf("%d", &C);
printf("%d
", C);
if(C<20) one::work();
else if(C<40) two::work();
else if(C<60) three::work();
else if(C<80) four::work();
else five::work();
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSONJSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.