唯沁

分类

总结(2) 题解(16)

/ 注册

全部文章（共24篇）

题解 | #网络优化#

线段树优化建图+网络流首先可以看出是求最大流源点向用户连一条容量为1的边，每个游客向可以登录的线连容量为1的边，最后m条线向汇点连边，第i条线连一条容量为v[i]的边求最大流即可。但是，连边操作太多了，可以达到O(nm),所以我们用线段树优化建图。以及，最后的最后，不要忘记多组输入呜呜呜～～...

2021-10-08

0 360

题解 | #活着的证据#

A题简单的贪心问题，首先把V从前向后每位都分配一个，剩下的V都是无用的了，然后考虑用I将剩下的没有V的位置填充，剩下的从前向后尽可能的分配给前面的位。 #include<bits/stdc++.h> using namespace std; typedef long long ll;...

2021-10-05

0 452

题解 | #深海少女#

A题对于这个关系式，xi和yi都是下标，只要记录一下每个下标被加或减的次数，把相加次数最少的分配给最小的值就可以 #include<bits/stdc++.h> using namespace std; const int N&nbs...

2021-09-30

0 479

差分约束系统

差分约束系统的解法如下：1、根据条件把题意通过变量组表达出来得到不等式组，注意要发掘出隐含的不等式，比如说前后两个变量之间隐含的不等式关系。2、进行建图：首先根据题目的要求进行不等式组的标准化。(1)、如果要求取最小值，那么求出最长路，那么将不等式全部化成xi – xj >= k的形式...

2021-09-01

0 476

CF1325F DFS序与独立集

求出一个大于 ⌈ n ⌉的环或找出 ⌈ n ⌉个点的独立集。可以用DFS树的方式找环，a到b 在树上的链与非树边(a,b)会形成一个环，环的大小为∣dep[a]−dep[b]∣+1。环一定由某条链和某条非树边组成。下面证明如果不存在这种环，就一定存在至少⌈ n ⌉个点的独立集由于不存在这种环，因...

2021-08-31

0 405

2021牛客多校1补题

F题求出L-R中多少个数满足子串是3的倍数鸽巢原理：长度>3时，一定会重复出现mod 3相等的数字，那么那一段就是3的倍数只需要计算999以内即可 G题给出列A,B，交换k次A的不同数字，使得AB对应位置差的绝对值之和最大。解：可以理解为分配+、-号，满足A和B的+号总和和-号总和相等n>...

2021-08-30

0 467

namomo camp笔记day6

讲课：博弈和构造对称博弈：n个硬币围成一圈，每人每次取走一个或两个相邻硬币，取完者胜。解：n<=2 先手胜，否则先手必败（先手会把圆变成一条链，后手把它变成两个相同的链，然后后手的操作和之前先手操作一致，这样最后取光的操作一定是后手进行的）巴什博弈：一堆石子，两人轮流每次取1、2、3颗，取...

2021-08-26

0 582

Codeforces Global Round 14

A题 #include<bits/stdc++.h> using namespace std; const int maxn = 110; int t,a[maxn],n,x,sum,f; void solve() { cin>>n>>x; s...

2021-05-13

0 397

Codeforces 716 div2

A题题意：问能否找出一个子序列使得其积不是完全平方数解：只要找到一个不是完全平方的元素就可以找到这样的子序列 import java.util.Scanner; public class Main { public static void main(String[] args) { ...

2021-04-30

0 521

Codeforces 108

A题题意：r个红豆和b个绿豆，要求跟他们分组，每组至少有1个红豆和1个绿豆，且红豆的绿豆的个数相差不能超过d代码： #include<bits/stdc++.h> using namespace std; typedef long long ll; ll t,a,b,c; int m...

2021-04-30

0 562