A. Diagonal Walking
题意
将一个序列中所有的\('RU'\)或者\('UR'\)替换成\('D'\)，问最终得到的序列最短长度为多少。
思路
贪心
Code
#include <bits/stdc++.h>
#define F(i, a, b) for (int i = (a); i < (b); ++i)
#define F2(i, a, b) for (int i = (a); i <= (b); ++i)
#define dF(i, a, b) for (int i = (a); i > (b); --i)
#define dF2(i, a, b) for (int i = (a); i >= (b); --i)
#define maxn 110
using namespace std;
char s[maxn];
typedef long long LL;
int main() {
int n, cnt=0;
scanf("%d%s", &n, s);
bool used=0;
F(i, 1, n) {
if (!used && ((s[i]=='U'&&s[i-1]=='R') || (s[i]=='R'&&s[i-1]=='U'))) {
++cnt, used = true;
}
else used = false;
}
printf("%d\n", n-cnt);
return 0;
}
B. String Typing
题意
要得到一个字符串，有两种操作：
- 打印一个字符
- 将前面打印过的部分拷贝一遍跟在后面；
第二种方法最多只能使用一次。
问要打印一个字符串最少的操作次数。
思路
数据量暴力可过，但是还是拿来回忆了下后缀数组。
题目即是要求最长的\(A\)，使得原字符串\(S\)可表示为\(AAB\)的形式。
通过后缀数组的\(height\)数组，可以知道原串与每一个后缀的\(LCP\)长度，要能够拷贝，满足的条件是：
- 该后缀与原串的\(LCP\)长度\(\geq\)两者之间的起始位置差
- 该后缀与原串间的起始位置差\(*2\leq\)原串的长度
在所有满足条件的当中取个最大值即可。
Code
#include <bits/stdc++.h>
#define F(i, a, b) for (int i = (a); i < (b); ++i)
#define F2(i, a, b) for (int i = (a); i <= (b); ++i)
#define dF(i, a, b) for (int i = (a); i > (b); --i)
#define dF2(i, a, b) for (int i = (a); i >= (b); --i)
#define maxn 1010
using namespace std;
int wa[maxn], wb[maxn], wv[maxn], wt[maxn], h[maxn], rk[maxn], sa[maxn], n, m, tot, r[maxn];
char s[maxn];
bool cmp(int* r, int a, int b, int l) { return r[a] == r[b] && r[a+l] == r[b+l]; }
void init(int* r, int* sa, int n, int m) {
int* x=wa, *y=wb, *t, i, j, p;
for (i = 0; i < m; ++i) wt[i] = 0;
for (i = 0; i < n; ++i) ++wt[x[i] = r[i]];
for (i = 1; i < m; ++i) wt[i] += wt[i - 1];
for (i = n-1; i >= 0; --i) sa[--wt[x[i]]] = i;
for (j = 1, p = 1; p < n; j <<= 1, m = p) {
for (p = 0, i = n-j; i < n; ++i) y[p++] = i;
for (i = 0; i < n; ++i) if (sa[i] >= j) y[p++] = sa[i] - j;
for (i = 0; i < n; ++i) wv[i] = x[y[i]];
for (i = 0; i < m; ++i) wt[i] = 0;
for (i = 0; i < n; ++i) ++wt[wv[i]];
for (i = 1; i < m; ++i) wt[i] += wt[i - 1];
for (i = n-1; i >= 0; --i) sa[--wt[wv[i]]] = y[i];
t = x, x = y, y = t, x[sa[0]] = 0;
for (p = 1, i = 1; i < n; ++i) x[sa[i]] = cmp(y, sa[i], sa[i-1], j) ? p - 1 : p++;
}
for (i = 0; i < n; ++i) rk[sa[i]] = i;
int k = 0;
for (i = 0; i < n - 1; h[rk[i++]] = k) {
for (k = k ? --k : 0, j = sa[rk[i] - 1]; r[i+k] == r[j+k]; ++k);
}
}
int main() {
scanf("%d%s", &n, s);
F(i, 0, n) m = max(r[tot++]=s[i], m); r[tot++] = 0;
init(r, sa, tot, ++m);
int p = rk[0], maxx = 0;
dF2(i, p-1, 1) {
if (h[i+1]>=sa[i] && (sa[i]<<1)<=n) maxx = max(maxx, sa[i]);
h[i] = min(h[i], h[i+1]);
}
F(i, p+1, tot) {
if (h[i]>=sa[i] && (sa[i]<<1)<=n) maxx = max(maxx, sa[i]);
h[i+1] = min(h[i], h[i+1]);
}
printf("%d\n", maxx?n-maxx+1:n);
return 0;
}
C. Matrix Walk
题意
一个\(N\times M\)的方格纸，从左到右从上到下分别标号\(1,2,\ldots,N\times M\). 在每一个格子中只能向上下左右相邻的四个格子走。
现给出一个行走序列，要求给出一组合法的\(N,M\). 或者指出不存在。
思路
注意到，合法的序列差只可能为\(1\)或者定值\(M\).
在满足该条件的基础上，还要注意不能从最右边的格子\(+1\)，不能从最左边的格子\(-1\).
注意一些细节即可。
Code
#include <bits/stdc++.h>
#define F(i, a, b) for (int i = (a); i < (b); ++i)
#define F2(i, a, b) for (int i = (a); i <= (b); ++i)
#define dF(i, a, b) for (int i = (a); i > (b); --i)
#define dF2(i, a, b) for (int i = (a); i >= (b); --i)
#define maxn 200010
using namespace std;
typedef long long LL;
int a[maxn];
int main() {
int n, y;
scanf("%d", &n);
F(i, 0, n) scanf("%d", &a[i]);
F(i, 1, n) {
y = abs(a[i]-a[i-1]);
if (y==0) { puts("NO"); return 0; }
if (y>1) break;
}
if (y==1) { puts("YES"); printf("%d %d\n", 1, 1000000000); }
else {
F(i, 1, n) {
if (a[i]-a[i-1]==1) {
if (a[i-1]%y==0) { puts("NO"); return 0; }
}
else if (a[i]-a[i-1]==-1) {
if (a[i]%y==0) { puts("NO"); return 0; }
}
else if (abs(a[i]-a[i-1])!=y) { puts("NO"); return 0; }
}
puts("YES");
printf("%d %d\n", 1000000000, y);
}
return 0;
}
D. Fight Against Traffic
题意
给定一张图和起点\(s\)终点\(t\)，现在原图不相邻的两点之间加一条边，问有多少种加边方式会不导致\(s\)到\(t\)之间的距离缩短。
思路
若加边导致距离缩短，则必经过刚加的边，假设加的边为\((u,v)\)，原\(s,t\)的距离为\(d\)，图中所有顶点到\(s\)的最短路距离为\(dist1[]\)，到\(t\)的最短路距离为\(dist2[]\)则必有$$dist1[u]+1+dist2[v]\lt d$$或者
\[dist1[v]+1+dist2[u]\lt d
\]
\]
枚举边根据上述条件\(check\)即可。
Code
#include <bits/stdc++.h>
#define F(i, a, b) for (int i = (a); i < (b); ++i)
#define F2(i, a, b) for (int i = (a); i <= (b); ++i)
#define dF(i, a, b) for (int i = (a); i > (b); --i)
#define dF2(i, a, b) for (int i = (a); i >= (b); --i)
#define maxn 1010
struct Edge { int to, ne; }edge[maxn<<1];
int tot, ne[maxn], dist1[maxn], dist2[maxn];
bool vis[maxn], mp[maxn][maxn];
void add(int u, int v) {
edge[tot] = {v, ne[u]};
ne[u] = tot++;
}
struct node {
int v, c;
bool operator < (const node& nd) const { return c > nd.c; }
};
using namespace std;
typedef long long LL;
void dij(int src, int* dist) {
memset(vis, 0, sizeof vis);
memset(dist, 0x3f, maxn*sizeof(int));
vis[src] = true; dist[src] = 0;
priority_queue<node> q;
while (true) {
for (int i = ne[src]; ~i; i = edge[i].ne) {
int v = edge[i].to;
if (vis[v]) continue;
if (dist[src]+1<dist[v]) {
dist[v] = dist[src]+1;
q.push({v, dist[v]});
}
}
while (!q.empty() && vis[q.top().v]) q.pop();
if (q.empty()) break;
vis[src=q.top().v] = true;
}
}
int main() {
memset(ne, -1, sizeof ne);
int n, m, s, t, u, v;
scanf("%d%d%d%d", &n, &m, &s, &t);
F(i, 0, m) {
scanf("%d%d", &u, &v);
add(u, v), add(v, u);
mp[u][v] = mp[v][u] = true;
}
dij(s, dist1);
dij(t, dist2);
int cur = dist1[t], ans = 0;
F2(i, 1, n) {
F2(j, i+1, n) {
if (mp[i][j]) continue;
if (dist1[i]+1+dist2[j]>=cur && dist2[i]+1+dist1[j]>=cur) ++ans;
}
}
printf("%d\n", ans);
return 0;
}
E. Water Taps
题意
\(n\)个水龙头，流量分别为\(a_1,a_2,\ldots,a_n\)，温度分别为\(t_1,t_2,\ldots,t_n\)，打开若干个水龙头放水，假设放出的水量分别为\(x_1,x_2,\ldots,x_n\)，则得到的水温为
\[\frac{\sum_{i=1}^{n}x_it_i}{\sum_{i=1}^{n}x_i}
\]
\]
现要得到温度为\(T\)的水，求能放出的水量的最大值。
思路
因为
\[\frac{\sum_{i=1}^{n}x_it_i}{\sum_{i=1}^{n}x_i}=T
\]
\]
所以
\[\sum_{i=1}^{n}x_i(t_i-T)=0
\]
\]
因此将所有的\(t_i\)减去\(T\)之后，每个水龙头对温度的贡献就分为正贡献和负贡献。
正的放在一边，负的放在一边，因为能取小数，所以少的一边必能取满。
而要多的那边能取到尽量多的\(x\)，只要\(t\)尽量小，所以将\(t\)从小到大排序后取即可。
Code
#include <bits/stdc++.h>
#define F(i, a, b) for (int i = (a); i < (b); ++i)
#define F2(i, a, b) for (int i = (a); i <= (b); ++i)
#define dF(i, a, b) for (int i = (a); i > (b); --i)
#define dF2(i, a, b) for (int i = (a); i >= (b); --i)
#define maxn 200010
using namespace std;
typedef long long LL;
struct node {
LL x, t;
bool operator < (const node& nd) const { return t < nd.t; }
}a[maxn];
int main() {
freopen("in.txt", "r", stdin);
freopen("out.txt", "w", stdout);
int n, T;
scanf("%d%d", &n, &T);
F(i, 0, n) scanf("%I64d", &a[i].x);
F(i, 0, n) scanf("%I64d", &a[i].t), a[i].t-=T;
sort(a, a+n);
int p2=0, p1=-1;
double ans=0;
for (; p2<n; ++p2) {
if (a[p2].t<0) p1=p2;
else if (!a[p2].t) ans += a[p2].x;
if (a[p2].t > 0) break;
}
if (p1==-1||p2==n) printf("%.8f\n", ans);
else {
LL sum1=0, sum2=0;
dF2(i, p1, 0) sum1-=a[i].x*a[i].t;
F(i, p2, n) sum2+=a[i].x*a[i].t;
if (sum1>=sum2) {
F(i, p2, n) ans += a[i].x;
int i=p1;
for (; i >= 0; --i) {
if (sum2-a[i].x*(-a[i].t)<0) break;
ans += a[i].x;
sum2 += a[i].x*a[i].t;
}
if (i>=0&&sum2) ans += 1.0*sum2/(-a[i].t);
}
else {
dF2(i, p1, 0) ans += a[i].x;
int i=p2;
for (; i < n; ++i) {
if (sum1-a[i].x*a[i].t<0) break;
ans += a[i].x;
sum1 -= a[i].x*a[i].t;
}
if (i<n&&sum1) ans += 1.0*sum1/a[i].t;
}
printf("%.8f\n", ans);
}
return 0;
}
G. Castle Defense
题意
数轴上\(n\)个位置每个位置放有若干个弓箭手，弓箭手的攻击范围为左右大小为\(r\)的范围内。
一个点的防御程度定义为 该点能被多少个弓箭手攻击到。整条放线的防御程度定义为其上所有点防御程度的 最小值。
现可以在防线上增添\(k\)个弓箭手，要求使防线的防御程度最大化，求这个最大值。
思路
最小值的最大值，首先显然二分答案。
对于初始固定的弓箭手，一段一段的线段覆盖，可以用前缀和差分来处理。
之后二分答案时的\(check\)怎么进行呢？
用一个变量记录至今为止多放置了多少个弓箭手，从左到右扫
- 若位置\(i\)不够，则要在位置\(i+r+1\)补弓箭手
- 考虑到位置\(i\)时，要记得消除掉前面的\(i-r-1\)位置的影响
复杂度\(O(n\log n)\)
Code
#include <bits/stdc++.h>
#define F(i, a, b) for (int i = (a); i < (b); ++i)
#define F2(i, a, b) for (int i = (a); i <= (b); ++i)
#define dF(i, a, b) for (int i = (a); i > (b); --i)
#define dF2(i, a, b) for (int i = (a); i >= (b); --i)
#define maxn 500010
using namespace std;
typedef long long LL;
int n, d; LL k;
LL sum[maxn], a[maxn], add[maxn];
bool check(LL x) {
memset(add, 0, sizeof add);
LL temp=0, tot=0;
F2(i, 1, n) {
temp -= (i>=d+2 ? add[i-d-1] : 0);
if (x<=sum[i]+temp) continue;
int p = min(i+d, n);
add[p] = x - (sum[i] + temp);
tot += add[p];
if (tot>k) return false;
temp = x-sum[i];
}
return true;
}
int main() {
scanf("%d%d%I64d", &n, &d, &k);
F2(i, 1, n) {
scanf("%I64d", &a[i]);
int l=max(i-d, 1), r=min(n+1, i+d+1);
sum[l]+=a[i], sum[r]-=a[i];
}
F2(i, 1, n) sum[i] += sum[i-1];
LL l=0, r=2e18, ans;
while (l<=r) {
LL mid=l+r>>1;
if (check(mid)) ans=mid, l=mid+1;
else r=mid-1;
}
printf("%I64d\n", ans);
return 0;
}