题目链接：https://codeforces.com/contest/1362/problem/E题目大意：多样例：一个n和p，下面输入n个数k[i],每个数代表p^k[i],把这些数分成两组。使他们的和的差值最小。输出这个差值mod 1e9+7。 思路一：把k[i]从大到小排序,如果k[i]为偶数，这个各种分配一半。如果为奇，那么一个就分配多了一个。我们希望用后面的 k[i]去弥补这个差值。模拟这个过程就可以了。思路二：直接用哈希暴力搞过去。 #include <bits/stdc++.h> #define LL long long using namespace std; ...

题目链接：https://ac.nowcoder.com/acm/contest/5795/M题目大意：有n堆石子。n一定为偶数。每次可以选择其中n/2堆。每堆可以任意取石头个数，必须取。谁不能取就输了。小陀螺先采取行动。如果小陀螺可以赢输出：Happy Little Gyro 否则输出：Sad Little Gyro思路： #include <bits/stdc++.h> using namespace std; int a[55]; int main(){ int t; scanf("%d", &t); while(t--){ ...

题目链接：https://ac.nowcoder.com/acm/problem/241584 #include <bits/stdc++.h> using namespace std; vector<int> v[30]; int d[30], f[1<<22]; int slove(int i, int t){ int L=0, R=v[i].size()-1, k=-1; while(L<=R){ int mid=(L+R)/2; if(v[i][mid]<=t){ ...

题目链接：https://ac.nowcoder.com/acm/problem/16655思路： 石头可能隔的非常远。我们必须离散化，如果a[i]-a[i-1]=90我们可以设置a[i]=a[i-1]+90。然后直接DP就可以了。 #include <bits/stdc++.h> using namespace std; int a[205], b[205], f[300*105], vis[300*105]; int main(){ int L, S, T, M; scanf("%d%d%d%d", &L, &S, &a...

题目链接：https://ac.nowcoder.com/acm/contest/5795/L给你长度为n的一个扩号序列。m次修改，每次修改把第x个扩号取反方向。并且修改后询问扩号序列是否合法。思路：用一个线段树维护这个扩号序列'('：-1')'：1每次修改其实就是一个单点修改。如果前缀和<0那么就不合法。如果前缀和>0并且1-n的和为0就合法。 #include <bits/stdc++.h> using namespace std; char s[100005]; int sum[4*100005], mi[4*100005]; void gx(int i, in...

给你一个A，B，C，D并且A<=B<=C<=D问A<=x<=B<=y<=C<=z<=D问x，y，z可以组成多少个三角形。思路：我们枚举x+y的值。那么z的取值范围就知道了。现在求x+y=i的方案数。 如果x为A,那么y为i-A如果x为A+1,那么y为i-A-1...如果x为B,那么y为i-B容易观察到y的变化范围为[i-B,i-A]不过y还需要在[B,C]之内,取区间交就行了 #include <bits/stdc++.h> #define LL long long #define mid (l+r>>1) usin...

给你n个柱体，让你用1x2的方块覆盖，问最多能够覆盖多少个方格。 思路：我们用类似于二分图染色的思想。把方块染成为黑白。假设黑色块比白色块多。那么对于一个没有匹配的白块一定有一个没有匹配的黑块和其对应，而且一定能从这个没有匹配的白块开始找到一条增广路h-b-h-b-h到这个没有匹配的黑块，那么这个白块一定可以匹配成功。所有覆盖的块数就是min(黑块数， 白块数)。 #include <bits/stdc++.h> #define LL long long #define mid (l+r>>1) using namespace std; int main(){ ...

给你一个01串，一次操作可以把0改成1，把1改成0。要求最少的改变次数，使这个01的1是间隔k出现。 思路： #include<bits/stdc++.h> #define LL long long using namespace std; char s[1000005]; int f[1000005][2], sum[1000005]; int main(){ int t; scanf("%d", &t); while(t--){ int n, k, ans=0; scanf("%d%d&q...

输入n，m求n!在m进制下末尾0的个数。n, m<1e18 #include<bits/stdc++.h> #define LL long long using namespace std; int prime[]={0, 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97}; LL ind[105], cnt[105]; LL getcnt(LL x, LL n){//计算1-n中所有质因子x的总和个数 LL res=0;...

有n个房子在x轴，房子的状态可以用0，1表示：0：不可以安装路由器1：可以安装路由器每个房子可以直接连接到互联网。第i个房子代价为i。也可以安装路由器第i个房子代价为i。但是路由器可以使[i-k, i+k]都连上网，求出所有房子全部连上网需要的最小代价。 #include<bits/stdc++.h> using namespace std; typedef long long LL; const int N=2e5+7; const LL INF=1e18; LL a[N], f[N][2]; struct SegTree { LL T[N<<2]; ...

#include<bits/stdc++.h> #define LL long long using namespace std; char ch[55][2505]; int f[55][55], val[55][55], DP[55][2505]; //val[i][j]：第i个木板涂j次色的最大正确格子数 //DP[i][j]:前i个木板涂j次色的最大正确格子数 int main(){ int n, m, T; scanf("%d%d%d", &n, &m, &T); for(int i=1; i<=...

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=6071题目大意：有1，2，3，4四个点。是一个环。你可以从i到i+1，i-1。给了你1-2,2-3,3-4,4-5的距离。和一个k。问你从2出发，回到2的>=k的最短路为多少。思路： #include<bits/stdc++.h> #define LL long long using namespace std; vector<pair<int, LL> > v[5]; queue<pair<int , LL> > q; LL d...

思路：因为只能从高度高到高度低。那么边就是有向的。而且最后一定是一棵树。第一问，直接dfs就可以了。标记可以到达的点。第二步，把这些点之间的边提出来。然后跑一个kruskal就可以了。边的排序：如果高度不一样，高度高的在前面，如果高度一样，边短的在前面。因为我们总是先访问高度高的边。如果直接按高度小的在前。这个样例： 3 3 3 2 1 1 3 2 1 2 8 2 3 4 就过不了 #include<bits/stdc++.h> #define LL long long using namespace std; vector<vector<int> > v...

不离线直接查询的麻烦在于查询的时候有两个东西都是未知的——区间左右端点和x。我们考虑离线，是要通过离线相关的操作把这询问有关的两个不同性质变得只问一个，也即，如果我们要问区间[l,r]有多少个数就保证当前所有数都是小于等于x的，如果要问小于等于x有多少个数，就要保证目前只有区间[l,r]里面的东西。 1. #include<bits/stdc++.h> using namespace std; typedef long long LL; LL s[1000005], n=1e5+10; void add(LL x,LL z) {for (LL i=x;i<=n;i+=(i...