这次又炸了两道题。。410变270。。

T3 dfs之后没恢复数组，T4 这次才知道string::erase的复杂度是$O(n)$。。

T2

description：

最近小G新开了一家蛋糕店。开业第一天，一共来个n位顾客。由于小G非常懒，他每次只会接待一位顾客。每个顾客都想尽快的买到蛋糕，所以没有第一个买到蛋糕的顾客都会有一个愤怒值。最终排在第i个位置的顾客x的愤怒值为i*a[x]。小G想要所有顾客的愤怒值之和最小。求最小的愤怒值之和。

签到题。。。

排个序后输出$sigma{i=1}{n}{a[i]*(i-1)}$即可

std:

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<ctime>
#include<vector>
#include<queue>
#include<algorithm>
#include<string>
#include<sstream>
#include<cctype>
#include<cmath>
#include<iomanip>
#include<map>
#include<stack>
#include<set>
#include<functional>
#define in(x) x=read()
#define qr read()
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
inline ll read()
{
    char ch=' ';
    ll f=1,x=0;
    while(!isdigit(ch)){ch=getchar();if(ch=='-')f*=-1;}
    while(isdigit(ch)){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();}
    return f*x;
}
bool cmp(int x,int y){return x>y;}
ll a[1000010],ans=0;
int main()
{
    freopen("cake.in","r",stdin);
    freopen("cake.out","w",stdout);
    ll n=qr;
    for(int i=1;i<=n;i++)in(a[i]);
    sort(a+1,a+1+n,cmp);
    for(int i=1;i<=n;i++)ans+=ll(i-1)*a[i];
    cout<<ans;
    return 0;
}

T3

description:

小G通过摆放一些城市和道路构成了一个世界地图。趁着小G出去玩的时候，大G把小G的世界地图上的城市全部打乱并放在了原来这些城市所在的位置（并不是一一对应），又修改了一些道路。小G玩完回来后发现自己的东西被打乱了，感到非常生气，但是他又被一个更有趣的问题吸引了：被修改之后的世界地图与原来的世界地图的最大相似度是多少？ （ps：相似度的定义为将城市还原后还有多少条道路和之前的道路相同）

$9!*500$暴搜即可

然而这题有许多坑。。

有重边。。。加边时要用++，不能用=1。。

另外check完后要把邻边矩阵还原（这个值90分。。。）

std:

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<ctime>
#include<vector>
#include<queue>
#include<algorithm>
#include<string>
#include<sstream>
#include<cctype>
#include<cmath>
#include<iomanip>
#include<map>
#include<stack>
#include<set>
#include<functional>
#define in(x) x=read()
#define qr read()
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
inline int read()
{
    char ch=' ';
    int f=1,x=0;
    while(!isdigit(ch)){ch=getchar();if(ch=='-')f*=-1;}
    while(isdigit(ch)){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();}
    return f*x;
}
int ans[10],vis[10],anss=0,m,n,a[510],b[510],c[510],d[510],e[10][10],f[10][10];
void check()
{
    int res=0;
    for(int i=1;i<=m;i++)
    {
        if(e[ans[c[i]]][ans[d[i]]])res++,e[ans[c[i]]][ans[d[i]]]--;
    }
    for(int i=1;i<=9;i++)
    {
        for(int j=1;j<=9;j++)
        {
            e[i][j]=f[i][j];
        }
    }
    anss=max(anss,res);
}
void dfs(int x)
{
    if(x>n)
    {
        check();
        return;
    }
    for(int i=1;i<=n;i++)
    {
        if(!vis[i])
        {
            ans[x]=i;
            vis[i]=1;
            dfs(x+1);
            ans[x]=vis[i]=0;
        }
    }
}
int main()
{
    freopen("similarity.in","r",stdin);
    freopen("similarity.out","w",stdout);
    in(n),in(m);
    for(int i=1;i<=m;i++)in(a[i]),in(b[i]),e[a[i]][b[i]]++;
    for(int i=1;i<=m;i++)in(c[i]),in(d[i]);
    for(int i=1;i<=9;i++)
    {
        for(int j=1;j<=9;j++)
        {
            f[i][j]=e[i][j];
        }
    } 
    dfs(1);
    cout<<anss;
    return 0;
}

