Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|
Nộp bài Các bài nộp Làm tốt nhất PDF Về danh sách bài

NGHICHTHE2 - Dãy nghịch thế 2

 

Giải bài toán ngược của bài "dãy nghịch thế 1" : biết mảng (p1, ..., pn) hãy tìm hoán vị (x1,x2,...,xn).
Input:


+Dòng đầu ghi n (n≤100)


+Các dòng tiếp theo ghi p1, p2, ..., pn
Output:


Ghi n số x1, x2, ..., xn­.
ví dụ
input


6
0 1 0 3 4 1
output

4 3 6 2 1 5   
Submit solution!
Được gửi lên bởi:Vương Trung Hiếu Nghĩa
Ngày:2015-10-03
Thời gian chạy:1s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:C++ 4.3.2 CPP CPP14
hide comments
2023-06-13 09:38:39
Input

2
7 7
1 2 7 5
1111111
0000011
1011001
1011100
1011110
1000000
1111111
7 7
1 2 7 6
1111111
0000001
1011000
1011100
1011110
1000000
1111111


Output

3

2

Last edit: 2023-06-19 09:45:12
2023-06-13 03:29:08
#include<bits/stdc++.h>
using namespace std;

struct canh
{
int dau,cuoi;
int trongso;
};
long long ntest,m,i,u,c,v;
long long d[101],dem=0,dad[101];
canh CA[10001];
long long chiphi=0;

int FindDad(int u)
{
if(dad[u]==-1)
{
dad[u]=u;return u;
}
else return dad[u];
}

void Add(int u,int v)
{
if(u>v)
for(int i=1;i<=m;i++)
{
if(dad[i]==u)
dad[i]=v;
}
else if(v>u)
for(int i=1;i<=m;i++)
{
if(dad[i]==v)
dad[i]=u;
}
}
void QUICK_SORT(canh CA[],int left,int right)
{
if(left==right)
return;
if(left<right)
{
int k=(left+right)/2;
int i=left,j=right;
while(i<=j)
{
while(CA[i].trongso<CA[k].trongso) i++;
while(CA[j].trongso>CA[k].trongso) j--;
if(i<=j)
{
canh g=CA[i];
CA[i]=CA[j];
CA[j]=g;
i++,j--;
}
}
QUICK_SORT(CA,left,j);
QUICK_SORT(CA,i,right);
}
}


void quickSort(canh CA[], int l, int r)
{
if(l<r){

int key = CA[(l+r)/2].trongso;
int i = l, j = r;
while(i <= j)
{
while(CA[i].trongso < key) i++;
while(CA[j].trongso > key) j--;
if(i <= j)
{
if (i < j)
{
canh g=CA[i];
CA[i]=CA[j];
CA[j]=g;
}
i++;
j--;
}
}
quickSort(CA, l, j);
quickSort(CA, i, r);
}
}

void Selec(canh CA[],int n)
{
for(int i=1;i<=n-1;i++)
for(int j=i+1;j<=n;j++)
if(CA[i].trongso>CA[j].trongso)
{
canh g=CA[i];
CA[i]=CA[j];
CA[j]=g;
}
}
void process()
{
//QUICK_SORT(CA,1,dem);
//Selec(CA,dem);
quickSort(CA,1,dem);
int demcanh=0,demdinh=0;
int i1=dem,x,y;
while(demcanh<m-1&&demdinh<m)
{
x=FindDad(CA[i1].dau);
if(x==-1) demdinh++;
y=FindDad(CA[i1].cuoi);
if(y==-1) demdinh++;
if(x!=y)
{
Add(x,y);demcanh++;
chiphi-=CA[i1].trongso;
}
//cout <<CA[i1].dau<<" "<<CA[i1].cuoi<<" "<<CA[i1].trongso<<endl;
i1--;
}
}
int main()
{
//freopen("input.txt.txt","r",stdin);
ios::sync_with_stdio(false);
cin>>ntest;
for(int j=1;j<=ntest;j++)
{
cin >>m;chiphi=0,dem=0;
for(int jj=1;jj<=m;jj++)
{
cin >>i>>u>>c;
d[i]=u,dad[i]=-1;
for(int j1=1;j1<=c;j1++)
{
cin >>v;
if(i>v)
{
CA[++dem].dau=i; CA[dem].cuoi=v;
CA[dem].trongso=d[i]+d[v];
chiphi+=CA[dem].trongso;
}
}
}
process();
//for(int i=1;i<=dem;i++)
// cout <<CA[i].dau<<" "<<CA[i].cuoi<<" "<<CA[i].trongso<<endl;
cout <<chiphi<<endl;

}
}
2023-06-12 11:38:53
import java.util.Scanner;

class Main {
static class Edge {
int start, end;
int weight;

Edge(int start, int end, int weight) {
this.start = start;
this.end = end;
this.weight = weight;
}
}

static Edge[] edges;
static int[] dad;
static int[] d;
static int numTests;

public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
numTests = scanner.nextInt();

for (int t = 0; t < numTests; t++) {
int m = scanner.nextInt();
dad = new int[m + 1];
d = new int[m + 1];
edges = new Edge[m * (m - 1) / 2 + 1];
int edgeCount = 0;
int totalCost = 0;

for (int i = 0; i <= m; i++) {
dad[i] = -1;
d[i] = 0;
}

for (int i = 1; i <= m; i++) {
d[i] = scanner.nextInt();
int u = scanner.nextInt();
int c = scanner.nextInt();

for (int j = 1; j <= c; j++) {
int v = scanner.nextInt();
if (i > v) {
edges[++edgeCount] = new Edge(i, v, d[i] + d[v]);
totalCost += d[i] + d[v];
}
}
}

quickSort(edges, 1, edgeCount);

int edgeCount1 = edgeCount;
int nodeCount = 0;
int i1 = edgeCount1;

while (edgeCount < m - 1 && nodeCount < m) {
int x = findDad(edges[i1].start);
if (x == -1) nodeCount++;
int y = findDad(edges[i1].end);
if (y == -1) nodeCount++;

if (x != y) {
add(x, y);
edgeCount++;
totalCost -= edges[i1].weight;
}

i1--;
}

System.out.println(totalCost);
}

scanner.close();
}

