@KirinBill 2017-09-18T18:17:07.000000Z 字数 6764 阅读 1229

AtCoder Regular Contest 080

题解 套题

目录

AtCoder Regular Contest 080

C. 4-adjacent

思路

代码

D. Grid Coloring

思路

代码

E. Young Maids

思路

代码

F. Prime Flip

思路

代码

C. 4-adjacent

题目大意：给你一个数列 $a$ ，问是否能通过置换（交换某些元素的位置），使得该数列满足 $a_i \times a_{i+1} \equiv 0 \pmod{4} ,1 \leq i < n,n \leq 2 \times 10^5$ 。

思路

显然要将 $4$ 的倍数和奇数交叉放， $2$ 的倍数放一起，那么只需统计一下这三种数的个数算一下就好了，很简单，注意一下细节就好（样例很良心，过了一般都A了）。

代码

#include <cstdio>
const int MAXN=1e5+5;
int n,cnt_4,cnt_not4;
int a[MAXN];
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;++i){
        scanf("%d",&a[i]);
        if(a[i]%4==0) ++cnt_4;
        else if(a[i]%2) ++cnt_not4;
    }
    if(cnt_4>=cnt_not4 || (cnt_4>=cnt_not4-1 && cnt_4+cnt_not4==n)) printf("Yes");
    else printf("No");
    return 0;
}

D. Grid Coloring

题目大意：给你 $n$ 种颜色，每种有一个数量要求 $a_i$ ，你要对一个 $H \times W$ 的四连通矩阵染色，使每种颜色数量为 $a_i$ ，并且每种颜色的方格必须互相连通，给出一种方案。

思路

直接蛇形染色就好了，很水。。。

代码

#include <cstdio>
#include <queue>
using std::queue;
const int MAXHW=105;
int n,h,w,a;
int sqr[MAXHW][MAXHW];
queue<int> q,ans;
int main(){
    scanf("%d%d%d",&h,&w,&n);
    for(int i=1;i<=n;++i){
        scanf("%d",&a);
        q.push(a);
    }
    int k=0;
    while(++k,q.size()){
        a=q.front();
        q.pop();
        for(int i=1;i<=a;++i)
            ans.push(k);
    }
    for(int i=1;i<=h;i+=2){
        for(int j=1;j<=w;++j){
            sqr[i][j]=ans.front();
            ans.pop();
        }
        for(int j=w;j && ans.size();--j){
            sqr[i+1][j]=ans.front();
            ans.pop();
        }
    }
    for(int i=1;i<=h;++i){
        for(int j=1;j<=w;++j)
            printf("%d ",sqr[i][j]);
        putchar('\n');
    }
    return 0;
}

E. Young Maids

题目大意：给你一个数列，每次可以取出相邻的两个数按原数列顺序加到一个新的数列的头部，求字典序最小的新数列。

思路

~~考试的时候傻掉了。。。~~

求字典序最小的这种显然贪心；
因为是不断向新数列头部添加，我们就倒着来，每次取原数列最小且合法的两个加在新数列尾部；
现在考虑怎么保证合法：
首先，第一次应该从奇数位置挑一个最小的并在其后面的偶数位置挑一个最小的；
之后，我们可以把原数列分成三段（有的段可能是空的），这样在每段内先挑和该段左端点位置奇偶性相同的，再在其后面且在该段内、位置的奇偶性不同的里面挑一个，操作总是合法的；
所以我们用堆维护一下这些区间，按区间内最小元素排序，每次取堆顶的区间进行以上操作，再将新产生的区间加入堆中即可；
又因为要查询区间最值，还需要用一个数据结构维护一下；

代码

整体不难，但实现起来有些繁琐

