codeforces #587 div3 ABCDE

A. Prefixes

Description

给出一个只包含a,b的偶数长度字符串。

每次可以将序列上某一个值a->b或者b->a。

问最小的操作次数满足从起始位置开始偶数长度的子串中a，b个数相等。

Solution

模拟。

B. Shooting

Description

Solution

按权值排序一遍，贪心。

C. White Sheet

Description

给出矩形A，B，C的左下和右上坐标。

求A是否完全被B,C覆盖。

Solution

求A与B的交集AB，A与C的交集AC，ABC的交集ABC。

容斥一下如果A=AB+AC-ABC则证明完全被覆盖。

判断两个矩形是否相交

$$max(A_{lx},B_{lx}) leq min(A_{rx},B_{rx}) && max(A_{ly},B_{ly}) leq min(A_{ry},B_{ry})$$

交点坐标

$$lx=max(A_{lx},B_{lx}),ly=max(A_{ly},B_{ly}),rx=min(A_{rx},B_{rx}),ry= min(A_{ry},B_{ry})$$

  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 struct node
 88 {
 89     int x1, y1, x2, y2;
 90     node() {}
 91     node(int a, int b, int c, int d)
 92     {
 93         x1 = a, y1 = b, x2 = c, y2 = d;
 94     }
 95     ll area()
 96     {
 97         return (x2 - x1) * 1LL * (y2 - y1);
 98     }
 99 };
100 ll cal(const node &t1, const node &t2)
101 {
102     node tmp;
103     tmp.y2 = min(t2.y2, t1.y2);
104     tmp.y1 = max(t1.y1, t2.y1);
105     tmp.x2 = min(t1.x2, t2.x2);
106     tmp.x1 = max(t1.x1, t2.x1);
107     return tmp.area();
108 }
109 inline int check(const node &t1, const node &t2)
110 {
111     node tmp;
112     tmp.x1 = max(t1.x1, t2.x1);
113     tmp.x2 = min(t1.x2, t2.x2);
114     tmp.y1 = max(t1.y1, t2.y1);
115     tmp.y2 = min(t1.y2, t2.y2);
116     if (tmp.x1 > tmp.x2 || tmp.y1 > tmp.y2)
117         return 0;
118     return 1;
119 }
120 inline node intersection(const node &t1, const node &t2)
121 {
122     node tmp;
123     tmp.x1 = max(t1.x1, t2.x1);
124     tmp.x2 = min(t1.x2, t2.x2);
125     tmp.y1 = max(t1.y1, t2.y1);
126     tmp.y2 = min(t1.y2, t2.y2);
127     return tmp;
128 }
129 int main(int argc, char const *argv[])
130 {
131 #ifndef ONLINE_JUDGE
132     freopen("in.txt", "r", stdin);
133     // freopen("out.txt","w", stdout);
134 #endif
135     vector<node> vec(3);
136     for (int i = 0; i < 3; i++)
137     {
138         int x1 = read<int>(), y1 = read<int>(), x2 = read<int>(), y2 = read<int>();
139         vec[i] = node(x1, y1, x2, y2);
140     }
141     ll p1 = 0, p2 = 0;
142     if (check(vec[0],vec[1]))
143         p1 = intersection(vec[0], vec[1]).area();
144     if (check(vec[0],vec[2]))
145         p2 = intersection(vec[0], vec[2]).area();
146     ll now = p1 + p2;
147     if (check(vec[1], vec[2]))
148         if (check(vec[0],intersection(vec[1],vec[2])))
149             now -= intersection(vec[0], intersection(vec[1], vec[2])).area();
150     if (now >= vec[0].area())
151         puts("NO");
152     else
153         puts("YES");
154     return 0;
155 }

View Code

D. Swords

Description

Solution

读题找规律。

找出最大的数mx，然后求所有数与mx的差的和以及gcd。

最后答案为sum/gcd,gcd。

  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 int 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     int mx = 0;
 96     for (int i = 1; i <= n;i++)
 97         a[i] = read<int>(), mx = max(a[i], mx);
 98     int gcd = 0;
 99     ll sum = 0;
100     for (int i = 1; i <= n;i++)
101         if (a[i]==mx)
102             continue;
103         else
104             sum += mx - a[i], gcd = __gcd(mx - a[i], gcd);
105     write_line(sum/gcd, gcd);
106     return 0;
107 }

View Code

E. Numerical Sequence

Description

给出序列112123123412345....

给q次查询，每次查询序列内的第k个数字（仅包含0-9）

Solution

只想到了简单版本的做法。

简单版本k的数量级是1e9，可以在根号复杂度下模拟完成求解。

复杂版本的题解：

长度为len的数的个数为$10^{len}-10^{len-1}$，那么对于$10^{len-1}-10^{len-1}$这些数的长度都是len。

我们可以记录一个add值，表示上一个数量级的前缀长度。

如1-9范围内，这个前缀长度为9，那么在求解10-99时，这个前缀长度对答案都有贡献，即每一个大于9的数里肯定包含了1-9的前缀

通过前缀累加我们可以很快求得以x结尾的最短序列的长度。即最早出现x的序列长度。

我们可以根据这个来二分一个长度最小但大于k的x序列。

那么我们把{x-1}产生的贡献减去后，就得到了k在单独x序列(只包含12345-...x)里的位置信息。同样二分这个位置，就能得到最后答案。

  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 ll lten[20];
 88 void init()
 89 {
 90     ll p = 1;
 91     for (int i = 0; i < 19;i++)
 92         lten[i] = p, p *= 10;
 93 }
 94 inline ll num(ll x){
 95     return (x + 1) * x / 2;
 96 }
 97 ll solve(ll x,int op){
 98     ll sum = 0, pre = 1, add = 0;
 99     for (int len = 1;;len++){
100         if (10LL*pre-1<x){
101             ll cnt = 10 * pre - pre;
102             if (op)
103             {
104                 sum += add * cnt + num(cnt) * len;
105                 add += cnt * len;
106             }
107             else
108                 sum += cnt * len;
109         }
110         else{
111             ll cnt = x - pre + 1;
112             if (op)
113                 sum += add * cnt + num(cnt) * len;
114             else
115                 sum += cnt * len;
116             break;
117         }
118         pre *= 10;
119     }
120     return sum;
121 }
122 string tostring(ll x)
123 {
124     string str = "";
125     while (x)
126         str += char(x % 10 + '0'), x /= 10;
127     reverse(str.begin(), str.end());
128     return str;
129 }
130 int main(int argc, char const *argv[])
131 {
132 #ifndef ONLINE_JUDGE
133     freopen("in.txt","r", stdin);
134     // freopen("out.txt","w", stdout);
135 #endif
136     fastIO;
137     int t;
138     cin >> t;
139     while (t--)
140     {
141         ll n;
142         cin >> n;
143         --n;
144         ll l = 1, r = 1e9,res=-1;
145         while(l<=r){
146             ll mid = l + r >> 1;
147             if (solve(mid,1)>n){
148                 res = mid;
149                 r = mid - 1;
150             }
151             else
152                 l = mid + 1;
153         }
154         n -= solve(res - 1, 1);
155 
156         l = 1, r = res,res=-1;
157         while(l<=r){
158             ll mid = l + r >> 1;
159             if (solve(mid,0)>n)
160                 res = mid, r = mid - 1;
161             else
162                 l = mid + 1;
163         }
164         n -= solve(res - 1, 0);
165         cout << tostring(res)[n] << "
";
166     }
167     return 0;
168 }

View Code