A. Cow and Haybales
time limit per test2 seconds memory limit per test256 megabytes
The USA Construction Operation (USACO) recently ordered Farmer John to arrange a row of n haybale piles on the farm. The i-th pile contains \(a_i\) haybales.
However, Farmer John has just left for vacation, leaving Bessie all on her own. Every day, Bessie the naughty cow can choose to move one haybale in any pile to an adjacent pile. Formally, in one day she can choose any two indices i and j \((1 \le i, j \le n)\) such that |i-j|=1 and a_i>0 and apply \(a_i = a_i - 1, a_j = a_j + 1\). She may also decide to not do anything on some days because she is lazy.
Bessie wants to maximize the number of haybales in pile 1 (i.e. to maximize a_1), and she only has d days to do so before Farmer John returns. Help her find the maximum number of haybales that may be in pile 1 if she acts optimally!Input
The input consists of multiple test cases. The first line contains an integer t \((1 \le t \le 100) \) — the number of test cases. Next 2t lines contain a description of test cases — two lines per test case.
The first line of each test case contains integers n and d\( (1 \le n,d \le 100) \)— the number of haybale piles and the number of days, respectively.
The second line of each test case contains n integers \(a_1, a_2, \ldots, a_n (0 \le a_i \le 100)\) — the number of haybales in each pile.Output
For each test case, output one integer: the maximum number of haybales that may be in pile 1 after d days if Bessie acts optimally.ExampleinputCopy
3 4 5 1 0 3 2 2 2 100 1 1 8 0
outputCopy
3 101 0
Note
In the first test case of the sample, this is one possible way Bessie can end up with 3 haybales in pile 1:
- On day one, move a haybale from pile 3 to pile 2
- On day two, move a haybale from pile 3 to pile 2
- On day three, move a haybale from pile 2 to pile 1
- On day four, move a haybale from pile 2 to pile 1
- On day five, do nothing
In the second test case of the sample, Bessie can do nothing on the first day and move a haybale from pile 2 to pile 1 on the second day.
签到
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(auto i=(a);i<=(b);++i)
#define dep(i,a,b) for(auto i=(a);i>=(b);--i)
#define pb push_back
typedef long long ll;
const int maxn=(int)1e6+100;
const int mod=(int)1e9+7;
int n,d,a[maxn];
void solve(){
scanf("%d%d",&n,&d);
rep(i,1,n) scanf("%d",&a[i]);
int ans=a[1];
rep(i,2,n){
int num=min(a[i]*(i-1),d)/(i-1);
ans+=num;d-=num*(i-1);
}
printf("%d\n",ans);
}
int main(){
int T;cin>>T;
while(T--) solve();
}
B. Cow and Friend
time limit per test2 seconds memory limit per test256 megabytes
Bessie has way too many friends because she is everyone's favorite cow! Her new friend Rabbit is trying to hop over so they can play!
More specifically, he wants to get from (0,0) to (x,0) by making multiple hops. He is only willing to hop from one point to another point on the 2D plane if the Euclidean distance between the endpoints of a hop is one of its n favorite numbers: \(a_1, a_2, \ldots, a_n\). What is the minimum number of hops Rabbit needs to get from (0,0) to (x,0)? Rabbit may land on points with non-integer coordinates. It can be proved that Rabbit can always reach his destination.
Recall that the Euclidean distance between points \((x_i, y_i)\) and \((x_j, y_j)\) is \(\sqrt{(x_i-x_j)^2+(y_i-y_j)^2}\).
For example, if Rabbit has favorite numbers 1 and 3 he could hop from (0,0) to (4,0) in two hops as shown below. Note that there also exists other valid ways to hop to (4,0) in 2 hops (e.g. \((0,0) \rightarrow (2,-\sqrt{5}) \rightarrow (4,0)\)).
Here is a graphic for the first example. Both hops have distance 3, one of Rabbit's favorite numbers.
In other words, each time Rabbit chooses some number a_i and hops with distance equal to a_i in any direction he wants. The same number can be used multiple times.Input
The input consists of multiple test cases. The first line contains an integer t\( (1 \le t \le 1000)\) — the number of test cases. Next 2t lines contain test cases — two lines per test case.
The first line of each test case contains two integers n and x \((1 \le n \le 10^5, 1 \le x \le 10^9)\) — the number of favorite numbers and the distance Rabbit wants to travel, respectively.
The second line of each test case contains n integers \(a_1, a_2, \ldots, a_n (1 \le a_i \le 10^9)\) — Rabbit's favorite numbers. It is guaranteed that the favorite numbers are distinct.
It is guaranteed that the sum of n over all the test cases will not exceed \(10^5\).Output
For each test case, print a single integer — the minimum number of hops needed.ExampleinputCopy
4 2 4 1 3 3 12 3 4 5 1 5 5 2 10 15 4
outputCopy
2 3 1 2
Note
The first test case of the sample is shown in the picture above. Rabbit can hop to \((2,\sqrt{5})\), then to (4,0) for a total of two hops. Each hop has a distance of 3, which is one of his favorite numbers.
In the second test case of the sample, one way for Rabbit to hop 3 times is: \((0,0) \rightarrow (4,0) \rightarrow (8,0) \rightarrow (12,0)\).
In the third test case of the sample, Rabbit can hop from (0,0) to (5,0).
In the fourth test case of the sample, Rabbit can hop: \((0,0) \rightarrow (5,10\sqrt{2}) \rightarrow (10,0)\).
签到
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(auto i=(a);i<=(b);++i)
#define dep(i,a,b) for(auto i=(a);i>=(b);--i)
#define pb push_back
typedef long long ll;
const int maxn=(int)1e6+100;
const int mod=(int)1e9+7;
int n,d,a[maxn];
void solve(){
scanf("%d%d",&n,&d);
rep(i,1,n) scanf("%d",&a[i]);
sort(a+1,a+1+n);
rep(i,1,n) if(a[i]==d) return (void)puts("1");
if(a[n]>d) return (void)puts("2");
printf("%d\n",d/a[n]+(d%a[n]>0));
}
int main(){
int T;cin>>T;
while(T--) solve();
}
C. Cow and Message
time limit per test2 seconds memory limit per test256 megabytes
Bessie the cow has just intercepted a text that Farmer John sent to Burger Queen! However, Bessie is sure that there is a secret message hidden inside.
The text is a string s of lowercase Latin letters. She considers a string t as hidden in string s if t exists as a subsequence of s whose indices form an arithmetic progression. For example, the string aab is hidden in string aaabb because it occurs at indices 1, 3, and 5, which form an arithmetic progression with a common difference of 2. Bessie thinks that any hidden string that occurs the most times is the secret message. Two occurrences of a subsequence of S are distinct if the sets of indices are different. Help her find the number of occurrences of the secret message!
For example, in the string aaabb, a is hidden 3 times, b is hidden 2 times, ab is hidden 6 times, aa is hidden 3 times, bb is hidden 1 time, aab is hidden 2 times, aaa is hidden 1 time, abb is hidden 1 time, aaab is hidden 1 time, aabb is hidden 1 time, and aaabb is hidden 1 time. The number of occurrences of the secret message is 6.Input
The first line contains a string s of lowercase Latin letters \((1 \le |s| \le 10^5)\) — the text that Bessie intercepted.Output
Output a single integer — the number of occurrences of the secret message.ExamplesinputCopy
aaabb
outputCopy
6
inputCopy
usaco
outputCopy
1
inputCopy
lol
outputCopy
2
Note
In the first example, these are all the hidden strings and their indice sets:
- a occurs at (1), (2), (3)
- b occurs at (4), (5)
- ab occurs at (1,4), (1,5), (2,4), (2,5), (3,4), (3,5)
- aa occurs at (1,2), (1,3), (2,3)
- bb occurs at (4,5)
- aab occurs at (1,3,5), (2,3,4)
- aaa occurs at (1,2,3)
- abb occurs at (3,4,5)
- aaab occurs at (1,2,3,4)
- aabb occurs at (2,3,4,5)
- aaabb occurs at (1,2,3,4,5)
Note that all the sets of indices are arithmetic progressions.
In the second example, no hidden string occurs more than once.
In the third example, the hidden string is the letter l.
很显然选长度为1和2的是最优的
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(auto i=(a);i<=(b);++i)
#define dep(i,a,b) for(auto i=(a);i>=(b);--i)
#define pb push_back
typedef long long ll;
const int maxn=(int)1e6+100;
const int mod=(int)1e9+7;
char s[maxn];
int n;
ll a[30][30],num[maxn][30],cnt[30],ans;
int main(){
scanf("%s",s+1);
n=strlen(s+1);
rep(i,1,n) cnt[s[i]-'a']++;
rep(i,0,25) ans=max(ans,cnt[i]);
dep(i,n,1) rep(j,0,25) num[i][j]=num[i+1][j]+(s[i]-'a'==j);
rep(i,1,n) rep(j,0,25) a[s[i]-'a'][j]+=num[i+1][j];
rep(i,0,25) rep(j,0,25) ans=max(ans,a[i][j]);
printf("%lld\n",ans);
}
D. Cow and Fields
time limit per test2 seconds memory limit per test256 megabytes
Bessie is out grazing on the farm, which consists of n fields connected by m bidirectional roads. She is currently at field 1, and will return to her home at field n at the end of the day.
The Cowfederation of Barns has ordered Farmer John to install one extra bidirectional road. The farm has k special fields and he has decided to install the road between two different special fields. He may add the road between two special fields that already had a road directly connecting them.
After the road is added, Bessie will return home on the shortest path from field 1 to field n. Since Bessie needs more exercise, Farmer John must maximize the length of this shortest path. Help him!Input
The first line contains integers n, m, and k \((2 \le n \le 2 \cdot 10^5, n-1 \le m \le 2 \cdot 10^5, 2 \le k \le n)\) — the number of fields on the farm, the number of roads, and the number of special fields.
The second line contains k integers\( a_1, a_2, \ldots, a_k (1 \le a_i \le n)\) — the special fields. All a_i are distinct.
The i-th of the following m lines contains integers \(x_i and y_i (1 \le x_i, y_i \le n, x_i \ne y_i)\), representing a bidirectional road between fields x_i and y_i.
It is guaranteed that one can reach any field from every other field. It is also guaranteed that for any pair of fields there is at most one road connecting them.Output
Output one integer, the maximum possible length of the shortest path from field 1 to n after Farmer John installs one road optimally.ExamplesinputCopy
5 5 3 1 3 5 1 2 2 3 3 4 3 5 2 4
outputCopy
3
inputCopy
5 4 2 2 4 1 2 2 3 3 4 4 5
outputCopy
3
Note
The graph for the first example is shown below. The special fields are denoted by red. It is optimal for Farmer John to add a road between fields 3 and 5, and the resulting shortest path from 1 to 5 is length 3.
The graph for the second example is shown below. Farmer John must add a road between fields 2 and 4, and the resulting shortest path from 1 to 5 is length 3.
我们跑两次dij得出每个点到1的最短路和到n的最短路，那么对于在k集合内的任意两个点，答案就是要最大化min(pre[a]+sub[b],pre[b]+sub[a])，这样做是\(n^2\)的；
如何优化，我们可以令pre[a]+sub[b]<=pre[b]+sub[a]，那么也就是pre[a]-sub[a]<=pre[b]-sub[b]，这样我们将k数组内的元素按照pre[i]-sub[i]升序排后，对于任意一对i，j满足i<j，i就是a，j就是b，这样我们只需要扫一遍，维护a的前缀最大值，再加上当前这个b就好了
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(auto i=(a);i<=(b);++i)
#define dep(i,a,b) for(auto i=(a);i>=(b);--i)
#define pb push_back
typedef long long ll;
typedef pair<int,int> pii;
const int maxn=(int)1e6+100;
const int mod=(int)1e9+7;
int n,m,k,head[maxn],tot=1,vis[maxn],d[2][maxn],a[maxn];
struct node{int u,v,nxt;}g[maxn];
void add(int u,int v){g[tot]={u,v,head[u]};head[u]=tot++;}
void dijkstra(int s,int op) {
priority_queue<pii,vector<pii>,greater<pii> > Q;
rep(i,1,n) d[op][i]=mod,vis[i]=0; d[op][s]=0;
Q.push({d[op][s],s});
while(!Q.empty()){
pii tmp=Q.top();Q.pop();
int x=tmp.second;
if(vis[x]) continue;vis[x]=1;
for(int i=head[x];i;i=g[i].nxt) if(d[op][g[i].v]>d[op][x]+1){
d[op][g[i].v]=d[op][x]+1;Q.push({d[op][g[i].v],g[i].v});
}
}
}
int main(){
scanf("%d%d%d",&n,&m,&k);
rep(i,1,k) scanf("%d",&a[i]);
rep(i,1,m){
int u,v;scanf("%d%d",&u,&v);
add(u,v);add(v,u);
}
dijkstra(1,0);dijkstra(n,1);
vector<pii> v;
rep(i,1,k) v.pb({d[0][a[i]]-d[1][a[i]],a[i]});
sort(v.begin(),v.end());
int mx=-mod,ans=-mod;
for(auto it:v){
int x=it.second;
ans=max(ans,mx+d[1][x]+1);
mx=max(mx,d[0][x]);
}
printf("%d\n",min(d[0][n],ans));
}
E. Cow and Treats
time limit per test1 second memory limit per test256 megabytes
After a successful year of milk production, Farmer John is rewarding his cows with their favorite treat: tasty grass!
On the field, there is a row of n units of grass, each with a sweetness s_i. Farmer John has m cows, each with a favorite sweetness f_i and a hunger value h_i. He would like to pick two disjoint subsets of cows to line up on the left and right side of the grass row. There is no restriction on how many cows must be on either side. The cows will be treated in the following manner:
- The cows from the left and right side will take turns feeding in an order decided by Farmer John.
- When a cow feeds, it walks towards the other end without changing direction and eats grass of its favorite sweetness until it eats h_i units.
- The moment a cow eats h_i units, it will fall asleep there, preventing further cows from passing it from both directions.
- If it encounters another sleeping cow or reaches the end of the grass row, it will get upset. Farmer John absolutely does not want any cows to get upset.
Note that grass does not grow back. Also, to prevent cows from getting upset, not every cow has to feed since FJ can choose a subset of them.
Surprisingly, FJ has determined that sleeping cows are the most satisfied. If FJ orders optimally, what is the maximum number of sleeping cows that can result, and how many ways can FJ choose the subset of cows on the left and right side to achieve that maximum number of sleeping cows (modulo \(10^9+7\))? The order in which FJ sends the cows does not matter as long as no cows get upset.Input
The first line contains two integers n and m\( (1 \le n \le 5000, 1 \le m \le 5000)\) — the number of units of grass and the number of cows.
The second line contains n integers \(s_1, s_2, \ldots, s_n (1 \le s_i \le n) \) — the sweetness values of the grass.
The i-th of the following m lines contains two integers f_i and \(h_i (1 \le f_i, h_i \le n)\) — the favorite sweetness and hunger value of the i-th cow. No two cows have the same hunger and favorite sweetness simultaneously.Output
Output two integers — the maximum number of sleeping cows that can result and the number of ways modulo 10^9+7.ExamplesinputCopy
5 2 1 1 1 1 1 1 2 1 3
outputCopy
2 2
inputCopy
5 2 1 1 1 1 1 1 2 1 4
outputCopy
1 4
inputCopy
3 2 2 3 2 3 1 2 1
outputCopy
2 4
inputCopy
5 1 1 1 1 1 1 2 5
outputCopy
0 1
Note
In the first example, FJ can line up the cows as follows to achieve 2 sleeping cows:
- Cow 1 is lined up on the left side and cow 2 is lined up on the right side.
- Cow 2 is lined up on the left side and cow 1 is lined up on the right side.
In the second example, FJ can line up the cows as follows to achieve 1 sleeping cow:
- Cow 1 is lined up on the left side.
- Cow 2 is lined up on the left side.
- Cow 1 is lined up on the right side.
- Cow 2 is lined up on the right side.
In the third example, FJ can line up the cows as follows to achieve 2 sleeping cows:
- Cow 1 and 2 are lined up on the left side.
- Cow 1 and 2 are lined up on the right side.
- Cow 1 is lined up on the left side and cow 2 is lined up on the right side.
- Cow 1 is lined up on the right side and cow 2 is lined up on the left side.
In the fourth example, FJ cannot end up with any sleeping cows, so there will be no cows lined up on either side.
英语阅读理解题；
题意：有n个草排成一列，每个草有一个甜味值；有m头牛，每头牛有一个自己喜欢的甜味值f和饥饿程度h，意思是这头牛只吃这个甜味值的草，并且吃h个就会饱；你需要在这列草的左右确定两个牛的集合，你可以决定牛的前后顺序以及吃草的方向，牛吃草的原则如下：
每头牛确定了吃草方向后就只能向那个方向走；
每头牛只吃自己喜欢的甜味值的草，不是这个甜味值直接跳过；
每头牛在吃了h个草之后会就地睡在这个格子上；
如果一头牛遇到了睡着的牛或者走到尽头还是没有吃够它就会不高兴；
农夫想要选择尽可能多的牛使得他们都高兴，问你最大数量以及方案数（左右两个集合内元素不同就视为不同的方案）；
思路：我们可以很显然地发现一个性质，就是一个集合内不可能出现两个及以上的甜味值相同的牛。由于这个性质，我们可以知道每头牛最后睡的格子都是互不相同的，那么如果一个可行的集合确定了，必然有一个可行的顺序使得每头牛都可以开心，我们只需要确定这个集合有多少种即可（实际上题目也是这么要求的）；
我们可以枚举向右走的第一头牛的编号（当然也可以没有牛向右走），假设这时候这头牛到达的位置为p，那么我们就将区间分为了[1,p-1]和[p+1,n]这两段，对于每一段可以单独思考；
对于段内的甜味值f，我们可以统计出这段内有多少个这个味道的草，记为c，那么我们就需要知道有多少头牛可以放在这一段的开头，显然数量就是甜味值为f并且饥饿值小于等于c的牛的数量。于是我们有了两个值x和y，分别表示对于当前甜味值f，可以放在左右的牛的数量，方便起见，我们令x<=y（后面会说为什么）。计算方案数和睡觉的牛的数量时有三种case，分别是：
1、x=0，y!=0，此时数量加上1，方案数乘y；
2、x=1，y=1，此时数量加1，方案数乘2；（因为一共只有一头牛满足条件，显然只有放左边或者放右边两种情况）
3、其他所有情况，此时数量加2，方案数乘x*(y-1)；（这里要求x<=y，因为一头牛如果满足了x那边就必然满足y那一边，所以在乘了x之后y就会有一头牛被用掉）
又因为每段内的不同颜色是互不干扰的，所以方案数直接累乘即可；
需要特判的有，在判断颜色时如果这个颜色和一开始枚举的第一头牛的颜色相同那么x直接就等于0，如果右边这个颜色的草的数量大于等于左边那y也要减去1（因为本来我枚举的这头牛是可以出现在y里的，但是现在确定了位置就不可以）
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(auto i=(a);i<=(b);++i)
#define dep(i,a,b) for(auto i=(a);i>=(b);--i)
#define pb push_back
typedef long long ll;
const int maxn=(int)1e4+100;
const int mod=(int)1e9+7;
int n,m,l[maxn],r[maxn],mx,a[maxn];ll ans;
vector<int> v[maxn];
int main(){
scanf("%d%d",&n,&m);
rep(i,1,n) scanf("%d",&a[i]); int f,h;
rep(i,1,m) scanf("%d%d",&f,&h),v[f].pb(h);
rep(i,1,n) sort(v[i].begin(),v[i].end());
rep(i,0,n){//枚举向右走的第一头牛的编号
rep(j,0,n) l[j]=r[j]=0;
rep(j,1,i) l[a[j]]++;
rep(j,i+1,n) r[a[j]]++;
int ok=i==0,num=i!=0;ll s=1;
for(auto x:v[a[i]]) if(x==l[a[i]]){ok=1;break;}
if(!ok) continue;
rep(j,1,n){
int x=0,y=0,sz=(int)v[j].size();
while(x<sz&&v[j][x]<=l[j]) x++;
while(y<sz&&v[j][y]<=r[j]) y++;
if(j==a[i]) x=0,y-=(r[j]>=l[j]);
if(x+y==0) continue;
if(x>y) swap(x,y);
if(!x) num++,s=s*y%mod;
else if(y==1) num++,s=s*2%mod;
else num+=2,s=s*x*(y-1)%mod;
}
if(num>mx) mx=num,ans=0;
if(num==mx) ans=(ans+s)%mod;
} printf("%d %lld\n",mx,ans);
}
