找到所有每两个 0 之间 1 的数量，记住最大和次大的。答案就只
#include <bits/stdc++.h>
using namespace std;
string s;
int ans1 = 0; // 最大
int ans2 = 0; // 次大
// 用 now 更新最大次大
void freshAns(int now)
{
if (now >= ans1)
{
ans2 = ans1;
ans1 = now;
}
else if (now >= ans2)
ans2 = now;
}
int main()
{
cin >> s;
int now = 0;
for (int i = 0; i < s.size(); i++)
{
if (s[i] == '0')
{
freshAns(now);
now = 0;
continue;
}
// 此时 s[i] 必然是 1
if (i == 0 || s[i - 1] == '0')
now = 1;
else
now++;
}
freshAns(now);
cout << max(ans2, ans1 / 2);
return 0;
}
排序，从大到小。如果与前一个不相等，必然要花差那么多次变成相等的。这样就变成了和前一个相等，然后显然花一次去掉所有相等的，此时如果至少有三个（和前前一个也相等）就免费，否则就需要花费一次。
#include <bits/stdc++.h>
using namespace std;
int n;
int a[500000 + 5];
int main()
{
cin >> n;
for (int i = 1; i <= n; i++)
cin >> a[i];
sort(a + 1, a + n + 1);
int ans = 0;
for (int i = n; i >= 2; i--)
{
// 不相等时肯定要变为相等
if (a[i] != a[i - 1])
{
ans += a[i] - a[i - 1];
a[i] = a[i - 1];
}
// 相等之后，所有相等的只要减一次即可
// 所以三连的不管，只有二连的才去减少一次
if (i >= 3 && a[i] == a[i - 2])
ans += 0;
else
ans++;
}
ans += a[1];
cout << ans;
return 0;
}
60 分纯暴力广搜深搜都可以。每个点为起点检查能走多少个点。
满分超纲，需要先建图、然后缩点、然后在 DAG 上跑个拓扑序，用 bitset 优化合并得到每个点能到哪些点。
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 500;
int n;
int a[MAXN + 5][MAXN + 5];
// vis[i][j] 为 idx 的时候表示当前这轮访问过了
int idx, vis[MAXN + 5][MAXN + 5];
queue<pair<int, int>> q;
int bfs(int x, int y)
{
int res = 1;
q.push(make_pair(x, y));
vis[x][y] = idx;
while (!q.empty())
{
pair<int, int> now = q.front();
q.pop();
x = now.first;
y = now.second;
for (int i = -a[x][y]; i <= a[x][y]; i++)
{
// (x-a[x][y],i) (x+a[x][y],j)
// (i,y-a[x][y]) (i,y+a[x][y])
int xx, yy;
xx = x - a[x][y];
yy = y + i;
if (1 <= xx && xx <= n &&
1 <= yy && yy <= n &&
vis[xx][yy] != idx)
{
res++;
q.push(make_pair(xx, yy));
vis[xx][yy] = idx;
}
xx = x + a[x][y];
yy = y + i;
if (1 <= xx && xx <= n &&
1 <= yy && yy <= n &&
vis[xx][yy] != idx)
{
res++;
q.push(make_pair(xx, yy));
vis[xx][yy] = idx;
}
xx = x + i;
yy = y - a[x][y];
if (1 <= xx && xx <= n &&
1 <= yy && yy <= n &&
vis[xx][yy] != idx)
{
res++;
q.push(make_pair(xx, yy));
vis[xx][yy] = idx;
}
xx = x + i;
yy = y + a[x][y];
if (1 <= xx && xx <= n &&
1 <= yy && yy <= n &&
vis[xx][yy] != idx)
{
res++;
q.push(make_pair(xx, yy));
vis[xx][yy] = idx;
}
}
}
return res;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
{
cin >> a[i][j];
// 大于等于 n 的都等价于 n，都是访问不到任意位置
a[i][j] = min(a[i][j], n);
}
idx = 0;
int ans = 0;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
{
idx++;
ans = max(ans, bfs(i, j));
}
cout << ans;
return 0;
}
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100;
const int MAXTOT = MAXN * MAXN;
int n, tot;
int a[MAXN + 5][MAXN + 5];
int getId(int x, int y)
{
return (x - 1) * n + y;
}
vector<int> e[MAXTOT + 5];
// tarjan
int idx, dfn[MAXTOT + 5], low[MAXTOT + 5];
stack<int> s;
bool inS[MAXTOT + 5];
// 新图
int id[MAXTOT + 5]; // 原图点 i 缩到了新图的哪个点
int w[MAXTOT + 5]; // 新图一个点是之前多少个点
vector<int> ee[MAXTOT + 5]; // 新图存边
// 存 SCC
// int sccCnt;
// vector<int> scc[MAXTOT + 5];
void dfs(int u)
{
dfn[u] = low[u] = ++idx;
s.push(u);
inS[u] = true;
for (int v : e[u])
{
if (dfn[v] == 0)
{
dfs(v);
low[u] = min(low[u], low[v]);
}
else if (inS[v])
low[u] = min(low[u], dfn[v]);
}
// 当前点是某个 scc 的根
if (dfn[u] == low[u])
{
//++sccCnt;
while (s.top() != u)
{
id[s.top()] = u; // 缩到 u 上
w[u]++;
inS[s.top()] = false;
// scc[sccCnt].push_back(s.top());
s.pop();
}
// 处理 u
id[s.top()] = u; // 缩点
w[u]++;
inS[s.top()] = false;
// scc[sccCnt].push_back(s.top());
s.pop();
}
}
// 新图的 DAG 上 DP 的拓扑排序
int d[MAXTOT + 5]; // 新图每个点的入度
queue<int> q; // 拓扑排序广搜的队列
vector<int> order; // 拓扑序
bitset<MAXTOT + 5> can[MAXTOT + 5]; // 每个点能到哪些点
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
cin >> a[i][j];
// 建图
tot = n * n;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
{
int id = getId(i, j);
if (a[i][j] == 0)
continue;
// (i,j) -> (x,y)
if (i - a[i][j] >= 1)
{
int x = i - a[i][j];
for (int y = max(1, j - a[i][j]);
y <= min(n, j + a[i][j]);
y++)
e[id].push_back(getId(x, y));
}
if (i + a[i][j] <= n)
{
int x = i + a[i][j];
for (int y = max(1, j - a[i][j]);
y <= min(n, j + a[i][j]);
y++)
e[id].push_back(getId(x, y));
}
if (j - a[i][j] >= 1)
{
int y = j - a[i][j];
for (int x = max(1, i - a[i][j]);
x <= min(n, i + a[i][j]);
x++)
e[id].push_back(getId(x, y));
}
if (j + a[i][j] <= n)
{
int y = j + a[i][j];
for (int x = max(1, i - a[i][j]);
x <= min(n, i + a[i][j]);
x++)
e[id].push_back(getId(x, y));
}
}
// 缩点
for (int i = 1; i <= tot; i++)
if (dfn[i] == 0)
dfs(i);
// 建新图（反图）
for (int u = 1; u <= tot; u++)
{
if (id[u] == u)
can[u][u] = 1;
for (int v : e[u])
{
if (id[u] != id[v])
{
ee[id[v]].push_back(id[u]);
d[id[u]]++;
}
}
}
// 拓扑排序
for (int i = 1; i <= tot; i++)
if (id[i] == i && d[i] == 0)
q.push(i);
while (!q.empty())
{
int u = q.front();
q.pop();
order.push_back(u);
for (int v : ee[u])
{
d[v]--;
if (d[v] == 0)
q.push(v);
}
}
// 调试
/*
cout << "缩点后 id" << "\n";
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= n; j++)
cout << id[getId(i, j)] << " ";
cout << "\n";
}
cout << "缩点后 w" << "\n";
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= n; j++)
cout << w[getId(i, j)] << " ";
cout << "\n";
}
cout << "缩点后边" << "\n";
for (int i = 1; i <= tot; i++)
for (int j : ee[i])
cout << i << " " << j << "\n";
*/
// 合并每个点能到的点
for (int u : order)
{
for (int v : ee[u])
can[v] |= can[u];
}
// 找最大值
int ans = 0;
for (int i = 1; i <= tot; i++)
{
int now = 0;
for (int j = 1; j <= tot; j++)
if (can[i][j])
{
now += w[j];
}
ans = max(ans, now);
}
cout << ans << "\n";
return 0;
}
来源：https://codeforces.com/problemset/problem/1486/C2
分在题目描述送了，需要注意交互题不能些输入输出优化那两行代码，输入输出优化的 ios::sync_with_stdio(false); 会解除掉 cout 缓冲区和 printf 缓冲区的关联，导致 fflush(stdout) 无法刷新 cout 的缓冲区。如果写了 ios::sync_with_stdio(false); 那么 cout 只能用 cout.flush() 刷新缓冲区。直接不写输入输出优化是最方便的。
保证了次大值在最左边，所以可以直接二分，每次问 ? 1 mid 时，如果答案是 1 就说明最大值在左半边，否则说明最大值在右半边。
#include <bits/stdc++.h>
using namespace std;
int query(int l, int r)
{
if (l == r)
return l;
int res;
cout << "? " << l << " " << r << "\n";
cout.flush();
cin >> res;
return res;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
int n;
cin >> n;
int l = 1;
int r = n;
int ans = 0;
while (l <= r)
{
int mid = (l + r) / 2;
if (query(1, mid) == 1)
{
ans = mid;
r = mid - 1;
}
else
{
l = mid + 1;
}
}
cout << "! " << ans << "\n";
cout.flush();
return 0;
}
对于区间 l r，先问 ? l r 得到次大值位置，然后问一下次大值那半边的次大值。就可以分析出最大值在左半边还是右半边了，所以两次询问就可以把区间二分了。这样一共需要 的询问次数。
#include <bits/stdc++.h>
using namespace std;
int query(int l, int r)
{
if (l == r)
return l;
int res;
cout << "? " << l << " " << r << "\n";
cout.flush();
cin >> res;
return res;
}
void outAns(int ans)
{
cout << "! " << ans << "\n";
cout.flush();
exit(0);
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
int n;
cin >> n;
int l = 1;
int r = n;
// 这个二分保证答案在区间中
while (l <= r)
{
int len = r - l + 1;
if (len == 1)
outAns(l);
int pos = query(l, r); // 区间次大值位置
if (len == 2)
{
if (pos == l)
outAns(r);
else
outAns(l);
}
int mid = (l + r) / 2;
if (pos <= mid)
{
// 次大值在左半边
if (mid - l + 1 >= 2)
{
// 左边除了次大值还有其他的，判断最大值在不在左边
int leftPos = query(l, mid);
if (leftPos == pos)
r = mid;
else
l = mid + 1;
}
else
{
// 左边只有次大值
l = mid + 1;
}
}
else
{
// 次大值在右半边
if (r - mid >= 2)
{
// 右边除了次大值还有其他的，判断最大值在不在右边
int rightPos = query(mid + 1, r);
if (rightPos == pos)
l = mid + 1;
else
r = mid;
}
else
{
// 右边只有次大值
r = mid;
}
}
}
return 0;
}
先问一次 ? 1 n 确定最次值的位置 pos，然后问 ? 1 pos 确定最大值在 还是 这就变成了子任务 2 的模式，直接每次包上 pos 来二分即可。
参考代码（原题官方题解代码）：
#include <bits/stdc++.h>
using namespace std;
int ask(int l, int r) {
if (l >= r) return -1;
cout << "? " << l + 1 << ' ' << r + 1 << endl;
int ans;
cin >> ans;
return ans - 1;
}
int main() {
int n;
cin >> n;
int smax = ask(0, n - 1);
if (smax == 0 || ask(0, smax) != smax) {
int l = smax, r = n - 1;
while (r - l > 1) {
int m = (l + r) / 2;
if (ask(smax, m) == smax) {
r = m;
} else {
l = m;
}
}
cout << "! " << r + 1 << endl;
} else {
int l = 0, r = smax;
while (r - l > 1) {
int m = (l + r) / 2;
if (ask(m, smax) == smax) {
l = m;
} else {
r = m;
}
}
cout << "! " << l + 1 << endl;
}
return 0;
}