A. K-divisible Sum
题意：假设n是数组长度，求数组之和能被k整除的条件下，数组里可以存在最小的数是多少
思路：分别判断下大于小于等于的情况即可
#include<bits/stdc++.h> using namespace std; int main() { int n,i,j,t,k; cin>>t; while(t--){ cin>>n>>k; if(n==k){ cout<<1<<endl; } else if(n>k){ if(n%k==0) cout<<1<<endl; else cout<<2<<endl; } else { cout<<(k%n==0?k/n:k/n+1)<<endl; } } }
B. Inflation
思路：只需要从左往右遍历，如果当前情况不能使等式成立，那么就加在第一个数即可，注意long long
#include<bits/stdc++.h> #define int long long using namespace std; int a[105]; signed main() { int n,i,j,t,k; cin>>t; while(t--){ cin>>n>>k; for(i=0;i<n;i++){ cin>>a[i]; } int sum=a[0]; int ans=0; for(i=1;i<n;i++){ int d1=a[i]*100; int min1; if(d1%k==0) min1=d1/k; else min1=d1/k+1; if(sum>=min1){ sum+=a[i]; continue; } else { ans+=(min1-sum); sum=min1; sum+=a[i]; } } cout<<ans<<endl; } }
C. Longest Simple Cycle
题意：给你n个长度为c[i]的的链，并且给出除了第一条以外的a[i]（与前一条链的头相连）和b[i]（与前一条链的尾巴相连）,求能构成的圈圈的最大周长。
思路：其实贪心判断一下就好，如果是a[i]和b[i]相等或者是第一条链，那么该链一定得作为左边界，然后不断去更新右边界，并且注意一下如果把当前链作为左边界更大，则在更新起点。
#include<bits/stdc++.h> #define int long long using namespace std; const int maxn=1e5+100; int a[maxn],b[maxn],c[maxn]; signed main(){ int t,n,i,j; cin>>t; while(t--){ cin>>n; for(i=0;i<n;i++) cin>>c[i]; for(i=0;i<n;i++) cin>>a[i]; for(i=0;i<n;i++) cin>>b[i]; int ans=0,length=0; for(i=1;i<n;i++){ if(i==1||a[i]==b[i]){ length=abs(a[i]-b[i])+2+(c[i]-1); } else { int m1=abs(a[i]-b[i])+2+(c[i]-1); int m2=length-abs(a[i]-b[i])+2+c[i]-1; length=max(m1,m2); } ans=max(ans,length); } cout<<ans<<endl; } }
D. Journey
思路：判断从i点往左走和往右走两种情况下能走的最大距离，答案就是L+R+1,但每个点都取L,R如果暴力是会超时的，所以应该用前缀和储存，并且能走的话应该是从s[i]开始向左就是LRLRLR相互交错，向右同理，因为每次走之后LR会反转，则只有交错才会走下去。
#include<bits/stdc++.h> using namespace std; const int maxn=3e5+100; int l[maxn],r[maxn]; int main() { string s; int t,i,j,n; cin>>t; while(t--){ cin>>n>>s; for (i=0;i<n;i++) { if(i==0||s[i]==s[i-1])l[i]=1; else l[i]=l[i-1]+1; } for(i=n-1;i>=0;i--){ if (i==n-1||s[i]==s[i+1]) r[i]=1; else r[i]=r[i+1]+1; } for(i=0;i<=n;i++) { int ans=0; if (i>0&&s[i-1]=='L') ans+=l[i-1]; if (i<n&&s[i]=='R') ans+=r[i]; cout<<ans+1<<" "; } cout<<endl; } }
