Codeforces Round #632 (Div. 2)题解

A.Little Artem

题意：
$n * m 的网格中，有黑白两种颜色$
$B 是相邻了白色的黑格数量$
$W 是相邻了黑色的白格数量$
$构造一个 n * m 的图，保证 B = W + 1$
题解：
$因为 B = W + 1 ，所以让黑白有 x 个相邻的$
$然后由于黑色的比白色多，让两个黑色的相邻一个公共的$
$所以就可以构造出，第一列和第 n 行全是 B ，其他是 W$
$这样，每个黑色对应一个白色$
$但是第一列第 n - 1 行的和第 n 行第 2 列的公用一个白色$
$所以白色的少一个，保证了 B = W + 1$

AC代码

#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define endl '\n'
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
//const int mod=1e9+7;
const int mod=998244353;
const double eps = 1e-10;
const double pi=acos(-1.0);
const int maxn=1e5+10;
const ll inf=0x3f3f3f3f;
const int dir[4][2]={{0,1},{1,0},{0,-1},{-1,0}};




int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    //freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);
    int t;
    cin>>t;
    while(t--){
        int n,m;
        cin>>n>>m;
        for(int i=1;i<n;i++,cout<<endl)
            for(int j=1;j<=m;j++)
                if(j==1)cout<<'B';
                else cout<<'W';
        for(int i=1;i<=m;i++)
            cout<<'B';
        cout<<endl;
    }
    return 0;
}

B.Kind Anton

题意：
$给定一个长度为 n 的数组 a 和数组 b$
$a 的每个元素由 {0, 1, - 1} 组成$
$可以进行一个操作任意次：$
$对于 i < j ， a_{j} + = a_{i}$
$问 a 是否能够等于 b$
题解：
$由于只有前面的数给后面的数赋值$
$所以用 m a p 或者数组维护已经出现过的 1 或者 - 1$
$所以只需要看如果 a_{i}! = b_{i} <mtext> </mtext> a_{i} 变成 b_{i} 需要 1 还是 - 1$
$如果对于所有 i 需要的都存在那么就能够等于数组 b$

AC代码

#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define endl '\n'
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
//const int mod=1e9+7;
const int mod=998244353;
const double eps = 1e-10;
const double pi=acos(-1.0);
const int maxn=1e5+10;
const ll inf=0x3f3f3f3f;
const int dir[4][2]={{0,1},{1,0},{0,-1},{-1,0}};


int a[maxn],b[maxn];

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    //freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);
    int t;
    cin>>t;
    while(t--){
        int n;
        cin>>n;
        map<int,int> m;
        for(int i=1;i<=n;i++)cin>>a[i];
        for(int i=1;i<=n;i++)cin>>b[i];
        bool f=0;
        for(int i=1;i<=n;i++){
            if(a[i]==b[i]){m[a[i]]++;continue;}
            int d=b[i]-a[i];
            if(d>0&&m[1]){m[a[i]]++;continue;}
            if(d<0&&m[-1]){m[a[i]]++;continue;}
            f=1;m[a[i]]++;
        }
        if(f)cout<<"NO"<<endl;
        else cout<<"YES"<<endl;
    }
    return 0;
}

C.Eugene and an array

题意：
$给一个长度为 n 的数组$
$问能找到多少个子段，这个子段的任意子段和不为 0$
题解：
$对于每个位置的值，看它能和它前面的多少位可以组成符合条件的子段$
$所以要用 m a p 维护已经枚举过的前缀和的最后一次出现位置$
$然后如果某个前缀和出现过，说明这次和 m a p 维护的位置之间和是 0$
$所以只能从 m a p 的位置的下一个开始到这个点的子段符合$
$由于子段和不能为 0 ，所以这一段也不能出现在后面的子段中$
$所以每次更新一个能取到最左值 l ，就是每次 m a p 位置的后一个位置$
$如果 a_{i} 为 0 ，那说明 1 到 i 的所有都不能和 i 后面的形成符合条件的子段$
$所以直接更新最左值 l = i + 1$
$对于每次位置的更新，答案也加上能取到的结果$

AC代码

#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define endl '\n'
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
//const int mod=1e9+7;
const int mod=998244353;
const double eps = 1e-10;
const double pi=acos(-1.0);
const int maxn=2e5+10;
const ll inf=0x3f3f3f3f;
const int dir[4][2]={{0,1},{1,0},{0,-1},{-1,0}};


