C:Alarm Clocks Everywhere 题意：给出n个起始时间x和m个可以选择的事件间隔p，确定一个起始时间和时间间隔使n个起始时间都能被包含进去。 解题思路：找出n个起始时间的相邻时间间隔的最小公约数t，看是否存在p满足p=t，或者p是t的因子，输出p的位置和可选择的起始时间即可。 代码如下：
#include<bits/stdc++.h> #define ll long long using namespace std; const int ma=3e5+10; int n,m,k; ll a[ma],t,c[ma]; struct node{ ll x,v; }b[ma]; bool cmp(node e,node f){ return e.v<f.v; } ll gcd(ll x,ll y){ if(y==0)return x; if(x%y==0)return y; else return gcd(y,x%y); } ll read() { ll y=0,flag=1; char ch=getchar(); while( (ch>'9' || ch<'0') && ch!='-' ) ch=getchar(); if(ch=='-') flag=-1,ch=getchar(); while(ch>='0' && ch<='9') y=y*10+ch-'0',ch=getchar(); return y*flag; } int main(){ n=read(),m=read(); for(int i=1;i<=n;i++)a[i]=read(); for(int i=1;i<=n;i++)c[i]=a[i]-a[i-1]; t=gcd(c[2],c[3]); for(int i=4;i<=n;i++){//计算每个时间段的最小公约数 t=gcd(c[i],t); } for(int i=0;i<m;i++){//其实不用结构体排序，这是最开始的思路 b[i].v=read(); b[i].x=i+1; } sort(b,b+m,cmp); for(int i=0;i<m;i++){ if(t%b[i].v==0){//找到满足的p cout<<"YES"<<endl; if(b[i].v!=a[1]&&b[i].v<a[1])cout<<a[1]-b[i].v<<" "<<b[i].x<<endl;//确定起始时间 else cout<<a[1]<<" "<<b[i].x<<endl; return 0; } } cout<<"NO"; return 0; }D： Beautiful Array 题意：给你一个长度为n的序列，找出一个区间使它区间和最大，或者使该区间乘以k之后的和最大，问最大值是多少。 解题思路：可以用动归的思路：dp[0][i]维护到第i个数不乘k所得到的最大字段和，dp[1][i]维护的是到第i个数以开始使用乘上k的最大子段和，dp[2][i]维护的是到第i个数已经结束乘以k的最大字段和。每次取max即可。 代码如下：
#include<cstdio> #include<algorithm> #include<iostream> using namespace std; typedef long long ll; const int ma=3e5+10; ll n,k,ans; ll dp[3][ma],x; ll read() { ll y=0,flag=1; char ch=getchar(); while( (ch>'9' || ch<'0') && ch!='-' ) ch=getchar(); if(ch=='-') flag=-1,ch=getchar(); while(ch>='0' && ch<='9') y=y*10+ch-'0',ch=getchar(); return y*flag; } int main(){ n=read(),k=read(); for(int i=1;i<=n;i++){ x=read(); dp[0][i]=max(dp[0][i-1]+x,(ll)0); dp[1][i]=max(dp[1][i-1]+x*k,dp[0][i]); dp[2][i]=max(dp[2][i-1]+x,dp[1][i]); ans=max(ans,dp[2][i]); } /* O(1)内存写法; int t1=0,t2=0,t3=0; for(int i=0;i<n;++i){ scanf("%lld",&x); t1=max(t1+x,(ll)0); t2=max(t2+x*k,t1); t3=max(t2,t3+x); ans=max(ans,t3); } */ cout<<ans; return 0; }C: Array Splitting 题意：给出一段递增序列，分成k个连续区间使每一个区间最大值减去最小值的和最小，问最小为多少。 思路：计算相邻两个数之间的差值，如果要保证较小的话，那么只需要将最大的k个差值去掉，使其单独成为一个区间，合并时值为0. 代码如下：
#include<bits/stdc++.h> #define LL long long using namespace std; const int N=3e5+10; int n,m,k,a,b,c,ans; int num[N]; int read() { int y=0,flag=1; char ch=getchar(); while( (ch>'9' || ch<'0') && ch!='-' ) ch=getchar(); if(ch=='-') flag=-1,ch=getchar(); while(ch>='0' && ch<='9') y=y*10+ch-'0',ch=getchar(); return y*flag; } int main(){ n=read(),k=read(),b=read(); for(int i=2;i<=n;i++){ a=read(); num[c++]=a-b; b=a; } sort(num,num+c); for(int i=0;i<n-k;i++){ ans+=num[i]; } cout<<ans; return 0; }D: Yet Another Subarray Problem 题意：给一个大小为n的数组，给定m， k，计算子序列的的最大值。 解题思路：由表达式可知最后权值中每隔m个就会减k，那么我们对原数组进行处理每隔m个减去k，枚举右端点mod m的数即可。
代码如下：
#include<bits/stdc++.h> #define ll long long using namespace std; const ll N=3e5+10; ll n,m,k,ans; ll num[N]; ll read() { ll y=0,flag=1; char ch=getchar(); while( (ch>'9' || ch<'0') && ch!='-' ) ch=getchar(); if(ch=='-') flag=-1,ch=getchar(); while(ch>='0' && ch<='9') y=y*10+ch-'0',ch=getchar(); return y*flag; } int main(){ n=read(),m=read(),k=read(); for(ll i=1;i<=n;i++)num[i]=read(); for(int j=0;j<m;j++){ ll now=0; for(int i=1;i<=n;i++){ now+=num[i]; if(i%m==j)ans=max(ans,now-k),now-=k; now=max(now,(ll)0); } } cout<<ans; return 0; }