阿里笔试(0314算法岗)

#include<stdio.h>
int main()
{

    int a, b, c, d, m;
    scanf("%d %d %d %d %d", &a, &b, &c, &d, &m);
    int ans = 0, x, y;
    for (x = a; x <= b; x++)
        for (y = c; y <= d; y++)
            if (ans < (x * y) % m)
                ans = (x * y) % m;
    printf("%d\n", ans);
    return 0;
}

交换字符

这个题目出的很好，很多边界条件，组合数学

当交换2个相同的字符时，不会产生不同的字符串，因此我们可以用"所有交换的方案数" - "s 维持不变方案数"来得到答案

还要注意特判存在2个字母相同的情况，可以得到原串

#include<bits/stdc++.h>
using namespace std;
#define ll long long
int main() {
    string s; cin >> s;
    ll n = s.size(); 
    map<char, ll> M; for (auto ch: s) M[ch]++;
    ll tot = n*(n-1)/2;
    for (auto [k,v]: M) tot -= v*(v-1)/2;

    //存在2个相同的字母
    for (auto [k,v]: M) if (v >= 2) {
        tot++;
        break;
    }
    cout << tot << endl;
    
}

第三题：切割

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

vector<int> gao(ll n, int k) {
  string s = to_string(n);
  vector<vector<int>> dp(s.size()+1, vector<int>(k, 0x3f3f3f3f));
  dp[0][0] = 0;
  for (int i = 0; i < s.size(); i++) {
    int cur = 0;
    for (int j = i; j < s.size(); j++) {
      cur = (cur * 10 + s[j]-'0')%k;
      for (int x = 0; x < k; x++) {
        dp[j+1][(cur+x)%k] = min(dp[j+1][(cur+x)%k] , dp[i][x]+(i!=0));
      }
    }
  }
  return dp.back();
}

int main() {
  int n, k; cin >> n >> k;
  vector<ll> A(n); for (auto &x: A) cin >> x;
  vector<int> cur(k, 0x3f3f3f3f);
  cur[0] = 0;
  for (auto &t: A) {
    vector<int> nxt(k, 0x3f3f3f3f);
    vector<int> tmp = gao(t, k);
    for (int i = 0; i < k; i++) {
      for (int j = 0; j < k; j++) nxt[(i+j)%k] = min(nxt[(i+j)%k], cur[i]+tmp[j]); 
    }
    cur = nxt;
  }
  cout << cur[0] << endl;
}