思路 首先每条线被切至少一次 在此基础上一条线每被割断一次就多付出一份代价 故每个交叉点上用权值较大的线割断权值较小的线比较优 因此，按权值从大到小的顺序切每条线是最优的。 模拟一下切割的过程就能统计出答案了。 代码 //#pragma GCC optimize("Ofast", "inline", "-ffast-math") //#pragma GCC target("avx,sse2,sse3,sse4,mmx") #include<bits/stdc++.h> #define inf 0x3f3f3f3f #define int long long using namesp...

思路 请大家都去看王天懿的贪心问题选讲ppt 代码 //#pragma GCC optimize("Ofast", "inline", "-ffast-math") //#pragma GCC target("avx,sse2,sse3,sse4,mmx") #include<bits/stdc++.h> #define inf 0x3f3f3f3f #define int long long using namespace std; const int N=2e6+7; const int mod=1e9+7; int n,m,ans=0,val[N],a[N]; vector...

思路 按位确定以下，在某一位如果是0，那么经过这些操作之后是0还是1，类似，如果某一位是1的时候也可以这样确定。 那么我们就可以用logn的时间算出某一个数经过这些操作之后的值，但是这里m有点大，我们不能直接枚举。 我们从高位向低位考虑，如果这一位上放0可以变成1，就直接放0，否则看放1是否能变成1并且不会超过m的范围， 这样处理最后就能得到每一位是0还是1啦。 代码 //#pragma GCC optimize("Ofast", "inline", "-ffast-math") //#pragma GCC target("avx,sse2,sse3,sse4,mmx") #include&l...

思路 二分大法好！！ 非正解，T了很多发，终于把他卡过去了。 看题解才知道可以将所有容器进制拆分直接塞，太妙了。 但所有人都在贪心的时候，就让我来一提供一份二分代码吧。 代码 #pragma GCC optimize("Ofast", "inline", "-ffast-math") #pragma GCC target("avx,sse2,sse3,sse4,mmx") #include<queue> #include<stdio.h> #include<algorithm> using namespace std; const int N=1e5+7; ...

rt

题意 其实就是求字典序最小的长度为2^k的01串使得子串不重复出现。 思路 第一个答案很直观可以得到2^k，然后第二个答案爆搜就行了。优先选择0，如果前面以及出现过相应子串就回退填1. 这是一道欧拉回路的题，如何理解呢？就是每个状态都可以连0或者1，都有两个入边和出边。那么必然存在一条路径可以使得走过所有点并且回到原状态，于是就可以求一个欧拉回路来实现这道题。 代码 #include<bits/stdc++.h> const int N=1e4; using namespace std; int n,bin,vis[N],ans[N]; bool dfs(int val,int...

思路 注意审题啊，操作之后没路径的那个人输，所以每个人都会把非关键的点填掉直到只留下一条路径。 然后题目保证了一开始有路径，那么我们判多余的空地数量的奇偶性即可。 代码 //#pragma GCC optimize("Ofast", "inline", "-ffast-math") //#pragma GCC target("avx,sse2,sse3,sse4,mmx") #include<bits/stdc++.h> using namespace std; int n,m; char c; signed main(){ cin>>n>>m; in...

思路 看了别人的题解才恍然大悟啊……赢的人乘k方，输的人乘k，那么a和b乘起来肯定是等于某个数的三次方的， 不过我还是给大家提供另外一种思路吧(我感觉不用动脑)——唯一分解定理。 我们先把a和b唯一分解，假设某一局的k贡献在了a和b的因子p上面，那么其指数k1,k2肯定会满足下面式子的 (k1%3+k2%3)%3==0&&k1<=2*k2&&k2<=2*k1) 然后我们对于所有因子都判一遍（别忘了最后的大质数）就可以了。 ### 代码 ```cpp //#pragma GCC optimize("Ofast", "inline", "-ffast-...

思路 注意看数据范围，nk≤1e7nk\le1e7nk≤1e7就说明了O(n2)O(n^2)O(n2)暴力可过，我们只需要记录前缀和，然后区间长度从大到小试区间和是否可以整除k即可。 代码 #pragma GCC optimize("Ofast", "inline", "-ffast-math") #pragma GCC target("avx,sse2,sse3,sse4,mmx") #include<bits/stdc++.h> #define int long long using namespace std; const int N=2e5+7; const int mod...

代码 //#pragma GCC optimize("Ofast", "inline", "-ffast-math") //#pragma GCC target("avx,sse2,sse3,sse4,mmx") #include<bits/stdc++.h> #define inf 0x3f3f3f3f #define int long long using namespace std; const int N=2e5+7; const int mod=1e9+7; //int read(){ int x=0,f=1;char ch=getchar();while(ch<...

思路 思路很简单，把a和b排个序，然后每次贪心地获得最大快乐值-最小痛苦值，每个三次就加上m,然后记录每次更新后的最大值就可以了。 1e6的数据，不加任何优化会有点危。 代码 #pragma GCC optimize("Ofast", "inline", "-ffast-math") #pragma GCC target("avx,sse2,sse3,sse4,mmx") #include<bits/stdc++.h> #define inf 0x3f3f3f3f #define int long long using namespace std; const int N=1e6+...

代码 //#pragma GCC optimize("Ofast", "inline", "-ffast-math") //#pragma GCC target("avx,sse2,sse3,sse4,mmx") #include<bits/stdc++.h> #define inf 0x3f3f3f3f #define int long long using namespace std; const int N=2e5+7; const int mod=1e9+7; //int read(){ int x=0,f=1;char ch=getchar();while(ch<...

思路 开map记录字符串之间的映射关系就可以了。 代码 //#pragma GCC optimize("Ofast", "inline", "-ffast-math") //#pragma GCC target("avx,sse2,sse3,sse4,mmx") #include<bits/stdc++.h> #define inf 0x3f3f3f3f #define int long long using namespace std; const int N=2e5+7; const int mod=1e9+7; //int read(){ int x=0,f=1;char ...

思路 线段树扫描线的经典题。求周长并和求面积并是类似的，把横线和竖线分别用结构体记录下来，在横线(扫描线)从下往上扫的同时，通过线段树对竖线进行区间修改，然后得出答案，累加到最终结果。 注意每一次更新操作，都要确认当前高度有多少条线段，是否可以合并为更少的线段。 每次答案的贡献是扫描线高度差×竖线条数+扫描线长度 代码 #include<bits/stdc++.h> #define inf 0x3f3f3f3f #define int long long using namespace std; const int N=2e5+7; const int mod=1e9+7; st...