T4

description：

小G最近学会了二进制数，他觉得太小的二进制数太没意思，于是他想对一个巨大二进制数做以下4种基础运算： 运算1：将整个二进制数加1 运算2：将整个二进制数减1 运算3：将整个二进制数乘2 运算4：将整个二进制数整除2 小G很想知道运算后的结果，他只好向你求助。 （Ps：为了简化问题，数据保证+，-操作不会导致最高位的进位与退位）

直接模拟。。。

然而直接用了string，结果string::erase是o(n)。。。T掉50分

而且这样实际上通不过。。

（如果1100000...,然后不断+1-1+1-1。。。复杂度就炸了）

正解：

存两个高精度x,y，开始x=输入，y=0

+：x++

-：y++

$*：x*=2,y*=2$

/：如果y末尾为0先y++，然后x/=2,y/=2

最后输出x-y即可

std：

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<ctime>
#include<vector>
#include<queue>
#include<algorithm>
#include<string>
#include<sstream>
#include<cctype>
#include<cmath>
#include<iomanip>
#include<map>
#include<stack>
#include<set>
#include<functional>
#define in(x) x=read()
#define qr read()
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
inline int read()
{
    char ch=' ';
    int f=1,x=0;
    while(!isdigit(ch)){ch=getchar();if(ch=='-')f*=-1;}
    while(isdigit(ch)){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();}
    return f*x;
}
int s1[7000010]={0},s2[7000010]={0},ss1[7000010]={0},ss2[7000010]={0};
int main()
{
    freopen("two.in","r",stdin);
    freopen("two.out","w",stdout);
    int n1=qr+700000-1,m=qr;
    for(int i=700000;i<=n1;i++)s1[i]=getchar()-'0';
    int n2=700000,l1=700000,l2=700000;
    char op=' ';
    for(int i=1;i<=m;i++)
    {
        op=getchar();
        while(op!='+'&&op!='-'&&op!='*'&&op!='/')op=getchar();
        if(op=='/')
        {
            if(s2[n2]==1&&s1[n1]==0)
            {
                s2[n2]++;
                int now=n2;
                while(s2[now]>=2)
                {
                    s2[now]=0;
                    now--;
                    s2[now]++;
                    if(now<l2)l2--;
                }
            }
            n1--,n2--;
            if(n2<l2)l2--;
        }
        if(op=='*'){s1[++n1]=0,s2[++n2]=0;}
        if(op=='+')
        {
            s1[n1]++;
            int now=n1;
            while(s1[now]>=2)
            {
                s1[now]=0;
                now--;
                s1[now]++;
                if(now<l1)l1--;
            }
        }
        if(op=='-')
        {
            s2[n2]++;
            int now=n2;
            while(s2[now]>=2)
            {
                s2[now]=0;
                now--;
                s2[now]++;
                if(now<l2)l2--;
            }
        }
    }
    for(int i=1;i<=n1-l1+1;i++)ss1[n1-l1+2-i]=s1[i+l1-1];
    for(int i=1;i<=n2-l2+1;i++)ss2[n2-l2+2-i]=s2[i+l2-1];
    int y1=n1-l1+1,y2=n2-l2+1;
    for(int i=1;i<=y2;i++)
    {
        ss1[i]-=ss2[i];
        if(ss1[i]<0)ss1[i]+=2,ss1[i+1]--;
    }
    int now=y2+1;
    while(ss1[now]<0)ss1[now]+=2,ss1[now+1]--,now++;
    if(ss1[y1]<0)y1--;
    for(int i=y1;i>=1;i--)cout<<ss1[i];
    return 0;
}

T5

description：

小 X 最近迷上了矩阵，他定义了一个对于一种特殊矩阵的特征函数 G。对于 N*N 的矩
阵 A， A 的所有元素均为 0 或 1，则 G(A)等于所有 A[i][j]*A[j][i](1<=i,j<=n)的和对 2 取余之
后的结果。举一个例子：
对于上图这个 3*3 矩阵 A， G(A)=(1*1+1*0+1*1+0*1+1*1+1*0+1*1+ 0*1+0*0) mod 2=0
当然询问一个矩阵的 G 值实在是太简单了。小 X 在给出一个 N*N 矩阵的同时将给你 Q
个操作，操作描述如下：
操作 1：形如一个整数 1 和一个整数 x，表示将第 x 行的元素全部“翻转”。
操作 2：形如一个整数 2 和一个整数 x，表示将第 x 列的元素全部“翻转”。
操作 3：形如一个整数 3，表示询问当前矩阵的特征值 G。
“翻转”的定义为将 1 变成 0，将 0 变成 1。

