名字不能相同

原创 学校网络 （tarjan）

题目一：对于环的存在，只要换上的一个学校获得软件，那么整个环都会获得软件，可以使用tarjan对连通分量进行缩点，此时得到一个有向无环图，入度为0的点的数量就是答案。题目二：设入度为0的点数量是a，出度为0的点数量是b，那么答案是max(a, b);#include<bits/stdc++.h> using namespace std;#define ff first#define ss second#define lowbit(x) (x&-x)#define pf(a)

原创 windows11 如何断开网络映射

问题描述：每次IP更换就需要映射一个新的网络，之前的废弃了，出现很不友好的画面。**环境：**我的电脑是win11家庭版解决办法：windows11家庭版真的拉，动不动资源管理器就崩\sout{windows11家庭版真的拉，动不动资源管理器就崩}windows11家庭版真的拉，动不动资源管理器就崩失败方法：添加一些命令，寻找windows资源管理器...

原创 2022-05-19

http://oj.daimayuan.top/problem/199给定一个长度为 nn 的数组a1,a2,…,ana_1,a_2,…,a_na1​,a2​,…,an​，接下来进行 n−1 次操作。每次选择一个下标 x ，将 axa_xax​和 ax+1a_{x+1}ax+1​合并成 ax×ax+1mod1000003a_x×a_{x+1}mod1000003ax​×ax+1​mod1000003，并且你会获得 (ax−ax+1)2(a_x−a_{x+1})^2(ax​−ax+1​)2 的分数。所以每

原创 #55. 出栈序列判断

