Wannafly挑战赛9

朱雀 2022-05-31 01:54 173阅读 0赞

## A ##

## 题目描述 ##

##  ##

给定n个正整数，请找出其中有多少个数x满足：在这n个数中存在数y=kx，其中k为大于1的整数

## 输入描述: ##

第一行输入一个n
       
        
       
        
         
        接下来一行输入n个正整数a
        
         i

## 输出描述: ##

输出符合条件个数

## 输入 ##

5
    1 2 3 4 5

## 输出 ##

1≤n,ai≤1000000

题目分析:类似素数打表一样，打表就可以了。

代码如下:

#include<stdio.h>
     
    const int maxn=1e6+5;
    int a[maxn];
     
    int main()
    {
        int n,x,ans=0;
        scanf("%d",&n);
        for(int i=1;i<=n;i++){
            scanf("%d",&x);
            a[x]++;
        }
        for(int i=1;i<=maxn/2;i++){
            if(a[i]==0)continue;
            for(int j=i+i;j<maxn;j+=i){
                if(a[j]){ans+=a[i];break;}
            }
        }
        printf("%d\n",ans);
        return 0;
    }

设s,t为两个字符串，定义f(s,t) = t的子串中，与s相等的串的个数。如f("ac","acacac")=3, f("bab","babab")=2。现在给出n个字符串，第i个字符串为s i。你需要对 ![301599_1517378935368_equation_tex_5Cforall_201_20_5Cleq_20i_20_5Cleq_20n][]，求出 ![301599_1517378946727_equation_tex_5Cprod_7Bj_3D1_7D_5En_20_7Bf_28s_i_2Cs_j_29_7D][]，由于答案很大，你只需要输出对 998244353取模后的结果。

## 输入描述: ##

第一行一个整数n。
    接下来n行每行一个仅由英文字母构成的非空字符串，第i个字符串代表si。

## 输出描述: ##

共n行，第i行输出对 998244353取模的结果。

## 输入 ##

1
    BALDRSKYKirishimaRain

## 输出 ##

1 ≤ n ≤ 106，所有字符串的总长度不超过2*106

题目分析:当s为最短串的时候才有可能不为0，其他情况一律为0，用最短的串去跑KMP就好了

代码如下:

#include<iostream>
    #include<cstdio>
    #include<cmath>
    #include<cstring>
    #define ll long long
    using namespace std;
     
    const int mod=998244353;
    const int maxn=1e6+100;
    string str[maxn];
    int nxt[maxn*2];
     
    void get_next(string s,int len)//得到匹配串的next数组
    {
        int j=0,k=-1;
        nxt[0]=-1;
        while(j<len){
            if(k==-1||s[j]==s[k]){
                j++;k++;
                nxt[j]=k;
            }
            else
                k=nxt[k];
        }
    }
    int KMP(string s1,string s2)//返回串2在串1中个数
    {
        int len1=s1.length();
        int len2=s2.length();
        get_next(s2,len2);
        int i=0,j=0,ans=0;
        while(i<len1){
            if(j==-1||s1[i]==s2[j])
                i++,j++;
            else
                j=nxt[j];
            if(j==len2){
                ans++;
                j=nxt[j];
            }
        }
        return ans;
    }
    int main()
    {
        int n;
        scanf("%d",&n);
        int len=maxn*2,pos;
        for (int i=1;i<=n;i++) {
            cin>>str[i];
            if (len>str[i].size()) {
                len=str[i].size();
                pos=1;
            }
        }
        string s=str[pos];
        ll ans=1;
        for (int i=1;i<=n;i++) {
            ans=(ans*KMP(str[i],s)%mod)%mod;
            if (ans==0) break;
        }
        for (int i=1;i<=n;i++) {
            if (s==str[i]) printf("%lld\n",ans);
            else printf("0\n");
        }
    }

小W在计算一个数列\{A n\},其中A 1=1,A 2=2,A n+2=A n+1\+A n。尽管他计算非常精准，但很快他就弄混了自己的草稿纸，他找出了一些他计算的结果，但他忘记了这些都是数列中的第几项。

输入描述:

每行包括数列中的一项Ak(k<=100000)。 总行数T<=30。

## 输出描述: ##

对于每一项Ak，输出一行包括一个正整数k表示输入中数是数列的第几项。

## 输入 ##

2
    3
    5
    8
    13

## 输出 ##

2
    3
    4
    5
    6

题目分析:直接跑出前面1e5项，肯定是不行的，内存存不下，我们mod1e9+7，像hash一样，减小了空间存储。

代码如下:

import java.math.BigInteger;
    import java.util.Scanner;
     
    public class Main{
        public static void main(String[] args) {
            BigInteger [] dp=new BigInteger [100001];
            final BigInteger mo=BigInteger.valueOf(100000007);
            dp[1]=BigInteger.ONE;
            dp[2]=BigInteger.valueOf(2);
            for (int i=3;i<=100000;i++) {
                if (i>=3) dp[i]=(dp[i-1].add(dp[i-2]));
                dp[i]=dp[i].mod(mo);
            }
            Scanner cin=new Scanner (System.in);
            while (cin.hasNext()) {
                BigInteger  n=cin.nextBigInteger();
                n=n.mod(mo);
                int a=0;
                for (int i=1;i<=100000;i++) {
                    if (dp[i].compareTo(n)==0) {
                        a=i;
                        break;
                    }
                }
                System.out.println(a);
            }
        }
    }

[301599_1517378935368_equation_tex_5Cforall_201_20_5Cleq_20i_20_5Cleq_20n]: https://uploadfiles.nowcoder.net/files/20180131/301599_1517378935368_equation?tex=%5Cforall%201%20%5Cleq%20i%20%5Cleq%20n
[301599_1517378946727_equation_tex_5Cprod_7Bj_3D1_7D_5En_20_7Bf_28s_i_2Cs_j_29_7D]: https://uploadfiles.nowcoder.net/files/20180131/301599_1517378946727_equation?tex=%5Cprod_%7Bj%3D1%7D%5En%20%7Bf%28s_i%2Cs_j%29%7D