A题:
一开始想着直接想k + 1往前面移动,然后直接输出,因为这个答案是 使得它最大化,那么一种贪心的想法就是直接移动k + 1移动到第一个,这样可以保证k + 2的答案是最优的,但是样例2就给了我一巴掌,这样是不行的,可能移动后面产生价值更好,所以我们需要从[k + 1,n]枚举往前面移动,但是n = 1e5 只能用o(n)的时间复杂度。注意到每次只会移动一段长度为k的序列,那么我们可以先统计出来i*a[i] = tot的和,然后因为那一段长度为k向后面移动1位实际上是对他们的和加大一倍,我们可以用前缀和直接计算这段区间和,然后tot + sum[i - 1] - sum[i - k - 1],就可以计算将那段区间向前面移动一位的值,然后因为i * a[i]被覆盖了所以需要剪掉,然后a[i]放到i - k的位置产生的价值就是a[i] * (i - k),然后不断更新答案即可。
这个题目的难点就是这个:tot - i * a[i] + sum[i - 1] - sum[i - 1 - k] + a[i] * (i - k)
代码:
#include<bits/stdc++.h> using namespace std; const int maxn = 1e5 + 10; typedef long long int ll; ll a[maxn]; ll sum[maxn]; void solved(){ int t;cin>>t; while(t--){ ll n,k;cin>>n>>k; ll tot = 0; for(int i = 1; i <= n; i++){ scanf("%lld",&a[i]); sum[i] = sum[i - 1] + a[i]; tot += a[i] * i; } ll ans = -1e9 + 10; for(int i = k + 1; i <= n; i++){ ans = max(ans,tot - i * a[i] + sum[i - 1] - sum[i - 1 - k] + a[i] * (i - k)); } cout<<ans<<endl; } } int main(){ solved(); return 0; }
B:
直接计算每个人超越n个人时间和 / n即可
每个人超越n个人时间和
代码:
#include<bits/stdc++.h> using namespace std; const int maxn = 1e4 + 10; //u:两两相隔距离 //v:每个人的匀速 double c[maxn],d[maxn]; void solved(){ int n;cin>>n; double v,u;cin>>v>>u; for(int i = 1; i <= n; i++)cin>>c[i],c[i]-=v; for(int i = 1; i <= n; i++)cin>>d[i]; double time = 0; for(int i = 1; i <= n; i++){ for(int j = 1; j <= n; j++){ time += n * u / (c[i] - (j - 1) *d[i]); } } printf("%.3lf\n",time / n); } int main(){ solved(); return 0; }
E:
这题我用bfs写的,之前在abc写过类似的。
先bfs出所有由4,7组成的数字,然后求和即可。
一开始是打算存在vector,然后遍历[l,r]求和但是超时了,然后注意到其实在bfs的时后就可以计算答案了,就是不断的维护左端点。然后用乘法去乘就行了,这样几次就能求出答案了。。。具体看代码把,if是关键。
代码:
#include<bits/stdc++.h> using namespace std; typedef long long int ll; const int maxn = 1e8; int a[maxn]; void solved(){ queue<ll>st; st.push(4); st.push(7); vector<ll>ve; ll l,r;cin>>l>>r; ll ans = 0; while(!st.empty()){ ll cur = st.front();st.pop(); ve.push_back(cur); if(cur >= l){ if(r >= cur) ans += (cur - l + 1) * cur; else { ans += (r - l + 1) * cur;break; } l = cur + 1; } if(l > r)break; if(cur > 1e9 +10)break; st.push(cur * 10 + 4); st.push(cur * 10 + 7); } cout<<ans<<endl; } int main(){ solved(); return 0; }
C:a:何老师,b:sk同学,c:小c同学
如果 dis(a,1) < dis(b,c) + dis(c,1) 这样肯定可以输出yes即可
如果 dis(a,1) == dis(b,c) + dis(c,1)这个时候需要判断一下a,c是否lca是根节点的一个儿子,如果是,则a老师显然只需要花费dis(a,lca(a,c))的时间,并不需要再往上面走了,就是它可以在lca等同学,这个时候输出YES,如果lca(a,c) = 1则老师始终慢同学一步,输出no即可
如果dis(a,1) > dis(b,c) + dis(c,1)输出no
这是第一次写lca也是第一次学lca,感觉lca可以处理树上的两个节点最短距离。
代码:
#include<cstdio> #include<algorithm> #include<cstring> using namespace std; const int maxn = 1e6 + 100; struct edge{ int v,next; edge(){} edge(int a,int b):v(a),next(b){} }e[maxn << 1]; int head[maxn],tot; int dep[maxn],f[maxn][25]; void add(int u,int v){ e[++tot].v = v; e[tot].next = head[u]; head[u] = tot; } void dfs(int v,int fa){ dep[v] = dep[fa] + 1; for(int i = 1; (1 << i) <= dep[v] ;i ++){ f[v][i] = f[f[v][i - 1]][i - 1]; } for(int i = head[v];i;i = e[i].next){ if(e[i].v != fa){ f[e[i].v][0] = v; dfs(e[i].v,v); } } } int lca(int x,int y){ if(dep[x] < dep[y])swap(x,y); for(int i = 20; i >= 0; i--){ if(dep[f[x][i]] >= dep[y]) x = f[x][i]; if(x == y)return x; } for(int i = 20; i >= 0; i--){ if(f[x][i] != f[y][i]){ x = f[x][i]; y = f[y][i]; } } return f[x][0]; } void solved(){ int t;scanf("%d",&t); while(t--){ memset(head,0,sizeof(head)); memset(dep,0,sizeof(dep)); memset(f,0,sizeof(f)); int n,q;scanf("%d%d",&n,&q); for(int i = 1; i < n; i++){ int u,v;scanf("%d%d",&u,&v); add(u,v);add(v,u); } dfs(1,0); while(q--){ int a,b,c;scanf("%d%d%d",&a,&b,&c); int la = dep[a] - dep[1]; int LCA = lca(b,c); int b_c = dep[b] - dep[LCA] + dep[c] - dep[LCA]; int ld = b_c + dep[c] - dep[1]; if(la < ld)printf("YES\n"); else if(la == ld){ if(lca(a,c) == 1){//不在同一棵子树上,老师总是慢学生一步 printf("NO\n"); }else printf("YES\n");//在同一子树上,虽然距离相同,但是但是可以先到lca等同学就行了 }else printf("NO\n"); } } } int main(){ solved(); return 0; }