codeforces #585 div2 ABCD

A. Yellow Cards

Description

Solution

最小值：先给每个人k-1张黄牌，剩下再判断。

最大值：先给k值最小的安排满，再考虑k小的组。

B. The Number of Products

Description

给出一个长为n的序列a。

求所有的字串$a[l,r]$满足$a[l] imes a[l+1] imes ... imes a[r] lt 0, l le r$

Solution

设$dp1[i]$表示以$a[i]$结尾的字串个数满足条件1

同样，设dp2满足条件2。

转移方程

$$a[i] gt 0 ightarrow dp1[i]=dp1[i-1]+1,dp2[i]=dp2[i-1]$$

$$a[i] lt 0 ightarrow dp1[i]=dp1[i-1],dp2[i]=dp2[i-1]+1$$

$$a[i] = 0 ightarrow dp1[i]=dp2[i]=0$$

  1 #include <algorithm>
  2 #include <cctype>
  3 #include <cmath>
  4 #include <cstdio>
  5 #include <cstdlib>
  6 #include <cstring>
  7 #include <iostream>
  8 #include <map>
  9 #include <numeric>
 10 #include <queue>
 11 #include <set>
 12 #include <stack>
 13 #if __cplusplus >= 201103L
 14 #include <unordered_map>
 15 #include <unordered_set>
 16 #endif
 17 #include <vector>
 18 #define lson rt << 1, l, mid
 19 #define rson rt << 1 | 1, mid + 1, r
 20 #define LONG_LONG_MAX 9223372036854775807LL
 21 #define pblank putchar(' ')
 22 #define ll LL
 23 #define fastIO ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
 24 using namespace std;
 25 typedef long long ll;
 26 typedef long double ld;
 27 typedef unsigned long long ull;
 28 typedef pair<int, int> P;
 29 int n, m, k;
 30 const int maxn = 2e5 + 10;
 31 template <class T>
 32 inline T read()
 33 {
 34     int f = 1;
 35     T ret = 0;
 36     char ch = getchar();
 37     while (!isdigit(ch))
 38     {
 39         if (ch == '-')
 40             f = -1;
 41         ch = getchar();
 42     }
 43     while (isdigit(ch))
 44     {
 45         ret = (ret << 1) + (ret << 3) + ch - '0';
 46         ch = getchar();
 47     }
 48     ret *= f;
 49     return ret;
 50 }
 51 template <class T>
 52 inline void write(T n)
 53 {
 54     if (n < 0)
 55     {
 56         putchar('-');
 57         n = -n;
 58     }
 59     if (n >= 10)
 60     {
 61         write(n / 10);
 62     }
 63     putchar(n % 10 + '0');
 64 }
 65 template <class T>
 66 inline void writeln(const T &n)
 67 {
 68     write(n);
 69     puts("");
 70 }
 71 template <typename T>
 72 void _write(const T &t)
 73 {
 74     write(t);
 75 }
 76 template <typename T, typename... Args>
 77 void _write(const T &t, Args... args)
 78 {
 79     write(t), pblank;
 80     _write(args...);
 81 }
 82 template <typename T, typename... Args>
 83 inline void write_line(const T &t, const Args &... data)
 84 {
 85     _write(t, data...);
 86 }
 87 int dp1[maxn], dp2[maxn], a[maxn];
 88 int main(int argc, char const *argv[])
 89 {
 90 #ifndef ONLINE_JUDGE
 91     freopen("in.txt", "r", stdin);
 92     // freopen("out.txt", "w", stdout);
 93 #endif
 94     n = read<int>();
 95     for (int i = 1; i <= n; i++)
 96         a[i] = read<int>();
 97 
 98     for (int i = 1; i <= n; i++)
 99     {
100         if (a[i] > 0)
101         {
102             dp1[i] = dp1[i - 1] + 1;
103             dp2[i] = dp2[i - 1];
104         }
105         else if (a[i] < 0)
106         {
107             dp2[i] = dp1[i - 1] + 1;
108             dp1[i] = dp2[i - 1];
109         }
110         else
111             dp1[i] = dp2[i] = 0;
112     }
113     ll res1 = accumulate(dp1 + 1, dp1 + 1 + n, 0LL), res2 = accumulate(dp2 + 1, dp2 + 1 + n, 0LL);
114     write_line(res2, res1);
115     return 0;
116 }

View Code

C. Swap Letters

Description

给出两个仅含a,b的字符串s,t。每次可以选择i,j使得$swap(s[i],t[j])$

问能否使s=t，如果可以输出最小的次数及对应交换方案。否则输出-1

