codeforeces近日题目小结

upd:2019-12-20

题目源自codeforces的Round_551

Round_551/F:

牛逼的dp

upd:2019-12-14

题目源自codeforces的Round_552

Round_552/F:

这个题一开始按照背包的经典dp转移去写，外面枚举物品，里面枚举状态，就WA

仔细思考之后发现这个问题里，把sp offer看作背包问题中的物品

两个不同物品放入背包的先后顺序，对答案是有影响的

为了避免这种影响，应该外层枚举状态，内层枚举物品。这样就可了

Round_552/G:

智力题。先处理两个数相同 lcm(x, x) = x的情况。然后再做下面。

假设ai和aj为最优解，那么有g=gcd(ai, aj)

枚举g，找到g的倍数中在a里出现过的最小的两个不同数x*g和y*g，用x*y*g更新答案即可

由于我们枚举g从1-1e7,所以一定能够枚举到gcd(ai, aj)，此时最优解一定会更新答案，所以保证正确

upd:2019-12-13

题目源自codeforces的Round_602_div1+2, Round_603_div2, Educational_Round_77

Round_603/F:

考虑一个经典dp状态定义, dp[i][j]代表上面一个树的最后一个被选取的叶节点编号是i

下面的树最后一个被选取的叶节点编号是j且 i != j

那么我们需要考虑第 max(i, j) + 1 个点是选择上下哪棵树的点

这个代价其实就是比较好求的了

Round_602_div1/E:

我直接参考的最短的代码

一个比较牛逼的构造，正确性自己手画一下是可以证明的

我先证明了相邻两行必然不等，然后证明的 1 <= i < j <= n 必有第i行和第j行不等

然后证明1 <= i <= n 必有第i行和第 n+1 行不等

Round_603_div1/F:

一个比较牛逼的分治

Educational_Round_77/F:

一个比较牛逼的树上计数

upd:2018-11-25

题目源自codeforeces的三场contest

contest/1043+1055+1076

目前都是solved 6/7，都差了最后一题

简单题:

contest/1043/E:

先不考虑m个限制，求出每个人与其他所有人组队的情况下这个人获得的分数

对于当前的 i ，如果他与 j 组队时 i 做第一题，则有 xi + yj <= xj + yi

即 xi - yi <= xj - yj，排序累加计算即可

contest/1055/C:

注意到 la 与 lb 的差距会由于 t0 和 t1 而变化 k*gcd(t0, t1)， k为系数

所以肯定想让 la 和 lb 离得尽量近，重合部分也就越大

能让两个位置重合就重合，不能重合就在那个位置前后蹭蹭就行了

contest/1076/D:

考虑最短路的dij算法，发现那些在最短路上的边形成了一棵树

所以直接跑堆优化dij

contest/1076/E:

kdtree模板题，变成二维空间操作，一维dep，一维dfn

二维空间矩形加+单点查询？考虑差分变为，单点加+前缀和

查询是在所有操作完成后，所以直接把操作和查询混在一起

按照第一关键字x，第二关键字y排序，排序后直接树状数组维护即可

O(nlogn)

思维僵化，有个O(n)做法，使用差分数组 f[ ]

把每个操作(v, d, x)挂到节点 v 上

然后一遍dfs，在到达v的时候对于节点上每个操作

f[dep[v]] += x, f[dep[v] + d + 1] -= x

dfs 回到点 v 父亲之前再做逆操作

对f[ ]求[1, dep[u]]的前缀和即为点 u 的答案

我傻逼了好久的题目:

contest/1055/D:

先对于那些w[i] != v[i]的所有串

求出他们共同的核心替换部分(必须替换并且长度一致)

然后为了不让无辜串也被替换所以要尝试将该串尽量向左右拓展

最后求出来替换串 s -> t 之后再验证，验证一开始想的太简单了

w[i] = v[i]的串，都满足w[i].find(s) == 0是不足够的

还会有别的情况！

简单暴力就是对n个串w[i]都find一下s，第一次找到就替换成 t

