epee_no_front's Notes
Happy learning! Happy Coding!
Toggle navigation
epee_no_front's Notes
主页
codeforces
人工智能
JAVA
python
Latex&Markdown
计算机系统
关于我
归档
标签
EDU-102-Div2
ACM
2021-01-16 03:08:37
239
0
0
admin
ACM
# edu_102_div2 [toc] ## A Replacing Elements 考虑最小的两个元素的和是否小于等于 $d$ 即可。 ## B String LCM 枚举两个串的“GCD串”即可,注意`C++`中`substr`的使用。 ## C No More Inversions(构造好题) 题目描述:  题解:  自己的理解回头再整理,基本和上面的一致,我寻思这构造的思路挺难想的,自己铁five一个,淦。 发现性质 $\Rightarrow$ 序列拆解以及逆序对总数分析 $\Rightarrow$ 构造 ## D Program 考虑将减号看作-1,加号看作1。计算前缀和数组s。 ST表维护区间最值。 每次询问的答案一定是去除该区间后剩下序列顺序操作能够得到的最大值减最小值+1(若0不在最大值与最小值之间说明0卡在区间边缘要再加一个1). 而剩下序列顺序操作能够得到的最值可能又两种情况: (1)前缀和数组在[1,l-1]的最值(ST表查询) (2)前缀和数组在[r+1,n]的最值(ST表查询)再减去[l,r]区间本身的贡献。 ```cpp #include<bits/stdc++.h> using namespace std; #define N 200020 int op[N], s[N], st1[N][20], st2[N][20], n, m; int a1[N], a0[N]; // 用于计算区间内加号以及减号的个数 char ch[N]; void init(){ scanf("%d%d", &n, &m); scanf("%s", ch + 1); a1[0] = a0[0] = s[0] = 0; for(int i = 1; i <= n; i++){ a1[i] = a1[i - 1]; a0[i] = a0[i - 1]; if(ch[i] == '-') op[i] = -1, a0[i]++; else op[i] = 1, a1[i]++; s[i] = s[i - 1] + op[i]; } return ; } void pre_st(){ // 计算前缀和数组s[]的st表,维护区间最大、最小值 for(int i = 1; i <= n; i++) st1[i][0] = s[i]; for(int i = 1; i <= n; i++) st2[i][0] = s[i]; for(int k = 1; (1 << k) <= n; k++){ for(int i = 1; i + (1 << k) - 1 <= n; i++){ st1[i][k] = min(st1[i][k - 1], st1[i + (1 << (k - 1))][k - 1]); st2[i][k] = max(st2[i][k - 1], st2[i + (1 << (k - 1))][k - 1]); } } return ; } // ST表查询区间最小值 int query_min(int l, int r){ if(l > r) return INT_MAX / 2; // 防止solve中溢出 int k = 0; while((1 << (k + 1)) <= r - l + 1) k++; int minx = min(st1[l][k], st1[r - (1 << k) + 1][k]); return minx; } // ST表查询区间最大值 int query_max(int l, int r){ if(l > r) return INT_MIN / 2; // 防止solve中溢出 int k = 0; while((1 << (k + 1)) <= r - l + 1) k++; int maxx = max(st2[l][k], st2[r - (1 << k) + 1][k]); return maxx; } void solve(int l, int r){ if(l == 1 && r == n){ cout<<1<<endl; return ; } int max1 = query_max(1, l - 1); int max2 = query_max(r + 1, n) - (a1[r] - a1[l - 1]) + (a0[r] - a0[l - 1]); int maxx = max(max1, max2); int min1 = query_min(1, l - 1); int min2 = query_min(r + 1, n) - (a1[r] - a1[l - 1]) + (a0[r] - a0[l - 1]); int minx = min(min1, min2); int o = 0; if(minx > 0 || maxx < 0) ++o; printf("%d\n", maxx - minx + 1 + o); return ; } int main(){ int T; cin>>T; while(T--){ init(); pre_st(); while(m--){ int l, r; scanf("%d%d", &l, &r); solve(l, r); } } return 0; } ``` ## E Minimum Path  两点: 1.问题转化与证明 2.构造状态并建图  建图如下: (x,f1,f2)表示点x,发 表示是否已走了一条double边,f2表示是否已经跳过了一条边。 下图为无向边(x,y,z)的拆点后的状态转移图示。  更清楚的图示:  ```cpp #include<bits/stdc++.h> using namespace std; #define N 220000 typedef long long ll; struct edge{ int to, val, nxt; }e[N * 20]; int head[N * 4], vis[N * 4], len, n, m; ll dist[N * 4]; void add_edge(int from, int to, int val){ e[++len].to = to; e[len].val = val; e[len].nxt = head[from]; head[from] = len; return ; } void init(){ len = 0; scanf("%d%d", &n,&m); for(int i = 1; i <= m; i++){ int x, y, z; scanf("%d%d%d", &x, &y, &z); add_edge(x, y, z); add_edge(y, x, z); add_edge(x + n, y + n, z); add_edge(y + n, x + n, z); add_edge(x + 2 * n, y + 2 * n, z); add_edge(y + 2 * n, x + 2 * n, z); add_edge(x + 3 * n, y + 3 * n, z); add_edge(y + 3 * n, x + 3 * n, z); add_edge(x, y + n, 0); add_edge(y, x + n, 0); add_edge(x, y + 2 * n, 2 * z); add_edge(y, x + 2 * n, 2 * z); add_edge(x, y + 3 * n, z); add_edge(y, x + 3 * n, z); add_edge(x + n, y + 3 * n, 2 * z); add_edge(y + n, x + 3 * n, 2 * z); add_edge(x + 2 * n, y + 3 * n, 0); add_edge(y + 2 * n, x + 3 * n, 0); } return ; } struct qnode{ ll idx, val; qnode(ll x, ll y){idx = x; val = y;} bool operator < (const qnode &x) const{ return val > x.val; } }; void dijkstra(){ memset(dist, 0x7f/3, sizeof(dist)); priority_queue<qnode> q; q.push(qnode(1, 0)); dist[1] = 0; while(!q.empty()){ int cur = q.top().idx; q.pop(); if(vis[cur]) continue; vis[cur] = 1; for(int i = head[cur]; i; i = e[i].nxt){ if(dist[cur] + e[i].val < dist[e[i].to] && !vis[e[i].to]){ dist[e[i].to] = dist[cur] + e[i].val; q.push(qnode(e[i].to, dist[e[i].to])); } } } return ; } void solve(){ dijkstra(); for(int i = 2; i <= n; i++) printf("%lld ", dist[i + 3 * n]); return ; } int main(){ init(); solve(); return 0; } ```
上一篇:
数位DP
下一篇:
文本摘要
0
赞
239 人读过
新浪微博
微信
腾讯微博
QQ空间
人人网
提交评论
立即登录
, 发表评论.
没有帐号?
立即注册
0
条评论
More...
皖ICP备20006612号
皖公网安备 34020302000165号
文档导航
没有帐号? 立即注册