2017中国大学生程序设计竞赛-哈尔滨站 Solution

A - Palindrome

题意：给出一个字符串，找出其中有多少个子串满足one-half-palindromic 的定义

思路：其实就是找一个i, j 使得以i为中轴的回文串长度和以j为中轴的回文串长度都大于j - i + 1

先Manacher 预处理出以每个字符为中轴的最长回文串长度，然后用树状数组维护j ，枚举i

 #include<bits/stdc++.h>

 using namespace std;

 typedef long long ll;

 const int maxn = 5e5 + ;

 int l;

 char Ma[maxn << ];

 int Mp[maxn << ];

 inline void Manacher(char s[], int len)

 {

     l = ;

     Ma[l++] = '$';

     Ma[l++] = '#';

     for(int i = ; i < len; ++i)

     {

         Ma[l++] = s[i];

         Ma[l++] = '#';

     }

     Ma[l] = ;

     int mx = , id = ;

     for(int i = ; i < l; ++i)

     {

         Mp[i] = mx > i ? min(Mp[ * id - i], mx - i) : ;

         while(Ma[i + Mp[i]] == Ma[i - Mp[i]]) Mp[i]++;

         if(i + Mp[i] > mx)

         {

             mx = i + Mp[i];

             id = i;

         }

     }

 }

 int cnt[maxn << ];

 char str[maxn];

 int a[maxn];

 int len;

 vector <int> vv[maxn];

 inline int lowbit(int x)

 {

     return x & (-x);

 }

 inline void update(int x, int val)

 {

     for (int i = x; i <= len; i += lowbit(i))

         a[i] += val;

 }

 inline int query(int x)

 {

     int res = ;

     for (int i = x; i > ; i -= lowbit(i))

         res += a[i];

     return res;

 }

 int main()

 {

     int t;

     scanf("%d", &t);

     while(t--)

     {

         memset(a, , sizeof a);

         scanf("%s", str);

         len = strlen(str);

         Manacher(str, len);

         ll ans = ;

         int pos = ;

         for(int i =  ; i < l; i += )

         {

             cnt[pos]= Mp[i] /  - ;

             vv[pos - cnt[pos]].push_back(pos);

             pos++;

         }

         for(int i = ; i <= pos; ++i)

         {

             for (auto it : vv[i])

             {

                 update(it, );

             }

             vv[i].clear();

             ans += query(i + cnt[i]) - query(i);

 //            cout << ans << endl;

         }

         printf("%lld\n",ans);

     }

     return ;

 }

B - K-th Number

题意：给出n个数，把这n个数中长度>= k 的区间中的第k小的数放到数组b中，最后求出数组b中的第m大的数

思路：二分答案，然后双指针法判断是否正确，因为存在这样一个性质，假如一个长度>=k的区间里面的第k小的数 >= ans

那么之后如果加入的数大于它，那么没有影响，如果小于它，要被计数

 #include<bits/stdc++.h>

 using namespace std;

 typedef long long ll;

 const int maxn = 1e5 + ;

 int n, k ;

 ll m;

 int arr[maxn];

 int brr[maxn];

 inline bool check(int mid)

 {

     ll tot = ;

     ll res = ;

     for(int i = , j = ; i <= n; ++i)

     {

         while(j <= n && res < k)

         {

             if(arr[++j] >= mid) ++res;

         }

         if(res >= k) tot += n - j + ;

         if(arr[i] >= mid) res--;

     }

     return tot >= m;

 }

 int main()

 {

     int t;

     scanf("%d", &t);

     while(t--)

     {

         scanf("%d %d %lld", &n, &k, &m);

         for(int i = ; i <= n; ++i)

         {

             scanf("%d", arr + i);

             brr[i] = arr[i];

         }

         sort(brr + , brr +  + n);

         int l = ;

         int r = n;

         int ans = ;

         while(r - l >= )

         {

             int mid = (l + r) >> ;

             if(check(brr[mid]))

             {

                 ans = mid;

                 l = mid + ;

             }

             else

             {

                 r = mid - ;

             }

         }

         printf("%d\n",brr[ans]);

     }

     return ;

 }

