上午

打比赛

T1

贪心（找到尽量大的数字）
找规律
找到第一个s[i+1]的情况，并找到前面第一个值为s[i]的位置，并且将s[i]-1，接下来（不管怎么改都不会变大了（喜））那个位置以后的每个数都改成’9′
注意开头为0的情况（-10pts）

T2

Dijkstra+heap
被slt坑了

#include <bits/stdc++.h>
#define inf 1e18
#define int long long 
using namespace std;
int n,m,s,dist[100001],vis[100001];
struct node
{
    int y,w;    
};
vector<node> a[100001];
struct node2
{
    int id,len;
    bool operator < (const node2&a) const
    {
        return a.len<len;   
    }
};
priority_queue<node2> que;
void Dijkstra()
{
    que.push({s,dist[s]});
    while(!que.empty())
    {
        int ind=que.top().id;
        if(vis[ind] == 1) //只能选到一次
        {
            que.pop();
            continue;
        }
        que.pop();
        vis[ind] = 1;
        for(int i=0;i<a[ind].size();i++)
        {
            if(dist[a[ind][i].y] > dist[ind]+a[ind][i].w)
            {
                dist[a[ind][i].y]=dist[ind]+a[ind][i].w;
                if(vis[a[ind][i].y] == 0) //只能选到一次
                {
                    que.push({a[ind][i].y,dist[a[ind][i].y]});
                }
            }
        }
    }
}
signed main()
{
    int x,y,w;
    cin >> n >> m >> s;
    for(int i=1;i<=m;i++)
    {
        cin >> x >> y >> w;
        a[x].push_back({y,w}); 
    }
    for(int i=1;i<=n;i++) dist[i]=inf;
    dist[s]=0;
    Dijkstra();
    for(int i=1;i<=n;i++) 
    {
        if(dist[i]==inf) cout << -1 << " ";
        else cout<<dist[i]<<" ";    
    }
    return 0;
} 

T3

xkrnb!
n!在k进制下可以表示为m \cdot k^n
我们可以给k进行分解质因数
接下来把这些质因数从一次方到k次方并且与n相除，最后……（写不下去了）

#include <bits/stdc++.h>
using namespace std;
long long n,k,n2,k2;
struct node
{
    long long num,cnt,cnt2;
} p[10000001];
int main()
{
    freopen("factorial.in","r",stdin);
    freopen("factorial.out","w",stdout);
    int cnt=0;
    cin >> n >> k;
    k2=k;n2=n;
    for(int i=2;i<=k;i++)
    {
        if(k2 % i == 0) p[++cnt].num=i;
        while(k2 % i == 0)
        {
            p[cnt].cnt++;
            k2 /= i;
        }
        if(k2 == 1) break; 
    }
    for(int i=1;i<=cnt;i++)
    {
        for(int j=1;pow(p[i].num,j) <= n;j++)
        {
            p[i].cnt2 += n/pow(p[i].num,j);
        }
    }
    long long ans=1e12;
    for(int i=1;i<=cnt;i++)
    {
        ans=min(ans,p[i].cnt2/p[i].cnt);
    }
    cout << ans;
    return 0;
}