长乐集训 Day 6

Posted on By 王, 柏铮 长乐集训 Day 6无评论

The sixth day of Changle trainning.
今天上午打了200分，感谢出题者的放水，谢谢！！！！！

T1

本题贪心找规律
小科同学最近醉心于动态规划的研究，他苦学百年，已经牢牢掌握了最长上升子序列的知识。
小科对于这种单调不减的序列非常着迷，于是他写下了一个数x。
他希望找到最大的一个小于等于x的数，使得这个数的各个数位是单调不减的。
他觉得这太简单了，于是想考考你。
代码如下（有亿点长）：

#include <bits/stdc++.h>
using namespace std;
string x;
int a[101010], cnt, t, z;
bool k;
int main() {
    freopen("increase.in", "r", stdin);
    freopen("increase.out", "w", stdout);
    cin >> x;
    int len = x.size();
    for (int i = 0; i < len; i++) {
        a[i + 1] = (int)(x[i] - &#039;0&#039;);
        if (a[i + 1] < a[i]) {
            k = 1;
        }
    }
    if (k == 0) {
        for (int i = 1; i <= len; i++) {
            cout << a[i];
        }
        exit(0);
    }
    for (int i = 1; i <= len - 1; i++) {
        if (a[i] > a[i + 1]) {
            t = i;
            break;
        }
    }
    for (int i = t - 1; i >= 1; i--) {
        if (a[i] == a[t]) {
            t = i;
        } else {
            break;
        }
    }
    for (int i = 1; i < t; i++) {
        cout << a[i];
    }
    if (t == 1 && a[t] == 1) {
    } else {
        cout << a[t] - 1;
    }
    for (int i = t + 1; i <= len; i++) {
        cout << "9";
    }
    return 0;
}

T2

根据 hamood 的回信，在遗迹中有分布着三样道具。
当三样道具都拿走后，遗迹就很快自动毁灭，所以必须要在最短时间内离开。
遗迹可以看作是由n个房间(编号1~n)和n-1条长度不等通道所组成，并且任意两个房间之间有且只有一条路可以相互到达。
现在我们的队员已经在编号为A,B,C的房间内拿到道具，并且准备撤退。
由于只有一架直升机，所以只能在一个房间上停留。
现在请你决定将直升机停在哪一个房间之上，能够使三人到达该房间的距离之和最短。
我的解法非正解！！！
用最短路径来做
代码如下：

#include <bits/stdc++.h>
using namespace std;
int n, A, B, C, ans, tot[20100], r, k;
int head[20100], cnt;
struct Edge {
    int next, to, w;
} a[101010];
void add(int x, int y, int z) {
    a[++cnt].next = head[x];
    head[x] = cnt;
    a[cnt].to = y;
    a[cnt].w = z;
}
void Forever_NJN_F(int k) {
    priority_queue<int> q;
    int h[20100];
    memset(h, 0, sizeof h);
    bool vis[20010];
    memset(vis, false, sizeof vis);
    q.push(k);
    vis[k] = true;
    while (q.size()) {
        int u = q.top();
        q.pop();
        for (int i = head[u]; i; i = a[i].next) {
            int v = a[i].to;
            if (!vis[v]) {
                q.push(v);
                vis[v] = true;
                h[v] = h[u] + a[i].w;
            }
        }
    }
    for (int i = 1; i <= n; i++) {
        tot[i] += h[i];
    }
}
int main() {
    freopen("escape.in", "r", stdin);
    freopen("escape.out", "w", stdout);
    cin >> n >> A >> B >> C;
    for (int i = 1; i <= n - 1; i++) {
        int x, y, z;
        cin >> x >> y >> z;
        add(x, y, z);
        add(y, x, z);
    }
    Forever_NJN_F(A);
    Forever_NJN_F(B);
    Forever_NJN_F(C);
    r = INT_MAX;
    for (int i = 1; i <= n; i++) {
        if (tot[i] < r) {
            r = tot[i];
            k = i;
        }
    }
    cout << k << endl << tot[k];
    return 0;
}

正解
由于是树形结构，可以以A,B,C三点为起点遍历一遍，分别求出任意点离A,B,C三点的距离。
枚举直升机停留的房间，求最小值即可。

#include <bits/stdc++.h>

using namespace std;

const int N = 20005;

struct EDGE {
    int v, w;
};

vector<EDGE> fir[N];
int dist[4][N], start[3];
bool vis[N];
int n;

void DFS(int rt, int* dis) {
    vis[rt] = true;
    for (int i = 0; i != fir[rt].size(); i++)
        if (!vis[fir[rt][i].v]) {
            dis[fir[rt][i].v] = dis[rt] + fir[rt][i].w;
            DFS(fir[rt][i].v, dis);
        }
    return;
}

void Init() {
    int u, v, w;
    EDGE tp;

    scanf("%d", &n);
    for (int i = 0; i <= 2; i++) scanf("%d", &start[i]);
    for (int i = 1; i < n; i++) {
        scanf("%d %d %d", &u, &v, &tp.w);
        tp.v = v;
        fir[u].push_back(tp);
        tp.v = u;
        fir[v].push_back(tp);
    }
    return;
}

void Work() {
    int best = -1;

    for (int i = 0; i <= 2; i++) {
        memset(vis, 0, sizeof(vis));
        DFS(start[i], dist[i]);//分别求出任意点离三点的距离
    }
    for (int i = 1; i <= n; i++) {//枚举
        dist[3][i] = dist[0][i] + dist[1][i] + dist[2][i];
        if (best == -1 || dist[3][i] < dist[3][best])
            best = i;
    }
    printf("%d\n%d\n", best, dist[3][best]);
    return;
}

int main() {
    freopen("escape.in", "r", stdin);
    freopen("escape.out", "w", stdout);

    Init();
    Work();
    return 0;
}

T3

比赛时想不出来
赛后没听懂。
此时此刻我需要向xkr大佬和wzt大佬致以最真诚的感谢！
感谢有你们！！！

阶乘在k进制的情况下求末尾的0的数量
先将k质因数分解，再将阶乘的结果n质因数分解再求
代码如下（感谢xkr大佬和wzt大佬帮助我找到这一堆问题）

#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll n,k,cnt,b[1010100],tot,d[1010100],hot;
struct NJN{
    int w,c;
}a[1010100];
void DreamBacktoNJN(ll h)
{
    ll t;
    while(h>1)
    {
        while(h>1)
        {
            t=2;
            while(h%t!=0)
            {
                t++;
            }
            d[++hot]=t;
            h/=t;
        }
    }
}
int main(){
//  freopen("factorial.in","r",stdin);
//  freopen("factorial.out","w",stdout);
    cin>>n>>k;
    DreamBacktoNJN(k);
    for(int i=1;i<=hot;i++)
    {
        if(d[i]==a[cnt].w)
        {
            a[cnt].c++;
        }
        else
        {
            a[++cnt].w=d[i];
            a[cnt].c=1;
        }
    }

    for(ll i=1;i<=cnt;i++)
    {
        ll t=0,x=a[i].w,z=0;
        while(1)
        {
            if(x>n)
            {
                break;
            }
            z+=n/x;
            t++;
            x*=a[i].w;
        }
        b[++tot]=z/a[i].c;
    }
    ll ans=LONG_LONG_MAX;
    for(ll i=1;i<=tot;i++)
    {
        ans=min(ans,b[i]);
    }
    cout<<ans;
    return 0;
}

T4

不会

一言时间

天之涯，地之角，知交半零落，一壶浊酒尽余欢，今宵别梦寒。
爱才应该是刺中好人的唯一的剑，是恶人能佩上的唯一的花。
若知是梦何须醒，不比真如一相会。
“沙漠，扬起你的沙砾，遮蔽太阳的光芒吧！！”
一剑！一念！
雨滴降落的速度是每秒十米，我该用怎么样的速度，才能将你挽留？
我们都是在不曾谋面之张开的神手掌上起舞的命运的奴隶。
清风徐来，我自盛开。
所有的梦境都是另一个现实，永远不要忘记。
路好不好走，也许我不能决定，但走不走，却只有我能决定。
只要不停下来，前进的道路就会不断延伸。
原是今生今世已惘然，山河岁月空惆怅，而我，终将是要等着你的。
有些人坐飞机就能见到，有些人坐时光机才可以。
纵马而已，何必认路？
独步天下，吾心自洁，无欲无求，如林中之象。
最渺小的人常关注着成绩和荣耀；最伟大的人常沉浸于创造和劳动。
我身上早已烙下沉默燃烧后遗留下来的哀愁。
读书只盼天数，工作只盼月数。
虚空有计算不到的事物，人也不会被过去束缚。
现在我这个遗患，已经成为把真学们极欲拔掉的夫来比道中钉。
人和人是无法理解的，所有的理解都是建立在自己的主观之上。
越是锐利的小刀切完东西后就越容易变钝。
形如野马色如碳，千书木兰太上权。
没有激流就称不上勇进，没有山峰就谈不上攀登。
如果必须要失去，那么不如一开始就不曾拥有。
总是在失去后，才会想再拥有，总是在离别中，才想在回头。
我们奔跑在曲折的时空，过去与未来发生交折。
生于黑暗，侍奉光明。万物皆虚，万事皆允。

训练日志

发表回复