3.13-777div2

发表于 | 分类于 |

3.13的cfdiv2

B.Madoka and the Elegant Gift

给定n*m的矩阵，矩阵中仅含0、1，求是否存在两个极大的、仅由1组成的子矩阵相交（若子矩阵扩张后无法满足都由1组成，则称其为极大矩阵）（若两个矩阵存在重叠部分，则称其相交）

题解：

1.我的思路，简单想一下有相交矩阵的情况，一行一行看的话，就相当于上下两行的极大行起始点不重合且有相交，故对每一行连通行的起始坐标后，再遍历每一行，进行比较，时间复杂度大概是O(n*m+n*m*m),这题数据比较小，给我暴力过了

（反思一下，循环里变量名都能写错，de了半天bug，麻）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
#include<algorithm>
#include<cmath>
#include<iostream>
#include<cstring>
#include<set>
#include<queue>
#include<vector>
#include<string>
#include<map>
#include<cstdio>
#include<list>
#include<unordered_set>
using namespace std;
using ll = long long;
ll T;
ll n;
ll m;
ll a[105][105];
vector<ll> be[105];
vector<ll>en[105];
int main()
{
  scanf("%lld", &T);
  while (T--)
  {
    scanf("%lld %lld", &n, &m);
    for (ll i = 1; i <= n; i++)
    {
      be[i].clear();
      en[i].clear();
      a[i][0] = 0;
      a[i][m + 1] = 0;
      for (ll j = 1; j <= m; j++)
      {
        scanf("%1lld", &a[i][j]);
      }
      for (ll j = 0; j <= m; j++)
      {
        if (a[i][j] == 0 && a[i][j + 1] == 1)
        {
          be[i].push_back(j+1);
        }
        else if (a[i][j] == 1 && a[i][j + 1] == 0)
        {
          en[i].push_back(j);
        }
      }
    }
    bool flag = 1;
    for (ll i = 2; i < n; i++)
    {
      for (ll j = 0; j < be[i].size(); j++)
      {
        for (ll k = 0; k < be[i + 1].size(); k++)
        {
          if (be[i][j] == be[i + 1][k] && en[i][j] == en[i + 1][k])
          {
            continue;
          }
          if (be[i][j] >= be[i + 1][k] && be[i][j] < en[i + 1][k])
          {
            flag = 0;
            break;
          }
          else if (be[i][j] > be[i + 1][k] && be[i][j] <= en[i + 1][k])
          {
            flag = 0;
            break;
          }
        }
        for (ll k = 0; k < be[i - 1].size(); k++)
        {
          if (be[i][j] == be[i - 1][k] && en[i][j] == en[i - 1][k])
          {
            continue;
          }
          if (be[i][j] >= be[i - 1][k] && be[i][j] < en[i - 1][k])
          {
            flag = 0;
            break;
          }
          else if (be[i][j] > be[i - 1][k] && be[i][j] <= en[i - 1][k])
          {
            flag = 0;
            break;
          }
        }
        
      }
      
    }
    if (n >= 2)
    {for (ll i = 1; i <= 1; i++)
    {
      for (ll j = 0; j < be[i].size(); j++)
      {
        for (ll k = 0; k < be[i + 1].size(); k++)
        {
          if (be[i][j] == be[i + 1][k] && en[i][j] == en[i + 1][k])
          {
            continue;
          }
          if (be[i][j] >= be[i + 1][k] && be[i][j] < en[i + 1][k])
          {
            flag = 0;
            break;
          }
          else if (be[i][j] > be[i + 1][k] && be[i][j] <= en[i + 1][k])
          {
            flag = 0;
            break;
          }
        }
      }
    }
    for (ll i = n; i <= n; i++)
    {
      for (ll j = 0; j < be[n].size(); j++)
      {
        for (ll k = 0; k < be[i - 1].size(); k++)
        {
          if (be[i][j] == be[i - 1][k] && en[i][j] == en[i - 1][k])
          {
            continue;
          }
          if (be[i][j] >= be[i - 1][k] && be[i][j] < en[i - 1][k])
          {
            flag = 0;
            break;
          }
          else if (be[i][j] > be[i - 1][k] && be[i][j] <= en[i - 1][k])
          {
            flag = 0;
            break;
          }
        }
      }
    }

    }
    
    
    if (flag)
    {
      cout << "YES\n";
    }
    else
    {
      cout << "NO\n";
    }
  }
  return 0;
}

