codeforces #598 div3 ABCDF

A. Payment Without Change

Description

给出a个价值为n的硬币和b个价值为1的硬币，问凑出来s元钱。

Solution

$lfloor frac{s}{n} floor imes n + b geq s$

我还憨憨写了个二分。结果只是因为爆int。

  1 #include <algorithm>
  2 #include <numeric>
  3 #include <cctype>
  4 #include <cmath>
  5 #include <cstdio>
  6 #include <cstdlib>
  7 #include <cstring>
  8 #include <iostream>
  9 #include <map>
 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 = 1e5 + 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 main(int argc, char const *argv[])
 88 {
 89 #ifndef ONLINE_JUDGE
 90     freopen("in.txt","r", stdin);
 91     // freopen("out.txt","w", stdout);
 92 #endif
 93     int t = read<int>();
 94     while(t--){
 95         ll a = read<int>(), b = read<int>(), n = read<int>(), s = read<int>();
 96         ll l = 0, r = a;
 97         ll res = -1;
 98         while(l<=r){
 99             ll mid = l + r>>1;
100             if (mid*n>s)
101                 res = mid, r = mid - 1;
102             else
103                 l = mid + 1;
104         }
105         if (res==-1){
106             if (a*n+b>=s)
107                 puts("YES");
108             else
109                 puts("NO");
110         }
111         else{
112             if ((res-1)*n+b>=s)
113                 puts("YES");
114             else
115                 puts("NO");
116         }
117     }
118     return 0;
119 }
View Code

B. Minimize the Permutation

Description

给出一个长为n的序列，一共可以进行n-1个操作，操作$i$可以将序列$a[j],a[j+1]$交换。

求交换后字典序最小的序列。

Solution

卡了很久这个，想想真的憨，后来发现是忘了更新pos值。

每次将最小的值移到尽可能的前面，记录操作了哪些步骤，判断满足大小关系或者当前步骤已经操作过则break

  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 = 1e5 + 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 a[maxn], pos[maxn],vis[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     int t = read<int>();
 95     while (t--)
 96     {
 97         n = read<int>();
 98         for (int i = 1; i <= n; i++)
 99         {
100             a[i] = read<int>();
101             pos[a[i]] = i;
102             vis[i] = 0;
103         }
104         int left = n - 1;
105         pos[0] = 0;
106         for (int i = 1; i <n && left; i++)
107         {
108             for (int j = pos[i]-1; j >=1;j--){
109                 if (a[j]<a[j+1]||vis[j])
110                     break;
111                 --left;
112                 swap(a[j], a[j+1]);
113                 swap(pos[a[j]], pos[a[j+1]]);
114                 vis[j] = 1;
115             }
116         }
117         for (int i = 1; i <= n; i++)
118             write(a[i]), pblank;
119         puts("");
120     }
121     return 0;
122 }
View Code

C. Platforms Jumping

Description

给出长为n的一条河，以及m个不同长度木板。

小明每次最多可以跳p个单位长度。

问如何安排木板能使小明从0位置安全跳到n+1。

要求木板的交换顺序。

Solution

能否安全跳到最右边很好判定，不过如何安排木板就憨了。

先说一句dyznb。

首先考虑m块木板的总长度为sum，left为n-sum。

即left为小明需要跳跃的距离。

m块木板，加上0和n+1两个点。

一共有m+1个间隙，每个间隙平均分配$left/m$

如果有余数则将前面的部分加一个空隙。

注意判断边界。

  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 = 1e5 + 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 a[maxn], vis[maxn];
 88 int st[maxn];
 89 int main(int argc, char const *argv[])
 90 {
 91 #ifndef ONLINE_JUDGE
 92     freopen("in.txt", "r", stdin);
 93     // freopen("out.txt","w", stdout);
 94 #endif
 95     n = read<int>(), m = read<int>(), k = read<int>();
 96     int sum = 0;
 97     for (int i = 1; i <= m; i++)
 98         a[i] = read<int>(), sum += a[i];
 99     int left = n - sum;
100     int mod = left % (m + 1);
101     int div = left / (m + 1);
102     int pdiv = div;
103     if (mod)
104         ++pdiv;
105     if (pdiv >=k||(k==1&&left))
106         puts("NO");
107     else
108     {
109         if (left <=m + 1)
110         {
111 
112             int mod = left;
113             int now = 1;
114             for (int i = 1; i <= n;i++){
115                 if (mod){
116                     ++i;
117                     --mod;
118                 }
119                 for (int j = i, p = 0; p < a[now]; j++, p++)
120                     vis[j] = now;
121                 i += a[now] - 1;
122                 ++now;
123             }
124         }
125         else
126         {
127             int div = left / (m + 1);
128             int mod = left % (m + 1);
129             int now = 1;
130             for (int i = 1; i <= n;i++)
131             {
132                 if (mod)
133                 {
134                     ++i;
135                     --mod;
136                 }
137                 i += div;
138                 for (int j = i, p = 0; p < a[now]; j++, p++)
139                     vis[j] = now;
140                 i += a[now] - 1;
141                 ++now;
142             }
143         }
144         puts("YES");
145         for (int i = 1; i <= n; i++)
146             write(vis[i]), pblank;
147         puts("");
148     }
149     return 0;
150 }
View Code

