思路 求最小公倍数，怕他越界所以用了int128。 代码 #include<bits/stdc++.h> #define int __int128 using namespace std; int t,x,y; inline void read(int &data){ int x=0;char ch=getchar(); while(ch<'0'||ch>'9') ch=getchar(); while(ch>='0'&&ch<='9'){ x=x*10+ch-'0'; ch=getchar(); } data=x; } int gc...

思路 贪心正解。用优先队列，每次把最小的两个果子合并了，得到的是最优解。 代码 #include<bits/stdc++.h> using namespace std; priority_queue<int,vector<int> , greater<int> >q; int n,a,b,ans=0; int main(){ scanf("%d",&n); for(int i=1;i<=n;i++){ scanf("%d",&a); q.push(a); } while(q.size(...

思路 应该是单调队列的板子题吧。我用的是双向队列deque（可能会比较慢）。原理很简单，对于需要输出大的那个数的队列，比较最后的元素是否比新加入的数小，是的话就弹出最后的元素，重复此操作，最终得到一个单调递增的队列。如果队首的元素滑出窗口了，那么直接pop掉，对另外一个队列也是同理。 代码 #include<bits/stdc++.h> using namespace std; const int maxn=1e6+7; deque<int>big,sml; int n,k,num[maxn]; int main(){ cin>>n>>k; fo...

思路 贪心可过，首先我们要把第一个坑填上，如果下一坑比较浅，那么我们肯定会顺便把它也填上，如果比较深的话，需要填的深度就减去了前面坑的深度。 代码 #include<bits/stdc++.h> using namespace std; int main(){ int n,a[100005],ans; cin>>n; for(int i=1;i<=n;i++) cin>>a[i]; ans=a[1]; for(int i=2;i<=n;i++){ if(a[i]>a[i-1]) ans+=a[i]-a[i-1]; } cout<&lt...

思路 对于每个选择的点，其周围的点都是不能选的，我们从根结点出发深搜+DP，就能求出答案了。可以参考 没有上司的舞会 ，这道题就是退化版。 代码 #include<bits/stdc++.h> using namespace std; const int maxn=500005; struct E{ int to,next; }edge[maxn<<1]; int n,s,cnt=0,dp[maxn][2]; int x,y,head[maxn],du[maxn]; void addedge(int from,int to){ edge[++cnt].next=head...

思路 这是一个分组背包的模板题，套一下下面的板吧！for 所有的组 ----for k=体力 k>0 -------- for 这个组的操作 ------------ dp递推式 代码 #include<bits/stdc++.h> using namespace std; const int maxn=1005; int main(){ ios::sync_with_stdio(0); cin.tie(0);cout.tie(0); int t,n,m,a[maxn],v[maxn][maxn],w[maxn][maxn],dp[maxn]; cin>>t; w...

思路 可以使用vector，也可以使用双向队列（deque）去做，幸好数据能过D操作，不然就要手打了。 代码 #include<bits/stdc++.h> #define int ll using namespace std; typedef long long ll; deque<int>dq; int x,t; char c; signed main(){ ios::sync_with_stdio(0); cin.tie(0);cout.tie(0); cin>>t; for(int i=1,cnt=1;i<=t;i++){ cin>&gt...

思路 暴力能过，只不过新加入文档编号cnt不能每次都从1数起，而是要从min（cnt++,x）数起（x为删除文档的最小编号）我最终的做法用了优先队列，如果前面的编号被清除了，就往里面加（空间是够用的）。虽然有点多此一举，但事实证明确实会快一点，下面贴两份代码。 优先队列代码 #include<bits/stdc++.h> using namespace std; int main(){ ios::sync_with_stdio(0),cin.tie(0),cout.tie(0); int n,cnt=0,x,a[100050]; string str; priority_queue...

思路 这道题数据范围很小，可以直接给字符串排序，大的在前小的在后，然后直接输出就好了。注意如果用strcmp进行字符串大小比较的话，“123”会在"12"之后，所以正确方法应该是s1+s2>s2+s1。 代码 #include<bits/stdc++.h> using namespace std; string s[25]; int n; int main(){ scanf("%d",&n); for(int i=1;i<=n;i++){ cin>>s[i]; } for(int i=1;i<=n;i++...

思路 感觉是入门题，没用到算法。我们从下往上叠地毯，那么我们从上往下数第一个覆盖这个坐标的地毯的编号就是答案了。如果没有找到就输出-1； 代码 #include<bits/stdc++.h> using namespace std; struct X{ int a,b,g,k; }mt[10005]; int main(){ int n,i,ans=-1,x,y; scanf("%d",&n); for(i=1;i<=n;i++){ scanf("%d%d%d%d",&mt[i].a,&mt[i].b,&...

思路 用前缀和去处理[L,L+1,L+2,....,L+k-1]，[R,R+1,R+2,...,R+k-1]的和。重点是这两个区间不相交，我们如果去枚举两个区间的位置肯定会超时的。那么我们可以考虑一个指针从k出发到n-k，移动过程中记录左边区间的最大值，（可能不变）同时我们右边区间是不断变化的，两者相加的最大值就是答案。 代码 #include<stdio.h> #include<algorithm> using namespace std; typedef long long ll; ll t,n,k,a[200005],sm[200005],ans=0,lf; in...

思路 正好练习一下Trie的板子，用二维数组去装，son[i][j]表示编号i第j个儿子的编号。因为有无字符的根节点，所以答案是从1开始的，然后往下添加新结点，答案就是最大节点的编号。 代码 #include<bits/stdc++.h> using namespace std; int son[1000005][30],cnt=1; char str[70]; int main(){ memset(son,0,sizeof(son)); while(scanf("%s",str)!=EOF){ int now=1; for(int i=0;i<strle...

思路 要维护区间和以及平方和两个线段树，同时支持加法和乘法操作。前面基本套模板就行了，那么我们重点是pushdown怎么写。（这个板子是参照oi-wiki先打出lazy的pushdown的，已经能支持加法维护区间和了） 我们可以用上述式子Pushdown区间平方和。考虑乘法：一开始我们建立cheng记录结点需要pushdown的乘数，在往下传递的过程中 这样两个线段树的更新操作就完成了。 代码 #include<bits/stdc++.h> #define int ll typedef long long ll; using namespace std; const int max...

思路 这道题的大意就是要我们求最小环的长度。我们知道这是一个n个顶点n条边的图，所以每一块最多只有一个环，并保证图中有环。我们可以从任意一个点开始搜索，如果碰到了原来记录过的顶点，那么就记录答案并跳出。如果下一个点已经被记录过了并且不是同一次搜索，那么直接跳出就好了。这个是一个O(n)的做法。 代码 #include<bits/stdc++.h> using namespace std; const int maxn=200005; int n,t[maxn],vis[maxn],dep[maxn],ans=1e7+5,cnt=0; void dfs(int node,int k)...