2.正解思路：同样思考下出现极大块相交的情况，易知一定会形成凸型，且若形成凸型则必定形成极大块相交情况，故我们统计是否出现凸型

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
#include<algorithm>
#include<cmath>
#include<iostream>
#include<cstring>
#include<set>
#include<queue>
#include<vector>
#include<string>
#include<map>
#include<cstdio>
#include<list>
#include<unordered_set>
using namespace std;
using ll = long long;
ll T;
ll n;
ll m;
ll a[105][105];
int main()
{
  scanf("%lld", &T);
  while (T--)
  {
    scanf("%lld %lld", &n, &m);
    for (ll i = 1; i <= n; i++)
    {
      a[i][0] = 0;
      a[i][m + 1] = 0;
      for (ll j = 1; j <= m; j++)
      {
        scanf("%1lld", &a[i][j]);

      }
    }
    bool flag = 1;
    ll cnt;
    for (ll i = 1; i < n; i++)
    {
      for (ll j = 2; j <= m; j++)
      {
        if ((cnt = a[i][j] + a[i][j - 1] + a[i + 1][j] + a[i + 1][j - 1]) == 3)
        {
          flag = 0;
          break;
        }
      }
    }
    if (flag)
    {
      printf("YES\n");
    }
    else
    {
      printf("NO\n");
    }
  }
  return 0;
}

C.Madoka and Childish Pranks

题面:给定一个n*m的矩阵，初始时都为0，每次操作可以选定一块矩形区域，将该区域涂成象棋棋盘的样式（即左上角为0，上下左右01交替），给定最终的图案，求操作序列

PS：不要求最少次数、每次操作要求左上角坐标与右下角左标）

题解：

简单的bfs，和之前的油画思路一样，倒着涂就好，即涂完之后标记一个万能色，而操作简化成两种，要么划一个1X2的矩阵，要么划一个2X1的矩阵，每次操作后将万能色的坐标压入）

