A.World Fragments I

题目大意：给两个二进制数字和，每次操作选一个在中的数字（0或1），对x整体进行操作使+=或-=，求最少的操作次数。

思路：只有=且时，无法变动大小，无解输出，否则每次选择中的，当时每次使+=，当时每次使-=，设和转换成十进制后的数字分别是和，最少的总操作次数为。

AC代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e6+10;
signed main()
{   
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    string x;
    string y;
    int a=0;
    int b=0;
    int flag=0;
    cin >>x;
    cin >>y;
    for(int i=0;i<x.size();i++)
        a=a*2+x[i]-'0';
    for(int i=0;i<y.size();i++)
        b=b*2+y[i]-'0'; 
    if(a==0&&b!=0)
        cout<<-1;
    else cout<<abs(a-b); 
    return 0;
}

H.Until the Blue Moon Rises

题目大意：共有n个元素的数组，每次可以选择其中一个数字+,另一个数字-,询问能否在若干次操作后满足数组中所有元素均为素数。

思路：

根据哥德巴赫猜想：

1）任何一个大于的偶数都能被分解为个素数相加

2）任何一个大于的数都能被分解成个素数相加

分情况讨论：

当=时，当且仅当本身是素数时满足;

当=时，当两数之和为大于等于的偶数时满足，当两数之和为奇数时，假设其中一个数为，另一个数为素数时满足。

当时，当所有数字之和时满足，可以保证经过若干次操作以后任取个数都能满足数字之和大于。

#include <bits/stdc++.h>
using namespace std;
long long a[1050];
int main(){
    int n;
    cin>>n;
    long long sum = 0;
  for(int i=1;i<=n;i++){
      cin>>a[i];
      sum += a[i];
  }
  int flag = 1;
  if(n == 1){
      if(a[1]!=2){
          for(long long i=2;i<=sqrt(a[1]);i++){
           if(a[1]%i == 0){
               cout<<"No";
               flag = 0;
               break;
           }
        }
      }
       if(flag == 1){
           if(a[1]!=1)
           cout<<"Yes";
      else
           cout<<"No";
       }         
}  
  else if(n == 2){
      if(sum%2==0 && sum!=2)
          cout<<"Yes";
      else if(sum%2 == 0 && sum == 2)
          cout<<"No";
      else if(sum % 2==1){
          for(long long i=2;i<=sqrt(sum-2);i++){
           if((sum-2)%i == 0){
               cout<<"No";
               flag = 0;
               break;
        }
    }
          if(flag == 1){
          if(sum-2 != 1)
            cout<<"Yes";
          else
           cout<<"No";
        } 
           
      }
      
  }
  else if(n>=3){
       if(sum >= 2*n) 
        cout<<"Yes";
          else
        cout<<"No";
}
    
    return 0;
}

J-Fine Logic

题目大意：共有个数字，提供个偏序关系，要求构造个排列，使得每一个给出的偏序关系至少被其中一个排列满足。

思路：按照给出的关系建有向图，用拓扑序列检查是否有环。如果没有可以另=和它的拓扑序，如果有环令=，输出分别到和到（这两种排列包括了所有偏序情况）。

AC代码：

#include <bits/stdc++.h>
using namespace std;
const int N=1e6+10;
int e[N];
int ne[N];
int h[N];
int n,m,idx;
int r[N];
queue<int>q;
int ans;
int top[N];
void add(int a,int b){
    e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
 
void topsort(){
    for(int i=1;i<=n;i++){
        if(r[i]==0){
            q.push(i);
        }
    }
    while(q.empty()!=1){
        int x=q.front();
        top[ans]=x;
        ans++;
        q.pop();
        for(int i=h[x];i!=-1;i=ne[i]){
            int j=e[i];
            r[j]--;
            if(r[j]==0){
                q.push(j);
            }
        }
    }
    if(ans==n){
        cout<<1<<'\n';
        for(int i=0;i<ans;i++){
            cout<<top[i]<<' ';
        }
    }
    else{
        cout<<2<<'\n';
        for(int i=1;i<=n;i++){
            cout<<i<<' ';
        }
        cout<<'\n';
        for(int i=n;i>=1;i--){
            cout<<i<<' ';
        }
    }
}
 
int main()
{
    memset(h,-1,sizeof(h));
    cin>>n>>m;
    for(int i=1;i<=m;i++){
        int a,b;
        cin>>a>>b;
        r[b]++;
        add(a,b);
    }
    topsort();
    return 0;
}

D-Ama no Jaku

题目大意：给定只包含和的矩阵，设每一行构成的二进制值分别为,设每一列构成的二进制值为，每次操作可以使任意一行/任意一列元素取反，求能否在数次操作内满足，求出最少操作次数。

思路：对比以下四种情况的操作次数，取最小

1）第一行先取反，矩阵变成全

2）矩阵变成全

3）第一行先取反，矩阵变成全

4）矩阵变成全

每种情况把每一行/每一列的第一个元素与目标数字（/）进行比较，不同就整行/整列取反，最后扫一遍数组看能不能变成全/全，调用四次操作函数。

AC代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N=2010;
const int inf=0x3f3f3f3f3f3f3f3f;
int n;
int a[N][N];
int op(int f,int num)
{
    int cnt=0;
    int b[N][N];
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
            b[i][j]=a[i][j];
    }
    if(f==1)
    {
        cnt++;
        for(int i=1;i<=n;i++)
            b[i][1]^=1;
    }
    for(int i=1;i<=n;i++)
    {
        if(b[i][1]!=num)
        {
            cnt++;
            for(int j=1;j<=n;j++)
                b[i][j]^=1;
        }
    }
    for(int i=1;i<=n;i++)
    {
        if(b[1][i]!=num)
        {
            cnt++;
            for(int j=1;j<=n;j++)
                b[j][i]^=1;
        }
    }
    int flag=1;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
            if(b[i][j]!=num) flag=0;
    }
    if(flag==0)
        return inf;
    else return cnt;
}
signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int ans=inf;
    cin >>n;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            char x;
            cin >>x;
            a[i][j]=x-'0';
        }
    }
    ans=min(ans,op(0,0));
    ans=min(ans,op(1,0));
    ans=min(ans,op(0,1));
    ans=min(ans,op(1,1));
    if(ans==inf)
        cout<<-1<<'\n';
    else cout<<ans<<'\n';
    return 0;
}