整整花费了一个周的时间来做，不是依托自身实力而是依托大佬的帮助才完成了这次比赛。
题目都很有意思，可惜能想出来的并不多。
那集训队的事情就等明年了。
| Solved | A | B | C | D | E | F | G | H | I | J | K | L |
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 12/12 | O | O | O | O | O | O | O | O | O | O | O | O |
- O for passing during the contest
- Ø for passing after the contest
- ! for attempted but failed
- · for having not attempted yet
A
题目描述
给出一段序列，求最少去除几个数使得剩下的数能够组成总和相同的两堆。
$1≤T≤50$，$1≤n≤50$，$0≤a,b≤10^9$，$0≤b−a≤50$
解题思路
根据$a$的个数和$b-a$的总和进行$DP$，滚动数组优化。
AC代码
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
int ans,x[55];
int f[2][110][5015];
int max(int p,int q){return p>q?p:q;}
int main(){
int i,j,k,t,n,a,b;
scanf("%d",&t);
while(t--){
memset(f,0,sizeof(f));
f[0][50][2500]=1;
int p=0;
scanf("%d%d%d",&n,&a,&b);
for(i=1;i<=n;i++)scanf("%d",&x[i]),x[i]-=a;
for(i=1;i<=n;i++){
p^=1;
for(j=50-i;j<=50+i;j++){//50+ a的个数
for(k=0;k<=5000;k++){//2500+ b-a累加
f[p][j][k]=f[p^1][j][k];
if(k-x[i]>=0&&j-1>=0&&f[p^1][j-1][k-x[i]])f[p][j][k]=max(f[p][j][k],f[p^1][j-1][k-x[i]]+1);
if(k+x[i]<=5000&&j-1>=0&&f[p^1][j+1][k+x[i]])f[p][j][k]=max(f[p][j][k],f[p^1][j+1][k+x[i]]+1);
}
}
}
int ans=f[p][50][2500];
for(i=0;i<=100;i++){
if(a*(i-50)+2500<0)continue;
if(a*(i-50)+2500>5000)break;
ans=max(ans,f[p][i][-a*(i-50)+2500]);
}
printf("%d\n",n-(ans-1));
}
return 0;
}
B
题目描述
升级有两种，吃糖直接升一级，或者攒经验。给定经验值，糖果数，各级升级经验数，问最多升到多少级。
解题思路
排完序暴力枚举答案就行了。（虽然可以二分答案）
AC代码
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
using namespace std;
struct E{
int d,i;
bool operator <(const E&a)const{return d>a.d};
}exp[110];
int n,m,a,b,c,t,p[110];
int jud(int x){
int u[110]={0};
int i,temp=n,mx=m;
for(i=1;i<=100;i++){
if(temp&&exp[i].i<=x)u[exp[i].x]=1,temp--;
}
for(i=1;i<=x;i++){
if(!u[i]){
if(mx>=p[i])mx-=p[i];
else return 0;
}
}
return 1;
}
int main(){
int i;
scanf("%d",&t);
while(t--){
scanf("%d%d%d%d%d",&n,&m,&a,&b,&c);
for(i=1;i<=100;i++)p[i]=exp[i].d=(i*a+b)%c,exp[i].i=i;
sort(exp+1,exp+100);
for(i=1;i<=100;i++)if(!jud(i))break;
printf("%d\n",i-1);
}
return 0;
}
C
题目描述
给一棵树，求出所有节点间路径的权值和和异或和的乘积之和。
解题思路
思路一：点分治，求出所有经过当前根的子树中的链，把所有链分别连起来，再减去在多算了的相同子树中链的加和。
思路二：树形DP。还暂时没有实现。
AC代码
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
typedef long long ll;
int max(int a,int b){return a>b?a:b;}
struct Edge{
int end,near;
ll len;
}e[N<<2];
struct Chain{
ll sum,xos;
}sub[N<<4],all[N<<4];
int head[N],cnt;
void add(int a,int b,ll l){
e[++cnt].end=b;e[cnt].len=l;
e[cnt].near=head[a];head[a]=cnt;
}
int n,rt,sum;
int siz[N],mxt[N],vis[N];
void getrt(int v,int fa){
int i,p;
siz[v]=1;mxt[v]=0;
for(i=head[v];i;i=e[i].near){
p=e[i].end;
if(vis[p]||p==fa)continue;
getrt(p,v);
siz[v]+=siz[p];
mxt[v]=max(mxt[v],siz[p]);
}
mxt[v]=max(mxt[v],sum-siz[v]);
if(mxt[v]<mxt[rt])rt=v;
}
void getdis(int v,int fa,ll s,ll x){
int i,p;
sub[++sub[0].sum].sum=s;
sub[sub[0].sum].xos=x;
for(i=head[v];i;i=e[i].near){
p=e[i].end;
if(p==fa||vis[p])continue;
getdis(p,v,(s+e[i].len)%w,x^e[i].len);
}
}
ll allBin[N],subBin[N];
ll calcsub(){
int i,j;
ll ans=0;
for(i=1;i<=sub[0].sum;i++){
ll r=0;
for(j=0;j<32;j++){
if(sub[i].xos&(1<<j))r+=(sub[0].sum-subBin[j])*(1<<j)%w;
else r+=subBin[j]*(1<<j)%w;
r%=w;
}
ans+=r*sub[i].sum%w;
ans%=w;
}
return ans;
}
ll calcall(){
int i,j;
ll ans=0;
for(i=1;i<=all[0].sum;i++){
ll r=0;
for(j=0;j<32;j++){
if(all[i].xos&(1<<j))r+=(all[0].sum-allBin[j])*(1<<j)%w;
else r+=allBin[j]*(1<<j)%w;
r%=w;
}
ans+=r*all[i].sum%w;
ans%=w;
}
return ans;
}
ll sol(int v){
int i,p,j,k;
vis[v]=1;all[0].sum=0;
ll ans=0;
for(i=0;i<32;i++)allBin[i]=0;
for(i=head[v];i;i=e[i].near){
p=e[i].end;
if(vis[p])continue;
sub[0].sum=0;
for(j=0;j<32;j++)subBin[j]=0;
getdis(p,v,e[i].len,e[i].len);
for(j=1;j<=sub[0].sum;j++)
for(k=0;k<32;k++)
if(sub[j].xos&(1<<k))subBin[k]++;
ans-=calcsub();ans%=w;
for(j=0;j<32;j++)allBin[j]+=subBin[j];
for(j=1;j<=sub[0].sum;j++)all[++all[0].sum]=sub[j];
}
ans+=calcall();ans%=w;
for(i=1;i<=all[0].sum;i++){
ans+=all[i].sum*all[i].xos%w;
ans%=w;
}
for(i=head[v];i;i=e[i].near){
p=e[i].end;
if(!vis[p]){
sum=siz[p];mxt[0]=n;rt=0;
getrt(p,v);
ans+=sol(rt);
ans%=w;
}
}
return (ans+w)%w;
}
int main(){
int i,a,b,t;
ll c;
scanf("%d",&t);
while(t--){
scanf("%d",&n);
for(i=1;i<n;i++)
scanf("%d%d%lld",&a,&b,&c),add(a,b,c),add(b,a,c);
rt=0;sum=mxt[0]=n;getrt(1,0);
printf("%lld\n",sol(rt));
memset(vis,0,sizeof(int)*(n+1));
memset(head,0,sizeof(int)*(n+1));
cnt=0;
}
return 0;
}
D
题目描述
一行点，往里头填数，每个点有最低限制，且要满足每个点相对左边的点的数满足给定条件，求最小总数。
解题思路
暴力
AC代码
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
int ans,now,a[110],b[110];
int main(){
int i,t,n;
scanf("%d",&t);
while(t--){
scanf("%d",&n);
for(i=0;i<n;i++)scanf("%d",&a[i]);
for(i=0;i<n;i++)scanf("%d",&b[i]);
now=ans=a[0];
for(i=1;i<n;i++){
now+=b[i];
if(now<a[i]){
ans+=i*(a[i]-now);
now=a[i];
}
ans+=now;
}
printf("%d\n",ans);
}
return 0;
}
E
题目描述
给定$n$个点， 两点间道路长度为两点权值的$gcd$，求最大生成树。（$a_i\leq 1e5$）
解题思路
根据$krustal$算法的原理，枚举边长上界，构造生成树。
AC代码
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
using namespace std;
int n,a[100010],f[100010],map[100010];
int find(int x){return x==f[x]?x:f[x]=find(f[x]);}
int main(){
int i,j,k,l,t,m;
scanf("%d",&t);
while(t--){
long long ans=0,max;
int temp,p,q,u[2]={0},now=0,cnt=0;
scanf("%d",&n);
for(i=1;i<=n;i++)scanf("%d",&a[i]);
sort(a+1,a+n+1);
max=a[n];
for(i=1;i<n;i++)if(a[i]==a[i+1])ans+=a[i],cnt++;
for(i=1;i<=n;i++)map[a[i]]=i;
for(i=1;i<=n;i++)f[i]=i;
for(i=max;i;i--){
now=u[0]=u[1]=0;
for(j=1;j*i<=max;j++){
if(map[j*i]){
u[now]=map[j*i];
if(u[now^1]){
p=find(u[now]);
q=find(u[now^1]);
if(p!=q){
ans+=i;
f[p]=q;
cnt++;
}
}
now^=1;
}
}
if(cnt==n-1)break;
}
printf("%lld\n",ans);
memset(map,0,sizeof(map));
}
return 0;
}
F
题目描述
求满足$(i+1)^i*i ≡ 0(mod m)$的$m$的个数的前缀和，$i\leq 1e7$。
解题思路
先考虑枚举每个数的质因数个数，发现会$T$飞。
故反向从枚举质因数筛原数。
AC代码
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
int ans[N+4],w=998244353;
int prime[N+4]={1,1},a[N/10],tot=1;
int main(){
int i,j,t,n,cnt;
scanf("%d",&t);
for(i=1;i<N;i++)ans[i]=1;
for(i=2;i<N;i++){
if(!prime[i])a[tot++]=i;
for(j=1;j<tot;j++){
if(i*a[j]>=N)break;
prime[i*a[j]]=1;
if(i%a[j]==0)break;
}
}
for(i=1;i<tot;i++){
for(j=1;j*a[i]<N;j++){
cnt=0;
int now=j*a[i],temp=now;
while(now%a[i]==0)now/=a[i],cnt++;
ans[temp-1]=ans[temp-1]*1LL*(cnt*1LL*(temp-1)+1)%w;
ans[temp]=ans[temp]*1LL*(cnt+1)%w;
}
}
for(i=2;i<N;i++)ans[i]=(ans[i]+ans[i-1])%w;
while(t--){
scanf("%d",&n);
printf("%d\n",ans[n]);
}
return 0;
}
G
题目描述
给定一个非常长的序列，求其中所有上升子序列的长度 $k$次方之和，答案对$1e9+7$取模，$k\leq 20$。
解题思路
先考虑$k=1$的情况。可以想到，从前到后遍历数组，用一个树状数组维护当前所有以$x$为结尾的上升子序列长度的和前缀和，每次加入（$y+query(x-1)$）更新。
在考虑$k\geq 2$的情况。维护$k+1$个树状数组，第$i$个树状数组记录上升子序列长度$l^i$的和的前缀和，更新的时候用二项式定理扫一遍即可。
注意到数据较大，需要离散化。
AC代码
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
using namespace std;
typedef long long ll;
int n,k,x[N],y[N],seq[N*10],M;
struct number{
int a,b,i;
bool operator<(const number&p)const{return a<p.a;}
}a[N];
ll w=1e9+7,t[21][N],c[25][25];
int l(int x){return x&(-x);}
void add(int d,int x,ll p){
while(x<=M){
t[d][x]+=p;
t[d][x]%=w;
x+=l(x);
}
}
ll query(int d,int x){
ll ans=0;
while(x){
ans+=t[d][x];
ans%=w;
x-=l(x);
}
return ans;
}
int main(){
int i,j,m,T;
ll now[25];
for(i=0;i<=20;i++)c[i][0]=1;
for(i=1;i<=20;i++)for(j=1;j<=20;j++)c[i][j]=c[i-1][j-1]+c[i-1][j];
scanf("%d",&T);
while(T--){
scanf("%d%d",&n,&k);
for(i=1;i<=n;i++)scanf("%d%d",&x[i],&y[i]),a[i].a=x[i],a[i].b=y[i],a[i].i=i;
sort(a+1,a+n+1);
for(i=1;i<=n;i++)seq[a[i].a]=a[i].a==a[i-1].a?seq[a[i-1].a]:seq[a[i-1].a]+1;
M=seq[a[n].a]+1;
for(i=1;i<=n;i++){
int X=seq[x[i]]+1,Y=y[i];
for(j=0;j<=k;j++)now[j]=query(j,X-1);
for(j=0;j<=k;j++){
ll tot=0;
for(m=0;m<=j;m++)tot+=Y*c[j][m]%w*now[m]%w,tot%=w;
add(j,X,(tot+Y)%w);
}
}
printf("%lld\n",query(k,M));
for(i=0;i<=k;i++)for(j=0;j<=M;j++)t[i][j]=0;
}
return 0;
}
H
题目描述
给定五张牌，问加入两张牌成为顺子有多少种情况。
解题思路
巨麻烦的分类讨论？
不，这题可以直接暴力。
AC代码
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
char a[8];
int x[150];
int main(){
int t,i,j,k;
x['A']=1;x['2']=2;x['3']=3;x['4']=4;
x['5']=5;x['6']=6;x['7']=7;x['8']=8;
x['9']=9;x['T']=10;x['J']=11;x['Q']=12;
x['K']=13;
scanf("%d",&t);
while(t--){
int t[25]={0},ans=0;
int used[60]={0},num[20]={0};
scanf("%s",a);
for(i=0;i<5;i++){
int s=x[a[i]];
t[s]++;
used[s*4+num[s]++]++;
if(a[i]=='A')t[14]++;
}
for(i=4;i<56;i++){
if(used[i])continue;
t[i/4]++;
for(j=i+1;j<56;j++){
if(used[j])continue;
t[j/4]++;
int flag=0;
for(k=1;k<=13;k++){
if(t[k]&&t[k+1]&&t[k+2]&&t[k+3]&&(t[k+4]||(k+4==14&&t[1]))){
flag=1;
break;
}
}
if(flag)ans++;
t[j/4]--;
}
t[i/4]--;
}
printf("%d\n",ans);
}
return 0;
}
I
题目描述
给定一个只含有$ATGC$的环，$ATGC$分别代表一种矩阵，定义一次操作为所有矩阵乘上下一个矩阵，问$k$次操作后（$k\leq 1e9$）的环。
解题思路
列个表发现$ATGC$之间的乘积具有异或的性质。
然后利用$k$的可加性，找到规律，倍增解决。
AC代码
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
char a[4]={'A','T','G','C'},c[1000010];
int res[4][4]={{0,1,2,3},{1,0,3,2},{2,3,0,1},{3,2,1,0}};
int now[2][1000010];
int map[510];
int main(){
int i,t,n,k,m;
scanf("%d",&t);
map['A']=0;map['T']=1;
map['G']=2;map['C']=3;
while(t--){
m=0;
int p,cnt;
scanf("%d%d%s",&n,&k,c);
for(i=0;i<n;i++)now[1][i]=map[c[i]];
while(k){
p=1;cnt=0;
while(k>=(1<<cnt+1))cnt++;
int d=(1<<cnt);
k-=d;
for(i=0;i<n;i++)now[m][i]=res[now[m^1][i]][now[m^1][(i+d)%n]];
m^=1;
}
for(i=0;i<n;i++)printf("%c",a[now[m^1][i]]);
printf("\n");
}
return 0;
}
J
题目描述
求满足方程组
$x_1+x_2+…+x_n=m$
$0\leq x_i \leq a_i$的解的个数， 对一堆素数的乘积取模。
解题思路
首先，求答案用插板法，写出组合数。
然后，分别对每一个模数取模，得到相应答案。
最后，把取模得到的数用中国剩余定理得到最终答案。
毒瘤爆$long long$，CRT需要龟速乘AC代码
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
using namespace std;
typedef long long ll;
int n,k;
ll m,v[20],ans[20],p[20];
ll jc[20][100010];
ll mul(ll x,ll y,ll mod) {
ll res=0;x%=mod;
for(;y;y>>=1,(x*=2)%=mod)if(y&1)(res+=x)%=mod;
return res;
}
void exgcd(ll a,ll b,ll &x,ll &y){
if(!b){x=1,y=0;return;}
exgcd(b,a%b,y,x);
y-=a/b*x;
}
ll China(int n,ll *m,ll *a){
int i;
ll M=1,ans=0,y,x=0;
for(i=0;i<n;i++)M*=m[i];
for(i=0;i<n;i++){
ll w=M/m[i];
exgcd(m[i],w,x,y);
ans=(ans+mul(mul(y,w,M),a[i],M))%M;
}
return (ans%M+M)%M;
}
ll pw(ll x,int y,int num){
int i;
ll ans=1;x%=p[num];
for(i=y;i;i>>=1,x=x*x%p[num])if(i&1)ans=ans*x%p[num];
return ans;
}
ll c(ll x,ll y,int num){
if(x<y)return 0;
return mul(mul(jc[num][x],pw(jc[num][y],p[num]-2,num),p[num]),pw(jc[num][x-y],p[num]-2,num),p[num]);
}
ll lucas(ll x,ll y,int num){
if(!y)return 1;
return mul(lucas(x/p[num],y/p[num],num),c(x%p[num],y%p[num],num),p[num]);
}
int main(){
int i,s,cnt,t,j;
ll temp;
scanf("%d",&t);
while(t--){
for(i=0;i<20;i++)ans[i]=0;
scanf("%d%lld%d",&n,&m,&k);
for(i=0;i<n;i++)scanf("%lld",&v[i]);
for(i=0;i<k;i++)scanf("%lld",&p[i]);
for(i=0;i<k;i++){
jc[i][0]=1;
for(j=1;j<=1e5;j++)jc[i][j]=jc[i][j-1]*j%p[i];
}
s=(1<<n);
for(i=0;i<s;i++){
cnt=1;
temp=0;
for(j=0;j<n;j++){
if(i&(1<<j)){
cnt*=-1;
temp+=v[j]+1;
}
}
if(temp>m)continue;
for(j=0;j<k;j++)
ans[j]=(ans[j]+mul(cnt<0?p[j]-1:1,lucas(m-temp+n-1,n-1,j),p[j]))%p[j];
}
printf("%lld\n",China(k,p,ans));
}
return 0;
}
K
题目描述
多次操作区间对最小值（定义为非零的最小值）取模，求取模前后该区间数的总和。
解题思路
线段树，区间和为$0$时特判剪枝。
AC代码
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
typedef long long ll;
struct SegmentTree{
int l,r;
ll sum,min;
}t[N<<3];
int n;
ll a[N];
ll minf(ll a,ll b){
if(!a||!b)return b|a;
return a>b?b:a;
}
void build(int p,int l,int r){
if(l==r){
t[p].l=t[p].r=l;
t[p].min=t[p].sum=a[l];
return;
}
t[p].l=l;t[p].r=r;
build(p<<1,l,(l+r)>>1);
build(p<<1|1,((l+r)>>1)+1,r);
t[p].sum=t[p<<1].sum+t[p<<1|1].sum;
t[p].min=minf(t[p<<1].min,t[p<<1|1].min);
}
ll query(int p,int l,int r){
int L=t[p].l,R=t[p].r;
if(l>R||r<L)return 0;
if(l<=L&&r>=R)return t[p].sum;
return query(p<<1,l,r)+query(p<<1|1,l,r);
}
ll minquery(int p,int l,int r){
int L=t[p].l,R=t[p].r;
if(l>R||r<L)return 0;
if(l<=L&&r>=R)return t[p].min;
return minf(minquery(p<<1,l,r),minquery(p<<1|1,l,r));
}
ll modify(int p,int l,int r,ll k){
int L=t[p].l,R=t[p].r;
if(l>R||r<L||!t[p].sum)return 0;
if(L==R)return t[p].min=t[p].sum%=k;
modify(p<<1,l,r,k);modify(p<<1|1,l,r,k);
t[p].min=minf(t[p<<1].min,t[p<<1|1].min);
t[p].sum=t[p<<1].sum+t[p<<1|1].sum;
return t[p].min;
}
void print(){
int i;
for(i=1;i<=44;i++)
if(t[i].l)printf("%d %d %lld %lld\n",t[i].l,t[i].r,t[i].sum,t[i].min);
printf("\n");
}
int main(){
int q,i,l,r,t;
scanf("%d",&t);
while(t--){
scanf("%d%d",&n,&q);
for(i=1;i<=n;i++)scanf("%lld",&a[i]);
build(1,1,n);
for(i=0;i<q;i++){
scanf("%d%d",&l,&r);
ll mn=minquery(1,l,r);
if(!mn)printf("0 0\n");
else{
printf("%lld ",query(1,l,r));
modify(1,l,r,mn);
printf("%lld\n",query(1,l,r));
}
//print();
}
}
return 0;
}
L
题目描述
告诉每回合出现哪些神龙，每回合怎么得钱，买一个神龙一块钱，问多少回合能集齐要求的神龙。
解题思路
二分答案。注意$p$爆$long long$。
AC代码
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
int n,m,p,k,l;
int a[N],b[N],tmp[N];
int f(int x,int y){return x*m+y;}//1->2
int g(int x){return x/m;}//2->1
int seq[N];
int jud(int num){
int i,mx=f(num,0)-1;
memset(seq,0,sizeof(seq));
memset(tmp,0,sizeof(tmp));
for(i=0;i<l;i++)tmp[b[i]]++;
for(i=mx;i>=0;i--){
if(tmp[a[i]]){
seq[g(i)]++;
tmp[a[i]]--;
}
}
for(i=0;i<l;i++)if(tmp[b[i]])return 0;
long long now=p;
for(i=0;i<num;i++){
now-=seq[i];
if(now<0)return 0;
if(now<l)now+=now/k+p;
}
return 1;
}
int main(){
int i,j,q,t;
scanf("%d",&t);
while(t--){
scanf("%d%d%d%d%d",&n,&m,&p,&k,&l);
for(i=0;i<n;i++)for(j=0;j<m;j++)scanf("%d",&a[f(i,j)]);
for(i=0;i<l;i++)scanf("%d",&b[i]);
int l=0,r=n;
while(l<r){
int mid=(l+r)>>1;
if(jud(mid))r=mid;
else l=mid+1;
}
if(!jud(l))l++;
if(l<=n)printf("%d\n",l);
else printf("-1\n");
}
return 0;
}