solved
题意：给出一个字符串，可以移掉最多一个字符，在所有可能性中选取一个字典序最小的。
思路：显然，一定可以移掉一个字符，如果移掉的字符的后一个字符大于当前字符，那么字典序会变大。
那只需要从左往右，遇到第一个后面的字符大于当前字符的就可以移掉该字符。
#include <bits/stdc++.h>
using namespace std; #define N 200010
int n;
char s[N]; int main()
{
while (scanf("%d%s", &n, s + ) != EOF)
{
int pos = n;
for (int i = ; i < n; ++i) if (s[i + ] < s[i])
{
pos = i;
break;
}
s[pos] = ;
printf("%s", s + );
printf("%s\n", s + pos + );
}
return ;
}
solved
题意：给出一个数n，如果n = 0,那么程序就结束。否则减去这个数的最小质因子，再循环执行该算法，问程序会执行多少步。
思路：
我们假设数$n的最小质因子为x, 令 y = \frac{n}{x}$
如果$y$是偶数，那么答案就很明显，直接不断减去2
如果$y是奇数，那么我们先减去一个x， 那么就会变成 n = (y - 1) \cdot x$
$此时 (y - 1) 显然为偶数 就不断减去2就可以$
#include <bits/stdc++.h>
using namespace std; #define ll long long
ll x; ll find(ll x)
{
ll limit = sqrt(x + );
for (ll i = ; i <= limit; ++i) if (x % i == ) return i;
return x;
} int main()
{
while (scanf("%lld", &x) != EOF)
{
ll y = find(x); ll z = x / y;
printf("%lld\n", (z - ) * y / + );
}
return ;
}
solved
题意：给出一个$d, 找a + b = d and a \cdot b = d$
思路：将$a = d - b$ 代入第二个式子，解二元一次方程。
#include <bits/stdc++.h>
using namespace std; int t, d; int main()
{
scanf("%d", &t);
while (t--)
{
scanf("%d", &d);
if (d * d < * d) puts("N");
else
{
double delta = sqrt(d * d - * d);
double b = (d - delta) / ;
double a = d - b;
printf("Y %.10f %.10f\n", a, b);
}
}
return ;
}
Upsolved
题意：给出一个无向图，定义$d_i为 1 - i 的最短路径$，定义一个点为好点为1 - 这个点的最短路径为 $d_i$，最多保留k条边，使得剩下的点中好点最多。
思路：Dijkstra构造最短路树，对最短路树DFS或者BFS皆可，按这个搜索顺序选取边，显然每选取一条边都会增加一个好点，所以最后好点的数量显然为$min(k + 1, n)$
#include <bits/stdc++.h>
using namespace std; #define ll long long
#define INFLL 0x3f3f3f3f3f3f3f3f
#define N 300010
int n, m, k; struct Edge
{
int u, v; ll w;
Edge() {}
Edge(int u, int v, ll w) : u(u), v(v), w(w) {}
}edge[N]; struct graph
{
struct node
{
int to, nx, id; ll w;
node () {}
node (int to, int nx, int id, ll w) : to(to), nx(nx), id(id), w(w) {}
}a[N << ];
int head[N], pos;
void init() { memset(head, , sizeof head); pos = ; }
void add(int u, int v, int id, ll w)
{
a[++pos] = node(v, head[u], id, w); head[u] = pos;
a[++pos] = node(u, head[v], id, w); head[v] = pos;
}
}G, g;
#define erp(G, u) for (int it = G.head[u], v = G.a[it].to, w = G.a[it].w; it; it = G.a[it].nx, v = G.a[it].to, w = G.a[it].w) struct Dijkstra
{
struct node
{
int to; ll w;
node () {}
node (int to, ll w) : to(to), w(w) {}
bool operator < (const node &r) const { return w > r.w; }
};
struct DIST
{
ll w; int id;
DIST() {}
DIST(ll w, int id) : w(w), id(id) {}
}dist[N]; bool used[N];
void solve()
{
for (int i = ; i <= n; ++i)
{
dist[i] = DIST(INFLL, -);
used[i] = false;
}
dist[] = DIST(, -);
priority_queue <node> q; q.emplace(, );
while (!q.empty())
{
int u = q.top().to; q.pop();
if (used[u]) continue;
used[u] = ;
int id = dist[u].id; if (id != -) g.add(edge[id].u, edge[id].v, id, edge[id].w);
erp(G, u) if (!used[v] && dist[v].w > dist[u].w + w)
{
dist[v].w = dist[u].w + w;
dist[v].id = G.a[it].id;
q.emplace(v, dist[v].w);
}
}
}
}dij; vector <int> res;
void DFS(int u, int fa)
{
erp(g, u) if (v != fa && res.size() < k)
{
res.push_back(g.a[it].id);
DFS(v, u);
}
} int main()
{
while (scanf("%d%d%d", &n, &m, &k) != EOF)
{
G.init(); g.init(); res.clear();
for (int i = , u, v, w; i <= m; ++i)
{
scanf("%d%d%d", &u, &v, &w);
edge[i] = Edge(u, v, w);
G.add(u, v, i, w);
} dij.solve(); DFS(, );
int len = res.size();
printf("%d\n", len);
for (int i = ; i < len; ++i) printf("%d%c", res[i], " \n"[i == len - ]);
}
return ;
}
solved
题意：给出一棵树，有m次操作，每次将以x为根的子树下，和x的距离不超过d的所有点的权值都加上v,最后输出每个点的权值。
思路：首先考虑$d$特别大的情况下，也就是子树下所有点都要加上，那么更新的时候直接在那个点上更新，
最后只需要DFS一遍，每个点都加上父亲的权值即可。
再考虑加入限制的情况：
其实对于一个点，我们DFS下去的时候，到回溯上来这段时间，遍历的都是它的子树，那么我们可以设立一个标记
对于每个点，给他加上更新的权值的时候，我们在对应的子树的deep界限那里加上，那么每次遍历下去的时候，首先要减去这个当前深度对应的lazy值，然后再更新答案，回溯上来的时候取消标记即可。
#include <bits/stdc++.h>
using namespace std; #define ll long long
#define N 300010
#define pii pair <int, int>
int n, m;
vector <int> G[N];
vector <pii> vec[N];
ll ans[N], gap[N]; int deep[N], fa[N];
void DFS(int u, ll res)
{
res -= gap[deep[u]];
for (auto it : vec[u])
{
int dep = min(deep[u] + it.first + , n + );
gap[dep] += it.second;
res += it.second;
}
ans[u] = res;
for (auto v : G[u]) if (v != fa[u])
{
fa[v] = u;
deep[v] = deep[u] + ;
DFS(v, res);
}
for (auto it : vec[u])
{
int dep = min(deep[u] + it.first + , n + );
gap[dep] -= it.second;
res -= it.second;
}
res += gap[deep[u]];
} void init()
{
for (int i = ; i <= n; ++i)
{
G[i].clear();
vec[i].clear();
}
memset(gap, , sizeof gap);
deep[] = ;
} int main()
{
while (scanf("%d", &n) != EOF)
{
init();
for (int i = , u, v; i < n; ++i)
{
scanf("%d%d", &u, &v);
G[u].push_back(v);
G[v].push_back(u);
}
scanf("%d", &m);
for (int i = , x, d, v; i <= m; ++i)
{
scanf("%d%d%d", &x, &d, &v);
vec[x].emplace_back(min(d, n), v);
}
DFS(, );
for (int i = ; i <= n; ++i) printf("%lld%c", ans[i], " \n"[i == n]);
}
return ;
}
Upsolved.
题意：
$第i天有x_i个糖果，y_i个果冻，要求将他们放在一排，且相同的东西连续最多放k个，要放n天，求是否有放置方案满足$
思路：
$dp[i][1/0] 表示第i天最后一部分放糖果还是果冻的最小数量，然后枚举四种状态DP转移即可。$
#include <bits/stdc++.h>
using namespace std; #define ll long long
#define INF 0x3f3f3f3f
#define N 300010
int n, k, x[N], y[N], dp[N][]; int calc(int pa, int pb, int a, int b)
{
int ans = INF;
if (pa <= k)
{
int tot = pa + a;
int cnt = (tot + k - ) / k - ;
if (b == cnt) ans = min(ans, tot - cnt * k);
else if (b > cnt && b <= (ll)a * k) ans = min(ans, );
}
if (pb <= k)
{
int cnt = (a + k - ) / k - ;
if (b == cnt) ans = min(ans, a - cnt * k);
else if (b > cnt && b <= (ll)a * k - pb) ans = min(ans, );
}
return ans;
} bool solve()
{
memset(dp, 0x3f, sizeof dp); dp[][] = dp[][] = ;
for (int i = ; i <= n; ++i)
{
dp[i][] = calc(dp[i - ][], dp[i - ][], x[i], y[i]);
dp[i][] = calc(dp[i - ][], dp[i - ][], y[i], x[i]);
if (dp[i][] == INF && dp[i][] == INF) return false;
}
return true;
} int main()
{
while (scanf("%d%d", &n, &k) != EOF)
{
for (int i = ; i <= n; ++i) scanf("%d", x + i);
for (int i = ; i <= n; ++i) scanf("%d", y + i);
puts(solve() ? "YES" : "NO");
}
return ;
}
Unsolved.