D1T1.铺地毯
for循环
#include<iostream> #include<cstdio> #include<algorithm> using namespace std; struct hp{ int a,b,g,k; }map[10001]; int main() { int n,i,x,y; cin>>n; for(i=1;i<=n;i++) cin>>map[i].a>>map[i].b>>map[i].g>>map[i].k; cin>>x>>y; for(int i=n;i>=1;i--) { if(map[i].a<=x&&map[i].a+map[i].g>=x&&map[i].b<=y&&map[i].b+map[i].k>=y) {cout<<i<<endl;return 0;} } cout<<"-1"<<endl; return 0; }
D1T2.选择客栈
这道题O(kn)算法很简单啊，我来讲讲O（n）的算法吧
a[c]表示记录到第i个客栈为止色调为c的客栈的总数
b[c]表示记录到离当前客栈i最近的消费水平不高于p的客栈为止色调为c的客栈的数量
s[c]记录到当前客栈i为止，最后一个色调为c的客栈的编号
f记录距离客栈i最近的消费水平不超过p的客栈的编号
每读入一个客栈的色调c和最低消费v，我们首先来判断v是否超过了p，如果v没有超过p的话，我们让f=i，即先更新f。
每读入一组数据c和v，我们就应该更新a[c]和s[c]，但是在这一步之前，我们要做如下操作：
不管当前客栈i的消费水平如何，我们来比较f和最后一个色调为c的客栈的编号s[c]的大小关系，
由于我们还没有更新s[c],所以这次比较不包含当前客栈i；
对于当前客栈i的色调c来说，如果该色调是在编号为f的客栈之后第一次出现，则必有f>=s[c]，那么a[c]里面记录的必然是在f客栈之前（包括f）色调为c的客栈的数量，这时我们让b[c]=a[c]，
如果色调c在客栈f之后出现的次数多于1次，那么我们必然已经更新过s[c]，那么必然有s[c]>f，这时我们不做任何操作，则b[c]内保存的依然是在客栈f之前（包括f）色调为c的客栈的数量。
在这里，f发生变化与否，对结果是没有影响的，因为即便在这一步之前f发生了变化，如果某个色调c一直没有出现的话，那对结果没有任何影响，
而一旦某个色调在f变化之后第一次出现，必然有f>=s[c]，这时必然要更新b[c]，那么b[c]必然在这里就会更新成为我们后面计算需要的正确的值，而且在f再次变化之前，b[c]将保持不变。
#include<cstdio> int a[51],b[51],s[51],f=0,n,k,p,c,v,ans=0; int main() { scanf("%d%d%d",&n,&k,&p); for(int i=1;i<=n;i++) { scanf("%d%d",&c,&v); if(v<=p)f=i; if(f>=s[c])b[c]=a[c]; ans+=b[c];a[c]++;s[c]=i; } printf("%d",ans); return 0; }
D1T3 Mayan游戏
搜索+剪枝
1.因为1优先于-1，所以如果一个方块左边也有方块，那么不用搜索这个状态
2.直接从地图的左下角按从下到上，从左到右的顺序搜索
#include<iostream> #include<cstdio> #include<cstring> #include<cstdlib> #include<algorithm> using namespace std; bool ret=0; int mp[9][7],n,ansx[6],ansy[6],ansg[6]; void diao() { int w[6];memset(w,0,sizeof(w)); for(int j=1;j<=5;j++) for(int i=7;i>=1;i--) { if(!mp[i][j]){w[j]=i;break;} } for(int i=7;i>=1;i--) for(int j=1;j<=5;j++) { if(mp[i][j]) { if(i>w[j])continue; mp[w[j]][j]=mp[i][j];mp[i][j]=0;w[j]--; } } } bool xiao() { int _mp[8][6];bool ok=0; for(int i=1;i<=7;i++)for(int j=1;j<=5;j++)_mp[i][j]=mp[i][j]; for(int i=1;i<=7;i++) { int j=1; while(j<=5) { if(_mp[i][j]==0){j++;continue;}int stop; for(stop=j+1;stop<=5;stop++)if(_mp[i][stop]!=_mp[i][stop-1])break; if(stop-j>=3){for(;j<stop;j++)mp[i][j]=0;ok=1;} else j=stop; } } for(int j=1;j<=5;j++) { int i=1; while(i<=7) { if(_mp[i][j]==0){i++;continue;}int stop; for(stop=i+1;stop<=7;stop++)if(_mp[stop][j]!=_mp[stop-1][j])break; if(stop-i>=3){for(;i<stop;i++)mp[i][j]=0;ok=1;} else i=stop; } } return ok; } void dfs(int t) { if(ret)return; int _mp[8][6]; if(t>n) { bool ok=0; for(int i=1;i<=7;i++) for(int j=1;j<=5;j++)if(mp[i][j])ok=1; if(!ok) { for(int i=1;i<=n;i++)printf("%d %d %d ",ansx[i],ansy[i],ansg[i]); ret=1; return; } return; } int color[11];memset(color,0,sizeof(color)); bool ok=0; for(int i=1;i<=7;i++)for(int j=1;j<=5;j++) { _mp[i][j]=mp[i][j];color[mp[i][j]]++;if(mp[i][j])ok=1; } if(!ok)return; for(int i=1;i<=10;i++)if(color[i]>0&&color[i]<3)return; for(int j=1;j<=5;j++) for(int i=7;i>=1;i--) { if(mp[i][j]==0)continue; if(j!=5) { swap(mp[i][j],mp[i][j+1]); do{ diao(); }while(xiao()); ansx[t]=j-1;ansy[t]=7-i;ansg[t]=1;dfs(t+1); for(int i=1;i<=7;i++)for(int j=1;j<=5;j++)mp[i][j]=_mp[i][j]; } if(j!=1) { if(mp[i][j-1]!=0)continue; swap(mp[i][j],mp[i][j-1]); do{ diao(); }while(xiao()); ansx[t]=j-1;ansy[t]=7-i;ansg[t]=-1;dfs(t+1); for(int i=1;i<=7;i++)for(int j=1;j<=5;j++)mp[i][j]=_mp[i][j]; } } } int main() { scanf("%d",&n); for(int i=1;i<=5;i++) for(int j=1;j<=8;j++) { scanf("%d",&mp[8-j][i]);if(!mp[8-j][i])break; } dfs(1); if(!ret)printf("-1"); return 0; }
D2T1 计算系数
杨辉三角
#include<iostream> using namespace std; int dp[1002][1002];const int mod=10007; int main() { int a,b,k,n,m;scanf("%d%d%d%d%d",&a,&b,&k,&n,&m); for(int i=1;i<=k+1;i++)dp[i][i]=1,dp[i][1]=1; for(int i=3;i<=k+1;i++) for(int j=2;j<i;j++)dp[i][j]=(dp[i-1][j]+dp[i-1][j-1])%mod; long long ans=dp[k+1][m+1]; for(int i=1;i<=n;i++)ans=(ans*a)%mod; for(int i=1;i<=m;i++)ans=(ans*b)%mod; cout<<ans; return 0; }
D2T2 聪明的质检员
首先分析公式计算，容易发现sigma ci会随着 m 的递增单调递减。
因此答案满足了单调性，我们考虑二分答案 m，然后对于每次二分出来的答案check 的话，时间复杂度太高。
我们可以发现，可以使用前缀和来 O(1)回答区间查询，对于每个二分出来的 m，先花 O(n)的时间按题意做一下前缀和，然后再 O(q)计算一下 sigma，
这样的话就可以把每次二分完的 O(nq)优化到 O(n+q)，总时间复杂度为O((n+q)log2S)
#include<cstring> #include<cstdio> #include<algorithm> using namespace std; int w[200001],v[200001],l[200001],r[200001],sw[200001],b[200001],c[200001]; int main() { int n,m;long long s;scanf("%d%d%lld",&n,&m,&s); for(int i=1;i<=n;i++){scanf("%d%d",&w[i],&v[i]);sw[i]=w[i];} for(int i=1;i<=m;i++)scanf("%d%d",&l[i],&r[i]); sort(sw+1,sw+n+1); long long ans=999999999999LL;int _l=1,_r=n+1; while(_l<_r) { int mid1=(_l+_r)/2; int mid=sw[mid1]; b[0]=0;c[0]=0; for(int i=1;i<=n;i++) { int g=v[i];c[i]=c[i-1]; if(w[i]<mid)g=0; else c[i]++; b[i]=b[i-1]+g; } long long x=0; for(int i=1;i<=m;i++)x+=(b[r[i]]-b[l[i]-1])*(c[r[i]]-c[l[i]-1]); if(x<s)_r=mid1; else _l=mid1+1; ans=min(ans,abs(x-s)); } printf("%lld",ans); return 0; }
D2T3 观光公交
sum[i]：在前i站下车的人的总数；las[i]：最晚的一个人的到达i站的时间；get[i]最早的到达i站时间。
那么，题目所求的问题就是∑(get[b[i]]-t[i])。
可以转化为：∑(get[b[i]])-∑(t[i])。而∑(t[i])是定值，于是就是要使∑(get[b[i]])最小。
至于get[i]，它取决于上一站的到站时间和最晚的一个人，get[i]=max(las[i-1],get[i-1])+d[i-1]。
容易想到，如果一个d[i]减小了，那么它肯定会影响到后面的一段连续的get[i]。
具体地来说，如果get[i]>las[i]，也就是车的最早到达时间要晚于最慢的人的到达时间，那么前面如果用了加速器，那么就能使get[i]减小，否则就不能造成影响。
我们开一个数组g[i]表示如果d[i]减小，那么最多影响到后面的哪个站。很明显，随着d[i]的减小，g[i]是要变的。
g[i]=g[i+1](get[i+1]>las[i+1]，后一个站的出发时间由到达时间决定) 或 i+1(get[i+1]<=las[i+1]，后一个站的出发时间由最晚到达的人决定)。
要使加速器的效果最大，那么就要使这个加速器的作用影响到最多的人，于是每次找sum[g[i]]-sum[i]最大的一个d[i]加速(d[i]>0)。重复k次即可。
每一个加速器互不影响，所以不存在后效性，局部最优即是全局最优。
#include<iostream> #include<cstdio> using namespace std; int n,m,k,sum[1001],las[1001],get[1001],g[1001],ans=0; int d[1001],a[10001],b[10001],t[10001]; int main() { scanf("%d%d%d",&n,&m,&k); for(int i=1;i<n;i++)scanf("%d",&d[i]); for(int i=1;i<=m;i++) { scanf("%d%d%d",&t[i],&a[i],&b[i]); las[a[i]]=max(las[a[i]],t[i]);sum[b[i]]++; } for(int i=1;i<=n;i++)sum[i]+=sum[i-1]; for(int i=1;i<=n;i++) { get[i]=max(get[i-1],las[i-1])+d[i-1]; } g[n]=n; for(int i=n-1;i>=1;i--) { if(get[i+1]>las[i+1])g[i]=g[i+1]; else g[i]=i+1; } for(int i=1;i<=m;i++)ans+=get[b[i]]-t[i]; while(k) { int rs=0,l,r; for(int i=1;i<n;i++) { if(sum[g[i]]-sum[i]>rs&&d[i]) { rs=sum[g[i]]-sum[i];l=i;r=g[i]; } } d[l]--;ans-=rs; for(int i=l;i<=r;i++) { get[i]=max(get[i-1],las[i-1])+d[i-1]; } if(r==n)r--;g[n]=n; for(int i=r;i>=l;i--) { if(get[i+1]>las[i+1])g[i]=g[i+1]; else g[i]=i+1; } k--; } printf("%d",ans); return 0; }