前言

一些话

炸了，细节有很多没处理好。

题目有些不明显，丢了很多不该丢的分。

P1 质因数

题面

有一个正整数数列 $a_1,a_2,…,a_n$ 。定义函数 $f(x)$ 为 $x$ 的不同的质因数数量。
求 $f(a_1),f(a_2)…f(a_n)$ 。

$n<=10^6$

思路

欧拉筛筛出素数，筛素数的时候记录下。

P2 编码

题面

一个字符串 $str$ 的 p 型编码 $a$ 的定义如下：把 $str$ 表示成 $b_1$ 个 $c_1,b_2$ 个 $c_2…b_n$ 个 c_n，然后将 $b_1,c_1,b_2,c_2,…,b_n,c_n$ 首尾拼接成的字符串中最短的字符串设为 a。例如：字符串 $122344111$ 可被描述为”1 个 1、 2 个 2、1 个 3、2 个 4、3 个 1″，因此我们说 $122344111$ 的 p 型编码为 $1122132431$ 。类似的道理， $00000000000$ 可描述为”11 个 0″，因此它的 p 型编码为 $110$ ； $100200300$ 可描述为”1 个 1、 2 个 0、 1 个 2、 2 个 0、 1 个 3、 2 个 0″，因此它的 p 型编码为 $112012201320$。很显然，一个串 $str$ 的 p 型编码是固定的，但是可能有多个串的 p 型编码相同。现在已知一个字符串 $str$ 的 p 型编码 $a$ ，但不知道原来的字符串， 求有多少种字符串的 p 型编码为 $a$ 。

$|a|<=10^6$

思路

设 $f[i]$ 为 $1 \sim i$ 这段字符串的编码方案数，则有: $$\begin{array}{l}f\lbrack i\rbrack=\left\{\begin{array}{c}1\;(i=0)\\0\;(s\lbrack i+1\rbrack=0)\\\sum_{j=0}^{i-1}\;(s\lbrack j\rbrack\neq s\lbrack i\rbrack)\end{array}\right.\\\end{array}$$

我们发现 $f[i]$ 其实就是前面所有 $f[j]$ 的和减去 $s[i]=s[j]$ 的情况，只要边算边把所有 $f$ 的和与 $s[j]$ 为特定数的和记录下就好了。

P3  八卦阵

题面

有一个八卦阵。这个阵可以认为是一个 $n$ 个点， $m$ 条边的有向图。每条边 $i$ 有一个困难 $a[i]$ 。每个点 $u$ 有八个状态： $b[u][1],b[u][2],…,b[u][8]$，这八个状态均为 $[1,8]$ 之间的整数(不一定是排列)，在第 $i$ 秒中， $u$ 的状态为 $b[u][(i-1)%8+1]$。对于任意两个状态 $i,j$ 都存在一个复杂度 $c[i][j]$。现在想从 $1$ 号点走到 $n$ 号点， 在第一秒开始时在 $1$ 号点，每次可以用 $1$ 秒从当前点 $u$ 走到另一个有边相连的点 $v$。也就是说， 在第一秒内走过第一条边，在第二秒内走过第二条边……由于八卦阵极其巧妙， 必须砸出一些榔头才能走过一条边。若在第 $i$ 秒通过第 $j$ 条边从点 $u$ 走到点 $v$ ，需要砸出 $a\lbrack j\rbrack+c\lbrack b\lbrack u\rbrack\lbrack(i-1)\%8+1\rbrack\rbrack\lbrack b\lbrack v\rbrack\lbrack(i-1)\%8+1\rbrack\rbrack$ 个榔头。
请计算出至少要多少个榔头才能从点 $1$ 走到点 $n$。

$n,m<=3 \times 10^5$

思路

最简单的一道题，有 $n$ 个结点，对于一条从 $x$ 到 $y$ ，权值为 $z$ 的边，枚举状态 $i (i \in [1,8])$ ，每次新建一条 $(i-1)*n+x$ 到 $(j-1)*n+y$，长度为 $z+c[b[x][(i-1)%8+1]][b[y][(i-1)%8+1]]$ 的边即可。

注意用 $SPFA$ ，$Dijkstra$ 会超时。

考试时候没注意是单向边，分数 $100 \rightarrow 20$ 。

代码

#include<bits/stdc++.h>
#define inf 1000000000
using namespace std;
inline long long read(){
	long long ret=0,f=1;char ch=getchar();
	while (ch<'0'||ch>'9') {if (ch=='-') f=-f;ch=getchar();}
	while (ch>='0'&&ch<='9') ret=ret*10+ch-'0',ch=getchar();
	return ret*f;
}
long long N,X;
long long head[2500005];
long long nodeP;
long long dist[2500005];
bool vis[2500005];
struct Node{
    long long v,w,next;
}Adj[2500005];
void add(long long src,long long to,long long weight){
    Adj[nodeP].v=to;
    Adj[nodeP].w=weight;
    Adj[nodeP].next=head[src];
    head[src]=nodeP++;
}
void Spfa(){
    queue<int> que;
    long long i;
    for(i=1;i<=N;i++){
        dist[i]=inf;
        vis[i]=false;
    }
    dist[X]=0;
    que.push(X);
    while(!que.empty()){
        long long now=que.front();
        que.pop();
        vis[now]=false;
        for(i=head[now];i!=-1;i=Adj[i].next) {
            long long to=Adj[i].v;				
            if(dist[to]==inf||dist[to]>dist[now]+Adj[i].w) {
                dist[to]=dist[now] + Adj[i].w;
                if(!vis[to]) {
                    vis[to]=true;
                    que.push(to);
                }
            }
        }
    }
}
long long n,m;
long long c[9][9],b[300005][9];
int main(){
    memset(head,-1,sizeof(head));
    freopen("hammer.in","r",stdin);
    freopen("hammer.out","w",stdout);
    n=read();m=read();X=1;N=8*n;
    for (long long i=1;i<=8;i++){
    	for (long long j=1;j<=8;j++){
    		c[i][j]=read();
		}
	}
	for (long long i=1;i<=n;i++){
    	for (long long j=1;j<=8;j++){
    		b[i][j]=read();
		}
	}
	for (long long t=1;t<=m;t++){
		long long x,y,z;
		x=read();y=read();z=read();
		for (long long i=1;i<=8;i++){
			long long j=i+1;
			if (i==8){
				j=1;
			}
			add((i-1)*n+x,(j-1)*n+y,z+c[b[x][(i-1)%8+1]][b[y][(i-1)%8+1]]);
		}
	}
	Spfa();
	long long ans=inf;
	for (long long i=1;i<=8;i++){
		ans=min(ans,dist[n*i]);
	}
	cout<<ans;
    return 0;
}