虽然在T5，但是很水。。

只有对角线上的点才对答案有贡献，所以每次修改ans必定0变1或1变0

所以每次ans=1-ans，最终输出ans即可

std：

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<ctime>
#include<vector>
#include<queue>
#include<algorithm>
#include<string>
#include<sstream>
#include<cctype>
#include<cmath>
#include<iomanip>
#include<map>
#include<stack>
#include<set>
#include<functional>
#define in(x) x=read()
#define qr read()
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
inline int read()
{
    char ch=' ';
    int f=1,x=0;
    while(!isdigit(ch)){ch=getchar();if(ch=='-')f*=-1;}
    while(isdigit(ch)){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();}
    return f*x;
}
int a[1010][1010],n,ans=0;
int main()
{
    freopen("matrix.in","r",stdin);
    freopen("matrix.out","w",stdout);
    in(n);
    int q=qr;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            in(a[i][j]);
            if(i==j)ans+=a[i][j]*a[i][j],ans%=2;
        }
    }
    for(int i=1;i<=q;i++)
    {
        int op=qr;
        if(op==3)cout<<ans;
        else qr,ans=1-ans;
    }
    return 0;
}

T1

description：

小G在一个n*m的棋盘上随意放上了一些黑色的棋子，然后又在剩下所有没有放棋子的格子里放上了白色的棋子。现在小G想知道他是否能通过以下两种变换将整个棋盘上的棋子全部变成白色。 变幻1：选择一列，将这一列的棋子全部反色，即黑变白，白变黑。 变幻2：选择一行，将这一行的棋子全部反色。 如果能将整个棋盘上的棋子全部变成白色，则输出最少需要的变幻次数。否则输出经过若干次变幻后，棋盘上最少的黑子个数。

对，你没看错，就是T1

这题虽然实际不难，但很难想，放在这里才是真实难度（考试时这题直接弃疗。。）

主要就是要发现每行最多只能反色一次，然后枚举行，贪心列即可

std：

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<ctime>
#include<vector>
#include<queue>
#include<algorithm>
#include<string>
#include<sstream>
#include<cctype>
#include<cmath>
#include<iomanip>
#include<map>
#include<stack>
#include<set>
#include<functional>
#define in(x) x=read()
#define qr read()
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
inline int read()
{
    char ch=' ';
    int f=1,x=0;
    while(!isdigit(ch)){ch=getchar();if(ch=='-')f*=-1;}
    while(isdigit(ch)){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();}
    return f*x;
}
int anss1=10000000,anss2=10000000,b[1010][1010],a[1010][1010];
int main()
{
    freopen("chess.in","r",stdin);
    freopen("chess.out","w",stdout);
    int n=qr,m=qr;
    bool f=0;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            b[i][j]=getchar()-'0';
        }
        getchar();
    }
    for(int i=0;i<(1<<n);i++)
    {
        int ans1=0,ans2=0;
        for(int j=1;j<=n;j++)
        {
            for(int k=1;k<=m;k++)a[j][k]=b[j][k];
        }
        for(int j=1;j<=n;j++)
        {
            if(i&(1<<j))
            {
                ans1++;
                for(int k=1;k<=m;k++)
                {
                    a[j][k]^=1;
                }
            }
        }
        for(int j=1;j<=m;j++)
        {
            int sum=0;
            for(int k=1;k<=n;k++)
            {
                if(a[k][j])sum++;
            }
            if(sum*2>n)ans1++,ans2+=(n-sum);
            else ans2+=sum;
        }
        if(ans2==0)anss1=min(anss1,ans1),f=1;
        else anss2=min(anss2,ans2);
    }
    if(f)cout<<anss1;
    else cout<<anss2;
    return 0;
}

今天真爆炸。。

T2 忘打回车 爆9

T3 复制时没把visb改成visa 52->9

