CF1110

Author Avatar
ZC 2月 08, 2019
  • 在其它设备中阅读本文章
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).

题解:

用一个bool$f$记录到目前是奇数还是偶数

如果$a_i$或$b_{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$,然后输入$q$个$a$,对于每个$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";
}