#835 div4
https://codeforces.com/contest/1760
D:
题目:
给出一个长度为 n 的序列,问你这个序列的大小变化是否符合山谷的形状
思路:
不难发现,对于山谷来说,如果说上升了之后一定不会再下降了。
代码
void solved()
{
cin >> n;
for(int i = 0; i < n; i++) cin >> a[i];
bool flag = false;
for(int i = 0; i < n - 1; i++)
{
if(a[i] < a[i + 1]) flag = true;
if(flag && a[i + 1] < a[i])
{
cout << "NO" << endl;
return;
}
}
cout << "YES" << endl;
}
E:
题目:
现在存在一个长度为 n的二进制数组,你最多可以进行一次操作
操作:
反转一个元素。
现在问你最多操作一次后,能够得到的最大逆序对是多少。
思路:
对于 0 变 1 来说,影响为 减去 前面 1的 个数和 加上后面 0 的个数
所以只对前缀 1和 后缀0 有影响。维护即可
代码
void solved()
{
cin >> n;
for(int i = 1; i <= n; i ++) cin >> a[i];
for(int i = 0; i <= n + 1; i ++) qz1[i] = hz0[i] = 0;
int sum0 = 0;
int ans = 0;
for(int i = n; i >= 1; i--)
{
if(a[i] == 0) hz0[i] = hz0[i + 1] + 1;
else hz0[i] = hz0[i + 1];
}
for(int i = 1; i <= n ;i++)
{
if(a[i] == 1) qz1[i] = qz1[i - 1] + 1;
else qz1[i] = qz1[i - 1];
}
for(int i = n; i >= 1; i--)
{
if(a[i] == 1) ans += hz0[i + 1];
}
int res = ans;
for(int i = 1; i <= n; i++)
{
if(a[i] == 0)
{
res = max(res, ans - qz1[i - 1] + hz0[i + 1]);
}else
{
res = max(res, ans - hz0[i + 1] + qz1[i - 1]);
}
}
cout <<res << endl;
}
F:
题目:
现在存在 n 个任务,每个任务都有一个价值, 每天只能完成一个任务,并且完成一个任务后存在一个间隔。
现在给出 d 天 和 c价值。现在你可以任意规定 k, k 代表完成一个任务后再完成这个任务需要的间隔。
但是保证在 d 天内获得 至少 c 个金币,求出最大的 k。
思路:
不难发现, k 越大可能得到的价值越多。存在二段性,我们可以二分 k 来 判断是否合法。
因为每个任务都存在一个间隔,我们肯定优先做价值大的,所以做任务的顺序类似于一个循环节。
根据循环节来check
代码
int check(int mid)
{
int sum = 0;
int s = 0;
for(int i = 0; i < min(mid +1, n); i++) s += a[i];
sum += s * (d / (mid + 1));
for(int i = 0; i < d % (mid + 1); i++)
{
if(i < n) sum += a[i];
}
return sum;
}
void solved()
{
cin >> n >> c >> d;
int sum = 0;
for(int i = 0; i < n; i++) cin >> a[i];
sort(a, a + n, bmp);
if(a[0] * d < c)
{
cout << "Impossible" << endl;
return;
}
int l = 0, r = 1e16;
while(l < r)
{
int mid = l + r + 1>> 1;
if(check(mid) >= c) l = mid;
else r = mid - 1;
}
if(l < 1e16)
cout << l << endl;
else cout << "Infinity" << endl;
}
G:
题目:
现在给出 n 个点 和 n - 1 条边, 每条边都有一个权重。
现在存在两个点 a 和 b, 你要从 a 走到 b, 并且经过的边都要异或起来,如果能够到 b 异或值为 0,那么是YES。
并且当你到任何一个点时候,你存在一次操作机会可以跳到任何一个点。
思路:
如果不存在跳跃,我们只需要跑一边 dfs,到 b 异或值为 0即可,但是跳跃意味着,从 a 到 c 点 然后跳到 d点 到 b 点。
并且 c 点是可以跳跃的,所以我们只需要跑一边从 a 点,记录一下前缀异或出现,如果说从 b 再跑一遍出现了这个数字,那么我们一定可以,从 a 跑到 c 跳到 d 再到 b
代码
void dfs(int u, int fa, int sum)
{
may[sum] = 1;
for(int i = h[u]; i != -1; i = ne[i])
{
int j = e[i];
if(j == fa) continue;
if(j == ed) continue;
dfs(j, u, sum ^ w[i]);
}
}
bool dfs2(int u, int fa, int sum)
{
for(int i = h[u]; i != -1; i = ne[i])
{
int j = e[i];
if(j == fa) continue;
if(may[sum ^ w[i]] == 1) return true;
if(dfs2(j, u, sum ^ w[i])) return true;
}
return false;
}
void solved()
{
may.clear();
memset(h, -1, sizeof h);
int n;
cin >> n >> st >> ed;
for(int i = 0; i < n - 1; i++)
{
int a, b, c;
cin >> a >> b >> c;
add(a,b ,c), add(b, a, c);
}
dfs(st, -1, 0);
may[0] = 1;
if(dfs2(ed, -1, 0)) cout << "YES" << endl;
else cout << "NO" << endl;
}