本来100+100+52+27+0+43=322 结果炸成186。。

这几天总是出各种低级失误，从没加分号到二进制拆分写错，忘打回车……总共也算丢了几百分吧，很致命！

以后要重视细节检查，争取发挥出应有水平！

更新题解：

T1

Description:

定义一个 6 位数是 lucky 的，当且仅当它的前 3 位之和等于后 3 位之和，比如 165912 给出数 x，找出最小的、大于 x 的幸运数字。 无解输出-1

题解：

直接模拟即可（这道题居然不会有-1。。）

std

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<ctime>
#include<vector>
#include<queue>
#include<algorithm>
#include<string>
#include<sstream>
#include<cctype>
#include<cmath>
#include<iomanip>
#include<map>
#include<stack>
#include<set>
#include<functional>
#define in(x) x=read()
#define qr read()
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
inline int read()
{
    char ch=' ';
    int f=1,x=0;
    while(!isdigit(ch)){ch=getchar();if(ch=='-')f*=-1;}
    while(isdigit(ch)){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();}
    return f*x;
}
inline bool check(int x){return (x%10+x/10%10+x/100%10)==(x/100000+x/10000%10+x/1000%10);}
int main()
{
    freopen("lucky.in","r",stdin);
    freopen("lucky.out","w",stdout);
    int x;
    in(x);x++;
    while(!check(x))
    {
        x++;
        if(x>=1000000)
        {
            cout<<-1;
            return 0;
        }
    }
    cout<<x;
    return 0;
}

T2

Description:

街道上有 n 个点 x1,x2,…,xn。你可以在其中一个点开始行程，在任何一个点结束。要求遍历所有点。从点 i 走到点 j，需要花费 abs(xi – xj)的时间。请问最少花费多少时间。

题解：

观察可知答案为max-min（计算时间时不会考虑中间的点）

然而我处理多组数据时没输回车。。爆9

std：

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<ctime>
#include<vector>
#include<queue>
#include<algorithm>
#include<string>
#include<sstream>
#include<cctype>
#include<cmath>
#include<iomanip>
#include<map>
#include<stack>
#include<set>
#include<functional>
#define in(x) x=read()
#define qr read()
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
inline int read()
{
    char ch=' ';
    int f=1,x=0;
    while(!isdigit(ch)){ch=getchar();if(ch=='-')f*=-1;}
    while(isdigit(ch)){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();}
    return f*x;
}
int main()
{
    freopen("salesman.in","r",stdin);
    freopen("salesman.out","w",stdout);
    int t;in(t);
    int y;
    while(t--)
    {
    int n;in(n);
    int minn=1010,maxx=-1;
    for(int i=1;i<=n;i++)in(y),minn=min(minn,y),maxx=max(maxx,y);
    cout<<maxx-minn<<endl;
    }
    return 0;
}

T3

Description:

有两个数组 A,B，大小均为 N。请在 A 中选择一个数 x，B 中选择一个数 y，使得 gcd(x,y) 最大；如果有多组数 gcd 相同，找出 x+y 最大的。

题解：

处理A,B数组的所有约数与此约数的最大原数，枚举即可

处理约数方法：

（1）考试时方法：$O(n*\sqrt{n})$，暴力枚举每个数的所有因数

然而考试时复制后忘把visa改成visb。。

而且这种方法只能得52分（最慢的点2.5秒）

（2）AC代码：枚举因子与倍数，判断倍数是否存在（O($n*\log n$)）

