本周没有任何进展，基本都是在牛客打CSP比赛，而且战绩感人。 补题1：乘法师 题意：给定一个长为n的数组，满足所有数都是非负整数。求A有多少个非空子区间，满足区间中所有数的积≥v。 解题思路：对于一段不含0的区间（l,r）若累乘到某一个数（位置i）时乘积已经大于等于v了，那么它对答案的贡献就是r-i+1，然后再将积除以最右边的数，继续向右累乘，以此类推。所以只需要对每一个不含0的区间进行计算求和即可，对于答案，
#include<iostream> #include<algorithm> #include<string.h> #include<string> #include<cstdio> #include<cmath> #define ll long long using namespace std; const int nn=1e5+10; ll n,m,k,ans,T; ll num[nn],ind[nn]; ll jisuan(int l,int r){ ll res=0,now=num[l],t=l; if(l>r)return 0; if(m==1)return (r-l+1)*(r-l+2)/2; for(int i=l;i<=r;i++){ if(now>=m){ now/=num[i];res+=(r-t+1); }else{ for(int j=t+1;j<=r;j++){ now*=num[j]; if(now>=m){ res+=(r-j+1); now/=num[i]; t=j; break; } if(j==r&&now<m)i=r; } } } return res; } int main(){ cin.sync_with_stdio(false); cin>>k; while(k--){ cin>>n>>m; ans=0;T=0; for(int i=1;i<=n;i++)cin>>num[i]; if(m==0){ cout<<n*(n+1)/2<<endl;continue; } for(int i=1;i<=n;i++){ if(num[i]>0){ int le=i,ri=i; while(num[ri+1]>0)ri++; i=ri; ans+=jisuan(le,ri); } } for(int i=1;i<=n;i++)num[i]=0; cout<<ans<<endl; } return 0; }最小差 题意：给出一段序列，可以在序列中去掉k个数，使最后序列中最大数-最小数最小。 解题思路：先对数组进行排序，最后剩下来的n-k个数一定是连续的，并且前后去掉的数之和为k，所以可以枚举左右端点，每一次取最小值即可。 代码如下：
#include<iostream> #include<algorithm> #define ll long long using namespace std; const int nn=1e5+10; int n,m,k,ans=nn,T; int num[nn]; int main(){ cin.sync_with_stdio(false); cin>>n>>k; for(int i=1;i<=n;i++)cin>>num[i]; sort(num+1,num+n+1); for(int i=0;i<=k;i++){ int now=n-(k-i); ans=min(ans,num[now]-num[i+1]); } cout<<ans; return 0; }幸运数字 题意：给出数字y，z，找出所有数字满足数的每一位数字之和为y并且为z的倍数，且数字中不含0，答案取mod。 解题思路：利用dp解决，f[i][j]代表数码和为i，余数为j的数字个数，于是我们转移方程为f[i+x][（j*10+x)%p]+=f[i+x][（j∗10+x)]。输出f[y][0]即可。 代码如下：
#include<bits/stdc++.h> using namespace std; const int MAXN=1e9+7; int y,z; int dp[50005][505]; int main() { cin>>y>>z; dp[0][0]=1; for(int i=0; i<=y; ++i) { for(int j=0; j<z; ++j) { for(int k=1; k<=9; ++k) { dp[i+k][(j*10+k)%z]+=dp[i][j]; dp[i+k][(j*10+k)%z]%=MAXN; } } } cout<<dp[y][0]; return 0; }填数游戏 题意：给出两个长度为n、m的序列(n<=m)，从m中选出n个数填到n个数中，使对应数字乘上填上的数字总和最大，问最大值是多少。 解题思路：对两个序列从大到小排序，然后从前往后遍历，若当前数字大于0，则乘上m序列中对应的值即可，若当前n中数字小于0，则n中后面的数字都小于0，贪心思想可以得出，n中最后一个数应该乘上m中最后一个数字，无论m中最后数字大于0或者小于0，所以当前位置的数字应该乘上m中向前递推m-n个数字。 代码如下：
#include<bits/stdc++.h> #define ll long long using namespace std; const ll N=1e5+10; int n,m,k,ma,x; int num[N],a[N],b[N]; ll ans; 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; } bool cmp(int x,int y){ return x>y; } int main(){ n=read(),m=read(); for(int i=0;i<n;i++)a[i]=read(); for(int i=0;i<m;i++)b[i]=read(); sort(a,a+n,cmp); sort(b,b+m,cmp); for(int i=0;i<n;i++){ if(a[i]>=0)ans+=(ll)(a[i]*b[i]); else ans+=(ll)(a[i]*b[m-n+i]);//小于0时，向前推m-n项 } cout<<ans; return 0; }终焉之理 题意：对与每一次测试，给出一段长为n的序列，每一轮从1到n-1，每一次都对k个数进行排序，问经过多少轮之后序列为递增序列。 解题思路：对于每一个逆序对，可以求出较小的在排完序之后应该所在的位置（该部分可以二分查找），当有相同元素进行排序时，后面的元素可以不用排到第一次出现该元素的位置，比如1 2 3 4 1，后面的1应该排到第二个位置，所以还应该记录原数组的元素下标，分析每一轮排序，较小的元素都只能向前移动k-1个位置，每一次移动对应一轮，所以只需要对每一个逆序对进行计算取最大即可，这里逆序对中较大的数字在第一轮中就会排到相应的位置，手动模拟一下即可。 代码如下：
#include<bits/stdc++.h> #define ll long long using namespace std; const ll N=1e5+10; int n,m,k,ma,T,now; int num[N],a[N]; int ans; 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; } struct node{ int x,y; node(){};//不能少 node(int xx,int yy){ x=xx;y=yy; } bool operator<(const node q)const{ return x<q.x; } }b[N]; int main(){ T=read(); while(T--){ n=read(),k=read(); ans=0; for(int i=1;i<=n;i++){ a[i]=read(); b[i].x=a[i]; b[i].y=i; } sort(b+1,b+n+1); for(int i=1;i<=n-1;i++){ if(a[i]>a[i+1]){ int t=lower_bound(b+1,b+n+1,node(a[i+1],i+1))-b;//二分函数对结构体查找第一个元素 while(b[t].y!=i+1)t++;//如果下标值不是当前逆序对的下标，则向后枚举 ans=max(ans,(int)ceil((double)(i+1-t)/(k-1)));//对每一次取max } } cout<<ans<<endl; } return 0; }公交换乘 题意： 给出n个出行记录，只有公交和地铁两种方式，每一次乘坐地铁可以获得一张价格等于地铁票持续时间等于45分钟的优惠卷，当乘坐公交时，可以选择一张在45分钟前到现在的票价大于等于公交票的优惠劵来抵消本次消费，若有多张满足优惠的优惠劵，选择时间最早的一张。问最终共需要花费多少钱。 解题思路： 用vector存每一张票的出现时间和价格，每接收到一张公交出行记录，就在vector种找到满足条件的票，在这个过程中，遇到时间相差大于45分钟的可以将其去除，满足条件的也要去除。 代码如下：
#include<iostream> #include<algorithm> #include<vector> using namespace std; int n,m,k,t,ans,p,time; struct node{ int b,val;//开始时间，票价 node(int bb,int vv){ b=bb;val=vv; } }; vector<node>v; int main(){ cin.sync_with_stdio(false); cin>>n; for(int i=1;i<=n;i++){ cin>>t>>p>>time; if(!t){v.push_back(node(time,p));ans+=p;}//将优惠劵存进vector中 else { int now=1; for(int j=0;j<v.size();j++){ if(time-v[j].b<=45){ if(v[j].val>=p){ now=0; v.erase(v.begin()+j);//删除满足的票 break; } }else {v.erase(v.begin()+j);j--;}//删除相差时间大于45的票 } if(now)ans+=p; } } cout<<ans; }