然后新串与v[i]对比即可

 #include <bits/stdc++.h>

 #define lb(x) (x&(-x))

 typedef long long ll;

 using namespace std;

 const int N = ;

 string s = "", t;

 int n, flag[N];

 string a[N], b[N];

 int nex[N], l[N], r[N];

 vector <int> lt;

 void calc_next() {

     nex[] = -;

     for (int i = ; i < s.size(); i ++) {

         int j = nex[i - ];

         while (j != - && s[j + ] != s[i]) j = nex[j];

         if (s[j + ] == s[i]) nex[i] = j + ;

         else nex[i] = -;

     }

 }

 void kmp(string &st) {

     for (int i = , j = -; i < st.size(); i ++) {

         while (j != - && s[j + ] != st[i]) j = nex[j];

         if (s[j + ] == st[i]) {

             j ++;

             if (j +  == s.size()) {

                 st = st.substr(, i +  - s.size()) + t + st.substr(i + );

                 return;

             }

         }

     }

 }

 int main() {

     ios::sync_with_stdio(false);

     cin >> n;

     for (int i = ; i <= n; i ++) cin >> a[i];

     for (int i = ; i <= n; i ++) cin >> b[i];

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

         l[i] = -, r[i] = -;

         for (int j = ; j < a[i].size(); j ++) {

             if (a[i][j] != b[i][j]) {

                 if (l[i] == -) l[i] = j;

                 r[i] = j;

             }

         }

         if (l[i] == -) continue;

         if (s == "") s = a[i].substr(l[i], r[i] - l[i] + ), t = b[i].substr(l[i], r[i] - l[i] + );

         else if (s != a[i].substr(l[i], r[i] - l[i] + ) || t != b[i].substr(l[i], r[i] - l[i] + )) {

             cout << "NO";

             return ;

         }

         lt.push_back(i);

     }

     while () {

         int flag = ;

         for (int i : lt) {

             l[i] --;

             if (l[i] < ) {

                 flag = ;

                 break;

             }

         }

         if (!flag) break;

         char ch = a[lt[]][l[lt[]]];

         for (int i : lt) {

             if (ch != a[i][l[i]]) {

                 flag = ;

                 break;

             }

         }

         if (!flag) break;

         s = ch + s;

         t = ch + t;

     }

     while () {

         int flag = ;

         for (int i : lt) {

             r[i] ++;

             if (r[i] >= a[i].size()) {

                 flag = ;

                 break;

             }

         }

         if (!flag) break;

         char ch = a[lt[]][r[lt[]]];

         for (int i : lt) {

             if (ch != a[i][r[i]]) {

                 flag = ;

                 break;

             }

         }

         if (!flag) break;

         s += ch;

         t += ch;

     }

     calc_next();

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

         kmp(a[i]);

         if (a[i] != b[i]) {

             cout << "NO";

             return ;

         }

     }

     cout << "YES\n" << s << '\n' << t;

     return ;

 }

其他题目:

contest/1055/F:

树上异或路径和，把每个点的权值变为到根的异或路径和

异或路径和就变为了两点的权值异或和

这个题如果问有多少条路径异或和<=x

就可以直接树分治+trie树，O(nlogn^2)

但是问排名为k的，套个二分O(nlogn^3)，gg

直接在trie树上搞，从高到低考虑当前位取0的结果个数

超过了k，则ans当前位取0，否则当前位取1

空间O(62*n)会爆MLE，直接一层一层的构建trie树

 #include <bits/stdc++.h>

 using namespace std;

 const int N = 2e6 + ;

 int cnt, t, sz[N];

 int n, a[N], b[N], ch[N][];

 long long s, k, ans, v[N];

 int pos(int x, int y) {

     return ch[x][y] ? ch[x][y] : ch[x][y] = ++ cnt;

 }

 int main() {

     ios::sync_with_stdio(false);

     cin >> n >> k;

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

         cin >> p >> v[i], v[i] ^= v[p];

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

         a[i] = b[i] = ;

     for (int j = ; ~j; j --) {

         for (int i = ; i <= cnt; i ++) ch[i][] = ch[i][] = sz[i] = ;

         s = t = cnt = ;

         for (int i = ; i <= n; i ++) sz[a[i] = pos(a[i], v[i] >> j & )] ++;

         for (int i = ; i <= n; i ++) s += sz[ch[b[i]][v[i] >> j & ]];

         if (s < k) ans |= 1ll << j, k -= s, t = ;

         for (int i = ; i <= n; i ++) b[i] = ch[b[i]][(v[i] >> j & ) ^ t];

     }

     cout << ans;

     return ;

 }

几个DP题目:

contest/1043/F:

给出n个数，问最少选几个数可以使得gcd=1

考虑最优解集合，先拿出第一个数

然后依次拿出其他数跟它求gcd，那么gcd一定是逐次减小的

并且每次约去的质因数都是不同的(不然这个数没有意义不会出现在最优集合里)

ai <= 3e5，可以求出ans如果存在一定 ans <= 7

设计dp[i][j]代表去除 i 个不同数字使得他们gcd为 j 的方案数有多少种

i 从小到大枚举， for i 1 -> 7

dp[i][j] 考虑容斥求出，取 i 个数的gcd为 j 的倍数的方案数

减去 gcd 为 j*2, j*3, j*4 的方案数即为我们需要的方案数了

dp[i][1] != 0，则取 i 个数能 gcd = 1

O(k*nlogn)，k为系数，最大是 7

考虑中间需要组合数，而C(n, 7)会爆long long

但注意到我们的不需要结果的具体方案数，只想知道dp[i][1] != 0

