Codeforces Round #506 (Div. 3)ABCDEF

并没有参加比赛，全是赛后AC

A题

　　题意：现有一个长度为n的字符串s。你需要构建一个长度最小的字符串t，使得t中恰好包含k个s（允许部分重叠），输出这个字符串

 1 /*
 2     我们可以非常容易的发现我们构造出来的字符串t有着鲜明的特征。即t中有大量重复的子串，可以证明的是t = S + (K-1)*A， A是S串中删去一段字符串（这段字符串满足既是S的前缀又是S的后缀）。
 3 */
 4 #include
 5 #include
 6 
 7 using namespace std;
 8 
 9 const int maxn = 50 + 5;
10 
11 char a[maxn];
12 int n, k;
13 
14 int main(void) {
15     scanf("%d%d", &n, &k);
16     scanf("%s", a + 1);
17     string s1 = "", s2 = ""; int res = 0;
18     for (int i = 1, j = n; i < n; ++ i, -- j) {
19         s1 = s1 + a[i];
20         s2 = a[j] + s2;
21         if (s1 == s2) res = max(res, i);
22     }
23     int len = n - res; 
24 //    cout << len << endl;
25     string ans = "";
26     for (int i = n; i >= n - len + 1; -- i) ans = a[i] + ans;
27     for (int i = 1; i <= n; ++ i) printf("%c", a[i]);
28     for (int i = 1; i < k; ++ i) cout << ans; puts("");
29     return 0;
30 }

B题

　　题意：给出一个长度为n的数组A，数组A中的元素a[i]满足（1<=a[i]<=10^9），且a[i]严格大于a[i-1](2<=i<=n)。现在要你找出一个数组B，满足数组B中所有元素在A中都是有序排列的，即B是A的非连续子序列，数组B中的元素要满足b[i]>=2*b[i-1]，输出这个数组B的最大长度。

 1 /*
 2 一个类似导弹拦截的DP+决策单调性优化（这个优化由单调队列实现）
 3 */
 4 #include
 5 #include
 6 
 7 using namespace std;
 8 
 9 const int maxn = 2e5 + 5;
10 
11 int n, a[maxn], f[maxn], Stack[maxn], val[maxn];
12 
13 
14 int main(void) {
15     scanf("%d", &n);
16     for (int i = 1; i <= n; ++ i) scanf("%d", &a[i]);
17     int L = 1, R = 1;
18     Stack[1] = 1;
19     val[1] = 1;
20     int ans = 1;
21     // a值小f值大 和 a值大f值小 
22     for (int i = 2; i <= n; ++ i) {
23         while (L <= R && a[Stack[L]] * 2 < a[i]) ++ L;
24         if (L <= R) {
25             int cur = val[L] + 1;
26             ans = max(ans, cur);
27             while (L <= R && cur >= val[R]) -- R;
28             ++ R; Stack[R] = i; val[R] = cur;        
29         } else {
30             int cur = 1;
31             ++ R; Stack[R] = i; val[R] = cur;
32         }
33     }
34     printf("%d\n", ans);
35     return 0;
36 }

C题：

　　题意：给出n个区间（2<=n<=3e5）,区间的左右边界均在[0,1e9]之间，现要你去掉一个区间，求出剩下n-1个区间的区间交，使得这个区间交的长度最大。输出这个长度

 1 /*
 2     我们维护两个东西，一个是区间并的前缀f[i]，另一个是区间并的后缀g[i]。如果我们去掉i这个区间，答案就是f[i-1]这个区间和g[i+1]这个区间的区间并。
 3     
 4 */
 5 #include
 6 
 7 using namespace std;
 8 
 9 const int maxn = 3e5 + 5;
10 
11 int n, l[maxn], r[maxn];
12 
13 struct node {
14     int l, r;
15 } f[maxn], g[maxn];
16 
17 pair<int, int> Make(int l0, int r0, int l1, int r1) {
18     if (l0 > l1) {
19         swap(l0, l1); swap(r0, r1);
20     }
21     // [l0, r0] [l1, r1]  l0 <= l1
22     if (r0 <= l1) return make_pair(-1, -1);
23     if (r0 >= r1) return make_pair(l1, r1);
24     return make_pair(l1, r0);
25 } // 输入两个区间，返回他们的并区间
26 
27 int Get_Ans(pair<int, int> tmp) {
28     return tmp.second - tmp.first;
29 } //得到区间tmp的长度。
30 
31 int main(void) {
32     scanf("%d", &n);
33     for (int i = 1; i <= n; ++ i) scanf("%d%d", &l[i], &r[i]);
34     
35     int L = l[1], R = r[1];
36     f[1].l = L; f[1].r = R;
37     for (int i = 2; i <= n; ++ i) {
38         pair<int, int> tmp = Make(L, R, l[i], r[i]);
39         L = f[i].l = tmp.first;    R = f[i].r = tmp.second;
40     }
41     
42     L = l[n]; R = r[n];
43     g[n].l = L; g[n].r = R;
44     for (int i = n - 1; i >= 1; -- i) {
45         pair<int, int> tmp = Make(L, R, l[i], r[i]);
46         L = g[i].l = tmp.first; R = g[i].r = tmp.second;
47     }
48     
49     int ans = max(Get_Ans(make_pair(g[2].l, g[2].r)), Get_Ans(make_pair(f[n - 1].l, f[n - 1].r)));
50     
51     for (int i = 2; i < n; ++ i) {
52         ans = max(ans, Get_Ans(Make(f[i - 1].l, f[i - 1].r, g[i + 1].l, g[i + 1].r)));
53     }
54     printf("%d\n", ans);
55     return 0;
56 }