static int findDad(int u) {
if (dad[u] == -1) {
dad[u] = u;
return u;
} else {
return dad[u];
}
}

static void add(int u, int v) {
if (u > v) {
for (int i = 1; i < dad.length; i++) {
if (dad[i] == u) {
dad[i] = v;
}
}
} else if (v > u) {
for (int i = 1; i < dad.length; i++) {
if (dad[i] == v) {
dad[i] = u;
}
}
}
}

static void quickSort(Edge[] arr, int left, int right) {
if (left < right) {
int pivotIndex = partition(arr, left, right);
quickSort(arr, left, pivotIndex - 1);
quickSort(arr, pivotIndex + 1, right);
}
}

static int partition(Edge[] arr, int left, int right) {
int pivot = arr[right].weight;
int i = left - 1;

for (int j = left; j <= right - 1; j++) {
if (arr[j].weight < pivot) {
i++;
swap(arr, i, j);
}
}

swap(arr, i + 1, right);
return i + 1;
}

static void swap(Edge[] arr, int i, int j) {
Edge temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
2023-06-12 11:04:20
import java.util.*;

class Vertex {
int id;
int score;
int[] neighbors;

public Vertex(int id, int score, int[] neighbors) {
this.id = id;
this.score = score;
this.neighbors = neighbors;
}
}

class Main {
private static int minScore;
private static Vertex[] graph;

public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int testCases = Integer.parseInt(scanner.nextLine());

for (int t = 0; t < testCases; t++) {
int verticesCount = Integer.parseInt(scanner.nextLine());
graph = new Vertex[verticesCount + 1];

for (int i = 0; i < verticesCount; i++) {
String[] vertexInfo = scanner.nextLine().split(" ");
int vertexId = Integer.parseInt(vertexInfo[0]);
int vertexScore = Integer.parseInt(vertexInfo[1]);
int neighborsCount = Integer.parseInt(vertexInfo[2]);

int[] neighbors = new int[neighborsCount];
String[] neighborsInfo = scanner.nextLine().split(" ");
for (int j = 0; j < neighborsCount; j++) {
neighbors[j] = Integer.parseInt(neighborsInfo[j]);
}

graph[vertexId] = new Vertex(vertexId, vertexScore, neighbors);
}

minScore = Integer.MAX_VALUE;
for (int i = 1; i <= verticesCount; i++) {
boolean[] visited = new boolean[verticesCount + 1];
dfs(i, i, visited, 0);
}

System.out.println(minScore);
}

scanner.close();
}

private static void dfs(int startVertex, int currentVertex, boolean[] visited, int currentScore) {
visited[currentVertex] = true;

for (int neighbor : graph[currentVertex].neighbors) {
if (!visited[neighbor]) {
dfs(startVertex, neighbor, visited, currentScore + graph[currentVertex].score);
} else if (neighbor == startVertex) {
minScore = Math.min(minScore, currentScore + graph[currentVertex].score);
}
}

visited[currentVertex] = false;
}
}
2023-06-12 10:41:28
import java.util.*;

class Main {
private static int minScore;

public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int testCases = Integer.parseInt(scanner.nextLine());

for (int t = 0; t < testCases; t++) {
int verticesCount = Integer.parseInt(scanner.nextLine());
Vertex[] vertices = new Vertex[verticesCount + 1];

for (int i = 1; i <= verticesCount; i++) {
String[] vertexInfo = scanner.nextLine().split(" ");
int vertexId = Integer.parseInt(vertexInfo[0]);
int vertexScore = Integer.parseInt(vertexInfo[1]);
int neighborsCount = Integer.parseInt(vertexInfo[2]);

int[] neighbors = new int[neighborsCount];
String[] neighborsInfo = scanner.nextLine().split(" ");
for (int j = 0; j < neighborsCount; j++) {
neighbors[j] = Integer.parseInt(neighborsInfo[j]);
}

vertices[vertexId] = new Vertex(vertexId, vertexScore, neighbors);
}

minScore = Integer.MAX_VALUE;
for (int i = 1; i <= verticesCount; i++) {
boolean[] visited = new boolean[verticesCount + 1];
dfs(i, i, vertices, visited, 0);
}

System.out.println(minScore);
}

scanner.close();
}

private static void dfs(int startVertex, int currentVertex, Vertex[] vertices, boolean[] visited, int currentScore) {
visited[currentVertex] = true;

for (int neighbor : vertices[currentVertex].neighbors) {
if (!visited[neighbor]) {
dfs(startVertex, neighbor, vertices, visited, currentScore + vertices[currentVertex].score);
} else if (neighbor == startVertex) {
minScore = Math.min(minScore, currentScore + vertices[currentVertex].score);
}
}

visited[currentVertex] = false;
}
}

class Vertex {
int id;
int score;
int[] neighbors;

public Vertex(int id, int score, int[] neighbors) {
this.id = id;
this.score = score;
this.neighbors = neighbors;
}
}
2021-08-13 10:29:25
.
2020-10-05 15:33:14
Có ai có thể cho em gợi ý về bài này được không ạ?
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.