杭电杯第五场

个人题解，欢迎指正

P1003

思路：

可以直接从$deep[i]$到$deep[j]$,我们考虑将对应的点建边，但是如果一条条边建那么复杂度为$n^2$,我们考虑另外一个点$t$,将$deep[i]$的点建一条到$t$，价值为$p$的边，再建$t$到$deep[j]$，价值为$0$的边，最后跑Dij最短路就可以了

Code：

#include<bits/stdc++.h>
#define ll long long
#define ptn putchar('\n')
using namespace std;

inline ll read() {ll x = 0, z = 1;char c = getchar();while (!isdigit(c)) {if (c == '-')z = -1;c = getchar();}while (isdigit(c)) {x = (x << 1) + (x << 3) + (c ^ 48);c = getchar();}return z * x;}
inline void writ(ll x){if(x<0) {putchar('-');x=(~x)+1;}if(x>9)writ(x/10);putchar(x-x/10*10+48);}
const ll INF=1e18+7;
const int N=1e6+5;
int n;
struct edge
{
    int to,next;ll w;
}e[N<<2];
int head[N<<1];
vector<vector<int>>deep;
bool visi[N<<1];
int ent=0;
int mxde=0;
ll dis[N<<1];
void init(){
    deep=vector<vector<int>>(n+5);
    memset(dis,1,sizeof dis);memset(visi,0,sizeof visi);memset(head,0,sizeof head);
    mxde=ent=0;
}
inline void addedge(int x,int y,ll w){
    e[++ent].to=y;
    e[ent].w=w;
    e[ent].next=head[x];
    head[x]=ent;
}
inline void dfs(int x,int de){
    mxde=max(mxde,de);
    deep[de].push_back(x);
    for(int i=head[x];i;i=e[i].next){
        int y=e[i].to;
        if(!visi[y]){
            visi[y]=1;
            dfs(y,de+1);
        }
    }
}
int k;ll p;
int sta,en;

#define pli pair<ll,int>

void Qingtuan(){
    scanf("%d",&n);init();
    int x,y;ll w;
    for (int i = 1; i < n; i++)
    {
        scanf("%d%d%lld",&x,&y,&w);
        addedge(x,y,w);addedge(y,x,w);
    }
    scanf("%d%d%d%d",&k,&p,&sta,&en);
    visi[1]=1;
    dfs(1,1);
    for (int i = 1; i+k <=n ; i++)
    {
        for(auto j:deep[i]){
            addedge(j,n+i,p);
        }
        for(auto j:deep[i+k]){
            addedge(n+i,j,0);
        }
    }
    
    memset(visi,0,sizeof visi);
    priority_queue<pli,vector<pli>,greater<pli>>pq;
    pq.push({0,sta});
    dis[sta]=0;
    pli hea;
    int h;
    while (!pq.empty())
    {
        hea=pq.top();pq.pop();
        w=hea.first;h=hea.second;
        if(visi[h])continue;
        visi[h]=1;
        for(int i=head[h];i;i=e[i].next){
            y=e[i].to;
            if(dis[y]>w+e[i].w){
                dis[y]=w+e[i].w;
                pq.push({dis[y],y});
            }
        }
    }
    printf("%lld\n",dis[en]);
}



int main(){
    //cin.tie(nullptr)->sync_with_stdio(false);

    int T;scanf("%d",&T);
    while (T--)
    Qingtuan();
    return 0;
}

P1010

一道简单博弈论，由于知道自己和对方的筛子，那么就可以喊出最大的了，特判每个筛子都不同时先手必输的情况

Code：

#include <bits/stdc++.h>
#define ll long long
#define endl '\n'
using namespace std;

const int maxn=2e5+10;
int x[10],y[10];

