首页 > > 程序设计 > C/C++ >

11.7

2018-06-17 21:36:03来源：未知阅读 ()

812. 单词默写
★☆ 输入文件：engzam.in 输出文件：engzam.out 简单对比
时间限制：1 s 内存限制：128 MB
【问题描述】
小D前一段日子刚刚参加了一次非常苛刻的英语考试。
考试不仅包括了听力、选择、填空等基本题型，还包括了一种特殊的单词默写题。这类题目都是按照以下形式给出的：
在本学期你所学的所有前缀是B的单词中，在课本中出现次数不少于L的有多少个。
例如小D这个学期只学过三个单词a、ab、bc，它们出现的次数分别是1、2、3；若给出询问（B = a，L = 2），那么前缀为a的单词一共有两个，是a和ab，其中频率不少于2的只有一个，是ab。
这个学期小D学过的单词非常多，而考试给出的这类询问也非常多。这么困难的任务小D当然不可能解决，于是这个问题被交给了你。
【输入文件】
输入文件第一行包含两个用空格隔开的整数N、M，分别表示小D本学期学过的单词数和考试中出现的询问数。
接下来N行，每行包含用空格隔开的一个单词A和一个整数P，描述小D本学期学过的一个单词A以及其出现的次数P。
接下来M行，每行包含用空格隔开的一个单词B和一个整数L，描述考试中给出的一个询问。
你可以假定所有单词均由小写字母组成，且长度不超过10。
【输出文件】
输出文件一共包含M行。
对于每个考试的询问输出一行一个整数，表示该问题的答案。
【样例输入】
3 3
a 1
ab 2
bc 3
a 2
a 1
a 3
【样例输出】
1
2
0
【样例说明】
前缀为a的单词一共有两个，是a和ab，出现次数分别为1和2。
【评分标准】
本题包含10个测试点，对于每个测试点，如果你的输出和标准输出完全一样则得到该测试点的全部分数，否则得0分。
【数据规模】
对于50%的测试数据，满足N、M ≤ 1 000
对于100%的测试数据，满足N、M ≤ 100 000，P、L ≤ 100 000

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<iostream>
 4 #include<algorithm>
 5 #define ll long long
 6 using namespace std;
 7 void Emine(){
 8     freopen("engzam.in","r",stdin);
 9     freopen("engzam.out","w",stdout);
10 }
11 int n,m,p,l,ans,cnt,i;
12 string s;
13 struct tree{int flag,son[30];}t[500001];
14 int read(){
15     int x=0,f=1;char ch=getchar();
16     while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
17     while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
18     return x*f;
19 }
20 void build(int at,int now){
21     if(now==s.length()){
22         t[at].flag+=p;
23         return;
24     }
25     int num=s[now]-'a';
26     if(!t[at].son[num])t[at].son[num]=++cnt;
27     build(t[at].son[num],now+1);
28     return;
29 }
30 void find(int at){
31     if(t[at].flag>=l)ans++;
32     for(int j=0;j<26;j++)if(t[at].son[j])find(t[at].son[j]);
33 }
34 void query(int at,int now){
35     if(now==s.length()){
36         find(at);
37         return;
38     }
39     int num=s[now]-'a';
40     if(!t[at].son[num])return;
41     query(t[at].son[num],now+1);
42     return;
43 }
44 int main(){
45     Emine();
46     n=read(),m=read();
47     for(int i=1;i<=n;i++){
48         cin>>s;p=read();
49         build(0,0);
50     }
51     for(int i=1;i<=m;i++){
52         ans=0;
53         cin>>s;l=read();
54         query(0,0);
55         printf("%d\n",ans);
56     }
57     return 0;
58 }

View Code

813. 小D的背包问题
★★☆   输入文件：baga.in   输出文件：baga.out   简单对比
时间限制：1 s   内存限制：128 MB
【问题描述】
放寒假了，小D终于可以回家了。一个学期之后他有太多的东西想带回家。
小D的背包可以被看作一个4行N列的矩阵，每个物品放入背包的物品恰好需要占据两个相邻的方格，任意两个物品不能占据相同的方格。为了充分的利用自己的背包，小D希望背包的所有空间都放置了物品，也就是说，背包中恰好放入了2N个物品。
现在小D想知道，不同的放置方案数有多少种。
【输入文件】
       输入文件只有一行，包含一个正整数描述N。
【输出文件】
输出一行，一个整数表示不同的方案数。因为答案可能很大，你只需要输出结果对997取模后的结果。
【样例输入】
2
【样例输出】
5
【样例说明】
       五种不同的放置方案如下：

【评分标准】
       本题包含10个测试点，对于每个测试点，如果你的输出和标准输出完全一样则得到该测试点的全部分数，否则得0分。
