[数据结构与算法]蓝桥杯每日练习

排它平方数

枚举六位数，但是因为他又有个很强的性质每一个数位都是不一样的数字，那么只需要dfs一下10个数字的全排列（只取前6位）然后把平方以后的结果依次判断数位是否使用过就可以了

#include <iostream>

using namespace std;

int st[10];
long long n;

void dfs(int k) {
  if(k==6) {
    if(n==203879) return;
    long long cnt=n*n;
    int flag=1;
    while(cnt) {
      if(st[cnt%10]) {
        flag=0;
        break;
      }
      cnt/=10;
    }
    if(flag) {
      cout<<n<<endl;
      exit(0);
    }
    return;
  }
  for(int i=0;i<10;i++) {
    if(!k&&!i) continue;
    if(!st[i]) {
        st[i]=1; n=n*10+i;
        dfs(k+1);
        n/=10; st[i]=0;
    }
  }
}

int main()
{
  dfs(0);
  return 0;
}

买不到的数目

完全背包。物品总共只有两件，每一种物品都是无限的，只需要01dp（0表示取不到该值，1表示能取到）然后每一个拿该物品能否被拿到都取决于不拿该物品的数量能否被取到

#include <iostream>
#include <vector>

using namespace std;

vector<int>res(2);
int q[100010];

int main()
{
  for(int i=0;i<2;i++) cin>>res[i],q[res[i]]=1;
  for(int i=0;i<2;i++) {
    for(int j=res[i];j<100010;j++) {
      q[j]|=q[j-res[i]];
    }
  }
  for(int i=100009;i>=0;i--) {
    if(!q[i]) {
      cout<<i<<endl;
      exit(0);
    }
  }
  return 0;
}

回文日期

枚举每一个日期，判断该日期是不是合法日期，判断日期是否会问。会问日期找到后再找是否满足ABABBABA

#include <iostream>
#include <algorithm>
#include <string>

using namespace std;

int n;
int days[] = { 0,31,28,31,30,31,30,31,31,30,31,30,31 };

string rev(string ch) {
    reverse(ch.begin(), ch.end());
    return ch;
}

bool check(int k) {
    string res = to_string(k);
    return res == rev(res);
}

bool check_(int k) {
    string res = to_string(k);
    int a = res[0], b = res[1];
    if(a==b) return false;
    return res[2] == a && res[5] == a && res[7] == a && res[3] == b && res[4] == b && res[6] == b;
}

bool check_date(int k) {
    int day = k % 100;
    int month = (k % 10000) / 100;
    int year = k / 10000;
    if (month == 2) {
        if (year % 400 == 0 || (year % 100 != 0 && year % 4 == 0)) return day <= 28;
        else return day <= 29;
    }
    if(month>12) return false;
    return day <= days[month];
}

int main()
{
    cin >> n;
    int flag = 0;
    for (int i = n + 1;; i++) {
        if(!check_date(i)) continue;
        if (!flag && check(i)) {
            cout << i << endl;
            flag = 1;
        }
        if (check_(i)) {
            cout << i << endl;
            break;
        }
    }
    return 0;
}

约瑟夫环

约瑟夫环问题是一个很经典的问题，一般做法就是找规律。但是找规律的博客比较多我也就不写了（其实是我觉得我写的不如他们）这里就提供一种短时间找不到规律的模拟写法

#include <iostream>
using namespace std;
int cal(int sum,int n,int num) {
  if(num==1) return (sum+n-1)%sum;
  return (cal(sum-1,n,num-1)+n)%sum;
}
int main()
{
  int n,m;
  cin>>n>>m;
  cout<<cal(n,m,n)+1<<endl;
  return 0;
}