我一开始题意理解错了，以为棋盘的左上角原本就要是0才能涂，wa了好几发。。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
#include<algorithm>
#include<cmath>
#include<iostream>
#include<cstring>
#include<set>
#include<queue>
#include<vector>
#include<string>
#include<map>
#include<cstdio>
#include<list>
#include<unordered_set>
using namespace std;
using ll = long long;
ll T;
ll n;
ll m;
ll curx, cury, nexx, nexy;
ll a[105][105];
vector<pair<ll, ll>>ans1;
vector<pair<ll, ll>>ans2;
void bfs()
{
  queue<pair<ll, ll>>q;
  for (ll i = 1; i <= n; i++)
  {
    for (ll j = 1; j <= m; j++)
    {
      if (a[i][j] == 1)
      {
        if (i > 1 && a[i - 1][j] == 0)
        {
          q.push({ i,j });
        }
        if (j > 1 && a[i][j - 1] == 0)
        {
          q.push({ i,j });
        }
      }
    }
  }
  while (!q.empty())
  {
    curx = q.front().first;
    cury = q.front().second;
    q.pop();
    if (a[curx][cury] == 1)
    {
      if (curx > 1 && (a[curx - 1][cury] == 0||a[curx-1][cury]==3))
      {
        ans1.push_back({ curx - 1,cury });
        ans2.push_back({ curx,cury });
        a[curx - 1][cury] = 0;
        a[curx][cury] = 3;
        q.push({ curx - 1,cury });
        q.push({ curx,cury });
      }
      if (cury > 1 && (a[curx][cury - 1] == 0 || a[curx ][cury-1] == 3))
      {
        ans1.push_back({ curx ,cury - 1 });
        ans2.push_back({ curx,cury });
        a[curx][cury - 1] = 0;
        a[curx][cury] = 3;
        q.push({ curx,cury - 1 });
        q.push({ curx,cury });
      }
    }
    else
    {
      if (curx < n && a[curx + 1][cury] == 1)
      {
        ans1.push_back({ curx ,cury });
        ans2.push_back({ curx + 1,cury });
        a[curx + 1][cury] = 3;
        a[curx][cury] = 0;
        q.push({ curx + 1,cury });
        q.push({ curx,cury });
      }
      if (cury < m && a[curx][cury + 1] == 1)
      {
        ans1.push_back({ curx ,cury });
        ans2.push_back({ curx,cury + 1 });
        a[curx][cury + 1] = 3;
        a[curx][cury] = 0;
        q.push({ curx,cury + 1 });
        q.push({ curx,cury });
      }
 
    }
  }
}
int main()
{
  scanf("%lld", &T);
  while (T--)
  {
    ans1.clear();
    ans2.clear();
    scanf("%lld %lld", &n, &m);
    for (ll i = 1; i <= n; i++)
    {
      for (ll j = 1; j <= m; j++)
      {
        scanf("%1lld", &a[i][j]);
      }
    }
    bfs();
 
    bool flag = 1;
    for (ll i = 1; i <= n; i++)
    {
      for (ll j = 1; j <= m; j++)
      {
        if (a[i][j] == 1)
        {
          flag = 0;
          break;
        }
      }
    }
    if (flag == 0)
    {
      printf("-1\n");
    }
    else
    {
      printf("%d\n", ans1.size());
      for (ll i = 1;i<=ans1.size();i++)
      {
        printf("%lld %lld %lld %lld\n", ans1[ans1.size()-i].first, ans1[ans1.size()-i].second, ans2[ans1.size() - i].first, ans2[ans1.size() - i].second);
      }
    }
  }
  return 0;
}

代码可以简化，如果（1,1）是黑色直接printf(“-1”)，然后每次只压入万能色或白色就好

其实都用不上bfs，直接遍历就好了，写bfs反而麻烦了。。

PS：看了一个红名大佬的码，初始状态都为0，他从下到上，从右往左涂，如果当前格为0，直接输出两边当前格坐标（强制当前格为白），若当前格为1，若行数>1，则向上涂，否则向左涂，保证当前步影响会被下一步覆盖，易知操作数一定为n*m-1,（1,1)不用涂，开vector存储答案都省了。。

D.Madoka and the Best School in Russia

题面：给定x、d，将x分解成几个数的乘积（这几个数都满足是d的倍数而不是d平方的倍数），分解方法超过2，则printYES，否则printNO

题解：

1.我们只需要知道分解方法是否超过2，显然，可以将x=q*d的p次方，则q一定不为d的倍数，若p≥2,我们一定能将x分解成x=（q*d）*d…..

即我们已经得到了一种分解方式

若p==0,则无解

若p==1，则无解

故我们继续讨论p≥2的情况

1.若q可以分解成两个数（≠1、q）的乘积（即q非质数），则我们可以将q=x*y，x、y一定不为d的倍数(若是，则q也是),得到一种新的分解方式，YES

2.若q为质数，则q无法继续分解，若d为质数，则NO。

3.是否有可能减少分解数的个数来得到新的解？若p==2，则不行，NO。否则将d分解成a*b，即d非质数，若p≥4，则x=（a*d）*（b*d）*（q*d），为什么a、b不能*q？—怕凑出q==b，a*q==d，即q是d的因子的情况，总之，若p≥4，则直接YES

3.若p==3,则分解出的a、b必须给q*d一个，即x=（a*d)*(q*b*d)，我们需要求证，d是否存在一个因子，满足q*b不为d的倍数，若存在，则YES，若不存在，则NO

