UOJ Logo zmwang的博客

博客

Day5

2018-04-07 22:07:33 By zmwang

今天真爆炸。。

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;
}

评论

zhengruioi
多注意细节处理，每次提交前花点时间检查一下容易翻车的位置。。。
  • 2018-04-08 11:21:36

中文 English

Server time: 2024-05-07 03:26:30   |   浙ICP备17047493号