ABC069

[ABC069C] 4-adjacent

题面翻译

题目描述

一个数列长为n。你的任务是将数列进行排列，使得当1 ≤ i ≤ N − 1 时，a[i]与a[i+1]的积是4的倍数。请判断你是否能完成这个任务。

输入格式

第一行包含一个正整数n，为数列的长度。第二行包含n个正整数，为数列内的数。

输出格式

如果你能完成这个任务，输出Yes，否则输出No。

题目描述

長さ $ N $ の数列 $ a = (a_1, a_2, ..., a_N) $ があります。各 $ a_i $ は正の整数です。

すぬけ君の目標は、$ a $ の要素を自由に並べ替え、次の条件が成り立つようにすることです。

各 $ 1 < = i < = N - 1 $ について、$ a_i $ と $ a_{i + 1} $ の積は $ 4 $ の倍数である。

すぬけ君が目標を達成できるか判定してください。

输入格式

入力は以下の形式で標準入力から与えられる。

$ N $ $ a_1 $ $ a_2 $ $ ... $ $ a_N $

输出格式

すぬけ君が目標を達成できるならば Yes を、できないならば No を出力せよ。

样例 #1

样例输入 #1
3
1 10 100
样例输出 #1
Yes
样例 #2

样例输入 #2
4
1 2 3 4
样例输出 #2
No
样例 #3

样例输入 #3
3
1 4 1
样例输出 #3
Yes
样例 #4

样例输入 #4
2
1 1
样例输出 #4
No
样例 #5

样例输入 #5
6
2 7 1 8 2 8
样例输出 #5
Yes
提示

制約

$ 2 < = N < = 10^5 $

$ a_i $ は整数である。

$ 1 < = a_i < = 10^9 $

Sample Explanation 1

例えば、$ (1, 100, 10) $ と並べ替えればよいです。

Sample Explanation 2

どのように並べ替えても、条件が成り立つようにできません。

Sample Explanation 3

最初から条件が成り立っています。

思路

不难想到有两种情况：

1、$a_n$为4的倍数。

2、$a_n$与$a_{n+1}$为2的倍数。

如果$a_n$为4的倍数，$a_{n+1}$没有任何要求，反之，如果$a_n$是2的倍数，那么$a_{n+1}$也需要是2的倍数。

需要计算一下贡献，判断是否大于$\frac{n}{2}$。

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const double PI=acos(-1);
const int MAXN=2e5+10;
const ll mod=1e9+7;
const ll INF=1e9;
ll a[MAXN];
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;cin>>n;
    int cnt1=0;
    int cnt2=0;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        if(a[i]%4==0)cnt1++;
        else if(a[i]%2==0)cnt2++;
    }
    //注意cnt2需要除以2
    if(cnt1+cnt2/2>=n/2)cout<<"Yes";
    else cout<<"No";
    return 0;
}

[ABC069D] Grid Coloring

题面翻译

给你一个序列$a$,满足$\sum\limits^{n}_{i=1}a_i=WH$
请你够构造一个$W*H$的矩阵,满足:

每一中颜色$i$,满足矩阵中出现了$a_i$次

要保证每一种颜色$i$都是相互联通的,即为一个联通块

可以证明一定可以构造出这样的矩阵

题目描述

縦 $ H $ 行、横 $ W $ 列のマス目があります。すぬけ君は、このマス目を色 $ 1 $, $ 2 $, $ ... $, $ N $ で塗り分けようとしています。このとき、次の条件が成り立つようにします。

各 $ i $ ($ 1 < = i < = N $) について、色 $ i $ のマスはちょうど $ a_i $ 個存在する。ただし、$ a_1 + a_2 + ... + a_N = H W $ である。

各 $ i $ ($ 1 < = i < = N $) について、色 $ i $ のマスは上下左右に連結である。すなわち、どの色 $ i $ のマスからどの色 $ i $ のマスへも、上下左右に隣り合う色 $ i $ のマスのみを辿って行き来できる。

条件を満たす塗り分け方をひとつ求めてください。解は必ず存在することが示せます。

输入格式

入力は以下の形式で標準入力から与えられる。

$ H $ $ W $ $ N $ $ a_1 $ $ a_2 $ $ ... $ $ a_N $

输出格式

条件を満たす塗り分け方をひとつ出力せよ。塗り分け方は次のフォーマットで出力せよ。ただし、$ c_{i j} $ は、上から $ i $ 行目、左から $ j $ 列目のマスの色である。

$ c_{1 1} $ $ ... $ $ c_{1 W} $ $ : $ $ c_{H 1} $ $ ... $ $ c_{H W} $

样例 #1

样例输入 #1
2 2
3
2 1 1
样例输出 #1
1 1
2 3
样例 #2

样例输入 #2
3 5
5
1 2 3 4 5
样例输出 #2
1 4 4 4 3
2 5 4 5 3
2 5 5 5 3
样例 #3

样例输入 #3
1 1
1
1
样例输出 #3
1
提示

制約

$ 1 < = H, W < = 100 $

$ 1 < = N < = H W $

$ a_i > = 1 $

$ a_1 + a_2 + ... + a_N = H W $

Sample Explanation 1

例えば、次の塗り分け方は条件を満たしません。色 $ 1 $ のマスが上下左右に連結でないからです。 1 2 3 1

思路

不难想到蛇形构造，但是细节需要注意。

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const double PI=acos(-1);
const int MAXN=2e5+10;
const ll mod=1e9+7;
const ll INF=1e9;
int h,w,n;
int g[1010][1010];
vector<int> a;
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin>>h>>w>>n;
    for(int i=0;i<n;i++){
        int x;cin>>x;
        //将所有需要的数字存在数组a中，可以理解为每一块拼图都存入其中
        for(int j=0;j<x;j++)
            a.push_back(i+1);
    }
    for(int i=0;i<h;i++){
        if(i%2==0)
            for(int j=0;j<w;j++)
                g[i][j]=a[w*i+j];
        else
            //注意反向
            for(int j=0;j<w;j++)
                g[i][w-j-1]=a[w*i+j];
    }
    for(int i=0;i<h;i++){
        for(int j=0;j<w;j++){
            cout<<g[i][j]<<" ";
        }
        cout<<"\n";
    }
    return 0;
}