#1024# 程序员调bug，改一处动全身但我们ACMer

题目大意 给你两个字符串，N,M |N|>|M|，经过转换之后，问你，连续的一段，能够匹配上的最大元素个数。 n <1e5 题目分析 题目求区间内匹配数最大。考虑区间有n^2个，暴力做显然会T，所以这里考虑，用FFT 将第二个串反置，这样我们相邻位置的匹配，可以转化为，对应位置的匹配 如下图： 此时我们发现，最大匹配数 就是 i+j的系数 因此，我们分别求R,S,P的匹配，三次FFT之后将系数加起来，求一个最大值即可 代码分析 #include <bits/stdc++.h> using namespace std; const int maxn = ...

A 树形dp 题目大意： 一棵5e3的树，可以选择一些点，放上基站，如果u上的基站价值为d，那么距离u小于等于d的点都会被覆盖，问使得整棵树被覆盖需要的最小价值。 题目分析 设 f [ u ] [ i ] ...

题目链接 https://codeforces.com/gym/102007 A- A Prize No One Can Win 题目大意 给一个序列，每个数表示物品的价值，要求选择一些数，使得任意两个物品的价格不能严格大于W 分析思考 必然是最大的两个相加不大于w 即可。 但是这个题的特殊情况就是：考虑所有物品都大于W B-Birthday Boy 题目大意 给你一些日期，表示同事的生日。要找到一个日期。离上一次同事过生日最久 分析思考 这是一个需要细心的模拟题。 那么计算两个日期之间的距离。要仔细一点。 C-Cardboard Container 题目大意 给定一...

洛谷P1966 题目大意 给两个序列 a i , b i a_i,b_i ai​,bi​ ，可以交换相邻两数，要求满足 ...

题目大意： 两个人轮流从若干堆牌中取数，A只能从上往下取，B只能从下往上取。 A先取 两人都想自己的数之和尽可能大。 问两个人的数字大概有多少。 分析： 因为对称性。两个人如果有一个人想放弃自己这一边的一个数，而去取另一边的数的话，对手一定可以先取走这个数，所以不存在这种情况。 每个人都只能取自己这半边的数。 对于所有中间的数，应该是从大到小轮流取。 代码： #include <bits/stdc++.h> using namespace std; vector<int>v; int main() { int n; scanf("%d&quo...

采用先来先服务（FCFS），最短作业优先（SJF）、响应比高者优先（HRRN）的调度算法 #include <bits/stdc++.h> using namespace std; const int maxn = 1e5+50; struct JCB { string name; int subtime; int runtime; int resource; int t; int tc; double w; string state; int idx=0; bool operator <(co...

两种调度方式 优先权法 时间片轮转法 #include <bits/stdc++.h> using namespace std; int n; struct node { int cpu; int priority; int idx=0; bool operator<(const node &oth)const { return oth.priority>priority; } }; vector<node> process; struct state { int cput...

基于udp的群聊系统

tips 本文专门用于介绍一些非常好用的函数和操作，学习一个是一个。可以使得比赛的时候大大简化工作量。 计算二进制中的1的个数 __builtin_popcount(x) 计算gcd __gcd(x,y) 计算全排列 next_permutation(a,a+n) auto string s; cin>>s; for(auto c:s) cout<<c<<" "; 判断乘积是否超long long bool Overflow(ll x,ll y) { if(x>LLONG...

稍微转化一下，将若干个相同的数合并成一个区间，权值为数的个数，构成一个新的数据 将这些数据求区间最值就可以了。 #include <bits/stdc++.h> #define cl(a) memset(a,0,sizeof(a)) #define sc(x) scanf("%d",&x) using namespace std; const int maxn = 2e5+50; int n,q; int p=0;//表示有多少个不同的数 int cnt[maxn],value[maxn];// cnt[i] 表示 第i种数的个数，value[i] 表...

树状数组水题 #include <bits/stdc++.h> #define sc(x) scanf("%d",&x) using namespace std; const int maxn = 20006; const int maxm = 1e5+50; typedef long long ll; int n; int a[maxn]; int bit[maxm]; int rbit[maxm]; int c[maxn],d[maxn]; int lowbit(int t) {return t&(-t);} void add(int i,...

并查集 路径查询` #include <bits/stdc++.h> using namespace std; const int maxn =1e5+50; const int mod = 1e9+7; int fa[maxn]; int edge[maxn]; int n; void init() { for(int i=0;i<maxn;i++) fa[i]=i; memset(edge,0,sizeof(edge)); } int findset(int t) { if(fa[t]==t) return edge[t]; else return findse...

水题 并查集维护是否有环。如果有两个节点在同一个集合里面。再添加这两个节点会形成环 #include <bits/stdc++.h> using namespace std; const int maxn =1e5+50; typedef long long ll; int fa[maxn]; void init() { for(int i=0;i<maxn;i++) fa[i]=i; } int findroot(int u) { if(fa[u]==u) return u; else return fa[u] = findroot(fa[u]); } bool ...