Solution

有点像最近的一道B2，如果之前做过这一场那道B2肯定能出。

考虑s=aa,t=bb,那么直接交换s[1],t[2]即可，这种情况只需要一次。

s=ab，t=ba，先swap[s[1],t[1]),再swap(s[1],t[2])。需要两次交换。

  1 #include <algorithm>
  2 #include <cctype>
  3 #include <cmath>
  4 #include <cstdio>
  5 #include <cstdlib>
  6 #include <cstring>
  7 #include <iostream>
  8 #include <map>
  9 #include <numeric>
 10 #include <queue>
 11 #include <set>
 12 #include <stack>
 13 #if __cplusplus >= 201103L
 14 #include <unordered_map>
 15 #include <unordered_set>
 16 #endif
 17 #include <vector>
 18 #define lson rt << 1, l, mid
 19 #define rson rt << 1 | 1, mid + 1, r
 20 #define LONG_LONG_MAX 9223372036854775807LL
 21 #define pblank putchar(' ')
 22 #define ll LL
 23 #define fastIO ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
 24 using namespace std;
 25 typedef long long ll;
 26 typedef long double ld;
 27 typedef unsigned long long ull;
 28 typedef pair<int, int> P;
 29 int n, m, k;
 30 const int maxn = 2e5 + 10;
 31 template <class T>
 32 inline T read()
 33 {
 34     int f = 1;
 35     T ret = 0;
 36     char ch = getchar();
 37     while (!isdigit(ch))
 38     {
 39         if (ch == '-')
 40             f = -1;
 41         ch = getchar();
 42     }
 43     while (isdigit(ch))
 44     {
 45         ret = (ret << 1) + (ret << 3) + ch - '0';
 46         ch = getchar();
 47     }
 48     ret *= f;
 49     return ret;
 50 }
 51 template <class T>
 52 inline void write(T n)
 53 {
 54     if (n < 0)
 55     {
 56         putchar('-');
 57         n = -n;
 58     }
 59     if (n >= 10)
 60     {
 61         write(n / 10);
 62     }
 63     putchar(n % 10 + '0');
 64 }
 65 template <class T>
 66 inline void writeln(const T &n)
 67 {
 68     write(n);
 69     puts("");
 70 }
 71 template <typename T>
 72 void _write(const T &t)
 73 {
 74     write(t);
 75 }
 76 template <typename T, typename... Args>
 77 void _write(const T &t, Args... args)
 78 {
 79     write(t), pblank;
 80     _write(args...);
 81 }
 82 template <typename T, typename... Args>
 83 inline void write_line(const T &t, const Args &... data)
 84 {
 85     _write(t, data...);
 86 }
 87 char s[maxn], t[maxn];
 88 set<int> pos, a, b;
 89 vector<P> r;
 90 int main(int argc, char const *argv[])
 91 {
 92 #ifndef ONLINE_JUDGE
 93     freopen("in.txt", "r", stdin);
 94     // freopen("out.txt", "w", stdout);
 95 #endif
 96     fastIO;
 97     cin >> n;
 98     cin >> s >> t;
 99     int aa = 0, bb = 0;
100     for (int i = 0; i < n; i++)
101     {
102         if (s[i] == 'a')
103             ++aa;
104         else
105             ++bb;
106         if (t[i] == 'a')
107             ++aa;
108         else
109             ++bb;
110         if (s[i] != t[i])
111         {
112             if (s[i] == 'a')
113                 a.emplace(i);
114             else
115                 b.emplace(i);
116         }
117     }
118     if ((aa & 1) || (bb & 1))
119     {
120         puts("-1");
121         return 0;
122     }
123     while (a.size() > 1)
124     {
125         int t1 = *a.begin();
126         a.erase(t1);
127         int t2 = *a.begin();
128         a.erase(t2);
129         r.emplace_back(t1, t2);
130         swap(s[t1], t[t2]);
131     }
132     while (b.size() > 1)
133     {
134         int t1 = *b.begin();
135         b.erase(t1);
136         int t2 = *b.begin();
137         b.erase(t2);
138         r.emplace_back(t1, t2);
139         swap(s[t1], t[t2]);
140     }
141     if (a.size() != b.size())
142     {
143         puts("-1");
144         return 0;
145     }
146     if (a.size())
147     {
148         int t1 = *a.begin(), t2 = *b.begin();
149         r.emplace_back(t1, t1);
150         r.emplace_back(t2, t1);
151     }
152     cout << r.size() << "
";
153     for (auto x : r)
154         cout << x.first + 1 << " " << x.second + 1 << "
";
155     return 0;
156 }

