转载一个板子 自适应辛普森法乱搞 https://blog.csdn.net/qq_45735851/article/details/115309408 #include<bits/stdc++.h> #define x first #define y second using namespace std; const int N=1007; const double eps=1e-8; typedef pair<double,double>PDD; struct Circle{ PDD o; double r; }c[N]; int n; PDD q[N]; int ...

思路 以树链剖分+主席树可解决。 要动态开点（不然的话肯定会爆啊） 然后就是对每种颜色（宗教）为根的树进行单点修改还有区间查询。 注：这道题容易被卡常，我宏定义就写炸了很多次。 代码 #include<bits/stdc++.h> #define int long long using namespace std; const int N=1e5+7; vector<int>G[N]; inline void addedge(int u,int v){ G[u].push_back(v); G[v].push_back(u); } int sz[N],fa[N],son...

思路 水题没必要写得像楼上那么复杂吧…… 从左到右出现和目标状态不同的字符和下一个字符改变， 这个操作的次数就是答案了，递推复杂度O(n) 代码 #include<bits/stdc++.h> //#define int long long using namespace std; const int N=2e5+7; const int mod=1e9+7; string str1,str2; int A[N],B[N],n,ans=0; signed main(){ // ios::sync_with_stdio(0);// cin.tie(0);cout.tie(0); //...

思路 水题，m保证是偶数，那么Alice在剩下没翻硬币个数为奇数时永远也赢不了。 只要第一轮没有把硬币全部翻完，那么Bob就可以使坏让没翻的硬币数为奇， 也就是说，n和m不相等的情况下，永远是Bob赢。 代码 #include<bits/stdc++.h> using namespace std; int t,n,m; signed main(){ cin>>t; while(t--){ cin>>n>>m; if(n==m) puts("Yes"); else puts("No"); } return 0; }

思路 bitset优化传递闭包模板。 代码 #include<bits/stdc++.h> #define inf 0x3f3f3f3f #define int long long using namespace std; const int maxn=2007; bitset<maxn>bi[maxn]; int n,ans=0; string str; signed main(){ cin>>n; for(int i=1;i<=n;i++){ cin>>str; for(int j=1;j<=n;j++) bi[i][j]=(st...

思路 图可能会有多个连通块，整个图最多有一个环。 基环树的题目，对每一块找环切断，然后树形dp。 环的切断方式有两种，从那条边的起始点出发做两次dp， 当前块的答案就加上两次dp结果的较大值。 代码 #include<bits/stdc++.h> #define inf 0x3f3f3f3f #define int long long using namespace std; const int maxn=1e6+7; //int read(){ int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-'...

思路 这道题用Py写很方便，因为懒得想dp所以就直接跑暴力过了。 代码 RES=0 maxn=55 dp=[[0 for i in range(maxn)] for j in range(maxn)] mp=[[0 for i in range(maxn)] for j in range(maxn)] def dfs(pos,sc,cnt): global RES if sc<mp[pos][cnt]: return mp[pos][cnt]=sc if cnt==k : if RES<sc*dp[pos+1][n-1]: RES=sc*dp[pos+1][n-1] return ...

思路 区间DP模板题。 代码 #include<bits/stdc++.h> using namespace std; int n,a[505],mx[505][505],mi[505][505],sum[505]; int main(){ scanf("%d",&n); for(int i=1;i<=n;i++){ scanf("%d",&a[i]); } sum[0]=0; for(int i=1;i<=n;i++){ sum[i]=sum[i-1]+a[i]; } memset(mx,0,sizeof(mx)); memset(mi,127/3,s...

思路 解决是个圈的问题，直接复制一遍数组，然后跑区间DP就好了。 区间DP是先枚举长度，再枚举起点，然后在起点和终点之间枚举中间点，表示合并的两个区间。 代码 #include<bits/stdc++.h> using namespace std; int main(){ int n,a[205],mx[205][205],mi[205][205],sum[205]; scanf("%d",&n); for(int i=1;i<=n;i++){ scanf("%d",&a[i]); a[i+n]=a[i]; } sum[0]=0; for(int i=1;i&...

思路 数据量太小了，直接用map存就可以了。 代码 #include<bits/stdc++.h> //#define int long long using namespace std; typedef long long ll; int n; string op,name; map<string,int>mp; signed main(){ ios::sync_with_stdio(0); cin.tie(0);cout.tie(0); cin>>n; for(int i=1;i<=n;i++){ cin>>op; getline(ci...

思路 我们没有办法直接对区间进行开方然后下传，所以pushdown就没必要写了。对于每个数，开方6次之后达到势能上限，其结果必然为0或者1。那么对于整个区间，可以记录开方次数（取区间内开方次数最少的那个值）是否达到6就可以了，或者只要一个区间全为0或1的话，也可以直接返回。 代码 #include<bits/stdc++.h> #define int long long using namespace std; typedef long long ll; const int maxn=2e5+7; int n,m,op,l,r; int tr[maxn<<2],cnt[...

思路 改一下线段树的模板就行了。每次添加数的时候len+1，查询区间是[len-L+1,len]。 代码 #include <bits/stdc++.h> #define int long long using namespace std; typedef long long ll; const int maxn = 2e5 + 7; char ch; int x, m, mod, a = 0, tr[maxn << 2]; void add(int p, int l, int r, int pos, int x) { if (l == r) { tr[p] = (x ...

思路 不得不说这个排序方法真的很妙。设定每个零件有x,y,id,分别表示在A车间加工时间，在B车间加工时间，以及编号。我们比较两个零件的优先级时，加入A应该在B之前加工，那么A.x+B.y+max(A.y,B.x)<B.x+A.y+max(A.x,B.y)已知min(x,y)+max(x,y)=x+y，那么上式就可以化为min(A.x,B.y)<min(A.y,B.x);我们以这个规则对所有零件进行排序（如果存在相等的情况，那么优先加工A区间加工时间少的），问题就解决啦！ 代码 #include<bits/stdc++.h> #define int long long ...

思路 二分 代码 #include<bits/stdc++.h> #define int long long using namespace std; const int maxn=1e5+7; inline void read(int &data){ int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-') f=f*-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} dat...