Znzryb's Blog
0%

Posted on Edited on

思路讲解

CF-1004-B. Two Large Bags

和这题也没那么像，但是确实这种有操作，而且操作没有次数限制的，一定要找出一种操作模式，虽然说有可能浪费，但是绝对不会恶化现有情况，这是我对这类题目的自己的一点感悟

那么，这道题目，我们发现，如果有一个逆序对（比如说下面这个5，4）

1
2
8
4 5 4 5 4 5 4 5

我们肯定就要处理这个，我们要让5变小

但是这个还要判断逆序对呀，能不能再进一步，对所有数都进行一次这个操作？

我们可以证明，这个操作一定是优的，因为他让前面的数减小了

于是我们顺着操作一遍，再判断是否是有序的就好了

AC代码

https://codeforces.com/contest/2060/submission/305951401

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
// Problem: D. Subtract Min Sort
// Contest: Codeforces - Codeforces Round 998 (Div. 3)
// URL: https://codeforces.com/contest/2060/problem/D
// Memory Limit: 256 MB
// Time Limit: 2000 ms
// by znzryb
//
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
#define FOR(i, a, b) for (int i = (a); i <= (b); ++i)
#define ROF(i, a, b) for (int i = (a); i >= (b); --i)
#define all(x) x.begin(), x.end()
#define CLR(i, a) memset(i, a, sizeof(i))
#define fi first
#define se second
#define pb push_back
#define SZ(a) ((int)a.size())

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll> pll;
typedef array<ll, 3> arr;
typedef double DB;
typedef pair<DB, DB> pdd;
constexpr ll MAXN = static_cast<ll>(2e5) + 10, INF = static_cast<ll>(5e18) + 3;

ll N, T, A[MAXN], backup[MAXN];

inline void solve() {
  cin >> N;
  FOR(i, 1, N) { cin >> A[i]; }
  if (A[1] > A[2]) {
    cout << "NO\n";
    return;
  }
  // 我们可以证明，这个操作一定是优的，因为他让前面的数减小了
  FOR(i, 1, N - 1) {
    ll t1 = A[i] - min(A[i], A[i + 1]), t2 = A[i + 1] - min(A[i], A[i + 1]);
    A[i] = t1;
    A[i + 1] = t2;
  }
  FOR(i, 1, N) { backup[i] = A[i]; }
  sort(A + 1, A + 1 + N);
  FOR(i, 1, N) {
    if (backup[i] != A[i]) {
      cout << "NO\n";
      return;
    }
  }
  cout << "YES\n";
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  cin >> T;
  while (T--) {
    solve();
  }
  return 0;
}
/*
AC
https://codeforces.com/contest/2060/submission/305951401
*/

心路历程（WA，TLE，MLE……）

Posted on Edited on

思路讲解

没有在X中的一点，任何一个点都到达不了，因为在有向图中你不发出边是到达不了任何点的

如果所有点都在X中，那么就选择一个q1（X[i]==1 时的i），一个q2（X[i]==N 时的i），他们的曼哈顿距离≥N-1

但是在这个只有N条边的有向图上，你觉得q1到q2以及q2到q1的有向图路径都大于N-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
else {  // 这种情况难搞一点
    // 因为这种情况理论上来说甚至有可能每个点之间都相互联通在有向图上
    // 但我们可以利用曼哈顿距离的特性来解决
    ll q1=0, q2=0;
    FOR(i, 1, N) {
      if (X[i] == 1)
        q1 = i;
      else if (X[i] == N)
        q2 = i;
    }
    cout << "? " << q1 << ' ' << q2 << endl;
    ll dis1, dis2;
    cin >> dis1;
    if (dis1 < N - 1) {  // dis1比最小曼哈顿距离都小，肯定也不对
      cout << "! A" << endl;
      return true;
    }
    cout << "? " << q2 << ' ' << q1 << endl;
    cin >> dis2;
    if (dis2 < N - 1) {  // dis2比最小曼哈顿距离都小，肯定也不对
      cout << "! A" << endl;
      return true;
    }
    cout << "! B" << endl;
  }

AC代码

AC

