首页 > 其他 > 详细

集训队日常训练20181117 DIV2

时间:2018-11-18 12:00:50      阅读:311      评论:0      收藏:0      [点我收藏+]

大佬们一顿操作猛如虎,拼命AC强啊

4262: 区间异或 技术分享图片

Time Limit(Common/Java):1000MS/3000MS     Memory Limit:65536KByte
Total Submit: 139            Accepted:58

Description

 

zzd通过艰苦的学习,终于领悟了异或(^)的计算方法.

可是现在他面前出现了一道难题,zzd陷入了迷茫之中…你能帮帮他么?

给出一个长为N的序列{A1, A2, A3, ... , An}。求解区间[L,R]的异或和 A(L)^A(L+1)^ ... ^ A(R)。

 

 

Input

 

题目数据有多组,请读入至文件结束。

每组第一行给出两个整数N,M(1<=N<=1000000, 1<=M<=100000)。N代表序列的长度,M代表询问数。

接下来有N行,每行有一个整数A(0<=A<=32767),代表序列的每一项。

接下来有M行,每行有两个整数L、R(1<=L<=R<=N),代表询问的区间。

 

Output

 

对于每组询问[L,R],请输出[L,R]区间的异或和。

 

Sample Input

5 3
1 2 3 4 5
1 1
1 5
2 4

Sample Output

1
1
5

Hint

大量数据,请使用scanf、printf输入输出


看起来好像是个O(q*n)或者O(n*n)的算法,但是不是的啊,异或有个性质,相同两个数异或为0,所以可以借助前缀和去优化

#include <stdio.h>
int a[1000005],b[1000005];
int main()
{
    int m,n;
    while(~scanf("%d%d",&n,&m))
    {
        for(int i=1; i<=n; i++)
            scanf("%d",&a[i]),b[i]=a[i]^b[i-1];
        while(m--)
        {
            int l,r;
            scanf("%d%d",&l,&r);
            int f=b[r];//1到r的异或值
            for(int i=1; i<l; i++)f^=a[i];//消除1到l-1的影响
            printf("%d\n",f);
        }
    }
    return 0;
}

所以我sb了,后面的不直接是存着的。直接b[r]^b[l-1]就完事

那么如果不是^,是gcd或者|或者&呢,可以用二分+ST表或者利用这个递减很快的性质去解决

技术分享图片
//https://vjudge.net/problem/Gym-101532A
#include<bits/stdc++.h>
using namespace std;
int fun(int x,int y)
{
    return x&y;
}
const int N=1e5+5;
int n,a[N],l[N],v[N];
int main()
{
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    int T;
    cin>>T;
    while(T--)
    {
        cin>>n;
        for(int i=1; i<=n; i++)cin>>a[i];
        long long ans=0;
        for(int i=1,j; i<=n; i++)
            for(v[i]=a[i],j=l[i]=i; j; j=l[j]-1)
            {
                v[j]=fun(v[j],a[i]);
                while(l[j]>1&&fun(a[i],v[l[j]-1])==fun(a[i],v[j]))l[j]=l[l[j]-1];
                ans+=v[j]*1LL*(j-l[j]+1);
            }
        cout<<ans<<"\n";
    }
    return 0;
}
Claris的niubi模板

1535: 找规律填数字 技术分享图片

Time Limit(Common/Java):1000MS/10000MS     Memory Limit:65536KByte
Total Submit: 1314            Accepted:583

Description

 

小瑜还在读幼儿园呢,现在的小孩子正够可怜的......
这不,老师给孩子们布置了一道连很多大人都不会的数学题目。且看: 
给你一组有规律序列的前面5个整数,请你给出它后面跟着的5个整数,如:1,2,3,4,5,___,___,___,__,___。这是个等差数列, 后面应该是6,7,8,9,10,这倒简单。但现在老师告诉孩子们这串序列有可能是等差数列,等比数列或者是斐波那契数列。亲爱的,你能帮小瑜完成这个题目吗?

 

Input

输入有多组数据,每组数据占一行,有5个数字组成,每个数字之间隔一个空格,当5个数字都为0时输入结束。

Output

每组测试数据对应一个输出为这串数列的后面5个数字,每个数字之间隔一个空格。当输入的5个数字都为0时不用输出结果。

Sample Input

1 2 3 4 5
1 2 4 8 16
1 2 3 5 8
0 0 0 0 0

Sample Output

6 7 8 9 10
32 64 128 256 512
13 21 34 55 89

Hint

用int可以满足精度
读懂题意分情况写一下吧,我代码找不到了
solution from addition  
#include <iostream>
#include <cstdio>
using namespace std;

