HDU多校4

赛中5题（都是队友过的

1004

题意：给一个边长为n的大正三角形，由许多边长为1的小正三角形组成。在所有小三角形的每个顶点中填写0,1或2，满足大三角形的左侧不应出现0。大三角形的右侧不应出现1。大三角形的底侧不应出现2。对于每个小三角形，三个顶点的总和不应是3的倍数。询问是否可以填写出这样的大三角形。

（想了半天硬是没推出一个Yes的，一看榜单过了好多人，猜一手结论不存在这样的大三角形）
思路：输出No即可。具体证明过程见官方题解。

1006

题意：DLee按顺序买了n张票，如果之前花费的总票价≥100，之后的票打8折；如果之前花费的总票价≥200，之后的票打5折。但是DLee妄想中可以将一张票拆成多次购买。求Dlee妄想中的花费以及实际花费。

思路：大模拟，按要求模拟即可。（丢给队友了）

1007

题意：有一座n层的高楼，每层都有一个怪物，第i层的怪物有生命值ai。DLee从第0层开始，要求打败所有的怪物。每次他可以选择往上跳1~k层或往下走1层。一开始DLee有一个初始攻击力a0，只有当自己的攻击力≥怪物的生命值，他才能击败怪物，击败怪物后可以吸收怪物的生命值加到自己的攻击力上。他不能去怪物生命值严格大于其攻击力的楼层，也不能去已经拜访过的楼层。判断DLee是否能击败所有的怪物。

（一读题面我就想到了刷视频经常刷到的那个小广告…）
思路：因为要击败所有怪物，所以一旦自己往上跳后，一定得先把跳过的这一段楼层一一往下打掉后，才能接着往上跳。贪心地想，自己每一步跳的距离一定要尽可能地小。遍历自己下一步能否跳到第i层，假设当前在pos层，则只有当自己跳到第i层并能将[pos+1,i]层的怪物都打掉，才能从pos层跳到i层。前缀和处理优化即可（我还带了个询问区间最大值）。

#include<bits/stdc++.h>
#define ll long long
#define L(i,j,k) for(ll i=(j);i<=(k);i++)
#define R(i,j,k) for(ll i=(j);i>=(k);i--)
#define inf 0x3f3f3f3f3f3f3f3f
#define fi first
#define se second
#define pb push_back
#define mkp make_pair
#define MS(i,j) memset(i,j,sizeof (i))
const ll N=1e6+10,M=10,mod=998244353,mmod=mod-1;
const double pi=acos(-1);
using namespace std;
ll fmul(ll a,ll b){a%=mod;b%=mod;ll res=0;while(b){if(b&1){res+=a;res%=mod;}a<<=1;if(a>=mod)a%=mod;b>>=1;}return res;}
ll gcd(ll x,ll y){if(y==0) return x;return gcd(y,x%y);}
ll fksm(ll a,ll b){ll r=1;if(b<0)b+=mod-1;for(a%=mod;b;b>>=1){if(b&1)r=r*a%mod;a=a*a%mod;}return r;}//a 分母; b MOD-2
ll lowbit(ll x){return x&(-x);}
const ll two=fksm(2,mod-2);

ll m,n,t,x,y,z,l,r,k,p,pp,nx,ny,ansx,ansy,lim,num,sum,pos,tot,root,block,key,cnt,mn,mx,ans;
ll a[N],b[N],c[N],dx[5]={0,1,0,-1},dy[5]={1,0,-1,0};
double dans;
bool vis[N],flag;
char s[N],mapp,zz[5];
struct qq{ll x,y,z;}q;
struct node{ll l,r,mx;}trs[N*4];
struct tree{ll fa,dep,dfn,siz,son,top,w;};
struct edge{ll to,nxt;}eg;

bool cmp(qq u,qq v){
    return u.x>v.x;
}
bool cmp1(qq u,qq v){
    return u.x<v.x;
}
bool cmpl(ll u,ll v){return u>v;}
struct cmps{bool operator()(ll u,ll v){
    return u>v;
}};//shun序

