9.6 腾讯-技术研究类和数据分析
全A。感觉今天难度倒排
1. 山谷序列，前n个严格递减，后n个严格递增，中间两个数相同，问最长长度。
#include <bits/stdc++.h>
using namespace std;
#define MAXN 10005
#define inf 0x3f3f3f3f
int n, m, T;
int ans;
int a[MAXN], b[MAXN];
int aa[MAXN], bb[MAXN];
int left(int r){
int c[MAXN];
int len=0;
memset(c,inf,sizeof(c));
for( int i = 1; i <= r; i++){
int k = lower_bound(c+1, c+r+1, aa[i])-c;
c[k] = aa[i];
len = max( len, k );
}
return len;
}
int right(int r){
int c[MAXN];
int len=0;
memset(c,inf,sizeof(c));
for( int i = 1; i <= r; i++){
int k = lower_bound(c+1, c+r+1, bb[i])-c;
c[k] = bb[i];
len = max( len, k );
}
return len;
}
int main()
{
scanf("%d", &T);
while(T--){
scanf("%d", &n);
for(int i = 1 ; i <= n ; i++){
scanf("%d", &a[i]);
a[i] *= -1;
b[n-i+1] = a[i];
}
ans = 0;
for(int i = 1 ; i < n ; i++){
for(int j = i+1 ; j <= n ; j++){
if(a[i] != a[j]) continue;
for(int k = 1 ; k <= n ; k++){
aa[k] = a[k];
bb[k] = b[k];
if(aa[k] > a[i]) aa[k] = a[i];
if(bb[k] > a[i]) bb[k] = a[i];
}
int l = left(i);
int r = right(n-j+1);
ans = max(ans, 2 * min(l, r));
}
}
printf("%d\n", ans);
}
return 0;
} 2.模拟解方程
#include <bits/stdc++.h>
using namespace std;
int n, m;
int a[10];
double eps = 0.0005;
double f(double x){
double t = x;
double ans = a[n];
for(int i = n-1 ; i >= 0 ; i--){
ans += t * a[i];
t *= x;
}
return ans;
}
int main()
{
scanf("%d", &n);
for(int i = 0 ; i <= n ; i++){
scanf("%d", &a[i]);
}
vector<double> ans;
for(double i = -5000 ; i < 5000 ; i += eps){
double p = f(i);
if( fabs(p) < 1e-8){
ans.push_back(i);
continue;
}
double q = f(i + eps);
if(p * q <= 0)
ans.push_back(i + eps/2);
}
if(ans.size() == 0)
printf("No\n");
else{
for(int i = 0 ; i < ans.size() ; i++)
printf("%.2f ", ans[i]);
printf("\n");
}
return 0;
} 3.概率题：长度L，如果超过d，随机折断，扔掉左边。对右边继续操作。问操作次数期望。
#include <bits/stdc++.h>
using namespace std;
int n, m;
double ans;
int main()
{
scanf("%d %d", &n, &m);
if(n <= m)
ans = 0;
else{
ans = log(n) - log(m) + 1;
}
printf("%.4f\n", ans);
return 0;
} 4. 排序
#include <bits/stdc++.h>
using namespace std;
int n, m;
int ans;
struct Node{
vector<int> nums;
Node(){}
bool operator < (const Node a) const{
for(int i = 0 ; i < 6 ; i++){
if(nums[i] == a.nums[i]) continue;
return nums[i] < a.nums[i];
}
return true;
}
}a[100005];
int main()
{
int T;
scanf("%d", &T);
while(T--){
scanf("%d", &n);
for(int i = 0 ; i < n ; i++){
a[i].nums.resize(6);
for(int j = 0 ; j < 6 ; j++){
scanf("%d", &a[i].nums[j]);
}
sort(a[i].nums.begin(), a[i].nums.end());
}
sort(a, a+n);
bool flag = false;
for(int i = 0 ; i < n-1 ; i++){
bool f = true;
for(int j = 0 ; j < 6 ; j++){
if(a[i].nums[j] != a[i+1].nums[j]){
f = false;
break;
}
}
if(f){
flag = true;
break;
}
}
if(flag)
printf("YES\n");
else
printf("NO\n");
}
return 0;
} 5. 单源最短路
#include <bits/stdc++.h>
using namespace std;
#define MAXN 2005
#define inf 0x3f3f3f3f
int n, m, T;
int ans;
struct edge{
int to,cost;
};
typedef pair<int,int> P; //first是最短距离，second是顶点的编号
vector<edge> G[MAXN];
int d[MAXN];
void dijkstra(int s){
priority_queue<P,vector<P>,greater<P> > que;
fill(d,d+n,inf);
d[s] = 0;
que.push(P(0,s));
while(!que.empty()){
P p = que.top();que.pop();
int v = p.second;
if(d[v] < p.first) continue;
for(int i = 0 ; i <G[v].size() ; i++){
edge e = G[v][i];
if(d[e.to] > d[v] + e.cost){
d[e.to] = d[v] + e.cost;
que.push(P(d[e.to],e.to));
}
}
}
}
int main()
{
int x, y, w;
scanf("%d %d %d", &n, &m, &T);
for(int i = 0 ; i < n ; i++)
G[i].clear();
for(int i = 0 ; i < m ; i++){
scanf("%d %d %d", &x, &y, &w);
x--;y--;
G[x].push_back(edge{y, w});
}
dijkstra(0);
ans = d[n-1];
dijkstra(n-1);
ans += d[0];
printf("%d\n", ans*T);
return 0;
} 
