| 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 for passing during the contest
- Ø for passing after the contest
- ! for attempted but failed
- · for having not attempted yet
A
题目描述
给一个表，求打表结果。
解题思路
签到打比赛，一个愿打一个愿挨。
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
int x[10][10];
char ch[4]={'I','E'};
int main(){
int i,n;
x[0][5]=x[1][1]=x[1][3]=x[1][5]=x[2][1]=x[2][3]=x[2][5]=1;
x[3][1]=x[3][3]=x[3][5]=x[4][1]=x[5][3]=1;
scanf("%d",&n);
for(i=0;i<n;i++){
char a[10]={0};
scanf("%s",a);
int p=a[0]-'0',q=2;
if(!p){
printf("X");
continue;
}
if(a[1]){
if(a[2]){
if(a[2]=='-')q=0;
else q=4;
}else{
if(a[1]=='-')q=1;
else q=3;
}
}
printf("%c",ch[x[q][p]]);
}
return 0;
}
B
题目描述
给定$m$个字符串$a[i] (1 \leq i \leq m)$，求一个长度为$n$的字符串$A$，使得$a[i] (i\leq i \leq m)$均不为$A$的连续子串。
解题思路
$AC$自动机套$DP$。用$dep[i]$表示$i$这个节点最多能延伸到多么深。沿着$trie$图走，记忆化搜索，只要遇到字符串标记则记$dep[i]=0$。如果成环则必定可行（这一个环上都没有子串），所以用$vis[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
55
56
57
58
59
60
61
62
63
64
65
66
using namespace std;
int t[N][P],END[N],fail[N],tot,n,m;
char a[N];
void insert(){
int i,now=0;
for(i=0;a[i];i++){
int c=a[i]-'a';
if(!t[now][c])t[now][c]=++tot;
now=t[now][c];
}
END[now]++;
}
queue<int>Q;
void build(){
int i;
for(i=0;i<P;i++)if(t[0][i])Q.push(t[0][i]);
while(!Q.empty()){
int p=Q.front();Q.pop();
for(i=0;i<P;i++){
if(!t[p][i])t[p][i]=t[fail[p]][i];
else{
fail[t[p][i]]=t[fail[p]][i];
if(END[fail[t[p][i]]])END[t[p][i]]=1;
Q.push(t[p][i]);
}
}
}
}
int vis[N],dep[N];
int dfs(int d,int now){
if(vis[now])return dep[now]=1e6;
if(~dep[now])return dep[now];
if(END[now])return dep[now]=0;
if(!d)return dep[now]=1;
vis[now]=1;
dep[now]=0;
int i;
for(i=0;i<P;i++)dep[now]=max(dep[now],dfs(d-1,t[now][i])+1);
vis[now]=0;
return dep[now];
}
void print(int d){
int i,now=0;
while(d){
for(i=0;i<P;i++){
if(d<=dep[t[now][i]]){
printf("%c",i+'a');d--;
now=t[now][i];
break;
}
}
}
}
int main(){
int i;
scanf("%d%d",&n,&m);
for(i=0;i<m;i++)scanf("%s",a),insert();
build();
memset(dep,-1,sizeof(dep));
dfs(n,0);
print(n);
return 0;
}
C
题目描述
路上有$n$个怪兽，每个怪兽有攻击力$x[i]$血量$d[i]$，你的攻击力是$k$。每遇到一个怪兽，你先手攻击，之后轮流攻击，当怪兽的血量$\leq 0$的时候该怪兽死亡。
有$c$个道具，该道具可以在瞬间吃下而且使本回合临时增加$k$点攻击力，该道具可以在任意时候吃，且可以连续吃。问你最少消耗多少血量。
解题思路
一个道具相当于多打该怪兽一个回合，贪心地攻击攻击力最高的怪兽即可，记得开$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
using namespace std;
struct Monster{
int d,x;
bool operator<(const Monster&a)const{return x>a.x;}
}a[100010];
int tot;
int main(){
int i,n,k,c,d,x;
scanf("%d%d%d",&n,&k,&c);
for(i=0;i<n;i++){
scanf("%d%d",&d,&x);
if(d>k)a[tot++]=(Monster){d/k+(d%k!=0)-1,x};
}
sort(a,a+tot);
int left=0;
for(i=0;i<c;i++){
a[left].d--;
if(a[left].d<=0)left++;
if(left>=tot)break;
}
long long ans=0;
for(i=0;i<tot;i++)ans+=a[i].d*1LL*a[i].x;
printf("%lld",ans);
return 0;
}
D
题目描述
在宽为$w$的走廊中有$n$个圆形障碍物，求能通过该走廊的最大圆的半径。
解题思路
显然，最大的圆能够使得整个走廊两端连接。故以两点之间距离减两圆半径作为边权，用$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
using namespace std;
struct Circle{
int x,y,r;
double dis;
bool operator<(const Circle&a)const{return dis<a.dis;}
}a[N];
int x[N],n,w;
double dist(int X1,int Y1,int X2,int Y2){
return sqrt((X1-X2)*(X1-X2)+(Y1-Y2)*(Y1-Y2));
}
void upd(int now,int last){
double d;
if(a[last].y+a[last].r>=w&&a[now].y+a[now].r>=w)a[now].dis=0;
else if(a[now].dis>(d=dist(a[now].x,a[now].y,a[last].x,a[last].y)-a[now].r-a[last].r))a[now].dis=d;
}
int main(){
int i,j,t;
scanf("%d",&t);
while(t--){
scanf("%d%d",&w,&n);
for(i=0;i<n;i++)scanf("%d%d%d",&a[i].x,&a[i].y,&a[i].r),a[i].dis=a[i].y-a[i].r,x[i]=a[i].x;
sort(x,x+n);
int mx=unique(x,x+n)-x;
for(i=0;i<mx;i++)a[n++]=(Circle){x[i],w,0,w*1.0};
sort(a,a+n);
double ans=max(a[0].dis,0.0);
for(j=1;j<n;j++)upd(j,0);
sort(a,a+n);
for(i=1;i<n;i++){
//for(j=0;j<n;j++)printf("%d %d %d %.4f\n",a[j].x,a[j].y,a[j].r,a[j].dis);
sort(a+i,a+n);
ans=max(ans,a[i].dis);
for(j=i+1;j<n;j++)upd(j,i);
}
printf("%.10f\n",ans/2);
}
return 0;
}
E
题目描述
给一个全排列，求多少个栈才能把全排列变成有序的升序序列。
解题思路
两个栈必定能完成全部操作：想取出任意一个元素均有可行方案。故只需要判断能否用一个栈解决。
AC代码
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
int st[100010],top,t,n,now,a[100010];
int main(){
int i;
scanf("%d",&t);
while(t--){
top=0;now=1;
scanf("%d",&n);
for(i=0;i<n;i++)scanf("%d",&a[i]);
for(i=0;i<n;i++){
st[top++]=a[i];
while(top&&st[top-1]==now)top--,now++;
}
if(now!=n+1)printf("2\n");
else printf("1\n");
}
return 0;
}
F
题目描述
给一个$n\times m$的网格图，求本质不同的四个顶点都在格点上构成的正方形个数。
解题思路
先考虑边长为$i\times i$的正方形，以它的四个边上的点为顶点的正方形个数为$i$。
故答案即为$\sum_{i=1}^{m}(n-i+1)\times (m-i+1)\times i$。
AC代码
2
3
4
5
6
7
8
9
10
11
12
13
int t,n,m;
int main(){
int i;
scanf("%d",&t);
while(t--){
long long ans=0;
scanf("%d%d",&n,&m);
for(i=1;i<=m;i++)ans+=1LL*(n-i+1)*(m-i+1)*i;
printf("%lld\n",ans);
}
return 0;
}
G
题目描述
有两个区域，$A$区域的人全都要去$B$区域。$A$区域的人分别位于$c[i]$上，$B$区域只能到达$d[i]$。现在给定$n$条特殊道路，$A$区域$[a,b]$范围和$B$区域$[c,d]$范围连通，需要的耗时为$w$，问$A$区的人同时出发，最后到达的人所需时间是多少。
解题思路
新建$s,t$，连$t->B,B->A,A->s$的边，跑最短路，找到$t$到$c[i]$路径最长的即为答案。
三种边分别如何连呢？
$t->B:$$t$到所有$d[i]$
$A->s:$所有$c[i]$到$s$（其实完全可以不连）
$B->A:$线段树维护，添加特殊点保证连边数量线性。其中令左线段树($B$)上的点为其编号本身，令右线段树($A$)上的点为其编号本身$+2n$，叶节点序号用$lnum,rnum$表示。
线段树维护过程：将线段树上每一个节点视为点，则该点代表所有以它为根的子树，故初始化的时候左线段树连接从儿子到爸爸权值为$0$的边，右线段树连接从爸爸到儿子权值为$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
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
using namespace std;
struct Edge{
int e,n,l;
}e[(N)<<2];
int hd[N],cnt;
void add(int a,int b,int l){
e[++cnt].e=b;e[cnt].n=hd[a];e[cnt].l=l;hd[a]=cnt;
//printf("%d %d %d %d\n",a,b,l,cnt);
}
struct Tree{
int l,r;
}t1[N],t2[N];
int t,s,n,m,p,q;
int c[N],d[N];
int ltnum(int x){return x;}//lefttreenum
int rtnum(int x){return x+2*n;}//righttreenum
int lnum[N],rnum[N];
int tot;
void build(struct Tree *a,int l,int r,int p,int dir){//dir:从根到叶-1；从叶到根-0
a[p].l=l;
a[p].r=r;
if(l==r){
if(!dir)lnum[l]=p;
else rnum[l]=p+2*n;
return;
}
build(a,l,(l+r)>>1,p<<1,dir);
build(a,((l+r)>>1)+1,r,p<<1|1,dir);
if(a[p<<1].l){
if(!dir)add(ltnum(p<<1),ltnum(p),0);
else add(rtnum(p),rtnum(p<<1),0);
}
if(a[p<<1|1].l){
if(!dir)add(ltnum(p<<1|1),ltnum(p),0);
else add(rtnum(p),rtnum(p<<1|1),0);
}
}
void adde(struct Tree *a,int l,int r,int midpoint,int p,int dir,int w,int offset){
//offset:点的id
int L=a[p].l,R=a[p].r;
if(l<=L&&R<=r){
if(!dir)add(p+offset,midpoint,w);
else add(midpoint,p+offset,w);
return;
}
if(a[p<<1].r>=l)adde(a,l,r,midpoint,p<<1,dir,w,offset);
if(a[p<<1|1].l<=r)adde(a,l,r,midpoint,p<<1|1,dir,w,offset);
}
struct Node{
int x;
long long w;
bool operator<(const Node&a)const{return w>a.w;}
};
priority_queue<Node>Q;
int vis[N];
long long dis[N];
void dijkstra(){
int i;
Q.push((Node){t,0});
while(!Q.empty()){
int top=Q.top().x;
Q.pop();
if(vis[top])continue;
vis[top]=1;
for(i=hd[top];i;i=e[i].n){
int q=e[i].e;
if(dis[q]>dis[top]+0LL+e[i].l){
dis[q]=dis[top]+0LL+e[i].l;
Q.push((Node){q,dis[q]});
}
}
}
}
int main(){
int i,a,b,C,D,w;
scanf("%d%d%d%d",&n,&m,&p,&q);
while(n&(n-1))n++;
t=4*n+1;
tot=s=4*n+2;
build(t1,1,n,1,0);
build(t2,1,n,1,1);
for(i=0;i<m;i++){
scanf("%d%d%d%d%d",&a,&b,&C,&D,&w);
adde(t2,a,b,++tot,1,0,w,2*n);
adde(t1,C,D,tot,1,1,0,0);
adde(t2,C,D,++tot,1,0,w,0);
adde(t1,a,b,tot,1,1,0,2*n);
}
for(i=0;i<p;i++)scanf("%d",&c[i]);
for(i=0;i<q;i++)scanf("%d",&d[i]);
sort(d,d+q);q=unique(d,d+q)-d;for(i=0;i<q;i++)add(t,lnum[d[i]],0);
sort(c,c+p);p=unique(c,c+p)-c;for(i=0;i<p;i++)add(rnum[c[i]],s,0);
memset(dis,0x3f,sizeof(dis));
dis[t]=0;
dijkstra();
long long ans=0;
for(i=0;i<p;i++)ans=max(ans,dis[rnum[c[i]]]);
if(ans<1e16)printf("%I64d",ans);
else printf("boring game");
return 0;
}
H
题目描述
找出$\sqrt {ax}+b=x$的解，保证解存在且为整数。
解题思路
初中数学题。
AC代码
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
int t,a,b;
int main(){
int i;
scanf("%d",&t);
while(t--){
scanf("%d%d",&a,&b);
int A[6]={0},ans=0;
int x1=round(1.0*(2*b+a+sqrt(a*a+4*a*b))/2),x2=round(1.0*(2*b+a-sqrt(a*a+4*a*b))/2);
if(fabs(sqrt(a*x1)+b-x1)<1e-5)A[ans++]=x1;
if(fabs(sqrt(a*x2)+b-x2)<1e-5&&x2!=x1)A[ans++]=x2;
printf("%d\n",ans);
for(i=0;i<ans;i++)printf("%d ",A[i]);
puts("");
}
return 0;
}
I
题目描述
给一个$n\times n$的棋盘，每个格子可以填$[1,k]$的正整数，定义棋盘中某个点为$bi$点当且仅当其为该行该列严格最大值，设$B[i]$为棋盘中恰好存在$i$个$bi$点的方案数，求$\sum_{i=0}^{n^2}i^2B[i]$。
解题思路
由于任意交换两行两列不影响$bi$点状况，故可以先讨论$bi$点在对角线且$bi$点非严格单调递增的情况。
设$dp[i][j]$表示已经确定了前$i$个$bi$点，且其中最大的$bi$点对应数值不超过$j$的方案总数。
那么有：$dp[i][j]=\sum_{k=0}^{j-1}dp[k][j-1]\times \frac{(j-1)^{(i-k)(2n-i-k-1)}}{(i-k)!}$。
递推的过程即为填$bi$点值为$j$的状态。其中$dp[k][j-1]$表示前$k$行列不超过$j-1$，$j-1$的次方表示非前$k$行控制的、$k+1$到$i$行列的，由新增加进来的值为$bi$点控制的节点。最后除以$(i-k)!$为了除重。
设至少有$i$个$bi$点的方案数位$b[i]$，则有$b[i]={A_{n}^{i}}^2dp[i][k]\times k^{(n-i)^2}$，即从$n$行$n$列分别选出$i$行$i$列，且最大不超过$k$，剩下未支配的部分从$[1,k]$任取的方案个数，这段可能有重复，不过无关紧要，请看下一步。
再设$f[i]$为恰好有$i$个$bi$点的方案总数，则可以进行容斥：$f[i]=b[i]+\sum_{i<j}(-1)^{(j-i)}b[j]\times C_{j}^{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
typedef long long ll;
int f[N],dp[N][N],b[N];
ll w=998244353,jc[N]={1};
ll qpow(ll x,ll p){
int i;
ll ans=1;
for(i=p;i;i>>=1,x=x*x%w)if(i&1)ans=ans*x%w;
return ans;
}
ll inv(ll x){return qpow(x,w-2);}
int main(){
int i,j,k,t,n,K;
scanf("%d",&t);
for(i=1;i<N;i++)jc[i]=jc[i-1]*i%w;
while(t--){
scanf("%d%d",&n,&K);
memset(dp,0,sizeof(dp));
memset(b,0,sizeof(b));
memset(f,0,sizeof(f));
for(i=0;i<=n;i++)dp[0][i]=1;
for(i=1;i<=n;i++){
for(j=0;j<=K;j++){
for(k=0;k<=i;k++)
dp[i][j]+=dp[k][j-1]*qpow(j-1,(i-k)*(2*n-i-k-1))%w*inv(jc[i-k])%w;
}
}
for(i=1;i<=n;i++)
b[i]=jc[n]*inv(jc[n-i])%w*jc[n]*inv(jc[n-i])%w*dp[i][K]%w*qpow(K,(n-i)*(n-i))%w;
for(i=1;i<=n;i++){
f[i]=b[i];
int nowsign=-1;
for(j=i+1;j<=n;j++){
f[i]+=(nowsign)*b[j]*jc[j]%w*inv(jc[i])%w*inv(jc[j-i])%w;
f[i]%=w;
nowsign*=-1;
}
f[i]+=w;
f[i]%=w;
}
ll ans=0;
for(i=1;i<=n;i++)
(ans+=i*i*f[i])%=w;
printf("%lld\n",(ans%w+w)%w);
}
return 0;
}
J
题目描述
定义一个合法的算式是一个恰好长为$n$的字符串，其中只包含$0-9,+,-$，不允许运算符相邻或出现在首尾，允许前导零。合法的算式的计算结果即为对该字符串模拟十进制加减法运算的结果。
求所有合法算式计算结果的和，答案对$998244353$取模。
解题思路
由于$+$和$-$都可以出现，所以能出现加号的地方必能出现减号，只需要考虑算式最左端的数对应的结果即可。
可设：
$p[j]=10^i$
$f[i]=\frac{10^i}{2}(10^i+1)$，此即只含有$i$位数字的算式计算结果。
$g[i]$为长度为$i$、第一个字符为$+$或$-$的不同串总种数。
$ans$为长度为$n$的合法算式计算结果的和。则有
$g[2]=20,g[i]=2p[i-1]+\sum_{j=2}^{i-2}2p[i-j-1]g[j]$处理成前缀和：
$g[i]=2f[i-1]+10^{i-1}\sum_{j=2}^{i-2}2*10^{-j}g[j]$
$=2f[i-1]+p[i-1]h[i-2]$其中$h[i]=\sum_{j=2}^{i}2\times 10^{-j}g[j]$，同时处理即可。
$ans=f[n]+\sum_{j=2}^{n-1}f[n-j]g[j]$
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
typedef long long ll;
int t,a,b;
ll inv=299473306;
ll w=998244353;
ll p[N]={1};
ll f[N]={1},g[N],h[N];
ll invf[N]={1};
int main(){
int i,n;
scanf("%d",&t);
for(i=1;i<N;i++)p[i]=p[i-1]*10%w;
for(i=1;i<N;i++)
f[i]=(p[i]-1)*p[i-1]*5%w,invf[i]=invf[i-1]*inv%w;
g[2]=20;
while(t--){
ll ans=0;
scanf("%d",&n);
for(i=2;i<=n;i++){
g[i]=(2*p[i-1]+p[i-1]*h[i-2])%w;
h[i]=(h[i-1]+2*invf[i]*g[i])%w;
}
for(i=2;i<=n-1;i++)ans=(ans+f[n-i]*g[i])%w;
ans=(ans+f[n])%w;
//for(i=1;i<n;i++)printf("h:%I64d g:%I64d f:%I64d\n",h[i],g[i],f[i]);
printf("%I64d\n",ans);
}
return 0;
}
K
题目描述
给一个多项式，求其导数各指数的系数。
解题思路
签到。
AC代码
2
3
4
5
6
7
8
9
10
11
12
13
int main(){
int i,j,n,k,a[110]={0};
scanf("%d%d",&n,&k);
for(i=n;i>=0;i--)scanf("%d",&a[i]);
for(i=0;i<k;i++){
for(j=0;j<=n;j++)
a[j]=(a[j]*((j>i)?j-i:0))%2019;
}
for(i=0;i<k;i++)printf("0 ");
for(i=n;i>=k;i--)printf("%d ",a[i]%2019);
return 0;
}
L
题目描述
给定$n$个点，$m$条边权均为$1$的边，从节点$1$开始，等概率选择其后继或停留，最多停留时间 为$1$，问总时间期望。
解题思路
推出式子树形$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
typedef long long ll;
struct Edge{
int e,n;
}e[N];
int ind[N],oud[N],cnt,hd[N],n,m;
void add(int a,int b){
e[++cnt].e=b;e[cnt].n=hd[a];hd[a]=cnt;
ind[b]++;oud[a]++;
}
int w=998244353;
ll qpow(ll x,ll p){
int i;
ll ans=1;
for(i=p;i;i>>=1,x=x*x%w)if(i&1)ans=ans*x%w;
return ans;
}
ll inv(ll x){return qpow(x,w-2);}
ll dfs(int x){
if(!oud[x])return 2;
int i,q;
ll p=0;
for(i=hd[x];i;i=e[i].n){
q=e[i].e;
(p+=dfs(q))%=w;
}
return (1+(p+oud[x])*inv(oud[x]+1)%w+inv(oud[x]+1)*inv(oud[x])%w*(p+2*oud[x]))%w;
}
int main(){
int i,t,u,v;
scanf("%d",&t);
while(t--){
scanf("%d%d",&n,&m);
for(i=0;i<m;i++)scanf("%d%d",&u,&v),add(u,v);
printf("%lld\n",dfs(1));
}
return 0;
}