欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

劳动节的玩具。。

程序员文章站 2022-04-19 21:40:28
第一题 987654321 problem 水题,打个表找个规律,一瞬间就好了。。 #include #include using namespace std; in...

第一题 987654321 problem
水题,打个表找个规律,一瞬间就好了。。

#include
#include
using namespace std;
int main()
{
    /*for(long long i=1000;i<=0x7ffffffff;i++)
    {
        if((i*i)%1000000000==987654321)
        {
            cout<>n;
    if(n<=8)
    {
        cout<<'0'<

第二题 self-numbers 2
这道题蛮好的。。 一开始忽略了内存大小,在用哈希表做(把所有不符合的存入哈希表中),在第5组的时候出现了pe。。 pe。。 然后各种调试都pe。。 搜题解, 发现原来这题的位置不是从小到大的,而且可能有重复的位置,那就sort2遍好了。。 第5组爆内存。。 哈希值得问题吧。。 第6组超时。。
然后就知道了,这道题用哈希很膨胀。。

于是 看题解, 他们把这个方式叫做滚动数组。。 说白了,就是数组的重复使用,机智。

他们是这么做的:1。比如,当前的数字是 13 ,那么13 可以推出 13+1+3=17 不是,于是 我们知道了 13 后面的第 4 个数字不可取;
2。当前数子是999 那么就是他后面的 第 27 个数字不可取。
3。最大的数字是10的7次, 那么他的影响力最多是 7*9=63。 7是位数,9是每位的最大数。于是就可以开一个长度为 126 的数组,以 63 为更新节(最大影响力是63),滚来滚去(f1记录在63中的(我的这一波),f2记录我这一波(f1)对下一波的影响力);
这样既省内存又方便。。机智。。

#include
#include
#include
#include
#include
using namespace std;
struct shu
{
    int v;
    int loc;
}who[5001];
int ans[5001];
bool f1[63],f2[63];
int cmp(shu a,shu b)
{
    return a.v

第三题 boxes

这道题一开始很自信,认为自己可以o(1)解决,失败了。。
但是,再想想一定可以o(1)解决的。。

这里给出模拟做法,因为有 *2 这个东西,而且数据最大才2的31次,最差的情况就是 31*31 因为每次移动31,运行了31组(log2 2的31次)。。(当然,这不是最差的,因为两者一定会逐渐接近)但是 900 这样的时间够了。。 实验证明50都可以。。数据水。。

#include
#include
using namespace std;
int main()
{
    int a,b;
    cin>>a>>b;
    int step=0;
    int flag=1;
    while(a&&b)
    {
        if(a50)//数据水。。。
        {
            flag=0;
            break;
        }
    }
    if(!flag)
    {
        cout<<"-1"<

第四题 palindrome pairs

这个东西,以我目前的水平,还不能统一字符长度为1的情况。。
记录一下头尾的所有就好了。。

#include
#include
#include
using namespace std;
char a[2001];
int p[2001];
int q[2001];
int main()
{
    scanf("%s",a);
    int len=strlen(a);
    for(int i=0;i=0&&a[id-to]==a[id+to])
        {
            p[id-to]++;
            q[id+to]++;
            to++;
        }
        id=i;
        to=0;
        while(id-to-1>=0&&id+to

e 模拟大法好。。 先找到最近的一段,然后就可以玩了。。

#include
#include
#include
#include
using namespace std;
string test;
int main()
{

    int n,k;
    cin>>n>>k;
    cin>>test;
    int mode;//不同模式,不同标准。。
    if(k==n)
    {
        mode=1;
    }
    else if(k==1)
    {
        mode=2;
    }
    else if(k>n/2)
    {
        while(k!=n)
        {
            cout<<"right"<=0;i--)
        {

            cout<<"print "<

f 还是模拟,排序一下就好了。。

#include
#include
#include
using namespace std;
struct sb
{
    int x;
    int y;
}boom[100010];
int cmp(sb a,sb b)
{
    if(abs(a.y)==abs(b.y))
        return abs(a.x)0)
        {
            printf("1 %d r\n",boom[i].x);
            mode1=1;
        }
        else if(boom[i].x<0)
        {
            printf("1 %d l\n",abs(boom[i].x));
            mode1=2;
        }
        if(boom[i].y>0)
        {
            printf("1 %d u\n",boom[i].y);
            mode2=1;
        }
        else if(boom[i].y<0)
        {
            printf("1 %d d\n",abs(boom[i].y));
            mode2=2;
        }
        printf("2\n");
        if(mode1==1)
        {
            printf("1 %d l\n",boom[i].x);
        }
        else if(mode1==2)
        {
            printf("1 %d r\n",abs(boom[i].x));
        }
        if(mode2==1)
        {
            printf("1 %d d\n",boom[i].y);
        }
        else if(mode2==2)
        {
            printf("1 %d u\n",abs(boom[i].y));
        }
        printf("3\n");
    }
    return 0;
}

g题 ,这道题 又是模拟,我发现了,在cf里面即使pe 了都没问题。。
不过我还是很认真的输出了。。
这道题运气好碰巧凑对了。。
值得注意的是下界的计算,反正我因为这个wa2发之后直接偷懒了。。

#include
#include
#include
#include
#include
using namespace std;
struct sb
{
    int x;
    int y;
    char d;
}node[1010];
int wa[2010][1010];
int main()
{
    int n;
    cin>>n;
    int test;
    node[0].x=0;
    node[0].y=0;
    int max1=-0x3f3f3f3f;
    int max2=-0x3f3f3f3f;
    memset(wa,0,sizeof(wa));
    for(int i=1;i<=n;i++)
    {
        cin>>test;
        node[i].x=node[i-1].x+test;
        if(i&1)
        {
            node[i].y=node[i-1].y+test;
        }
        else
        {
            node[i].y=node[i-1].y-test;
        }
        max1=max(max1,node[i].y);
        if(node[i-1].y

h wall painting
异或 这题不错,既然要算的是每一个组合后数的和(sum),
1。sum=第一位+第二位+第三位。。。第一位,第二位,第三位。。 他们之间是无关的。
2。这道题算的是所有东西的和,所以重复也没关系,用不到容斥,话说早上和友人讨论的32n微软面试题 应该容斥做是可行的吧。。(嘘)。。
这样就是一道简单的排列组合题目了。。
用int wa了。。 那就开 long long 吧

#include
#include
#include
using namespace std;
const long long mod=1000003;
long long a[10010];
long long wei[64];
long long c[1010][1010];
void build()
{
    for(long long i=0;i<=1001;i++)
    {
        c[i][0]=c[i][i]=1;
        for(long long j=1;j>1;
                cnt++;
            }
            maxlen=max(maxlen,cnt);
        }
        for(long long i=1;i<=n;i++)
        {
            long long ans=0;
            for(long long j=0;j

i railway tickets 这道题太有趣了,交了11次。。 因为终点可以在起点前面。。

简单的dp。。

#include
#include
#include
using namespace std;
int a[10010];
int way[10010];
int main()
{
    int l1,l2,l3,c1,c2,c3;
    int n;
    int s,e;
    scanf("%d%d%d%d%d%d",&l1,&l2,&l3,&c1,&c2,&c3);
    scanf("%d",&n);
    scanf("%d%d",&s,&e);
    if(s>e)
        swap(s,e);
    for(int i=2;i<=n;i++)
    {
        scanf("%d",&a[i]);
    }
    memset(way,0x3f3f3f3f,sizeof(way));
    way[s]=0;
    for(int i=s+1;i<=e;i++)
    {
        int j=i-1;
        int dis=a[i]-a[j];
        while(dis<=l1&&j>=s)
        {
            way[i]=min(way[i],way[j]+c1);
            j--;
            dis=a[i]-a[j];
        }
        j=i-1;
        dis=a[i]-a[j];
        while(dis<=l2&&j>=s)
        {
            way[i]=min(way[i],way[j]+c2);
            j--;
            dis=a[i]-a[j];
        }
        j=i-1;
        dis=a[i]-a[j];
        while(dis<=l3&&j>=s)
        {
            way[i]=min(way[i],way[j]+c3);
            j--;
            dis=a[i]-a[j];
        }
    }
    printf("%d\n",way[e]);
    return 0;
}

j ministry 这道题2刷的时候居然爆内存了。。 哇擦,我第一遍做的时候怎么可以那么机智,用数字表示如何走。。用字母果断爆炸了。。

一开始想到了b题的滚动数组,因为走到下一层,上一层就没用了。
原来这就是dp里面套dp,先左扫一遍,然后右边扫一遍。。 因为某个点,到底是从左走还是从右走,一切都是趋向于最小,所以先左先右没关系。。

#include
#include
#include
using namespace std;
int a[501];
int time[501];
int way[101][501];
int n;
void print(int who,int len)
{
    if(len==0)
        return ;
    else if(way[len][who]==1)
    {
        print(who,len-1);
        printf("%d",who);
        if(len==n)
        {
            printf("\n");
        }
        else
            printf(" ");
    }
    else if(way[len][who]==2)
    {
        print(who-1,len);
        printf("%d ",who);
    }
    else
    {
        print(who+1,len);
        printf("%d ",who);
    }
}
int main()
{
    int m;
    scanf("%d%d",&n,&m);
    memset(time,0,sizeof(time));
    for(int j=1;j<=n;j++)
    {
        for(int i=1;i<=m;i++)
        {
            scanf("%d",&a[i]);
        }
        for(int i=1;i<=m;i++)
        {
            time[i]=time[i]+a[i];
            way[j][i]=1;
        }
        for(int i=2;i<=m;i++)
        {
            if(time[i-1]+a[i]=1;i--)
        {
            if(time[i+1]+a[i]

k 题,,放一放,放一放,找规律,吃不消。。
现在可以了,根据我的手动模拟,首先来看“。。。。”这种情况,很明显2个点,然后看“。。。。。”这种情况,3个点。
于是 像这种1条的得出规律n/2+if(奇数)则1;
2*1的时候一个点 2*2 的时候1个点 2*3 的时候,我们找到规律,就是可以消去一条边 边成1*3的情况。。2*4 的情况我们可以照样消去3个点。。于是3就是关键。。这样我们就可以尽可能的去消除3 题目也就是水题了。。

#include
#include
using namespace std;
int main()
{
    int n,m;
    while(scanf("%d%d",&n,&m)==2)
    {
        if(n>m)
            swap(n,m);
        if(n==1||n==2) //2可以转化为1,1的时候没有符合要求的1*3
            printf("%d\n",(m+1)/2);
        else//尽量用1*3消除
        {
            n=n%3;
            m=m%3;
            if(n

l gentlemen
身为大绅士的我,自然要华丽的做出啦。。。
感觉自己比网上题解写的好多了。。不过方法一样
用一个pre记录路径,dp来看有几条路。。并不用01背包的样子。。(反而觉得用了看不懂了)

#include
#include
#include
using namespace std;
int a[110];
int dp[1000010];
int pre[1000010];
int ans[110];
int main()
{
    int fin;
    scanf("%d",&fin);
    int n;
    scanf("%d",&n);
    memset(dp,0,sizeof(dp));
    memset(pre,-1,sizeof(pre));
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
    }
    dp[0]=1;
    for(int i=1;i<=n;i++)
    {
        for(int j=fin;j>=a[i];j--)
        {
            if(dp[j-a[i]])
            {
                dp[j]=dp[j]+dp[j-a[i]];
                if(pre[j]==-1)
                pre[j]=i;
            }
        }
    }
    if(dp[fin]>1)
    {
        printf("-1\n");
    }
    else if(dp[fin]==0)
    {
        printf("0\n");
    }
    else
    {
        memset(ans,0,sizeof(ans));
        int num=n;
        while(pre[fin]!=-1)
        {
            ans[pre[fin]]=1;
            fin=fin-a[pre[fin]];
            num--;
        }
        for(int i=1;i<=n;i++)
        {
            if(!ans[i])
            {
                num--;
                printf("%d",i);
                if(!num)
                {
                    printf("\n");
                }
                else
                {
                    printf(" ");
                }
            }
        }
    }
    return 0;
}

m broken line 这道题一开始没读清题目意思,觉得是任何图形(奇形怪状),用数学的向量做,然后爆炸啊,写不出来啊,分类太多了。
然后,搜题解,妈呀,人家为何呢么几个等号就出来了呢?原来是方形,方形,方形,一下子水了。。。

#include
#include
#include
#include
using namespace std;
struct sb
{
    long long x1,y1;
    long long x2,y2;
}xian[10010];
struct sb1
{
    long long x;
    long long y;
}vector1,vector2,vector3;
int main()
{
    long long n;
    cin>>n;
    for(long long i=1;i<=n;i++)
    {
        cin>>xian[i].x1>>xian[i].y1>>xian[i].x2>>xian[i].y2;
    }
        long long x,y;
        cin>>x>>y;
        long long ok=1;
        for(long long i=1;i<=n;i++)
        {
            if((xian[i].x1==xian[i].x2&&x==xian[i].x1&&y>=min(xian[i].y1,xian[i].y2)&&y<=max(xian[i].y2,xian[i].y1))||(xian[i].y1==xian[i].y2&&y==xian[i].y1&&x<=max(xian[i].x2,xian[i].x1)&&x>=min(xian[i].x1,xian[i].x2)))
            {
                ok=0;
                cout<<"border"<

n beat
数据小的可怜,dfs一下就好了。。
总算最后一题了。。

#include
#include
#include
#include
using namespace std;
int n;
int flag[20];
int way[20][20];
int ans;
void dfs(int who,int num,int old)
{
    ans=max(num,ans);
    for(int i=0;i=old)
        {
            flag[i]=1;
            dfs(i,num+1,way[who][i]);
            flag[i]=0;
        }
    }
}
int main()
{
    while(scanf("%d",&n)!=eof)
    {
        for(int i=0;i