这次Rank202我就很不爽了，凭什么有个罚时也是210的就排在200了
主要还是T2太ZZ了，前几次都忘了输Emply。之前还因为map的变量名叫做hash被判错了？
后面两题我都不会，这种玄学字符串的题目我是真的烦
说实话我还是比较喜欢图论题
A. 淘宝的推荐系统
咋一看题目很烦，一般的O(n^2)的DP式子肯定都可以推出来，但优化......
全机房开始YY数据结构，单调队列，线段树，主席树......感觉都比较科学，但有个dalao叫trie这就是什么鬼？
好吧其实他是先看T2的
这里其实仔细看一下数据范围就水得一匹，d<=100,p[i]<=1e5
然后我们就换一种思路DP，设f[i]表示最后一件选择的价格为i的商品最多能卖出多少件，则有转移
f[i]=max(f[i],f[j]+1)(max(1,i-d)<=j<=min(MAX_p[i],i+d))
10min1A（如果先看到数据范围的话就可以5min了）
CODE
#include<cstdio>
#include<cstring>
using namespace std;
const int N=30005,MAX=1e5+5;
int f[MAX+100],t,n,d,x,ans;
inline char tc(void)
{
static char fl[100000],*A=fl,*B=fl;
return A==B&&(B=(A=fl)+fread(fl,1,100000,stdin),A==B)?EOF:*A++;
}
inline void read(int &x)
{
x=0; char ch=tc();
while (ch<'0'||ch>'9') ch=tc();
while (ch>='0'&&ch<='9') x=x*10+ch-'0',ch=tc();
}
inline void write(int x)
{
if (x/10) write(x/10);
putchar(x%10+'0');
}
inline int min(int a,int b)
{
return a<b?a:b;
}
inline int max(int a,int b)
{
return a>b?a:b;
}
int main()
{
//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
register int i,j; read(t);
while (t--)
{
memset(f,0,sizeof(f));
read(n); read(d); ans=0;
for (i=1;i<=n;++i)
{
read(x); f[x]+=1;
for (j=x-1;j>=max(1,x-d);--j) f[x]=max(f[x],f[j]+1);
for (j=x+1;j<=x+d;++j) f[x]=max(f[x],f[j]+1);
ans=max(ans,f[x]);
}
write(ans); putchar('
');
}
return 0;
}
B. 阿里巴巴的手机代理商（简单）
这种题目无力吐槽。
尽管他们都选择把trie改成从后向前的来一口气AT2，T3，但我吸取了昨天的教训，迅速开map刚T2
然后就如前文说的出现了SB错误，最后90min的时候才过，还交了6次
然后浪费了一次绝佳上200的机会
缅怀CJJT2炸裂
记住一个教训：map的变量名不能叫hash！（雾）I don't know why
CODE
#include<iostream>
#include<map>
#include<string>
#include<cstring>
using namespace std;
typedef long long LL;
const LL N=1005;
string p,s[N];
map <string,LL> h;
map <string,bool> vis;
LL n,t,x,opt[N],a[N],tot;
inline LL work(string p)
{
vis.clear();
register LL i; LL len=p.size(),sum=0;
for (i=1;i<=n;++i)
if (opt[i]==1&&s[i].size()>=len&&!vis[s[i]])
{
LL p1=s[i].size()-1,p2=len-1; bool flag=1;
while (p2>=0)
{
if (s[i][p1]!=p[p2]) { flag=0; break; }
--p1; --p2;
}
if (flag) sum+=a[h[s[i]]],vis[s[i]]=1;
}
return sum;
}
int main()
{
ios::sync_with_stdio(false);
register LL i; cin>>t;
while (t--)
{
h.clear(); memset(a,0,sizeof(a)); cin>>n; tot=0;
for (i=1;i<=n;++i)
{
cin>>p;
if (p[0]=='i')
{
opt[i]=1; cin>>s[i]>>x;
if (!h[s[i]]) h[s[i]]=++tot;
a[h[s[i]]]+=x;
}
if (p[0]=='q') opt[i]=2,cin>>s[i],cout<<work(s[i])<<endl;
if (p[0]=='d')
{
opt[i]=3; cin>>s[i];
if (!a[h[s[i]]]) cout<<"Empty"<<endl; else a[h[s[i]]]=0;
}
}
}
return 0;
}
后面的两题我就不会了，自行Baidu吧