传送门
题意
一个楼里有一个电梯，第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;
}
|
题意
题解
近期评论