中文题意 Mandarin Chinese
Eugene has a sequence of upper hemispheres and another of lower hemispheres. The first set consists of N upper hemispheres indexed 1 to N and the second has M lower hemispheres indexed 1 to M. The hemispheres in any sequence can have different radii.
He is now set out on building spheres using them. To build a sphere of radius R, he must take one upper half of the radius R and one lower half of the radius R. Also, he can put a sphere into a bigger one and create a sequence of nested concentric spheres. But he can't put two or more spheres directly into another one.
Examples:
If there is a sequence of (D+1) nested spheres, we can call this sequence as a D-sequence.
Eugene has to find out how many different X-sequence are possible (1 <= X <= C). An X sequence is different from another if the index of any of the hemisphere used in one X-sequence is different from the other. Eugene doesn't know how to do it, so Chef agreed to help him. Of course, Chef is too busy now and he asks you to help him.
Input
The first line contains a three integers: N denoting the number of upper sphere halves, M denoting the number of lower sphere halves and C.
The second line contains N space-separated integers U1, U2, ..., UN denoting the radii of upper hemispheres.
The third line contains M space-separated integers L1, L2, ..., LM denoting the radii of lower hemispheres.
Output
Output a single line containing C space-separated integers D1, D2, ..., DC, where Diis the number of ways there are to build i-sequence in modulo 109+7.
Constraints
- 1 ≤ N ≤ 105
- 1 ≤ M ≤ 105
- 1 ≤ C ≤ 103
- 1 ≤ Ui ≤ C
- 1 ≤ Li ≤ C
Subtasks
- Subtask 1: 1 ≤ N, M, C ≤ 10 - 15 points
- Subtask 2: 1 ≤ N, M, C ≤ 100 - 25 points
- Subtask 3: Original constraints - 60 points
Example
Input: 3 4 3 1 2 3 1 1 3 2 Output: 5 2 0
Explanation
We can build spheres with such radii:
R=1 and there are 2 ways to do it. (We can choose any of 2 lower hemispheres with R=1)
R=2 and there is 1 way to do it.
R=3 and there is 1 way to do it.
We can build these 1-sequences:
1->2 and there are 2 ways to do it. ( sphere with radius 1 is inside sphere with radius 2, we can choose any of 2 ways of building sphere with radius 1)
1->3 and there are 2 ways to do it.
2->3 and there is 1 way to do it.
2 + 2 + 1 = 5
We can build these 2-sequences:
1->2->3 and there are 2 ways to do it.
We can't build 3-sequences, because we don't have 4 spheres of different radii.
Mandarin Chinese
题解：当时这题考试来着，想了10分钟，手推了一下，发现对于每个i的答案就是这c个数取i个的组合，然后我就暴力求每个数的组合了。。。居然还打了半小时==，以为有5s时限能卡过，但没想到只有15分。
纪念一下。。
1 var 2 n,m,c,i,j,k,tot,l:longint; 3 ans:int64; 4 vis:array[0..10005]of boolean; 5 a,b,t,rt,d,sum,num:array[0..100005]of longint; 6 procedure dfs(s:longint); 7 var i,su:longint; 8 begin 9 if s=k+1 then 10 begin 11 su:=1; 12 for i:=1 to k do su:=su*d[num[i]] mod 1000000007; 13 // for i:=1 to k do write(num[i],' '); 14 // writeln; 15 ans:=(ans+su)mod 1000000007; 16 exit; 17 end else 18 for i:=num[s-1]+1 to c do 19 begin 20 num[s]:=i; 21 vis[i]:=true; 22 dfs(s+1); 23 vis[i]:=false; 24 end; 25 end; 26 begin 27 readln(n,m,c); 28 for i:=1 to n do begin read(a[i]); inc(t[a[i]]);end; 29 readln; 30 for i:=1 to m do begin read(b[i]); inc(rt[b[i]]);end; 31 for i:=1 to c do 32 begin 33 d[i]:=(t[i]*rt[i]) mod 1000000007; 34 end; 35 // for i:=1 to c do writeln(d[i]); 36 for i:=1 to c do 37 begin 38 k:=i+1; 39 if k>c then begin write(0,' ');continue; end; 40 ans:=0; 41 for l:=1 to 1500 do num[i]:=0; 42 for l:=1 to 1500 do vis[i]:=false; 43 dfs(1); 44 45 write(ans mod 1000000007,' '); 46 end; 47 48 end.
考完之后询问大佬，发现可以dp? 类似于递推，再回去看我的那些组合，后面的组合包含前面的，前面是后面的子问题，用dp思想，f[i][j]表示套i个圆，当前最大的圆的半径是j的方案数。
（其实dp方程表示出来的东西要能表示整个题目的问题和答案）递推方程就是f[i,j]=f[i,j-1]+f[i-1,j-1]*d[i] f[i,j-1]是继承前面一个圈的，f[i-1,j-1]是当前这个圈的方案数。
1 var 2 n,m,c,i,j,k,tot,l,modd:longint; 3 ans:int64; 4 f:array[0..1005,0..1005]of int64; 5 vis:array[0..10005]of boolean; 6 a,b,t,rt,d,sum,num:array[0..100005]of longint; 7 begin 8 modd:=1000000007; 9 readln(n,m,c); 10 for i:=1 to n do begin read(a[i]); inc(t[a[i]]);end; 11 readln; 12 for i:=1 to m do begin read(b[i]); inc(rt[b[i]]);end; 13 for i:=1 to c do 14 begin 15 d[i]:=(t[i]*rt[i]) mod 1000000007; 16 end; 17 // for i:=1 to c do writeln(d[i]); 18 for i:=1 to c do f[0][i]:=f[0,i-1]+d[i]; 19 for i:=1 to c-1 do 20 for j:=1 to c do 21 begin 22 f[i,j]:=(f[i,j-1]+(f[i-1,j-1]*d[j]) mod modd)mod modd; 23 end; 24 for i:=1 to c do write(f[i,c],' '); 25 end.
明显短了不少==
中文题意 mandarin chinese
题解：因为每次都是加1，而且操作如此多次，暴力直接算会超时，操作多次用递归计算又很麻烦，所以。。想到差分。比如你要在x~y区间上加1，操作就是在a[x]位置+1，在a[y-1]的位置-1
最后从1~n扫一遍，a[i]=a[i]+a[i-1]就行了。另外在操作2的时候，你需要从后往前搜（后面不影响前面），也要用差分来做，不然只有50分，所以这个题目，需要用到两个差分来做，
最最后，还要注意负数取mod， (x mod INF+INF)mod INF （INF为模数）
1 var 2 a,q,x,y,id,b:array[-100005..100005]of int64; 3 t,n,m:int64; 4 i,j,l:longint; 5 modd:longint; 6 begin 7 readln(t); 8 modd:=1000000000+7; 9 for l:=1 to t do 10 begin 11 //fillchar(q,sizeof(q),0); 12 // fillchar(x,sizeof(x),0); 13 // fillchar(y,sizeof(y),0); 14 fillchar(b,sizeof(b),0); 15 fillchar(a,sizeof(a),0); 16 readln(n,m); 17 for i:=1 to m do 18 begin 19 readln(q[i],x[i],y[i]); 20 inc(id[i]); 21 end; 22 b[m]:=1; 23 for i:=m downto 1 do 24 begin 25 b[i]:=(b[i]+b[i+1])mod modd; 26 if q[i]=2 then 27 begin 28 // for j:=x[i] to y[i] do id[j]:=((id[j]+id[i])mod modd+modd)mod modd; 29 b[y[i]]:=(b[y[i]]+b[i])mod modd; 30 b[x[i]-1]:=((b[x[i]-1]-b[i])mod modd+modd)mod modd; 31 // id[i]:=0; 32 end; 33 end; 34 for i:=1 to m do 35 if q[i]=1 then 36 begin 37 a[x[i]]:=((a[x[i]]+b[i])mod modd+modd)mod modd; 38 a[y[i]+1]:=((a[y[i]+1]-b[i])mod modd+modd)mod modd; 39 end; 40 for i:=1 to n do 41 begin 42 a[i]:=((a[i-1]+a[i])mod modd+modd)mod modd; 43 write(a[i],' '); 44 end; 45 writeln; 46 end; 47 end.
中文题意 mandarin chinese
题意：给你若干个英文单词，前带+号的要保留，前带-号的要舍去，舍去的方法是用 前缀过滤器，就是以此为前缀的单词会被舍去。求出最少需要的个数和输出该前缀。如果做不到就输出-1.
题解：考试的时候当然想不出了。考后问大佬，可以用字典树做？那就来普及一下字典树吧。据我的理解，就是把一个字符串存入树中，每个节点是一个字符（char），插入字符串时，如果当前字符树中有，树中该字符num[ ]++，然后遍历下去，若没有，就新开一个节点记录，最后应该是一个森林。
在此题中，字典树建好后，你需要再开两个数组，ban 和 admit 。分别记录该节点字符舍去和保留的数目。
最后从根节点 dfs一遍，若遇到admit[now]=0 时，则说明该节点下去没有需保留的单词了，那就返回该节点被ban的字符个数和字符串（前缀），还有做不到的
情况是返回ban的字符个数小于总的要被ban个数，则输出-1.（情理之中，不需要想太多）
1 var 2 n,m,i,ssum,sum,tot,bannum,c,k:longint; 3 s:ansistring; 4 ans:array[0..200005]of ansistring; 5 tree:array[0..200005,0..28]of longint; 6 adm,ban:array[0..200005]of longint; 7 procedure insert(s1:ansistring;c:longint);// 字典树建树 模板 8 var len,now,val,i:longint; 9 begin 10 now:=0;val:=0;len:=length(s1); 11 for i:=1 to len do 12 begin 13 val:=ord(s1[i])-ord('a'); 14 15 if tree[now,val]=0 then 16 begin 17 inc(tot); 18 tree[now,val]:=tot; 19 end; 20 now:=tree[now,val];// 注意，now<>tot 如果字典树中有该字符，就不需要++tot了，直接指为它就好 21 // inc(num[now]); 22 23 if c=1 then inc(adm[now]) else inc(ban[now]); 24 25 end;
// endd[now]:=true; 26 end; 27 procedure dfs(u:longint;nows:ansistring); 28 var i:longint; 29 begin 30 // writeln(nows); 31 // writeln(u); 32 if adm[u]=0 then 33 begin 34 inc(sum); 35 ans[sum]:=nows; 36 ssum:=ssum+ban[u]; 37 exit; 38 end; 39 if ban[u]=0 then exit; 40 for i:=0 to 25 do // 0 所表示的字符为'a' ，从'a'~'z' 41 begin 42 43 if tree[u,i]<>0 then dfs(tree[u,i],nows+chr(i+ord('a'))); 44 45 end; 46 end; 47 48 begin 49 readln(n); 50 for i:=1 to n do 51 begin 52 readln(s); 53 if s[1]='+' then c:=1 else begin c:=0; inc(bannum); end; 54 // writeln(copy(s,3,length(s)-2)); 55 insert(copy(s,3,length(s)-2),c); 56 end; 57 adm[0]:=-1; ban[0]:=-1;//初始化，根节点不参与 58 dfs(0,''); 59 // writeln(adm[1]); 60 // writeln(ans[1]); 61 if ssum<bannum then writeln(-1) else 62 begin 63 writeln(sum); 64 for i:=1 to sum do writeln(ans[i]); 65 end; 66 end.