长沙集训Ⅱ——Day5

· · 个人记录

T1

嘟嘟噜

经典的约瑟夫问题，但需要比较低的时间复杂度。
看到数据范围，知道这题肯定不能用模拟（O(n^2)）啦!（当然，如果实在做不出来也可以用，不过会全TLE，0分）

优化1

先把每个人的编号当成0……n-1，最后把计算出的的答案+1即可。
我们来拿n=5,k=3来举个栗子（k就是题目中的m）。

显然，时间复杂度已经被优化到O(n)了。但还是会超时。。。那怎么办呢？

优化2


这个方法的时间复杂度约为O(mlog(n))，可以过。

#include<cstdio>
#include<cstring>
using namespace std;
int T;
long long n,m;
int main()
{
    scanf("%d",&T);
    while(T--)
    {
        scanf("%lld%lld",&n,&m);
        long long f1=0,f2,x,i=2;
        if(m==1)
        {
            printf("%lld\n",n);
            continue;
        }
        while(i<=n)
        {
            if(f1+m<i)
            {
                x=(i-f1)/m;
                if(i+x<n)
                {
                    i+=x;
                    f2=f1+x*m;
                    f1=f2;
                }
                else
                {
                    f2=f1+m*(n-i);
                    i=n;
                    f1=f2;
                }
            }
            f2=(f1+m)%i;
            f1=f2;
            i++;
        }
        printf("%lld\n",f2+1);
    }
    return 0;
}

T2

这题简直就是数学题。。。

首先，要知道下面这个结论——

如果\vec a=(x_{1},y_{1})，\vec b=(x_{2},y_{2})，那么，|\vec a×\vec b|=|x_{1}y_{2}-x_{2}y_{1}|。

再来看一下题目中的式子。

\ \ \ \ \sum\limits_{1<=i<j<=n}|v_{i}×v_{j}|^2 =\sum\limits_{1<=i<j<=n}(x_{i}y_{j}-y_{i}x_{j})^2 =\sum\limits_{1<=i<j<=n}x_{i}^2y_{j}^2+\sum\limits_{1<=i<j<=n}y_{i}^2x_{j}^2-2\sum\limits_{1<=i<j<=n}x_{i}y_{i}x_{j}y_{j} =(\sum\limits_{i=1}^{n}x_{i}^2)(\sum\limits_{i=1}^{n}y_{i}^2)-(\sum\limits_{i=1}^{n}x_{i}y_{i})^2

然后我们只要用树状数组维护这三个前缀和即可。

注：1.每次修改不仅要修改树状数组中的数，还要修改原序列中的数
\ \ \ \ \ \ \ 2.这题运算当中有乘，有加，有减，很容易使结果变成负的，所以保险起见，每次运算都加上20170927再模上20170927。

#include<cstdio>
using namespace std;
const long long MN=1000010,p=20170927;
long long n,m,x[MN],y[MN],a[MN],b[MN],c[MN];
inline long long lowbit(long long x) { return x&(-x); }
inline void add(long long x,long long y,long long g[])
{
    for(;x<=n;x+=lowbit(x)) g[x]=(g[x]+y)%p;
}
inline long long ask(long long x,long long g[])
{
    long long res=0;
    for(;x;x-=lowbit(x)) res=(res+g[x])%p;
    return res;
}
int main()
{
    scanf("%lld%lld",&n,&m);
    for(long long i=1;i<=n;i++) 
    {
        scanf("%lld%lld",&x[i],&y[i]);
        add(i,x[i]*x[i],a);
        add(i,y[i]*y[i],b);
        add(i,x[i]*y[i],c); 
    }
    for(long long i=1;i<=m;i++)
    {
        long long h;
        scanf("%lld",&h);
        if(h==1)
        {
            long long pp,xx,yy;
            scanf("%lld%lld%lld",&pp,&xx,&yy);
            add(pp,((p+xx*xx-x[pp]*x[pp])%p+p)%p,a);
            add(pp,((p+yy*yy-y[pp]*y[pp])%p+p)%p,b);
            add(pp,((p+xx*yy-x[pp]*y[pp])%p+p)%p,c);
            x[pp]=xx; y[pp]=yy;
        }
        else
        {
            long long l,r;
            scanf("%lld%lld",&l,&r);
            long long aa=(p+ask(r,a)-ask(l-1,a))%p,
                      bb=(p+ask(r,b)-ask(l-1,b))%p,
                      cc=(p+((p+ask(r,c)-ask(l-1,c))%p)*((p+ask(r,c)-ask(l-1,c))%p)%p)%p;
            printf("%lld\n",(p+(aa%p)*(bb%p)%p-cc%p)%p);
        }
    }
    return 0;
}

T3

凤凰院凶真

本题很明显是让我们求最长公共上升子序列（LCIS），《算法竞赛进阶指南》第264到第265页有求其长度的方法。

所以我们只要解决如何保存状态的问题就行了（详见代码）。 

#include<cstdio>
#include<vector>
#include<iostream>
using namespace std;
int n,m,a[5010],b[5010],dp[5010][5010],pre[5010][5010],pos,ans;
vector<int>res;
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++) scanf("%d",&a[i]);
    scanf("%d",&m);
    for(int i=1;i<=m;i++) scanf("%d",&b[i]);
    a[0]=-0x3f3f3f3f; b[0]=-0x3f3f3f3f;
    int tmp=0,id=0;
    for(int i=1;i<=n;i++)
    {
        tmp=0,id=0;
        for(int j=1;j<=m;j++)
        {
            if(a[i]==b[j]) dp[i][j]=tmp+1,pre[i][j]=id;
            else dp[i][j]=dp[i-1][j];
            if(b[j]<a[i]&&tmp<dp[i-1][j]) tmp=dp[i-1][j],id=j;
        }
    }
    for(int i=1;i<=m;i++) 
        if(ans<=dp[n][i]) ans=dp[n][i],pos=i;
    printf("%d\n",ans);
    if(!ans) return 0;
    res.push_back(pos);
    while(n&&pos)
    {
        if(pre[n][pos])
        {
            pos=pre[n][pos];
            res.push_back(pos);
        }
        else
            n--;
    }
    for(int i=res.size()-1;i>=0;i--)
        printf("%d ",b[res[i]]);
    return 0;
}