zcmimi's blog
avatar
zcmimi
2019-02-08 18:15:39
  • 本文总阅读量
A Parity standard input/output1 s, 256 MB Submit Add to favourites img x6385
B Tapestandard input/output1 s, 256 MB Submit Add to favourites img x4448
C Meaningless Operationsstandard input/output1 s, 256 MB Submit Add to favourites img x3704
D Jongmahstandard input/output3 s, 256 MB Submit Add to favourites img x940
E Magic Stonesstandard input/output1 s, 256 MB Submit Add to favourites img x1096

A. Parity

题意:

n = a_1 \cdot b_{k−1} + a_2 \cdot b_{k−2} + … a_{k−1} \cdot b + a_k

给出b,k​、数组a​,判断n​是偶数(even)还是奇数(odd).

题解:

用一个boolf记录到目前是奇数还是偶数

如果a_ib_{k-i}之间有一个是偶数,a_i \cdot b_{k-i}就是偶数

如果i=k就只看a_k就可以了

#include<cstdio>
#define Fur(i,x,y) for(int i=x;i<=y;i++)
using namespace std;
int b,k,x;
int main(){
    scanf("%d%d",&b,&k);
    bool f=0;
    Fur(i,1,k){
        scanf("%d",&x);
        if((k-i!=0&&!(b&1))||!(x&1))continue;
        f^=1;
    }
    printf(f?"odd\n":"even\n");
}

B. Parity

原题

就是输入顺序不一样罢了

贪心取空隙最大的不要就可以了。

#include<cstdio> 
#include<algorithm> 
#define N 100010
using namespace std; 
int m,s,c,ans;
int a[N],C[N];
bool cmp(int x,int y){return x>y;}
int main() { 
    scanf("%d %d %d",&c,&s,&m);
    for(int i=1;i<=c;i++)scanf("%d",&a[i]);
    if(m>c){printf("%d\n",c);return 0;}
    sort(a+1,a+c+1);
    ans=a[c]-a[1]+1;
    for(int i=2;i<=c;i++)C[i-1]=a[i]-a[i-1];
    sort(C+1,C+c,cmp);
    for(int i=1;i<=m-1;i++)ans=ans-C[i]+1;
    printf("%d\n",ans);
} 

C. Meaningless Operations

题意:

输入q,然后输入qa,对于每个a,找到一个b(0<b<a),使 gcd(a\ xor\ b, a\ and\ b) 最大,输出这个最大的gcd

题解:

如果a不是 (1 << k) - 1这种形式,那么总能找到一个b使a\ xor\ b == (1 << k) - 1,而a\ and\ b == 0,这个时候gcd一定最大

如果a(1 << k) - 1,那么因为b不能为0,所以凑不出 (1 << k) - 1,没办法只能暴力了,因为 (1 << k) - 1这样的形式的a也只有24个,所以我们要事先打表,否则应该会超时

#include<cstdio>
#include<map>
using namespace std;
#define N 100011
int n;
map<int,int>mp;
int main(){
mp[3]=1;mp[7]=1;mp[15]=5;mp[31]=1;mp[63]=21;mp[127]=1;mp[255]=85;mp[511]=73;mp[1023]=341;mp[2047]=89;mp[4095]=1365;mp[8191]=1;mp[16383]=5461;mp[32767]=4681;mp[65535]=21845;mp[131071]=1;mp[262143]=87381;mp[524287]=1;mp[1048575]=349525;mp[2097151]=299593;mp[4194303]=1398101;mp[8388607]=178481;mp[16777215]=5592405;mp[33554431]=1082401;
int T,n;scanf("%d",&T);
while(T--){
    scanf("%d",&n);
    if(mp.count(n))printf("%d\n",mp[n]);
    else printf("%d\n",(1<<(int(log2(n))+1))-1);
}
}

D. Jongmah

题意:

你有n(10^6)个数字,范围[1, m(10^6)],你可以选择其中的三个数字构成一个三元组,但是这三个数字必须是连续的或者相同的,每个数字只能用一次,问这n个数字最多构成多少个三元组?

题解:

看到n那么大,以为是贪心,其实是dp

分析:如果有3个三元组(i,i+1,i+2)那么肯定可以拆成3个三元组(i,i,i),(i+1,i+1,i+1),(i+2,i+2,i+2),所以对于每个i最多有2对(i,i+1,i+2)

先用桶b记录每种数字出现的次数