$O(n*\sqrt{n})$ TLE代码：

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<ctime>
#include<vector>
#include<queue>
#include<algorithm>
#include<string>
#include<sstream>
#include<cctype>
#include<cmath>
#include<iomanip>
#include<map>
#include<stack>
#include<set>
#include<functional>
#define in(x) x=read()
#define qr read()
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
inline int read()
{
    char ch=' ';
    int f=1,x=0;
    while(!isdigit(ch)){ch=getchar();if(ch=='-')f*=-1;}
    while(isdigit(ch)){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();}
    return f*x;
}
int a[5000010],b[5000010],pp1[5000010]={0},pp2[5000010]={0};
int vis1[5000010]={0},vis2[5000010]={0},nn1[5000010]={0},nn2[5000010]={0};
int main()
{
    freopen("gcd.in","r",stdin);
    freopen("gcd.out","w",stdout);
    int n;
    in(n);
    for(int i=1;i<=n;i++)in(a[i]);
    for(int i=1;i<=n;i++)in(b[i]);
    pp1[1]=pp2[1]=1;
    for(register int i=1;i<=n;i++)
    {
        int t=sqrt(a[i]);
        for(register int j=1;j<=t;j++)
        {
            if(a[i]%j==0)pp1[j]=pp1[a[i]/j]=1,nn1[j]=max(nn1[j],a[i]),nn1[a[i]/j]=max(nn1[a[i]/j],a[i]);
        }
    }
    for(register int i=1;i<=n;i++)
    {
        int t=sqrt(b[i]);
        for(register int j=1;j<=t;j++)
        {
            if(b[i]%j==0)pp2[j]=pp2[b[i]/j]=1,nn2[j]=max(nn2[j],b[i]),nn2[b[i]/j]=max(nn2[b[i]/j],b[i]);
        }
    }
    int ans;
    for(int i=1000000;i>=1;i--)
    {
        if(pp1[i]&&pp2[i])
        {
            cout<<nn1[i]+nn2[i];
            return 0;
        }
    }
    return 0;
}

std:

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<ctime>
#include<vector>
#include<queue>
#include<algorithm>
#include<string>
#include<sstream>
#include<cctype>
#include<cmath>
#include<iomanip>
#include<map>
#include<stack>
#include<set>
#include<functional>
#define in(x) x=read()
#define qr read()
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
inline int read()
{
    char ch=' ';
    int f=1,x=0;
    while(!isdigit(ch)){ch=getchar();if(ch=='-')f*=-1;}
    while(isdigit(ch)){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();}
    return f*x;
}
int a[5000010],b[5000010],pp1[5000010]={0},pp2[5000010]={0},t[1000010]={0};
int vis1[5000010]={0},vis2[5000010]={0},nn1[5000010]={0},nn2[5000010]={0};
int main()
{
    freopen("gcd.in","r",stdin);
    freopen("gcd.out","w",stdout);
    int n;
    in(n);
    for(int i=1;i<=n;i++)in(a[i]),t[a[i]]++;
    for(int i=1;i<=n;i++)in(b[i]);
    for(int i=1;i<=1000000;i++)
    {
        for(int j=i;j<=1000000;j+=i)
        {
            if(t[j])
            {
                pp1[i]=1;
                nn1[i]=max(nn1[i],j);
            }
        }
    }
    for(int i=1;i<=n;i++)t[a[i]]--,t[b[i]]++;
    for(int i=1;i<=1000000;i++)
    {
        for(int j=i;j<=1000000;j+=i)
        {
            if(t[j])
            {
                pp2[i]=1;
                nn2[i]=max(nn2[i],j);
            }
        }
    }
    for(int i=1000000;i>=1;i--)
    {
        if(pp1[i]&&pp2[i])
        {
            cout<<nn1[i]+nn2[i];
            return 0;
        }
    }
    return 0;
}

T4

Description:

蓝月商场有 n 件宝贝，每件宝贝有两个属性：价钱 price 和品牌 brand。其中 brand 是 1-5 之间某个整数。每件宝贝价钱两两不同。 贪玩蓝月有 Q 个代言人，每个代言人拍完戏之后，希望能从蓝月商场免费顺走一样宝贝。但是每个代言人有自己的喜好，例如古天乐只喜欢品牌 1，陈小春喜欢品牌 1 或品牌 2，渣渣辉喜欢品牌 3 和 5……具体来说，代言人会有 d 个喜欢的品牌（1 <= d <= 5），同时他最喜欢这些品牌中，价钱第 k 便宜的宝贝。

题解：

（考试时直接打了暴力）

预处理b[i][j]表示价格前i的物品中第j品牌有多少，询问时二分位置

