SPOJ classical 第53版的一套题，题目来源是POI、ONTAK和PA
STC00 Hamsters
给定n个模板串，前后两个串可以共用前缀/后缀，问m个模板串相接的最短长度
Solution：预处理串i后面放串j的方案数，倍增
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <algorithm>
using namespace std;
int n,m,i,j,k;
unsigned long long hash[205][30005],power[100005];
char s[205][30005];
int len[205],add[205][205];
unsigned long long a[205][205],b[205][205],c[205][205],ans;
int main()
{
scanf("%d%d",&n,&m);
for(i=1;i<=n;++i)
{
scanf("%s",s[i]+1);
len[i]=strlen(s[i]+1);
for(j=1;j<=len[i];++j)
hash[i][j]=hash[i][j-1]*27+s[i][j]-'a';
}
if(m==1)
{
k=len[1];
for(i=1;i<=n;++i)if(len[i]<k)k=len[i];
printf("%d\n",k);
return 0;
}
power[0]=1;
for(i=1;i<=100000;++i)power[i]=power[i-1]*27;
for(i=1;i<=n;++i)
for(j=1;j<=n;++j)
{
if(i==j)k=len[i]-1;else k=min(len[i],len[j]);
for(;k;--k)
{
if(hash[i][len[i]]-hash[i][len[i]-k]*power[k]==hash[j][k])
break;
}
add[i][j]=len[j]-k;
}
m-=2;
for(i=1;i<=n;++i)
for(j=1;j<=n;++j)
b[i][j]=a[i][j]=add[i][j];
for(;m;m/=2)
{
if(m&1)
{
for(i=1;i<=n;++i)
for(j=1;j<=n;++j)
c[i][j]=1000000000000000000ll;
for(i=1;i<=n;++i)
for(j=1;j<=n;++j)
for(k=1;k<=n;++k)
if(b[i][k]+a[k][j]<c[i][j])
c[i][j]=b[i][k]+a[k][j];
for(i=1;i<=n;++i)
for(j=1;j<=n;++j)
b[i][j]=c[i][j];
}
for(i=1;i<=n;++i)
for(j=1;j<=n;++j)
c[i][j]=1000000000000000000ll;
for(i=1;i<=n;++i)
for(j=1;j<=n;++j)
for(k=1;k<=n;++k)
if(a[i][k]+a[k][j]<c[i][j])
c[i][j]=a[i][k]+a[k][j];
for(i=1;i<=n;++i)
for(j=1;j<=n;++j)
a[i][j]=c[i][j];
}
ans=1000000000000000000ll;
for(i=1;i<=n;++i)
for(j=1;j<=n;++j)
if(b[i][j]+len[i]<ans)
ans=b[i][j]+len[i];
printf("%llu\n",ans);
}
STC01 Fire Extinguishers
一棵树上放灭火器，树上每个节点代表一个房间，一个灭火器可以分配到与它距离不超过K的S个房间，问最少需要多少灭火器
Solution：贪心，把灭火器放在深度尽量深的节点上
#include <stdio.h>
#include <stdlib.h>
#include <algorithm>
using namespace std;
int n,S,K,i,j,k,u,v,ans,root;
int f[100005][25],g[100005][25];
int son[100005],next[200005],ed[200005],tot;
bool vis[100005];
int dfs(int x)
{
int i,j,k;
vis[x]=true;
for(i=son[x];i;i=next[i])
if(!vis[ed[i]])
{
dfs(ed[i]);
for(j=0;j<=K;++j)
{
f[x][j+1]+=f[ed[i]][j];
if(j)
{
g[x][j-1]+=g[ed[i]][j];
if(g[x][j-1]>n)g[x][j-1]=n;
}
}
}
++f[x][0];
j=f[x][K]/S+(f[x][K]%S!=0);
ans+=j;
g[x][K]=j*S-f[x][K];
f[x][K]=0;
k=0;
for(j=K;j>=0;--j)
{
if(f[x][j]<=g[x][j])g[x][j]-=f[x][j],f[x][j]=0;
else f[x][j]-=g[x][j],g[x][j]=0;
if(f[x][j]<=g[x][j+1])g[x][j+1]-=f[x][j],f[x][j]=0;
else f[x][j]-=g[x][j+1],g[x][j+1]=0;
}
g[x][0]=0;
}
int main()
{
scanf("%d%d%d",&n,&S,&K);
for(i=1;i<n;++i)
{
scanf("%d%d",&u,&v);
++tot;next[tot]=son[u];son[u]=tot;ed[tot]=v;
++tot;next[tot]=son[v];son[v]=tot;ed[tot]=u;
}
root=1;
dfs(root);
k=0;
for(j=K;j>=0;--j)
{
k+=g[root][j];if(k>n)k=n;
if(f[root][j]<=k)k-=f[root][j],f[root][j]=0;
else f[root][j]-=k,k=0;
}
k=0;
for(i=0;i<=K;++i)k+=f[root][i];
ans+=k/S+(k%S!=0);
printf("%d\n",ans);
}
STC02 Antisymmetry
定义一种反回文串为按中间点对称，且01相反如001->001100->001011，001011是一个反回文串，给出一个串，求这个串有多少子串是反回文串，只要子串位置不同就认为不同
Solution：二分+Hash
#include <stdio.h>
#include <stdlib.h>
#include <algorithm>
#define H 100000007
using namespace std;
int n,i,j,k,l,r,mid,aim;
char s[500005];
unsigned long long hash1[500005],hash2[500005],power[500005];
long long Hash1[500005],Hash2[500005],Power[500005];
long long ans;
int main()
{
scanf("%d",&n);
scanf("%s",s+1);
for(i=1;i<=n;++i)hash1[i]=hash1[i-1]*2+s[i]-'0',Hash1[i]=(Hash1[i-1]*2+s[i]-'0')%H;
for(i=n;i>=1;--i)hash2[i]=hash2[i+1]*2+'1'-s[i],Hash2[i]=(Hash2[i+1]*2+'1'-s[i])%H;
power[0]=Power[0]=1;
for(i=1;i<=n;++i)power[i]=power[i-1]*2,Power[i]=Power[i-1]*2%H;
for(i=1;i<n;++i)
{
l=1;r=min(i,n-i);aim=0;
while(l<=r)
{
mid=l+r>>1;
if(hash1[i]-hash1[i-mid]*power[mid]==hash2[i+1]-hash2[i+1+mid]*power[mid]
&&(Hash1[i]-Hash1[i-mid]*Power[mid]%H+H)%H==(Hash2[i+1]-Hash2[i+1+mid]*Power[mid]%H+H)%H)
aim=mid,l=mid+1;else r=mid-1;
}
ans+=aim;
}
printf("%lld\n",ans);
}
STC03 Gifts(hidden)
STC04 Difference
给定一个a~z的字符串，求一个子串，出现次数最多的字符和最少的字符的出现次数差值最大，求这个差值
Solution：枚举最多最少的字符，其中一个设为1，另一个设为-1，利用前缀和求解
#include <stdio.h>
#include <stdlib.h>
using namespace std;
int n,i,j,k,a,b,sum,Max,Min,tmp,ans,tot;
int son[27],next[1000005];
char s[1000005];
int main()
{
scanf("%d",&n);
scanf("%s",s+1);
for(i=1;i<=n;++i)s[i]-='a';
for(i=n;i>=1;--i)
next[i]=son[s[i]],son[s[i]]=i;
ans=0;
for(a=0;a<26;++a)
for(b=a+1;b<26;++b)
if(son[a]&&son[b])
{
tmp=-10000000;sum=0;
Max=-10000000;Min=10000000;
i=son[a];j=son[b];
tot=0;
if(i<=j)
{
while(i<j&&i)
{
++sum;++tot;
i=next[i];
}
}
else
{
while(j<i&&j)
{
--sum;++tot;
j=next[j];
}
}
if(tot-1>ans)ans=tot-1;
while(i||j)
{
if(tmp!=-10000000)
{
if(tmp<Min)Min=tmp;
if(tmp>Max)Max=tmp;
}
tmp=sum;tot=0;
if(i&&(i<j||j==0))
{
while(i&&(i<j||j==0))
{
++sum;++tot;
i=next[i];
}
}
else
{
while(j&&(j<i||i==0))
{
--sum;++tot;
j=next[j];
}
}
if(tot-1>ans)ans=tot-1;
if(Max-sum>ans)ans=Max-sum;
if(sum-Min>ans)ans=sum-Min;
}
}
printf("%d\n",ans);
}
STC05 Garden
在一个笛卡尔坐标系上有很多点，问有多少以这些点为端点的边平行于坐标轴的正方形
Solution：枚举正方形左上角，枚举这个点下方的点，唯一确定剩下的两个点位置，Hash判断，这种暴力是均摊n1.5的
#include <stdio.h>
#include <stdlib.h>
#include <algorithm>
using namespace std;
int x[100005],y[100005],r[100005],d[100005],rsum[100005],dsum[100005];
int n,i,j,k,ans;
int son[1000005],next[100005];
long long val[100005];
struct node
{
int x,y,id;
}t[100005];
inline bool cmpx(const node &a,const node &b){if(a.x!=b.x)return a.x<b.x;return a.y<b.y;}
inline bool cmpy(const node &a,const node &b){if(a.y!=b.y)return a.y<b.y;return a.x<b.x;}
long long get_val(int x,int y)
{
x+=1000000;y+=1000000;
return (long long)x*10000000+y;
}
int h;
long long tmp;
bool find(int x,int y)
{
tmp=get_val(x,y);
for(h=son[tmp%995997];h;h=next[h])
if(val[h]==tmp)return true;
return false;
}
int main()
{
scanf("%d",&n);
for(i=1;i<=n;++i)
{
scanf("%d%d",&x[i],&y[i]);
t[i].x=x[i];
t[i].y=y[i];
t[i].id=i;
val[i]=get_val(x[i],y[i]);
next[i]=son[val[i]%995997];
son[val[i]%995997]=i;
}
sort(t+1,t+n+1,cmpx);
for(i=n;i>=1;--i)
if(i==n||t[i].x!=t[i+1].x)rsum[t[i].id]=1;
else r[t[i].id]=t[i+1].id,rsum[t[i].id]=rsum[t[i+1].id]+1;
sort(t+1,t+n+1,cmpy);
for(i=n;i>=1;--i)
if(i==n||t[i].y!=t[i+1].y)dsum[t[i].id]=1;
else d[t[i].id]=t[i+1].id,dsum[t[i].id]=dsum[t[i+1].id]+1;
for(i=1;i<=n;++i)
if(rsum[i]<dsum[i])
{
for(j=r[i];j;j=r[j])
{
k=y[j]-y[i];
if(find(x[i]+k,y[i])&&find(x[i]+k,y[i]+k))
++ans;
}
}
else
{
for(j=d[i];j;j=d[j])
{
k=x[j]-x[i];
if(find(x[i],y[i]+k)&&find(x[i]+k,y[i]+k))
++ans;
}
}
printf("%d\n",ans);
}
STC06 Keyboard
STC07 Railway
NOIP双栈排序，要求线性
Solution：每次是对一段区间的已有点连边，这个可以倒着做，每个点拆成代表两个栈，然后并查集
#include <stdio.h>
#include <stdlib.h>
using namespace std;
int n,i,j,k,u,v;
int fa[200005],done[100005],a[100005],r[100005],ans[200005],skip[100005];
bool app[100005];
int get(int x,int *fa){return fa[x]==x?x:fa[x]=get(fa[x],fa);}
int main()
{
scanf("%d",&n);
for(i=1;i<=n+1;++i)r[i]=skip[i]=i;
for(i=1;i<=2*n;++i)fa[i]=i;
for(i=1;i<=n;++i)
{
scanf("%d",&a[i]);
for(app[a[i]]=true;app[k+1];++k);
done[i]=k;
}
for(i=n;i>=1;--i)
{
for(j=get(get(done[i]+1,r),skip);j<a[i];j=get(get(j+1,r),skip))
{
u=get(j,fa);
v=get(a[i]+n,fa);
fa[u]=v;
u=get(j+n,fa);
v=get(a[i],fa);
fa[u]=v;
if(j<a[i]-1)r[j]=j+1;
}
skip[a[i]]=a[i]+1;
}
for(i=1;i<=n;++i)
if(get(i,fa)==get(i+n,fa))
{
printf("NIE\n");
return 0;
}
printf("TAK\n");
for(i=1;i<=n;++i)
{
u=get(a[i],fa);
if(!ans[u])
{
ans[u]=1;
if(u>n)ans[u-n]=2;else ans[u+n]=2;
}
printf("%d",ans[get(a[i],fa)]);
if(i==n)printf("\n");else printf(" ");
}
}
STC08 Kangaroos
STC09 Aesthetic Text
分配一些诗句，相邻两行的诗句长度差会产生不美观度，求最小的不美观度
Solution：决策单调性
#include <stdio.h>
#include <stdlib.h>
using namespace std;
int n,m,i,j,k,L,R,l,r,mid,aim,a[2005];
int f[2005][2005],len[2005][2005],sum[2005],ans;
int st[2005],range[2005],top;
int Abs(int x){if(x<0)return -x;return x;}
int calc(int l,int mid,int r){return f[l][mid-1]+Abs(len[l][mid-1]-len[mid][r]);}
int main()
{
scanf("%d%d",&m,&n);
for(i=1;i<=n;++i)scanf("%d",&a[i]);
for(i=1;i<=n;++i)sum[i]=sum[i-1]+a[i];
for(i=1;i<=n;++i)
for(j=i;j<=n;++j)
len[i][j]=sum[j]-sum[i-1]+j-i;
for(i=2;i<=n;++i)
{
for(L=i-1;L>1;--L)if(len[L-1][i-1]>m)break;
for(R=i;R<n;++R)if(len[i][R+1]>m)break;
st[top=1]=L;range[top]=R;
for(j=L+1;j<i;++j)
{
while(top&&calc(j,i,range[top])<=calc(st[top],i,range[top]))--top;
if(!top)st[top=1]=j,range[top]=R;
else
{
aim=0;l=i;r=range[top];
while(l<=r)
{
mid=l+r>>1;
if(calc(j,i,mid)<=calc(st[top],i,mid))l=mid+1,aim=mid;
else r=mid-1;
}
if(aim)st[++top]=j,range[top]=aim;
}
}
for(j=i;j<=R;++j)
{
if(range[top]<j)--top;
f[i][j]=calc(st[top],i,j);
}
}
ans=f[n][n];
for(i=1;i<=n;++i)
if(len[i][n]<=m&&f[i][n]<ans)
ans=f[i][n];
printf("%d\n",ans);
}
STC10 Blockade
一张无向图，求割掉每个点后减少的连通点对是数量
Solution：基于tarjan的DP，和求割点过程类似，当确定一个点是割点时，下面那个连通块就是被割掉的连通块
#include <stdio.h>
#include <stdlib.h>
using namespace std;
int n,m,i,j,k,u,v;
long long ans[100005],size[100005];
int tarjan_index;
struct Graph_old
{
int son;
int dfn,low,from;
bool inst;
}graph[100001];
struct Edge_node
{
int next,ed;
}e[1000001];
int tot;
void addedge(int u,int v){++tot;e[tot].next=graph[u].son;graph[u].son=tot;e[tot].ed=v;}
void tarjan(int now,int from)
{
int i,tot=0;unsigned sum=0;
graph[now].dfn=graph[now].low=++tarjan_index;
graph[now].inst=true;size[now]=1;
for(i=graph[now].son;i;i=e[i].next)
if(e[i].ed!=from)
{
if(!graph[e[i].ed].dfn)
{
++tot;
tarjan(e[i].ed,now);size[now]+=size[e[i].ed];
if(graph[e[i].ed].low<graph[now].low)
graph[now].low=graph[e[i].ed].low;
if(graph[e[i].ed].low>=graph[now].dfn)
{
ans[now]+=size[e[i].ed]*sum;
sum+=size[e[i].ed];
}
}
else
{
if((graph[e[i].ed].inst)&&(graph[e[i].ed].low<graph[now].low))
graph[now].low=graph[e[i].ed].low;
}
}
graph[now].inst=false;
ans[now]+=sum*(n-1-sum);
if(now==1&&tot<=2)ans[i]=0;
ans[now]+=n-1;
ans[now]*=2;
}
int main()
{
scanf("%d%d",&n,&m);
for(;m;--m)
{
scanf("%d%d",&u,&v);
addedge(u,v);addedge(v,u);
}
tarjan(1,0);
for(i=1;i<=n;++i)printf("%lld\n",ans[i]);
}
STC11~15 (hidden)
2022年9月08日 20:40
In intermediate education, Botany is a very important subject for science group students for part-1 and part-2 first and the second year of junior and senior intermediate students, and the BIEAP has conducted the General Science examination tests including botany subject, download AP inter Botany Model Paper 2023 AP 2nd Inter Botany Question Paper Pdf with solutions for all 1st and 2nd-year students for paper-1 and paper-2 exams 2023.
2022年12月23日 00:40
The SPOJ-Problemsets STC, or problem set competition, is a contest that allows contestants to show off real estate property management Tunnel Hill their problem-solving skills. Contestants are given a set of problems to solve, and the person who solves the most problems in the shortest amount of time is the winner. This competition is a great way for problem solvers to showcase their abilities and for others to see the great work that they can do.