题目链接

A.Little Artem

题意:
n m n*m的网格中,有黑白两种颜色 nm
B B是相邻了白色的黑格数量 B
W W是相邻了黑色的白格数量 W
n m B = W + 1 构造一个n*m的图,保证B=W+1 nmB=W+1
题解:
B = W + 1 x 因为B=W+1,所以让黑白有x个相邻的 B=W+1x
然后由于黑色的比白色多,让两个黑色的相邻一个公共的
n B W 所以就可以构造出,第一列和第n行全是B,其他是W nBW
这样,每个黑色对应一个白色
n 1 n 2 但是第一列第n-1行的和第n行第2列的公用一个白色 n1n2
B = W + 1 所以白色的少一个,保证了B=W+1 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 给定一个长度为n的数组a和数组b nab
a { 0 , 1 , 1 } a的每个元素由\{0,1,-1\}组成 a{0,1,1}
可以进行一个操作任意次:
i < j a j + = a i 对于i<j,a_j+=a_i i<jaj+=ai
a b 问a是否能够等于b ab
题解:
由于只有前面的数给后面的数赋值
m a p 1 1 所以用map或者数组维护已经出现过的1或者-1 map11
a i ! = b i <mtext>     </mtext> a i b i 1 1 所以只需要看如果a_i!=b_i~~~a_i变成b_i需要1还是-1 ai!=bi   aibi11
i b 如果对于所有i需要的都存在那么就能够等于数组b ib

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 给一个长度为n的数组 n
0 问能找到多少个子段,这个子段的任意子段和不为0 0
题解:
对于每个位置的值,看它能和它前面的多少位可以组成符合条件的子段
m a p 所以要用map维护已经枚举过的前缀和的最后一次出现位置 map
m a p 0 然后如果某个前缀和出现过,说明这次和map维护的位置之间和是0 map0
m a p 所以只能从map的位置的下一个开始到这个点的子段符合 map
0 由于子段和不能为0,所以这一段也不能出现在后面的子段中 0
l m a p 所以每次更新一个能取到最左值l,就是每次map位置的后一个位置 lmap
a i 0 1 i i 如果a_i为0,那说明1到i的所有都不能和i后面的形成符合条件的子段 ai01ii
l = i + 1 所以直接更新最左值l=i+1 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 一个队列有n个人,每个人站的方向可能是L或R nLR
可能两个人会有面对面的情况
使 你每次至少使一对面对面的人同时转身 使
k 使 是否你能够在k次使得这个队列没有面对面的人 k使
k 如果可以输出这k次翻转的人 k
题解:
由于你想让所有面对面的人都不面对面
只有每次让他们转身
所以只有暴力模拟,直到不出现面对面,每次记录
由于每次至少翻转一对,所以可以同时翻转多对面对面的人
使 为了使答案最小化,每次翻转所有面对面的人 使
k 如果这样翻转还是需要比k次数多,说明不可能完成 k
然而,你可以每次只翻转一对,可以达到将一次翻转分成多次的效果
k 但是,如果按这样全部分开,还是比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 给一个数n n
1 n x ( 2 < = x < = n ) s 让你从1-n中每次找出x个数(2<=x<=n)为集合s 1nx(2<=x<=n)s
F ( s ) x a b g c d ( a , b ) F(s)表示x个数中任意两个数a,b的gcd(a,b)的最大值 F(s)xabgcd(a,b)
使 2 < = x < = n 使 F ( s ) 让你使这个对于2<=x<=n使得F(s)最小 使2<=x<=n使F(s)
x 2 n F ( s ) 对于x从2-n求出这个最小的F(s) x2nF(s)
题解:
首先自己手写枚举一下,可以发现
1 每次先把质数找齐,肯定这些值都是1 1
2 4 6 9 8 10 然后再找2,4,6,9,8,10这样的顺序 2469810
F ( s ) x 而且F(s)是随x递增的 F(s)x
这样会发现,如果一个数不是质数,你又必须选到这个数
F ( s ) 那么F(s)就是这个数的最大因子 F(s)
所以问题转化成了,找每个数的最大因子,统计到一起
然后从小到大输出就可以了
这里就可以用类似素数筛的方法进行预处理
v e c t o r 然后找到每个数的最大因子,再用vector读取一遍排个序 vector

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;
}