pair<ll,ll>pr;
vector<ll>v,vans;//v.assign(m,vector<ll>(n));
//priority_queue<ll,vector<ll>,cmps>sp;
queue<ll>sq;
stack<ll>st;
map<ll,ll>mp;
multiset<ll>se;
set<ll>::iterator it;
bitset<M>bi;

void push_up(ll k){
    trs[k].mx=max(trs[k*2].mx,trs[k*2+1].mx);
}

void bd_tree(ll k,ll l,ll r){
    trs[k].l=l,trs[k].r=r;
    if(l==r){
        trs[k].mx=c[l];
        return;
    }
    ll mid=(l+r)/2;
    bd_tree(k*2,l,mid);
    bd_tree(k*2+1,mid+1,r);
    push_up(k);
}

ll query(ll k,ll pl,ll pr){
    ll ml=-inf,mr=-inf;
    if(trs[k].l>=pl&&trs[k].r<=pr){
        return trs[k].mx;
    }
    ll mid=(trs[k].l+trs[k].r)/2;
    if(mid>=pl)ml=query(k*2,pl,pr);
    if(mid+1<=pr)mr=query(k*2+1,pl,pr);
    return max(ml,mr);
}

void solve(){
    scanf("%lld%lld%lld",&n,&a[0],&m);
    L(i,1,n)scanf("%lld",&a[i]);
    b[0]=a[0];
    L(i,1,n)b[i]=b[i-1]+a[i];
    L(i,1,n)c[i]=a[i]-(b[n]-b[i]);
    bd_tree(1,1,n);
    pos=0;
    L(i,1,n){
        if(i-pos>m)break;
        if(query(1,pos+1,i)+b[n]-b[i]<=b[pos])pos=i;
    }
    if(pos==n)printf("YES\n");
    else printf("NO\n");
}

int main(){
    // ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    // cout<<fixed<<setprecision(12);//精度
    ll T=1;
    scanf("%lld",&T);
    while(T--)solve();
}

1011

题意：给定一个长度为n的数组a。可以执行任意次以下操作：选择一段区间[l,r]，将区间内每个ai推平成${\oplus }_{i=l}^r{a}_i\backslash oplus\_\{i=l\}^r\; a\_i$（$\oplus \backslash oplus$表示按位异或）。最终将a数组的所有元素变为同一值，求这个的最大值。（保证a数组存在至少一对相同的数字）

思路：问题可以等价于求最大子序列异或和，属于线性基模板题，证明过程见官方题解。

#include<bits/stdc++.h>
#define ll long long
#define L(i,j,k) for(ll i=(j);i<=(k);i++)
#define R(i,j,k) for(ll i=(j);i>=(k);i--)
#define inf 0x3f3f3f3f3f3f3f3f
#define fi first
#define se second
#define pb push_back
#define mkp make_pair
#define MS(i,j) memset(i,j,sizeof (i))
const ll N=1e6+10,M=10,mod=998244353,mmod=mod-1;
const double pi=acos(-1);
using namespace std;
ll fmul(ll a,ll b){a%=mod;b%=mod;ll res=0;while(b){if(b&1){res+=a;res%=mod;}a<<=1;if(a>=mod)a%=mod;b>>=1;}return res;}
ll gcd(ll x,ll y){if(y==0) return x;return gcd(y,x%y);}
ll fksm(ll a,ll b){ll r=1;if(b<0)b+=mod-1;for(a%=mod;b;b>>=1){if(b&1)r=r*a%mod;a=a*a%mod;}return r;}//a 分母; b MOD-2
ll lowbit(ll x){return x&(-x);}
const ll two=fksm(2,mod-2);

ll m,n,t,x,y,z,l,r,k,p,pp,nx,ny,ansx,ansy,lim,num,sum,pos,tot,root,block,key,cnt,mn,mx,ans;
ll a[N],b[N],dx[5]={0,1,0,-1},dy[5]={1,0,-1,0};
double dans;
bool vis[N],flag;
char s[N],mapp,zz[5];
struct qq{ll x,y,z;}q;
struct node{ll l,r,tag,sum;}trs;
struct tree{ll fa,dep,dfn,siz,son,top,w;};
struct edge{ll to,nxt;}eg;

