A.牛能和宝石
题意：
给定a、b两组数字序列，询问你通过任意排序后，max(ai+bi)的最小值
题解：
一个升序、一个降序，遍历更新最大值即可
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int maxn = 1e5 + 5;
const int INF = 0x3f3f3f3f;
ll a[maxn],b[maxn];
int main()
{
int n;
scanf("%d",&n);
for(int i=0;i<n;i++)
scanf("%lld",&a[i]);
for(int i=0;i<n;i++)
scanf("%lld",&b[i]);
ll mx= 0;
sort(a,a+n);
sort(b,b+n);
for(int i=0;i<n;i++)
mx=max(mx,a[i]+b[n-i-1]);
printf("%lld\n",mx);
return 0;
}B.牛妹和01串
题意：
牛妹有一个01串，串中只包含0和1，牛妹要把这个串划分成连续的m段，使得每一段至少包含一个0和一个1。牛妹想最大化m，m最大是多少呢？
题解：
贪心，遍历一遍，如果有0和1就划分成一段
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int maxn = 1e5 + 5;
const int INF = 0x3f3f3f3f;
ll a[maxn],b[maxn];
int main()
{
string s;
cin >> s;
int f1=0,f2=0;
int ans=0;
for(int i=0;i<s.length();i++)
{
if(s[i]=='1')
{
if(!f1)
f2=1;
else
{
ans++;
f1=f2=0;
}
}
else if(s[i]=='0')
{
if(!f2)
f1=1;
else
{
ans++;
f1=f2=0;
}
}
}
printf("%d\n",ans);
return 0;
}C.矩阵消除游戏
题意：
见题面
题解：
考虑到n、m均不超过15，只要枚举列的情况，剩余的行sort前几个即可
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int maxn = 1e5 + 5;
const int INF = 0x3f3f3f3f;
int a[16][16], sum[16];
int main()
{
int n, m, k;
scanf("%d%d%d", &n, &m, &k);
k = min(k, min(n, m));
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
scanf("%d", &a[i][j]);
int ans = 0;
for (int i = 0; i < (1 << m); i++)
{
int tot = __builtin_popcount(i);
if (tot > k)
continue;
memset(sum, 0, sizeof(sum));
int res = 0;
for (int j = 1; j <= n; j++)
for (int k = 0; k < m; k++)
{
if ((i >> k) & 1)
res += a[j][k + 1];
else
sum[j] += a[j][k + 1];
}
sort(sum + 1, sum + n + 1, greater<int>());
for (int j = 1; j <= k - tot; j++)
res += sum[j];
ans = max(ans, res);
}
printf("%d\n", ans);
return 0;
}D.迷宫（DP）
题意：
见题面
题解：
分析可以发现不会向左或者向上走，否则只会在一个区域内反复横跳，所以只要考虑向右和向下的情况，优先考虑向右，求最少的操作次数，很显然是用DP，具体状态转移方程：
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int maxn = 1005;
const int INF = 0x3f3f3f3f;
char s[maxn][maxn];
int dp[maxn][maxn];
int main()
{
int n, m;
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i++)
scanf("%s", s[i] + 1);
memset(dp, INF, sizeof(dp));
dp[1][1] = 0;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
if (s[i][j] == '0')
{
if (j < m && s[i][j + 1] == '0')
dp[i][j + 1] = min(dp[i][j + 1], dp[i][j]);
if (i < n && s[i + 1][j] == '0')
{
if (j == m || s[i][j + 1] == '1')
dp[i + 1][j] = min(dp[i + 1][j], dp[i][j]);
else
dp[i + 1][j] = min(dp[i + 1][j], dp[i][j] + 1);
}
}
if (dp[n][m] == INF)
puts("-1");
else
printf("%d\n", dp[n][m]);
return 0;
}E.最大GCD
题意：
见题面
题解：
一个区间和x的最大gcd一定是区间内某一个数和x的gcd。所以我们预处理一下每个因子所在的全部下标。然后对于x的全部因子都check一遍取最大值即可。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int maxn = 1e5 + 5;
const int INF = 0x3f3f3f3f;
struct node
{
int l, r, id;
bool operator<(const node &C) const
{
return r < C.r;
}
};
int ans[maxn];
vector<int> v[maxn];
vector<node> p[maxn];
int main()
{
int n, q;
scanf("%d%d", &n, &q);
for (int i = 1, x; i <= n; i++)
{
scanf("%d", &x);
for (int j = 1; j * j <= x; j++)
{
if (x % j == 0)
{
v[j].push_back(i);
if (x / j != j)
v[x / j].push_back(i);
}
}
}
for (int i = 1; i <= q; i++)
{
int l, r, x;
scanf("%d%d%d", &l, &r, &x);
for (int j = 1; j * j <= x; j++)
{
if (x % j == 0)
{
p[j].push_back(node{l, r, i});
if (x / j != j)
p[x / j].push_back(node{l, r, i});
}
}
}
for (int i = 1; i <= 100000; i++)
{
if (!v[i].size())
continue;
int k = 0;
sort(p[i].begin(), p[i].end());
while (k < p[i].size() && p[i][k].r < v[i][0])
k++;
for (int j = 0; j < v[i].size() - 1; j++)
{
while (k < p[i].size() && p[i][k].r < v[i][j + 1])
{
if (p[i][k].l <= v[i][j])
ans[p[i][k].id] = max(ans[p[i][k].id], i);
k++;
}
}
while (k < p[i].size())
{
if (p[i][k].l <= v[i][v[i].size() - 1])
ans[p[i][k].id] = max(ans[p[i][k].id], i);
k++;
}
}
for (int i = 1; i <= q; i++)
printf("%d\n", ans[i]);
return 0;
}F.XOR TREE（树剖）
题意：
见题面
题解：
据两个相同数字异或一遍为0的规律，我们不难发现如果路径长度是奇数就是所有点权值的异或值，如果路径长度是偶数就是隔一个点取异或值。所以我们可以树剖一下，然后根据节点深度维护两棵线段树分别记录奇数深度和偶数深度的路径异或和即可。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int maxn = 2e5 + 5;
const int INF = 0x3f3f3f3f;
int read()
{
int x = 0;
char c = getchar();
while (c < '0' || c > '9')
c = getchar();
while (c >= '0' && c <= '9')
x = (x << 1) + (x << 3) + c - '0', c = getchar();
return x;
}
int a[maxn], n, q;
int head[maxn], cnt;
int f[maxn], dep[maxn], siz[maxn], son[maxn], dfn[maxn], top[maxn], id[maxn], tot;
struct Edge
{
int to, next;
} E[maxn << 1];
void init()
{
memset(head, -1, sizeof(head));
cnt = tot = 0;
}
void addedge(int u, int v)
{
E[cnt].to = v;
E[cnt].next = head[u];
head[u] = cnt++;
}
void dfs1(int u, int fa, int d)
{
f[u] = fa;
dep[u] = d;
siz[u] = 1;
for (int i = head[u]; ~i; i = E[i].next)
{
int v = E[i].to;
if (v == fa)
continue;
dfs1(v, u, d + 1);
siz[u] += siz[v];
if (siz[son[u]] < siz[v])
son[u] = v;
}
}
void dfs2(int u, int tp)
{
top[u] = tp;
dfn[u] = ++tot;
id[tot] = u;
if (son[u] != 0)
dfs2(son[u], tp);
for (int i = head[u]; ~i; i = E[i].next)
{
int v = E[i].to;
if (v == f[u] || v == son[u])
continue;
dfs2(v, v);
}
}
struct node
{
int l, r, sum;
} tr[2][maxn << 2];
void pushup(int rt, int idx)
{
tr[idx][rt].sum = tr[idx][rt << 1].sum ^ tr[idx][rt << 1 | 1].sum;
}
void build(int l, int r, int rt, int idx)
{
tr[idx][rt].l = l;
tr[idx][rt].r = r;
if (l == r)
{
if ((dep[id[l]] & 1) == (idx & 1))
tr[idx][rt].sum = a[id[l]];
else
tr[idx][rt].sum = 0;
return;
}
int mid = l + r >> 1;
build(l, mid, rt << 1, idx);
build(mid + 1, r, rt << 1 | 1, idx);
pushup(rt, idx);
}
void update(int l, int r, int rt, int pos, int val, int idx)
{
if (l == r)
{
tr[idx][rt].sum = val;
return;
}
int mid = l + r >> 1;
if (pos <= mid)
update(l, mid, rt << 1, pos, val, idx);
else
update(mid + 1, r, rt << 1 | 1, pos, val, idx);
pushup(rt, idx);
}
int query(int rt, int l, int r, int L, int R, int idx)
{
if (L <= l && r <= R)
return tr[idx][rt].sum;
int ans = 0;
int mid = l + r >> 1;
if (L <= mid)
ans ^= query(rt << 1, l, mid, L, R, idx);
if (mid < R)
ans ^= query(rt << 1 | 1, mid + 1, r, L, R, idx);
return ans;
}
int qRange(int u, int v)
{
int ans = 0;
if (abs(dep[u] - dep[v]) & 1)
{
while (top[u] != top[v])
{
if (dep[top[u]] < dep[top[v]])
swap(u, v);
ans ^= query(1, 1, n, dfn[top[u]], dfn[u], 0);
ans ^= query(1, 1, n, dfn[top[u]], dfn[u], 1);
u = f[top[u]];
}
if (dep[u] > dep[v])
swap(u, v);
ans ^= query(1, 1, n, dfn[u], dfn[v], 0);
ans ^= query(1, 1, n, dfn[u], dfn[v], 1);
}
else
{
int idx = (dep[u] + 1) & 1;
while (top[u] != top[v])
{
if (dep[top[u]] < dep[top[v]])
swap(u, v);
ans ^= query(1, 1, n, dfn[top[u]], dfn[u], idx);
u = f[top[u]];
}
if (dep[u] > dep[v])
swap(u, v);
ans ^= query(1, 1, n, dfn[u], dfn[v], idx);
}
return ans;
}
int main()
{
init();
n = read();
q = read();
for (int i = 1; i <= n; i++)
a[i] = read();
for (int i = 1; i < n; i++)
{
int u = read();
int v = read();
addedge(u, v);
addedge(v, u);
}
dfs1(1, 0, 1);
dfs2(1, 1);
build(1, n, 1, 0);
build(1, n, 1, 1);
while (q--)
{
int op = read(), u = read(), v = read();
if (op == 1)
update(1, n, 1, dfn[u], v, dep[u] & 1);
else
printf("%d\n", qRange(u, v));
}
return 0;
}
京公网安备 11010502036488号