std：

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<ctime>
#include<vector>
#include<queue>
#include<algorithm>
#include<string>
#include<sstream>
#include<cctype>
#include<cmath>
#include<iomanip>
#include<map>
#include<stack>
#include<set>
#include<functional>
#define in(x) x=read()
#define qr read()
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
inline int read()
{
    char ch=' ';
    int f=1,x=0;
    while(!isdigit(ch)){ch=getchar();if(ch=='-')f*=-1;}
    while(isdigit(ch)){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();}
    return f*x;
}
struct ee
{
    int t;
    int p;
}a[500010];
bool cmp(ee a1,ee a2)
{
    return a1.p<a2.p;
}
int p[500010],e[500010],b[500010][6]={0},now=0,d;
int check(int x)
{
    int ans=0;
    for(int i=1;i<=d;i++)
    {
//        printf("b[%d][%d]=%d\n",x,e[i],b[x][e[i]]);
        ans+=b[x][e[i]];
    }
    return ans;
}
int main()
{
    freopen("purchase.in","r",stdin);
    freopen("purchase.out","w",stdout);
    int n;in(n);
    for(int i=1;i<=n;i++)in(a[i].t);
    for(int i=1;i<=n;i++)in(a[i].p);
    sort(a+1,a+1+n,cmp);
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=5;j++)b[i][j]=b[i-1][j];
        b[i][a[i].t]++;
    }
    int q;in(q);
    while(q--)
    {
        in(d);
        for(int i=1;i<=d;i++)in(e[i]);
        int k;in(k);
        if(check(n)<k)
        {
            cout<<-1<<endl;
        }
        else
        {
            int l=1,r=n;
            while(l<r)
            {
                int mid=(l+r)>>1;
                if(check(mid)>=k)r=mid;
                else l=mid+1;
            }
            cout<<a[l].p<<endl;
        }
    }
    return 0;
}

T5

Description:

有两个仅包含小写字母的字符串 x,y， 长度分别为 n,m。 你需要修改 x 串中某些字符， 是的新的 x 串和 y 串的最长公共子序列长度至少为 k。 我们将’a’…’z’对应成 0…25， 修改两个字符付出的代价，为它们对应的数的 xor 值。 比如 说，将’a’修改成’z’代价为 0 xor 25=25。 请问最少付出多少代价，使得新的 x 串和 y 串的 LCS 大于等于 k。

题解：

“非常基础”的dp？

定义f[i][j][k]表示使x前i字符，y前j字符的LCS等于k需付出代价

边界：

k=0：为0

i=0,j!=0或j=0,i!=0：为inf

转移：

$f[i][j][k]=min(f[i][j-1][k],min(f[i-1][j][k],f[i-1][j-1][k-1]+a[i][j]))$（a：代价）

std:

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<ctime>
#include<vector>
#include<queue>
#include<algorithm>
#include<string>
#include<sstream>
#include<cctype>
#include<cmath>
#include<iomanip>
#include<map>
#include<stack>
#include<set>
#include<functional>
#define in(x) x=read()
#define qr read()
#define inf 2000000000 
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
inline int read()
{
    char ch=' ';
    int f=1,x=0;
    while(!isdigit(ch)){ch=getchar();if(ch=='-')f*=-1;}
    while(isdigit(ch)){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();}
    return f*x;
}
string s1,s2;
int dp[400][400][400]={0};
int a[30][30]={0};
int work(int n,int m,int k)
{
    if(!k)return 0;
    if(m<k||n<k)return inf;
    if(dp[n][m][k]!=-1)return dp[n][m][k];
    dp[n][m][k]=min(work(n-1,m,k),min(work(n,m-1,k),work(n-1,m-1,k-1)+a[s1[n-1]-'a'][s2[m-1]-'a']));
    return dp[n][m][k];
}
int main()
{
    freopen("string.in","r",stdin);
    freopen("string.out","w",stdout);
    int n=qr,m=qr,k=qr;
    memset(dp,-1,sizeof(dp));
    cin>>s1>>s2;
    for(int i=0;i<=25;i++)
    {
        for(int j=0;j<=25;j++)
        {
            a[i][j]=i^j;
        }
    }
    int ans=work(n,m,k);
    if(ans>=2000000000)cout<<-1;
    else cout<<ans;
    return 0;
}

T6

Description:

给出长度为 n 的序列 A1,A2,…,An。进行 m 次操作，有三种类型： 1、 给出 l,r，将区间[l,r]的 Ai 都加一。 2、 给出 l,r，询问区间[l,r]的 Ai!的和，对 10^9 取模。 3、 给出 I,v，将 Ai 单点修改为 v。

