A. Three swimmers
给你三个数a,b,c和一个p。你在p分钟将达到泳池左侧,而a到达泳池左侧时间分别是[0,a,2a,3a…]。[0,b,2b,3b…]。[0,c,2c,3c…]。求你到达后最少还需要等多久会碰上他们其中一人。
实际上不管a,b,c你到达后需要等待x=(p+a-1)/a,res=a*x-p
。分别求三个的最小值即可
#include <bits/stdc++.h>
#define pb push_back//vector,deque
#define INF 0x3f3f3f3f
using namespace std;
typedef long long ll;
const int N=1e5+5;
void solve()
{
int t;
cin>>t;
while(t--){
ll p,a,b,c;
cin>>p>>a>>b>>c;
ll t1=(p+a-1)/a;
ll t2=(p+b-1)/b;
ll t3=(p+c-1)/c;
ll res=min(t1*a-p,min(t2*b-p,t3*c-p));
cout<<res<<'\n';
}
}
int main() {
solve();
return 0;
}
B. Card Deck
给你一副牌,下标从小到大对应牌从下到上,你每次可以选择一个k,然后从k到最后放到另一个地方,牌的顺序是按照下标对应从下到上,也就是说下一次选择的k,从k到最后继续放另一个地方的时候是压在之前方的地方上面的。直至第一副牌空为止,求这样操作之后的使得[ n n − 1 ∗ a [ 0 ] + n n − 2 ∗ a [ 1 ] + . . . n 0 ∗ a [ n − 1 ] n^{n-1}*a[0]+n^{n-2}*a[1]+...n^0*a[n-1] nn−1∗a[0]+nn−2∗a[1]+...n0∗a[n−1]]最大。
实际上就是最后的数组要尽可能大数在前边。那么每次肯定选择最大值和之后的往另一个地方放,继续选择次大值,范围1e5。那么就必须来维护这个最大值。用一个vis数组即可。
#include <bits/stdc++.h>
#define pb push_back//vector,deque
#define INF 0x3f3f3f3f
using namespace std;
typedef long long ll;
const int N=1e5+5;
int a[N],vis[N];
void solve()
{
int t;
cin>>t;
while(t--){
int n;
cin>>n;
for(int i=1;i<=n;i++)cin>>a[i];
int last=n;
stack<int>s;
memset(vis,0,sizeof vis);
for(int i=n;i>=1;i--){
vis[a[i]]=1;
s.push(a[i]);
if(a[i]==last){
while(s.size()){
cout<<s.top()<<' ';
s.pop();
}
while(vis[last])last--;
}
}
cout<<'\n';
}
}
int main() {
solve();
return 0;
}
C. Maximum width
给你两个串a和b,然后b去匹配a,(保证一定能匹配成功)。把a数组匹配的下标存起来求相邻的最大值。
一开始只是反正匹配一次,发现样例2就过不了,后来接着群友口胡,正匹配一次。求相邻最大值即可
#include <bits/stdc++.h>
#define pb push_back//vector,deque
#define INF 0x3f3f3f3f
using namespace std;
typedef long long ll;
const int N=3e5+5;
int res1[N],res2[N];
void solve()
{
// int t;
// cin>>t;
// while(t--){
int n,m,ans=0;
cin>>n>>m;
string s1,s2;
cin>>s1>>s2;
for(int i=0,j=0;i<n&&j<m;i++){
if(s1[i]==s2[j]){
res1[j]=i;j++;
}
}
for(int i=n-1,j=m-1;i>=0&&j>=0;i--){
if(s1[i]==s2[j]){
res2[j]=i;
j--;
}
}
for(int i=1;i<m;i++){
ans=max(res2[i]-res1[i-1],ans);
}
cout<<ans<<'\n';
}
int main() {
solve();
return 0;
}
//5 4 1