…弱鸡只会ABCD

A.Not Shading

题目要求

给一个n * m方格图,’B’ means 黑,’W’ means 白,每次操作能将任意黑的格子所在的行or列都染黑,再给出目标x,y,问最少操作数使得(x,y)格子被染黑;

思路:

1 如果目标格子本就是黑色，则无需操作;

2如果目标格子所在的列 or 行存在黑格子，则操作数为1

3 若存在黑格子但是不在目标行 or 列,则操作数为 2

4 方格图中都没黑格子 操作 0;

代码如下

#include<iostream>
#include<algorithm>
#include<cstring>
#include<vector>
using namespace std;
const int N=55;
char s[N][N];
int n,m,x,y;

void solve()
{
    bool flag=false;
    memset(s,0,sizeof s);
    cin>>n>>m>>x>>y;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            cin>>s[i][j];
            if(s[i][j]=='B')  flag=true;
        }
    }
    if(s[x][y]=='B')  {
        cout<<"0"<<endl;
        return;
    }
    for(int i=1;i<=m;i++){
        if(i!=y&&s[x][i]=='B')  {
            cout<<"1"<<endl;
            return;
        }

    }
    for(int i=1;i<=n;i++){
        if(i!=x&&s[i][y]=='B') {
             cout<<"1"<<endl;
             return;
        }

    }
    if(flag)  {
        cout<<"2"<<endl;
        return;
    }
    else cout<<"-1"<<endl;
    return;
}


int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        solve();
    }

    return  0;

}

B.Not Sitting

题目要求

给出n * m 方格图,图中有两个人分别是舔狗和女生,舔狗很有原则不会坐在被染色的地方,女生都能坐, k是染色格子数，求k从0~n*m-1,求舔狗想离女生更近，但是女生想离舔狗更远，问随着涂色数越来越多，舔狗离女神的曼哈顿距离;

思路:女生肯定是坐在四个角的，然后分别枚举每个点到最远点的距离，存下后sort一遍。

代码

#include<iostream>
#include<algorithm>
#include<cstring>
#include<vector>
using namespace std;
const int N=1e5+10;
int n,m,x,y;
int a[N];
void solve()
{
    cin>>n>>m;
    memset(a,0,sizeof a);
    int cnt=0;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            a[++cnt]=max(n-i,i-1)+max(m-j,j-1);
        }
    }
    sort(a+1,a+1+cnt);
    for(int i=1;i<=cnt;i++){
        cout<<a[i]<<" ";
    }
    cout<<endl;
    return;

}


int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        solve();
    }

    return  0;

}

C.Not Assigning

题意: 给出n个点，n-1条无向边,构造出任意路径的边权之和为素数的树;

我们可以发现,任何入度大于2的点,无法构造出和为素数,符合条件的从入度为1开始看就是一条链,找到入度为1的结点,

爆搜出它能拓展的边,开个ans存下构造的边权就可以了;

代码如下

#include<iostream>
#include<algorithm>
#include<cstring>
#include<vector>
using namespace std;
typedef pair<int,int> PII;
const int N=1e5+10,M=2*N;

int h[N],e[M],ne[M],idx;
int n;
int du[N];

void add(int a,int b)
{
    e[idx]=b;
    ne[idx]=h[a];
    h[a]=idx++;
}
void dfs(int now,int pre,int c,int ans[])
{
    int x=2;
    if(c==2)  x=5-c;
    for(int i=h[now];~i;i=ne[i]){
        int j=e[i];
        if(j!=pre){
            ans[i]=c;
            dfs(j,now,x,ans);
        }
    }
}

void _solve()
{
    cin>>n;
    memset(h,-1,sizeof h);
    memset(du,0,sizeof du);
    idx=0;
    bool flag=true;
    for(int i=1;i<n;i++){
        int a,b;
        cin>>a>>b;
        add(a,b);
        add(b,a);
        if(++du[a]>2||++du[b]>2)  flag=false;
    }
    if(!flag){
        cout<<"-1"<<endl;
        return;
    }
    int ans[n-1];
    for(int i=1;i<=n;i++){
        if(du[i]==1){
            dfs(i,-1,2,ans);
        }
    }

    for(int i=0;i<n-1;i++){
        cout<<ans[i]<<" ";
    }
    cout<<endl;
    return ;
}

int main()
{
    int _test;
    for(cin>>_test;_test;_test--){
        _solve();
    }
    return 0;
}

D.Not Adding

给出长度为n的序列,每次操作任意两个gcd没有出现在序列中的数,并将gcd加入原序列,求最大操作数;

思路：暴力出奇迹,某个数如果满足条件,则它的所有倍数的gcd为1;

#include<iostream>
#include<algorithm>
#include<cstring>
#include<vector>
#include<unordered_map>
using namespace std;
const int N=1e6+10;

int  n;
int a[N];
bool mp[N];
int gcd(int a,int b)
{
    return b==0?a:gcd(b,a%b);
}

int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)  {
        int x;
        cin>>x;
        mp[x]=true;
    }
    int ans=0;
    for(int i=1;i<=1e6;i++){
        int g=0;
        for(int j=i;j<=1e6;j+=i){
            if(mp[j]){
                g=gcd(g,j/i);
            }

        }
        if(g==1&&!mp[i]){
            mp[i]=true;
            ans++;
        } 
    }
    cout<<ans<<endl;
    return 0;

}