#include <cstdio>
#include <algorithm>
#include <utility>
#include <queue>
#include <vector>
#include <functional>
#include <climits>
#include <cmath>
using std::min;
using std::pair;
using std::priority_queue;
using std::vector;
using std::greater;
typedef pair<int,int> range;
typedef pair<int,int> number;
typedef pair<number,range> sub_qry;
const int MAXN=2e5+5,MAXLOG=(int)(log(MAXN)/log(2)+0.5);
int p[MAXN];
class SparseTab{
    private:
        int log_tab[MAXN];
        number c[MAXLOG][MAXN];
    public:
        void build(int n,int a[],bool type){
            log_tab[0]=-1;
            for(int i=1;i<=n;++i){
                c[0][i]=number((i&1)==type ? a[i]:INT_MAX,i);
                log_tab[i]= i&(i-1) ? log_tab[i-1]:log_tab[i-1]+1;
            }
            for(int i=1;i<=log_tab[n];++i){
                for(int j=1;j+(1<<i)-1<=n;++j)
                    c[i][j]=min(c[i-1][j],c[i-1][j+(1<<i-1)]);
            }
        }
        number qry(int l,int r){
            int k=log_tab[r-l+1];
            return min(c[k][l],c[k][r-(1<<k)+1]);
        }
}odd,even;
inline void solve(int n){
    static priority_queue<sub_qry,vector<sub_qry>,greater<sub_qry> > hp;
    number tmp1=odd.qry(1,n),tmp2=even.qry(tmp1.second,n);
    printf("%d %d ",tmp1.first,tmp2.first);
    if(1<=tmp1.second-1)
        hp.push(sub_qry(odd.qry(1,tmp1.second-1),range(1,tmp1.second-1)));
    if(tmp1.second+1<=tmp2.second-1)
        hp.push(sub_qry(even.qry(tmp1.second+1,tmp2.second-1),range(tmp1.second+1,tmp2.second-1)));
    if(tmp2.second+1<=n)
        hp.push(sub_qry(odd.qry(tmp2.second+1,n),range(tmp2.second+1,n)));
    sub_qry now;
    number that;
    SparseTab *st1,*st2;
    while(hp.size()){
        now=hp.top();
        hp.pop();
        st1= now.second.first&1 ? &odd:&even;
        st2= now.second.first&1 ? &even:&odd;
        that=st2->qry(now.first.second,now.second.second);
        printf("%d %d ",now.first.first,that.first);
        if(now.second.first<now.first.second-1)
            hp.push(sub_qry(st1->qry(now.second.first,now.first.second-1),range(now.second.first,now.first.second-1)));
        if(now.first.second+1<that.second-1)
            hp.push(sub_qry(st2->qry(now.first.second+1,that.second-1),range(now.first.second+1,that.second-1)));
        if(that.second+1<now.second.second)
            hp.push(sub_qry(st1->qry(that.second+1,now.second.second),range(that.second+1,now.second.second)));
    }
}
int main(){
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;++i)
        scanf("%d",&p[i]);
    odd.build(n,p,1),even.build(n,p,0);
    solve(n);
    return 0;
}

F. Prime Flip

题目大意：有一个无限长的卡片序列标号为 $1,2,\cdots,\infty$ ，给定 $n$ 个数 $x_1,x_2,\cdots,x_n$ ，这些数对应标号的卡片是向上的，其它为向下的，每次只可以连续翻转奇质数长度的卡片，求使得整个卡片序列都向下的最少操作次数。（ $1 \leq n \leq 100$ ， $1 \leq \max(x_i) \leq 10^7$ ）。

思路

这题太神了，看了半天题解。。。orz

考虑将原问题进行转化，记 $i$ 号卡片是否向上为布尔函数 $is\_up(i)$ 且 $is\_up(0)=0$ ，设01序列 $b$ 满足 $b_i=[is\_up(i)=is\_up(i-1)]$ ，则翻转一段连续的卡片 $[l,r]$ 可以表示为 $b_l=\lnot b_l,b_{r+1}=\lnot b_{r+1}$ ；
那么问题就变成了给定一个01序列 $b$ ，每次对两个元素 $b_i,b_j$ 取反，其中 $\mid j-i \mid$ 是质数，求使得该序列元素全变为0的最少操作次数；
设对 $b_i,b_j$ 取反的最小代价为 $cost(i,j)$ ，其中 $\mid j-i \mid$ 不一定为质数，现在我们分四种情况讨论：
1. $\mid j-i \mid$ 是质数，则 $cost(i,j)=1$ ；
2. $\mid j-i \mid$ 是偶数，则根据波利尼亚克猜想，任意一个偶数可以表示为两个质数之差（至少在这题的数据范围内是成立的...）， $cost(i,j)=2$ ；
3. $\mid j-i \mid$ 是奇合数，则有 $cost(i,j)=3$ ，因为有一个“猜想”（它貌似尚未被完全证明，只能说在这题范围内成立）：任意一个奇合数可以表示为3个奇质数之和。
  证明：
  1. 根据维诺格拉多夫定理，任意一个大于5的奇数可以表示为3个质数之和。
  2. 那么只需证明若一个奇合数能被分解为 $2+2+x,x$ 为奇质数时，它一定能表示为其它3个奇质数之和。
  3. 将该奇合数写成 $y+x,y=4$ ，考虑当 $x>3$ 时，不断将 $y+=2,x-=2$ ，则总有一刻， $x$ 变为一个奇质数（ $eg. 3,5,7,\cdots$ ）。
  4. 又因为哥德巴赫猜想，偶数 $y$ 定能写成两个质数之和（至少在这题数据范围内可以），并且当 $y=4 \to 6$ 后， $y$ 写成的质数和不含2！
  5. 最后，再考虑 $x=3$ 时， $2+2+3=7$ ，7不是奇合数，证毕！（出题人太神了orz）。
