备战蓝桥杯---牛客寒假训练营2VP

题挺好的，收获了许多

1.暴力枚举（许多巧妙地处理细节方法）

n是1--9,于是我们可以直接暴力，对于1注意特判开头0但N！=1，对于情报4，我们可以把a,b,c,d的所有取值枚举一遍，那么如何判断有无前导0？我们只要与10000...比即可，最后用2和3判断一下放入set中去重。

这里有一个小性质：判断是否可以被8除只要看后3位，因为前面的都乘了1000.

下面是AC代码：

#include<bits/stdc++.h>
using namespace std;
const int mod=1e9+7;
int t,n,y;
string s;
void solve(){set<int>st;if(s[0]=='0'&&n!=1){cout<<0;return;}int mi=1;for(int i=2;i<=n;i++) mi*=10;if(n==1) mi=0;for(int a=0;a<=9;a++){for(int b=0;b<=9;b++){for(int c=0;c<=9;c++){for(int d=0;d<=9;d++){if(a==b||a==c||a==d||b==c||b==d||c==d) continue;for(int _=0;_<=9;_++){int x=0;for(int j=0;j<n;j++){if(s[j]<='9'&&s[j]>='0'){x=x*10+(s[j]-'0');}else{if(s[j]=='a'){x=x*10+a;}else if(s[j]=='b'){x=x*10+b;}else if(s[j]=='c'){x=x*10+c;}else if(s[j]=='d'){x=x*10+d;}else{x=x*10+_;}}}if(x>=mi&&x<=y&&x%8==0) st.insert(x); }}}}}cout<<st.size()%mod;
}
int main(){ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);cin>>t;while(t--){cin>>n>>s>>y;solve();cout<<endl;}
}

2.思维：

我们不妨把绝对值拆开，发现它就是两个点的min的两倍，那么对于任意两个点最小dis可能是这两个点较小的2倍，也可能是绕过最小点a[1]的4倍。

于是我们sort一下，从小到大枚举每一个点的贡献即可。

下面是AC代码：

#include<bits/stdc++.h>
using namespace std;
int n,t,a[200010];
bool cmp(int a,int b){return a<b;
}
void solve(){cin>>n;for(int i=1;i<=n;i++) scanf("%d",&a[i]);sort(a+1,a+n+1,cmp);long long sum=0;for(int i=1;i<=n;i++){sum+=4ll*min(2*a[1],a[i])*(n-i);}cout<<sum;
}
int main(){cin>>t;while(t--){solve();cout<<endl;}
}

3.DP

直接按照题目要求DP会TLE，因此我们可以预先维护好每一张卡牌走1---n步的最小花费，同时注意到modn的性质，走n次一定会回到原点以此判断结尾。

dp[i][j]表示最大走i步后使聚合卡提高到j的最小代价，dp[0][0]=0,求dp[n][n-k],易得状态转移方程：

dp[i][j]=min(dp[i-1][j],dp[i-1][(j-i+n)%n]+min[i]),其中我们只用减一个i即可（因为走更多的话就不满足最大走i步的条件）

下面是AC代码：

#include<bits/stdc++.h>
using namespace std;
long long t,n,m,k,c[1110],a[1100],mins[5005],dp[5005];
bool vis[5002];
void solve(){for(int i=0;i<=n;i++) mins[i]=2e18;  for(int i=0;i<=n;i++)  dp[i]=2e18;for(int i=1;i<=m;i++){for(int j=1;;j++){if((a[i]*j)%n==a[i]%n&&j>1) break;int u=(a[i]*j)%n;mins[u]=min(mins[u],c[i]*j);}}dp[0]=0;for(int i=1;i<=n;i++){for(int j=0;j<=n;j++){dp[j%n]=min(dp[j%n],dp[(j-i+n)%n]+mins[i]);}}long long ww=dp[n-k];if(ww>=2e18) cout<<-1;else cout<<ww;return;
}
int main(){ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);cin>>t;while(t--){cin>>n>>m>>k;for(int i=1;i<=m;i++) cin>>a[i]>>c[i];solve();cout<<endl;}
}