js333 > 计算机互联网 > flower,flour

原标题:flower,flour

浏览次数:127 时间:2019-11-12

flower,flour

【题目描述】
YouSiki和hhd是一对好朋友。hhd开了一家花店,YouSiki想要在hhd的花店里购买一些自己没有的种类的花。每一种花YouSiki都给它起了一个名字,名字都是由小写字母构成的字符串。现在YouSiki想知道hhd这里有哪些花自己没有。

【输入格式】
第一行两个整数n、m,表示YouSiki拥有的花的种类数以及hhd拥有的花的种类数。
接下来n行,每行一个字符串,表示YouSiki拥有的花的名字(不重复)。
接下来m行,每行一个字符串,表示hhd拥有的花的名字(不重复)。

【输出格式】
每行一个字符串表示一种hhd拥有但YouSiki没有的花的名字。(按输入顺序输出)

【样例输入】
2 3
abc
aaa
abc
aaac
abcd

【样例输出】
aaac
abcd

【数据规模与约定】
对于40%的数据,1≤n,m≤100,花的名字长度不超过100。
对于60%的数据,1≤n,m≤1,000。
对于100%的数据,1≤n,m≤100,000。
保证输入字符串的总长度不超过10,000,000。

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
typedef pair<long long,long long> pll;
const int maxn=100500,base=13131;
long long mod1=10000000001239,mod2=10000000004779;

int n,m;
pll rec[maxn];
char s[5000100];

inline pll hash(){
    pll ret(0,0);
    for (int i=0;s[i]!='';++i){
        ret.first=(ret.first*base+s[i])%mod1;
        ret.second=(ret.second*base+s[i])%mod2;
    }
    return ret;
}

inline bool find(pll x){
    int l=1,r=n,mid;
    while(l<r){
        mid=(l+r)/2;
        if (rec[mid]>x) r=mid-1;
        else if (rec[mid]==x) return true;
        else l=mid+1;
    }
    if (rec[l]==x) return true;
    return false;
}

int main(){
    freopen("flower.in","r",stdin);
    freopen("flower.out","w",stdout);
    scanf("%d%d",&n,&m);
    for (int i=1;i<=n;++i){
        scanf("%s",s);
        rec[i]=hash();
    }
    sort(rec+1,rec+1+n);
    for (int i=0;i<m;++i){
        scanf("%s",s);
        if (!find(hash())) puts(s);
    }
    fclose(stdout);
    return 0;
}

 

【题目描述】 YouSiki和hhd是一对好朋友。hhd开了一家花店,YouSiki想要在hhd的花店里购买一些自己没有的种类的花。每一种花You...

P1077 摆花,p1077摆花

题目描述

小明的花店新开张,为了吸引顾客,他想在花店的门口摆上一排花,共m盆。通过调查顾客的喜好,小明列出了顾客最喜欢的n种花,从1到n标号。为了在门口展出更多种花,规定第i种花不能超过ai盆,摆花时同一种花放在一起,且不同种类的花需按标号的从小到大的顺序依次摆列。

试编程计算,一共有多少种不同的摆花方案。

输入输出格式

输入格式:

第一行包含两个正整数n和m,中间用一个空格隔开。

第二行有n个整数,每两个整数之间用一个空格隔开,依次表示a1、a2、……an。

输出格式:

输出只有一行,一个整数,表示有多少种方案。注意:因为方案数可能很多,请输出方案数对1000007取模的结果。

输入输出样例

输入样例#1:

2 4
3 2

输出样例#1:

2

说明

【数据范围】

对于20%数据,有0<n≤8,0<m≤8,0≤ai≤8;

对于50%数据,有0<n≤20,0<m≤20,0≤ai≤20;

对于100%数据,有0<n≤100,0<m≤100,0≤ai≤100。

NOIP 2012 普及组 第三题

用dp[i][j]表示前i种花,放了j朵的方案数

然后枚举可以已经放置的花的数量k就可以

转移方程:

  dp[i][j]+=(dp[i-1][k])%1000007

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<cmath>
 5 using namespace std;
 6 const int MAXN=101;
 7 int read(int & n)
 8 {
 9     char p='+';int x=0;
10     while(p<'0'||p>'9')
11         p=getchar();
12     while(p>='0'&&p<='9')
13     x=x*10+p-48,p=getchar();
14     n=x;
15 }
16 int n,m;
17 int dp[MAXN][MAXN];
18 int num[MAXN];
19 int main()
20 {
21     read(n);read(m);
22     for(int i=1;i<=n;i++)
23         read(num[i]),dp[i][0]=1;
24     dp[0][0]=1;
25     for(int i=1;i<=n;i++)// 每一种花 
26     {
27         for(int j=1;j<=m;j++) 
28         {
29             for(int k=j;k>=j-num[i]&&k>=0;k--)
30             {
31                 dp[i][j]+=(dp[i-1][k])%1000007;
32             }
33         }
34     }
35     cout<<dp[n][m]%1000007;
36     return 0;
37 }

 

摆花,p1077摆花 题目描述 小明的花店新开张,为了吸引顾客,他想在花店的门口摆上一排花,共m盆。通过调查顾客的喜好,小明列出...

本文由js333发布于计算机互联网,转载请注明出处:flower,flour

关键词:

上一篇:没有了

下一篇:扩展堆数组的大小,C语言动态存储分配金沙js3