Taxi

题目大意:给定我们n个点的坐标,m次询问,每次询问给出一个点的坐标,让我们求一下这个点到n个点中的那个点的
代价最小,一个点到某个点的代价定义为,这两个点之间曼哈顿距离和所到点的权值的最小值

$如果此题只是让我们求一个点到n个点中曼哈顿距离的最大值我们怎么办呢?$
$设当前点的坐标为(x,y),n个点的坐标为(x_i,y_i)$
$ max(|x-x_i|+|y-y_i|)$
$=max(x-x_i,x_i-x) + max(y-y_i,y_i-y)$
$=max((x+y)+(-x_i-y_i),((x-y)+(-x_i+y_i)),((y-x)+(x_i-y_i)),(-x-y)+(x_i+y_i))(两两组合)$
$我们将max分成了几个部分,这几部分是相互独立的$
$可见只要我们维护一下这四部分的最大值即可$
$如此就可以O(1)时间内查询每个点到n个点的曼哈顿距离的最大值了$

但是本题还有一个w进行约束,对于求最小值的考虑二分,将w按从小到大进行排序
预处理出a[i],b[i],c[i],d[i]分别表示从i~n的每个最值(排完序后的顺序)
对w的值进行二分,对于(mid,r)这一段区间,如果max(mid,r)小于w,那么说明答案一定在左侧
若大于等于w,那么答案一定在右侧,可见答案具有二分性,可以这样不断缩小距离直到找到最大的答案

#include<iostream>
#include<cstring>
#include<algorithm>
#include<vector>
#include<queue>
#include<map>
#include<set>

using namespace std;

const int N = 1e5 + 10,INF = 0x3f3f3f3f;
typedef long long LL;
//#define int long long
typedef pair<int,int>PII;
//#define x first
//#define y second
int a[N],b[N],c[N],d[N];

struct Node
{
    int x,y,w;
    bool operator<(const Node&T)const
    {
        return w < T.w;
    }
}node[N];

int ans,x,y;

bool check(int mid)//检查当前的max曼哈顿距离是否超过了当前的mid位置的w
{
    int t = -INF;//存储mid点对应的曼哈顿距离的最大值
    t = max(t, abs(x + y + a[mid]));
    t = max(t, abs(x - y + b[mid]));
    t = max(t, abs(- x + y + c[mid]));
    t = max(t, abs(- x - y + d[mid]));

    ans = max(ans, min(node[mid].w, t));

    return node[mid].w <= t;
}

void solve()
{
    int n,m;cin >> n >> m;
    for(int i = 0; i < n; i ++)
    {
        int x,y,z;cin >> x >> y >> z;
        node[i] = {x,y,z};
    }

    sort(node, node + n);//按照w进行排序

    a[n] = b[n] = c[n] = d[n] = -INF;
    //求出排序后的那四个最大值
    for(int i = n - 1; i >= 0; i --)
    {
        a[i] = max(a[i + 1], -node[i].x - node[i].y);
        b[i] = max(b[i + 1], -node[i].x + node[i].y);
        c[i] = max(c[i + 1], node[i].x - node[i].y);
        d[i] = max(d[i + 1], node[i].x + node[i].y);
    }

    while(m --)
    {
        cin >> x >> y;
        ans = -INF;
        int l = 0,r = n - 1;
        //找到最右边的w,对于w而言肯定是具有二分性的,我们的四个数组随着mid的左移也是单调递增的,即曼哈顿距离非严格单增
        //所以说对于一个最优解而言,越往左肯定是越不满足条件的,越向右越是满足条件的
        //即两个条件单调性要保持一致才能二分得到最优解
        while(l < r)
        {
            int mid = l + r + 1 >> 1;
            if(check(mid))l = mid;
            else r = mid - 1;
        }

        check(r);//为了防止答案没有被更新
        cout << ans << endl;
    }
}

int main()
{
    ios::sync_with_stdio(0), cin.tie(0);
    int t;cin >> t;
    while(t --)
    {
        solve();
    }
    return 0;
}

Boss Rush

题意:我们有n个灼烧型技能,每个技能只能放一次,每个的释放时间为t[i],持续伤害时间为len[i]
每秒的伤害为d[i][j],j从0到len[i]。boss的血量为m,问最少要多少时间才能杀死它。

求最小值,考虑二分答案,由于技能的释放顺序不同会导致相同的时间伤害不同,并且不同时间释放顺序也不同
所以我们要找到mid时间内最优的释放顺序,考虑记忆化搜索最优状态,同时我们还要记录一个技能的前缀和数组
来表示到当前时间所造成的伤害

#include<iostream>
#include<cstring>
#include<algorithm>
#include<vector> 
#include<queue>
#include<map>
#include<set>

using namespace std;

const int N = 20,M = 2e5 + 10;
typedef long long LL;
#define int long long
typedef pair<int,int>PII;
#define x first
#define y second
int len[N],t[N],s[N][M],f[(1 << 18) + 10];
int n,m,mid;
//对于记忆化搜索的使用场合:对于某一个状态是确定的,不能是变化的
int dfs(int state)
{
    if(f[state] != -1)return f[state];

    int times = 0;//统计释放节能所花费的时间
    for(int i = 0; i < n; i ++)
    {
        if(state >> i & 1)times += t[i + 1];
    }

    if(times > mid)return f[state] = 0;

    int ans = 0;//找到最大的技能伤害
    //枚举技能的释放
    for(int i = 0; i < n; i ++)
        if(!(state >> i & 1))ans = max(ans, s[i + 1][min(mid - times,len[i + 1])] + dfs(state | (1 << i)));

    return f[state] = ans;
}

