3.31

T1

导弹拦截魔改...简单的 $dp$ 可我竟然调了1hour...

Code

简单题不放了

T2

每次找中间的 l 然后往两边搜，若不能匹配再减一下就好...

Code

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

inline ll read()
{
								ll a=0,f=1;
								char ch=getchar();
								for(; !isdigit(ch); ch=getchar())
																if(ch=='-') f=-1;
								for(; isdigit(ch); ch=getchar())
																a=(a<<3)+(a<<1)+ch-'0';
								return a*f;
}

const ll mod=1e9+7;
const int N=1e6+5;
long long num1,num2,n,num,ans;

inline ll qpow(ll a,ll n)
{
								ll ans=1;
								for(; n; n>>=1)
								{
																if(n&1) ans=(ans*a)%mod;
																a=(a*a)%mod;
								}
								return ans;
}

signed main()
{
								freopen("jiangge.in","r",stdin);
								freopen("jiangge.out","w",stdout);
								n=read();
								for(int i=1; i<=n; i++)
								{
																char ch=getchar();
																if(ch=='b') ans =( ans+num2)%mod;
																else if(ch=='l') num2=(num2+num1)%mod;
																else if(ch=='a') num1=(num1+qpow(3,num))%mod;
																else if(ch=='?')
																{
																								ans =(ans*3%mod+num2)%mod;
																								num2=(num2*3%mod+num1)%mod;
																								num1=(num1*3%mod+qpow(3,num))%mod;
																								num++; num%=mod;
																}
//		printf("%lld--->%lld--->%lld\n",num1,num2,ans);
//		if(num1<0)break;
								}
								printf("%lld\n",(ans+mod)%mod);
								return 0;
}
/*
   600849148
 */

T4

原本以为这题很难...实则有一种很水的解法可以卡过去（原题可过，比赛题时间复杂度是wa的）
就是先将序列变成差值序列，然后找一个序列，枚举左端点，取一个匹配到的最短的序列再和答案取个max即可。

Code

#include <cstdio>
#include <iostream>
#include <algorithm>
#define int long long
using namespace std;
const int N=1e3+10;
int n,m[N],a[N][N],ans,i,j,l,r,maxx,p,rr;
signed main()
{
        cin >> n;
        for(i=1; i<=n; i++)
        {
                cin >> m[i];
                for(j=1; j<=m[i]; j++)
                        scanf("%lld",&a[i][j]);
                m[i]--;
                if(m[i]==0) {puts("1"); return 0;}
                for(j=1; j<=m[i]; j++)
                        a[i][j]=a[i][j+1]-a[i][j];
        }
        for(l=1; l<=m[1]; l++)
        {
                r=m[1];
                for(i=2; i<=n; i++)
                {
                        maxx=0;
                        for(j=1; j<=m[i]; j++)
                        {
                                if(a[i][j]==a[1][l])
                                {
                                        p=j,rr=l;
                                        while(a[i][p]==a[1][rr] && p<=m[i] && rr<=r)
                                                rr++,p++;
                                        maxx=max(maxx,rr-1);
                                }
                        }
                        r=min(r,maxx);
                }
                ans=max(ans,r-l+1);
        }
        cout<<ans+1;
}

4.2

T4

Idea

不难看出，这是一道 $dp$ 题，但是发现求没被激活的集合数有点难？怎么办？我们可以求出被激活的集合数（因为其是一一对应的）。又因为每个机器人被激活后会激活后面的一系列机器人，那么我们就只需要将这个机器人和它所能激活的一系列机器人缩到一起就可以了。
我们先定义 $to[i]$ 为激活第 $i$ 个机器人后至 $to[i]$ 个都会被激活。

$dp$方程也很好推：
$f[i,0]$ 表示不激活机器人 $i$ 时 机器人 $i$ 后的集合数。
$f[i,1]$ 表示激活机器人 $i$ 是 机器人 $i$ 后的集合数。
那么
$f[i,0]=f[i+1,0]+f[i+1,1]$
$f[i,1]=f[to[i],0]+f[to[i],1]$

那么接下来的问题就是如何求 $to[i]$ 了，这也很好办，二分一下然后用线段树查找一下最值即可。（别问为什么用线段树，问就是这几星期学图论锻炼一下线段树能力）

最后答案就是 $f[1,0]+f[1,1]$

Code

#include <cstdio>
#include <iostream>
#include <algorithm>
#define int long long
using namespace std;
const int N = 200001;
const int mod = 998244353;
int n,f[N][2],maxx[N],to[N];
struct stu
{
        int qi,la;
};
bool cmp(stu x, stu y)
{
        return x.qi<y.qi;
}
stu a[N];

int ls(int val)
{
        return val<<1;
}
int rs(int val)
{
        return val<<1|1;
}

void pushup(int p)
{
        maxx[p]=max(maxx[ls(p)],maxx[rs(p)]);
}
void updata(int l, int r, int p, int val, int k)
{
        if(l==r) {maxx[p] = k; return;}
        int mid=(l+r)/2;
        if (val<=mid) updata(l, mid, ls(p), val, k);
        else updata(mid + 1, r, rs(p), val, k);
        pushup(p);
}
int maxv(int l, int r, int p, int ll, int rr)
{
        if (ll > rr) return 0;
        if (l >= ll && r <= rr) return maxx[p];
        int mid = l + r >> 1, res = 0;
        if (ll <= mid) res = maxv(l, mid, ls(p), ll, rr);
        if (rr > mid) res = max(res, maxv(mid + 1, r, rs(p), ll, rr));
        return res;
}
signed main()
{
        cin >> n;
        for (int i=1; i<=n; i++) cin >> a[i].qi >> a[i].la;//qi 起点 la到哪
        sort(a+1,a+n+1,cmp);//先按起点从小到大排序

        for (int i=n; i; --i)
        {
                int l = i, r = n, mid, sum = 0;

                while (l<=r)
                {
                        int mid=(l+r)/2;
                        if (a[mid].qi<a[i].qi+a[i].la) l=mid+1,sum=mid;
                        else r=mid-1;
                }
                to[i]=max(r+1,maxv(1,n,1,i+1,sum));
                updata(1,n,1,i,to[i]);
        }//二分求to[i]

        f[n+1][0]=1;
        for (int i=n; i>=1; i--)
        {
                f[i][0]=(f[i+1][1]+f[i+1][0]) % mod;
                f[i][1]=(f[to[i]][0]+f[to[i]][1]) % mod;
        }//dp
        cout << (f[1][0]+f[1][1]) % mod;
}