NOIP2023 国庆集训 A 组 Day8
A. 增量幻境(increase)
- 贪心，能贪就贪，贪不动再退位纯输出9;
- $100pts$
#include
using namespace std;
string s;
int i;
int n;
int main() {
freopen("increase.in", "r", stdin);
freopen("increase.out", "w", stdout);
cin>>s;
n=s.size();
for(; is[i+1])
break;
}
if(i!=n-1) {
while(s[i]-1<s[i-1])
i--;
for(int j=0; j<i; j++)
cout<<s[j];
if( i!=0 || (s[i]-1)!='0')
putchar(s[i]-1);
while(i<n-1) {
cout<<9;
i++;
}
} else
cout<<s;
return 0;
}
B. 逃离遗迹(escape)
- 一不小心枚举所有点求最小值，直接TLE，50pts；
- 由于是树形结构，可以以A、B、C三点为起点遍历一遍，分别求出任意点离A、B、C三点的距离;
- 枚举直升机停留的房间，求最小值即可;
- $100pts$
#include
using namespace std;
int n, a, b, c;
int u, v, w;
struct po {
int tv;
int tw;
};
struct note {
int x;
int step;
};
note no, ne;
po now;
vector<vector > adj;
int dis[4][20001];
queue q;
int sum = 999999999;
int ans;
string s1, s2;
bool check(int p, int q) {
int pp = p, qq = q;
s1.clear();
s2.clear();
while (pp != 0) {
char c = pp % 10 + '0';
s1.push_back(c);
pp /= 10;
}
reverse(s1.begin(), s1.end());
while (qq != 0) {
char c = qq % 10 + '0';
s2.push_back(c);
qq /= 10;
}
reverse(s2.begin(), s2.end());
if (s1 > s2)
return true;
return false;
}
void bfs(int ii, int m) {
for (int i = 1; i <= n; i++) dis[m][i] = 999999999;
dis[m][ii] = 0;
no.x = ii;
no.step = 0;
q.push(no);
while (!q.empty()) {
no = q.front();
q.pop();
for (int i = 0; i < adj[no.x].size(); i++) {
ne.x = adj[no.x][i].tv;
ne.step = no.step + adj[no.x][i].tw;
if (ne.step < dis[m][ne.x]) {
dis[m][ne.x] = ne.step;
q.push(ne);
}
}
}
return;
}
int main() {
freopen("escape.in", "r", stdin);
freopen("escape.out", "w", stdout);
scanf("%d%d%d%d", &n, &a, &b, &c);
adj.resize(n + 3);
for (int i = 1; i < n; i++) {
scanf("%d%d%d", &u, &v, &w);
now.tv = v;
now.tw = w;
adj[u].push_back(now);
now.tv = u;
adj[v].push_back(now);
}
bfs(a, 1);
bfs(b, 2);
bfs(c, 3);
for (int i = 1; i <= n; i++) {
int sn;
sn = dis[1][i] + dis[2][i] + dis[3][i];
if (sn == sum) {
if (check(ans, i))
ans = i;
}
if (sn < sum) {
sum = sn;
ans = i;
}
}
cout << ans << endl << sum;
return 0;
}
C. 阶乘计算(factorial)
- 开了个unsigned long long，炸了10pts;
- 求n!在k进制下末尾0的个数，相当于求符合k^a\mid n!最大的a;
- 对k质因数分解，求出各个质因数在n!中出现的次数即可;
- $100pts$
#include
using namespace std;
long long n,k,ans=99999999999,kk;
struct note {
long long a;
long long b;
};
vector sub;
note no;
inline bool check( long long x) {
for(long long i=2; i*i=ne) {
as+=m/ne;
ne*=x.a;
}
return as/x.b;
}
int main() {
freopen("factorial.in", "r", stdin);
freopen("factorial.out", "w", stdout);
scanf("%lld%lld",&n,&k);
if(n==0) {
cout<<0;
return 0;
}
kk=k;
for(long long i=2; i<=kk; i++) {
no.a=no.b=0;
if(check(kk)) {
no.a=kk;
no.b=1;
sub.push_back(no);
break;
} else {
if(kk%i==0)
no.a=i;
while(kk%i==0) {
kk/=i;
no.b++;
}
if(no.a!=0)
sub.push_back(no);
}
}
for(int i=0; i<sub.size(); i++)
ans=min(ans,work(sub[i]));
cout<<ans;
return 0;
}
D. 奔山赴海(traffic)
- $BFS$，结果才$10pts$……
- 如果枚举每一条边，然后删去，跑bfs是O(m^2)无法通过;
- 可以发现在原图上a,b间的次短路（不通过该条边），即为删去该边后a,b最短路;
- 枚举图上的每个点S，计算以这个点为起点的所有边被删去后的最短路和次短路;
- 从S开始向外搜索。维护数组f(i,0/1)，0表示最短路，1表示次短路;
- 对于每个还要状态记录fir(i,0/1)表示这个状态下除了S外经过的第一个节点，使得次短路和最短路的除S外第一个经过的节点不同;
- 注意从S点开始向外搜索的时候是不能回到S点的，这样会导致被删除掉的S出发的边重新被使用;
- 对于每条边(S,T)，f(T,0)=1，f(T,1) 就是答案;