bool cmp(qq u,qq v){
    return u.x>v.x;
}
bool cmp1(qq u,qq v){
    return u.x<v.x;
}
bool cmpl(ll u,ll v){return u>v;}
struct cmps{bool operator()(ll u,ll v){
    return u>v;
}};//shun序

pair<ll,ll>pr;
vector<ll>v,vans;//v.assign(m,vector<ll>(n));
//priority_queue<ll,vector<ll>,cmps>sp;
queue<ll>sq;
stack<ll>st;
map<ll,ll>mp;
multiset<ll>se;
set<ll>::iterator it;
bitset<M>bi;

void solve(){
    scanf("%lld",&n);
    L(i,1,n)scanf("%lld",&a[i]);
    L(i,0,62)b[i]=0;
    L(i,1,n)R(j,61,0){
        if((a[i]>>j)&1){
            if(b[j])a[i]^=b[j];
            else{
                b[j]=a[i];
                R(k,j-1,0)if(b[k]&&((b[j]>>k)&1))b[j]^=b[k];
                L(k,j+1,61)if((b[k]>>j)&1)b[k]^=b[j];
                break;
            }
        }
    }
    ans=0;
    L(i,0,61)ans^=b[i];
    printf("%lld\n",ans);
}

int main(){
    // ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    // cout<<fixed<<setprecision(12);//精度
    ll T=1;
    scanf("%lld",&T);
    while(T--)solve();
}

1001

题意：给定一个长度为n的括号序列，其中有一些位置上的元素丢失了。已知总共有m种括号，求有多少种填充方式使括号序列合法。

思路：区间dp。直接甩给队友写了。

1002

题意：给定n个点m条有向边的图，保证1到n的连通性。每条边都有两个权值ei和pi，Link从点1跑到点n，经过第i条路将获得ei的能量和pi的健康值。要求在能量最少的前提下，健康值最大。

思路：最短路求出能量的最小值，然后在最短路图上跑最长路求出健康值的最大值。因为存在环和0边，需要用tarjan缩点，属于是图论大杂烩了。（debug了好久T-T）

#include<bits/stdc++.h>
#define ll long long
#define L(i,j,k) for(ll i=(j);i<=(k);i++)
#define R(i,j,k) for(ll i=(j);i>=(k);i--)
#define inf 0x3f3f3f3f3f3f3f3f
#define fi first
#define se second
#define pb push_back
#define mkp make_pair
#define MS(i,j) memset(i,j,sizeof (i))
const ll N=1e6+10,M=10,mod=998244353,mmod=mod-1;
const double pi=acos(-1);
using namespace std;
ll fmul(ll a,ll b){a%=mod;b%=mod;ll res=0;while(b){if(b&1){res+=a;res%=mod;}a<<=1;if(a>=mod)a%=mod;b>>=1;}return res;}
ll gcd(ll x,ll y){if(y==0) return x;return gcd(y,x%y);}
ll fksm(ll a,ll b){ll r=1;if(b<0)b+=mod-1;for(a%=mod;b;b>>=1){if(b&1)r=r*a%mod;a=a*a%mod;}return r;}//a 分母; b MOD-2
ll lowbit(ll x){return x&(-x);}
ll dx[5]={0,1,0,-1},dy[5]={1,0,-1,0};

ll m,n,t,x,y,z,l,r,u,v,k,p,pp,nx,ny,nz,ansx,ansy,num,sum,mn,mx,ans;
ll lim,pos,tot,cnt,root,key,block;
ll b[N],c[N],head[N],he[N];
double dans;
bool vis[N],flag;
char s[N],mapp,zz[5];
struct qq{ll x,w;}q;
struct node{ll l,r,tag,sum;};
struct tree{ll fa,dep,dfn,siz,son,top,w;};
struct edge{ll to,nxt,w0,w1;}eg[N],eg1[N];