https://codeforces.com/contest/2067/submission/305909277

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
// Problem: D. Object Identification
// Contest: Codeforces - Codeforces Round 1004 (Div. 2)
// URL: https://codeforces.com/contest/2067/problem/D
// Memory Limit: 256 MB
// Time Limit: 2000 ms
// by znzryb
//
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
#define FOR(i, a, b) for (int i = (a); i <= (b); ++i)
#define ROF(i, a, b) for (int i = (a); i >= (b); --i)
#define all(x) x.begin(), x.end()
#define CLR(i, a) memset(i, a, sizeof(i))
#define fi first
#define se second
#define pb push_back
#define SZ(a) ((int)a.size())
#define LOCAL

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll> pll;
typedef array<ll, 3> arr;
typedef double DB;
typedef pair<DB, DB> pdd;
constexpr ll MAXN = static_cast<ll>(2e5) + 10, INF = static_cast<ll>(5e18) + 3;

ll N, T, X[MAXN];
bool vis[MAXN];

inline bool solve() {
  cin >> N;
  if (N == -1) {
    return false;
  }
  FOR(i, 1, N) { vis[i] = false; }
  FOR(i, 1, N) {
    cin >> X[i];
    vis[X[i]] = true;
  }
  vector<ll> disN;  // 没有在X中出现的点
  ll app;           // 随便取一个出现过的点
  FOR(i, 1, N) {
    if (!vis[i])
      disN.pb(i);
    else
      app = i;
  }
  if (SZ(disN) >= 1) {
    // 没有在X中的一点，任何一个点都到达不了，因为在有向图中你不发出边是到达不了任何点的
    cout << "? " << disN[0] << ' ' << app << endl;
    ll dis;
    cin >> dis;
    if (dis == 0)
      cout << "! A" << endl;
    else
      cout << "! B" << endl;
  } else {  // 这种情况难搞一点
    // 因为这种情况理论上来说甚至有可能每个点之间都相互联通在有向图上
    // 但我们可以利用曼哈顿距离的特性来解决
    ll q1=0, q2=0;
    FOR(i, 1, N) {
      if (X[i] == 1)
        q1 = i;
      else if (X[i] == N)
        q2 = i;
    }
    cout << "? " << q1 << ' ' << q2 << endl;
    ll dis1, dis2;
    cin >> dis1;
    if (dis1 < N - 1) {  // dis1比最小曼哈顿距离都小，肯定也不对
      cout << "! A" << endl;
      return true;
    }
    cout << "? " << q2 << ' ' << q1 << endl;
    cin >> dis2;
    if (dis2 < N - 1) {  // dis2比最小曼哈顿距离都小，肯定也不对
      cout << "! A" << endl;
      return true;
    }
    cout << "! B" << endl;
  }
  return true;
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  cin >> T;
  while (T--) {
    bool flag = solve();
    if (!flag) return 0;
  }
  return 0;
}
/*
AC
https://codeforces.com/contest/2067/submission/305909277
*/

心路历程（WA，TLE，MLE……）

Posted on Edited on

思路讲解

https://codeforces.com/blog/entry/139415?locale=en

image

就只看最后一位数（因为最后一位数不会有进位什么的问题），就可以得到最多不会超过9次的结论

然后就直接暴力就好了，不知道题解后面在写什么

AC代码

https://codeforces.com/contest/2067/submission/305782258

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
// Problem: C. Devyatkino
// Contest: Codeforces - Codeforces Round 1004 (Div. 2)
// URL: https://codeforces.com/contest/2067/problem/C
// Memory Limit: 256 MB
// Time Limit: 2000 ms
// by znzryb
//
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
#define FOR(i, a, b) for (int i = (a); i <= (b); ++i)
#define ROF(i, a, b) for (int i = (a); i >= (b); --i)
#define all(x) x.begin(), x.end()
#define CLR(i, a) memset(i, a, sizeof(i))
#define fi first
#define se second
#define pb push_back
#define SZ(a) ((int)a.size())
#define LOCAL

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll> pll;
typedef array<ll, 3> arr;
typedef double DB;
typedef pair<DB, DB> pdd;
constexpr ll MAXN = static_cast<ll>(1e6) + 10, INF = static_cast<ll>(5e18) + 3;

ll N, T;
ll pow10[20];

