链接：https://www.nowcoder.com/discuss/32063?type=2&order=0&pos=14&page=3
来源：牛客网
练习链接: https://www.nowcoder.com/test/6291726/summary
等差数列
分析
对序列排序,然后比对一下是否等差即可。
参考code
#include
using namespace std;
int n;
int x[55];
string solve() {
sort(x, x + n);
if(n <= 2) return "Possible";
else {
int d = x[1] - x[0];
bool ok = 1;
for(int i = 1; ok && i < n; i++) {
if(d != x[i] - x[i - 1]) return "Impossible";
}
return "Possible";
}
}
int main() {
cin >> n;
for(int i = 0; i < n; i++) cin >> x[i];
cout << solve() << endl;
return 0;
}
彩色砖块
分析
题目有点唬人。。
设颜色种数为s,那么
if s > 2 ans = 0
else ans = s
参考代码
#include
using namespace std;
string s;
set S;
int main() {
cin >> s;
for(int i = 0; i < s.size(); i++) S.insert(s[i]);
int ans = S.size();
if(ans > 2) ans = 0;
cout << ans << endl;
return 0;
}
交错01串
分析
就挨着比较,记录当前是交错01串的长度,维护最大值即可。
参考代码
#include
using namespace std;
string s;
int main() {
cin >> s;
int ans = 1, cnt = 1;
for(int i = 1; i < s.size(); i++) {
if(s[i] != s[i - 1]) {
cnt++;
} else {
cnt = 1;
}
ans = max(ans, cnt);
}
cout << ans << endl;
return 0;
}
独立的小易
分析
首先计算能保证的房屋能租多少天,如果有剩余再考虑购买水果。
参考代码
#include
using namespace std;
int x, f, d, p;
int solve(int x, int f, int d, int p) {
int tmp1 = d / x;
if(tmp1 <= f) return tmp1;
d -= f * x;
return f + d / (x + p);
}
int main() {
cin >> x >> f >> d >> p;
cout << solve(x, f, d, p) << endl;
return 0;
}
堆棋子
分析
对于一个k,我们找一个坐标(x, y)让k个棋子距离这个坐标的曼哈顿距离之和最小。注意到x和y其实是独立的,考虑枚举棋盘上所有可能得坐标(x[i], y[j]),计算这个坐标到所有棋子的距离分别是多少,然后维护k个棋子对于这个坐标最小曼哈顿距离和即可。
参考代码
#include
using namespace std;
const int inf = 1e9;
int n, x[55], y[55];
int main() {
int n;
cin >> n;
for(int i = 0; i < n; i++) cin >> x[i];
for(int i = 0; i < n; i++) cin >> y[i];
vector res(n, inf);
for(int i = 0; i < n; i++) {
for(int j = 0; j < n; j++) {
for(int k = 0; k < n; k++) {
vector res2(n);
for(int l = 0; l < n; l++) {
res2[l] = abs(x[l] - x[j]) + abs(y[l] - y[k]);
}
sort(res2.begin(), res2.end());
int res3 = 0;
for(int l = 0; l < i + 1; l++) res3 += res2[l];
res[i] = min(res[i], res3);
}
}
}
for(int i = 0; i < n; i++) {
i == 0 ? cout << res[i] : cout << " " << res[i];
}
return 0;
}
操作序列
分析
观察每一次操作之后的序列跟之前的关系,可以根据这个直接得到最终的数列。
参考代码
#include
using namespace std;
const int maxn = 2e5 + 5;
int a[maxn];
int n;
int main() {
scanf("%d", &n);
for(int i = 1; i <= n; i++) scanf("%d", &a[i]);
if(n % 2) {
for(int i = n; i >= 1; i -= 2) printf("%d ", a[i]);
for(int i = 2; i <= n; i += 2) i == n - 1 ? printf("%d", a[i]) : printf("%d ", a[i]);
} else {
for(int i = n; i >= 1; i -= 2) printf("%d ", a[i]);
for(int i = 1; i <= n; i += 2) i == n - 1 ? printf("%d", a[i]) : printf("%d ", a[i]);
}
printf("\n");
return 0;
}
疯狂队列
分析
根据样例提示,猜想了一个结论:
我们要把这个队列安排为交错的形式(证明略)。
交错有两种形式,看第一个人是比他相邻的人高还是矮。
以矮的为例:
总共的疯狂值为(h2 - h1) + (h2 - h3) + (h4 - h3) + ... = -h1 + 2h2 - 2h3 + 2h4 - ...,
如果总共是偶数个人,疯狂值为-h1 + 2h2 - 2h3 + 2h4 - ... - 2h{n-1} + h{n},所以我们需要从最大的开始依次安排h2,...h{n-2},然后安排h{n},然后继续安排剩下的。
如果总共是奇数个人,疯狂值为-h1 + 2h2 - 2h3 + 2h4 - ... + 2h{n-1} - h{n},所以我们需要从最大的开始依次安排h2,...h{n-1},然后安排h1和h{n},然后继续安排剩下的。
然后另外一种形式类似,维护最大的疯狂值即可。
参考代码
#include
using namespace std;
int h[55];
int n;
int main() {
cin >> n;
for(int i = 0; i < n; i++) cin >> h[i];
sort(h, h + n);
int tmp, ans = 0, ans1 = 0, ans2 = 0;
if(n % 2 == 0) {
tmp = n / 2;
for(int i = 0; i < tmp; i++) {
ans += 2 * (h[tmp + i] - h[i]);
}
ans += h[tmp - 1] - h[tmp];
cout << ans << endl;
return 0;
} else {
tmp = n / 2;
for(int i = 0; i < tmp; i++) {
ans1 += 2 * (h[tmp + 1 + i] - h[i]);
ans2 += 2 * (h[tmp + 1 + i] - h[i]);
}
ans1 += -h[tmp] + h[tmp - 1];
ans2 += h[n] - h[n + 1];
cout << max(ans1, ans2) << endl;
return 0;
}
return 0;
}
小易喜欢的数列
分析
想象一下,如果我们确定这个数列的第一个数是i,那么第二个数可以是1到k中除了是i的约数的任何数。
于是我们定义dp[j][i]表示长度为i最后一个数是j的小易喜欢的数列的数量,然后挨着转移即可。。实现请参考参考代码。
参考代码
#include
using namespace std;
const int mod = 1e9 + 7;
const int maxn = 1e5 + 5;
int dp[maxn][15];
int n, k;
int main() {
cin >> n >> k;
dp[1][0] = 1;
for(int i = 1; i <= n; i++) {
int sum = 0;
for(int j = 1; j <= k; j++) {
sum += dp[j][i - 1];
sum %= mod;
}
for(int j = 1; j <= k; j++) {
int sum2 = 0;
for(int z = j + j; z <= k; z += j) {
sum2 += dp[z][i - 1];
sum2 %= mod;
}
dp[j][i] = (sum - sum2 + mod) % mod;
}
}
int ans = 0;
for(int j = 1; j <= k; j++) {
ans += dp[j][n];
ans %= mod;
}
cout << ans << endl;
return 0;
}