易知q为质数，d不为质数，若d与q互质，则YES

若d与q不互质，且q是质数，则d是q的倍数，d=n*q，若n≠q，则x=（q*q*d）*（n*d），即d不为q的平方时，YES

若n==q，则d=q*q，d分配时会出现d平方，NO

难点在于p==3时的分析，以及互质、质数的关系的运用

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
#include<algorithm>
#include<cmath>
#include<iostream>
#include<cstring>
#include<set>
#include<queue>
#include<vector>
#include<string>
#include<map>
#include<cstdio>
#include<list>
#include<unordered_set>
using namespace std;
using ll = long long;
ll T;
ll n;
ll m;
ll x, d;
ll gcd(ll x, ll y)
{
  return y == 0 ? x : gcd(y, x % y);
}
bool isprime(ll x)
{
  if (x == 1) return 1;
  for (ll i = 2; i * i <= x; i++)
  {
    if (x % i == 0)
      return 0;
  }
  return 1;
}
void solve()
{
  ll p = 0;
  while (x % d == 0)
  {
    x /= d;
    p++;
  }
  if (p <= 1)
  {
    cout << "NO\n";
  }
  else
  {
    if (!isprime(x))
    {
      cout << "YES\n";
    }
    else if (isprime(d))
    {
      cout << "NO\n";
    }
    else if (p >= 4)
    {
      cout << "YES\n";
    }
    else if (p == 2)
    {
      cout << "NO\n";
    }
    else if (gcd(x, d) == 1)
    {
      cout << "YES\n";
    }
    else if (d == x * x)
    {
      cout << "NO\n";
    }
    else
    {
      cout << "YES\n";
    }
  }
}
int main()
{
  cin >> T;
  while (T--)
  {
    cin >> x >> d;
    solve();
  }
  return 0;
}

要注意1也算质数，return 1

2.官方题解：dp做法，我们先找到x所有满足是d的倍数而不是d平方倍数的因子，规定dp[i]为将x分解成i的方法数，易知dp[i]+=dp[i*k](k为x的因子），而该转移方程没法保证不重复，如2可分解成1、1、2或2、1、1,故我们规定除的数必须大于等于（初始为1，故大于等于）前一次除的数，故添加一维表示当前除的数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
#include<algorithm>
#include<cmath>
#include<iostream>
#include<cstring>
#include<set>
#include<queue>
#include<vector>
#include<string>
#include<map>
#include<cstdio>
#include<list>
#include<unordered_set>
using namespace std;
using ll = long long;
ll T;
ll n;
ll m;
ll x, d;
bool isbeautiful(ll x)
{
  return ((x % d == 0) && (x % (d * d) != 0)) ? 1 : 0;
}
bool  solve()
{
  map<pair<ll, ll>,ll > mp;
  mp[{x, 1}] = 1;//初始化dp
  vector<ll> del;//存储x符合条件的因子
  for (ll i = 1; i * i <= x; i++)
  {
    if (x % i == 0)
    {
      if (isbeautiful(i)) del.push_back(i);
      if (i * i != x && isbeautiful(x / i))del.push_back(x / i);
    }
  }
  ll ans = 0;
  while (!mp.empty())
  {
    auto it = mp.rbegin();//拿出pair的first最大的状态
    ll cur = it->first.first, predel = it->first.second, cnt = it->second;
    if (cur == 1)
      ans += cnt;
    for (auto curdel : del)
    {
      if (curdel >= predel && cur % curdel == 0)
      {
        mp[{cur / curdel, curdel}] += cnt;
      }
    }
    mp.erase(it->first);
  }
  return ans >= 2 ? 1 : 0;
}
int main()
{
  cin >> T;
  while (T--)
  {
    cin >> x >> d;
    if (solve())
      cout << "YES\n";
    else
    {
      cout << "NO\n";
    }
  }
  return 0;
}

注意用map来实现dp