D题：

　　题意：给出一个长度为n的数组A和一个k，满足1<=n<= 2e5, 2<=k<=1e9,1<=a[i]<=1e9。现在你可以拿出A数组里面的两个数字a[i]和a[j]（i！=j），将a[i]和a[j]拼在一起形成一个大数（例如5和123拼在一起可以拼出5123）如果这个拼成的大数是k的倍数，那么++ Ans。要求输出Ans。

　　我好菜啊：

 1 /*
 2 这题我。。。唉。（因为某个智障错误我的代码比别人的代码慢了20%，T了11发才发现。。）
 3 思路：我们考虑连接好的大数x，可以发现x%k==0这个条件等价于把x减去好多好多的k，直到把x减到0为止。于是乎，我们就发现了一个算法，就是我们把a[i]*（10^(a[j]的长度)）对K取模，得到一个小于k的数字x2，
 4 然后在把a[j]对k取模，得到一个小于k的数字y2。那么（x2+y2）%k等价于原来的大数%k。我们这么处理后就可以用map来维护这个东西。计算答案就简单啦。
 5     智障错误是：我计算i的时候为了防止a[i]和a[i]拼在一起的情况出现，直接在map里面消除了a[i]的影响，算完后再加上去，这个操作复杂度是log的还带上一个巨大的常数，结果就T了几百ms，别人算法的这个操作都是O(1)的。。。。我好菜啊
 6 */
 7 #pragma GCC diagnostic error "-std=c++11"
 8 #pragma GCC target("avx")
 9 #pragma GCC optimize(3)
10 #pragma GCC optimize("Ofast")
11 #pragma GCC optimize("inline")
12 #pragma GCC optimize("-fgcse")
13 #pragma GCC optimize("-fgcse-lm")
14 #pragma GCC optimize("-fipa-sra")
15 #pragma GCC optimize("-ftree-pre")
16 #pragma GCC optimize("-ftree-vrp")
17 #pragma GCC optimize("-fpeephole2")
18 #pragma GCC optimize("-ffast-math")
19 #pragma GCC optimize("-fsched-spec")
20 #pragma GCC optimize("unroll-loops")
21 #pragma GCC optimize("-falign-jumps")
22 #pragma GCC optimize("-falign-loops")
23 #pragma GCC optimize("-falign-labels")
24 #pragma GCC optimize("-fdevirtualize")
25 #pragma GCC optimize("-fcaller-saves")
26 #pragma GCC optimize("-fcrossjumping")
27 #pragma GCC optimize("-fthread-jumps")
28 #pragma GCC optimize("-funroll-loops")
29 #pragma GCC optimize("-fwhole-program")
30 #pragma GCC optimize("-freorder-blocks")
31 #pragma GCC optimize("-fschedule-insns")
32 #pragma GCC optimize("inline-functions")
33 #pragma GCC optimize("-ftree-tail-merge")
34 #pragma GCC optimize("-fschedule-insns2")
35 #pragma GCC optimize("-fstrict-aliasing")
36 #pragma GCC optimize("-fstrict-overflow")
37 #pragma GCC optimize("-falign-functions")
38 #pragma GCC optimize("-fcse-skip-blocks")
39 #pragma GCC optimize("-fcse-follow-jumps")
40 #pragma GCC optimize("-fsched-interblock")
41 #pragma GCC optimize("-fpartial-inlining")
42 #pragma GCC optimize("no-stack-protector")
43 #pragma GCC optimize("-freorder-functions")
44 #pragma GCC optimize("-findirect-inlining")
45 #pragma GCC optimize("-fhoist-adjacent-loads")
46 #pragma GCC optimize("-frerun-cse-after-loop")
47 #pragma GCC optimize("inline-small-functions")
48 #pragma GCC optimize("-finline-small-functions")
49 #pragma GCC optimize("-ftree-switch-conversion")
50 #pragma GCC optimize("-foptimize-sibling-calls")
51 #pragma GCC optimize("-fexpensive-optimizations")
52 #pragma GCC optimize("-funsafe-loop-optimizations")
53 #pragma GCC optimize("inline-functions-called-once")
54 #pragma GCC optimize("-fdelete-null-pointer-checks")
55 #include
56 #include
57 #include
58 #define ll long long
59 #define LG 32
60 #define N 200100
61 using namespace std;
62 
63 ll n,m,ten[40],num[N],ans;
64 mapcnt[40];
65 
66 inline ll ws(ll u){ll res=0;for(;u;u/=10) res++;return res;}
67 
68 int main()
69 {
70     ll i,j,p,q;
71     cin>>n>>m;
72     ten[0]=1;
73     for(i=1;i<=LG;i++) ten[i]=ten[i-1]*10%m;
74     for(i=1;i<=n;i++)
75     {
76         scanf("%lld",&num[i]);
77         cnt[ws(num[i])][num[i]%m]++;
78     }
79     for(i=1;i<=n;i++)
80     {
81         p=num[i];
82         for(j=1;j<=LG;j++)
83         {
84             p=p*10%m;
85             if(cnt[j].count((m-p)%m))
86                 ans+=cnt[j][(m-p)%m];
87         }
88         if((num[i]*ten[ws(num[i])]+num[i])%m==0) ans--;
89     }
90     cout<<ans;
91 }

