A Maximize The Beautiful Value
题目大意：
给一单调不减序列，问进行一次操作和序列的 最大值是多少？
操作为：选择下标为j的数字使他向前移动大于等于k个位置,显然j>k;
题解:
显然贪心来讲，大的数位置越靠后 越大，所以对于每个数我们肯定贪心的向前移动K个位置，并且数列未操作时已经达到最大值，那么我们只需要枚举一下，每个数往前移动k个位置，使当前的和减小的最少就好了
代码
#pragma GCC optimize(2)
#include<bits/stdc++.h>
#define ls rt<<1
#define rs rt<<1|1
#define pb push_back
#define fi first
#define se second
#define ios ios::sync_with_stdio(0);
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
typedef vector<int> VI;
const int maxn = 2e6 + 6;
const LL inf = 0x3f3f3f3f3f3f3f3f;
const int mod = 998244353;
LL qp(LL x,LL y){LL ans=1;x%=mod;while(y){if(y&1) ans=ans*x%mod;x=x*x%mod;y>>=1;}return ans;}
LL inv(LL x){return qp(x,mod-2);}
//head
LL t,n,k,a[maxn],sum[maxn];
int main(){
scanf("%lld",&t);
while(t--){
scanf("%lld%lld",&n,&k);
for(int i=1;i<=n;i++) scanf("%lld",&a[i]),sum[i]=sum[i-1]+a[i];
LL ans=0,res=inf;
for(int i=1;i<=n;i++){
ans+=1ll*i*a[i];
if(i>k){
res=min(res,1ll*i*a[i]-1ll*(i-k)*a[i]-(sum[i-1]-sum[i-k-1]));
}
//printf("%lld,",res);
}
printf("%lld\n",ans-res);
}
}B 身体训练
题意：
美团外卖的配送员用变速跑的方式进行身体训练。
他们训练的方式是：n个人排成一列跑步，前后两人之间相隔 u 米，每个人正常速度均为 v 米/秒。
当某个配送员排在最后的时候，他需要以当时自己的最高速度往前跑，直到超过排头的人 u 米，然后降回到原始速度 v 米/秒。每个人最初的最高速度为c[i] 米/秒，每轮衰减d[i] 米/秒，也就是说，如果i是第j个跑的，那么他的速度就是c[i]-(j-1)*d[i] 米/秒。
n个人初始以随机的顺序排列，每种顺序的概率完全相等，跑完一轮（每个人都追到排头一次，序列恢复原样）的期望需要的时间是多少？
题解；
考虑先求每个人所贡献的期望，即第i个人在第j个位置的贡献为
所以我们只需要n^2枚举每个人在那个位置的贡献求和后，在除以总人数就可以了
代码
#pragma GCC optimize(2)
#include<bits/stdc++.h>
#define ls rt<<1
#define rs rt<<1|1
#define pb push_back
#define fi first
#define se second
#define ios ios::sync_with_stdio(0);
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
typedef vector<int> VI;
const int maxn = 2e6 + 6;
const LL inf = 0x3f3f3f3f3f3f3f3f;
const int mod = 998244353;
LL qp(LL x,LL y){LL ans=1;x%=mod;while(y){if(y&1) ans=ans*x%mod;x=x*x%mod;y>>=1;}return ans;}
LL inv(LL x){return qp(x,mod-2);}
//head
int n;
double v,u,c[maxn],d[maxn];
int main(){
scanf("%d%lf%lf",&n,&v,&u);
for(int i=1;i<=n;i++){scanf("%lf",&c[i]);}
for(int i=1;i<=n;i++){scanf("%lf",&d[i]);}
double ans=0;
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++) ans+=1.0*u/(c[i]-(j-1)*d[i]-v);
}
printf("%.3f\n",ans);
}
C Borrow Classroom
题目大意:
给一棵树，两个人x,y,q次询问，;
树上相邻两点距离都为1,
在每次询问中，x最开始在b点，然后去c，再去1号节点。y一开始在c点(他要拦截x)。两个人一起走。
问，两人是否能在1号节点之前相遇？
题解：
lca模板题，分别算出x，y到根的距离，看y是否严格小于x。
然后特判一下特殊情况就可以了。具体看代码。
代码
#pragma GCC optimize(2)
#include<bits/stdc++.h>
#define ls rt<<1
#define rs rt<<1|1
#define pb push_back
#define fi first
#define se second
#define ios ios::sync_with_stdio(0);
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
typedef vector<int> VI;
const int maxn = 2e6 + 6;
const LL inf = 0x3f3f3f3f3f3f3f3f;
const int mod = 998244353;
LL qp(LL x,LL y){LL ans=1;x%=mod;while(y){if(y&1) ans=ans*x%mod;x=x*x%mod;y>>=1;}return ans;}
LL inv(LL x){return qp(x,mod-2);}
//head
vector<int>vec[100010];
int dp[100010][30];
int d[100010],n,m;
void init()
{
for(int i=0;i<=100000;i++)for(int j=0;j<=30;j++) dp[i][j]=0;
for(int i=0;i<=100000;i++) d[i]=0,vec[i].clear();
}
void bfs(int x)
{
d[x]=1;
queue<int>q;q.push(x);
int Lgn=(int)(log(n)/log(2));
while(!q.empty()){
int f=q.front();q.pop();
int len=vec[f].size();
for(int i=0;i<len;i++){
int to=vec[f][i];
if(!d[to]){
q.push(to);
d[to]=d[f]+1;
dp[to][0]=f;
for(int i=1;i<=Lgn;i++){
dp[to][i]=dp[dp[to][i-1]][i-1];
}
}
}
}
}
int Lca(int x,int y)
{
if(d[x]<d[y]) swap(x,y);
int lgn=(int)(log(n)/log(2));
for(int i=lgn;i>=0;i--){
int to=dp[x][i];
if(d[to]>=d[y]){
x=to;
}
}
if(x==y) return x;
for(int i=lgn;i>=0;i--){
int tx=dp[x][i],ty=dp[y][i];
if(tx!=ty){
x=tx;y=ty;
}
}
return dp[x][0];
}
int dis(int x,int y){
int lca=Lca(x,y);
return d[x]+d[y]-2*d[lca];
}
int main()
{
int t,cs=0;scanf("%d",&t);
while(t--){
init();
int q;scanf("%d%d",&n,&q);
for(int i=1;i<n;i++){
int u,v;scanf("%d %d",&u,&v);
vec[u].pb(v);
vec[v].pb(u);
}
bfs(1);
int lgn=(int)(log(n)/log(2));
while(q--){
int a,b,c;scanf("%d %d %d",&a,&b,&c);
if(c==1&&b==1){
printf("NO\n");continue;
}
int d1=d[a],d2=dis(b,c)+d[c];
if(d1<d2) printf("YES\n");
else if(d1==d2){
if(Lca(a,c)==1) printf("NO\n");
else printf("YES\n");
}
else printf("NO\n");
}
}
}
D 景区路线规划
题意：
美团旅行团队最近打算推出一项新服务，为景区的各个景点规划游览路线，提升游客满意度。其中一个重要的问题是对于一个景区道路网，求出游客的满意度的期望值。基于用户的喜好差异，我们需要对男性游客和女性游客的满意度分别计算。
景区被描述成一张n个点、m条边的无向图（无重边，无自环）。每个点代表一个景点，第i个景点游览需要耗费ci分钟，会让男性游客和女性游客的满意度分别增加h1i和h2i（满意度初始值都为0）。每条边代表一条路，第i条边连接编号为xi,yi的两个景点，从景点xi走到yi和从yi走到xi的时间都是ti分钟。
每个游客在景区中最长可以游览k分钟，最开始会随机的通过不同大门进入到一个景点开始游览，每游览完一个项目，游客会等概率随机选择一个可以从当前景点直达且来得及游览的景点作为下一个游览目标（已经游览过的景点也会因为有各种新活动而让游客再次考虑，所以我们这里不区分景点是否已经游览过）。如果游览完一个景点后，周围没有来得及游览的景点，本次游玩就结束了。
请你分别计算小y和妹子在游玩结束后开心度的期望。
题解：
看数据范围显然dp能做
我们令dp[i][j]表示一开始在景点i，有j时间的开心度期望。
那么dp[j][i]= /cnt+hj
然后从小到大转移时间就好拉~~
代码
#pragma GCC optimize(2)
#include<bits/stdc++.h>
#define ls rt<<1
#define rs rt<<1|1
#define pb push_back
#define fi first
#define se second
#define ios ios::sync_with_stdio(0);
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
typedef vector<int> VI;
const int maxn = 2e6 + 6;
const LL inf = 0x3f3f3f3f3f3f3f3f;
const int mod = 998244353;
LL qp(LL x,LL y){LL ans=1;x%=mod;while(y){if(y&1) ans=ans*x%mod;x=x*x%mod;y>>=1;}return ans;}
LL inv(LL x){return qp(x,mod-2);}
//head
struct Edge{
int to,w,next;
}edge[maxn];
int head[maxn],tot;
void add(int u,int v,int w){
edge[++tot]={v,w,head[u]};
head[u]=tot;
}
int n,m,k,c[maxn],h1[maxn],h2[maxn];
double dp[101][505];
double calu(int *h){
for(int i=0;i<=n;i++){
for(int j=0;j<=k;j++) dp[i][j]=0;
}
//for(int i=1;i<=n;i++) cout<<h[i]<<',';cout<<endl;
for(int i=1;i<=k;i++){
for(int j=1;j<=n;j++){
int cnt=0;
double res=0;
if(i<c[j]) continue;
for(int u=head[j];u;u=edge[u].next){
int v=edge[u].to,w=edge[u].w;
if(w<=i-c[j]&&dp[v][i-c[j]-w]) {
res+=dp[v][i-c[j]-w];
cnt++;
}
}
if(cnt==0){
dp[j][i]=h[j];
}
else dp[j][i]=1.0*res/cnt+h[j];
}
}
double ans=0;
for(int i=1;i<=n;i++) {
ans+=dp[i][k];
//cout<<dp[i][k]<<endl;
}
return 1.0*ans/n;
}
int main(){
scanf("%d%d%d",&n,&m,&k);
for(int i=1;i<=n;i++){
scanf("%d%d%d",&c[i],&h1[i],&h2[i]);
}
for(int i=1,u,v,w;i<=m;i++){
scanf("%d%d%d",&u,&v,&w);
add(u,v,w);add(v,u,w);
}
double c=calu(h1),d=calu(h2);
printf("%.5f %.5f\n",c,d);
}
E 幸运数字Ⅱ
题意：
定义一个数字为幸运数字当且仅当它的所有数位都是4或者7。比如说，47、744、4都是幸运数字而5、17、467都不是。定义next(x)为大于等于x的第一个幸运数字。给定l，r，请求出next(l) + next(l + 1) + ... + next(r - 1) + next(r)。
题解：
由于每个幸运数字的每一位只有两种选择4or7那么小于1e9的幸运数字，只有2^9左右个。
所以我们可以dfs预处理出所有的幸运数。
那么对于一个区间l~r，我们只需一直在幸运数的数组中循环计算可以了
代码
#pragma GCC optimize(2)
#include<bits/stdc++.h>
#define ls rt<<1
#define rs rt<<1|1
#define pb push_back
#define fi first
#define se second
#define ios ios::sync_with_stdio(0);
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
typedef vector<int> VI;
const int maxn = 2e6 + 6;
const LL inf = 0x3f3f3f3f3f3f3f3f;
const int mod = 998244353;
LL qp(LL x,LL y){LL ans=1;x%=mod;while(y){if(y&1) ans=ans*x%mod;x=x*x%mod;y>>=1;}return ans;}
LL inv(LL x){return qp(x,mod-2);}
//head
LL t,n,k,a[maxn],l,r,cnt=0;
void dfs(LL x,LL sum){
if(x==0){
if(sum) a[++cnt]=sum;
return ;
}
if(sum==0) dfs(x-1,0);
dfs(x-1,sum+4*qp(10,x-1));
dfs(x-1,sum+7*qp(10,x-1));
}
int main(){
dfs(9,0);
//cout<<cnt<<endl;
sort(a+1,a+1+cnt);
a[++cnt]=4444444444;
scanf("%lld%lld",&l,&r);
LL sum=0;
for(LL i=l;i<=r;){
LL p=lower_bound(a+1,a+1+cnt,i)-a;
sum+=min(a[p]-i+1,r-i+1)*a[p];
i=a[p]+1;
}
printf("%lld\n",sum);
}
京公网安备 11010502036488号