Zory冬日暖心赛

还真是暖心原题赛,

第一题就是道“激光炸弹”。

还有一种扫描线的做法,也就是考虑能覆盖一点$(x,y)$的矩形右上角的范围,这个范围也是一个矩形(不要混淆),左下角定点$(x,y)$,右上角顶点$(x+r,y+r)$,之后扫描线处理,区间$(y_1,y_1+r)$与区间$(y_2,y_2+r)$重的部分,就是矩形(不是范围矩形),右上角可以取到最大值选择的范围,重的区间可以pushdown得到,之后用线段树维护一下最大值。

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#define gc getchar()
#define ll long long
using namespace std;
const int N=5005;
inline void qr(int &x)
{
    x=0;char c=gc;int f=1;
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=gc;}
    while(c>='0'&&c<='9'){x=x*10+(c^48);c=gc;}
    x*=f;
}
void qw(int x)
{
    if(x<0)x=-x,putchar('-');
    if(x/10)qw(x/10);
    putchar(x%10+48);
}
int f[N][N],sum[N][N],n,r;
int main()
{
    //freopen("bomb1.in","r",stdin);
    //freopen("a.out","w",stdout);
    memset(sum,0,sizeof(sum));
    qr(n),qr(r);
    for(int i=1,x,y,w;i<=n;i++)
    {
        qr(x),qr(y),qr(w),++x,++y;
        sum[x][y]+=w;
        /*if(x>=82&&x<=90&&y>=41&&y<=49)
        {
            printf("%d %d %d\n",x,y,w);
        }*/
    }
    int mx=5001;
    for(int i=1;i<=mx;i++)
        for(int j=1;j<=mx;j++)
        {
            sum[i][j]+=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1];
        }
    int ans=0;
    for(int i=r;i<=mx;i++)
        for(int j=r;j<=mx;j++)
        {
            f[i][j]=sum[i][j]-sum[i-r][j]-sum[i][j-r]+sum[i-r][j-r];
            //if(i<=101&&j<=101)printf("%d %d:%d\n",i,j,f[i][j]);
            ans=max(f[i][j],ans);
        }
    qw(ans);puts("");
    return 0;
}

第二题

也是原题。

树形$DP$,用$f_{x,i}$记录一下从子树到$x$(包括$x$本身)的路径长度$\%3=i$的路径数,同理,自顶而下处理一下一个点除子树的路径,做一次二次换根即可。

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#define gc getchar()
#define ll long long
using namespace std;
const int N=2e5+5;
template<class o>
inline void qr(o &x)
{
    x=0;char c=gc;int f=1;
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=gc;}
    while(c>='0'&&c<='9'){x=x*10+(c^48);c=gc;}
    x*=f;
}
void qw(ll x)
{
    if(x<0)x=-x,putchar('-');
    if(x/10)qw(x/10);
    putchar(x%10+48);
}
struct edge{int y;ll w;int next;}a[N<<1];int len,last[N];
void ins(int x,int y,ll w){a[++len]=(edge){y,w,last[x]};last[x]=len;}
ll f[N][3],g[N][3];
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
int fa[N];
void treedp(int x)
{
    f[x][0]=1;
    for(int k=last[x];k;k=a[k].next)
    {
        int y=a[k].y;
        if(y==fa[x])continue;
        fa[y]=x;treedp(y);
        f[x][(1+a[k].w)%3]+=f[y][1];
        f[x][(2+a[k].w)%3]+=f[y][2];
        f[x][(0+a[k].w)%3]+=f[y][0];
    }
}
void sdp(int x)
{
    for(int k=last[x];k;k=a[k].next)
    {
        int y=a[k].y;
        if(y==fa[x])continue;
        g[y][(1+a[k].w)%3]+=g[x][1]+f[x][1]-f[y][((1-a[k].w)%3+3)%3];
        g[y][(2+a[k].w)%3]+=g[x][2]+f[x][2]-f[y][((2-a[k].w)%3+3)%3];
        g[y][a[k].w%3]+=g[x][0]+f[x][0]-f[y][(-a[k].w%3+3)%3];
        sdp(y);
    }
}
int main()
{
    int n;qr(n);
    for(int i=1,x,y;i<n;i++){ll w;qr(x),qr(y),qr(w),w%=3,ins(x,y,w),ins(y,x,w);}
    treedp(1);
    g[1][0]=g[1][1]=g[1][2]=0;
    sdp(1);
    ll ans=0;
    for(int i=1;i<=n;i++)ans+=f[i][0]+g[i][0];
    ll d=gcd(ans,1ll*n*n);
    printf("%lld/%lld\n",ans/d,1ll*n*n/d);
    return 0;
}
/*
5
1 2 1
1 3 2
1 4 1
2 5 3
*/

第三题

第一问很无脑,先预处理一下$B$串从$j$往后,字符$c$最先出现的位置,之后枚举左端点,单调拓展右端点,判断是否匹配,若失配,则更新答案。

第二问稍显复杂,由于$A$串也是子序列,考虑$DP$,

有$f_{i,j}$表示$A$串前$i$个字符用$f_{i,j}$个字符匹配到$B$串的第$j$个字符(有些字符可以不选)。

因此,可以分为两种状态,选$i$和不选$i$。

则有

$\large f_{i,nxt_{j+1,a_i}}=\min\{f_{i-1,j}+1\}(选)\\\large f_{i,j}=\min\{f_{i-1,j}\}(不选)$

分别对应以上两种情况。

考场以为很难,颓废了。

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<cmath>
using namespace std;
const int N=2005;
int nxt[N][27],f[N][N];
//nxt[i][c]表示B串第i个位置之后第c个字符出现的最早位置 
//f[i][j]表示A串前i个字符与B串前j个字符相匹配,既可以选i,又可以不选的最短匹配长度。 
char a[N],b[N];
int main()
{
    int n,m;scanf("%s%s",a+1,b+1);
    n=strlen(a+1),m=strlen(b+1);
    for(int i=1;i<=26;i++)nxt[m+1][i]=m+1;
    for(int i=m;~i;i--)
    {
        for(int j=1;j<=26;j++)
            nxt[i][j]=nxt[i+1][j];
        if(i!=0)nxt[i][b[i]-'a'+1]=i;
    }
    int ans=0x3f3f3f3f;
    for(int l=1;l<=n;l++)
    {
        int pos=0;
        for(int r=l;r<=n;r++)
        {
            pos=nxt[pos+1][a[r]-'a'+1];
            if(pos==m+1)//失配
            {
                ans=min(ans,r-l+1);
                break;//失配之后再也不能匹配了。 
            }
        }
    }
    if(ans==0x3f3f3f3f){puts("-1");}
    else printf("%d",ans),puts("");
    memset(f,0x3f,sizeof(f));f[0][0]=0;
    ans=0x3f3f3f3f;
    for(int i=1;i<=n;i++)
    {
        for(int j=m;~j;j--)
        {
            f[i][nxt[j+1][a[i]-'a'+1]]=min(f[i][nxt[j+1][a[i]-'a'+1]],f[i-1][j]+1);//i匹配b串在j的下一个a[i]字符。
            f[i][j]=min(f[i][j],f[i-1][j]);//不选i这个字符去跟b串匹配。 
        }
        ans=min(ans,f[i][m+1]);//不匹配的最短长度(m+1表示不匹配)。 
    }
    if(ans==0x3f3f3f3f)puts("-1");
    else printf("%d",ans),puts("");
    return 0;
}