A.Leftbest 题目： 链接：https://ac.nowcoder.com/acm/contest/7830/A 来源：牛客网
Jack is worried about being single for his whole life, so he begins to use a famous dating app. In this app, the user is shown single men/women’s photos one by one, and the user may choose between “yes” and “no”. Choosing “yes” means an invitation while choosing “no” means nothing. The photos would be shown one by one until the number of rest photos to be shown reaches zero. Of course, efficient and single Jack would always choose “yes”.
When viewing photos, Jack would have a “fake impression point” on every photo, which is not accurate. To calculate the “true impression point” of one photo, Jack would recall the “fake impression point” of every previous photo whose “fake impression point” is larger than this photo, and regard the smallest “fake impression point” of them as the “true impression point” of this photo. Jack would like to sum the “true impression point” of all photos as the outcome of his effort.
Note that if such a larger “fake impression point” does not exist, the “true impression point” of this photo is zero.
题意： 给你一行数，对于每个数，找到其左边大于它的最小的数，输出所有这样的数的和。
思路： n的范围是1e5，每次循环遍历的话复杂度过不去。线段树的话好像也可以写，但是我懒得敲了。就直接用set函数将前面读进来的数自动排序，然后直接寻找该数的位置，那下一个位置就是我们要找的数；找到末尾的话就是零。
代码：
#include <cstdio> #include <cstring> #include <stack> #include <queue> #include <map> #include <set> #include <vector> #include <cmath> #include <algorithm> #include<bits/stdc++.h> using namespace std; const double N = 1e6+10; const double pi = acos(-1.0); const int INF = 0x3f3f3f3f; const int MOD = 1000000007; const inline int read(){ int k = 0, f = 1; char c = getchar(); for(;!isdigit(c); c = getchar()) if(c == '-') f = -1; for(;isdigit(c); c = getchar()) k = k * 10 + c - '0'; return k * f; } #define ll long long #define CL(a,b) memset(a,b,sizeof(a)) #define MAXN 400010 set<ll> s; ll n; ll res; int main() { scanf("%lld",&n); set<ll>::iterator it; res = 0; ll k = 0; for(long long int i = 0 ; i < n ; i++) { scanf("%lld",&k); s.insert(k); it = s.find(k); it++; if(it!=s.end()) res = res + *it; } printf("%lld\n",res); return 0; }F.Points 题目： 链接：https://ac.nowcoder.com/acm/contest/7830/F 来源：牛客网
Jack and Rose are playing games after working out so many difficult problems. They together drew a “Haizi” tree to show their collaboration. “Haizi” tree is the same as the tree defined in graph theory.
Now Jack would like to count the number of vertices whose degree is one in this tree. You need to help him with this calculation.
\textit{Degree}Degree: The degree of a vertex of a graph is the number of edges that are connected with the vertex.
题意： 给出一棵树，输出叶子结点的个数。
思路： 直接输出度等于1的点就行了。
代码：
#include <cstdio> #include <cstring> #include <stack> #include <queue> #include <map> #include <set> #include <vector> #include <cmath> #include <algorithm> #include<bits/stdc++.h> using namespace std; const double N = 1e6+10; const double pi = acos(-1.0); const int INF = 0x3f3f3f3f; const int MOD = 1000000007; const inline int read(){ int k = 0, f = 1; char c = getchar(); for(;!isdigit(c); c = getchar()) if(c == '-') f = -1; for(;isdigit(c); c = getchar()) k = k * 10 + c - '0'; return k * f; } #define ll long long #define CL(a,b) memset(a,b,sizeof(a)) #define MAXN 400010 vector<int> G[MAXN]; int n , x , y , res; int main() { std::ios::sync_with_stdio(false); cin >> n; for(int i = 1 ; i < n ; i++) { cin >> x >> y; G[x].push_back(y); G[y].push_back(x); } res = 0; for(int i = 1 ; i <= n ; i++) { if(G[i].size()==1) { res = res + 1; } } printf("%d\n",res); return 0; }J.Flowers 题目： 链接：https://ac.nowcoder.com/acm/contest/7830/J 来源：牛客网
Recently Jack becomes much more romantic. He would like to prepare several bunches of flowers.
Each bunch of flowers must have exactly M flowers. As Jack does not want to be boring, he hopes that flowers in the same bunch are all different species. Now there are {N}N species of flowers in the flower shop, and the number of the i-th species of flower is a_ia i . Now Jack would like to know how many bunches of flowers he can prepare at most.
\textit{(Flowers are used to propose.)}(Flowers are used to propose.)
题意： 买花，花店有n种花，给出每种花的数量。做成一束花，需要m种不同的花，一种花一朵，问最多可以做成多少束花。
思路： 开始的时候没想到应该怎么做，因为没有一种好的做法能满足复杂度。在想着N和 M的关系的时候，就觉得怎么遍历都会超，那不如就直接枚举结果好了。然后就开始了二分。结果数，最小的情况是M>N的时候，结果数是0，最大的情况是M=1的时候，结果数是所有花的数量。判断好l和r之后就是判断应该区间左移还是区间右移的判定条件。 K是我们枚举的结果数，从头遍历一遍，每种花的数量就是a[i]和K的较小值。因为如果a[i]大于K的话，那对于这种花，最大的利用数量就是每束里都用一朵，所以最大是K朵；小与K的话那就是a[i]朵，num就是我们每次选出来的花的数量的总和。最终K束花所需要的花的数量是KM，而我们选出来的花的数量是num，那么如果num大于KM，就说明结果数选小了，区间右移；反之区间左移。
代码：
#include <cstdio> #include <cstring> #include <stack> #include <queue> #include <map> #include <set> #include <vector> #include <cmath> #include <algorithm> #include<bits/stdc++.h> using namespace std; const double N = 1e6+10; const double pi = acos(-1.0); const int INF = 0x3f3f3f3f; const int MOD = 1000000007; const inline int read(){ int k = 0, f = 1; char c = getchar(); for(;!isdigit(c); c = getchar()) if(c == '-') f = -1; for(;isdigit(c); c = getchar()) k = k * 10 + c - '0'; return k * f; } #define ll long long #define CL(a,b) memset(a,b,sizeof(a)) #define MAXN 300010 ll a[MAXN]; ll b[MAXN]; ll n , m; ll res , num; ll l , r; int main() { int t; scanf("%d",&t); while(t--) { res = 0; scanf("%lld %lld",&n,&m); l = 0; r = 0; for(int i = 1 ; i <= n ; i++) { scanf("%lld",&a[i]); r = r + a[i]; } ll k; for(int j = 1 ; j <= 100 ; j++) { int flag = 0; k = (l+r)>>1; num = 0; for(int i = 1 ; i <= n ; i++) { b[i] = min(a[i],k); num = num + b[i]; } // cout << k*m << " " << num << "********" << endl; if(k*m <= num) { l = k+1; res = k; // cout << k << "*" << endl; } else { r = k-1; // cout << k << "**" << endl; } } printf("%lld\n",res); } return 0; }菜的一批的我就只只只只只只只只做出来三道题，直接挂机四个小时。 下面是补题的情况：
B.First Date 题目： 链接：https://ac.nowcoder.com/acm/contest/7830/B 来源：牛客网
Jack finally meets a girl, and today is their first date. The city they live in consists of n vertices and m bidirectional roads. Each road has a standard time x_ix i to pass through and an influence factor y_iy i . Every day there is a congestion factor a, which is a uniformly distributed random variable between [0,1]. The time needed to pass the i-th road is x_i + a \cdot y_ix i +a⋅y i . Note that x_i + y_ix i +y i is always not less than {0}0.
Jack wants to calculate the \textbf{expected value}expected value of minimum time between his home {S}S and their date place {T}T.
题意： 有n个顶点和m条道路，给你起点和终点的位置，问之间的最小时间期望值。
思路： dijkstra求最短路在计算期望即可。
代码：
#include <cstdio> #include <cstring> #include <stack> #include <queue> #include <map> #include <set> #include <vector> #include <cmath> #include <algorithm> #include<bits/stdc++.h> using namespace std; const double N = 1e6+10; const double pi = acos(-1.0); const int INF = 0x3f3f3f3f; const int MOD = 1000000007; const inline int read(){ int k = 0, f = 1; char c = getchar(); for(;!isdigit(c); c = getchar()) if(c == '-') f = -1; for(;isdigit(c); c = getchar()) k = k * 10 + c - '0'; return k * f; } #define ll long long #define CL(a,b) memset(a,b,sizeof(a)) #define maxn 100010 const double c=1e-4; int n,m,s,t; int head[maxn],mm; struct Edge{ int to,nxt; double c1,c2; }edge[maxn<<1]; double d[maxn]; void add(int x,int y,double c1,double c2){ edge[++mm]={y,head[x],c1,c2}; head[x]=mm; } double dij(double a){ priority_queue<pair<double,int>>q; for(int i=1;i<=n;i++) d[i]=1e15; d[s]=0; q.push({0,s}); while(!q.empty()){ auto now = q.top(); q.pop(); int u=now.second; if(u==t) return d[t]; for(int i=head[u];i;i=edge[i].nxt){ int to=edge[i].to; double c1=edge[i].c1; double c2=edge[i].c2; double w=c1+c2*a; if(d[u]+w<d[to]){ d[to]=d[u]+w; q.push({-d[to],to}); } } } } int main(){ ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); cin>>n>>m>>s>>t; for(int i=1;i<=m;i++){ int x,y; double c1,c2; cin>>x>>y>>c1>>c2; add(x,y,c1,c2); add(y,x,c1,c2); } double ans=0; for(double a=0;a<=1;a+=c){ ans+=dij(a); } cout<<fixed<<setprecision(4)<<ans/10001<<'\n'; }