int main()
{
    int a[15];
    while(scanf("%d%d%d%d%d",&a[0],&a[1],&a[2],&a[3],&a[4]),a[0]||a[1]||a[2]||a[3]||a[4])
    {
        int flag=0,k;
        if(a[4]-a[3]==a[3]-a[2])
        {
            flag=1;
            k=a[4]-a[3];
            for(int i=5; i<10; i++)
            {
                a[i]=a[i-1]+k;
            }
        }
        else if(a[4]*a[2]==a[3]*a[3])
        {
            flag=2;
            k=a[4]/a[3];
            for(int i=5; i<10; i++)
            {
                a[i]=a[i-1]*k;
            }
        }
        else
        {
            flag=3;
            for(int i=5; i<10; i++)
            {
                a[i]=a[i-1]+a[i-2];
            }
        }
        for(int i=5; i<10; i++)
        {
            if(i!=5)printf(" ");
            printf("%d",a[i]);
        }
        printf("\n");
    }
    return 0;
}

1438: 螺旋形 技术分享图片

Time Limit(Common/Java):1000MS/3000MS     Memory Limit:65536KByte
Total Submit: 576            Accepted:183

Description

输入n,(0 < n <= 20),建立n*n二维数组,按照下图规则把1~n*n个数放在n*n二维数组中,然后按行优先顺序输出。

1 2 3 4 12 13 14 5 11 16 15 6 10 9 8 7

 

Input

输入数据由多个测试实例组成,每个测试实例占一行,包括一个整数n(0<n<=20),n的含义如题目中描述。n=0表示输入数据的结束,不做处理。

Output

对于每个测试实例,输出该二维数组,该二维数组按行输出,行中数据之间有一个空格,每个数据占3个字符位置,左对齐,注意每行的最后一个元素后面没有空格,每个测试例子后面有空行。

Sample Input

1
2
3
0

Sample Output

 

1

1 2
4 3

1 2 3
8 9 4
7 6 5

Source

TOJ

真实模拟题,不过我这个写法好像有点过于强了,应该是螺旋矩阵的通解

 

#include <stdio.h>
int get(int x,int y,int n)
{
    if(x<=y)
    {
        int k=(x<n-1-y)?x:n-1-y;
        return 4*k*(n-k)+1+(x+y-k*2);
    }
    int k=(y<n-1-x)?y:n-1-x;
    k=k+1;
    return 4*k*(n-k)+1-(x+y-(k-1)*2);
}
int main()
{
    int n,i,j;
    while(scanf("%d",&n)!=EOF,n)
    {
        int a[21][21];
        for(i=0; i<n; i++)
            for(j=0; j<n; j++)
                a[i][j]=get(i,j,n);
        for(i=0; i<n; i++)
        {
            printf("%-3d",a[i][0]);
            for(j=1; j<n; j++)
                printf(" %-3d",a[i][j]);
            printf("\n");
        }
        printf("\n");
    }
    return 0;
}

模拟的代码,不够我个人喜欢while,稍微好控制些

solution from Nayo 

#include<iostream>
#include<stdio.h>
using namespace std;
int main()
{
    int t,a[21][21]= {0};
    while(cin>>t,t)
    {
        int num=1;
        for(int n=0; n<=t/2; n++)
        {
            for(int j=n; j<=t-n-1; j++)
            {
                a[n][j]=num++;
            }
            for(int i=n+1; i<t-n-1; i++)
            {
                a[i][t-n-1]=num++;
            }
            for(int j=t-n-1; j>n; j--)
            {
                a[t-n-1][j]=num++;
            }
            for(int i=t-n-1; i>n; i--)
            {
                a[i][n]=num++;
            }
        }
        for(int o=0; o<t; o++)
        {
            for(int p=0; p<t; p++)
            {
                if(p!=t-1)
                    printf("%-3d ",a[o][p]);
                else
                    printf("%-3d",a[o][p]);
            }
            cout<<endl;
        }
        cout<<endl;
    }
}

4604: 搞笑版费马大定理 技术分享图片

Time Limit(Common/Java):1000MS/3000MS     Memory Limit:65536KByte
Total Submit: 238            Accepted:135

Description

 

费马大定理:当n>2时,不定方程an+bn=cn没有正整数解。比如a3+b3=c3没有正整数解。为了活跃气氛,我们不妨来个搞笑版:把方程改成a3+b3=c3,这样就有解了,比如a=4, b=9, c=79时43+93=793。
输入两个整数x, y, 求满足x<=a,b,c<=y的整数解的个数。

 

Input

 

输入最多包含10组数据。每组数据包含两个整数x, y(1<=x,y<=108)。

 

