T1
30% 爆搜。
20% 找c最小的，开始跳。
20% 按h从小到大排序，顺序跳+枚举从哪座楼开始跳。
100% 1.按照高度从低向高排序。n^2枚举最矮的楼和最高的楼是谁，
然后对于中间的楼按c从小到大排序，然后顺序选就可以确定。
复杂度 n^3*log(n)
2。按照高度从小到大排序。f[i][j]表示我停在第i栋楼上，已
经跳了j次楼的最小花费是几。
状态转移方程：f[i][j+1]=min(f[i][j+1],f[k][j]+c[k]+abs(h[i]-h[k])）;
#include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #define N 51 using namespace std; struct node{ int c,h; }e[N]; int n,t; int dp[N][N]; bool cmp(node p,node q){ return p.h<q.h; } int main(){ freopen("meet.in","r",stdin); freopen("meet.out","w",stdout); scanf("%d",&n); for(int i=1;i<=n;i++) scanf("%d",&e[i].c); for(int i=1;i<=n;i++) scanf("%d",&e[i].h); sort(e+1,e+n+1,cmp); memset(dp,63,sizeof(dp)); for(int i=1;i<=n;i++) dp[0][i]=e[i].c; for(int i=1;i<=n;i++) for(int j=1;j<=n;j++){ for(int k=1;k<j;k++) dp[i][j]=min(dp[i][j],dp[i-1][k]+e[j].h-e[k].h); dp[i][j]+=e[j].c; } scanf("%d",&t); for(int i=n;i>=0;i--) for(int j=1;j<=n;j++) if(dp[i][j]<=t){ printf("%d",i+1); return 0; } }
T2
- 已知a1,a2,a3……an；
- 已知b1,b2,b3……bn*(n-1)/2;
- 首先排序。
- 由题意得 a1+a2=b1;a1+a3=b2;a3=a2+b2-b1;
- 设a2+a3=x;
- 可以解得：a1,a2,a3;
- 把a1+a2，a1+a3,a2+a3删去。
- 那么剩余的数中最小的一定是a1+a4。
- 然后a4可求。
- 然后删去a1+a4,a2+a4,a3+a4。
- 那么剩余的数中最小的一定是a1+a5。
- 然后a5可求。
- ……
- 剩下的问题就是如何确定a2+a3。
- 枚举a2+a3等于b3,b4……bn*(n-1)/2。
- 然后判断是否有可行的解即可。
#include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #define MAXN 310 using namespace std; int n,m,cnt; int ans[MAXN][MAXN]; bool use[MAXN*MAXN]; int num[MAXN*MAXN],res[MAXN]; void check(int now){ memset(use,false,sizeof(use)); if((num[1]+num[2]+num[now])&1) return ; res[1]=(num[1]+num[2]+num[now])/2-num[now]; res[2]=num[1]-res[1]; res[3]=num[2]-res[1]; use[1]=use[2]=use[now]=true; for(int i=4,j=3;i<=n;i++){ while(j<=m&&use[j]) j++; if(j>m) return ; res[i]=num[j]-res[1]; use[j]=true; for(int k=2;k<i;k++){ if(res[k]>res[i]) return ; int tmp=res[k]+res[i]; int now=lower_bound(num+1,num+1+m,tmp)-num; if(num[now]!=tmp) return ; int no=now; while(no&&num[no]==num[now]) no--; no++; while(no<=m&&num[no]==num[now]&&use[no]) no++; if(num[no]!=num[now]||use[no]) return ; now=no; use[now]=true; } } cnt++; for(int i=1;i<=n;i++) ans[cnt][i]=res[i]; } int main(){ freopen("city.in","r",stdin); freopen("city.out","w",stdout); scanf("%d",&n); m=n*(n-1)/2; for(int i=1;i<=m;i++) scanf("%d",&num[i]); sort(num+1,num+1+m); for(int i=3;i<=m;){ check(i); int j=i; while(j<=m&&num[j]==num[i]) j++; i=j; } cout<<cnt<<endl; for(int i=1;i<=cnt;i++){ for(int j=1;j<=n;j++) cout<<ans[i][j]<<" "; cout<<endl; } } /* 4 11 17 21 12 20 15 */
T3
30%暴力枚举可过。
60% 1.首先全部mod p，记录下余数。然后用某种数据结构记录一下。
然后每次查询时二分一下在这个l和r的位置，做差即为数的个数。
空间复杂度O(n)。
100% 对p分块。
由60分思路考虑到对所有的p进行预处理。但是时间复杂度变为
O(p*n)，会TLE。
所以想到分块。
对于p<=100，套用60%的做法，对于每一个p预处理一遍。
对于p>100的显然不能套用60%的做法。所以我们不去进行预处理。
v+kp是%p等于v的情况。
已知v+kp<=10000,p>100;
所以k<=100
对于所以每个%p最多只用计算100次。
#include<vector> #include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #define MAXN 100001 using namespace std; vector<int>vec[10001]; vector<int>ve[101][101]; int n,m; int num[MAXN]; int main(){ freopen("light.in","r",stdin); freopen("light.out","w",stdout); scanf("%d%d",&n,&m); for(int i=1;i<=n;i++){ scanf("%d",&num[i]); vec[num[i]].push_back(i); } for(int i=1;i<=100;i++) for(int j=1;j<=n;j++) ve[i][num[j]%i].push_back(j); while(m--){ int l,r,p,v,L,R; scanf("%d%d%d%d",&l,&r,&p,&v); if(p<=100){ L=0,R=ve[p][v].size()-1; int tmp1=-1,tmp2=-1; while(L<=R){ int mid=(L+R)/2; if(ve[p][v][mid]>=l) tmp1=mid,R=mid-1; else L=mid+1; } if(tmp1==-1){ cout<<"0"<<endl;continue; } L=tmp1;R=ve[p][v].size()-1; while(L<=R){ int mid=(L+R)/2; if(ve[p][v][mid]<=r) tmp2=mid,L=mid+1; else R=mid-1; } if(tmp2==-1){ cout<<"0"<<endl;continue; } cout<<tmp2-tmp1+1<<endl; } else{ int pos=v,tot=0; while(pos<=10000){ L=0;R=vec[pos].size()-1; int tmp1=-1,tmp2=-1; while(L<=R){ int mid=(L+R)/2; if(vec[pos][mid]>=l) tmp1=mid,R=mid-1; else L=mid+1; } if(tmp1==-1){ pos+=p;continue; } L=tmp1;R=vec[pos].size()-1; while(L<=R){ int mid=(L+R)/2; if(vec[pos][mid]<=r) tmp2=mid,L=mid+1; else R=mid-1; } if(tmp2==-1){ pos+=p;continue; } tot+=tmp2-tmp1+1; pos+=p; } cout<<tot<<endl; } } } /* 5 2 1 5 2 3 7 1 3 2 1 2 5 3 0 */