双指针例题
不能小瞧双指针 有时候十分重要
[模板] [c++]12345678for(int i=0,j=0; i<n; i++){ while(j<i&&check(i,j) j++) .....}直接可以替代for i 循环
最简单情况 将几个词分别输出例abc def ghi
[例1] [c++]123456789101112131415161718#include<bits/stdc++.h>using namespace std;int main(){ char str[1000]; gets(str); int n=strlen(str); for(int i=0;i<n;i++) { int j=i; while(j<n && str[i]!=' ') j++; for(int k=i;k<j;k++) cout<<str[k]; //输出两指针之间的 ...
unordered_set
unordered_set set1; 构造unordered_set set2(set1); 拷贝构造set1.count(2); 出现次数unordered_set 无序 set 容器可以和字符串哈希有着类似的作用 也可以一起用
例题acwing1460
[unordered_set做法] [c++]12345678910111213141516171819202122232425262728293031323334#include<bits/stdc++.h>using namespace std;string str;int n,l,r;bool check(int mid){ unordered_set<string> hash; for(int i=0;i+mid-1<str.size();i++) { auto s1=str.substr(i,mid); if(hash.count(s1)) return false; //查找出现次数 如果重复直接寄 hash.insert(s1); } return ...
字符串前缀哈希
字符串前缀哈希当遇到如比较两个区间内的字符是否相同时 可以用这种方法 十分快速
此方法精髓在于用数来表示哈希值 便于理解与记忆 用P=10即十进制来理解如1234h[0]=0 注意从h[1]开始存 不然A为0 算下去AA也为0 所以从1开始h[1]=h[0]P+str[1]=010+1=1h[2]=h[1]P+str[2]=110+2=12h[3]=h[2]P+str[3]=1210+3=123h[4]=h[3]P+str[4]=12310+4=1234
若求一个区间 如L=3 R=4 即34则是 1234-12*10^2即 h[4]-h[2]*P^2即L到R之间的哈希值为 h(R)-h(L-1)*P^(R-L+1) 题里这个P的次方用数组p[]存 需要初始化一下P一般取131
防止长度过长本需mod Q unsigned long long来存储h 它可以溢出 溢出时就相当于模了一个2的64次方
[字符串前缀哈希法] [c+ ...
牛寒5补题
A题贪心二分前缀和可以直接upper_bound(x)找到大于x的第一个数的下标再减一自己感觉还是板子好用
[A] [c++]123456789101112131415161718192021222324252627282930313233343536#include<bits/stdc++.h>using namespace std;long long n,q,a[100010],v[100010],ans;long long k,x,m;long long check(long long x1 ) //升序 找到小于等于x的第一个下标{ long long l=0,r=n; while(l<r) { long long mid=(l+r+1)/2; if(v[mid]<=x1) l=mid; else r=mid-1; } return l; }int main(){ cin>>n>>q; fo ...
牛寒4补题
A题是个数学题就是比较x的y次方和y的x次方哪个大取对数就是ylnx和xlny 直接写代码比较就行
[A] [c++]123456789101112131415161718192021#include<bits/stdc++.h>using namespace std;int main(){ ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); long long x,y; cin>>x>>y; double x1=y*log(x); double y1=x*log(y); if(x1==y1) cout<<min(x,y); else { if(x1>y1) cout<<x<<endl; else cout<<y<<endl; } return 0;}
L题解方程组 注意题目要的是正整数 ...
牛寒3补题
自己太菜 只过了四道签到题 必须好好补补题
A题重大教训 没有用long long 浪费了几次提交
D是博弈题结论是只要是偶数 先手必胜一个奇数的因数一定是奇数 因为如果是偶数 这个偶数与某个整数的乘积一定不会是奇数这个奇数减掉某个因子后 就变成了偶数所以
偶数总可以变成奇数
奇数只可以变成偶数
1是奇数 谁拿到谁就输了综上 总拿到奇数的肯定就输了这道题其实很简单 但是自己没去想过这种博弈问题
C题是一个构造题构造题也没做过 想不出什么思路呜呜原则是找到有既有一般性又有可行性的方式一般考虑将输入分成几类 再分别构造 以满足所有情况
实例是3 4 1 2 则可以构造出n=4k的所有情况 如n=8则有3 4 1 2 7 8 5 6n=5时可以构造出4 5 1 2 3 n=6时有4 5 6 1 2 3这样 n=4k+5 n=4k+6 n=4k+11分别就是nmod4为1 2 3的情况 就覆盖了基本所有整数但是n=7 n<4是肯定无解的需要特判
[C忽远忽近的距离] [c++]12345678910111 ...
