hgoi#20190706

muronglin
muronglin 2019年07月06日
  • 在其它设备中阅读本文章

T1- 质因数

有一个正整数数列 a1,a2…an。定义函数 f(x)为 x 的不同的质因数数量。 求 f(a1),f(a2)…f(an)。

解法

写个欧拉筛,然后欧拉筛的时候直接判断一下有没有新增质因数

ac 代码

#include<bits/stdc++.h>
using namespace std;
int n,cnt,x,a[1000010],p[1000010],dp[1000010];
void oula()
{
    for(int i=2;i<=1000000;i++)
    {
        if(a[i]==0)a[i]=p[++cnt]=i,dp[i]=1;
        for(int j=1;j<=cnt;j++)
        {
            if(i*p[j]>1000000||a[i]<p[j])break;
            a[i*p[j]]=p[j];
            if(i%p[j]==0)dp[i*p[j]]=dp[i];
            else dp[i*p[j]]=dp[i]+1;
        }
    }
}
int main()
{
    freopen("easy.in","r",stdin),freopen("easy.out","w",stdout),oula(),scanf("%d",&n);
    while(n--)scanf("%d",&x),printf("%dn",dp[x]);
    return 0;
} 

T2- 编码

一个字符串 str 的 p 型编码 a 的定义如下:把 str 表示成 b1 个 c1,b2 个 c2...bn 个 cn,然后将 b1,c1,b2,c2,...,bn,cn 首尾拼接成的字符串中最短的字符串设为 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。

解法

显然是个 dp 的题目,我们设状态 dp[i]为以第 i 个字符为结尾的 b[x]的方案数,那么最终的答案就是 dp[n-1] 我们想状态转移,dp[i]可以从 dp[j] (1<=j<=i-2)推的,顺便一提,初值都是 1 问题是无法转移的情况,一种是 a[i]为 0 时,不能从 dp[i-2]转移至 dp[i] 因为 dp[i-2]的时候一个 b[x]结尾了,a[i-1]是 c[x],b[i+1]就是 a[i] 而题目要求的是最短字符串,所以不会有前导 0,所以这种情况不行 另一种情况,如果 a[j+1]==a[i+1],就一定能合并,而不是最短的,所以也不能转移 我们只需要维护一个 sum 以及各种 c[x]的方案数即可

ac 代码

#include<bits/stdc++.h>
#define mod 998244353
using namespace std;
char s[1000010];
int n,sum,ss[10],a[1000010],dp[1000010];
int main()
{
    freopen("hard.in","r",stdin),freopen("hard.out","w",stdout),scanf("%s",s),n=strlen(s);
    for(int i=1;i<=n;i++)a[i]=s[i-1]-'0',dp[i]=1;
    for(int i=3;i<n;i++)
    {
        if(a[i]!=0)sum=(sum+dp[i-2])%mod,ss[a[i-1]]=(ss[a[i-1]]+dp[i-2])%mod;
        dp[i]=((dp[i]+sum-ss[a[i+1]])%mod+mod)%mod;
    }
    if(a[1]==0)puts("0");else printf("%dn",dp[n-1]);
    return 0;
}

T3- 八卦阵

有一个八卦阵。这个阵可以认为是一个 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[j]+c[b[u][(i-1)%8+1]][b[v][(i-1)%8+1]] 个榔头。 请计算出至少要多少个榔头才能从点 1 走到点 n。

解法

这道题挺水的,感觉还没 T2 难,只要跑最短路就好了,把一个点剖成八个点,然后跑最短路 考虑到会被卡 spfa,优先队列优化一下,不多说咯 QWQ

ac 代码

#include<bits/stdc++.h>
#define inf (2e9)
#define v e[i].to
#define d e[i].w+cb[u.nw]b[v]
using namespace std;
struct node{int to,w,next;}e[300010];
int n,m,cnt,x,y,z,head[100010],c10,b100010,dis100010,used100010;
struct Node{int nw,t,dd;bool operator<(const Node b)const{return dd>b.dd;}}u;
priority_queue<Node>q;
void add(){e[++cnt]={y,z,head[x]},head[x]=cnt;}
void spfa()
{
    while(!q.empty())
    {
        while(usedq.top().nw)q.pop();
        u=q.top(),q.pop(),usedu.nw=1;
        if(u.nw==n)printf("%dn",disu.nw),exit(0);
        for(int i=head[u.nw];i;i=e[i].next)
            if(!usedv)if(u.dd+d<disv)
                disv=u.dd+d,q.push({v,u.t%8+1,disv});
    }
}
int main()
{
    freopen("hammer.in","r",stdin),freopen("hammer.out","w",stdout),scanf("%d%d",&n,&m);
    for(int i=1;i<=8;i++)for(int j=1;j<=8;j++)scanf("%d",&ci);
    for(int i=1;i<=n;i++)for(int j=1;j<=8;j++)scanf("%d",&bi),disi=inf;
    for(int i=1;i<=m;i++)scanf("%d%d%d",&x,&y,&z),add();
    dis1=0,q.push({1,1,0}),spfa();
    return 0;
}