1.成绩
原题：https://www.luogu.com.cn/problem/P3954
代码：
#include<bits/stdc++.h>
#define ll long long
using namespace std;
int a,b,c;
int main(){
cin>>a>>b>>c;
cout<<a/10*2+b/10*3+c/10*5;
return 0;
}
解题思路：
因为数据保证a,b,c都是10的整倍数，所以直接做加法就行了
2.图书管理员
代码：
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 1e3+255,w[39]={1,10,100,1000,10000,100000,1000000,10000000,100000000,1000000000};
int n,q,p[N];
int main(){
cin>>n>>q;
for(int i=1;i<=n;i++)cin>>p[i];
sort(p+1,p+n+1);
for(int i=1,x,b;i<=q;i++){
bool flag=0;
cin>>x>>b;
for(int j=1;j<=n;j++){
if(p[j]%w[x]==b){
cout<<p[j]<<'\n';
flag=1;
break;
}
}
if(!flag)cout<<-1<<'\n';
}
return 0;
}
解题思路：
列举出10的次幂，每次去模10的次幂，判断是否相同即可
3.棋盘
代码：
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 1e3+255,dx[4]={0,0,1,-1},dy[4]={1,-1,0,0};
int a[N][N],m,n,ans=1e9,dp[N][N];
void dfs(int x,int y,int precolor,int sum){
if(x==m&&y==m){
if(ans>sum)ans=sum;
return;
}
if(sum>=dp[x][y])return;
else dp[x][y]=sum;
for(int i=0;i<4;i++){
int xx=x+dx[i],yy=y+dy[i];
if(xx<1||xx>m||yy<1||yy>m)continue;
if(a[xx][yy]==precolor){
dfs(xx,yy,precolor,sum);
continue;
}else if(!a[xx][yy]&&precolor==a[x][y]){
dfs(xx,yy,precolor,sum+2);
}else if(a[xx][yy]){
dfs(xx,yy,a[xx][yy],sum+1);
}
}
}
int main(){
memset(a,0,sizeof(a));
memset(dp,1,sizeof(dp));
cin>>m>>n;
for(int i=1;i<=n;i++){
int x,y,z;
cin>>x>>y>>z;
a[x][y]=z+1;
}
dfs(1,1,a[1][1],0);
if(ans!=1e9)cout<<ans;
else cout<<"-1";
return 0;
}
解题思路：
记录每个格子的颜色，进行深搜，分三种情况：第一种，下一个格子的颜色与precolor相等，直接dfs；第二种，下一个格子无色，且当前格子与precolor颜色相等，金币数+2；第三种，下一个格子有色，但和当前格子颜色不同，金币数+1。再加上最优性剪枝，这道题就可以AC了
4.跳房子
代码：
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 5e5+255;
ll n,d,k,x[N],s[N],sum=0,dp[N],maxdis,jid;
bool dpp(ll fir,ll sec){
memset(dp,200,sizeof(dp));
deque<int>q;
dp[0]=0;int fp=0;
for(int i=1;i<=n;i++){
while(fp<i&&x[i]-x[fp]>=fir){
while(q.size()&&dp[q.back()]<=dp[fp])q.pop_back();
q.push_back(fp);
fp++;
}
while(q.size()&&x[i]-x[q.front()]>sec)q.pop_front();
if(q.size())dp[i]=max(dp[i],dp[q.front()]+s[i]);
if(dp[i]>=k)return 1;
}
return 0;
}
int main(){
cin>>n>>d>>k;
for(int i=1;i<=n;i++){
cin>>x[i]>>s[i];
sum+=(s[i]>0?s[i]:0);
if(s[i]>0){
maxdis=max(maxdis,x[i]-x[jid]);
jid=i;
}
}
if(sum<k){
cout<<-1;
return 0;
}else{
int l=-1,r=maxdis;
while(l+1<r){
int mid=(l+r)/2;
if(dpp(max(1ll,d-mid),d+mid))r=mid;
else l=mid;
}
cout<<r;
}
return 0;
}
解题思路：
求出每个距离中最大的差值，进行二分。在判断是否可行时，使用了双端队列来优化，这样可以排除不用的数据，使复杂度大大降低