[日志]12-10
我不是柳橙汁
2017-12-10 21:53:02
## 1.今天呢，我考了一套题目。
分数100/300。
很无奈。
### sequence[模拟]
题面就是给你个序列，然后让你找出max{a[i]-a[j]}(i<j)
只要线性找最大值然后拿当前值减即可。
心态爆炸。只有50/100分。mod爆了。
```cpp
#include<cstdio>
long long sa,sb,sc,sd,n,mode;
long long a[5000010];
inline long long v_in(){
char ch=getchar();
long long sum=0,f=1;
while (ch<'0'||ch>'9'){
if (ch=='-') f=-1;
ch=getchar();
}
while (ch>='0'&&ch<='9'){
sum=(sum<<3)+(sum<<1)+(ch^48);
ch=getchar();
}
return sum*f;
}
inline long long f(long long x){
long long res=sa;
res=((res*x)%mode+sb)%mode;
res=((res*x)%mode+sc)%mode;
res=((res*x)%mode+sd)%mode;
return res;
}
inline void prework(){
for (register long long i=2;i<=n;i++)
a[i]=(f(a[i-1])+f(a[i-2]))%mode;
}
int main(){
freopen("sequence.in","r",stdin);
freopen("sequence.out","w",stdout);
n=v_in();
sa=v_in();
sb=v_in();
sc=v_in();
sd=v_in();
a[0]=0;
a[1]=v_in();
mode=v_in();
prework();
long long maxn=a[1],ans=0;
for (long long i=2;i<=n;i++){
if (maxn<a[i]) maxn=a[i];
if (ans<maxn-a[i]) ans=maxn-a[i];
}
if (ans&1) ans++;
printf("%lld\n",ans>>1);
return 0;
}
```
### travel[并查集]
0/100分。
并没有做这道题。
如果强行暴力的话可以60分。
然而正解是并查集。
我们只需要按照权值将询问和边从小到大排序
然后按顺序每次询问将权值小于该询问权值的边连起来合并即可。
```cpp
#include<cstdio>
#include<algorithm>
using namespace std;
struct edge{
int u,v,w;
bool operator < (const edge &k)const{
return w<k.w;
}
}e[200010];
struct query{
int x,w,id;
bool operator < (const query &k)const{
return w<k.w;
}
}qu[100010];
int fa[100010],size[100010],ans[100010];
int n,m,q;
inline int v_in(){
char ch=getchar();
int sum=0,f=1;
while (ch<'0'||ch>'9'){
if (ch=='-') f=-1;
ch=getchar();
}
while (ch>='0'&&ch<='9'){
sum=(sum<<3)+(sum<<1)+(ch^48);
ch=getchar();
}
return sum*f;
}
inline int getf(int x){
if (fa[x]==x) return x;
return fa[x]=getf(fa[x]);
}
inline void chain(int u,int v){
int f1=getf(u),f2=getf(v);
if (f1!=f2){
fa[f2]=f1;
size[f1]+=size[f2];
}
}
int main(){
freopen("travel.in","r",stdin);
freopen("travel.out","w",stdout);
n=v_in();
m=v_in();
q=v_in();
for (int i=1;i<=n;i++){
fa[i]=i;
size[i]=1;
}
for (int i=1;i<=m;i++){
int u=v_in(),v=v_in(),w=v_in();
e[i].u=u;
e[i].v=v;
e[i].w=w;
}
sort(e+1,e+m+1);
for (int i=1;i<=q;i++){
int x=v_in(),w=v_in();
qu[i].x=x;
qu[i].w=w;
qu[i].id=i;
}
sort(qu+1,qu+q+1);
int pos=1;
for (int i=1;i<=q;i++){
while (e[pos].w<=qu[i].w&&pos<=m){
chain(e[pos].u,e[pos].v);
pos++;
}
ans[qu[i].id]=size[getf(qu[i].x)];
}
for (int i=1;i<=q;i++) printf("%d\n",ans[i]);
return 0;
}
```
### string[KMP]
这个题因为不会~~看毛片~~所以不会做。
然后就暴力了50/100分。
其实这题是很裸的一道KMP
求出匹配数=x
```cpp
#include<cstdio>
#include<cstring>
int k,n,ans,next[5010];
char s[5010];
void kmp(int pos){
for (int i=1;i<=n;i++) next[i]=pos-1;
for (int i=pos+1;i<=n;i++){
int j=next[i-1];
while (j!=pos-1&&s[j+1]!=s[i]) j=next[j];
if (s[j+1]==s[i]) j++;
next[i]=j;
}
int j=next[pos];
for (int i=pos+1;i<=n;i++){
while (j!=pos-1&&s[j+1]!=s[i]) j=next[j];
if (s[j+1]==s[i]) j++;
while ((j-pos+1)*2>=i-pos+1) j=next[j];
if (j-pos+1>=k) ans++;
}
}
int main(){
freopen("string.in","r",stdin);
freopen("string.out","w",stdout);
scanf("%s",s+1);
scanf("%d",&k);
n=strlen(s+1);
for (int i=1;i<=n;i++) kmp(i);
printf("%d\n",ans);
return 0;
}
```
ans+=x\*(x+1)/2
所以说呢，我其实基本功还是不过关的。
如果说最优状态的话，我估计可以拿到260分左右。
第二题暴力骗60，其他裸题，不出差错就有260分。
最终只有一百分。我好菜啊。
## 2.kmp真是玄学啊
我今天重新复习了一边kmp，看了一个写的很好的博客
然后就觉得kmp这种算法真的是优化了很多，节约了很多时间
比起暴力o(nm)，kmp只需要o(n+m)
在这里贴个[链接](http://blog.csdn.net/v\_JULY\_v/article/details/7041827)
## 3.还有需要弄的内容
(1) 白书4.1~4.5（一个星期弄完）
(2) kmp复习
(3) 计算几何（扫描线&&凸包）