Fork me on GitHub

20191106模拟赛

给我也整一个这样的评测环境

huanj

A

思路

考虑两个人的答案,发现如果这对于某个特定的问题,如果这两个人的答案相同的话,那么他们可以将分数同时$+1$或者无变化.而若两个人的答案不同的话,显然我们选择分数相对较少的人加分更优.
但是需要注意一个问题,我们需要先判断两个人答案相同的情况,因为若先判断答案不同的情况的话,发现可能会出现一个人已经到达了目标分数,而另一个人没到,这时候再判断答案一样的话显然两个人都不能再加分了.

代码

1
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
#include <bits/stdc++.h>

inline int read () {
int s = 0 , w = 1;
char ch = getchar ();
while ( ch > '9' || ch < '0' ) { if ( ch == '-' ) w = -1; ch = getchar ();}
while ( ch >= '0' && ch <= '9' ) { s = s * 10 + ch - '0'; ch = getchar ();}
return s * w;
}

using namespace std;

const int N = 1e5 + 10;

int n , x , y;
char A[N] , B[N];

int main ( void ) {
freopen ( "A.in" , "r" , stdin );
freopen ( "A.out" , "w" , stdout );
int T = read ();
while ( T-- ) {
n = read () , x = read () , y = read ();
scanf ( "%s%s" , A + 1 , B + 1 );
int tmp = 0;
for ( int i = 1 ; i <= n ; i++ ) {
if ( A[i] == B[i] )
tmp++;
}
int NowScoreA = 0 , NowScoreB = 0;
NowScoreA = min ( tmp , min ( x , y ) );
NowScoreB = min ( tmp , min ( x , y ) );
for ( int i = 1 ; i <= n ; i++ ) {
if ( NowScoreB == y && NowScoreA == x )
break;
if ( A[i] != B[i] ) {
if ( NowScoreB < NowScoreA ) {
if ( NowScoreB < y )
NowScoreB++;
else if ( NowScoreA < x )
NowScoreA++;
}
else if ( NowScoreA <= NowScoreB ) {
if ( NowScoreA < x )
NowScoreA++;
else if ( NowScoreB < y )
NowScoreB++;
}
}
}
//printf ( "%d %d %d %d\n" , x , y , NowScoreA , NowScoreB );
if ( NowScoreA == x && NowScoreB == y )
puts ( "Yes" );
else
puts ( "No" );
}
return 0;
}

B

思路

首先,我们可以发现,大多数的数字一定为$1$.我们假设现在数列里只有$1,2$这两种数字的话,那么为了满足题目中要求的条件,那么非一的数字的个数一定是最多的.
我们设

那么可以算出$k$的取值范围最多为$11$,即最多会出现$11$个非零的数字.数字不多,所以我们可以考虑把这$11$个数字搜出来.
我们设集合$p$为所有非一的数字构成的集合,$i$为集合中的元素,$k$为$p$集合中元素的个数,$A=\sum_i a_i,B=\Pi_i a_i$.
那么因为有$B=A+n-k$,即$n=B-A+k$.所以我们可以去搜索$B-A+k$的这一部分.
但是发现…直接搜索的话..复杂度会上天?然后我们考虑怎么剪枝.

  • 可行性剪枝:一旦超过$3000$就剪掉
  • 去重:例如$2,3,2,3,4,5$和$2,2,3,3,4,5$是相似的指数不同的排列所以我们搜的时候只搜后面的情况然后通过组合数直接算出来就行了
  • 预处理:我们发现每次的搜索过程都是一样的只是$n$不同 我们现在搜一次将答案存到桶里每次询问直接输出就行了

代码

1
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
#include<bits/stdc++.h>
using namespace std;

typedef long long LL;

const LL p=1e9+7;


const int N=3e3+10;

LL n;

LL f[20][N];

LL C[N][20];

LL h[20],ni[20];


void dfs(LL x,LL y,LL z,LL s,LL k,LL g) {
if(y>10000) return;
if(z-s>3000) return;
if(x>13) return;
f[x-1][z-s]+=(h[x-1]*g%p)*ni[k]%p,f[x-1][z-s]%=p;
dfs(x+1,y,z*y,s+y,k+1,g);
for(LL i=y+1;i<=20000;i++) {
if((z*i-s-i)>3000) break;
dfs(x+1,i,z*i,s+i,1,g*ni[k]%p);
}
return;
}