C - Confliction

留坑。

D - X-Men

题意：有若干个X-Man 他们要汇合，直到所有Xman的距离都小于等于1的时候，他们就停止行动，一个小时行进一个单位长度，求他们期望的行进时间

思路：因为给的是一棵树，实际上就是最远的两个X-man 的距离 / 2

 #include <bits/stdc++.h>

 using namespace std;

 #define N 1010

 struct Edge

 {

     int to, nx;

     inline Edge() {}

     inline Edge(int to, int nx) : to(to), nx(nx) {}

 }edge[N << ];

 int t, n, m;

 int head[N], pos;

 bool vis[N];

 inline void Init()

 {

     memset(vis, false, sizeof vis);

     memset(head, -, sizeof head);

     pos = ;

 }

 inline void addedge(int u, int v)

 {

     edge[++pos] = Edge(v, head[u]); head[u] = pos;

     edge[++pos] = Edge(u, head[v]); head[v] = pos;

 }

 int rmq[N << ];

 int F[N << ];

 int P[N], deep[N];

 int cnt;

 struct ST

 {

     int mm[N << ];

     int dp[N << ][];

     inline void init(int n)

     {

         mm[] = -;

         for (int i = ; i <= n; ++i)

         {

             mm[i] = ((i & (i - )) == ) ? mm[i - ] +  : mm[i - ];

             dp[i][] = i;

         }

         for (int j = ; j <= mm[n]; ++j)

             for (int i = ; i + ( << j) -  <= n; ++i)

                 dp[i][j] = rmq[dp[i][j - ]] < rmq[dp[i + ( << (j - ))][j - ]] ? dp[i][j - ] : dp[i + ( << (j - ))][j - ];

     }

     inline int query(int a, int b)

     {

         if (a > b) swap(a, b);

         int k = mm[b - a + ];

         return rmq[dp[a][k]] <= rmq[dp[b - ( << k) + ][k]] ? dp[a][k] : dp[b - ( << k) + ][k];

     }

 }st;

 inline void DFS(int u, int pre)

 {

     F[++cnt] = u;

     rmq[cnt] = deep[u];

     P[u] = cnt;

     for (int it = head[u]; ~it; it = edge[it].nx)

     {

         int v = edge[it].to;

         if (v == pre) continue;

         deep[v] = deep[u] + ;

         DFS(v, u);

         F[++cnt] = u;

         rmq[cnt] = deep[u];

     }

 }

 inline void LCA_Init(int root, int node_num)

 {

     cnt = ; deep[] = ;

     DFS(root, root);

     st.init( * node_num - );

 }

 inline int query_lca(int u, int v)

 {

     return F[st.query(P[u], P[v])];

 }

 inline void Run()

 {

     scanf("%d", &t);

     while (t--)

     {

         scanf("%d%d", &n, &m); Init();

         for (int i = , x; i <= m; ++i)

         {

             scanf("%d", &x);

             vis[x] = true;

         }

         for (int i = , u, v; i < n; ++i)

         {

             scanf("%d%d", &u, &v);

             addedge(u, v);

         }

         LCA_Init(, n);

         int ans = ;

         for (int i = ; i <= n; ++i)

         {

             if (!vis[i]) continue;

             for (int j = ; j <= n; ++j)

             {

                 if (!vis[j] || j == i) continue;

                 int lca = query_lca(i, j);

                 //printf("%d %d %d\n", i, j, lca);

                 ans = max(ans, deep[i] + deep[j] -  * deep[lca]);

             }

         }

         printf("%d.00\n", ans / );

     }

 }

 int main()

 {

     #ifdef LOCAL

         freopen("Test.in", "r", stdin);

     #endif

     Run();

     return ;

 }

E - Square Network

留坑。

F - Permutation

题意：给出一个n，里面有1-n，构造一个数列使得满足题目要求

