M_sea

「题解」Codeforces Global Round 1
传送门还好这场没打,不然肯定掉分[A]Parity分析大力分类讨论。如果$b$是奇数显然此时$b^{k-i}$全部...
扫描右侧二维码阅读全文
08
2019/02

「题解」Codeforces Global Round 1

传送门

还好这场没打,不然肯定掉分

[A]Parity

分析

大力分类讨论。

  • 如果$b$是奇数

显然此时$b^{k-i}$全部为奇数。于是$a_i\cdot b^{k-i}$是奇数当且仅当$a_i$是奇数。

于是统计$a$中奇数的个数$s$。如果$s$为奇数,则整个式子为奇数;否则整个式子为偶数。

  • 如果$b$是偶数

显然仅有$b^0$为奇数,其它的$b_i(i>0)$都为偶数。

于是整个式子的奇偶性取决于$a_k$。如果$a_k$为奇数,则整个式子为奇数;否则,整个式子为偶数。

代码

//It is made by M_sea
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <queue>
#define re register
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=100000+10;

int a[N],b,k;

int main() {
    b=read(),k=read();
    for (re int i=1;i<=k;++i) a[i]=read();
    if (b&1) {
        int s=0;
        for (re int i=1;i<=k;++i)
            if (a[i]&1) ++s;
        if (s&1) puts("odd");
        else puts("even");
    }
    else {
        if (a[k]&1) puts("odd");
        else puts("even");
    }
    return 0;
}

[B]Tape

分析

我连PJ题都不会做了

先放置$n$条长度为$1$的线段,放在每个点上。现在要把这$n$条缩成$k$条,并要使总长度最短。

很显然地,每次选出间距最短的两条缩成一条是最优的。

维护一个小根堆救星啦。

细节见代码。

代码

//It is made by M_sea
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <vector>
#include <cmath>
#include <queue>
#define re register
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=100000+10;

int n,m,k;
int a[N];
priority_queue<int,vector<int>,greater<int> > Q;

int main() {
    n=read(),m=read(),k=read();
    for (re int i=1;i<=n;++i) a[i]=read();
    for (re int i=1;i<n;++i) Q.push(a[i+1]-a[i]);
    int ans=k; //k个端点
    for (re int i=1;i<=n-k;++i) ans+=Q.top(),Q.pop();
    printf("%d\n",ans);
    return 0;
}

[C]Meaningless Operations

分析

分类讨论。

  • 如果$a\not=2^i-1$

找到$a$的最高的是$1$的位,设这一位为$x$。

如果$b$取一个$1\sim x$位都与$a$相反的数,此时$a\oplus b=2^{x+1}-1$,$a\&b=0$,所以$\gcd(a\oplus b,a\&b)=2^{x+1}-1$。

容易发现这样是最大的。

  • 如果$a=2^i-1$

此时$a\&b=b$,$a\oplus b=a-b$。

于是$\gcd(a\oplus b,a\&b)=\gcd(a-b,b)=\gcd(a,b)$。(后面那一步不懂的请百度更相减损术)

所以$b$取$a$的最大真因子时$\gcd(a\oplus b,a\&b)$最大。

代码

//It is made by M_sea
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <vector>
#include <cmath>
#include <queue>
#define re register
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

int mark[1<<25];

int main() {
    for (re int i=1;i<=25;++i) mark[(1<<i)-1]=1;
    int Q=read();
    while (Q--) {
        int a=read();
        if (mark[a]) {
            for (re int i=3;i<=a;i+=2)
            if (a%i==0) { printf("%d\n",a/i); break; }
        }
        else {
            int l=0;
            while (a) a>>=1,++l;
            printf("%d\n",(1<<l)-1);
        }
    }
    return 0;
}

[D]Jongmah

分析

显然$(i-2,i-1,i)$这样的组合最多选两个,因为三个的话就可以凑成$(i,i,i)$这种东西。

考虑$\texttt{DP}$。设$f[i][j][k]$表示前$i$位,第$i$位已经拿了$j$个,第$i-1$位已经拿了$k$个,最多能组成的三元组个数。

转移直接枚举选了几个$(i-2,i-1,i)$即可。

转移方程:$f[i][j][k]=\max\limits_{l=0}^2\left\{f[i-1][k+l][l]+\left\lfloor\frac{a_i-j-l}{3}\right\rfloor\right\}$,这里的$a_i$是$i$的个数。

答案是$f[m][0][0]$。

代码

//It is made by M_sea
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#define re register
using namespace std;

inline void chkmax(int& x,int y) { if (y>x) x=y; }
inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=1000000+10;

int a[N];
int f[N][5][5];

int main() {
    int n=read(),m=read();
    for (re int i=1;i<=n;++i) ++a[read()];
    for (re int i=0;i<=min(4,a[1]);++i) f[1][i][0]=(a[1]-i)/3;
    for (re int i=2;i<=m;++i)
    for (re int j=0;j<=min(4,a[i]);++j)
        for (re int k=0;k<=min(4,a[i-1]);++k)
                for (re int l=0;l<=2;++l) {
                if (j+l>a[i]||k+l>a[i-1]||l>a[i-2]||k+l>4) break;
                chkmax(f[i][j][k],f[i-1][k+l][l]+(a[i]-j-l)/3+l);
            }
    printf("%d\n",f[m][0][0]);
    return 0;
}

[E]Magic Stones

分析

考虑一次变换后发生了什么。

看题解后发现,每次变换相当于交换了差分数组中相邻的两个数。

也就是对$i$操作后,$c_{i+1}-c_i$与$c_i-c_{i-1}$交换了。

于是直接将$c$和$t$的差分数组$\texttt{sort}$一遍比较就行了。

注意$1$和$n$是不能操作的,所以要专门判断一下。

代码

//It is made by M_sea
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#define re register
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=100000+10;

int c[N],t[N],a[N],b[N];

int main() {
    int n=read();
    for (re int i=1;i<=n;++i) c[i]=read();
    for (re int i=1;i<=n;++i) t[i]=read();
    if (c[1]!=t[1]||c[n]!=t[n]) { puts("No"); return 0; }
    for (re int i=1;i<n;++i) a[i]=c[i+1]-c[i],b[i]=t[i+1]-t[i];
    sort(a+1,a+n+1); sort(b+1,b+n+1);
    for (re int i=1;i<n;++i)
        if (a[i]!=b[i]) { puts("No"); return 0; }
    puts("Yes");
    return 0;
}

未完待续...

最后修改:2019 年 02 月 13 日 10 : 30 AM

发表评论