Problem A Bad Hair Day
题目链接：https://ac.nowcoder.com/acm/contest/984/A/
题意:给定n头牛的高度，设d(i)为第i头牛可以看到(向右看)的其它牛的总数。
思路:反过来想，求第i头牛可以被左边多少头牛看到。维护一个单调栈即可。
Accepted Code:
#include <bits/stdc++.h>
using namespace std;
int main() {
int n, a;
long long ans = 0;
stack <int> S;
scanf("%d", &n);
for (int i = 0; i < n; i++) {
scanf("%d", &a);
while (!S.empty() && S.top() <= a)
S.pop();
ans += S.size();
S.push(a);
}
printf("%lld\n", ans);
return 0;
} Problem B 切长条
题目链接：https://ac.nowcoder.com/acm/contest/984/B/
题意:给你一些长条，问至少要切几刀才能把每一根长条都切开。
思路:贪心，按结束位置从小到大排序，然后直接暴力。
Accepted Code:
#include <bits/stdc++.h>
using namespace std;
const int N = 32005;
struct edge {
int l, r;
bool operator < (const edge & s) const {
if (s.l != l)
return s.r > r;
return s.l < l;
}
}p[N];
int vis[N];
int main() {
int n, l, ans = 0;
scanf("%d", &n);
for (int i = 0; i < n; i++) {
scanf("%d%d", &p[i].l, &l);
p[i].r = p[i].l + l;
}
sort(p, p + n);
for (int i = 0; i < n; i++) {
if (!vis[i]) {
ans++;
vis[i] = 1;
for (int j = i + 1; j < n; j++) {
if (p[j].l < p[i].r)
vis[j] = 1;
}
}
}
printf("%d\n", ans);
return 0;
} Problem C Cows Of The Round Table
题目链接：https://ac.nowcoder.com/acm/contest/984/C/
题意:n个数字组成一个环，使得相邻之间的差距不超过k，有几种组合方法。
思路:暴力枚举排列。
Accepted Code:
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 15;
int vis[MAXN], arr[MAXN], h[MAXN];
int n, k, ans = 0;
void DFS(int p) {
if (p == n) {
ans++;
return ;
}
for (int i = 0; i < n; i++) {
if (vis[i] != 1 && abs(arr[p - 1] - h[i]) <= k) {
if (p == n - 1 && abs(h[i] - arr[0]) > k)
continue;
arr[p] = h[i];
vis[i] = 1;
DFS(p + 1);
vis[i] = 0;
}
}
}
int main() {
scanf("%d%d", &n, &k);
for (int i = 0; i < n; i++)
scanf("%d", &h[i]);
arr[0] = h[0];
vis[0] = 1;
DFS(1);
printf("%d\n", ans);
return 0;
} Problem D 饥饿的牛
题目链接：https://ac.nowcoder.com/acm/contest/984/D/
题意:按照FJ的规定，最多有多少头奶牛能吃上饭。
思路:最长上升子序列。
Accepted Code:
#include <bits/stdc++.h>
using namespace std;
const int N = 100005;
int dp[N], s[N];
int search(int dp[], int x, int l, int r) {
while (l < r) {
int mid = l + (r - l) / 2;
if (dp[mid] >= x)
r = mid;
else l = mid + 1;
}
return l;
}
int LIS(int a[], int n) {
int p, len = 1;
memset(dp, 0, sizeof dp);
dp[0] = a[0];
for(int i = 1; i < n; i++) {
if (a[i] > dp[len - 1])
dp[len++] = a[i];
else {
p = search(dp, a[i], 0, len - 1);
dp[p] = a[i];
}
}
return len;
}
int main() {
int n;
scanf("%d", &n);
for (int i = 0; i < n; i++)
scanf("%d", &s[i]);
printf("%d\n", LIS(s, n));
return 0;
} Problem E The Eating Puzzle
题目链接：https://ac.nowcoder.com/acm/contest/984/E/
题意:确定饲料桶的最佳组合，使Bessie在不超过限制C的情况下获得多的卡路里。
思路:01背包。
Accepted Code:
#include <bits/stdc++.h>
using namespace std;
int w[25], dp[35005];
int main() {
int v, n;
scanf("%d%d", &v, &n);
for (int i = 0; i < n; i++)
scanf("%d", &w[i]);
memset(dp, 0, sizeof(dp));
for (int i = 0; i < n; i++)
for (int j = v; j >= w[i]; j--)
dp[j] = max(dp[j], dp[j - w[i]] + w[i]);
printf("%d\n", dp[v]);
return 0;
} Problem F 随机数
题目链接：https://ac.nowcoder.com/acm/contest/984/F/
题意:给定一个区间，寻找区间内二进制表示法中0的个数大于等于1的个数的数的个数。
思路:把给定区间的上限用二进制表示出来，其长度就是二进制表示上限，举个例子吧，1011011001，假定其为区间上限的二进制表示，长度为10，所以说，任何长度小于10的二进制数都没有它大，所以我们就可以从长度为1开始枚举，长度为i=1的只有二进制表示的1，只有一个1，没有0，不满足题意，继续遍历，长度i>=2时要注意，最高位必须是1，所以也就是说最高位是已知的，在剩下的i-1 位中按照排列组合法求满足条件的数的组合数，因为已经有了最高位的1，所以算的时候只要0的个数大于等于1的个数加1。当长度等于上限长度，但是数值小于等于上限数值的数，这个就要挨个遍历寻找了。
组合公式：C[i][j]=C[i-1][j-1]+C[i-1][j];
Accepted Code:
#include <bits/stdc++.h>
using namespace std;
const int N = 2e9 + 7;
int m, n;
int dp[50][50], sum[50];
void init() {
memset(dp, 0, sizeof(dp));
for (int i = 0; i < 50; i++)
for (int j = 0; j <= i; j++)
if (!j || i == j)
dp[i][j] = 1;
else dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j];
}
int solve(int x) {
if (x <= 1)
return 0;
int ans = 0, ans0 = 0, ans1 = 0, len = 0;
while (x) {
sum[len++] = x & 1;
if (x & 1)
ans1++;
else ans0++;
x >>= 1;
}
for (int i = len - 1; i > 0; i--) { //从第一位到最高位的次位依次遍历
if (i & 1)//总数位为奇数 除去最高位的1,就剩下偶数位了
ans += ((1 << (i - 1)) - dp[i - 1][(i - 1) >> 1]) >> 1; //二进制中0和1个数不想等的数目，总情况减去剩余位中1和0相等的情况，比如i=5，剩下4位中两个0两个1的组合数
else ans += (1 << (i - 1)) >> 1;//总位数为偶数i，最高位为1,剩下的i-1位的组合数
}
if (ans0 >= ans1)//数本身二进制表示也满足条件
ans++;
ans0 = 0, ans1 = 1;
for (int i = len - 2; i >= 0; i--) {
if (!sum[i])
ans0++;
else { //遍历满足条件的插入法
for (int j = i; j >= 0 && j + ans0 + 1 >= i - j + ans1; j--)
ans += dp[i][j];
ans1++;
}
}
return ans;
}
int main() {
init();
while (~scanf("%d%d", &m, &n))
printf("%d\n", solve(n) - solve(m - 1));
return 0;
} Problem G Wonderprime Brands
题目链接：https://ac.nowcoder.com/acm/contest/984/G/
题意:找到一个大于等于n且由都不小于d位的两个素数组成的一个数。
思路:直接暴力，从n开始，一个一个的试。
Accepted Code:
#include <bits/stdc++.h>
#define ll long long
using namespace std;
ll d, n, mod = 10, minimum = 1;
bool prime(ll x) {
if (x < 2)
return false;
for (ll i = 2; i * i <= x; i++)
if (x % i == 0)
return false;
return true;
}
bool iskey(ll n) {
ll x = n / mod, y = n % mod, pow = mod;
if (n % mod / minimum)
if (prime(x) && prime(y))
return true;
y += x % 10 * pow;
x /= 10;
while (x >= minimum) {
if (prime(x) && prime(y))
return true;
pow *= 10;
y += x % 10 * pow;
x /= 10;
}
return false;
}
int main() {
scanf("%lld%lld", &d, &n);
for (ll i = 1; i < d; i++) {
mod *= 10;
minimum *= 10;
}
if (n < mod * minimum)
n = mod * minimum;
while (!iskey(n))
n++;
printf("%lld\n", n);
return 0;
} Problem H 数字游戏
题目链接：https://ac.nowcoder.com/acm/contest/984/H/
题意:求变动的次数。
思路:直接模拟。
Accepted Code:
#include <bits/stdc++.h>
using namespace std;
int main() {
int n, ans = 0;
scanf("%d", &n);
while (n != 1) {
if (n & 1)
n = n * 3 + 1;
else n >>= 1;
ans++;
}
printf("%d\n", ans);
return 0;
} Problem I Protecting the Flowers
题目链接：https://ac.nowcoder.com/acm/contest/984/I/
题意:有n头牛在吃花，每头牛牵走（避免吃花）要花费2*t秒（来回），每头牛吃花的速率是d，要你自己设计一个牵走牛的顺序，使被牛吃的花最少?
思路:贪心思想，设a，b是两头牛，我们想要的就是先送损失的花少的。
送a牛则b牛损失的花为2*t_a*d_b，送b牛则a牛损失的花为 2*t_b*d_a；
假设b牛吃得花比a牛多，那么就有关系式t_a*d_b < t_b*d_a，即d_b/t_b > d_a/t_a，所以这样就可以按照这个速率比时间的值来贪心，让被牛吃的花尽量少。
Accepted Code:
//正着算
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
struct edge {
int t, c;
bool operator < (const edge & r) const {
return t * r.c < r.t * c;
}
}a[N];
int main() {
int n;
scanf("%d", &n);
long long ans = 0, sum = 0;
for(int i = 0; i < n; i++) {
scanf("%d%d", &a[i].t, &a[i].c);
sum += a[i].c;
}
sort(a, a + n);
for (int i = 0; i < n; i++) {
sum -= a[i].c;
ans += 2ll * a[i].t * sum;
}
printf("%lld\n", ans);
return 0;
}
//反着算
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
struct edge {
int t, c;
bool operator < (const edge & r) const {
return t * r.c > r.t * c;
}
}a[N];
int main() {
int n;
scanf("%d", &n);
for(int i = 0; i < n; i++)
scanf("%d%d", &a[i].t, &a[i].c);
sort(a, a + n);
long long ans = 0, sum = 0;
for (int i = 0; i < n; i++) {
ans += 2ll * a[i].t * sum;
sum += a[i].c;
}
printf("%lld\n", ans);
return 0;
} Problem J 护城河
题目链接：https://ac.nowcoder.com/acm/contest/984/J/
题意:护城河总是笔直地连接在河道上的相邻的两股泉水且能包围所有的泉水，问护城河的总长最小是多少。
思路:凸包。
Accepted Code:
#include <bits/stdc++.h>
using namespace std;
struct edge {
int x, y;
} p[5005], s[5005];
int top = 0;
double ans = 0;
edge operator - (const edge& a, const edge& b) {
return (edge){a.x - b.x, a.y - b.y};
}
long long dis(edge a, edge b) {
return (a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y);
}
long long operator * (const edge& a, const edge& b) {
return a.x * b.y - a.y * b.x;
}
bool operator < (const edge& a, const edge& b) {
long long x = (a - p[1]) * (b - p[1]);
if (!x)
return dis(p[1], a) < dis(p[1], b);
else return x < 0;
}
int main() {
int n;
scanf("%d", &n);
for (int i = 1; i <= n; i++)
scanf("%d%d", &p[i].x, &p[i].y);
int t = 1;
for (int i = 1; i <= n; i++)
if (p[i].y < p[t].y || (p[i].y == p[t].y && p[i].x < p[t].x))
t = i; //扫描一遍，找到起始点
swap(p[1], p[t]);
sort(p + 2, p + n + 1);
s[++top] = p[1];
s[++top] = p[2];
for (int i = 3; i <= n; i++) {
while (top >= 2 && (s[top] - s[top - 1]) * (p[i] - s[top - 1]) >= 0)
top--;
s[++top] = p[i];
}
s[top + 1] = p[1];
for (int i = 1; i <= top; i++)
ans += sqrt(dis(s[i], s[i + 1]));
printf("%.2lf\n", ans);
return 0;
} Problem K 金币馅饼
题目链接：https://ac.nowcoder.com/acm/contest/984/K/
题意:从(1,1)到(r,c)，从左向右走，不能回头，问最多可以拿到多少金币。
思路:数塔变形;
dp[i][j] = max(dp[(i-1)~(i+1)][j - 1], dp[i][j]),
if(dp[i][j]!=0) dp[i][j]+=mp[i][j];
dp[i][j]!=0表示可以到达。
Accepted Code:
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 105;
int mp[MAXN][MAXN], dp[MAXN][MAXN], r, c;
int main() {
scanf("%d%d", &r, &c);
for (int i = 1; i <= r; i++)
for (int j = 1; j <= c; j++)
scanf("%d", &mp[i][j]);
memset(dp, 0, sizeof(dp));
dp[1][1] = mp[1][1];
for (int j = 2; j <= c; j++) {
for (int i = 1; i <= r; i++) {
for (int k = i - 1; k <= i + 1; k++)
if (dp[k][j - 1])
dp[i][j] = max(dp[k][j - 1], dp[i][j]);
if (dp[i][j])
dp[i][j] += mp[i][j];
}
}
printf("%d\n", dp[r][c]);
return 0;
} Problem L Catch That Cow
题目链接：https://ac.nowcoder.com/acm/contest/984/L/
题意:从s到t，可加1，可减1，可乘2，问多少步能到达。
思路:BFS。
Accepted Code:
#include <bits/stdc++.h>
using namespace std;
struct edge {
int x, l;
}u;
int vis[100005], arr[2] = {1, -1};
int BFS(int s, int t) {
int tx;
vis[s] = 1;
queue <edge> Q;
Q.push((edge){s, 0});
while (!Q.empty()) {
u = Q.front();
Q.pop();
if (!(u.x - t))
return u.l;
for (int i = 0; i < 3; i++) {
if (!i)
tx = u.x << 1;
else tx = u.x + arr[i - 1];
if (tx < 0 || tx > 100000 || vis[tx])
continue;
Q.push((edge){tx, u.l + 1});
vis[tx] = 1;
}
}
return -1;
}
int main() {
int s, t;
scanf("%d%d", &s, &t);
printf("%d\n", BFS(s, t));
return 0;
}
京公网安备 11010502036488号