题解：

（考试时依然打了暴力）

用线段树维护最小值与阶乘，支持单点修改，区间求和

区间修改：发现当x>=40时，

$x! mod 10^9=0$!!

通过最小值找到所有小于40的数后单点修改

每个数最多被修改40次，所以总复杂度为$O((n+q)*50*log n)$

std：

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<ctime>
#include<vector>
#include<queue>
#include<algorithm>
#include<string>
#include<sstream>
#include<cctype>
#include<cmath>
#include<iomanip>
#include<map>
#include<stack>
#include<set>
#include<functional>
#define mod 1000000000
#define in(x) x=read()
#define qr read()
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
inline int read()
{
    char ch=' ';
    int f=1,x=0;
    while(!isdigit(ch)){ch=getchar();if(ch=='-')f*=-1;}
    while(isdigit(ch)){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();}
    return f*x;
}
ll a[2000010],c[2000010],f[2000010];
int n;
ll fac[50]={0,1,2,6,24,120,720,5040,40320,362880,3628800,39916800,479001600,227020800,178291200,674368000,789888000,428096000,705728000,408832000,176640000,709440000,607680000,976640000,439360000,984000000,584000000,768000000,504000000,616000000,480000000,880000000,160000000,280000000,520000000,200000000,200000000,400000000,200000000,800000000};
void pushup(int x)
{
    c[x]=min(c[x<<1],c[x<<1|1]);
    f[x]=f[x<<1]+f[x<<1|1]%mod;
}
void build(int l,int r,int x)
{
    if(l==r)
    {
        c[x]=a[l];
        if(a[l]>=40)f[x]=0;
        else f[x]=fac[a[l]];
        return;
    }
    int mid=(l+r)>>1;
    build(l,mid,x<<1);
    build(mid+1,r,x<<1|1);
    pushup(x);
}
void update1(int pl,int pr,int cc,int v,int x)
{
    if(pl==pr)
    {
        c[x]=v;
        if(v>=40)f[x]=0;
        else f[x]=fac[v];
        return;
    }
    int mid=(pl+pr)>>1;
    if(mid>=cc)update1(pl,mid,cc,v,x<<1);
    else update1(mid+1,pr,cc,v,x<<1|1);
    pushup(x);
}
//int query1(int l,int r,int v,int x)
//{
//    if(l==r)return c[x];
//    int mid=(l+r)>>1;
//    if(mid>=v)return query1(l,mid,v,x<<1);
//    else return query1(mid+1,r,v,x<<1|1);
//}
void update2(int l,int r,int pl,int pr,int x)
{
    if(pl==pr)
    {
//        update1(l,r,l,c[x]+1,x);
        c[x]++;
        if(c[x]>=40)f[x]=0;
        else f[x]=fac[c[x]];
        return;
    }
    int mid=(pl+pr)>>1;
    if(c[x<<1]<40&&l<=mid)
    {
        update2(l,r,pl,mid,x<<1);
    }
    if(c[x<<1|1]<40&&mid<r)
    {
        update2(l,r,mid+1,pr,x<<1|1);
    }
    pushup(x);
}
ll query2(int l,int r,int pl,int pr,int x)
{
    if(l<=pl&&pr<=r)return f[x]%mod;
    int mid=(pl+pr)>>1;
    ll ans=0;
    if(l<=mid)ans+=query2(l,r,pl,mid,x<<1);
    if(mid<r)ans+=query2(l,r,mid+1,pr,x<<1|1);
    return ans%mod;
}
int main()
{
    freopen("array.in","r",stdin);
    freopen("array.out","w",stdout);
    int m;
    in(n),in(m);
    for(int i=1;i<=n;i++)in(a[i]);
    build(1,n,1);
    for(int i=1;i<=m;i++)
    {
        int op;
        in(op);
        if(op==1)
        {
            int l,r;
            in(l),in(r);
            update2(l,r,1,n,1);
        }
        else if(op==2)
        {
            int l,r;
            in(l),in(r);
            cout<<query2(l,r,1,n,1)<<endl;
        }
        else
        {
            int l,v;
            in(l),in(v);
            update1(1,n,l,v,1);
        }
    }
    return 0;
}