给定一个出栈序列，问进出栈的情况如何？map 存一下栈里出现了哪些元素，栈中元素是单调递增的，每当出现一个该弹出的元素，则弹出它以及它之后的所有元素。再while循环判断，栈中是否还有需要弹出的元素，知道栈中没有需要弹出的元素，那就让后边的元素进栈。void solve(){ stack<int> s; cin >> n; rep(i,1,n) { scanf("%d", &a[i]); } map<int, int> mp; int l

原创 #500. 异或和或

给定01串 s 和 p， 每次选择两个位置i 和 j， i!=ji != ji!=j定义x和yx=aix = a_ix=ai​ XOR aja_jaj​y=aiy = a_iy=ai​ OR aja_jaj​令 aia_iai​ = x , aja_jaj​ = y或 aia_iai​ = y，ai=xa_i = xai​=x问s 能不能变到 p注意：s和p的长度不一样发现1：如果数组中一个1，则可以变成若干个1，或者全1例如：001 可以变为：010、 100、 110、 111、 10

原创 #496. 跳跳

跳跳 - Problem - Daimayuan Online Judge给定n个点，从某个点（x，y）跳到其他点，每次跳到 （x + a，x+b），可以跳多次，但每次只有一个(a, b) 可选问（a，b）最少有几种？n 只有500，暴力跑出所有情况，时间复杂度：O(n2)O(n^2)O(n2)因为可以走多次，存最下步，最后统计个数#define rep(i,l,r) for(int i = l; i <= r; i++)#define PII pair<int,int>vo

原创 #496. 跳跳

跳跳 - Problem - Daimayuan Online Judge给定n个点，从某个点（x，y）跳到其他点，每次跳到 （x + a，x+b），可以跳多次，但每次只有一个(a, b) 可选问（a，b）最少有几种？n 只有500，暴力跑出所有情况，时间复杂度：O(n2)O(n^2)O(n2)因为可以走多次，存最下步，最后统计个数#define rep(i,l,r) for(int i = l; i <= r; i++)#define PII pair<int,int>vo

原创 463. 饿饿 饭饭

用 map 存 a[i] 出现的次数，map默认从小到大排序如果当前 k 可以使得 饭量为 a[i] 的这些同学吃饱，那么把这些同学从队伍中删去，维护队伍长度变化。否则，每打完一次饭，当前同学剩余饭量最少为0。，维护当前队列即可。#include <bits/stdc++.h>using namespace std;#define ll long long#define PII pair<int,int>const int N = 1e5 + 10, inf = 0x

原创 1672D - Cyclic Rotation

1672D - Cyclic Rotation逆向思维：b 能否转成 a ？选择一个位置 j， bj−1==bjb_{j-1} == b_jbj−1​==bj​, 那么可以把 j-1 这个位置的值放到前面去双指针实现：if(bj==ai)if(b_j ==a_i)if(bj​==ai​) i ++, j ++;if(bj==bj−1)if(b_j == b_{j-1})if(bj​==bj−1​) 在mutiset中寻找是否出现过 bj−1b_{j-1}bj−1​ ，如果出现过意味着可以把它插

原创 1672D - Cyclic Rotation

1672D - Cyclic Rotation逆向思维：b 能否转成 a ？选择一个位置 j， bj−1==bjb_{j-1} == b_jbj−1​==bj​, 那么可以把 j-1 这个位置的值放到前面去双指针实现：if(bj==ai)if(b_j ==a_i)if(bj​==ai​) i ++, j ++;if(bj==bj−1)if(b_j == b_{j-1})if(bj​==bj−1​) 在mutiset中寻找是否出现过 bj−1b_{j-1}bj−1​ ，如果出现过意味着可以把它插

原创 1672D - Cyclic Rotation

1672D - Cyclic Rotation逆向思维：b 能否转成 a ？选择一个位置 j， bj−1==bjb_{j-1} == b_jbj−1​==bj​, 那么可以把 j-1 这个位置的值放到前面去双指针实现：if(bj==ai)if(b_j ==a_i)if(bj​==ai​) i ++, j ++;if(bj==bj−1)if(b_j == b_{j-1})if(bj​==bj−1​) 在mutiset中寻找是否出现过 bj−1b_{j-1}bj−1​ ，如果出现过意味着可以把它插

原创 I. Ice Cream Shop

原创 尺取法（双指针）

原创 单调栈、单调队列

维护单调队列：如果后来的位置更优，则对队列进行更新。滑动窗口模板题// Problem: 滑动窗口// Contest: AcWing// URL: https://www.acwing.com/problem/content/156/void solve() { int l = 1, r = 1; for(int i = 1; i <= n; i++) { while(l <= r && q[l] <= i - m) l++; while(l &

原创 AcWing 3418. 杨辉三角形

杨辉三角求某个数 n 在第几个数出现？ n<=109n<=10^9n<=109（1）观察发现，10910^9109 比较坏的情况下出现在什么位置：C450002>109C^2_{45000} > 10^9C450002​>109 如果这个位置都找不到，那么肯定在Cn1C^1_{n}Cn1​ 处 ， 而且 C3216<109但C3217>109C^{16}_{32} < 10^9 但 C^{17}_{32} > 10^9C3216​<1

原创 3417. 砝码称重

dp[i][j]; // dp[i][j] 表示前i个砝码，能表示j克的重量吗？ // 初始状态： dp[0][0] = 1;// 转台转移： dp[i][j] = dp[i-1][j] || dp[i-1][a[i]+j] || dp[i-1][abs(a[i]-j)];表示不放第 i 个砝码，放第 i 个砝码在左边，放第 i 个砝码在右边#include <iostream>#include <cstring>#include <algorithm>

原创 最受欢迎的牛（targan）

如果是一个拓扑图，存在最受欢迎的牛 等价于 只有一个出度为0的节点。如果不是一个拓扑图，需要使用tarjan算法进行缩点，最后符合条件的点的强连通分量即使答案。#include <bits/stdc++.h>using namespace std;const int N = 1e5 + 10;int stk[N], top;int e[N], ne[N], h[N], idx;int dfn[N], low[N], id[N], ins[N], Time, cnt;int dou

原创 招募军队 （超级源点）

超级源点+最大/最小生成树招募军队#include<bits/stdc++.h> using namespace std;#define ff first#define ss second#define lowbit(x) (x&-x)#define pf(a) printf("%d\n",a)#define mem(x,y) memset(x,y,sizeof(x))#define dbg(x) cout << #x << " = " <

原创 C - Chat Ban

C - Chat Ban注意二分边界条件吧// Problem: C. Chat Ban// Contest: Codeforces - Educational Codeforces Round 117 (Rated for Div. 2)// URL: https://codeforces.com/contest/1612/problem/C// Memory Limit: 512 MB// Time Limit: 2000 ms// // Powered by CP Editor (ht

原创 E1 - Escape The Maze (easy version)（双向广搜）

有一个无向图，Vlad和他的k个朋友分别在不同的房间，Vlad在一号房如果Vlad走到一个只有一条通道的房间，他就获胜如果他的朋友在途中遇到他，则朋友获胜每个单位时间，每人可以移动一个单位距离。解法：双向广搜初始队列：每个被朋友占领的节点+Vlad所在的节点遍历队列，如果这个节点没有被占领过，相邻的节点优先占领// Problem: E1. Escape The Maze (easy version)// Contest: Codeforces - Codeforces Round #756

原创 D. Weights Assignment For Tree Edges （数+构造）

D. Weights Assignment For Tree Edges给定b数组：对于b数中的一个数，bib_ibi​ 是i个祖先给定一个排列p，要求dist[p[i]]<dist[p[i+1]]dist[p[i]] < dist[p[i+1]]dist[p[i]]<dist[p[i+1]] ，也就是说p排列给了从根节点到各个节点距离大小关系。dist[i]dist[i]dist[i] 表示从根节点到当前节点的距离（1）根节点的dist[p[1]]=0dist[p[1]]=0di

原创 B - Triple Shift（偶排列）

atc之旅

原创 D. Yet Another Sorting Problem (偶排列)

奇偶排列：一个排列中，如果交换两个数，那么它排列的奇偶性一定发生变化。参考：百度-奇排列-性质1（1）考虑数组中的数两两不相同：比较当前数组与不下降数组之间排列奇偶性。如果它们排列的奇偶性相同，可以变化，否则不行。具体请自行证明。（2）数组中有相同的数：数组逆序对奇偶性可以随意转换，就一定能转换为不下降子序列。逆序对树：acwing板子// Problem: D. Yet Another Sorting Problem// Contest: Codeforces - Codeforces Ro

原创 dfs 判断二分图 && dsu判断图的连通性

HDU-3478题目大意：给一个起点，判断是否存在一个某个时刻，能到达所有点？（1）判断图是不是连通的（2） 如果是二分图，那么图会被分为两个部分，不能到达#include <iostream>#include <bits/stdc++.h>using namespace std;const int N = 1e5 + 10;int fa[N], color[N];std::vector<int> G[N];int find(int x){

原创 python 中os.path.join 的坑，解决办法

import osa = user/iconb = 1.pngc = os.path.join(a, b)print(c)明显不是我们想要的结果！仔细想想，这个函数的作用不就是加了一个 /直接手动加上去就行啦a = user/iconb = 1.pngc = a + '/' + bprint(c)

原创 1614C Divan and bitwise operations

尺取法模板注意 每次取出的钱不能超过ATM机剩余的余额：sum+a[t]+S>=0sum + a[t] + S >= 0sum+a[t]+S>=0typedef long long ll;const int N = 2e5+10;int n;ll S, a[N];void solve(){ scanf("%d %lld", &n, &S); for(int i = 1; i <= n; i++) scanf("%lld", &a[i])

原创 Educational Codeforces Round 117 (Rated for Div. 2)

a稍微进行分类讨论#include <iostream>using namespace std;#define eps 1e-8const int maxn = 1e6; void solve(){ int a, b, x, y; // c(x, y); // A(0,0) B(x,y) scanf("%d %d", &a, &b); int dis_ac = x + y; // 2x + 2y = a + b; ---- (1) // 2abs(a

原创 rmq（区间最值问题）

rmqRMQ（Range Minimum/Maximum Query），即区间最值查询，是指这样一个问题：对于长度为nnn的数列AAA，设A[i]A[i]A[i]是要求区间最值的数列，F[i,j]F[i, j]F[i,j]表示从第iii个数起连续2j2^j2j个数中的最大值。（DP的状态）例如：A数列为：3 2 4 5 6 8 1 2 9 7F[1，0]F[1，0]F[1，0]表示第1个数起，长度为20=12^0=120=1的最大值，其实就是333这个数。同理F[1,1]=max(3,2)=3F

原创 AcWing 1022 (二维费用背包)

#include <iostream>#include <cstring>#include <algorithm>using namespace std;const int N = 1010, M = 510;int V1, V2, n;int f[N][M]; // f[i][j] 需要i精灵球的数量，受到的伤害是j，表示收获最多的精灵个数int main(){ cin >> V1 >> V2 >> .

原创 1598B

给定n * m 的网格，一开始全部涂成红色。有两种操作，一种是切割，一种是涂蓝色。切割的限制：不能切成1*1 的网格，可以切无限次；涂蓝色没有限制。涂蓝色最少多少次，可以使得相邻的网格颜色不一样？通关观察可以发现，切割成1* 3 或者 3 * 1 的网格比较划算，此时的红蓝比是 2:1按列3个一切， 列可以切多少次呢？ int y = (int)floor(1.0*m / 3)，此时有n行因此：ans = y * n。 3个一切如果剩下一列，那么ans += (int)floor(1.

原创 acwing278（0/1背包）

acwing278（0/1背包）acwing278（0/1背包）acwing278（0/1背包）（1）体积一定，求价值的最大或者最小价值状态转移方程：f[i][j]=f[i−1][j]+f[i−1][j−v[i]]f[i][j] = f[i-1][j] + f[i-1][j-v[i]]f[i][j]=f[i−1][j]+f[i−1][j−v[i]] 不选择第i个数，选择第i个数f[i]f[i]f[i] 每次出现的时候，没有被更新过，是f[i−1]f[i-1]f[i−1] cin >&gt

原创 F. Fixing Banners

// Problem: F. Fixing Banners// Contest: Codeforces - The 2019 China Collegiate Programming Contest Harbin Site// URL: https://codeforces.com/gym/102394/problem/F// Memory Limit: 512 MB// Time Limit: 1000 ms// // Powered by CP Editor (https://cpedito

原创 Third-Party Software - 2（贪心+最小覆盖问题）

#include<iostream>#include<cstdio>#include<string>#include<ctime>#include<cmath>#include<cstring>#include<algorithm>#include<stack>#include<climits>#include<queue>#include<map>#in

原创 Codeforces Round #750 (Div. 2) a-d

//all a, b, c;void solve(){ cin >> a >> b >> c; ll sum = a + 2*b + 3*c; if(sum&1) cout << 1 << endl; else cout << 0 << endl; }//bint n, m;ll a[N];ll qmi(ll a, ll b){ ll res = 1; while(b) {

原创 贪心（排序）

https://codeforces.com/gym/102215/problem/F#include <iostream>#include <cstring>#include <algorithm>#define PII pair<int,int>using namespace std;#define ll long longconst int N =3e5 + 10;int n;struct Node { ll a, b;

原创 M. Camouflage (搜索)

从外层开始搜，标记哪些在外围的点找到内层的点，记录要涂的点数，合适就填上。// Problem: M. Camouflage// Contest: Codeforces - The 15-th BIT Campus Programming Contest - Onsite Round// URL: https://codeforces.com/gym/102878/problem/M// Memory Limit: 256 MB// Time Limit: 1000 ms// // Powe

原创 G. Nim plus

一个 简单 sg 函数#include <iostream>#include <cmath>#include <cstring>using namespace std;int n, m;int f[2][105];int sg[2][5005];void getSG() { for (int i = 1; i <= n; i++) { for (int j = 1; j <= m and f[0][j] <=

原创 C. Portal

https://codeforces.com/contest/1581/problem/C暴力n^4 方，当枚举最后一列之前，判断是否大于16，大于就剪枝，16是最坏情况下的修改数为什么16是最坏情况呢？想想，5行4列，四个边角不需要改变，那就是4*5 - 4 = 16；先枚举行，再枚举列，枚举最后一列的时候，之前的矩形需要修改的数量已经是确定好了，如果已经确定好的数都大于最坏情况，直接break;然后就是一些预处理啦， 保证每次在O(1)时间内算出当前方案需要修改的数。// Problem:

原创 D. Productive Meeting (大根堆)

放到堆里，每次取出堆顶的两个元素来判断就好了// Problem: D. Productive Meeting// Contest: Codeforces - Codeforces Round #744 (Div. 3)// URL: https://codeforces.com/contest/1579/problem/D// Memory Limit: 256 MB// Time Limit: 2000 ms// // Powered by CP Editor (https://cpedi

原创 B. Shifting Sort (思维)

思路大家都能想到，代码不是很好写// Problem: B. Shifting Sort// Contest: Codeforces - Codeforces Round #744 (Div. 3)// URL: https://codeforces.com/contest/1579/problem/B// Memory Limit: 256 MB// Time Limit: 2000 ms// // Powered by CP Editor (https://cpeditor.org)c