Codeforces Round #630 (Div. 2)

题目链接：https://codeforces.com/contest/1332

A. Exercising Walk

可走的最远距离：左：x-x1，右：x2-x，下：y-y1，上：y2-y

如果可以移动，通过折返行走，两个相对方向至少有一个可以消为0，然后看余下步数是否小于等于该方向可走的最远距离，类似于一种模拟的做法，好多大佬都是直接结论QAQ。

#include <bits/stdc++.h>

using namespace std;

void solve()

{

    int a,b,c,d;

    cin>>a>>b>>c>>d;

    int x,y,x1,x2,y1,y2;

    cin>>x>>y>>x1>>y1>>x2>>y2;

    int l1=max(x-x1,x2-x),l2=max(y-y1,y2-y);

    if(l1>0){

        int mi=min(a,b);

        a-=mi,b-=mi;

        if(a>0&&a<=x-x1) a=0;

        if(b>0&&b<=x2-x) b=0;

    }

    if(l2>0){

        int mi=min(c,d);

        c-=mi,d-=mi;

        if(c>0&&c<=y-y1) c=0;

        if(d>0&&d<=y2-y) d=0;

    }

    if(a||b||c||d) cout<<"No\n";

    else cout<<"Yes\n";

}

int main()

{

    int t;cin>>t;

    while(t--)

        solve();

    return 0;

}

B. Composite Coloring

题面其实暗示得非常明确：给你一个合数数组，最多染11种颜色，相同颜色gcd大于1。

为什么是11？因为平方小于1000的质因数只有11个：

2，3，5，7，11，13，17，19，23，29，31。

因为每个数可以被分解成质因数之积，最小质因数相同的染一个颜色即可。

#include <bits/stdc++.h>

using namespace std;

void solve()

{

    int n;cin>>n;

    int res[n]={};

    int color=0;

    map<int,int> m;

    for(int i=0;i<n;i++){

        int t;cin>>t;

        for(int j=2;j<=t;j++){

            if(t%j==0){//j为t的最小质因数

                if(m[j]) res[i]=m[j];

                else res[i]=m[j]=++color;

                break;

            }

        }

    }

    cout<<color<<"\n";

    for(int i=0;i<n;i++) cout<<i<<" \n"[i==n-1];

}

int main()

{

    int t;cin>>t;

    while(t--)

        solve();

    return 0;

}

C. K-Complete Word

每次操作如下：

回文：取两端
周期：取两端向另一端的周期字符

由题意这些字符必须相同，因为要最小替换次数，统计每个字母，换成出现次数最多的即可。

#include <bits/stdc++.h>

using namespace std;

void solve()

{

    int n,k;cin>>n>>k;

    string s;cin>>s;

    int ans=0;

    bool vis[n]={};

    for(int i=0;i<n;i++)

    {

        if(vis[i]) continue;

        vector<char> v;

        for(int j=i;j<n;j+=k)

            if(!vis[j]){

                v.push_back(s[j]);

                vis[j]=true;

            }

        for(int j=n-i-1;j>=0;j-=k)

            if(!vis[j]){

                v.push_back(s[j]);

                vis[j]=true;

            }

        int mx=0,cnt[26]={};

        for(char c:v) mx=max(mx,++cnt[c-'a']);

        ans+=int(v.size())-mx;

    }

    cout<<ans<<"\n";

}

int main()

{

    int t;cin>>t;

    while(t--)

        solve();

    return 0;

}

D. Walk on Matrix

该dp代码会因为追求当前的最大与值而舍弃掉会使答案更大的较小值，如：

$\begin{bmatrix} 0 & 011 & 0 \\ 100 & 111 & 011 \end{bmatrix}$

所以可以构造：

$\begin{bmatrix} inf+k & k &inf \\ inf & inf+k &k \end{bmatrix}$

#include <bits/stdc++.h>

using namespace std;

const int inf=1<<17;

int main()

{

    int k;cin>>k;

    cout<<"2 3\n";

    cout<<(inf+k)<<' '<<k<<' '<<inf<<"\n";

    cout<<inf<<' '<<(inf+k)<<' '<<k;

    return 0;

}

巴特西

Codeforces Round #630 (Div. 2)

A. Exercising Walk

B. Composite Coloring

C. K-Complete Word

D. Walk on Matrix

最新文章

热门文章