Lruihao's Note

链接：https://www.nowcoder.com/acm/contest/157/A
来源：牛客网

题目描述

xb 有 m 种石子，每种无限个，Ta 想从这些石子中取出 n 个，并按顺序排列起来，为了好看，相邻的石子不能相同。xb 想知道有多少种排列的方法。

题目链接

Dreamoon wants to climb up a stair of n steps. He can climb 1 or 2 steps at each move. Dreamoon wants the number of moves to be a multiple of an integer m.

What is the minimal number of moves making him climb to the top of the stairs that satisfies his condition?

Input

The single line contains two space separated integers n, m (0 < n ≤ 10000, 1 < m ≤ 10).

题目链接

题目大意

就是给定两个字符串，第一个字符串由"+","-“组成，第二个字符串由”+","-","?“组成，“+”代表加 1，”-“代表减一，“?“代表可取正也可取负，问第二个字符串的位置和第一个字符串相等的概率是多少。

题意

给出 a,b,c,x1,x2,y1,y2，求满足 ax+by+c=0，且 x∈[x1,x2],y∈[y1,y2] 的整数解个数。

题目链接

题目大意

给定两个数 n,k 求 n^k 的前三位和最后三位。

分析

求后三位的话：直接快速幂，对 1000 取模就好了。
求前三位，对于给定的一个数 n, 它可以写成 n=10^{a, 其中这个 a 为浮点数，则t=n^k=(10^a)^k=10^a*k=(10^x)*(10^y);其中 x,y 分别是a*k的整数部分和小数部分，对于 t=n}k 这个数，它的位数由 (10^{x) 决定，它的位数上的值则有 (10}y) 决定，因此我们要求 t 的前三位，只需要将 10^{y 求出，在乘以 100，就得到了它的前三位。
分析完，我们再整体看，设 n}k=10^z; 那么z=k*log10(n)
fmod(z,1)可以求出 x 的小数部分。

A. The Rank

题目大意：
给出 n 个学生的成绩，Thomas Smith 的成绩是第一行，然后要按总成绩进行排序，总分相同的按编号从小到大排；
开始看还以为要写 sort 的 cmp 函数进行多条件排序，敲完才发现其实只要按总分就可以了，因为托马斯的 id 是一，必然会排在前面。

欧拉函数是求小于 x 并且和 x互质 的数的个数

通式：φ(x)=x(1-1/p1)(1-1/p2)(1-1/p3)(1-1/p4)…..(1-1/pn)
其中 p1, p2……pn 为 x 的所有质因数，x 是不为 0 的整数
φ(1)=1（唯一和 1 互质的数就是 1 本身）【注意：每种质因数只一个。比如 12=223】

定理

1. 若 n 是素数 p 的 k 次幂，φ(n)=p^k-p(k-1)=(p-1)p^(k-1)，因为除了 p 的倍数外，其他数都跟 n 互质
2. 欧拉函数是积性函数——若 m,n 互质，φ(mn)=φ(m)φ(n)

特殊性质

1. 当 n 为奇数时，φ(2n)=φ(n)
2. p 是素数，φ(p) = p - 1，φ(p) 称为 p 的欧拉值
3. 若 a 为素数，b mod a=0,φ(a*b)=φ(b)*a

题目链接

大意：
要从城市 1 到城市 N 运送货物，有 M 条道路，每条道路都有它的最大载重量，问从城市 1 到城市 N 运送最多的重量是多少。
其实题意很简单，就是找一条 1–>N 的路径，在不超过每条路径的最大载重量的情况下，使得运送的货物最多。一条路径上的最大载重量为这个路径上权值最小的边；

看到知乎，百度的页面 F12 检查后都会有一些有趣的招聘信息。于是乎我也想给我的博客加一个。
我主要用到的工具：

• console.log()
• Notepad++
• 在线图片转文字工具

题目链接

题目大意：
说的是，一只奶牛位于 N 号节点，输入 N 个节点和 T 对双向的边，求出由 N 到 1 的最短的距离，其实就是问的单源最短路问题。

两个点可能有多条路，选择最短的。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54

#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;

const int INF=99999999;                    //设为无穷大
int maps[1005][1005],v[1005],d[1005];  //v 表示是否已经过遍历 d 表示从源到点当前最短路
int n;

void Dijkstra(int s,int t)
{
    int i,j,k,mini;
    for(i=1;i<=n;i++)
        d[i]=INF;                      //除源点设为 0 距离外 其他先设为无穷大
    d[s]=0;
    for(i=1;i<=n;i++)         //n 点循环 n 次 , 找出 n 个 k, 找 n 个点
    {
        mini=INF;
        k=-1;
        for(j=1;j<=n;j++)              //在所有未标记点中 选 d 值最小的点
            if(!v[j] && d[j]<mini)
                mini=d[k=j];

        v[k]=1;                         //标记节点
        if(k==t)
        {
            printf("%d\n",d[t]);
            return;
        }
        for(j=1;j<=n;j++)
            if(!v[j] && (d[k]+maps[k][j])<d[j])   //表示从 k 出发的点，对于所有边，更新相连点
                d[j]=d[k]+maps[k][j];
    }
}

int main()
{
    int T,i,j,x,y,D;
    while(scanf("%d %d",&T,&n)!=EOF)
    {
        memset(v,0,sizeof(v));            //清除标记
        for(i=1;i<=n;i++)
            for(j=1;j<=n;j++)
                maps[i][j]=INF;

        for(i=1;i<=T;i++){
            scanf("%d%d%d",&x,&y,&D);
            if(maps[x][y]>D)               //可能有多条路，只记录最短的
                maps[x][y]=D,maps[y][x]=D;
        }
        Dijkstra(1,n);
    }
    return 0;
}