bool cmp(qq u,qq v){
    return u.x>v.x;
}
bool cmp1(qq u,qq v){
    return u.x<v.x;
}
bool cmpl(ll u,ll v){return u>v;}
struct cmps{bool operator()(qq u,qq v){
    return u.w>v.w;
}};//shun序

pair<ll,ll>pa[N];
vector<ll>sv,vans;//v.assign(m,vector<ll>(n));
priority_queue<qq,vector<qq>,cmps>sp;
queue<ll>sq;
stack<ll>st;
map<ll,ll>mp;
set<ll>se;
set<ll>::iterator it;
bitset<M>bi;

void _eg(ll u,ll v,ll w0,ll w1){
	eg[++cnt].to=v;
    eg[cnt].w0=w0;
    eg[cnt].w1=w1;
	eg[cnt].nxt=head[u];
	head[u]=cnt;
}

void _eg1(ll u,ll v,ll w0,ll w1){
    eg1[++tot].to=v;
    eg1[tot].w0=w0;
    eg1[tot].w1=w1;
    eg1[tot].nxt=he[u];
    he[u]=tot;
}

ll dis[N];
void dij(ll s){
    L(i,1,n)dis[i]=inf;
    dis[s]=0;
    sp.push({s,0});
    while(!sp.empty()){
        qq tmp=sp.top();sp.pop();
        ll x=tmp.x,w=tmp.w;
        if(dis[x]<w)continue;
        for(ll k=head[x];k;k=eg[k].nxt){
            ll y=eg[k].to,dw=w+eg[k].w0;
            if(dis[y]>dw){
                dis[y]=dw;
                sp.push({y,dw});
            }
        }
    }
}

ll scccnt,dfncnt;
ll dfn[N],low[N],scc[N];
void tarjan(ll x){
    ll y;
    dfn[x]=low[x]=++dfncnt;
    vis[x]=1;
    st.push(x);
    for(ll k=head[x];k;k=eg[k].nxt){
        y=eg[k].to;
        if(dis[y]==dis[x]+eg[k].w0){
            if(!dfn[y]){
                tarjan(y);
                low[x]=min(low[x],low[y]);
            }
            else if(vis[y]){
                low[x]=min(low[x],low[y]);
            }
        }
    }
    if(low[x]==dfn[x]){
        ++scccnt;
        do{
            y=st.top();st.pop();
            scc[y]=scccnt;
            vis[y]=0;
        }while(x!=y);
    }
}

void bd_dag(ll n){
    scccnt=dfncnt=tot=0;
    L(i,1,n)he[i]=dfn[i]=0;
    while(!st.empty())st.pop();
    L(i,1,n){
        if(!dfn[i])tarjan(i);
    }//L(i,1,n)printf("%lld ",scc[i]);printf("\n");
    L(x,1,n){
        for(ll k=head[x];k;k=eg[k].nxt){
            ll y=eg[k].to;
            if(dis[y]==dis[x]+eg[k].w0){
                if(scc[x]==scc[y]);
                else{
                    c[scc[y]]++;
                    _eg1(scc[x],scc[y],eg[k].w0,eg[k].w1);
                }
            }
        }
    }
}

void init(){
    cnt=tot=0;
    L(i,1,n){
        head[i]=0;
        b[i]=c[i]=0;
    }
}

void solve(){
    scanf("%lld%lld",&n,&m);
    init();
    L(i,1,m){
        scanf("%lld%lld%lld%lld",&x,&y,&l,&r);
        _eg(x,y,l,r);
    }
    dij(1);
    bd_dag(n);

    ll s=scc[1],t=scc[n];
    b[s]=0;
    sq.push(s);
    while(!sq.empty()){
        ll x=sq.front();sq.pop();
        for(ll k=he[x];k;k=eg1[k].nxt){
            ll y=eg1[k].to;
            b[y]=max(b[y],b[x]+eg1[k].w1);
            c[y]--;
            if(c[y]==0)sq.push(y);
        }
    }
    printf("%lld %lld\n",dis[n],b[t]);
}

int main(){
    // ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    // cout<<fixed<<setprecision(12);//精度
    ll T=1;
    scanf("%lld",&T);
    while(T--)solve();
}