博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
Codeforces Edu Round 48 A-D
阅读量:4839 次
发布时间:2019-06-11

本文共 4235 字,大约阅读时间需要 14 分钟。

A. Death Note

简单模拟,可用\(\%\)\(/\)来减少代码量

#include 
#include
using namespace std;const int N = 200010;int n, m, a[N], cnt = 0, tot = 0;int main(){ scanf("%d%d", &n, &m); for(int i = 1; i <= n; i++){ scanf("%d", a + i); cnt = (tot + a[i]) / m; tot = (tot + a[i]) % m; printf("%d ", cnt); } }

B - Segment Occurrences

预处理\(A、B\)\(Hash\)表,可以将时间复杂度降到\(O(qn)\)

#include 
#include
#include
using namespace std;typedef unsigned long long ULL;const int N = 1010, B = 221;int n, m, q, len;char s[N], t[N]; ULL P[N], S[2][N];ULL inline get(int l, int r, int c){ return S[c][r] - S[c][l - 1] * P[r - l + 1];}int main(){ scanf("%d%d%d%s%s", &n, &m, &q, s + 1, t + 1); P[0] = 1; for(int i = 1; i <= n; i++){ P[i] = P[i - 1] * B; S[0][i] = S[0][i - 1] * B + s[i]; S[1][i] = S[1][i - 1] * B + t[i]; } while(q--){ int l, r, res = 0; scanf("%d%d", &l, &r); for(int i = l; i <= r - m + 1; i++) if(get(i, i + m - 1, 0) == get(1, m, 1))res++; printf("%d\n", res); } return 0;}

C - Vasya And The Mushrooms

硬核模拟 + 前缀和处理。要不重复的绕完 \(2 * N\) 的格子,从左上角出发,要么\(S\)形绕几次然后绕大圈,要么绕整个的一圈。

可以枚举绕\(S\)格子的次数,\(S\)的部分可以前缀和计算,系数是一样的,后面的部分计算比较复杂。

示例1

第一种情况,前面的部分绕了了几个完整的 \(U\)。要从上方出发。

求(\(now\)代表\(U\)字结束(包括)的列数):

上半部分:$\sum_{i=now + 1}^n a[0][i] * (i * 2) $

我们发现,数列后缀和的后缀和是:

\(sufx[j] = \sum_{i = j} ^ n a[i] * (i - j + 1) = a[j] * 1 + a[j + 1] * 2 + … + a[n] * (n - j + 1)\)

故,把\(sufx[now + 1]\)再加上\(\sum_{i = j} ^ n a[i] * (i * 2 - 1)\),即为答案,后面这部分可用后缀和\(O(1)\)计算。

下半部分:$\sum_{i=now + 1}^n a[1][i] * (n + (n - i + 1)) $

我们想要这样的东西:

\(a[i] * 3 + a[i + 1] * 2 + a[i + 2] * 1\)

这个看上去很像\(Hash\)表的原理,只不过\(b = 1\),可以用hash表的思想在\(O(1)\) 求出这个,然后在用后缀和加上系数既可。

case2

对于第二种情况,只不过将上下颠倒,我们互换一下处理方式既可。

预处理前缀和、后缀和和枚举\(S\)的时间都为\(O(n)\),每次求解只需\(O(1)\),故总共复杂度为$ O(n) $的

#include 
#include
#include
using namespace std;typedef long long LL;const int N = 300010;//s形的预处理int n, a[2][N];LL pre[2][N], s[2][N], suf[2][N], sum[N], prex[2][N], sufx[2][N], ans = -1; int main(){ scanf("%d", &n); for(int i = 1; i <= n; i++) scanf("%d", &a[0][i]); for(int i = 1; i <= n; i++) scanf("%d", &a[1][i]); int S = n >> 1, tot = 0; for(int i = 1; i <= S * 2; i+=2){ s[0][i] = (LL)a[0][i] * (tot++); s[1][i] = (LL)a[1][i] * (tot++); s[1][i + 1] = (LL)a[1][i + 1] * (tot++); s[0][i + 1] = (LL)a[0][i + 1] * (tot++); } for(int i = 0; i < 2; i++) for(int j = 1; j <= n; j++){ pre[i][j] = pre[i][j - 1] + a[i][j]; prex[i][j] = prex[i][j - 1] + pre[i][j]; } for(int j = 0; j < 2; j++) for(int i = n; i >= 1; i--){ suf[j][i] = suf[j][i + 1] + a[j][i]; sufx[j][i] = sufx[j][i + 1] + suf[j][i]; } for(int i = 0; i <= n; i++){ LL tot = sum[i] = sum[i - 1] + s[0][i] + s[1][i]; //如果是奇数,则在下面出发 if(i % 2){ tot += (n + i - 1) * suf[0][i + 1] + (prex[0][n] - prex[0][i] - (n - i) * pre[0][i]); tot += (i * 2 - 1) * suf[1][i + 1] + (sufx[1][i + 1]); }else{ //从上面出发 tot += (i * 2 - 1) * suf[0][i + 1] + (sufx[0][i + 1]); tot += (n + i - 1) * suf[1][i + 1] + (prex[1][n] - prex[1][i] - (n - i) * pre[1][i]); } ans = max(ans, tot); } printf("%lld", ans); return 0;}

D - Vasya And The Matrix

参考题解。 存在性参考异或的性质,\(x\) \(xor\) $ x = 0$ 。

考虑构造一个合理的序列,只需将除了最后一行,最后一列的所有数添上\(0\)

除右下角外其他数照搬数据,右下角用异或尝试既可。

#include 
#include
using namespace std;const int N = 110;int n, m, a[N], b[N], ans = 0;int main(){ scanf("%d%d", &n, &m); for(int i = 1; i <= n; i++) scanf("%d", a + i), ans ^= a[i]; for(int i = 1; i <= m; i++) scanf("%d", b + i), ans ^= b[i]; if(ans != 0)puts("NO"); else{ puts("YES"); ans = b[m]; for(int i = 1; i < n; i++){ for(int j = 1; j < m; j++) printf("0 "); printf("%d\n", a[i]); ans ^= a[i]; } b[m] = ans; for(int i = 1; i <= m; i++) printf("%d ", b[i]); } return 0;}

转载于:https://www.cnblogs.com/dmoransky/p/11247607.html

你可能感兴趣的文章
应用间共享数据方法(一)---sharepreferce
查看>>
傅盛:如何快慢“炼”金山?(转)
查看>>
模拟——作业调度方案
查看>>
node——module.exports
查看>>
爬虫简单实现
查看>>
sql查询语句如何执行
查看>>
CentOS 安装 ceph 单机版
查看>>
导航条选项卡
查看>>
bootstrap table 复选框使用
查看>>
ng -v 不是内部或外部命令
查看>>
图片模糊化处理
查看>>
iOS10 App适配权限 Push Notifications 字体Frame 遇到的坑!!!!
查看>>
一语道破项目管理知识体系五大过程组
查看>>
Mac连接远程Linux管理文件(samba)
查看>>
WPF变换详解
查看>>
flash player 请求本地存储为无限制
查看>>
程序逻辑的组织方式
查看>>
今天正式开通博客
查看>>
javascript逗号添加函数
查看>>
Codeforces Round #307 (Div. 2) E. GukiZ and GukiZiana 分块
查看>>