1.Searching Local Mininum
题目类型
神奇二分 + 递增递减的数学知识 这是一道交互型题目 感觉挺有趣的
题目大意
- 有n个数字，数字范围为1~n且不重复。
- 有数字流传输过来，你预先不知道其位置，但是你可以在接收数字之前给其定下位置。
- 问：你能否在确定小于等于100个数字位置之前找到一个数字，这个数字 idx 满足 a[idx] 为波谷位置
题目思路
数据范围大 肯定不能暴力 用二分来找
如果 [l, n] 左边递减右边递增 那么在 [l, n] 一定存在波谷
因为a[0] 和 a[n] 为正无穷 故二分找 a[mid] 使得 a[mid] < a[mid - 1] && a[mid] < a[mid + 1]
代码实现
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e5 + 10;
int n;
int a[N];
void get(int x)
{
if (x < 1 || x > n || a[x]) return;
cout << "? " << x << endl;
fflush(stdout);
cin >> a[x];
}
signed main()
{
cin.tie(0); cout.tie(0);
ios::sync_with_stdio(false);
cin >> n;
a[0] = a[n + 1] = N;
int l = 1, r = n;
while (l < r)
{
int mid = l + r >> 1;
get(mid), get(mid + 1);
if (a[mid] < a[mid + 1]) r = mid;
else l = mid + 1;
}
cout << "! " << r << endl;
return 0;
}
2.滑雪与时间胶囊
题目类型
最小生成树 + 图的遍历
题目思路
因为只能由高到低 所以需要遍历出从1能到达那些点 不能盲目的进行Kruskal()
要先用dfs把从1能到的点筛选出来, 加边的时候不要else if 因为当H[a] == H[b]的时候, 是双向边
然后用Kruskal算法求解
代码实现
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 1e6 + 10, M = 3e6 + 10;
int e[M], ne[M], h[N], idx;
int p[N], H[N];
int n, m;
LL cnt, res;
bool vis[N];
struct Edge
{
int u, v, w;
bool operator < (const Edge &W)const
{
if (H[v] != H[W.v]) return H[v] > H[W.v];
return w < W.w;
}
}edge[M];
void add(int a, int b)
{
e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
}
int find(int a)
{
if (p[a] != a) p[a] = find(p[a]);
return p[a];
}
void dfs(int nu)
{
vis[nu] = 1;
cnt ++;
for (int i = h[nu]; i != -1; i = ne[i])
{
int j = e[i];
if (vis[j]) continue;
dfs(j);
}
}
void Kruskal()
{
sort(edge, edge + m);
for (int i = 1; i <= n; i ++ ) p[i] = i;
for (int i = 0; i < m; i ++ )
{
auto e = edge[i];
if (!vis[e.u] || !vis[e.v]) continue;
int pu = find(e.u), pv = find(e.v);
if (pu != pv)
{
p[pu] = pv;
res += (LL)e.w;
}
}
}
int main()
{
cin.tie(0); cout.tie(0);
ios::sync_with_stdio(false);
memset(h, -1, sizeof h);
cin >> n >> m;
for (int i = 1; i <= n; i ++ ) cin >> H[i];
for (int i = 0; i < m; i ++ )
{
int a, b, c;
cin >> a >> b >> c;
if (H[a] >= H[b]) edge[i] = {a, b, c}, add(a, b);
if (H[a] <= H[b]) edge[i] = {b, a, c}, add(b, a);
}
dfs(1);
Kruskal();
cout << cnt << ' ' << res << endl;
return 0;
}
3.Painting the Array I
题目类型
贪心 + 二分查找
题目思路
- 当 p == q 时 a[i] 加到哪都行
- 当 p == a[i] q != a[i] 时 要加在a2 中 同理知 p != a[i] q == a[i] 时 加在 a1 中
- 当都不相同时候 要找一下 我们可以求出p和q在a[i]之后出现的离i最近的位置f[p][pp]和f[q][qq]，如果f[p][pp]<f[q][qq]，那么就将a[i]放入a1中，否则放入a2中。
这里只需要举一个简单的小例子：
假设p=1，q=2，a中还有[3,2,2,1]这三个元素，如果将3放入a1中，那么答案只能再加3。但是如果将3放入a2中，答案可以再加4。
代码实现
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int a[N], n, num[N];
vector<int> f[N];
int main()
{
cin.tie(0); cout.tie(0);
ios::sync_with_stdio(false);
int res = 0;
cin >> n;
for (int i = 1; i <= n; i ++ )
{
cin >> a[i];
f[a[i]].push_back(i);
}
int p = 0, q = 0;
for (int i = 1; i <= n; i ++ )
{
if (p == a[i] && q == a[i]) continue;
else if (p != a[i] && q == a[i])
{
p = a[i];
res ++ ;
}
else if (p == a[i] && q != a[i])
{
q = a[i];
res ++ ;
}
else
{
int pp = lower_bound(f[p].begin(), f[p].end(), i) - f[p].begin();
int qq = lower_bound(f[q].begin(), f[q].end(), i) - f[q].begin();
if (pp >= f[p].size()) q = a[i];
else if (qq >= f[q].size()) p = a[i];
else if (f[p][pp] > f[q][qq]) q = a[i];
else p = a[i];
res ++ ;
}
}
cout << res << endl;
return 0;
}
4.蒙德里安的梦想
推荐题解 结合代码实现的注释来看
题目类型
状态压缩DP
代码实现
#include <iostream>
#include <algorithm>
#include <vector>
#include <cstring>
using namespace std;
typedef long long LL;
const int N = 12, M = 1 << N;
int n, m;
LL f[N][M];
bool st[M];
vector<vector<int>> status(M);
int main()
{
while (cin >> n >> m, n || m)
{
// 对每列进行筛选 看中间空余0的个数是否为偶数
for (int i = 0; i < 1 << n; i ++ )
{
int cnt = 0;
bool isValid = true;
for (int j = 0; j < n; j ++ )
{
if ((i >> j) & 1)
{
if (cnt & 1)
{
isValid = false;
break;
}
cnt = 0;
}
else cnt ++ ;
}
if (cnt & 1) isValid = false;
st[i] = isValid;
}
// 保证没有重叠横块 以及 保证i和i - 1的横块组合起来之后的i处空余0是否为偶数
for (int i = 0; i < 1 << n; i ++ )
{
status[i].clear();
for (int j = 0; j < 1 << n; j ++ ) // j是 第i - 1列的 所有情况
{
if ((i & j) == 0 && st[i | j])
status[i].push_back(j);
}
}
memset(f, 0, sizeof f);
f[0][0] = 1; // 满足条件的只有全部为竖块
for (int i = 1; i <= m; i ++ )
for (int j = 0; j < 1 << n; j ++ )
for (auto k : status[j])
f[i][j] += f[i - 1][k];
cout << f[m][0] << endl;
}
return 0;
}
5.耍杂技的牛
题目类型
贪心 + 公式推导
题目思路
代码实现
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 50010;
int n;
pair<long, long> cow[N];
int main()
{
cin >> n;
for (int i = 0; i < n; i ++ )
{
long long w, s;
cin >> w >> s;
cow[i] = {w + s, w};
}
sort(cow, cow + n);
long long res = -2e9, sum = 0;
for (int i = 0; i < n; i ++ )
{
long long w = cow[i].second, s = cow[i].first - w;
res = max(res, sum - s);
sum += w;
}
cout << res << endl;
return 0;
}
6.Minimum Grid Path
题目类型
贪心 (貌似dp也可以做)
题目思路
用pre记录所有已用到的所有c * 1然后用minr minu来分别记录在向右和向上所用到的c中的最小值
用up right来记录向上和向右所用过几个c 然后 pre + (up + 1) * minu + (right + 1) * minr即为当前最小值
然后更新res 贪心前缀的最小值
代码易懂
代码实现
#include <iostream>
#include <algorithm>
#define int long long
using namespace std;
const int N = 2e5 + 10;
int n, res;
int pre;
int minu, minr, up, rig;
void init()
{
res = 1e15;
pre = 0;
up = rig = 0;
minu = minr = 1e9 + 10;
}
signed main()
{
int t;
cin >> t;
while (t -- )
{
cin >> n;
init();
int num;
for (int i = 0; i < n; i ++ )
{
cin >> num;
pre += num;
if (i & 1)
{
minu = min(minu, num);
up ++ ;
}
else
{
minr = min(minr, num);
rig ++ ;
}
res = min(res, pre + (n - up) * minu + (n - rig) * minr);
}
cout << res << endl;
}
return 0;
}