E题：

　　题意：给出一个节点数量为n的树，边权都为1,。然后定义dis[i]为i号节点到1号节点的最短路径的距离。然后有一个加边的操作，你可以随意连接两个点，边权为1。显然这个加边操作可以显著缩小某些点的dis值。现问你最少要加几条边才可以让所有的点的dis值全部小于3。输出这个加边操作的最小数量。

 1 /*
 2 这题就是贪心啊，我们可以知道如果我们对这颗树（当然若干次操作后就不是一颗树了）上加一条边，那么这条边的一头一定是1（因为这样最优啊）。然后如果我们设Mx为当前最大的dis值，那么这条边连接的一定是一个dis值为Mx - 1的节点（因为这样最优啊）。于是我们就得到了一个贪心。写得优美点就是下面的程序啦！
 3 */
 4 #pragma GCC optimize(3)
 5 #include
 6 #include
 7 
 8 using namespace std;
 9 
10 const int maxn = 2e5 + 5;
11 
12 int n, ans = 0;
13 vector<int> G[maxn];
14 
15 int dfs(int x, int fat) {
16     int dis = 2;
17     for (unsigned i = 0; i < G[x].size(); ++ i) {
18         int v = G[x][i]; if (v == fat) continue;
19         dis = min(dis, dfs(v, x));
20     }
21     if (dis == 0 && x != 1 && fat != 1) ++ ans;
22     return (dis + 1) % 3;
23 }
24 
25 int main(void) {
26     scanf("%d", &n);
27     for (int i = 1; i < n; ++ i) {
28         int x, y; scanf("%d%d", &x, &y);
29         G[x].push_back(y);
30         G[y].push_back(x);
31     }
32     dfs(1, 0);
33     printf("%d\n", ans);
34     return 0;
35 }

F题：

　　题意：现有一面长宽可无线延伸的网格，现要求将a">aa个格子染成红色，b">bb个格子染成蓝色。要求染成的图形为矩形，且至少有一种颜色染成了矩形。求染成的图形的最小周长。

 1 /*
 2 枚举（a+b）大小的矩形的边长，并暴力判断（注意暴力判断的顺序）能否成立，更新答案。
 3 */
 4 #include 
 5 
 6 #define forn(i, n) for (int i = 0; i < int(n); i++)
 7 
 8 typedef long long li;
 9 
10 using namespace std;
11 
12 const int N = 1000 * 1000;
13 
14 int lens[N];
15 int k;
16 
17 li solve(li a, li b){
18     k = 0;
19     for (li i = 1; i * i <= b; ++i)
20         if (b % i == 0)
21             lens[k++] = i;
22     
23     li ans = 2 * (a + b) + 2;
24     li x = a + b;
25     int l = 0;
26     for (li i = 1; i * i <= x; ++i){
27         if (x % i == 0){
28             while (l + 1 < k && lens[l + 1] <= i)
29                 ++l;
30             if (b / lens[l] <= x / i)
31                 ans = min(ans, (i + x / i) * 2);
32         }
33     }
34     
35     return ans;
36 }
37 
38 int main() {
39     li a, b;
40     scanf("%lld%lld", &a, &b);
41     printf("%lld\n", min(solve(a, b), solve(b, a)));
42     return 0;
43 }
DP平衡树模拟贪心队列

相关

队列的顺序/链式存储实现

DP决策优化小结

dp专题练习

实现延迟消息队列

顺序存储的循环队列（c++实现）

使用webgl(three.js)搭建一个3D智慧园区、3D建筑，3D消防模拟，web版3D,bim管理系统——第

noip多校模拟30

腾讯云搭建个人博客wordpress

2019.11.8模拟赛

dp多维状态的优化

CS5265完全替代兼容龙迅LT8711|Type-C/DP1.2 to HDMI2.0方案芯片|CS5265兼容TYPEC手机

[NOIP模拟赛] 2021.11.16

标签