bool check()
{
    memset(f,-1,sizeof f);
    //搜索能造成的最大伤害
    return dfs(0) >= m;
}

void solve()
{
    cin >> n >> m;
    int l = 1,r = 0;
    for(int i = 1; i <= n; i ++)
    {
        cin >> t[i] >> len[i];
        r += max(len[i],t[i]);
        for(int j = 1; j <= len[i]; j ++)cin >> s[i][j],s[i][j] += s[i][j - 1];
    }

    int INF = r;
    while(l < r)
    {
        mid = l + r >> 1;
        if(check())r = mid;
        else l = mid + 1;
    }

    if(l == 0 || l == INF)cout << -1 << endl;
    else cout << l - 1 << endl;
}

signed main()
{
    ios::sync_with_stdio(0), cin.tie(0);
    int t;cin >> t;
    while(t --)
    {
        solve();
    }
    return 0;
}

Cyber Language

题意:输出每个拼音的首个字母的大写
直接模拟即可

#include<iostream>
#include<cstring>
#include<algorithm>
#include<sstream>
#include<vector>
#include<queue>
#include<map>
#include<set>

using namespace std;

//const int N = ;
typedef long long LL;
//#define int long long
typedef pair<int,int>PII;
#define x first
#define y second

void solve()
{
    string line;
    getline(cin,line);
    stringstream ssin(line);
    string s;
    while(ssin >> s)cout << (char)(s[0] - ('a' - 'A'));

    cout << endl;
}

signed main()
{
    ios::sync_with_stdio(0), cin.tie(0);
    int t;cin >> t;
    string ss;getline(cin,ss);
    while(t --)
    {
        solve();
    }
    return 0;
}

Two Permutations

题意:给定三个数组a,b,c.每次从a或b最左侧拿一个数对c进行匹配,看总共有多少种匹配的方案
记忆化搜索,用两个指针分别指向a,b数组对c进行匹配

#include<iostream>
#include<cstring>
#include<algorithm>
#include<vector>
#include<queue>
#include<map>
#include<set>

using namespace std;

const int N = 2e6 + 10,mod = 998244353;
typedef long long LL;
#define int long long
typedef pair<int,int>PII;
//#define x first
//#define y second
int a[N],b[N],c[2 * N],f[N][2];//f第一维表示匹配到哪了,第二维表示是从哪个数组转移过来的
int n;

//x是第一个数组中匹配到的位置,y是第二个数组中匹配到的位置,from是从谁转移过来的
//from的作用是为了区别a,b数组
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 res = 0;
    //x是a中正要匹配的位置,y是b中正要匹配的位置,x+y-1是c中正要匹配的位置
    if(a[x] == c[x + y - 1] && x <= n)res = (res + dfs(x + 1,y,0)) % mod;
    if(b[y] == c[x + y - 1] && y <= n)res = (res + dfs(x,y + 1,1)) % mod;

    f[x + y - 1][from] = res;
    return res % mod;
}

void solve()
{
    cin >> n;
    for(int i = 1; i <= n; i ++)cin >> a[i];
    for(int i = 1; i <= n; i ++)cin >> b[i];
    for(int i = 1; i <= 2 * n; i ++)cin >> c[i];

    memset(f,-1,sizeof f);
    cout << dfs(1,1,0) << endl;
}

signed main()
{
    ios::sync_with_stdio(0), cin.tie(0);
    int t;cin >> t;
    while(t --)
    {
        solve();
    }
    return 0;
}

Package Delivery

题意:有n件快递,每次我们最多拿k件,问至少去多少次能拿完所有快递

核心思路:我们一次能拿k件货物,但是不应该一开始就拿,应该往后拖,等货物多了我们再一起拿
但是不能无限制的拖,当一件货物到达deadline的时候,这时我们是不得不拿了,贪心拿,每次都尽量
拿k件货物,首先将所有等于deadline的货物一起拿了,如果不是k的倍数,我们应该选取前面到货的
一些物品(虽然没有到deadline)
用一个小根堆当作我们的仓库,存储每一个截止日期前面的最小的deadline,我们用他们进行充数

#include<iostream>
#include<cstring>
#include<algorithm>
#include<vector>
#include<queue>
#include<map>
#include<set>

using namespace std;

const int N = 2e6 + 10;
typedef long long LL;
#define int long long
typedef pair<int,int>PII;
#define x first
#define y second
PII segs[N];
int ed[N];

void solve()
{
    int n,k;cin >> n >> k;
    for(int i = 0; i < n; i ++)
    {
        int a,b;cin >> a >> b;
        segs[i] = {a,b};
        ed[i] = b;
    }

    sort(segs,segs + n);
    sort(ed,ed + n);

    priority_queue<int,vector<int>,greater<int>>q;
    int l = 0,ans = 0;
    for(int i = 0; i < n; i ++)//从小到大枚举ed,将这个ed之前到货的货物的右端点也加到里面
    {
        int cnt = 0;
        while(l < n && segs[l].x <= ed[i])q.push(segs[l ++].y);
        //查看仓库内有多少件货物的截至时间等于ed
        while(!q.empty() && q.top() == ed[i])cnt ++,q.pop();

        ans += cnt / k;
        if(cnt % k == 0)continue;//如果正好是k的倍数,那么就不用拿前面的凑了
        cnt = k - cnt % k;//如果每凑够k个,尽可能凑满
        while(!q.empty() && cnt)q.pop(),cnt --;
        ans ++;
    }

    cout << ans << endl;
}

signed main()
{
    ios::sync_with_stdio(0), cin.tie(0);
    int t;cin >> t;
    while(t --)
    {
        solve();
    }
    return 0;
}