4. $\mid j-i \mid=1$ ，考虑一个质数减去它相邻的比它小的质数等于1，则 $\mid j-i \mid=1$ 的情况可以被分解为 $\mid j-i \mid$ 是质数和偶数两个情况，所以 $cost(i,j)=3$ .
又由于每一段连续向上的卡片，都产生了两个 $1$ ，我们只需看怎么将这些 $1$ 两两分组使 $\sum cost(i,j)$ 最小；
现在，我们的任务是将这些 $1$ 两两配对，每对的代价为 $cost(i,j)$ ，求最小代价和；
将1按原位置奇偶分组，则每组里的 $1$ 两两配对，它们的 $\mid j-i \mid$ 定为偶数，而两组间配对， $\mid j-i \mid$ 为奇数，有两种可能；
由于，我们要求最小代价，我们先对这两组 $1$ 求二分图最大匹配（只连 $\mid j-i \mid$ 为质数的边），设匹配了 $k$ 对，则其花费为 $k$ ，剩下的我们先试图用代价为 $2$ 的来配对，最后再用 $3$ ；
设奇数组 $1$ 的个数为 $odd \_ size$ ，偶数组 $1$ 的个数为 $even \_ size$ ，那么 $ans=k+(odd \_ size/2+even \_ size/2)\times 2+odd \_ size \mod 2 \times 3$ .

代码

#include <cstdio>
#include <cmath>
#include <climits>
#include <queue>
#include <algorithm>
using std::queue;
using std::min;
const int MAXX=1e7+5,MAXN=205;
int n,cnt_x,cnt_y;
int x_id[MAXN],y_id[MAXN];
bool up[MAXX];
struct node{int he,iter,dis;}d[MAXN];
struct line{int to,nex,cap;}ed[MAXN*MAXN<<1];
inline bool is_odd_prm(int x){
    if(x==1) return false;
    for(int i=2;i*i<=x;++i){
        if(x%i==0) return false;
    }
    return true;
}
inline void addE(int u,int v,int cap){
    static int cnt=1;
    ed[++cnt]=(line){v,d[u].he,cap};
    d[u].he=cnt;
}
inline int revE(int i){return i^1;}
inline bool BFS(int s,int t,int n){
    for(int i=1;i<=n;++i)
        d[i].dis=-1;
    static queue<int> q;
    d[s].dis=0;
    q.push(s);
    int u;
    while(q.size()){
        u=q.front();
        q.pop();
        for(int i=d[u].he,v;i;i=ed[i].nex){
            if(ed[i].cap==0) continue;
            v=ed[i].to;
            if(d[v].dis==-1){
                d[v].dis=d[u].dis+1;
                q.push(v);
            }
        }
    }
    return d[t].dis!=-1;
}
int aug(int u,int rest,const int t){
    if(u==t) return rest;
    int ret=0;
    for(int &i=d[u].iter,v,cap,flow;i;i=ed[i].nex){
        v=ed[i].to,cap=ed[i].cap;
        if(d[v].dis!=d[u].dis+1 || cap==0)
            continue;
        flow=aug(v,min(cap,rest),t);
        ed[i].cap-=flow,ed[revE(i)].cap+=flow;
        ret+=flow,rest-=flow;
        if(rest==0) return ret;
    }
    if(ret==0) d[u].dis=-1;
    return ret;
}
inline int Dinic(int s,int t,int n){
    int ret=0;
    while(BFS(s,t,n)){
        for(int i=1;i<=n;++i)
            d[i].iter=d[i].he;
        ret+=aug(s,INT_MAX,t);
    }
    return ret;
}
inline void build(){
    for(int i=1;i<=cnt_x;++i){
        for(int j=1,v;j<=cnt_y;++j){
            if(is_odd_prm(abs(x_id[i]-y_id[j]))){
                v=j+cnt_x;
                addE(i,v,INT_MAX),addE(v,i,0);
            }
        }
    }
    for(int i=1,s=cnt_x+cnt_y+1;i<=cnt_x;++i)
        addE(s,i,1),addE(i,s,0);
    for(int i=1,u,t=cnt_x+cnt_y+2;i<=cnt_y;++i){
        u=cnt_x+i;
        addE(u,t,1),addE(t,u,0);
    }
}
int main(){
    scanf("%d",&n);
    int x;
    for(int i=1;i<=n;++i){
        scanf("%d",&x);
        up[x]=true;
    }
    for(int i=1;i<=x+1;++i){
        if(up[i]!=up[i-1])
            i&1 ? x_id[++cnt_x]=i:y_id[++cnt_y]=i;
    }
    build();
    int k=Dinic(cnt_x+cnt_y+1,cnt_x+cnt_y+2,cnt_x+cnt_y+2);
    printf("%d",k+((cnt_x-k)/2+(cnt_y-k)/2)*2+(cnt_x-k)%2*3);
    return 0;
}

AtCoder Regular Contest 080

C. 4-adjacent

思路

代码

D. Grid Coloring

思路

代码

E. Young Maids

思路

代码

F. Prime Flip

思路

代码

内容目录