Noip2023国庆集训A组Day8
A. 增量幻境（increase）
水题一题，贪心
#include
using namespace std;
typedef long long ll;
const int N = 1e6 + 100;
inline ll read() {
ll x = 0, f = 1;
char c = getchar();
while (!isdigit(c) && c != '-') c = getchar();
if (c == '-')
f = -1, c = getchar();
while (isdigit(c)) x = x * 10 + c - '0', c = getchar();
return f * x;
}
char s[N];
int num[N];
int main() {
freopen("increase.in", "r", stdin);
freopen("increase.out", "w", stdout);
scanf("%s", s + 1);
int len = strlen(s + 1), cnt = 0;
if (len == 1 && s[1] == '0') {
printf("0\n");
}
for (int i = 1; i = 1; i--) {
if (num[i] < num[i - 1]) {
num[i] = 9;
num[i - 1]--;
}
}
for (int i = 1; i <= len; i++)
if (num[i]) {
cnt = i;
break;
}
for (int i = cnt; i <= len; i++) {
if (num[i - 1] == 9) {
printf("9");
num[i] = 9;
} else {
printf("%d", num[i]);
}
}
printf("\n");
return 0;
}
B. 逃离遗迹(escape)
由于是树形结构，可以以A,B,C三点为起点遍历一遍，分别求出任意点离A,B,C三点的距离。枚举直升机停留的房间，求最小值即可
#include
using namespace std;
const int N=20010;
const int INF=0x3f3f3f3f;
typedef long long ll;
int n,S1,S2,S3;
int d1[N],d2[N],d3[N];
bool f[N];
struct edge
{
int to,from,next;
}e[N<<1];
int head[N];
int cnt;
inline ll read()
{
ll x = 0, f = 1;
char c = getchar();
while (!isdigit(c) && c != '-') c = getchar();
if (c == '-')
f = -1, c = getchar();
while (isdigit(c)) x = x * 10 + c - '0', c = getchar();
return f * x;
}
inline void add(int x,int y,int z)
{
e[++cnt].to=y;
e[cnt].from=z;
e[cnt].next=head[x];
head[x]=cnt;
}
void spfa(int s,int*a)
{
queue q;
for(int i=1;ia[u]+e[i].from)
{
a[k]=a[u]+e[i].from;
if(!f[k])
{
q.push(k);
f[k]=true;
}
}
}
}
return;
}
int ans=INF,sum;
int main()
{
freopen("escape.in","r",stdin);
freopen("escape.out","w",stdout);
int n=read(),A=read(),B=read(),C=read();
for(int i=1;i<n;++i)
{
int x=read(),y=read(),z=read();
add(x,y,z);
add(y,x,z);
}
for(int i=1;i<=n;++i)
{
d1[i]=d2[i]=d3[i]=INF;
}
spfa(A,d1);
spfa(B,d2);
spfa(C,d3);
for(int i=1;id1[i]+d2[i]+d3[i])
{
sum=i;
ans=d1[i]+d2[i]+d3[i];
}
}
printf("%d\n%d\n",sum,ans);
return 0;
}
C. 阶乘计算(factorial)
大水题，求n!n!在kk进制下末尾00的个数，相当于求符合k^a∣n!最大的a;
对k质因数分解，求出各个质因数在n!中出现的次数即可;
#include
using namespace std;
typedef long long ll;
const int N = 1610;
ll a[N], b[N];
ll ans = 0x7fffffffffffffff;
inline ll read() {
ll x = 0, f = 1;
char c = getchar();
while (!isdigit(c) && c != '-') c = getchar();
if (c == '-')
f = -1, c = getchar();
while (isdigit(c)) x = x * 10 + c - '0', c = getchar();
return f * x;
}
ll ol(ll x, ll y) {
if (x < y) {
return 0;
} else {
return x / y + ol(x / y, y);
}
}
int main() {
freopen("factorial.in", "r", stdin);
freopen("factorial.out", "w", stdout);
ll n = read(), k = read(), sum = 0;
for (int i = 2; i 1) {
b[++sum] = k;
a[sum] = 1;
}
for (int i = 1; i <= sum; i++) {
ans = min(ans, ol(n, b[i]) / a[i]);
}
cout << ans << endl;
return 0;
}
D. 奔山赴海(traffic)
如果枚举每一条边，然后删去，跑bfs是O(m^2)无法通过;
可以发现在原图上a,b间的次短路（不通过该条边），即为删去该边后a,b最短路;
枚举图上的每个点S，计算以这个点为起点的所有边被删去后的最短路和次短路;
从S开始向外搜索。维护数组f(i,0/1)，0表示最短路，1表示次短路;
对于每个还要状态记录fir(i,0/1)表示这个状态下除了S外经过的第一个节点，使得次短路和最短路的除S外第一个经过的节点不同;
注意从SS点开始向外搜索的时候是不能回到S点的，这样会导致被删除掉的S出发的边重新被使用;
对于每条边(S,T)，f(T,0)=1，f(T,1)就是答案;
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e3 + 100, M = 1e5 + 100;
int head[N], ver[M], tail[M], cnt;
inline ll read() {
ll x = 0, f = 1;
char c = getchar();
while (!isdigit(c) && c != '-') c = getchar();
if (c == '-')
f = -1, c = getchar();
while (isdigit(c)) x = x * 10 + c - '0', c = getchar();
return f * x;
}
struct edge {
int u, v;
} e[M];
int ans[N][N], f[N][2], g[N][2];
void add(int x, int y) {
ver[++cnt] = y;
tail[cnt] = head[x];
head[x] = cnt;
}
queue<pair<int, int> > q;
int main() {
freopen("traffic.in", "r", stdin);
freopen("traffic.out", "w", stdout);
int n = read(), m = read();
for (int i = 1; i <= m; i++) {
e[i].u = read(), e[i].v = read();
add(e[i].u, e[i].v);
}
for (int k = 1; k <= n; k++) {
memset(f, -1, sizeof(f));
memset(g, 0, sizeof(g));
f[k][0] = f[k][1] = 0;
for (int i = head[k]; i; i = tail[i]) {
int v = ver[i];
f[v][0] = 1;
g[v][0] = v;
q.push(make_pair(v, 0));
}
while (!q.empty()) {
int u = q.front().first, op = q.front().second;
q.pop();
for (int i = head[u]; i; i = tail[i]) {
int v = ver[i];
if (f[v][0] == -1) {
f[v][0] = f[u][op] + 1;
g[v][0] = g[u][op];
q.push(make_pair(v, 0));
} else {
if (f[v][1] != -1 || g[v][0] == g[u][op]) {
continue;
}
f[v][1] = f[u][op] + 1;
g[v][1] = g[u][op];
q.push(make_pair(v, 1));
}
}
}
for (int j = 1; j <= n; j++) {
ans[k][j] = f[j][1];
}
}
for (int i = 1; i <= m; i++) {
printf("%d", ans[e[i].u][e[i].v]);
}
return 0;
}