f[i][j][k]表示1-i中的数字有j(i-1,i,i+1)的三元组,有k(i,i+1,i+2)的三元组。

根据分析可以得出j,k \leq 2,所以复杂度不会翻车。

转移:

我们考虑i \rightarrow i+1的方式。

now为目前第i种数字剩下的个数

f[i+1][j][t]=MAX(f[i+1][j][t],f[i][j][k]+\frac {(now-t)} 3+t)

意思就是在f[i][j][k]的基础上,把第i种数字剩下中的t个用来组成3连续数字(i,i+1,i+2)类型的三元组

#include<cstdio>
#include<cstring>
#define Fur(i,x,y) for(int i=x;i<=y;i++)
int MAX(int x,int y){return x>y?x:y;}
int MIN(int x,int y){return x<y?x:y;}
using namespace std;
#define N 1000011
int n,m,b[N],f[N][3][3];
int main(){
    scanf("%d%d",&n,&m);
    int x;
    Fur(i,1,n)scanf("%d",&x),b[x]++;
    memset(f,-1,sizeof(f));
    f[0][0][0]=0;
    Fur(i,0,m+1)
        Fur(j,0,2)
            Fur(k,0,2)if(f[i][j][k]>=0){
                int now=b[i+1]-j-k;
                Fur(t,0,MIN(2,now))f[i+1][k][t]=MAX(f[i+1][k][t],f[i][j][k]+(now-t)/3+t);
            }
    printf("%d\n",f[m+1][0][0]);
}

E. Magic Stones

感觉比D容易多了

题意:

有一个序列a,你可以把a_i(1<i<n)变成a_{i-1}+a_{i+1}-a_i,问序列a能否变成序列b

题解:

如果把序列a,b​变为差分数组(原来的a_i​变为a_i-a_{i-1}​)的话可以巧妙地发现每次操作就是交换差分数组中相邻的的两个数。

所以把a,b​分别排序后比较是否相同就可以了。

#include<cstdio>
#include<algorithm>
namespace FastIO{const char* ln="\n";struct Reader{char buf[1<<20],*s,*t;bool EOF_FLG;Reader():s(buf),t(buf),EOF_FLG(false) {};char gt() {return s==t&&((t=(s=buf)+fread(buf,1,1<<20,stdin))==s)?EOF:(*s++);}Reader& operator>>(char* str) {if(EOF_FLG)return *str=0,*this;while((*str=gt())!=' '&&*str!='\n'&&*str!=EOF)++str;if(*str==EOF)EOF_FLG=true;*str=0;return *this;}template<typename T>Reader&operator>>(T&x) {if(EOF_FLG)return *this;char c=0,d;while(c!=EOF&&(c<'0'||c>'9'))d=c,c=gt();if(c==EOF){EOF_FLG=true;return *this;}else x=0;while(c>='0'&&c<='9')x=(x<<3)+(x<<1)+c-'0',c=gt();if(d=='-')x=-x;return *this;}}in;struct Writer{char buf[1<<20],*s,*t;Writer():s(buf),t(buf+(1<<20)){}~Writer(){fwrite(buf,1,s-buf,stdout);}void pt(char c){(s==t)?(fwrite(s=buf,1,1<<20,stdout),*s++=c):(*s++=c);}template<typename T>Writer&operator<<(T x){if(!x)return pt('0'),*this;if(x<0)pt('-'),x=-x;char a[40],t=0;while(x)a[t++]=x%10,x/=10;while(t--)pt(a[t]+'0');return *this;}Writer&operator<<(const char*s) {while(*s)pt(*s++);return *this;}}out;}using namespace FastIO;
#define Fur(i,x,y) for(int i=x;i<=y;i++)
using namespace std;
#define N 100011
int a[N],b[N],n;
int main(){
    in>>n;
    int x=0,y=0;
    Fur(i,1,n)in>>x,a[i]=x-y,y=x;
    x=y=0;
    Fur(i,1,n)in>>x,b[i]=x-y,y=x;
    if(a[1]!=b[1])return out<<"No\n",0;//因为第一个数没法操作
    sort(a+2,a+n+1);
    sort(b+2,b+n+1);
    Fur(i,2,n)if(a[i]!=b[i])return out<<"No\n",0;
    out<<"Yes\n";
}

作者:zcmimi

链接:https://blog.zcmimi.top/posts/CF1110/

声明: 本博客所有文章除特别声明外,均采用CC BY-NC-SA 3.0许可协议. 转载请注明来自zcmimi's blog

CF1110
comment评论
Search
search