2018计蒜客初赛2

一天之后，计蒜客第二场，感觉一般般，第一题卡了一下处理的比较慢，导致后面时间略微不足，第二题倒是没什么坑点

A. 淘宝的推荐系统

思路：这题dp的味道还是挺明显的，dp选择当前元素所能达到的最大长度，至于转移，第一次想的是转移之前所有状态中可能的状态，然而O（n^2）的复杂度，加上多组数据，毫无疑问tle

之后想到用d，转移可能的状态，而不是转移先前的状态，用map存储状态，然而，map只是重载了下标运算符，内部红黑树实现O（log（n））的复杂度，结果还是被卡掉了

于是想到各种优化，优化cin，优化运算，优化函数等各种，然而依然杯水车薪

于是想到set预处理已经出现过的状态，实现离散化，二分查找离散化后的状态来优化原来的暴力枚举，结果依然tle

最后猛然发现状态的数据范围仅有5次方，于是果断回到第二种做法，还原map为数组，顺利ac，好吧，醉了

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <cstring>
#include <map>
#include <cmath>
#include <string>
#include <queue>
#include <stack>
#include <set>

using namespace std;

const int N = 200;

const int maxn = 2e5+10;
/*
int p[maxn];

set<int> p;
int dp[maxn];

map <int,int> dp;


int myabs(int k)
{
    if(k<0)
    {
        k *= (-1);
    }
    return k;
}

int main()
{
    int t;
    //ios::sync_with_stdio(false);
    scanf("%d",&t);
    while(t--)
    {
        p.clear();
        int n,d;
        //cin >> n >> d ;
        scanf("%d%d",&n,&d);
        int maxl = 1;
        for(int i=0;i<n;i++)
        {
            //cin >> p[i];
            int pp;
            scanf("%d",&pp);
            dp[pp] = 1;
            set<int> :: iterator it = p.lower_bound(pp-d);
            for(;it!=p.end()&&(*it)<=pp+d;it++)
            {
                //if(myabs(p[i] - p[j])<=d)
                //if(((p[i] - p[j]) <= d )&& ((p[i] - p[j]) >= ((-1)*d)))
                //{
                //cout << (*it) << "&&" << dp[(*it)] << endl;
                    if(dp[(*it)]+1>dp[i])
                    {
                        dp[pp] = dp[(*it)]+1;
                    }
                //}
            }
            p.insert(pp);
            if(dp[pp] > maxl)
            {
                maxl = dp[pp];
            }
        }
        //cout << maxl << endl;
        printf("%d\n",maxl);
    }
}*/



//map<int,int> dp;

int dp[maxn];

int main()
{
    int t;
    //ios::sync_with_stdio(false);
    scanf("%d",&t);
    //cout << dp[0];
    while(t--)
    {
        //dp.clear();
        memset(dp,0,sizeof(dp));
        int n,d;
        //cin >> n >> d ;
        scanf("%d%d",&n,&d);
        int maxl = 1;
        for(int i=0;i<n;i++)
        {
            int p;
            //cin >> p[i];
            scanf("%d",&p);
            //dp[i] = 1;
            int now = 1;
            for(int j=p-d;j<=p+d;j++)
            {
                 //cout << j << "#" <<dp[j]<< endl;
                //if(myabs(p[i] - p[j])<=d)
                int temp = dp[j+N] + 1;
                if(temp > now)
                {
                    now = temp;
                    //cout << j << "#" <<dp[j]<< endl;
                }
            }
            dp[p+N] = now;
            //cout << dp[p] << "*" << endl;
            if(now > maxl)
            {
                maxl =  now;
            }
        }
        //cout << maxl << endl;
        printf("%d\n",maxl);
    }
}

//O(n^2)
//O(2*n*d*log(n))
//优化
//O（n*(log(n)+d)*log(n))
//O(2*n*d)

B. 阿里巴巴的手机代理商（简单）

思路：这题就是个字符串大模拟，map存取键值，后缀都采用substr截断判断，毕竟处于简单位置，比较友好

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <cstring>
#include <map>
#include <cmath>
#include <string>
#include <queue>
#include <stack>

using namespace std;

const int maxn = 1e5+10;

map<string,int> col;

int main()
{
    int t;
    ios::sync_with_stdio(false);
    cin >> t;
    while(t--)
    {
        col.clear();
        int n;
        cin >> n;
        while(n--)
        {
            string temp;
            cin >> temp;
            if(temp=="insert")
            {
                string cha;
                int num;
                cin >> cha >> num;
                col[cha] += num;
            }
            else if(temp=="delete")
            {
                 string cha;
                 cin >> cha;
                 if(col[cha] == 0)
                 {
                     cout << "Empty\n";
                 }
                 else
                 {
                     col[cha] = 0;
                 }
            }
            else if(temp=="query")
            {
                 string cha;
                 cin >> cha;
                 int len = cha.size();
                 map<string,int> :: iterator it;
                 int re = 0;
                 for(it = col.begin();it!=col.end();it++)
                 {
                     string ch = it->first;
                     int nnum = it->second;
                     int nlen = ch.size();
                     if(nlen<len)
                     {
                         continue;
                     }
                     ch = ch.substr(nlen-len,len);
                     if(ch == cha)
                     {
                         re += nnum;
                     }
                 }
                 cout << re << "\n";
            }
        }
    }
    return 0;
}