inline void solve() {
  ll x;
  cin >> x;
  ll ans = 9;
  string s = to_string(x);
  N = SZ(s);
  FOR(i, 0, N - 1) {
    if (s[i] == '7') {
      cout << 0 << '\n';
      return;
    }
  }
  FOR(i, 1, N + 1) {
    ll add = pow10[i] - 1;
    ll t = x;
    FOR(j, 1, ans) {
      t += add;
      string ts = to_string(t);
      bool isBreak = false;
      FOR(k, 0, SZ(ts) - 1) {
        if (ts[k] == '7') {
          ans = j;
          // #ifdef LOCAL
          // FOR(lk, 0, SZ(ts) - 1) { cerr << ts[lk]; }
          // cerr << '\n';
          // #endif
          isBreak = true;
          break;
        }
      }
      if (isBreak) break;
    }
  }
  cout << ans << '\n';
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  cin >> T;
  pow10[0] = 1;
  FOR(i, 1, 18) { pow10[i] = pow10[i - 1] * 10; }
  while (T--) {
    solve();
    // #ifdef LOCAL
    // cerr << '\n';
    // #endif
  }
  return 0;
}
/*
AC
https://codeforces.com/contest/2067/submission/305782258
*/

心路历程（WA，TLE，MLE……）

Posted on Edited on

思路讲解

https://codeforces.com/blog/entry/139415?locale=en

基本就是官方题解的思路

我们可以证明可以进行二操作的时候一定是先进行二操作的（说白了就那些数，+1了总归和后面相等的概率大一点），而不是先进行一操作

把所有2操作进行完了再进行1操作，我们可以证明，我们一定要将一个等于a1的数字发送到bag B，否则B中所有数字都大于a1。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
while (idx <= N - 1) {
  if (A[idx] != A[idx + 1]) {
    cout << "No\n";
    return;
  } else {
    vis[A[idx + 1]] = true;
    idx += 2;  // 相当于将idx以及idx+1锁住(idx是因为要满足idx+1的需求，idx+1是因为移入了B)
    FOR(i, idx, N) {
      if (vis[A[i]]) {
        A[i] += 1;
      } else {
        break;
      }
    }
  }
// #ifdef LOCAL
  // FOR(i, 1, N) { cerr << A[i] << ' '; }
  // cerr << '\n';
// #endif
}
cout << "Yes\n";
}

AC代码

https://codeforces.com/contest/2067/submission/305772242

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
// Problem: B. Two Large Bags
// Contest: Codeforces - Codeforces Round 1004 (Div. 2)
// URL: https://codeforces.com/contest/2067/problem/B
// Memory Limit: 256 MB
// Time Limit: 1000 ms
// by znzryb
//
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
#define FOR(i, a, b) for (int i = (a); i <= (b); ++i)
#define ROF(i, a, b) for (int i = (a); i >= (b); --i)
#define all(x) x.begin(), x.end()
#define CLR(i, a) memset(i, a, sizeof(i))
#define fi first
#define se second
#define pb push_back
#define SZ(a) ((int)a.size())
#define LOCAL

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll> pll;
typedef array<ll, 3> arr;
typedef double DB;
typedef pair<DB, DB> pdd;
constexpr ll MAXN = static_cast<ll>(1e3) + 10, INF = static_cast<ll>(5e18) + 3;

ll N, M, T, A[MAXN], vis[MAXN];

inline void solve() {
  cin >> N;
  FOR(i, 1, N) {
    cin >> A[i];
    vis[i] = false;  // B这个袋子里有没有这个数字？
  }
  sort(A + 1, A + 1 + N);
  ll idx = 1;
  while (idx <= N - 1) {
    if (A[idx] != A[idx + 1]) {
      cout << "No\n";
      return;
    } else {
      vis[A[idx + 1]] = true;
      idx += 2;  // 相当于将idx以及idx+1锁住
      FOR(i, idx, N) {
        if (vis[A[i]]) {
          A[i] += 1;
        } else {
          break;
        }
      }
    }
// #ifdef LOCAL
    // FOR(i, 1, N) { cerr << A[i] << ' '; }
    // cerr << '\n';
// #endif
  }
  cout << "Yes\n";
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  cin >> T;
  while (T--) {
    solve();
// #ifdef LOCAL
    // cerr << '\n';
// #endif
  }
  return 0;
}
/*
AC
https://codeforces.com/contest/2067/submission/305772242
*/

心路历程（WA，TLE，MLE……）

Posted on Edited on

思路讲解