【数据规模】
       对于40%的测试数据，N ≤ 1 000
       对于70%的测试数据，N ≤ 1 000 000
       对于100%的测试数据，N ≤ 1 000 000 000

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<iostream>
 4 #include<algorithm>
 5 #define ll long long
 6 #define Mod 997 
 7 using namespace std;
 8 void Emine(){
 9     freopen("baga.in","r",stdin);
10     freopen("baga.out","w",stdout);
11 }
12 int read(){
13     int x=0,f=1;char ch=getchar();
14     while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
15     while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
16     return x*f;
17 }
18 class matrix{
19 public:
20     int h[5][5];
21     matrix(){memset(h,0,sizeof(h));}
22 };
23 matrix a,b;
24 int n;
25 matrix multiply(matrix x,matrix y){
26     matrix tmp;
27     for(int i=1;i<=4;i++)
28         for(int j=1;j<=4;j++)
29             for(int k=1;k<=4;k++)
30                 tmp.h[i][j]=(tmp.h[i][j]+x.h[i][k]*y.h[k][j])%Mod;
31     return tmp; 
32 }
33 int main(){
34     Emine();
35     int f[4]={1,1,5,11};
36     a.h[1][1]=1;a.h[1][2]=5;a.h[1][3]=1;a.h[1][4]=-1;a.h[2][1]=1,a.h[3][2]=1,a.h[4][3]=1;
37     b.h[1][1]=11;b.h[2][1]=5;b.h[3][1]=1;b.h[4][1]=1;
38     n=read();if(n<4){printf("%d\n",f[n]);return 0;}
39     matrix ans;
40     ans.h[1][1]=1;ans.h[2][2]=1;ans.h[3][3]=1;ans.h[4][4]=1;
41     n-=3;
42     while(n>0){
43         if(n%2==1)
44             ans=multiply(ans,a);
45         a=multiply(a,a);
46         n>>=1;
47     }
48     ans=multiply(ans,b);
49     printf("%d",(ans.h[1][1]+Mod)%Mod);
50     return 0;
51 }

View Code

814. 工作指派
★☆   输入文件：dividea.in   输出文件：dividea.out   简单对比
时间限制：1 s   内存限制：128 MB
【问题描述】
小D有N份工作要完成，每一份工作有一个难度系数。由于工作数目太多了，小D光靠自己的能力是无法完成的，所以他打算雇佣很多工人很多人来帮他。工人是非常精明的，他们要求按照工作数目收费，如果分派给他的工作数目小于k，他们将不愿意接受。工人完成一份工作的收费是C。但是，小D也是很精明的老板，考虑到有些工作之间很类似，完成了一份工作之后可以很轻松的完成下一份工作，所以他提出了这样的要求，工人能够得到的报酬将是C + (maxB–minB)^2。其中，maxB表示工人接受的所有工作中的难度系数的最大值，minB是最小值。显然，如果工人只接受了一份工作，那么他将得到的报酬是C。
作为小D的助理，现在你需要告诉他，为了完成这些工作，他至少要支付多少钱给工人？
【输入文件】
       第一行三个非负整数N、k、C，意义如题所述；
       第二行N个正整数分别描述N份工作的难度系数。
【输出文件】
一个整数表示小D最少需要支付的工资。
【样例输入】
2 1 1
2 4
【样例输出】
2
【样例说明】
       如果分给一个工人做，收费为1 + (4–2)2 = 5；
如果分给两个工人作，收费为1 + 1 = 2；
所以最小收费为2。
【评分标准】
       本题包含10个测试点，对于每个测试点，如果你的输出和标准输出完全一样则得到该测试点的全部分数，否则得0分。
【数据规模】
       对于50%的测试数据，满足1 ≤ k ≤ N ≤ 20
对于100%的测试数据，满足
1 ≤ k ≤ N ≤ 10 000
0 < C ≤ 1 000 000
难度系数 ≤ 100 000 000

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<iostream>
 4 #include<algorithm>
 5 #define ll long long
 6 #define maxn 10005
 7 #define inf 1000000000000000
 8 using namespace std;
 9 void Emine(){
10     freopen("dividea.in","r",stdin);
11     freopen("dividea.out","w",stdout);
12 }
13 int read(){
14     int x=0,f=1;char ch=getchar();
15     while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
16     while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
17     return x*f;
18 }
19 int n,k,c,a[maxn];
20 ll f[maxn];
21 int main(){
22     Emine();
23     int n=read(),k=read(),c=read();
24     for(int i=1;i<=n;i++)a[i]=read();
25     sort(a+1,a+n+1);
26     for(int i=1;i<=n;i++){
27         f[i]=inf;
28         for(int j=0;j<=i-k;j++)
29             f[i]=min(f[i],f[j]+1ll*(a[i]-a[j+1])*(a[i]-a[j+1]));
30         f[i]+=c;
31     }
32     printf("%d\n",f[n]);
33     return 0;
34 }