Codeforces Round #460 (Div. 2)

签到

题意

定义：一个数（没有前缀0）的各个位数之和为10位“perfec”数，问第k个“perfect”数位多少（1<=k<=1e5）

分析

一开始找错了，以为会超过1e9，通过理性的分析不难发现，最大不超过1e9，强行打个表即可

签到

题意

n个点m条边的有向图，每个点有一个数字（可以重复，0~25），定义一条路径的权值为该路径出现数字最多的数字的次数，若有环输出-1，否则输出最大值(1 ≤ n, m ≤ 300 000)

分析

思路：首先直接dfs肯定不行，最坏情况n^2，

问题就在于：如何记忆的记录已经搜索的路的每个数字的次数

解决：dp思想，每个点记录下到改点的所有数字的次数即可

正解：拓扑排序+dp

拓扑排序的时候dp即可

定义：dp[i][j]：第i个点数字j的最大值

转移：直接从上一个节点到当前节点转移即可

时间复杂度（26*m）

#include<bits/stdc++.h>
#define ll long long

using namespace std;

const int maxn = 300000+2;


int num[maxn];
struct node
{
    int to,next;

}edge[maxn];
int cnt;
int head[maxn];

void addedge(int u, int v)
{
    ++cnt;
    edge[cnt].to=v;
    edge[cnt].next=head[u];
    head[u]=cnt;
}

bool flag;
int n, m;
string s;
int dp[maxn][26];
int answer=0;
queue<int>q;
int deep[maxn];

void topsort()
{
    int ans=0;
    while(!q.empty())
    {
        ans++;
        int now=q.front();
        q.pop();
        for(int i=head[now];i!=0;i=edge[i].next)
        {
            int v=edge[i].to;
            deep[v]--;
            if(!deep[v])
                q.push(v);
             for(int j=0;j<26;j++)
             {
                 if(j==num[v])
                    dp[v][j]=max(dp[v][j],dp[now][j]+1);
                 else
                    dp[v][j]=max(dp[v][j],dp[now][j]);
                answer=max(answer, dp[v][j]);
             }

        }
    }
    if(ans<n)
        flag=false;

}

int main()
{
    flag=true;
    scanf("%d%d", &n, &m);
    cin>>s;
    for(int i=0;i<n;i++)
    {
        num[i+1]=s[i]-'a';
    }
    int u,v;
    for(int i=0;i<m;i++)
    {
        scanf("%d%d", &u, &v);
        addedge(u,v);
        deep[v]++;
    }
    for(int i=1;i<=n;i++)
    {
        if(deep[i]==0)
        {
              q.push(i);
              dp[i][num[i]]++;
        }
    }
    topsort();
    if(!flag)
        printf("-1
");
    else
        printf("%d
", answer);
    return 0;
}

View Code

题意

n*a^n = b (mod p) （1<=n<=x）,给出a，b，x，p（p为素数），问满足上式的n的个数 (2 ≤ p ≤ 10⁶ + 3, 1 ≤ a, b < p, 1 ≤ x ≤ 10¹²)

分析

费马小定理应用