美团

1.

 

n=int(input().strip()) res = 1 cnt = 0 a = list(range(n+1)) for i in range(5,n+1,5): while a[i]%5==0: a[i]//=5 cnt+=1 i = 2 while i//2<=cnt: a[i]//=2 i+=2 for i in range(2,n+1): res*=a[i] while res==0: res//=10 res%=10 print(res)

2.

 

n=int(input().strip()) t = 1 for i in range(1,n+1): t*=i t%=(10**6+3) print(t)

3.

此法样例过不了，但是可以过73%，dfs

#include <algorithm> #include <iostream> #include <vector> using namespace std; void dfs(vector<vector<int>>& graph,vector<bool>& vis, int n,int pos,int end) { if (vis[pos] == true) return; if (pos == end) { vis[end] = true; return; } vis[pos] = true; for (int i = 1; i <= n; ++i) { if (graph[pos][i] == 1 && vis[i] == false) dfs(graph, vis, n, i, end); } } int main() { int n, m; cin >> n >> m; vector<vector<int>> graph(n + 1, vector<int>(n + 1, 0)); int u, v; for (int i = 0; i < m; ++i) { cin >> u >> v; graph[u][v] = 1; graph[v][u] = 1; } int s, t; cin >> s >> t; vector<bool> vis(n + 1, false); dfs(graph, vis, n, s, t); for (int i = 1; i <= n; ++i) { if (!vis[i]) cout << i << " "; } return 0; }

小马智行

1.

n个数，每连续k个数求截尾平均数，求其中最大的截尾平均数

90%

n,k= map(int, input().strip().split()) arr=list(map(int, input().strip().split())) ans=0 sum1=sum(arr[0:k]) max1=max(arr[0:k]) min1=min(arr[0:k]) mean=(sum1-min1-max1)/(k-2) ans=mean for i in range(n-k): sum1=sum1-arr[i]+arr[i+k] if arr[i]==max1: max1=max(arr[i+1:i+k+1]) if arr[i]==min1: min1=min(arr[i+1:i+k+1]) mean=(sum1-min1-max1)/(k-2) if mean>ans: ans=mean #print(sum1,max1,min1,mean) print(ans)

2.

有 n 个石头从左到右拍成一排，第 i 个石头的颜色为 ci 。现在小 Ho 在第一个石头，他想跳到第 n 个石头，每一步有两种跳跃方式：

1. 从第 i 个石头跳到第 i+1 个石头

2. 跳到右边第一个和当前石头颜色相同的石头（如果存在的话）

现在他想知道，从第一个石头跳到第 n 个石头至少需要几步跳跃

输入 第一行一个正整数 n

第二行 n 个正整数，表示ci

1 ≤ n, ci ≤ 2 × 105

输出 输出至少需要几步跳跃

样例输入 6 1 2 1 3 4 2样例输出 2

#include<iostream> #include<cstdio> #include<algorithm> #include<cstring> using namespace std; int n; int c[200010];//输入数组 int vis[200010];//记录数组中每个颜色出现的次数 int dp[200010];//统计每到一步需要走的最少步数 int a[200010];//我的循环从左到右，标记走到当前位置时，前面与之是相同颜色的最右边的位置i int main() { cin>>n; memset(vis,0,sizeof(vis)); for(int i=1;i<=n;i++) { cin>>c[i]; vis[c[i]]++;//统计颜色出现的次数 } memset(dp,0,sizeof(dp)); memset(a,0,sizeof(a)); dp[0]=-1;//很关键的初始化，因为下面的dp中第一个位置到后面位置可能需要用到dp[0] a[c[1]]=1;//第一个元素的位置在1号位 for(int i=2;i<=n;i++) { int k=a[c[i]];//当前元素的位置 if(vis[c[i]]>=2 && dp[k]>=0) dp[i]=min(dp[i-1]+1,dp[k]+1);//满足该种颜色出现两次（含）以上并且标记k不是第一个位置 else dp[i]=dp[i-1]+1; a[c[i]]=i;//更新当前标记 } cout<<dp[n]<<endl; return 0; }

还有两道题，超级复杂的那种