ll a[maxn],sum[maxn];
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    //freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)cin>>a[i],sum[i]=sum[i-1]+a[i];
    map<ll,int> m;
    int l=0;
    ll ans=0;
    for(ll i=1;i<=n;i++){
        if(!m[sum[i]]&&sum[i]&&a[i])ans+=(i-l);
        else if(!a[i])l=i;
        else l=max(l,m[sum[i]]+1),ans+=(i-l);
        m[sum[i]]=i;
    }
    cout<<ans;
    return 0;
}

D.Challenges in school №41

题意：
$一个队列有 n 个人，每个人站的方向可能是 L 或 R$
$可能两个人会有面对面的情况$
$你每次至少使一对面对面的人同时转身$
$是否你能够在 k 次使得这个队列没有面对面的人$
$如果可以输出这 k 次翻转的人$
题解：
$由于你想让所有面对面的人都不面对面$
$只有每次让他们转身$
$所以只有暴力模拟，直到不出现面对面，每次记录$
$由于每次至少翻转一对，所以可以同时翻转多对面对面的人$
$为了使答案最小化，每次翻转所有面对面的人$
$如果这样翻转还是需要比 k 次数多，说明不可能完成$
$然而，你可以每次只翻转一对，可以达到将一次翻转分成多次的效果$
$但是，如果按这样全部分开，还是比 k 小，那就说明不能完成$
$然后，就是按这样，把所有的次数转化成 k 次完成即可$

AC代码

#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define endl '\n'
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
//const int mod=1e9+7;
const int mod=998244353;
const double eps = 1e-10;
const double pi=acos(-1.0);
const int maxn=3e6+10;
const ll inf=0x3f3f3f3f;
const int dir[4][2]={{0,1},{1,0},{0,-1},{-1,0}};

vector<int> v[100010];
vector<int> ans[maxn];

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    //freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);
    int n,k;
    cin>>n>>k;
    string s;
    cin>>s;
    int cnt=0,tot=0;
    while(1){
        cnt++;
        bool f=0;
        for(int i=0;i<n;i++)
            if(s[i]=='R'&&s[i+1]=='L')
                v[cnt].pb(i+1),swap(s[i],s[i+1]),f=1,tot++,i++;
        if(!f)break;
        if(cnt>k){cout<<-1;return 0;}
    }
    if(k>tot){cout<<-1;return 0;}
    int c=0;
    for(int i=1;i<cnt;i++){
        for(auto j:v[i]){
            if(cnt-i<k)ans[c++].pb(j),k--;
            else ans[c].pb(j);
        }
        if(cnt-i>=k&&!ans[c].empty())c++,k--;
    }
    for(int i=0;i<c;i++){
            cout<<(int)ans[i].size()<<' ';
            for(auto j:ans[i])cout<<j<<' ';
            cout<<endl;
    }
    return 0;
}

F.Kate and imperfection

题意：
$给一个数 n$
$让你从 1 - n 中每次找出 x 个数 (2 < = x < = n) 为集合 s$
$F (s) 表示 x 个数中任意两个数 a ， b 的 g c d (a, b) 的最大值$
$让你使这个对于 2 < = x < = n 使得 F (s) 最小$
$对于 x 从 2 - n 求出这个最小的 F (s)$
题解：
$首先自己手写枚举一下，可以发现$
$每次先把质数找齐，肯定这些值都是 1$
$然后再找 2 ， 4 ， 6 ， 9 ， 8 ， 10 这样的顺序$
$而且 F (s) 是随 x 递增的$
$这样会发现，如果一个数不是质数，你又必须选到这个数$
$那么 F (s) 就是这个数的最大因子$
$所以问题转化成了，找每个数的最大因子，统计到一起$
$然后从小到大输出就可以了$
$这里就可以用类似素数筛的方法进行预处理$
$然后找到每个数的最大因子，再用 v e c t o r 读取一遍排个序$

AC代码

#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define endl '\n'
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
//const int mod=1e9+7;
const int mod=998244353;
const double eps = 1e-10;
const double pi=acos(-1.0);
const int maxn=5e5+10;
const ll inf=0x3f3f3f3f;
const int dir[4][2]={{0,1},{1,0},{0,-1},{-1,0}};

int a[maxn];

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    //freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);
    int n;
    cin>>n;
    for(int i=2;i<=n;i++)
        if(!a[i])
        for(int j=i;j<=n;j+=i)
            if(!a[j])a[j]=j/i;
    a[1]=1;
    vector<int> v;
    for(int i=1;i<=n;i++)
        if(a[i])v.pb(a[i]);
    sort(all(v));
    for(int i=1;i<n;i++)
        cout<<v[i]<<' ';
    return 0;
}