| Solved | A | B | C | D | E | F | G | H | I | J |
|---|---|---|---|---|---|---|---|---|---|---|
| 6/10 | . | 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
B
题目描述
给一个$01$串，分别求出$01$个数相同的最长子序列和最长连续子序列的长度。
解题思路
最长子序列直接$min(num_0,num_1)$，最长连续子序列转化成$\pm 1$，求前缀和记录即可。
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
typedef long long ll;
using namespace std;
int n,pos[N<<1],t[N],ans;
char a[N];
int main(){
int i,offset=N;
int n1=0,n2=0;
scanf("%d",&n);
scanf("%s",a+1);
for(i=1;i<=n;i++){
if(a[i]=='0')t[i]=-1,n1++;
else t[i]=1,n2++;
}
int s=offset;
for(i=0;i<N<<1;i++)pos[i]=-1;
pos[s]=0;
for(i=1;i<=n;i++){
s+=t[i];
if(pos[s]==-1)pos[s]=i;
else ans=max(ans,i-pos[s]);
}
printf("%d %d",ans,min(n1,n2)*2);
return 0;
}
C
题目描述
解题思路
AC代码
2
D
题目描述
问有多少对$(i,j)$满足$A(i^j)%p=0$，其中$1\leq i\leq n,1\leq j\leq m;p,n,m\leq 10^9$，$p$为素数，$A(x)=111…1$，共$x$个$1$。
解题思路
等价变形为：$10^{i^j}%9p=1$
先求$10^n%9p$的循环节$d$。显然有$n=2,n=5$时该式子不可能为$1$；其他时候可枚举$\phi(9p)$的因子。（提前推出了$p=3$的结论：循环节为$3$，所以也可以特判$3$然后枚举$\phi(p)$的因子）
$O(\log p\log\log p )$暴力求出$d$后，考虑有多少对$(i,j)$满足$d|i^j$。
对于每一个$j$，对$d$质因数分解成$p_1^{k_1}p_2^{k_2}…p_t^{k_t}$后，满足条件的$i$必然为$g=p_1^{\lceil \frac{k_1}j\rceil}p_2^{\lceil \frac{k_2}j\rceil}…p_t^{\lceil \frac{k_t}j\rceil}$的整数倍（否则凑不成$d$的倍数），故这个$j$对答案的贡献为$\frac ng$。显然，在$j\geq max(k_p)$的时候贡献是相同的，于是枚举$j$到$min(30,m)$进行计算即可（因为显然$max(k_p)\leq 30$）。
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;
using namespace std;
ll mod,n,m,ans;
ll qp(ll a,int p){
ll ans=1;
for(;p;p>>=1,a=a*a%mod)if(p&1)ans=ans*a%mod;
return ans;
}
ll solve(){
int i,j,d=mod+1,x=mod-1;
for(i=1;i*i<=x;i++){
if(x%i==0){
if(qp(10,i)==1){d=i;break;}
if(i*i!=x&&qp(10,x/i)==1)d=x/i;
}
}
if(d>mod)return 0;
int p[110]={0},k[110]={0},tot=0;
for(i=2;i*i<=d;i++){
if(d%i==0){
p[++tot]=i;k[tot]=0;
while(!(d%i))d/=i,++k[tot];
}
}
if(d!=1)p[++tot]=d,k[tot]=1;
ll ret=0;
for(j=1;j<=m;j++){
ll g=1;
for(i=1;i<=tot;i++)g*=qp(p[i],(k[i]+j-1)/j);
ret+=n/g;
if(j>=30)ret+=n/g*(m-j),j=m+1;
}
return ret;
}
int main(){
int i,t;
scanf("%d",&t);
while(t--){
scanf("%lld%lld%lld",&mod,&n,&m);
if(mod==3)ans=n/3*m;
else if(mod==2||mod==5)ans=0;
else ans=solve();
printf("%lld\n",ans);
}
return 0;
}
E
题目描述
解题思路
AC代码
2
F
题目描述
给一个矩阵，求最大矩形的面积，保证矩形内元素的最大最小值之差小于给定值。
解题思路
枚举上下界，再枚举矩形右端点，左端点显然可以保证单调性，于是到此时复杂度为$O(n^3)$。考虑左端点每次移动代价为$O(1)$，用两个单调栈分别保存最小值和最大值即可。
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
typedef long long ll;
using namespace std;
int n,m;
int a[N][N],mn[N],mx[N];
int qmn[N],hmn,tmn,qmx[N],hmx,tmx;
int main(){
int T,i,j,k;
scanf("%d",&T);
while(T--){
int ans=0;
scanf("%d%d",&n,&m);
for(i=0;i<n;i++)for(j=0;j<n;j++)scanf("%d",&a[i][j]);
for(i=0;i<n;i++){
for(j=0;j<n;j++)mn[j]=mx[j]=a[i][j];
for(j=i;j<n;j++){
for(k=0;k<n;k++)mn[k]=min(mn[k],a[j][k]),mx[k]=max(mx[k],a[j][k]);
hmn=hmx=1;tmn=tmx=0;
if(n*(j-i+1)<ans)continue;
int l=0,r;
for(r=0;r<n;r++){
while(hmn<=tmn&&mn[qmn[tmn]]>=mn[r])tmn--;
qmn[++tmn]=r;
while(hmx<=tmx&&mx[qmx[tmx]]<=mx[r])tmx--;
qmx[++tmx]=r;
while(l<=r&&mx[qmx[hmx]]>m+mn[qmn[hmn]]){
l++;
if(hmn<=tmn&&qmn[hmn]<l)hmn++;
if(hmx<=tmx&&qmx[hmx]<l)hmx++;
}
if((j-i+1)*(n-l+1)<ans)break;
if(ans<(j-i+1)*(r-l+1))ans=(j-i+1)*(r-l+1);
}
}
}
printf("%d\n",ans);
}
return 0;
}
G
题目描述
有一个游戏，规则是给定多堆石子，石子总个数为偶数，每次从不同的两堆石子中各取一个，能够取完则获得胜利，有残余则失败。
给定一个数列，求该数列中有多少种能够取胜的连续子列。如果连续子列总个数为奇数，则弃掉石子个数最小的那一堆中的一个石子。
解题思路
题意很容易转化为：给定一个数列，求出有多少个区间满足区间中的最大值比区间中的其他所有值的和严格大。
分治，每次$rmq$找到最大值，跑出这个最大值对应的贡献，再分别处理两边不包含这个最大值的贡献。计算最大值对应的贡献时，考虑一端枚举另一端二分，为保证复杂度，在数少的一端枚举，另一端二分。
复杂度$O(n\log^2 n)$。
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
typedef long long ll;
using namespace std;
int a[N],n;
ll s[N],ans;
int rmq[20][N],pos[20][N],lg[N];
void init(){
int i,j;
for(i=1;i<=n;i++)rmq[0][i]=a[i],pos[0][i]=i;
for(j=1;(1<<j)<=n;j++){
for(i=1;i+(1<<j-1)-1<=n;i++){
if(rmq[j-1][i]<rmq[j-1][i+(1<<(j-1))]){
pos[j][i]=pos[j-1][i+(1<<(j-1))];
rmq[j][i]=rmq[j-1][i+(1<<(j-1))];
}else{
pos[j][i]=pos[j-1][i];
rmq[j][i]=rmq[j-1][i];
}
}
}
}
int query(int l,int r){
int f=lg[r-l+1];
if(rmq[f][l]<rmq[f][r+1-(1<<f)])return pos[f][r+1-(1<<f)];
else return pos[f][l];
}
void dc(int l,int r,int pos){
int i;
if(l>r)return;
if((l+r)/2>pos)
for(i=pos;i>=l;i--){
ll now=s[pos-1]-s[i-1],remain=a[pos]-now;
if(remain<=0)break;
int rm=lower_bound(s+pos,s+r+1,remain+s[pos])-s-1;
ans+=rm-pos+1;
}
else
for(i=pos;i<=r;i++){
ll now=s[i]-s[pos],remain=a[pos]-now;
if(remain<=0)break;
int lm=upper_bound(s+l-1,s+pos,-remain+s[pos-1])-s+1;
ans+=pos-lm+1;
}
ans--;
int tmp=pos-1;
if(a[pos]==a[tmp])while(tmp&&a[tmp-1]==a[pos])tmp--;//卡常
dc(l,tmp,query(l,tmp));
tmp=pos+1;
if(a[tmp]==a[pos])while(tmp<n&&a[tmp+1]==a[pos])tmp++;//卡常
dc(tmp,r,query(tmp,r));
}
int main(){
int i,t;
scanf("%d",&t);
for(i=2;i<N;i++)lg[i]=lg[i-1]+(1<<(lg[i-1]+1)==i);
while(t--){
scanf("%d",&n);
int mx=0,pos=0;
ans=0;
for(i=1;i<=n;i++){
scanf("%d",&a[i]);
s[i]=s[i-1]+a[i];
}
init();
dc(1,n,query(1,n));
printf("%lld\n",1LL*n*(n-1)/2-ans);
}
return 0;
}
H
题目描述
给平面上$n$个不同的点，求一条不经过任何这些点的直线把他们分割成点数完全相等的两部分。输出这条直线经过的两个不同整数点。
解题思路
把所有点按照先$x$后$y$的方法排好序，找到中间两个点，画一条斜率超级大的倾斜直线即可。
AC代码
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
using namespace std;
struct P{
int x,y;
bool operator<(const P&a)const{return x<a.x||(x==a.x&&y<a.y);}
}p[N];
int main(){
int t,n,i;
scanf("%d",&t);
while(t--){
scanf("%d",&n);
for(i=0;i<n;i++)scanf("%d%d",&p[i].x,&p[i].y);
sort(p,p+n);
int mid=p[n/2-1].x;
int temp=999000000;
printf("%d %d %d %d\n",mid-1,temp+1+p[n/2-1].y,mid+1,-temp+p[n/2-1].y);
}
return 0;
}
I
题目描述
解题思路
AC代码
2
J
题目描述
要求实现一个队列，有两种操作，一种是找到某个字符串，如果找到则把它移到最后面，没找到就加进去，超过容量则删掉第一个；另一种是找到它前驱后继。
解题思路
$trie$存一下位置，链表维护一下就行了…
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
typedef long long ll;
using namespace std;
int tr[10][N],tot,ed[N];
int l[N],r[N],dat[N],s,t,sz;
int ins(char s[]){
int i,now=0;
for(i=0;s[i];i++){
int x=s[i]-'0';
if(!tr[x][now])tr[x][now]=++tot;
now=tr[x][now];
}
ed[now]=1;
return now;
}
int find(char s[]){
int i,now=0;
for(i=0;s[i];i++){
int x=s[i]-'0';
now=tr[x][now];
if(!now)return 0;
}
if(!ed[now])return 0;
return now;
}
void del(int x){
sz--;
l[r[x]]=l[x];
r[l[x]]=r[x];
if(x==s)s=r[x];
if(x==t)t=l[x];
l[x]=r[x]=dat[x]=0;
}
void add(int x,int v){
sz++;
dat[x]=v;
if(sz==1)s=t=x;
else r[t]=x,l[x]=t,t=x;
}
char a[N];
int main(){
int i,j,t,n,m,opt,v;
scanf("%d",&t);
while(t--){
scanf("%d%d",&n,&m);
for(i=0;i<n;i++){
scanf("%d%s%d",&opt,a,&v);
int p=find(a);
if(!opt){
if(p){
v=dat[p];
del(p);//node
add(p,v);
}else{
if(sz==m)ed[s]=0,del(s);
add(ins(a),v);
}
printf("%d\n",v);
}else{
if(!p)puts("Invalid");
else{
if(v==-1)p=l[p];
else if(v==1)p=r[p];
if(!p)puts("Invalid");
else printf("%d\n",dat[p]);
}
}
}
for(i=0;i<=tot;i++){
for(j=0;j<10;j++)tr[j][i]=0;
ed[i]=0;
}
while(s)del(s);
tot=sz=0;
}
return 0;
}