纪念第一次rk1↓

Problem A: lcm

题意:

给T组数据,每次求\sum _{i=1}^n lcm(n,i)

T \leq 300000,n \leq 1000000

题解:

我是整个一起筛的。

代码:

#include <bits/stdc++.h>
#define il inline
#define Max 1000005
#define ll long long
#define int ll
using namespace std;
#define getchar() (tt==ss&&(tt=(ss=In)+fread(In,1,Max,stdin),tt==ss)?EOF:*ss++)
char In[Max],*ss=In,*tt=In;
il ll read()
{
    char c=getchar();
    ll x=0,f=1;
    while(c>'9'||c<'0')
    {
        if(c=='-') f=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9')
    {
        x=x*10+c-'0';
        c=getchar();
    }
    return x*f;
}
int p[Max],cnt,m,n,T;
bool np[Max];
ll f[Max],g[Max],ans;
il void init()
{
    f[1]=1;g[1]=1;
    for(int i=2;i<Max;i++)
    {
        if(!np[i])
        {
            p[++cnt]=i;
            f[i]=i;
            g[i]=1ll*i*(i-1)+1;
        }
        for(int j=1;j<=cnt&&i*p[j]<Max;j++)
        {
            np[i*p[j]]=1;
            ll t=i*p[j];
            if(!(i%p[j]))
            {
                f[i*p[j]]=f[i]*p[j];
                if(f[i*p[j]]==i*p[j]) g[t]=g[i]+1ll*(t-i)*t;
                else
                {
                    g[t]=g[f[t]]*g[t/f[t]];
                }
                break;
            }
            f[t]=f[p[j]];
            g[t]=g[i]*g[p[j]];
        }
    }
}
il ll calc(int n)
{
    ll res=g[n]+1;
    res=res*n,res=res/2;
    return res;
}
il void write(ll x)
{
    //cout<<x<<endl;
    if(x>9) write(x/10);
    if(x) putchar(x%10+'0');
}
signed main()
{
    //freopen("A.txt","r",stdin);
    //freopen("A.out","w",stdout);
    init();
    T=read();
    while(T--)
    {
        n=read();
        write(calc(n));
        //printf("%lld\n",calc(n));
        putchar('\n');
    }
}

Problem B: lis

题意:

n个数,求长度为l的字典序最小的最长上升子序列。

n \leq 100000,a_i \leq 100000

题解:

从后往前做最长下降子序列,记录每个位置能往后做的最长上升子序列长度。

然后排序后xjb贪心就完事了。

代码:

#include <bits/stdc++.h>
#define il inline
#define Max 100005
using namespace std;
#define getchar() (tt==ss&&(tt=(ss=In)+fread(In,1,Max,stdin),tt==ss)?EOF:*ss++)
char In[Max],*ss=In,*tt=In;
il int read()
{
    char c=getchar();
    int x=0,f=1;
    while(c>'9'||c<'0')
    {
        if(c=='-') f=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9')
    {
        x=x*10+c-'0';
        c=getchar();
    }
    return x*f;
}
struct node
{
    int x,id;
}e[Max];
il bool cmp(node a,node b)
{
    if(a.x!=b.x) return a.x<b.x;
    else return a.id<b.id;
}
int n,a[Max],f[Max],cnt,g[Max],l;
int main()
{
    n=read();l=read();
    for(int i=1;i<=n;i++) a[i]=read();
    f[0]=-10000000;
    for(int i=n;i>=1;i--)
    {
        if(a[i]<-f[cnt])
        {
            f[++cnt]=-a[i];
            g[i]=cnt;
        }
        else
        {
            int m=lower_bound(f+1,f+1+cnt,-a[i])-f;
            f[m]=-a[i];
            g[i]=m;
        }
    }
    //for(int i=1;i<=n;i++) cout<<g[i]<<endl;
    if(cnt<l) puts("impossible");
    for(int i=1;i<=n;i++) e[i].x=a[i],e[i].id=i;
    sort(e+1,e+1+n,cmp);
    int lst=0,mn=0;
    for(int i=1;i<=n&&l;i++)
    {
        if(g[e[i].id]>=l&&e[i].id>lst&&e[i].x>mn)
        {
            printf("%d ",e[i].x);
            l--;
            lst=e[i].id;
            mn=e[i].x;
        }
    }
    puts("");
}

Problem C: string

题意:

|S| \leq 1000000

题解:

代码:

#include <bits/stdc++.h>
#define il inline
#define Max 1000005
#define Mod 1000000007
#define ll long long
#define int ll
using namespace std;
il int read()
{
    char c=getchar();
    int x=0,f=1;
    while(c>'9'||c<'0')
    {
        if(c=='-') f=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9')
    {
        x=x*10+c-'0';
        c=getchar();
    }
    return x*f;
}
char s[Max];
int n,a[Max],nt[Max],f[Max][2];
ll ans[Max];
il void kmp()
{
    nt[1]=0;
    for(int i=2,j;i<=n;i++)
    {
        j=nt[i-1];
        while(j&&s[j+1]!=s[i]) j=nt[j];
        if(s[j+1]==s[i]) nt[i]=j+1;
        else nt[i]=0;
    }
    for(int i=0;i<n;i++)
    {
        f[i][a[i+1]]=i+1;
        f[i][a[i+1]^1]=f[nt[i]][a[i+1]^1];
    }
}
signed main()
{
    scanf("%s",s+1);
    n=strlen(s+1);
    for(int i=1;i<=n;i++) a[i]=(s[i]=='T');
    kmp();
    ans[1]=2;
    for(int i=1;i<n;i++)
    {
        ll t=(ans[i]-ans[f[i][a[i+1]^1]]+2+Mod)%Mod;
        ans[i+1]=(ans[i]+t)%Mod;
    }
    cout<<ans[n]<<endl;
}