View Code

D. Ticket Game

Description

给出一个长度为偶数n的字符序列。包含数字和?。

A喜欢前一半的数字和不等于后一半数字之和。

B恰恰相反。

A,B轮流选择一个?变成一个数字，问最终谁能得到这一串序列。

Solution

没想到解法，补的题。

计算前一半和pre,后一半和last。

前一半?数目l，后一半？数目r。

pre=last&&l=r肯定B赢。

pre=last&&l!=r肯定A赢。

pre!=last的情况，假设pre<last。

如果l<=r那么A一定赢。

l>r时，前r次游戏中，A一定尽可能拉大last的值将后半部分r变为9，而B只能紧跟差距也使前面的r个问号变为9。

那么剩下(l-r)/2次操作，如果(l-r)/2=last-pre,不论A怎么放x，B总能找到一个数字y使得x+y=9,从而使最终pre=last。

  1 #include <algorithm>
  2 #include <cctype>
  3 #include <cmath>
  4 #include <cstdio>
  5 #include <cstdlib>
  6 #include <cstring>
  7 #include <iostream>
  8 #include <map>
  9 #include <numeric>
 10 #include <queue>
 11 #include <set>
 12 #include <stack>
 13 #if __cplusplus >= 201103L
 14 #include <unordered_map>
 15 #include <unordered_set>
 16 #endif
 17 #include <vector>
 18 #define lson rt << 1, l, mid
 19 #define rson rt << 1 | 1, mid + 1, r
 20 #define LONG_LONG_MAX 9223372036854775807LL
 21 #define pblank putchar(' ')
 22 #define ll LL
 23 #define fastIO ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
 24 using namespace std;
 25 typedef long long ll;
 26 typedef long double ld;
 27 typedef unsigned long long ull;
 28 typedef pair<int, int> P;
 29 int n, m, k;
 30 const int maxn = 2e5 + 10;
 31 template <class T>
 32 inline T read()
 33 {
 34     int f = 1;
 35     T ret = 0;
 36     char ch = getchar();
 37     while (!isdigit(ch))
 38     {
 39         if (ch == '-')
 40             f = -1;
 41         ch = getchar();
 42     }
 43     while (isdigit(ch))
 44     {
 45         ret = (ret << 1) + (ret << 3) + ch - '0';
 46         ch = getchar();
 47     }
 48     ret *= f;
 49     return ret;
 50 }
 51 template <class T>
 52 inline void write(T n)
 53 {
 54     if (n < 0)
 55     {
 56         putchar('-');
 57         n = -n;
 58     }
 59     if (n >= 10)
 60     {
 61         write(n / 10);
 62     }
 63     putchar(n % 10 + '0');
 64 }
 65 template <class T>
 66 inline void writeln(const T &n)
 67 {
 68     write(n);
 69     puts("");
 70 }
 71 template <typename T>
 72 void _write(const T &t)
 73 {
 74     write(t);
 75 }
 76 template <typename T, typename... Args>
 77 void _write(const T &t, Args... args)
 78 {
 79     write(t), pblank;
 80     _write(args...);
 81 }
 82 template <typename T, typename... Args>
 83 inline void write_line(const T &t, const Args &... data)
 84 {
 85     _write(t, data...);
 86 }
 87 char s[maxn];
 88 int pre, last;
 89 int r, l;
 90 int main(int argc, char const *argv[])
 91 {
 92 #ifndef ONLINE_JUDGE
 93     freopen("in.txt", "r", stdin);
 94     // freopen("out.txt", "w", stdout);
 95 #endif
 96     fastIO;
 97     cin >> n;
 98     cin >> s + 1;
 99     for (int i = 1; i <= n / 2; i++)
100         if (s[i] == '?')
101             ++l;
102         else
103             pre += s[i] - '0';
104     for (int i = n / 2 + 1; i <= n; i++)
105         if (s[i] == '?')
106             ++r;
107         else
108             last += s[i] - '0';
109 
110     if (pre == last)
111     {
112         if (l == r)
113             cout << "Bicarp
";
114         else
115             cout << "Monocarp
";
116         return 0;
117     }
118     else
119     {
120         if (pre > last)
121             swap(pre, last), swap(l, r);
122         if (l <= r)
123             cout << "Monocarp
";
124         else
125         {
126             int left = last - pre;
127             l -= r;
128             l /= 2;
129             if (l * 9 == left)
130                 cout << "Bicarp
";
131             else
132                 cout << "Monocarp
";
133         }
134     }
135     return 0;
136 }

View Code