void solve() {
    memset(x,0,sizeof(x));
    memset(y,0,sizeof(y));
    int n;
    bool flag=0;
    cin>>n;
    if(n>6) flag=1;
    int flag1=0,a,b;
    for(int i=1;i<=n;i++) {
        cin>>a;
        if(i==1) b=a;
        if(b!=a) flag1=1;
        x[a]++;
    }
    if(!flag) {
        bool p=0;
        for(int i=1;i<=6;i++) if(x[i]>1) p=1;
        if(!p) memset(x,0,sizeof(x));
    }
    if(flag1==0) x[a]++;
    for(int i=1;i<=n;i++) {
        cin>>a;
        if(i==1) b=a;
        if(b!=a) flag1=1;
        y[a]++;
    }
    if(flag1==0) y[a]++;
    if(!flag) {
        bool p=0;
        for(int i=1;i<=6;i++) if(y[i]>1) p=1;
        if(!p) memset(y,0,sizeof(y));
    }
    for(int i=1;i<=6;i++) x[i]+=y[i];
    if(x[1]==0&&x[2]==0&&x[2]==0&&x[3]==0&&x[4]==0&&x[5]==0&&x[6]==0) cout<<"Just a game of chance."<<endl;
    else cout<<"Win!"<<endl;
}

int main() {
    std::ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    int T=1;
    cin>>T;
    while(T--) {
        solve();
    }
    return 0;
}

P1012

按照题目给的方式模拟即可，用优先队列维护目前要走的人的时间和位置，用线段树维护位置的人数，单点修改

Code：

#include<bits/stdc++.h>
#define ll long long
#define ptn putchar('\n')
using namespace std;

inline ll read() {ll x = 0, z = 1;char c = getchar();while (!isdigit(c)) {if (c == '-')z = -1;c = getchar();}while (isdigit(c)) {x = (x << 1) + (x << 3) + (c ^ 48);c = getchar();}return z * x;}
inline void writ(ll x){if(x<0) {putchar('-');x=(~x)+1;}if(x>9)writ(x/10);putchar(x-x/10*10+48);}
const int N=2e5+5;
#define pll pair<ll,int>
int n,m;

pair<int,int>tr[N<<2];

inline void push_up(int h){
    if(tr[h<<1].first==tr[h<<1|1].first){
        tr[h]=tr[h<<1];return;
    }
    tr[h]=min(tr[h<<1],tr[h<<1|1]);
}

inline void build(int h,int l,int r){
    if(l==r){
        tr[h]={0,l};return;
    }
    int mid=(l+r)>>1;
    build(h<<1,l,mid);
    build(h<<1|1,mid+1,r);
    push_up(h);
}
pair<int,int> ul;
inline void update(int h,int l,int r){
    if(l==ul.first&&r==ul.first){
        tr[h].first+=ul.second;return;
    }
    int mid=(l+r)>>1;
    if(ul.first<=mid)update(h<<1,l,mid);
    else update(h<<1|1,mid+1,r);
    push_up(h);
}


void Qingtuan(){
    n=read();m=read();
    build(1,1,m);
    vector<pll>a(n+1);vector<ll>b(m+1);
    for (int i = 1; i <= n; i++)
    {
        a[i].first=read();a[i].second=read();
    }
    sort(a.begin()+1,a.end());
    priority_queue<pll,vector<pll>,greater<pll>>pq;
    pair<int,int>trh;
    pll h;
    for (int i = 1; i <= n; i++)
    {
        if(pq.empty()){
            ul={tr[1].second,1};update(1,1,m);b[ul.first]=a[i].first+a[i].second;
            pq.push({a[i].first+a[i].second,ul.first});
        }else{
            while(!pq.empty()){
                h=pq.top();
                if(a[i].first>=h.first){
                    pq.pop();
                    ul={h.second,-1};update(1,1,m);
                }else break;
            }
            ul={tr[1].second,1};update(1,1,m);
            b[ul.first]=max(a[i].first,b[ul.first])+a[i].second;
            pq.push({b[ul.first],ul.first});
        }
    }
    while (!pq.empty())
    {
        h=pq.top();pq.pop();
    }
    writ(h.first);ptn;
}



int main(){
    //cin.tie(nullptr)->sync_with_stdio(false);

    int T=read();while (T--)
    Qingtuan();
    return 0;
}