1. 先把不符合要求的去掉,然后按照策略排序,选择前n个,最后再按编号排序,Python代码:
import sys # sys.setrecursionlimit(1000000) m = int(sys.stdin.readline().strip(' ').strip(' ').strip(' ')) arr = [] for _ in range(m): idx,cpuCount,memSize,cpuArch,supportNP = list(map(int,sys.stdin.readline().strip(' ').strip(' ').strip(' ').split(','))) arr.append([idx,cpuCount,memSize,cpuArch,supportNP]) n,strategy,cpuCount,memSize,cpuArch,supportNP = list(map(int,sys.stdin.readline().strip(' ').strip(' ').strip(' ').split(' '))) remaid_arr= [] for i in range(m): if arr[i][1]>= cpuCount and arr[i][2]>=memSize: if (cpuArch==9&nbs***bsp;cpuArch==arr[i][3]) and (supportNP==2&nbs***bsp;supportNP==arr[i][4]): remaid_arr.append(arr[i].copy()) if strategy==1: remaid_arr = sorted(remaid_arr,key=lambda x:[x[1],x[2],x[0]]) else: remaid_arr = sorted(remaid_arr,key=lambda x:[x[2],x[1],x[0]]) remaid_arr = remaid_arr[:n] res = [v[0] for v in remaid_arr] res = sorted(res) t = len(res) res.insert(0,t) print(" ".join(list(map(str,res))))
2. 拓扑排序:
import sys # sys.setrecursionlimit(1000000) m = int(sys.stdin.readline().strip(' ').strip(' ').strip(' ')) n = int(sys.stdin.readline().strip(' ').strip(' ').strip(' ')) z = int(sys.stdin.readline().strip(' ').strip(' ').strip(' ')) arr = [] graph = [[] for _ in range(m+1)] cnt_in = [0]*(m+1) cnt_out = [0]*(m+1) for _ in range(z): i,j = list(map(int,sys.stdin.readline().strip(' ').strip(' ').strip(' ').split(' '))) arr.append([i,j]) cnt_in[j]+=1 cnt_out[i]+=1 graph[i].append(j) length = [-1]*(m+1) for i in range(1,m+1): def dfs(idx): if len(graph[idx])==0: length[idx] =0 return 0 if length[idx]>=0: return length[idx] res = 0 for to in graph[idx]: res = max(res,1+dfs(to)) length[idx] = res return res dfs(i) res = 0 book = [0]*(m+1) book[0]=1 while True: tn = n temp_book = [0]*(m+1) flag = True for _ in range(tn): temp_idx = 0 for i in range(1,m+1): if book[i]==0 and temp_book[i]==0 and cnt_in[i]==0 and (temp_idx==0&nbs***bsp;length[temp_idx]<length[i]): # if book[i]==0 and temp_book[i]==0 and cnt_in[i]==0 and (temp_idx==0&nbs***bsp;cnt_out[temp_idx]<cnt_out[i]): temp_idx =i if temp_idx==0: break flag = False book[temp_idx] = 1 for to in graph[temp_idx]: cnt_in[to]-=1 temp_book[to]=1 if flag: break res+=1 print(res)
3. 求路径,需要保证经过图上所以能到达的点,一次且仅一次。我是暴力做的,Python过不了,但是C++可以😂。
Python代码(AC 60%):
import sys # sys.setrecursionlimit(1000000) m,n = list(map(int,sys.stdin.readline().strip(' ').strip(' ').strip(' ').split(' '))) # n = int(sys.stdin.readline().strip(' ').strip(' ').strip(' ')) # z = int(sys.stdin.readline().strip(' ').strip(' ').strip(' ')) graph = [] line_num = 1 start,end = [], [] for i in range(m): line = list(map(int,sys.stdin.readline().strip(' ').strip(' ').strip(' ').split(' '))) graph.append(line) for j in range(n): v = line[j] if v ==0 : line_num+=1 elif v==1: start = [i,j] elif v==2: end = [i,j] res = [0] nex = [[0,1],[1,0],[0,-1],[-1,0]] book = [[0 for _ in range(n)] for _ in range(m)] def dfs(x,y,temp_line_num,m,n,line_num): if x==end[0] and y ==end[1]: if temp_line_num== line_num: res[0]+=1 return book[x][y] = 1 for k in range(len(nex)): newx,newy = nex[k][0]+x,nex[k][1]+y if 0<=newx<m and 0<=newy<n and book[newx][newy] == 0 and (graph[newx][newy]==1&nbs***bsp;graph[newx][newy]==0&nbs***bsp;graph[newx][newy]==2 ): dfs(newx,newy,temp_line_num+1,m,n,line_num) book[x][y]= 0 dfs(start[0],start[1],0,m,n,line_num) print(res[0])
C++(AC 100%):
#include <iostream> #include <vector> using namespace std; int graph[41][41]; int book[41][41]; int res,sx,sy,ex,ey; int nex[4][2]={{0,1},{1,0},{0,-1},{-1,0}}; void dfs(int x,int y,int temp_line_num,int m ,int n ,int line_num){ if (x==ex and y==ey){ if (temp_line_num == line_num){ res+=1; } return; } book[x][y] = 1; int newx,newy; for (int i = 0; i < 4; ++i) { newx= nex[i][0]+x; newy = nex[i][1]+y; if (0<= newx && newx<m && 0<=newy && newy<n &&book[newx][newy] == 0 && (graph[newx][newy]==1 || graph[newx][newy]==0 || graph[newx][newy]==2)){ dfs(newx,newy,temp_line_num+1,m,n,line_num); } } book[x][y] =0; return; } int main() { int t; int a,b,n,m,line_num=1; cin>>m>>n; for (int i = 0; i <m ; ++i) { for (int j = 0; j <n ; ++j) { cin>>graph[i][j]; if (graph[i][j]==0){ line_num+=1; } else if (graph[i][j]==1){ sx= i; sy = j; } else if (graph[i][j]==2){ ex= i; ey = j; } } } dfs(sx,sy,0,m,n,line_num); cout<<res<<endl; // std::cout << "Hello, World!" << std::endl; return 0; }
全部评论
(4) 回帖