所以考虑直接模大质数即可，自然溢出也可以

再不相信就直接取两个大质数跑两次验证

 #include <bits/stdc++.h>

 using namespace std;

 const int N = 3e5 + ;

 const int Mod = 1e9 + ;

 int n, m, a[N], b[N];

 int c[N], dp[N], cnt[N];

 int main() {

     ios::sync_with_stdio(false);

     cin >> n;

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

         cin >> a[i], m = max(m, a[i]), b[a[i]] ++;

     for (int i = ; i <= m; i ++) {

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

             cnt[i] += b[j];

         c[i] = ;

     }

     for (int k = ; k < ; k ++) {

         for (int i = m; i; i --) {

             dp[i] = (c[i] = 1ll * c[i] * (cnt[i] +  - k) % Mod);

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

                 dp[i] = (dp[i] - dp[j]) % Mod;

         }

         if (dp[] != ) {

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

             return ;

         }

     }

     puts("-1");

contest/1055/E:

这题面有毒啊，应该用set不是multiset啊

直接二分答案x进行验证

是否可以取出m个区间，使得m个区间组成的set里<=x的数字>=k个

dp[i][j]代表假设总区间只有[1, i]

选择了 j 个区间后，最多能包含多少个<=x的数字　　

枚举 i，考虑dp[i][j]，只有包含 i 和不包含 i

不包含 i -> dp[i - 1][j]

包含 i，找到所有包含i的区间里最小的左端点L -> dp[L - 1][j - 1] + count(ai <= x for i in [L, i])

 #include <bits/stdc++.h>

 using namespace std;

 const int N = ;

 int n, m, s, k;

 int a[N], l[N], r[N], dp[N][N];

 bool check(int x) {

     memset (dp, , sizeof dp);

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

         int pos = i + , sum = ;

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

             if (l[j] <= i && i <= r[j])

                 pos = min(pos, l[j]);

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

             sum += a[j] <= x;

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

             dp[i][j] = max(dp[i - ][j], dp[pos - ][j - ] + sum);

     }

      return dp[n][m] >= k;

 }

 int main() {

     ios::sync_with_stdio(false);

     int L = 1e9, R = , mid, ans = -;

     cin >> n >> s >> m >> k;

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

         cin >> a[i], L = min(L, a[i]), R = max(R, a[i]);

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

         cin >> l[i] >> r[i];

     while (L <= R) {

         if (check(mid = L + R >> )) ans = mid, R = mid - ;

         else L = mid + ;

     }

     cout << ans;

     return ;

 }

contest/1076/F:

dp[i][j]代表第 i 页以 type j 结尾的话，最少结尾是几个连续的type j

因为考虑当前页以type x结尾的话

如果下一页的全局最优答案是以type x开始的话，那肯定希望当前页结尾的x越少越好

如果不是type x开始的话，那么当前页只要以x结尾，多少个都无所谓啦

所以我们需要这个状态！

min(dp[n][0], dp[n][1])即为答案

转移就贪心转移

 #include <bits/stdc++.h>

 #define lb(x) (x&(-x))

 using namespace std;

 const int N = 3e5 + ;

 typedef long long ll;

 ll n, k, a[N][], dp[N][];

 int main() {

     ios::sync_with_stdio(false);

     cin >> n >> k;

     for (ll i = ; i <= n; i ++) cin >> a[i][];

     for (ll i = ; i <= n; i ++) cin >> a[i][];

     for (ll s0, min0, s1, min1, i = ; i <= n; i ++) {

         dp[i][] = dp[i][] = k + ;

         if (dp[i - ][] <= k) {

             s0 = dp[i - ][] + a[i][];

             min1 = (s0 + k - ) / k - ;

             if (a[i][] >= min1 && a[i][] <= (a[i][] + ) * k) {

                 if (a[i][] == min1) dp[i][] = min(dp[i][], s0 - k * min1);

                 else if (a[i][] > a[i][] * k) dp[i][] = min(dp[i][], a[i][] - a[i][] * k);

                 else dp[i][] = dp[i][] = ;

             }

         }

         if (dp[i - ][] <= k) {

             s1 = dp[i - ][] + a[i][];

             min0 = (s1 + k - ) / k - ;

             if (a[i][] >= min0 && a[i][] <= (a[i][] + ) * k) {

                 if (a[i][] == min0) dp[i][] = min(dp[i][], s1 - k * min0);

                 else if (a[i][] > a[i][] * k) dp[i][] = min(dp[i][], a[i][] - a[i][] * k);

                 else dp[i][] = dp[i][] = ;

             }

         }

     }

     cout << (dp[n][] <= k || dp[n][] <= k ? "YES" : "NO");

     return ;

 }

巴特西

codeforeces近日题目小结

最新文章

热门文章