思路：142536 类似这样构造

 #include <bits/stdc++.h>

 using namespace std;

 #define N 100010

 int t, n;

 int arr[N];

 int main()

 {

     scanf("%d", &t);

     while (t--)

     {

         scanf("%d", &n);

         int cnt = ;

         for (int i = ; i <= n; i += )

             arr[i] = cnt++;

         for (int i = ; i <= n; i += )

             arr[i] = cnt++;

         for (int i = ; i <= n; ++i) printf("%d%c", arr[i], " \n"[i == n]);

     }

     return ;

 }

G - Debug

留坑。

H - A Simple Stone Game

题意：有n堆石子，每次可以移动一个石子要另一堆，如果某一次移动之后，每一堆的石子个数都是x(x > 1) 的倍数，那么游戏结束，问最少需要移动多少个石子使得游戏结束

思路：x一定是石子和的因数，我们可以枚举石子和的每个因数，求出每个因数下的移动次数，取min。至于如何求移动次数，我们可以将每个石子的余数记录下来，并将余数相加再除以因数，可以的到有多少堆石子得到石子，然后再将需要减少的石子数相加就可以得到。注意当只有一个石子的时候为0；

 #include<bits/stdc++.h>

 using namespace std;

 typedef long long ll;

 const ll INFLL = 0x3f3f3f3f3f3f3f3f;

 const int maxn = 1e5 + ;

 int n;

 ll arr[maxn];

 ll sum;

 ll ans;

 int cnt;

 ll brr[maxn];

 ll crr[maxn];

 int tot;

 ll prime[maxn];

 bool isprime[maxn];

 inline void Init_prime()

 {

     memset(isprime, true, sizeof isprime);

     isprime[] = isprime[] = false;

     for(int i = ; i < maxn; ++i)

     {

         if(isprime[i] == true)

         {

             prime[tot++] = i;

             for(int j = i << ; j < maxn; j += i)

             {

                 isprime[j] = false;

             }

         }

     }

 }

 inline void cal(ll x)

 {

     ll sum_tmp = ;

     int pos = ;

     for(int i = ; i <= n; ++i)

     {

         if(arr[i] % x)

         {

             crr[pos++] = arr[i] % x;

             sum_tmp += arr[i] % x;

         }

     }

     ll p = sum_tmp / x;

     sort(crr, crr + pos);

     ll res = ;

     for(int i = ; i < pos - p; ++i)

     {

         res += crr[i];

     }

     ans = min(ans, res);

 }

 inline void get_x(ll tmp)

 {

     ll tmp_ = sqrt(tmp) + ;

     for(int i = ; i < tot && prime[i] <= tmp_; ++i)

     {

         if(tmp % prime[i] == )

         {

             cal(prime[i]);

         }

     }

 }

 int main()

 {

     Init_prime();

     int t;

     scanf("%d",&t);

     while(t--)

     {

         scanf("%d", &n);

         sum = ;

         for(int i = ; i <= n; ++i)

         {

             scanf("%lld", arr + i);

             sum += arr[i];

         }

         ans = INFLL;

         get_x(sum);

         cal(sum);

         printf("%lld\n", ans);

     }

     return ;

 }

