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


    题挺好的,收获了许多

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

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

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

    下面是AC代码:

    1. #include
    2. using namespace std;
    3. const int mod=1e9+7;
    4. int t,n,y;
    5. string s;
    6. void solve(){
    7. set<int>st;
    8. if(s[0]=='0'&&n!=1){
    9. cout<<0;
    10. return;
    11. }
    12. int mi=1;
    13. for(int i=2;i<=n;i++) mi*=10;
    14. if(n==1) mi=0;
    15. for(int a=0;a<=9;a++){
    16. for(int b=0;b<=9;b++){
    17. for(int c=0;c<=9;c++){
    18. for(int d=0;d<=9;d++){
    19. if(a==b||a==c||a==d||b==c||b==d||c==d) continue;
    20. for(int _=0;_<=9;_++){
    21. int x=0;
    22. for(int j=0;j
    23. if(s[j]<='9'&&s[j]>='0'){
    24. x=x*10+(s[j]-'0');
    25. }
    26. else{
    27. if(s[j]=='a'){
    28. x=x*10+a;
    29. }
    30. else if(s[j]=='b'){
    31. x=x*10+b;
    32. }
    33. else if(s[j]=='c'){
    34. x=x*10+c;
    35. }
    36. else if(s[j]=='d'){
    37. x=x*10+d;
    38. }
    39. else{
    40. x=x*10+_;
    41. }
    42. }
    43. }
    44. if(x>=mi&&x<=y&&x%8==0) st.insert(x);
    45. }
    46. }
    47. }
    48. }
    49. }
    50. cout<size()%mod;
    51. }
    52. int main(){
    53. ios::sync_with_stdio(false);
    54. cin.tie(0);cout.tie(0);
    55. cin>>t;
    56. while(t--){
    57. cin>>n>>s>>y;
    58. solve();
    59. cout<
    60. }
    61. }

    2.思维:

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

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

    下面是AC代码:

    1. #include
    2. using namespace std;
    3. int n,t,a[200010];
    4. bool cmp(int a,int b){
    5. return a
    6. }
    7. void solve(){
    8. cin>>n;
    9. for(int i=1;i<=n;i++) scanf("%d",&a[i]);
    10. sort(a+1,a+n+1,cmp);
    11. long long sum=0;
    12. for(int i=1;i<=n;i++){
    13. sum+=4ll*min(2*a[1],a[i])*(n-i);
    14. }
    15. cout<
    16. }
    17. int main(){
    18. cin>>t;
    19. while(t--){
    20. solve();
    21. cout<
    22. }
    23. }

    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代码:

    1. #include
    2. using namespace std;
    3. long long t,n,m,k,c[1110],a[1100],mins[5005],dp[5005];
    4. bool vis[5002];
    5. void solve(){
    6. for(int i=0;i<=n;i++) mins[i]=2e18;
    7. for(int i=0;i<=n;i++) dp[i]=2e18;
    8. for(int i=1;i<=m;i++){
    9. for(int j=1;;j++){
    10. if((a[i]*j)%n==a[i]%n&&j>1) break;
    11. int u=(a[i]*j)%n;
    12. mins[u]=min(mins[u],c[i]*j);
    13. }
    14. }
    15. dp[0]=0;
    16. for(int i=1;i<=n;i++){
    17. for(int j=0;j<=n;j++){
    18. dp[j%n]=min(dp[j%n],dp[(j-i+n)%n]+mins[i]);
    19. }
    20. }
    21. long long ww=dp[n-k];
    22. if(ww>=2e18) cout<<-1;
    23. else cout<
    24. return;
    25. }
    26. int main(){
    27. ios::sync_with_stdio(false);
    28. cin.tie(0);cout.tie(0);
    29. cin>>t;
    30. while(t--){
    31. cin>>n>>m>>k;
    32. for(int i=1;i<=m;i++) cin>>a[i]>>c[i];
    33. solve();
    34. cout<
    35. }
    36. }

  • 相关阅读:
    CTF是黑客大赛?新手如何入门CTF?
    Spring Security 自定义用户信息端点与多种登录方式共存
    Kfka监控工具--Kafka-eagle安装
    Unity IL2CPP 游戏分析入门
    嵌入式复古游戏项目开发与实现
    watchdog介绍
    Java连接MySQL数据库
    C/C++预定义宏、 #line 、#error、 #pragma和泛型选择
    Js逆向教程20-Hook基础
    ARouter出现 there‘s no route matched in group问题排查
  • 原文地址:https://blog.csdn.net/cocoack/article/details/136852776