其实还是挺简单的，不难，就是要分类讨论一下

前面搞着搞着搞错了，其实cnt→fi才是我们要加的

就是如果说我们不知道怎么排序或者什么，我们可以直接将答案算出来，取最大的答案就行了

1
2
3
4
5
6
7
8
9
10
11
12
lans -= 1;  // 先不管我们这个要做第二个操作的联通块
if (cnt.rbegin()->fi > 1) {
  // #ifdef LOCAL
  // cerr << lans << '\n';
  // #endif
  lans += cnt.rbegin()->fi;
} else if (cnt.rbegin()->fi == 1) {
  // #ifdef LOCAL
  // cerr<<"In if:" << i << ' ' << lans << '\n';
  // #endif
  lans += cnt.rbegin()->fi - 1;
}

AC代码

AC

https://codeforces.com/contest/2063/submission/305604041

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
// Problem: C. Remove Exactly Two
// Contest: Codeforces - Codeforces Round 1000 (Div. 2)
// URL: https://codeforces.com/contest/2063/problem/C
// Memory Limit: 256 MB
// Time Limit: 2000 ms
// by znzryb
//
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
#define FOR(i, a, b) for (int i = (a); i <= (b); ++i)
#define ROF(i, a, b) for (int i = (a); i >= (b); --i)
#define all(x) x.begin(), x.end()
#define CLR(i, a) memset(i, a, sizeof(i))
#define fi first
#define se second
#define pb push_back
#define SZ(a) ((int)a.size())
#define LOCAL

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll> pll;
typedef array<ll, 3> arr;
typedef double DB;
typedef pair<DB, DB> pdd;
constexpr ll MAXN = static_cast<ll>(2e5) + 10, INF = static_cast<ll>(5e18) + 3;

ll N, M, T;
vector<ll> g[MAXN];
ll edges[MAXN];

inline void solve() {
  cin >> N;
  map<ll, ll> cnt;
  // 初始化
  FOR(i, 1, N) { g[i].clear(); }
  FOR(i, 1, N - 1) {
    ll u, v;
    cin >> u >> v;
    g[u].pb(v);
    g[v].pb(u);
  }
  if (N == 2) {
    cout << 0 << '\n';
    return;
  }
  ll mx = 0, mxN = 1;
  FOR(i, 1, N) {
    edges[i] = SZ(g[i]);
    cnt[edges[i]] = cnt.find(edges[i]) == cnt.end() ? 1 : cnt[edges[i]] + 1;
  }
  ll ans = 0;
  map<ll, ll> backup = cnt;
  FOR(i, 1, N) {
    ll lans = edges[i];
    // #ifdef LOCAL
    // cerr << i << ' ' << edges[i] << '\n';
    // #endif
    cnt[edges[i]] -= 1;
    if (cnt[edges[i]] == 0) {
      cnt.erase(edges[i]);
    }
    FOR(j, 0, SZ(g[i]) - 1) {
      ll node = g[i][j];
      cnt[edges[node]] -= 1;
      cnt[edges[node] - 1] = cnt.find(edges[node] - 1) == cnt.end() ? 1 : cnt[edges[node] - 1] + 1;
      if (cnt[edges[node]] == 0) {
        cnt.erase(edges[node]);
      }
    }
    lans -= 1;  // 先不管我们这个要做第二个操作的联通块
    if (cnt.rbegin()->fi > 1) {
      // #ifdef LOCAL
      // cerr << lans << '\n';
      // #endif
      lans += cnt.rbegin()->fi;
    } else if (cnt.rbegin()->fi == 1) {
      // #ifdef LOCAL
      // cerr<<"In if:" << i << ' ' << lans << '\n';
      // #endif
      lans += cnt.rbegin()->fi - 1;
    }

    // #ifdef LOCAL
    // cerr << i << ' ' << lans << '\n';
    // #endif
    ans = max(ans, lans);
    cnt = backup;
  }
  cout << ans << '\n';
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  cin >> T;
  while (T--) {
    solve();
#ifdef LOCAL
    cerr << '\n';
#endif
  }
  return 0;
}
/*
AC
https://codeforces.com/contest/2063/submission/305604041
1
5
1 2
1 3
2 4
3 5

3

1
3
1 2
1 3

1
*/

心路历程（WA，TLE，MLE……）