I - Cow`s Segment

留坑。

J - Interview

留坑。

K - Server

题意：给出一些区间，每个区间附加两个值ai 和 bi 选出一些区间覆盖1 - t 并且 sgm(ai) / sgm(bi) 最小

思路：二分答案那么就是使得 sgm(ai) - sgm(bi) * x >0

然后 ai - bi * x > 0 的都选，，剩下的就是用最小代价覆盖所有区间 dp + 数据结构

我是用线段树和树状数组，本来以为动态开点线段树会比普通线段树要快一点，实际上没有

线段树

 #include <cstdio>

 #include <algorithm>

 #include <iostream>

 using namespace std;  

 #define N 100010

 #define ll long long

 #define INF 0x3f3f3f3f

 const double eps = 1e-;

 struct node

 {

     int l, r;

     double Min;

     inline node() {}

     inline node(int l, int r, double Min) : l(l), r(r), Min(Min) {}

 }tree[N << ];

 int cnt, root;

 inline void Init()

 {

     cnt = ; root = ;

     tree[] = node(, , INF * 1.0);

 }

 inline void update(int &id, int l, int r, int ql, int qr, double val)

 {

     if (id == )

     {

         id = ++cnt;

         tree[id] = node(, , val);

     }

     if (l >= ql && r <= qr)

     {

         tree[id].Min = min(tree[id].Min, val);

         return;

     }

     int mid = (l + r) >> ;

     if (ql <= mid) update(tree[id].l, l, mid, ql, qr, val);

     if (qr > mid) update(tree[id].r, mid + , r, ql, qr, val);

 }

 double ansMin; 

 inline void query(int id, int l, int r, int pos)

 {

     if (id == ) return;

     ansMin = min(ansMin, tree[id].Min);

     if (l == r)

         return;

     int mid = (l + r) >> ;

     if (pos <= mid) query(tree[id].l, l, mid, pos);

     else query(tree[id].r, mid + , r, pos);

 }

 struct Interval

 {

     int l, r; double a, b;

     inline void scan()

     {

         scanf("%d%d%lf%lf", &l, &r, &a, &b);

     }

     inline bool operator < (const Interval &r) const

     {

         return l < r.l;

     }

 }interval[N];

 int T;

 int n, t;

 inline bool check(double x)

 {

     double sum = 0.0;

     for (int i = ; i <= n; ++i)

         if (interval[i].a - interval[i].b * x < )

             sum += interval[i].a - interval[i].b * x;

     Init();

     update(root, , t, , , 0.0);

     for (int i = ; i <= n; ++i)

     {

         ansMin = INF * 1.0; query(root, , t, interval[i].l - );

         ansMin = max(ansMin, ansMin + interval[i].a - interval[i].b * x);

         update(root, , t, interval[i].l, interval[i].r, ansMin);

     }

     ansMin = INF * 1.0; query(root, , t, t);

     return sum + ansMin > ;

 }

 inline void Run()

 {

     scanf("%d", &T);

     while (T--)

     {

         scanf("%d%d", &n, &t);

         for (int i = ; i <= n; ++i)

             interval[i].scan();

         sort(interval + , interval +  + n);

         double l = , r =  * 1.0;

         while (r - l > eps)

         {

             double mid = (l + r) / ;

             if (check(mid))

                 l = mid;

             else

                 r = mid;

         }

         printf("%.3f\n", l);

     }

 }

 int main()

 {

     #ifdef LOCAL

         freopen("Test.in", "r", stdin);

     #endif

     Run();

     return ;

 }

树状数组

 #include <cstdio>

 #include <algorithm>

 #include <iostream>

 using namespace std;  

 #define N 100010

 #define ll long long

 #define INF 0x3f3f3f3f

 const double eps = 1e-;

 double a[N];

 int T, n, t;

 inline int lowbit(int x)

 {

     return x & (-x);

 }

 inline void update(int x, double val)

 {

     for (int i = x; i > ; i -= lowbit(i))

         a[i] = min(a[i], val);

 }

 inline double query(int x)

 {

     if (x == ) return ;

     double res = INF;

     for (int i = x; i <= t; i += lowbit(i))

         res = min(a[i], res);

     return res;

 }

 struct Interval

 {

     int l, r; double a, b;

     inline void scan()

     {

         scanf("%d%d%lf%lf", &l, &r, &a, &b);

     }

     inline bool operator < (const Interval &r) const

     {

         return l < r.l;

     }

 }interval[N];

 inline bool check(double mid)

 {

     double sum = 0.0;

     for (int i = ; i <= n; ++i)

         if (interval[i].a - interval[i].b * mid < )

             sum += interval[i].a - interval[i].b * mid;

     for (int i = ; i <= t; ++i) a[i] = INF;

     for (int i = ; i <= n; ++i)

     {

         double x = query(interval[i].l - );

         x = max(x, interval[i].a - interval[i].b * mid);

         update(interval[i].r, x);

     }

     return sum + query(t) > ;

 }

 inline void Run()

 {

     scanf("%d", &T);

     while (T--)

     {

         scanf("%d%d", &n, &t);

         for (int i = ; i <= n; ++i)

             interval[i].scan();

         sort(interval + , interval +  + n);

         double l = , r =  * 1.0;

         while (r - l > eps)

         {

             double mid = (l + r) / ;

             if (check(mid))

                 l = mid;

             else

                 r = mid;

         }

         printf("%.3f\n", l);

     }

 }

 int main()

 {

     #ifdef LOCAL

         freopen("Test.in", "r", stdin);

     #endif

     Run();

     return ;

 }

L - Color a Tree

题意：给出两条规则： A , 以x为根的子树下的黑点数量不小于y B : 除了以x为根的子树下的黑点数量不小于y ，求满足给出的所有规则，需要染色的最小数量

思路：假如我们知道答案，那么B规则就可以转变为以x为根的子树下的黑点数量不大于(ans - y)

然后二分，DFScheck

 #include <bits/stdc++.h>

 using namespace std; 

 #define N 100010

 struct Edge

 {

     int to, nx;

     inline Edge() {}

     inline Edge(int to, int nx) : to(to), nx(nx) {}

 }edge[N << ];

 int n;

 int head[N], pos;

 int son[N];

 int A[N], B[N], C[N];

 inline void Init()

 {

     memset(head, -, sizeof head);

     memset(son, , sizeof son);

     memset(A, , sizeof A);

     memset(B, , sizeof B);

     pos = ;

 }

 inline void addedge(int u, int v)

 {

     edge[++pos] = Edge(v, head[u]); head[u] = pos;

     edge[++pos] = Edge(u, head[v]); head[v] = pos;

 }

 inline void DFS_PRE(int u, int pre)

 {

     son[u] = ; int cnt = ;

     for (int it = head[u]; ~it; it = edge[it].nx)

     {

         int v = edge[it].to;

         if (v == pre) continue;

         DFS_PRE(v, u);

         cnt += A[v];

         son[u] += son[v];

     }

     A[u] = max(A[u], cnt);

 }

 inline void DFS_CHECK(int u, int pre)

 {

     int cnt = ;

     for (int it = head[u]; ~it; it = edge[it].nx)

     {

         int v = edge[it].to;

         if (v == pre) continue;

         DFS_CHECK(v, u);

         cnt += C[v];

     }

     C[u] = min(C[u], cnt);

 }

 inline bool check(int mid)

 {

     for (int i = ; i <= n; ++i)

     {

         C[i] = mid - B[i];

         if (A[i] > son[i] || B[i] > (n - son[i]) || A[i] > C[i]) return false;

     }

     //for (int i = 1; i <= n; ++i) printf("%d %d\n", i, C[i]);

     DFS_CHECK(, );

     //printf("bug -> %d\n", mid);

     //for (int i = 1; i <= n; ++i) printf("%d %d\n", i, C[i]);

     for (int i = ; i <= n; ++i)

     {

         if (A[i] > C[i]) return false;

     }

     return C[] >= mid;

 }

 inline void Run()

 {

     int t; scanf("%d", &t);

     while (t--)

     {

         scanf("%d", &n); Init();

         for (int i = , u, v; i < n; ++i)

         {

             scanf("%d%d", &u, &v);

             addedge(u, v);

         }

         int tot, u, v;

         scanf("%d", &tot);

         while (tot--)

         {

             scanf("%d%d", &u, &v);

             A[u] = max(A[u], v);

         }

         scanf("%d", &tot);

         while (tot--)

         {

             scanf("%d%d", &u, &v);

             B[u] = max(B[u], v);

         }

         DFS_PRE(, );

         int l = , r = n, ans = -;

         while (r - l >= )

         {

             int mid = (l + r) >> ;

             if (check(mid))

             {

                 ans = mid;

                 r = mid - ;

             }

             else

                 l = mid + ;

         }

         printf("%d\n", ans);

     }

 }

 int main()

 {

     #ifdef LOCAL

         freopen("Test.in", "r", stdin);

     #endif

     Run();

     return ;

 }

M - Geometry Problem

题意：给出n个点，求一个圆心以及半径，使得有一半以上的点在这个圆上

思路：随机选三个点，构成外接圆判断一下是不是 n <= 4 的时候特判

 #include <bits/stdc++.h>

 using namespace std; 

 const double eps = 1e-;

 inline int sgn(double x)

 {

     if (fabs(x) < eps) return ;

     if (x < ) return -;

     return ;

 }

 struct Point

 {

     double x, y;

     inline Point() {}

     inline Point(double x, double y) : x(x), y(y) {}

     inline void scan() { scanf("%lf%lf", &x, &y); }

     inline Point operator + (const Point &b) const { return Point(x + b.x, y + b.y); }

     inline Point operator - (const Point &b) const { return Point(x - b.x, y - b.y); }

     inline Point operator / (const double &k) const { return Point(x / k, y / k); }

     inline Point operator * (const double &k) const { return Point(x * k, y * k); }

     inline double operator ^ (const Point &b) const { return x * b.y - y * b.x; }

     inline double operator * (const Point &b) const { return x * b.x + y * b.y; }

     inline double distance(Point b) { return hypot(x - b.x, y - b.y); }

     inline Point rotleft() { return Point(-y, x); }

 };

 struct Line

 {

     Point s, e;

     inline Line() {}

     inline Line(Point s, Point e) : s(s), e(e) {}

     inline Point crosspoint(Line v)

     {

         double a1 = (v.e - v.s) ^ (s - v.s);

         double a2 = (v.e - v.s) ^ (e - v.s);

         return Point((s.x * a2 - e.x * a1) / (a2 - a1), (s.y * a2 - e.y * a1) / (a2 - a1));

     }

     inline int relation(Point p)

     {

         int c = sgn((p - s) ^ (e - s));

         if (c < ) return ;

         if (c > ) return ;

         return ;

     }

 };

 struct Circle

 {

     Point p;

     double r;

     inline Circle() {}

     inline Circle(Point p, double r) : p(p), r(r) {}

     inline Circle(Point a, Point b, Point c)

     {

         Line u = Line((a + b) / , ((a + b) / ) + ((b - a).rotleft()));

         Line v = Line((b + c) / , ((b + c) / ) + ((c - b).rotleft()));

         p = u.crosspoint(v);

         r = p.distance(a);

     }

 };

 int t, n;

 vector <Point> v;

 inline void Run()

 {

     scanf("%d", &t);

     while (t--)

     {

         scanf("%d", &n);

         double x, y; v.clear();

         for (int i = ; i <= n; ++i)

         {

             scanf("%lf%lf", &x, &y);

             v.emplace_back(x, y);

         }

         if (n == )

         {

             printf("%.6f %.6f 0\n", v[].x, v[].y);

             continue;

         }

         else if (n <= )

         {

             Point ans = Point((v[].x + v[].x) / , (v[].y + v[].y) / );

             double dis = ans.distance(v[]);

             printf("%.6f %.6f %.6f\n", ans.x, ans.y, dis);

             continue;

         }

         else

         {

             Circle cir;

             while (true)

             {

                 random_shuffle(v.begin(), v.end());

                 //if (Line(v[0], v[1]).relation(v[2]) == 3) continue;

                 cir = Circle(v[], v[], v[]);

                 int cnt = ;

                 for (int i = , len = v.size(); i < len; ++i)

                     if (fabs(cir.p.distance(v[i]) - cir.r) < eps) ++cnt;

                 if (cnt >= ((n + ) >> ))

                     break;

             }

             printf("%.6f %.6f %.6f\n", cir.p.x, cir.p.y, cir.r);

         }

     }

 }

 int main()

 {

     #ifdef LOCAL

         freopen("Test.in", "r", stdin);

     #endif

     Run();

     return ;

 }

巴特西

2017中国大学生程序设计竞赛-哈尔滨站 Solution

最新文章

热门文章