大概咕掉了，以后看摸着再回来做吧。
| Solved | A | B | C | D | E | F | G | H | I | J | K | L | M |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 6/13 | Ø | Ø | Ø | Ø | . | . | Ø | Ø | . | . | . | . | . |
- O for passing during the contest
- Ø for passing after the contest
- ! for attempted but failed
- · for having not attempted yet
A
题目描述
我们将五角星关于它的中心旋转$alpha$角度得到一个新五角星，再与原五角星重叠，得到一个新的平面图形，请问在新的平面图形中二维平面被分成了多少个区域？
解题思路
观察易得，情况就两种。
AC代码
2
3
4
5
6
7
8
9
10
int main(){
int n,t;
scanf("%d",&t);
while(t--){
scanf("%d",&n);
printf("%d\n",n%72?32:7);
}
return 0;
}
B
题目描述
给一个$01$串，求一个最短非空$01$串，使得其不是给定串的子串，求最短长度。
解题思路
答案不超过$23$（$2^{23}>4.5e6$），故从上界向下枚举即可。
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
char a[N];
int vis[N];
int main(){
int i,j,t;
scanf("%d",&t);
while(t--){
scanf("%s",a);
int ans,l=strlen(a),k=0,now=0;
while((1<<k)<=l)k++;
ans=k;
for(i=0;i<l;i++){
if(i<k)now=(now<<1)+a[i]-'0';
else now=((now&((1<<k-1)-1))<<1)+a[i]-'0';
if(i>=k-1)vis[now]=1;
}
for(i=k-1;i;i--){
int flag=0;
for(j=0;j<(1<<i);j++)
if(vis[j<<1]||vis[j<<1|1]||vis[j+(1<<i)]||vis[j])vis[j]=1;
else flag=1;
if(flag)ans=i;
else break;
}
printf("%d\n",ans);
memset(vis,0,sizeof(vis));
}
return 0;
}
C
题目描述
给定一个等腰梯形，每一行均匀分布一些点，问从这个等腰梯形中的点里面选三个构成正三角形的个数。
解题思路
极其麻烦的一道题，做了整整三个小时。（还不是因为菜）
把三角形分为头朝上、头朝下两部分解决。假设头朝下的、底边在宽度为$i$的一层中的正三角形个数为$a_i$，头朝上的、顶点在宽度为$i$的一层中的正三角形个数为$b_i$，那么答案便是$\sum_{i=n}^{m}{a_i+b_i}$。
先求$a_i$。
底边在宽度为$i$的一层中的正三角形，其边长的取值范围为$l∈[1,i-n]$，记$h_i=i-n$，$H=m-n$，于是相当于考虑在$i+1$个点中选择距离$d\leq h_i$的种数，也就是$a_i=h_i(i+1)-\frac{h_i(h_i+1)}2$。
解释一下上面这个式子。在$i+1$个点中任选一个点$p$，在不考虑超出范围的情况下，距离$d\leq h_i$的点有$p+1,p+2,…,p+h_i$，共有$h_i$个。但显然这样多算了选了并不能选的点的情况。这种右端的点超出范围情况共有$(1+2+3+…+h_i)$种情况，即$\frac{h_i(h_i+1)}2$。
于是
$\sum_{i=n}^{m} a_i$
$=\sum_{i=n}^{m}{(i+1)h_i-\frac{h_i(h_i+1)}2}$
$=\sum_{i=0}^{H}{\frac{(i+2n+1)i}2}$
$=\sum_{i=0}^{H}{\frac{i^2}{2}+\frac{(2n+1)i}2}$
$=\frac{H(H+1)(2H+1)}{12}+\frac{(2n+1)(H+1)H}{4}$
$=\frac{n(H+1)H}2+\frac{H(H+1)(H+2)}6$
再来计算$b_i$。
对于顶点在宽度为$i$的一层中的三角形，其边长为$l=min(i-n,\left\lfloor\frac i2\right\rfloor)$。枚举底边宽度$j$，则正三角形边长为$i-j$，个数为$2j-i+1$。
故$b_i=\sum_{j=n}^{i-1}2j-i+1,k\leq2n;\sum_{j=\left\lfloor\frac{k+1}2\right\rfloor}^{i-1}2j-i+1,k>2n$。
分段求和，有
$1.m\leq2n$
$\sum_{i=n}^{m}b_i$
$=\sum_{i=n}^{m}\sum_{j=n}^{i-1}2j-i+1$
$=\sum_{i=n}^{m}(1-i)(i-1-n+1)+2\frac{(n+i-1)(i-n)}{2}$
$=\sum_{i=n}^{m}n(i-n)$
$=\frac{n(1+H)H}2$
$2.m>2n$
$\sum_{i=n}^{m}b_i$
$=\sum_{i=n}^{2n}b_i+\sum_{i=2n+1}^{m}b_i$
$=\frac{n(1+2n-n)(2n-n)}2+\sum_{i=2n+1}^{m}b_i$
$=\frac{n^2(1+n)}2+\sum_{i=2n+1}^{m}\sum_{j=\left\lfloor\frac{k+1}2\right\rfloor}^{i-1}2j-i+1$
$=\frac{n^2(1+n)}2+\sum_{i=2n+1}^{m}(1-i)(i-\left\lfloor\frac{i+1}2\right\rfloor)+(\left\lfloor\frac{i+1}2\right\rfloor+i-1)(i-\left\lfloor\frac{i+1}2\right\rfloor)$
$=\frac{n^2(1+n)}2+\sum_{i=2n+1}^{m}\left\lfloor\frac{i+1}2\right\rfloor\left\lceil\frac{i+1}2\right\rceil$
$=\frac{n^2(1+n)}2+\sum_{i=2n+1}^{m}\frac{i^2}4-\frac14(当i为奇数)$
$=\frac{n^2(1+n)}2+\frac14(\frac{m(m+1)(2m+1)}6-\frac{2n(2n+1)(4n+1)}6)-\frac14(\left\lfloor\frac m2\right\rfloor-n)$
然后加起来就行了。
AC代码
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
long long n,m,w=1e9+7;
long long ans;
int main(){
int t;
scanf("%d",&t);
while(t--){
ans=0;
scanf("%lld%lld",&m,&n);
long long H=m-n;
ans=(n*H*(H+1)/2+(H+2)*(H+1)*H/6)%w;
if(m<=2*n)ans=(ans+(n*H*(H+1)/2)%w)%w;
else ans=(ans+n*n*(n+1)/2+(((m*(m+1)*(2*m+1)-(2*n)*(2*n+1)*(4*n+1))/6+n-m/2)/4)%w)%w;
printf("%lld\n",ans%w);
}
return 0;
}
D
题目描述
从几堆牌中随机等概率取牌，一堆中取一张牌则所有的牌被取走。除了第一堆，每一堆牌的个数都是从一个闭区间中等概率选取的。当第一堆被取走时，游戏结束。问游戏结束时，取走的牌数期望值。
解题思路
设$P(i,j)$表示第$i$堆牌有$j$个，这堆牌其中某一张牌在第一堆牌某一张牌之前被取走的概率。于是有$P(i,j)=\frac{j}{a_1+j}$。
$ans=\sum_{i=2}^{n}\frac1{up[i]-low[i]+1}\sum_{j=low[i]}^{up[i]}\frac{j^2}{a_1+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
32
33
typedef long long ll;
int u[N],l[N],w=998244353;
ll a[N*10];
ll pw(ll a,ll p){
ll x=1;
for(;p;p>>=1,a=a*a%w)if(p&1)x=x*a%w;
return x;
}
int inv[N*20];
ll invf(int x){
if(inv[x])return inv[x];
return inv[x]=pw(x,w-2);
}
int main(){
int i,t,n,a1;
scanf("%d",&t);
while(t--){
scanf("%d%d",&n,&a1);
int max=0;
ll ans=a1;
for(i=1;i<n;i++){
scanf("%d%d",&l[i],&u[i]);
if(u[i]>max)max=u[i];
}
for(i=1;i<=max;i++)a[i]=1LL*i*i%w*invf(a1+i)%w;
for(i=1;i<=max;i++)a[i]=(a[i]+a[i-1])%w;
for(i=1;i<n;i++)ans=(ans+(invf(u[i]-l[i]+1)*(a[u[i]]-a[l[i]-1]+w)%w)%w)%w;
printf("%lld\n",(ans+w)%w);
}
return 0;
}
E
题目描述
解题思路
AC代码
F
题目描述
解题思路
AC代码
G
题目描述
给定一个一元二次方程，如果有无限小数实数解则保留到$1e6$位，如果有有限小数实数解则保留所有小数，如果无解则输出无解。
按照以下规则输出：输出$0-9$在解中出现的频率百分比，保留到整数。
解题思路
先判断有解无解、有无有理解，如果解无理，则全部输出$10$。
如果有有理解，再分为有限小数、无限小数讨论。如果无限小数且$1e6+1$位$\geq5$，则需要找到循环节中对应的位置进行进位、增加等处理；否则直接处理循环节输出。
我没有AC，但还是要发题解。
没有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
int num[11],cir[2010],cnt,infinite;
//出现次数，余数是否出现，总数，不循环
int len,fir;
//循环节长度及初始出现位置
int cy[2010];
//循环节
int tail;
//第1e6+1位在循环节中的位置
void init(){
memset(num,0,sizeof(num));
memset(cir,0,sizeof(cir));
memset(cy,0,sizeof(cy));
fir=tail=infinite=cnt=len=0;
}
void solveinteger(int x){
if(!x)num[0]++,cnt++;
while(x)num[x%10]++,x/=10,cnt++;
}
void find(int k,int d){
int temp[11]={0},tot=0;
int i,j,r=k;
cir[r]=1;
for(i=1;i<=M;i++){
if(!r)break;
if(!infinite&&cir[r]&&i!=1){
infinite=1;
cy[++len]=r*10/d;
for(j=r*10%d;j!=r;j=j*10%d)cy[++len]=j*10/d;
fir=i-len;
int number=(M-i)/len;//后面循环节个数
for(j=r*10%d;;j=j*10%d){
temp[j*10/d]+=number;
if(j==r)break;
}
i+=number*len;
tot+=number*len;
tail=(M-i+2)%len;//M+1
}
temp[r*10/d]++;
tot++;
cir[r]=i;
r=r*10%d;
}
if(!infinite||cy[tail]<5){
for(i=0;i<10;i++)num[i]+=temp[i];
cnt+=tot;
}else{
if(!tail)tail=len;
int mx;
for(i=1;i<=len;i++){
mx=(tail-1-i+len)%len+1;
if(cy[mx]!=9)break;
}
r=k;
cir[r]=1;
int tmp=i,flag=0;
memset(cir,0,sizeof(cir));
for(i=1;i<=M-tmp;i++){
if(!r)break;
if(!flag&&cir[r]&&i!=1){
flag=1;
int number=(M-i-tmp)/len;//后面循环节个数
for(j=r*10%d;;j=j*10%d){
num[j*10/d]+=number;
if(j==r)break;
}
i+=number*len;
}
num[r*10/d]++;
cir[r]=i;
r=r*10%d;
}
num[(r*10/d+1)%10]++;
for(i=M-tmp+2;i<=M;i++)num[0]++;
cnt+=M;
}
}
void printresult(){
int i;
for(i=0;i<10;i++){
double tp=num[i]*100.0/cnt;
printf("%d ",tp-(int)tp<0.5-1e-10?(int)tp:(int)tp+1);
}
printf("\n");
}
void print(int k,int d){
if(k<0)k=-k;
if(d<0)d=-d;
init();
solveinteger(k/d);
find(k%d,d);
printresult();
}
int main(){
int a,b,c,T;
scanf("%d",&T);
while(T--){
scanf("%d%d%d",&a,&b,&c);
int delta=b*b-4*a*c;
if(delta<0)printf("NO JIE\n");
else if(round(sqrt(delta))*round(sqrt(delta))==delta){
if(a<0)print((-b+round(sqrt(delta))),2*a),print((-b-round(sqrt(delta))),2*a);
else print((-b-round(sqrt(delta))),2*a),print((-b+round(sqrt(delta))),2*a);
}else printf("10 10 10 10 10 10 10 10 10 10\n10 10 10 10 10 10 10 10 10 10\n");
}
return 0;
}
H
题目描述
给定一个$300*300$以内的数字矩阵，其中$’x’$表示这个点不能被选择，再给出$\leq 1000$组询问，每组询问要求输出在包含给定$(x,y)$的基础上的、不选$’x’$点的元素之和最大的子矩阵中元素之和。
解题思路
把子矩阵包含$(x,y)$这个条件转化成：在行数范围在$[up,down]$区间内、必选$k$这一列时，最大的子矩阵大小，并在$up\leq x\leq down$条件下取最大值。
$’x’$可设置成一个比较小的数，但不能太小，$-1e7$比较好，而$-1e8$就不太行了，否则可能会爆掉。
通过问题转化，可以$O(n^2m+q)$解决问题。
剧毒，卡常数（还不是因为我太菜了）
TLE代码
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
int inf=-1e7;
int read(){
char c=getchar();int f=1,num=0;
while(c>'9'||c<'0'){
if(c=='-')f=-1;
if(c=='x')return inf;
c=getchar();
}
while(c>='0'&&c<='9')num=(num<<3)+(num<<1)+c-'0',c=getchar();
return num*f;
}
int n,m,q,mt[N][N],sum[N][N];
int pre[N],suc[N],s[N],mx[N][N][N];
int p[N][N][N],f[N][N];
void init(){
int i,j,k;
for(i=1;i<=n;i++){
for(j=i;j<=n;j++){
pre[0]=suc[m+1]=0;
for(k=1;k<=m;k++)s[k]=sum[j][k]-sum[j][k-1]-(sum[i-1][k]-sum[i-1][k-1]);
//预处理减小常数
for(k=1;k<=m;k++)pre[k]=max(0,pre[k-1])+s[k];
for(k=m;k>=0;k--)suc[k]=max(0,suc[k+1])+s[k];
for(k=1;k<=m;k++)mx[i][j][k]=pre[k]+suc[k]-s[k];
//mx[i][j][k]:i为上界，j为下界，必须包含第k列在上下界范围内全部值的最大值
}
}
for(i=1;i<=n;i++){
for(k=1;k<=m;k++){
//p[i][j][k]:i为上界，j为下界的上界，必须包含第k列的最大值
//只是起到简化运算的作用
p[i][n+1][k]=inf;
for(j=n;j>=i;j--)
p[i][j][k]=max(p[i][j+1][k],mx[i][j][k]);
}
}
for(i=1;i<=n;i++)
for(j=1;j<=m;j++){
//f[i][j]=min{p[up][i][j]},up<=i
f[i][j]=p[1][i][j];
for(k=2;k<=i;k++)f[i][j]=max(f[i][j],p[k][i][j]);
}
}
int main(){
int i,j,t,x,y;
t=read();
while(t--){
n=read(),m=read();
for(i=1;i<=n;i++)for(j=1;j<=m;j++)
mt[i][j]=read(),sum[i][j]=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]+mt[i][j];
init();
q=read();
while(q--)x=read(),y=read(),printf("%d\n",f[x][y]);
}
return 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
int inf=-1e7;
int read(){
char c=getchar();int f=1,num=0;
while(c>'9'||c<'0'){
if(c=='-')f=-1;
if(c=='x')return inf;
c=getchar();
}
while(c>='0'&&c<='9')num=(num<<3)+(num<<1)+c-'0',c=getchar();
return num*f;
}
int n,m,q,mt[N][N],sum[N][N];
int pre[N],suc[N],mx[N][N];
int p[N][N][N],f[N][N],s[N];
void init(){
int i,j,k;
for(i=1;i<=n;i++){//合并到用一个i
for(j=i;j<=n;j++){
pre[0]=suc[m+1]=0;
for(k=1;k<=m;k++)s[k]=sum[j][k]-sum[j][k-1]-(sum[i-1][k]-sum[i-1][k-1]);
for(k=1;k<=m;k++)pre[k]=max(0,pre[k-1])+s[k];
for(k=m;k>=0;k--)suc[k]=max(0,suc[k+1])+s[k];
for(k=1;k<=m;k++)mx[j][k]=pre[k]+suc[k]-s[k];
//i为上界，j为下界，必须包含第k列的最大值
}
for(k=1;k<=m;k++)p[i][n][k]=mx[n][k];
for(j=n-1;j>=i;j--)for(k=1;k<=m;k++)p[i][j][k]=max(p[i][j+1][k],mx[j][k]);
for(j=1;j<=m;j++){
f[i][j]=p[1][i][j];
for(k=2;k<=i;k++)f[i][j]=max(f[i][j],p[k][i][j]);
}
}
}
int main(){
int i,j,t,x,y;
t=read();
while(t--){
n=read(),m=read();
for(i=1;i<=n;i++)for(j=1;j<=m;j++)
mt[i][j]=read(),sum[i][j]=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]+mt[i][j];
init();
q=read();
while(q--)x=read(),y=read(),printf("%d\n",f[x][y]);
}
return 0;
}
I
题目描述
解题思路
AC代码
2
J
题目描述
解题思路
AC代码
2
K
题目描述
解题思路
AC代码
2
L
题目描述
解题思路
AC代码
2
M
题目描述
解题思路
AC代码
2