22/7/26-杭电多校3

1003，1009，1012，1011；

---

1，1003；

签到题，用stringstream；注意在输入T后吃回车；

void solve()
{
    string line;
    getline(cin,line);
    stringstream ssin(line);
    string s;
    while(ssin>>s)
    {
        s[0]=toupper(s[0]);
        cout<0];
    }
    cout<
    
}
signed main()
{
    quick_cin();
    int T;
    cin>>T;
    cin.get();
    while(T--)solve();
    return 0;
}

2，1009 Package Delivery；

过程想复杂了，一直T；

枚举右端点，然后用小根堆来存储入库的快递；

贪心思想是到截止日期的快递一定得拿走，如果够k的倍数，那么直接拿k的倍数次，否则看能否从仓库里在拿没到截止日期的来凑足k的倍数，能凑足就拿满就走，不能 也把仓库里的清空（本着多拿一定对后面有利的原则）；

#pragma GCC optimize(2)
#include
#define rep1(i,a,n) for( int i=(a);i<(n);++i) 
#define rep2(i,a,n) for(register int i=(a);i<=(n);++i) 
#define per1(i,n,a) for( int i=(n);i>(a);i--) 
#define per2(i,n,a) for( int i=(n);i>=(a);i--)
#define quick_cin() cin.tie(0),cout.tie(0),ios::sync_with_stdio(false)
#define memset(a,i,b) memset((a),(i),sizeof (b))
#define memcpy(a,i,b) memcpy((a),(i),sizeof (b))
#define pro_q priority_queue
#define eb emplace_back
#define endl "\n"
#define lowbit(m) ((-m)&(m))
#define dbug(y) cout<<(y)<<"\n"
#define dbug2(a,b) cout<" "<"\n"
#define dbug3(a,b,c) cout<" "<" "<"\n"
#define dbug4(a,b,c,d) cout<" "<" "<" "<"\n"
#define yi first
#define er second
#define INF 0x3f3f3f3f
#define tulun int e[N],ne[N],h[N],w[N],idx;
#define add2(a,b) e[idx]=b,ne[idx]=h[a],h[a]=idx++;
#define add3(a,b,c) w[idx]=c,e[idx]=b,ne[idx]=h[a],h[a]=idx++;
#define T_solve() int T;cin>>T;while(T--)solve();
#define pi 3.14159265358979323846
using namespace std;
typedef long long LL;
typedef pair<int,int> PII;
typedef pair<long long,long long> PLL;
typedef double dob;
const int N=2e5+10,M=1e6+10;
int n,k;
vectorduand;
vector<int>R;
pro_q<int,vector<int>,greater<int>>q;
void solve()
{
    cin>>n>>k;
    rep2(i,1,n)
    {
        int l,r;
        cin>>l>>r;
        duand.eb(make_pair(l,r));
        R.eb(r);
    }
    sort(duand.begin(),duand.end());
    sort(R.begin(),R.end());
    int i=0,ans=0;
    for(auto it:R)
    {
        int cnt=0;
        while(ipush(duand[i++].second);
        while(q.size()&&q.top()==it)cnt++,q.pop();
        int gs=cnt%k;
        if(!gs)
        {
            ans+=cnt/k;
            continue;
        }
        else
        {
            ans+=cnt/k+1;
            int num=k-gs;
            while(q.size()&&num--)q.pop();
        }
    }
    dbug(ans);
    duand.clear();
    R.clear();
    q.empty();
}
signed main()
{
    quick_cin();
    T_solve();
    return 0;
}

3，1012，Two Permutations；

题意：给定长度为n的排列a和b，以及长度为2n的排列c，问每次从a或b的左端取一个元素加到c的右边（c初始为空），最终拼成c的方案数；

记忆化搜索dp；

转移方程：

    if(P[x]==S[x+y-1]&&x<=n)

        ans=(ans+dfs(x+1,y,0))%mod;

    if(Q[y]==S[x+y-1]&&y<=n)

        ans=(ans+dfs(x,y+1,1))%mod;

注意起点情况；

#pragma GCC optimize(2)
#include
#define rep1(i,a,n) for( int i=(a);i<(n);++i) 
#define rep2(i,a,n) for( int i=(a);i<=(n);++i) 
#define per1(i,n,a) for( int i=(n);i>(a);i--) 
#define per2(i,n,a) for( int i=(n);i>=(a);i--)
#define quick_cin() cin.tie(0),cout.tie(0),ios::sync_with_stdio(false)
#define memset(a,i,b) memset((a),(i),sizeof (b))
#define memcpy(a,i,b) memcpy((a),(i),sizeof (b))
#define pro_q priority_queue
#define eb emplace_back
#define endl "\n"
#define lowbit(m) ((-m)&(m))
#define dbug(y) cout<<(y)<<"\n"
#define dbug2(a,b) cout<<(a)<<" "<<(b)<<"\n"
#define dbug3(a,b,c) cout<<(a)<<" "<<(b)<<" "<<(c)<<"\n"
#define dbug4(a,b,c,d) cout<<(a)<<" "<<(b)<<" "<<(c)<<" "<<(d)<<"\n"
#define yi first
#define er second
#define INF 0x3f3f3f3f
#define tulun int e[N],ne[N],h[N],w[N],idx;
#define add2(a,b) e[idx]=b,ne[idx]=h[a],h[a]=idx++;
#define add3(a,b,c) w[idx]=c,e[idx]=b,ne[idx]=h[a],h[a]=idx++;
#define T_solve() int T;cin>>T;while(T--)solve();
#define pi 3.14159265358979323846
using namespace std;
typedef long long LL;
typedef pair<int,int> PII;
typedef pair<long long,long long> PLL;
typedef double dob;
const int N=1e6+10;
const int mod=998244353;
int n;
int P[N],Q[N],S[N];
int f[N][2];
int dfs(int x,int y,int from)
{
    if(x>n&&y>n)return 1;
    if(f[x+y-1][from]!=-1)return f[x+y-1][from];
    int ans=0;
    if(P[x]==S[x+y-1]&&x<=n)
        ans=(ans+dfs(x+1,y,0))%mod;
    if(Q[y]==S[x+y-1]&&y<=n)
        ans=(ans+dfs(x,y+1,1))%mod;
    f[x+y-1][from]=ans;
    return ans;
}
void solve()
{
    cin>>n;
    rep2(i,1,n)cin>>P[i];
    rep2(i,1,n)cin>>Q[i];
    rep2(i,1,n*2)cin>>S[i];
    memset(f,-1,f);
    int ans=0;
    if(P[1]==S[1])ans=(ans+dfs(2,1,0))%mod;
    if(Q[1]==S[1])ans=(ans+dfs(1,2,1))%mod;
    dbug(ans);
}
signed main()
{
    quick_cin();
    T_solve();
    return 0;
}

4，1011，Taxi；

题意：小明有出租车vip卡，可帮他减少出租车费，减少规则是min（距离费用，终点权值）；

终点费用由题目给出，距离费用是起点到终点的曼哈顿距离；

先给出n个城镇以及权值，给出小明位置，输出vip卡可节省的最大费用；

思路：

一个难点是如何快速求出小明位置到其它点的曼哈顿距离；

题解O（1）求距离最大值需要记住；

 由此可见，只需要处理出上面说的四个值，代入小明坐标即可求出；

那如何选城镇使得min（距离，w）最大呢，二分；

先按w权值升序排序城镇，然后维护城镇后缀最大距离；

为啥是后缀：

如果是前缀的话：

选到mid，如果wmid

如果wmid>=d，那么答案贡献是d，往后d会增大，那么答案还是会变大的；还是要在mid+1~n中找，所以这样做并不能缩小查找区间，只能On遍历，而有q<=n个询问，所以会爆炸；

那么如果后缀维护最大距离的话，

选mid，如果wmid

反之在1~mid-1区间找；

#pragma GCC optimize(2)
#include
#define rep1(i,a,n) for( int i=(a);i<(n);++i) 
#define rep2(i,a,n) for( int i=(a);i<=(n);++i) 
#define per1(i,n,a) for( int i=(n);i>(a);i--) 
#define per2(i,n,a) for( int i=(n);i>=(a);i--)
#define quick_cin() cin.tie(0),cout.tie(0),ios::sync_with_stdio(false)
#define memset(a,i,b) memset((a),(i),sizeof (b))
#define memcpy(a,i,b) memcpy((a),(i),sizeof (b))
#define pro_q priority_queue
#define eb emplace_back
#define endl "\n"
#define lowbit(m) ((-m)&(m))
#define dbug(y) cout<<(y)<<"\n"
#define dbug2(a,b) cout<<(a)<<" "<<(b)<<"\n"
#define dbug3(a,b,c) cout<<(a)<<" "<<(b)<<" "<<(c)<<"\n"
#define dbug4(a,b,c,d) cout<<(a)<<" "<<(b)<<" "<<(c)<<" "<<(d)<<"\n"
#define yi first
#define er second
#define tulun int e[N],ne[N],h[N],w[N],idx;
#define add2(a,b) e[idx]=b,ne[idx]=h[a],h[a]=idx++;
#define add3(a,b,c) w[idx]=c,e[idx]=b,ne[idx]=h[a],h[a]=idx++;
#define T_solve() int T;cin>>T;while(T--)solve();
#define pi 3.14159265358979323846
using namespace std;
typedef long long LL;
typedef pair<int,int> PII;
typedef pair<long long,long long> PLL;
typedef double dob;
int n,q;
const int N=1e5+10;
#define int LL
int a[N],b[N],c[N],d[N];
struct node
{
    int x,y,w;
    bool operator < ( const node &b)
    {
        return w
    }
}e[N];
int INF=LONG_LONG_MAX;
int ans;
bool check(int mid,int x,int y)
{
    int w=e[mid].w;
    int maxv=-INF;
    maxv=max(maxv,x+y+a[mid]);
    maxv=max(maxv,x-y+b[mid]);
    maxv=max(maxv,-x+y+c[mid]);
    maxv=max(maxv,-x-y+d[mid]);
    ans=max(ans,min(w,maxv));
    return w<=maxv;
}
void solve()
{
    cin>>n>>q;
    rep2(i,1,n)
    {
        int x,y,w;
        cin>>x>>y>>w;
        e[i]={x,y,w};
    }
    sort(e+1,e+n+1);
    a[n+1]=b[n+1]=c[n+1]=d[n+1]=-INF;
    per2(i,n,1)
    {
        a[i]=max(a[i+1],-e[i].x-e[i].y);
        b[i]=max(b[i+1],-e[i].x+e[i].y);
        c[i]=max(c[i+1],e[i].x-e[i].y);
        d[i]=max(d[i+1],e[i].x+e[i].y);
    }
    while(q--)
    {
        int x,y;
        cin>>x>>y;
        int l=1,r=n;
        ans=-INF;
        while(l
        {
            int mid=l+r+1>>1;
            if(check(mid,x,y))l=mid;
            else r=mid-1;
        }
        check(r,x,y);
        dbug(ans);
    }
}
signed main()
{
    quick_cin();
    T_solve();
    return 0;
}