LL ksm(LL x,LL y) {
LL Ans=1;
for(;y;y>>=1,x*=x,x%=p)
if(y&1) Ans*=x,Ans%=p;
return Ans;
}



int main() {
freopen("B.in","r",stdin);
freopen("B.out","w",stdout);
int t;
cin>>t;
h[0]=1;
for(LL i=1;i<=13;i++) h[i]=h[i-1]*i%p;
for(LL i=0;i<=13;i++) ni[i]=ksm(h[i],p-2);
dfs(1,2,1,0,0,1);
C[0][0]=1;
for(int i=1;i<=3000;i++) {
C[i][0]=1;
for(int j=1;j<=min(i,12);j++) C[i][j]=C[i-1][j]+C[i-1][j-1]%p;
}
for(int i=1;i<=12;i++)
for(int j=0;j<=3000;j++) f[i][j]%=p;
while(t--) {
cin>>n;
LL Ans=0;
for(int i=1;i<=min(12ll,n);i++)
Ans+=f[i][n-i]*C[n][i]%p;
Ans%=p;
cout<<Ans<<endl;
}
}

C

思路

发现若对于每次询问都进行一次$floyd$的话,那么时间复杂度显然上天.而考虑$floyd$算法的实质就是在经过了前i个点的情况下的最短路,那么我们可以选择离线.
我们对于每个询问,也把询问按照权值排序.然后我们对于每次询问,使用能更新的节点去更新$G$数组即可.

代码

1
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
#include <bits/stdc++.h>

inline int read () {
int s = 0 , w = 1;
char ch = getchar ();
while ( ch > '9' || ch < '0' ) { if ( ch == '-' ) w = -1; ch = getchar ();}
while ( ch >= '0' && ch <= '9' ) { s = s * 10 + ch - '0'; ch = getchar ();}
return s * w;
}

using namespace std;

const int N = 205;
const int M = 20005;

int n , m;
long long G[N][N];

struct Que {
int st , ed;
int w;
int id;
} query[M];
struct Node {
int pos;
int val;
} nd[N];

inline bool cmp1 ( Node x , Node y ) {
return x.val < y.val;
}
inline bool cmp2 ( Que x , Que y ) {
return x.w < y.w;
}

long long ans[M];

int main ( void ) {
freopen ( "C.in" , "r" , stdin );
freopen ( "C.out" , "w" , stdout );
int T = read ();
while ( T-- ) {
memset ( ans , 0 , sizeof ( ans ) );
n = read () , m = read ();
for ( int i = 1 ; i <= n ; i++ ) {
nd[i].val = read ();
nd[i].pos = i;
}
for ( int i = 1 ; i <= n ; i++ )
for ( int j = 1 ; j <= n ; j++ )
G[i][j] = read ();
sort ( nd + 1 , nd + 1 + n , cmp1 );
for ( int i = 1 ; i <= m ; i++ ) {
query[i].st = read () , query[i].ed = read ();
query[i].w = read ();
query[i].id = i;
}
sort ( query + 1 , query + 1 + m , cmp2 );
int NumNode = 1;
for ( int now = 1 ; now <= m ; now++ ) {
while ( NumNode <= n && nd[NumNode].val <= query[now].w ) {
int kk = nd[NumNode].pos ;
// printf ( "%d " , kk );
for ( int i = 1 ; i <= n ; i++ )
for ( int j = 1 ; j <= n ; j++ )
G[i][j] = min ( G[i][j] , G[i][kk] + G[kk][j] );
NumNode++;
}
int l = query[now].st , r = query[now].ed;
int tmp = G[l][r];
ans[query[now].id] = tmp;
}
for ( int i = 1 ; i <= m ; i++ )
printf ( "%lld\n" , ans[i] );
}
return 0;
}
因为知道了自己是多么的菜,所以才要更加努力去追求那个永远也不可能实现的梦想

本文标题:20191106模拟赛

文章作者:KRrrrrrrrr

发布时间:2019年11月07日 - 09:11

最后更新:2019年11月07日 - 10:11

原始链接:http://krrrr.xyz/2019/11/07/20191106模拟赛/

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。