阿里笔试 9.8 上午
第一题直接模拟过了 100%
#include <climits>
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
uint64_t solve(uint64_t n, int k)
{
if (k <= 1)
return 0;
vector<int> arr;
do {
arr.push_back(n%k);
n /= k;
} while (n);
uint64_t ret = 0;
for (int e : arr)
ret = ret*k + e;
return ret;
}
int main()
{
int t, k;
uint64_t n;
cin >> t;
while (t--) {
cin >> n >> k;
cout << solve(n, k) << endl;
}
return 0;
}
第二题想到思路二分，但是没写完。暴力过程中可以发现从左向右是单调递减的，二分找到最接近 0 的线，后来补写的代码
#include <cmath>
#include <cstdio>
#include <climits>
#include <iostream>
using namespace std;
static int64_t func(int64_t sum, int64_t sline, int n, int d, int k)
{
return sum - 2 * k * sline - n * k * (k-1) * d;
}
pair<int, int64_t> solve(int64_t sum, int64_t sline, int n, int d, int maxk)
{
int64_t mins = INT64_MAX;
int k;
int lo = 1, hi = maxk;
while (lo <= hi) {
int mid = lo + (hi-lo)/2;
auto s = func(sum, sline, n, d, mid);
printf("k: %d, delta: %d\n", mid, (int)s);
if (abs(s) < mins || (abs(s) == mins && mid < k)) {
mins = abs(s);
k = mid;
}
if (s > 0) {
lo = mid+1;
} else {
hi = mid-1;
}
}
return {k, mins};
}
void print_solve(int64_t n, uint64_t m)
{
int64_t sum = n*m*(n*m+1)/2;
int64_t col_sum = n + n*(n-1)*m/2;
int64_t row_sum = m*(m+1)/2;
auto col_min = solve(sum, col_sum, n, 1, m-1);
auto row_min = solve(sum, row_sum, m, m, n-1);
cout << "sum: " << sum << endl;
cout << "col_sum: " << col_sum << endl;
cout << "row_sum: " << row_sum << endl;
printf("col_min: {%d, %zd}\n", col_min.first, col_min.second);
printf("row_min: {%d, %zd}\n", row_min.first, row_min.second);
if (col_min.second <= row_min.second) {
cout << "V " << col_min.first << endl;
} else {
cout << "H " << row_min.first << endl;
}
}
int main()
{
int t;
int64_t n, m;
cin >> t;
while (t--) {
cin >> n >> m;
print_solve(n, m);
}
return 0;
} 