D. Binary String Minimizing

Description

给出一个只包含01的字符串，可以进行k次操作。

每次操作可以将任意相邻两个值交换。

问最小的字典序。

Solution

讲道理这个题比BC简单好吧。

直接贪心，将0移到可能移到的最前面。

  1 #include <algorithm>
  2 #include <numeric>
  3 #include <cctype>
  4 #include <cmath>
  5 #include <cstdio>
  6 #include <cstdlib>
  7 #include <cstring>
  8 #include <iostream>
  9 #include <map>
 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 ll n, m, k;
 30 const int maxn = 1e6 + 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 lftz[maxn],lfto[maxn];
 89 int main(int argc, char const *argv[])
 90 {
 91 #ifndef ONLINE_JUDGE
 92     freopen("in.txt","r", stdin);
 93     // freopen("out.txt","w", stdout);
 94 #endif
 95     fastIO;
 96     int t;
 97     cin >> t;
 98     while(t--){
 99         cin >> n >> k;
100         cin >> s+1;
101         for (int i = 1; i <= n;i++)
102             if (s[i]=='1')
103                 lfto[i] = lfto[i - 1] + 1, lftz[i] = lftz[i - 1];
104             else
105                 lftz[i] = lftz[i - 1] + 1, lfto[i] = lfto[i - 1];
106         for (int i = 1; i <= n&&k;i++)
107             if (s[i]=='0'){
108                 if (lfto[i-1]<=k){
109                     int pre = lftz[i - 1];
110                     swap(s[pre + 1], s[i]);
111                     k -=lfto[i - 1];
112                 }
113                 else{
114                     swap(s[i], s[i-k]);
115                     k = 0;
116                 }
117             }
118         cout << s + 1 << "
";
119     }
120     return 0;
121 }
View Code

F. Equalizing Two Strings

Description

给出两个字符串s,t，每次可以选择等长的两个不要求相同的字串进行翻转。

问能否将st翻转为相同。

Solution

1，字母数量不同$ ightarrow NO$

2，字母数量相同且存在大于1$ ightarrow YES$

3，字母相同且数目均为1,则考虑两个序列奇偶性是否相同。

  1 #include <algorithm>
  2 #include <numeric>
  3 #include <cctype>
  4 #include <cmath>
  5 #include <cstdio>
  6 #include <cstdlib>
  7 #include <cstring>
  8 #include <iostream>
  9 #include <map>
 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 inline int lowbit(int x){
 88     return x & (-x);
 89 }
 90 struct node{
 91     char ch;
 92     int id;
 93     node(){}
 94     node(char ch,int id){
 95         this->ch = ch;
 96         this->id = id;
 97     }
 98 };
 99 char s1[maxn], s2[maxn];
100 int main(int argc, char const *argv[])
101 {
102 #ifndef ONLINE_JUDGE
103     freopen("in.txt","r", stdin);
104     // freopen("out.txt","w", stdout);
105 #endif
106     fastIO;
107     int t;
108     cin >> t;
109     while(t--){
110         cin >> n;
111         cin >> s1 >> s2;
112         vector<int> num1(26, 0), num2(26, 0);
113         for (int i = 0; i < n;i++)
114             num1[s1[i] - 'a']++, num2[s2[i] - 'a']++;
115         int f = 1;
116         for (int i = 0; i < 26;i++)
117             if (num1[i]!=num2[i]){
118                 f = 0;
119                 break;
120             }
121             else{
122                 if (num1[i]>1)
123                     f = 2;
124             }
125         if (!f)
126             puts("NO");
127         else if (f==2)
128             puts("YES");
129         else{
130             int f1 = 0, f2 = 0;
131             for (int i = 0; i < n;i++)
132                 for (int j = 0; j < i;j++){
133                     if (s1[i]>s1[j])
134                         ++f1;
135                     if (s2[i]>s2[j])
136                         ++f2;
137                 }
138             if ((f1+f2)%2==0)
139                 puts("YES");
140             else
141                 puts("NO");
142         }
143     }
144     return 0;
145 }
View Code
【推广】 免费学中医，健康全家人
原文地址：https://www.cnblogs.com/mooleetzi/p/11801987.html