Output

 

对于每组数据,输出解的个数。

 

Sample Input

1 10
1 20
123 456789

Sample Output

 

Case 1: 0
Case 2: 2
Case 3: 16

题目都是骗人的,暴力就完事

#include <stdio.h>
int main()
{
    int x,y,a,b,c,num,k=1;
    while(scanf("%d%d",&x,&y)!=EOF)
    {
        num=0;
        for(a=x; a<=1000&&a<=y; a++)
            for(b=x; b<=1000&&b<=y; b++)
            {
                int s=a*a*a+b*b*b;
                if(s%10!=3) continue;
                c=s/10;
                if(c>=x&&c<=y) num++;
            }
        printf("Case %d: %d\n",k++,num);
    }
    return 0;
}

4638: 单位转换 技术分享图片

Time Limit(Common/Java):1000MS/3000MS     Memory Limit:65536KByte
Total Submit: 633            Accepted:428

Description

 

BobLee最近在复习考研,在复习计算机组成原理的时候,遇到了一个问题。就是在计算机存储里面的单位转换。我们都知道1MB=1024KB,1KB=1024B,1B=8bit,他在做题的时候经常会遇到格式各样的,比如多少MB,KB,B什么的,但是都要转换为bit,题目做的太多他都迷茫了,现在需要你通过程序来帮他解决这个问题。

 

Input

 

输入为多行未化简的数据,如xMB,xKB,xB,xbit,(1<=x<=50)

 

Output

 

输出为换算过后的数据,ybit

 

Sample Input

1MB
1KB
1B
1bit

Sample Output

 

8388608bit
8192bit
8bit
1bit

简单模拟,请注意细节

#include <stdio.h>
#include <string.h>
int main()
{
    int n;
    char s[3];
    while(~scanf("%d%s",&n,s))
    {
        if(strcmp(s,"B")==0)
            n=n*8;
        else if(strcmp(s,"KB")==0)
            n=n*8*1024;
        else if(strcmp(s,"MB")==0)
            n=n*8*1024*1024;
        printf("%dbit\n",n);
    }
    return 0;
}

4650: 调皮的萌萌 技术分享图片

Time Limit(Common/Java):1000MS/3000MS     Memory Limit:65536KByte
Total Submit: 218            Accepted:89

Description

 

调皮的萌萌喜欢在传输的数据上做改动,具体方法如下:
在一串由0、1组成的数据中,执行任意次数(可能为0次)的如下的操作:
任意选取相邻的两位a、b,把这两位变成a or b、a xor b。
比如:10可变为11,11可变为01或10.
给你两个01串s1、s2,请你s2是否有可能是萌萌用s1改动的来的数据。

 

Input

 

输入数据包含多组测试数据。
每组数据包含两行0、1组成的字符串s1、s2。

 

Output

 

对于每组数据,如果s2可由s1改动而来,输出“YES”,否则输出“NO”。

 

Sample Input

11
10
1
01
000
101

Sample Output

YES
NO
NO

找找规律,按题意贪心吧,不过能证明是对的,CF DIV2B往往是这种类型

#include <stdio.h>
#include <string.h>
int main()
{
    char s1[1000],s2[1000];
    while(~scanf("%s",s1))
    {
        int f,t,i;
        f=0;
        t=0;
        int l1=strlen(s1);
        scanf("%s",s2);
        int l2=strlen(s2);
        for(i=0; s1[i]!=\0; i++)
            if(s1[i]==1)
            {
                f++;
                break;
            }
        for(i=0; s2[i]!=\0; i++)
            if(s2[i]==1)
            {
                t++;
                break;
            }
        if(l1==l2&&f&&t)
            printf("YES\n");
        else if(l1==l2&&!f&&!t)
            printf("YES\n");
        else
            printf("NO\n");
    }

    return 0;
}

3360: 回文素数 技术分享图片

Time Limit(Common/Java):1000MS/3000MS     Memory Limit:65536KByte
Total Submit: 409            Accepted:95

Description

 

151 是一个回文素数,因为它既是一个素数又是回文数(回文数是指一个数 从左到右 和 从右到左 读的结果一样).

试写一个程序计算区间 [ a , b ] 内的所有回文素数.( 5 <= a < b <= 100,000,000 )

 

Input

只有一组测试数据: a b

Output

输出[a,b]区间内所有回文素数,每个数占一行

Sample Input

 5 500

Sample Output

5
7
11
101
131
151
181
191
313
353
373
383

 

集训队日常训练20181117 DIV2

原文:https://www.cnblogs.com/BobHuang/p/9977405.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!