A. The Fair Nut and Elevator
time limit per test1 second memory limit per test256 megabytes
The Fair Nut lives in ?n story house. ??ai people live on the ?i-th floor of the house. Every person uses elevator twice a day: to get from the floor where he/she lives to the ground (first) floor and to get from the first floor to the floor where he/she lives, when he/she comes back home in the evening.
It was decided that elevator, when it is not used, will stay on the ?x-th floor, but ?x hasn't been chosen yet. When a person needs to get from floor ?a to floor ?b, elevator follows the simple algorithm:
- Moves from the ?x-th floor (initially it stays on the ?x-th floor) to the ?a-th and takes the passenger.
- Moves from the ?a-th floor to the ?b-th floor and lets out the passenger (if ?a equals ?b, elevator just opens and closes the doors, but stillcomes to the floor from the ?x-th floor).
- Moves from the ?b-th floor back to the ?x-th.
The elevator never transposes more than one person and always goes back to the floor ?x before transposing a next passenger. The elevator spends one unit of electricity to move between neighboring floors. So moving from the ?a-th floor to the ?b-th floor requires |?−?||a−b|units of electricity.
Your task is to help Nut to find the minimum number of electricity units, that it would be enough for one day, by choosing an optimal the ?x-th floor. Don't forget than elevator initially stays on the ?x-th floor.Input
The first line contains one integer ?n (1≤?≤1001≤n≤100) — the number of floors.
The second line contains ?n integers ?1,?2,…,??a1,a2,…,an (0≤??≤1000≤ai≤100) — the number of people on each floor.Output
In a single line, print the answer to the problem — the minimum number of electricity units.
Examples
input
3
0 2 1
output
16
input
2
1 1
output
4
Note
In the first example, the answer can be achieved by choosing the second floor as the ?x-th floor. Each person from the second floor (there are two of them) would spend 44 units of electricity per day (22 to get down and 22 to get up), and one person from the third would spend 88units of electricity per day (44 to get down and 44 to get up). 4⋅2+8⋅1=164⋅2+8⋅1=16.
In the second example, the answer can be achieved by choosing the first floor as the ?x-th floor.
作为一道签到题，这个题意并不难，让你选择一个电梯的初始楼层，告诉你每层楼的人数，让你算出每天电梯要走多少层。考虑到n<100，暴力！
#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define INF 0x3f3f3f3f
#define eps 1e-8
#define PI acos(-1.0)
#define mst(a,b) memset(a,b,sizeof(a))
#define FF(i,a) for(int i=0;i<(a);++i)
#define dep(i,a,b) for(int i=(a);i>=(b);--i)
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define sc(t) scanf("%d",&(t))
#define sc2(t,x) scanf("%d%d",&(t),&(x))
#define sc3(x,y,z) scanf("%d%d%d",&(x),&(y),&(z))
#define pr(t) printf("%d\n",(t))
#define pb push_back
#define quickcin {ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);}
#define Exit {printf("-1\n");exit(0);}
#define lson rt<<1
#define rson rt<<1|1
#define delf (l+r)>>1
#define lowbit(x) (x&-x)
#define pii pair<int,int>
#define F first
#define S second
#define maxn int(5e5)+100
#define mod int(1e9)+7
using namespace std;
int main(){
int n;sc(n);
int a[110];
rep(i,1,n) sc(a[i]);
int ans=INF;
rep(i,1,n){
int tot=0;
rep(j,1,n){
if(j<=i){
tot+=a[j]*(i-1)*4;
}
else tot+=a[j]*(j-1)*4;
}
ans=min(ans,tot);
}
pr(ans);
return 0;
}
B. Kvass and the Fair Nut
time limit per test1 second memory limit per test256 megabytes
The Fair Nut likes kvass very much. On his birthday parents presented him ?n kegs of kvass. There are ??vi liters of kvass in the ?i-th keg. Each keg has a lever. You can pour your glass by exactly 11 liter pulling this lever. The Fair Nut likes this drink very much, so he wants to pour his glass by ?s liters of kvass. But he wants to do it, so kvass level in the least keg is as much as possible.
Help him find out how much kvass can be in the least keg or define it's not possible to pour his glass by ?s liters of kvass.Input
The first line contains two integers ?n and ?s (1≤?≤1031≤n≤103, 1≤?≤10121≤s≤1012) — the number of kegs and glass volume.
The second line contains ?n integers ?1,?2,…,??v1,v2,…,vn (1≤??≤1091≤vi≤109) — the volume of ?i-th keg.Output
If the Fair Nut cannot pour his glass by ?s liters of kvass, print −1−1. Otherwise, print a single integer — how much kvass in the least keg can be.
Examples
input
3 3
4 3 5
output
3
input
3 4
5 3 4
output
2
inputCopy
3 7
1 2 3
outputCopy
-1
Note
In the first example, the answer is 33, the Fair Nut can take 11 liter from the first keg and 22 liters from the third keg. There are 33 liters of kvass in each keg.
In the second example, the answer is 22, the Fair Nut can take 33 liters from the first keg and 11 liter from the second keg.
In the third example, the Fair Nut can't pour his cup by 77 liters, so the answer is −1−1.
11-大佬告诉我用二分（原谅我不知道怎么用），事实证明弱鸡的代码也是可以a的
#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define INF 0x3f3f3f3f
#define eps 1e-8
#define PI acos(-1.0)
#define mst(a,b) memset(a,b,sizeof(a))
#define FF(i,a) for(int i=0;i<(a);++i)
#define dep(i,a,b) for(int i=(a);i>=(b);--i)
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define sc(t) scanf("%d",&(t))
#define sc2(t,x) scanf("%d%d",&(t),&(x))
#define sc3(x,y,z) scanf("%d%d%d",&(x),&(y),&(z))
#define pr(t) printf("%d\n",(t))
#define pb push_back
#define quickcin {ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);}
#define Exit {printf("-1\n");exit(0);}
#define lson rt<<1
#define rson rt<<1|1
#define delf (l+r)>>1
#define lowbit(x) (x&-x)
#define pii pair<int,int>
#define F first
#define S second
#define maxn int(5e5)+100
#define mod int(1e9)+7
using namespace std;
int main(){
int n;sc(n);
ll k;scanf("%lld",&k);
ll tot=0;
ll minx=INF;
FF(i,n){
ll x;
scanf("%lld",&x);
tot+=x;
minx=min(minx,x);
}
if(tot<k){
printf("-1\n");
exit(0);
}
printf("%lld\n",min(minx,(tot-k)/n));
return 0;
}
C. The Fair Nut and String
time limit per test1 second memory limit per test256 megabytes
The Fair Nut found a string ?s. The string consists of lowercase Latin letters. The Nut is a curious guy, so he wants to find the number of strictly increasing sequences ?1,?2,…,??p1,p2,…,pk, such that:
- For each ?i (1≤?≤?1≤i≤k), ???=spi= 'a'.
- For each ?i (1≤?<?1≤i<k), there is such ?j that ??<?<??+1pi<j<pi+1 and ??=sj= 'b'.
The Nut is upset because he doesn't know how to find the number. Help him.
This number should be calculated modulo 109+7109+7.Input
The first line contains the string ?s (1≤|?|≤1051≤|s|≤105) consisting of lowercase Latin letters.Output
In a single line print the answer to the problem — the number of such sequences ?1,?2,…,??p1,p2,…,pk modulo 109+7109+7.
Examples
input
abbaa
output
5
input
baaaa
output
4
input
agaa
output
3
Note
In the first example, there are 55 possible sequences. [1][1], [4][4], [5][5], [1,4][1,4], [1,5][1,5].
In the second example, there are 44 possible sequences. [2][2], [3][3], [4][4], [5][5].
In the third example, there are 33 possible sequences. [1][1], [3][3], [4][4].
题意有点搞，半天没读懂，其实就是找首位都是a，并且两个a之间存在b的子段的数量，简单dp
#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define INF 0x3f3f3f3f
#define eps 1e-8
#define PI acos(-1.0)
#define mst(a,b) memset(a,b,sizeof(a))
#define FF(i,a) for(int i=0;i<(a);++i)
#define dep(i,a,b) for(int i=(a);i>=(b);--i)
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define sc(t) scanf("%d",&(t))
#define sc2(t,x) scanf("%d%d",&(t),&(x))
#define sc3(x,y,z) scanf("%d%d%d",&(x),&(y),&(z))
#define pr(t) printf("%d\n",(t))
#define pb push_back
#define quickcin {ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);}
#define Exit {printf("-1\n");exit(0);}
#define lson rt<<1
#define rson rt<<1|1
#define delf (l+r)>>1
#define lowbit(x) (x&-x)
#define pii pair<int,int>
#define F first
#define S second
#define maxn int(1e5)+100
#define mod (int(1e9)+7)
using namespace std;
int main(){
string t;cin>>t;
string s;
FF(i,t.length()){
if(t[i]=='a'){
s+=t[i];
}
else if(t[i]=='b'){
if(s.length()&&s[s.length()-1]=='b') continue;
else s+=t[i];
}
}
//cout<<s.length()<<endl;
int pre=0;
int v[maxn];
mst(v,0);
FF(i,s.length()){
if(s[i]=='b'){
if(i==0)
v[i]=0;
else{
v[i]=v[i-1];
pre=v[i-1];
}
}
else{
if(i==0) v[i]=1;
else {v[i]=(v[i-1]+pre+1)%mod;}
//cout<<tot<<endl;
}
//cout<<v[i]<<endl;
//cout<<s[i]<<" "<<v[i]<<endl;
}
pr(v[s.length()-1]);
return 0;
}
D. The Fair Nut and the Best Path
time limit per test3 seconds memory limit per test256 megabytes
The Fair Nut is going to travel to the Tree Country, in which there are ?n cities. Most of the land of this country is covered by forest. Furthermore, the local road system forms a tree (connected graph without cycles). Nut wants to rent a car in the city ?u and go by a simple path to city ?v. He hasn't determined the path, so it's time to do it. Note that chosen path can consist of only one vertex.
A filling station is located in every city. Because of strange law, Nut can buy only ??wi liters of gasoline in the ?i-th city. We can assume, that he has infinite money. Each road has a length, and as soon as Nut drives through this road, the amount of gasoline decreases by length. Of course, Nut can't choose a path, which consists of roads, where he runs out of gasoline. He can buy gasoline in every visited city, even in the first and the last.
He also wants to find the maximum amount of gasoline that he can have at the end of the path. Help him: count it.Input
The first line contains a single integer ?n (1≤?≤3⋅1051≤n≤3⋅105) — the number of cities.
The second line contains ?n integers ?1,?2,…,??w1,w2,…,wn (0≤??≤1090≤wi≤109) — the maximum amounts of liters of gasoline that Nut can buy in cities.
Each of the next ?−1n−1 lines describes road and contains three integers ?u, ?v, ?c (1≤?,?≤?1≤u,v≤n, 1≤?≤1091≤c≤109, ?≠?u≠v), where ?u and ?v — cities that are connected by this road and ?c — its length.
It is guaranteed that graph of road connectivity is a tree.Output
Print one number — the maximum amount of gasoline that he can have at the end of the path.
Examples
input
3
1 3 3
1 2 2
1 3 2
output
3
input
5
6 3 2 5 0
1 2 10
2 3 3
2 4 1
1 5 1
output
7
Note
The optimal way in the first example is 2→1→32→1→3.
The optimal way in the second example is 2→42→4.
学了一手树型dp，dp[i]表示编号为i的节点最大的贡献，但是对于每个点能产生的答案是这个节点的子节点中最大值和次大值的和（因为可以从最大值节点经过当前节点再回到次大节点），因此每次更新ans和节点信息的时候要记录一下最大和次大，然后dfs搜到底再回溯上来就可以了
#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define INF 0x3f3f3f3f
#define eps 1e-8
#define PI acos(-1.0)
#define mst(a,b) memset(a,b,sizeof(a))
#define FF(i,a) for(int i=0;i<(a);++i)
#define dep(i,a,b) for(int i=(a);i>=(b);--i)
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define sc(t) scanf("%d",&(t))
#define sc2(t,x) scanf("%d%d",&(t),&(x))
#define sc3(x,y,z) scanf("%d%d%d",&(x),&(y),&(z))
#define pr(t) printf("%d\n",(t))
#define pb push_back
#define quickcin {ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);}
#define Exit {printf("-1\n");exit(0);}
#define lson rt<<1
#define rson rt<<1|1
#define delf (l+r)>>1
#define lowbit(x) (x&-x)
#define pii pair<int,int>
#define F first
#define S second
#define maxn (int(3e5)+100)
#define mod (int(1e9)+7)
using namespace std;
struct node{
int v,w;
};
vector<node> g[maxn];//存边
ll w[maxn];
int vis[maxn];
ll dp[maxn];
ll ans=0;
int n;
void tree_dp(int s,int fa){
vis[s]=1;dp[s]=w[s];ll maxx=-INF;ll cmax=-INF;
FF(i,g[s].size()){
if(g[s][i].v!=fa&&vis[g[s][i].v]==0){
tree_dp(g[s][i].v,s);
if(max(0ll,dp[g[s][i].v]-g[s][i].w)>maxx){//更新最大值和次大值
cmax=maxx;
maxx=max(0ll,dp[g[s][i].v]-g[s][i].w);
}
else if(max(0ll,dp[g[s][i].v]-g[s][i].w)>cmax){//更新次大值
cmax=max(0ll,dp[g[s][i].v]-g[s][i].w);
}
}
}
ans=max(ans,maxx+cmax+w[s]);//更新答案
dp[s]+=max(0ll,maxx);//s节点能产生的最大贡献
ans=max(ans,dp[s]);
}
int main(){
sc(n);
rep(i,1,n) sc(w[i]),ans=max(ans,w[i]);//原地不动的情况
rep(i,1,n-1){
int u,v,w;sc3(u,v,w);
g[u].pb({v,w});
g[v].pb({u,w});
}
mst(vis,0);
tree_dp(1,1);
printf("%lld\n",ans);
return 0;
}
E. The Fair Nut and Strings
time limit per test1 second memory limit per test256 megabytes
Recently, the Fair Nut has written ?k strings of length ?n, consisting of letters "a" and "b". He calculated ?c — the number of strings that are prefixes of at least one of the written strings. Every string was counted only one time.
Then, he lost his sheet with strings. He remembers that all written strings were lexicographically not smaller than string ?s and not biggerthan string ?t. He is interested: what is the maximum value of ?c that he could get.
A string ?a is lexicographically smaller than a string ?b if and only if one of the following holds:
- ?a is a prefix of ?b, but ?≠?a≠b;
- in the first position where ?a and ?b differ, the string ?a has a letter that appears earlier in the alphabet than the corresponding letter in ?b.
Input
The first line contains two integers ?n and ?k (1≤?≤5⋅1051≤n≤5⋅105, 1≤?≤1091≤k≤109).
The second line contains a string ?s (|?|=?|s|=n) — the string consisting of letters "a" and "b.
The third line contains a string ?t (|?|=?|t|=n) — the string consisting of letters "a" and "b.
It is guaranteed that string ?s is lexicographically not bigger than ?t.Output
Print one number — maximal value of ?c.
Examples
input
2 4
aa
bb
output
6
input
3 3
aba
bba
output
8
input
4 5
abbb
baaa
output
8
Note
In the first example, Nut could write strings "aa", "ab", "ba", "bb". These 44 strings are prefixes of at least one of the written strings, as well as "a" and "b". Totally, 66 strings.
In the second example, Nut could write strings "aba", "baa", "bba".
In the third example, there are only two different strings that Nut could write. If both of them are written, ?=8c=8.
待补
