传送门
题意
一个楼里有一个电梯,第i层有A[i]人,每个人每天用两次电梯,下楼一次和上楼一次,现在规定电梯初始处于一个点 每次有人需要电梯 ,电梯就上去到这个人的楼 载到一楼再到初始的层数
题解
发现 如果电梯在一楼和在任意一楼的接送花费是一样的,但是如果在一楼, 一楼的人需要电梯就不需要电梯额外跑两次,所以电梯在一楼最优(当然数据很小,你也可以暴力
1 2 3 4 5
|
int n; cin>>n; ll sum=0; for(int i=1;i<=n;i++)cin>>a[i],sum+=a[i]*2LL*(i-1)*2; cout<<sum<<endl;
|
题意
N个桶,需要K升酒,问取完K升酒后 桶中剩余酒的最小值的最大是多少
题解
直接二分答案,判断把酒取到这个值能否到达K升,注意如果本身就有酒比答案小的话直接返回false
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45
|
using namespace std; typedef long long ll; #define pp pair<int,int> const ll mod=998244353; const int maxn=1e6+50; const ll inf=0x3f3f3f3f3f3f3f3fLL; int (int a,int b){while(b){int t=a%b;a=b;b=t;}return a;} int lcm(int a,int b){return a*b/gcd(a,b);} ll a[maxn]; bool ok(int mid,int n,ll s){ ll cnt=0; for(int i=1;i<=n;i++){ cnt+=ll(max(0LL,a[i]-mid)); if(a[i]<mid)return false; } if(cnt>=s)return true; else return false; } int main() { std::ios::sync_with_stdio(false); std::cin.tie(0); std::cout.tie(0); int n; ll s; cin>>n>>s; ll sum=0; ll mx=-inf; for(int i=1;i<=n;i++)cin>>a[i],sum+=1LL*a[i],mx=max(a[i],mx); if(sum<s){cout<<-1<<endl;exit(0);} sort(a,a+n); int l=0,r=mx; int ans=0; while(l<=r){ int mid=(l+r)/2; if(ok(mid,n,s)){ ans=mid; l=mid+1; } else r=mid-1; } cout<<ans<<endl; return 0; }
|
题意
给你一个字符串,让你构造下标组成的严格递增序列
要求:1.这些下标对应字符串必须是‘a’
2.相邻两个下标之间必须在原字符串中隔着一个’b’
题解
把字符串分块,对于每个块中的a有块的大小种取法,但是也可以不取,所以对大小+1表示这个块都不取,然后根据乘法原理,相乘,最后因为题目要求不能有空的序列,所以答案-1;
1 2 3 4 5 6 7 8 9 10 11 12
|
string s; cin>>s; int len=s.length(); ll ans=1; ll a=0; for(int i=0;i<len;i++){ if(s[i]=='a')a++; else if(s[i]=='b')ans=(ans*(a+1LL))%mod,a=0; } ans=(ans*(a+1LL))%mod; ans--;ans+=mod;ans%=mod; cout<<ans<<endl;
|
题意
每个点都有正权值,每条边都有负权值,选择一个边,使得经过的总权值最大
题解
对于每一个点,都有走一条边和走两条边两种选择,走一条边肯定是选择权值最大的,两条边就是权值第二大的加起来;
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57
|
using namespace std; typedef long long ll; #define pp pair<int,int> const ll mod=1e9+7; const int maxn=1e6+50; const ll inf=0x3f3f3f3f3f3f3f3fLL; int (int a,int b){while(b){int t=a%b;a=b;b=t;}return a;} int lcm(int a,int b){return a*b/gcd(a,b);} ll w[maxn]; struct node{ int to; ll c; }; vector<node>ve[maxn]; void add(int u,int v,ll c){ ve[u].push_back(node{v,c}); ve[v].push_back(node{u,c}); } ll mx=-inf; ll dp1[maxn],dp2[maxn]; void dfs(int now,int pre){ dp1[now]=0; dp2[now]=0; ll ans1=0,ans2=0; for(auto i:ve[now]){ int to=i.to; ll value=i.c; if(to==pre)continue; dfs(to,now); if(dp1[to]-value>ans1){ ans2=ans1; ans1=dp1[to]-value; } else if(dp1[to]-value>ans2)ans2=dp1[to]-value; } dp1[now]=max(0LL,ans1+w[now]); dp2[now]=max(0LL,ans1+ans2+w[now]); mx=max(mx,max(dp1[now],dp2[now])); } int main() { std::ios::sync_with_stdio(false); std::cin.tie(0); std::cout.tie(0); int n; cin>>n; for(int i=1;i<=n;i++)cin>>w[i]; for(int i=1;i<n;i++){ int u,v;ll c; cin>>u>>v>>c; add(u,v,c); } dfs(1,-1); cout<<mx<<endl; return 0; }
|
题意
他写了K个字符串 ,字符串由a,b组成,c是这K个字符串的(不同前缀)的数目
他忘记了他的K个字符串,但是他还记得 这K个字符串的字典序最大T和字典序最小S 意思就是 这K个字符串最大的字符串是T最小的字符串是S
求构造K个字符串,求出这K个字符串的最大不同前缀数目;
题解
把a和b堪称0和1,然后组成一个0 1 字典树,
1.发现树的结点数就是答案;
2.k代表最多分出K个分支,
字符串T和S之间的间隔就是K个分支可以插的地方,
一个优化:如果第n层的分支数大于等于K那么肯定接下来的n+1层的结点数肯定可以有K个
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33
|
using namespace std; typedef long long ll; #define pp pair<int,int> const ll mod=1e9+7; const int maxn=1e6+50; const ll inf=0x3f3f3f3f3f3f3f3fLL; int (int a,int b){while(b){int t=a%b;a=b;b=t;}return a;} int lcm(int a,int b){return a*b/gcd(a,b);}
int main() { std::ios::sync_with_stdio(false); std::cin.tie(0); std::cout.tie(0); ll n,k; cin>>n>>k; string s,t; cin>>s>>t; ll ans=0; ll a=0,b=0; for(int i=0;i<n;i++){ a<<=1;b<<=1; a|=(s[i]-'a');b|=(t[i]-'a'); if(b-a+1>=k){ ans+=k*(n-i);break; } ans+=(b-a+1); if(b==a)b=a=0; } cout<<ans<<endl; return 0; }
|
题意
题解
近期评论