2020杭电多校联合训练(第二场)
in 杭电多校多校训练 with 0 comment

2020杭电多校联合训练(第二场)

in 杭电多校多校训练 with 0 comment

摘要

/ABCDEFGHIJKL
场上
zyj
wrf
lmj

题目

A.Total Eclipse

lmj+wrf (03:49:36) +3

题意

题解

代码

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;

const int inf=0x3f3f3f3f;
const ll mint=0x7fffffff;
const ll linf=1000000000000000000LL;
const ll mod=998244353LL;
const double eps=1e-3;

const int N=100020;

inline ll read()
{
    ll x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}

struct findunion
{
    vector<int> v;

    findunion(void){}
    findunion(int n)
    {
        v.resize(n);
        for(int i=0;i<n;i++)
        {
            v[i]=i;
        }
    }

    int getfa(int n)
    {
        if(v[n]!=n)
        {
            v[n]=getfa(v[n]);
        }

        return v[n];
    }

    bool ifbro(int l,int r)
    {
        return getfa(l)==getfa(r);
    }

    void unset(int l,int r)
    {
        if(v[l]==l && v[r]==r)
        {
            if(l>r)
            {
                swap(l,r);
            }
            v[r]=l;
        }
        else
        {
            unset(getfa(l),getfa(r));
        }

        return ;
    }
};

int main(void)
{
    
    for(int _=read();_>0;_--)
    {
        int n=read(),m=read();
        vector<vector<int> > g(n+1);
        vector<pair<int,int> > b(n+1);
        vector<int> rb(n+1);
        findunion f(n+1);

        for(int i=1;i<=n;i++) b[i]={read(),i};
        for(int i=0;i<m;i++)
        {
            int l=read(),r=read();
            g[l].push_back(r);
            g[r].push_back(l);
        }
        sort(b.begin()+1,b.end());
        for(int i=1;i<=n;i++) rb[b[i].second]=i;

        int root=0;

        ll ans=0;
        int r=n+1;
        for(int i=n;i>=1;i--)
        {
            for(auto j:g[b[i].second])
            {
                if(b[rb[j]].first>=b[i].first && !f.ifbro(rb[j],i)) 
                {
                    f.unset(rb[j],i);
                    root++;
                }
            }
            if(b[i].first>b[i-1].first) 
            {
                r=i;
                ans+=1ll*(n-i+1-root)*(b[i].first-b[i-1].first);
            }
        }

        printf("%lld\n",ans);
    }
    
    return 0;
}

B.Blood Pressure Game

lmj (赛后)

题意

给定一个序列,将其任意排列,所得到的和为$\sum_{i=1}^{n-1}|b_{i+1}-b_i|$,求前k大的和以及方案数

题解

将b序列排序,考虑将任意排列完的序列的答案表示为排序后相邻2个数的差的倍数和。
考虑dp,dpi[t]代表前i个数,有j个连通块,存在$a_i$或者$a_n$的数量,每加入一个数,他的贡献为$(b_{i+1}-b_i)*(2*j-t)$,考虑当前有j个连通块,每个连通块除了含有$a_i$或者$a_n$的都有2个位置可以填,含有$a_i$或者$a_n$的有一个位置可以填,填上的数必定比$b_i$大,其旁边已经被填的数必定比$b_i$小,那么必定有$b_{i+1}-b_i$的贡献。
考虑转移,可以加一个没有$a_1$或者$a_n$的连通块,往$dp[i+1][j+1][t]$转移,方案数为$j+1-t$.
可以加一个含有$a_1$或者$a_n$的连通块,往$dp[i+1][j+1][t+1]$转移,方案数为$2-t$.
可以合并两个相邻连通块,往$dp[i+1][j-1][t]$转移,方案数为$j-1$.
可以将某个连通块往左往右扩展但不含有$a_1$或者$a_n$,往$dp[i+1][j][t]$转移,方案数为$2*j-t$.
可以将某个连通块往左往右扩展且为$a_1$或者$a_n$,往$dp[i+1][j][t+1]$转移,方案数为$2-t$.
因为要将相同大小的进行合并,一开始考虑了map, 复杂度同样也是$n^2klogk$,然后T飞了。。。只能用数组去写了,注意考虑只留前k大

代码

#include <bits/stdc++.h>
using namespace std;
#define paii pair<int,int>
#define fr first
#define sc second
typedef long long ll;
const int N=2e5+5;
const int p=1e9+7;
ll qpow(ll a,ll n){ll res=1;while(n){if(n&1)res=res*a%p;a=a*a%p;n>>=1;}return res;}
struct node
{
    ll v;
    ll sum;
};
bool cmp(node x,node y)
{
    return x.v>y.v;
}
struct NODE
{
    int tot=0;
    node state[125];
    void add(node tmp)
    {
        state[++tot]=tmp;
    }
    void update()
    {
        if(tot==0)return;
        sort(state+1,state+tot+1,cmp);
        int tot1=0;
        node tmp;
        tmp=state[1];
        for(int i=2;i<=tot;i++){
            if(state[i].v==state[i-1].v){
                tmp.sum=(tmp.sum+state[i].sum)%p;
            }else{
                if(tmp.sum!=0){
                    state[++tot1]=tmp;
                }
                tmp=state[i];
            }
        }
        if(tmp.sum!=0){
            state[++tot1]=tmp;
        }
        tot=tot1;
    }
}dp[2][305][3];
ll b[305];
void work()
{
    int n,k;
    scanf("%d%d",&n,&k);
    for(int i=1;i<=n;i++){
        scanf("%lld",&b[i]);
    }
    for(int i=0;i<=1;i++){
        for(int j=1;j<=(n+1)/2;j++){
            for(int t=0;t<=2;t++){
                dp[i][j][t].tot=0;
            }
        }
    }
    sort(b+1,b+n+1);
    dp[1][1][0].add({0,1});
    dp[1][1][1].add({0,2});
    int op=1;
    for(int i=2;i<=n;i++){
        op^=1;
        for(int j=1;j<=min(i,n-i+1);j++){
            for(int t=0;t<=2;t++){
                dp[op][j][t].tot=0;
            }
        }
        for(int j=1;j<=min(i,n-i+1);j++){
            for(int t=0;t<=2;t++){
                if(i+j-1+(2-t)>n)continue;
                if(j!=1){
                    if(i-1>=t){
                        for(int ii=1;ii<=min(k,dp[op^1][j-1][t].tot);ii++){
                            node tmp=dp[op^1][j-1][t].state[ii];
                            dp[op][j][t].add({tmp.v+(b[i]-b[i-1])*(2*(j-1)-t),tmp.sum*(j-t)%p});
                        }
                    }
                    if(t!=0&&i>=t){
                        for(int ii=1;ii<=min(k,dp[op^1][j-1][t-1].tot);ii++){
                            node tmp=dp[op^1][j-1][t-1].state[ii];
                            dp[op][j][t].add({tmp.v+(b[i]-b[i-1])*(2*(j-1)-(t-1)),tmp.sum*(2-(t-1))%p});
                        }
                    }
                }
                if(i-1>=j+1&&i-1>=t){
                    for(int ii=1;ii<=min(k,dp[op^1][j+1][t].tot);ii++){
                        node tmp=dp[op^1][j+1][t].state[ii];
                        dp[op][j][t].add({tmp.v+(b[i]-b[i-1])*(2*(j+1)-(t)),tmp.sum*(j)%p});
                    }
                }
                if(i-1>=j&&i-1>=t){
                    for(int ii=1;ii<=min(k,dp[op^1][j][t].tot);ii++){
                        node tmp=dp[op^1][j][t].state[ii];
                        dp[op][j][t].add({tmp.v+(b[i]-b[i-1])*(2*(j)-(t)),tmp.sum*(2*j-t)%p});
                    }
                }
                if(t!=0&&i-1>=j&&i>=t){
                    for(int ii=1;ii<=min(k,dp[op^1][j][t-1].tot);ii++){
                        node tmp=dp[op^1][j][t-1].state[ii];
                        dp[op][j][t].add({tmp.v+(b[i]-b[i-1])*(2*(j)-(t-1)),tmp.sum*(2-(t-1))%p});
                    }
                }
                dp[op][j][t].update();
            }
        }
    }
    for(int i=1;i<=min(k,dp[op][1][2].tot);i++){
        printf("%lld %lld\n",dp[op][1][2].state[i].v,dp[op][1][2].state[i].sum);
    }
    for(int i=1;i<=k-dp[op][1][2].tot;i++){
        printf("-1\n");
    }
}
int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int T=1;
    scanf("%d",&T);
    //cin>>T;
    while(T--){
        work();
    }
}

C.Count on a Tree II Striking Back

zyj (赛后) +10086

题意

给出一棵树,可以修改点权和询问,询问给你两条路径问你两条路径经过的点权种数哪个多,强制在线。$(1 \leq n \leq 500000,1 \leq m \leq 10000)$

题解

随机乱搞题,我们把每种颜色随机一个值,然后对于一个询问跑30次,树剖求数链点权最小值,30个最小值加起来比较一下即可。
为什么?因为题目保证了$f(a, b) \geq 2 f(c, d) \text { or } f(c, d) \geq 2 f(a, b)$,所以其实很粗略就可以定性。

代码

都是树剖+线段树板子,放个solve吧

void solve(){
    int las=0;
    scanf("%d%d",&n,&m);tp.init();init();
    rep(i,1,n) scanf("%d",&col[i]);
    rep(i,1,n-1){
        int u,v;scanf("%d%d",&u,&v);
        addedge(u,v);addedge(v,u);
    }tp.dfs1(1,0,1);tp.dfs2(1,1);tp.build(1,1,n);
    while(m--){
        int op;scanf("%d",&op);
        if(op==1){
            int x,y;scanf("%d%d",&x,&y);x^=las;y^=las;
            tp.Interadd(1,x,x,y);
        }else{
            int a,b,c,d;scanf("%d%d%d%d",&a,&b,&c,&d);
            a^=las;b^=las;c^=las;d^=las;
            int A=tp.querysum(a,b),B=tp.querysum(c,d);
            if(A<B) puts("Yes"),las++;
            else puts("No");
        }
    }
}

D.Diamond Rush

题意

题解

代码


E.New Equipments

zyj lmj (赛后) +3

题意

n个开口向上且非负的二次函数,取值范围是[1,m],对于每个$k \in [1,n]$,选出k个互不相同的取值使得所有函数值的和最大,对每个k输出答案。

题解

费用流裸题,n个函数建n个点,令为$F_i$(至多50个),由于指数爆炸,每个函数的可能取值只能是对称轴左右50个位置。把每个函数的所有取值拿出来建点,令为$X_i$(至多2500个),S向每个$X_i$连边(容量1,费用0),每个$X_i$向可以作为取值的函数$F_i$连边(容量1,费用$F(x)$),然后每个$F_i$向$T$连边(容量1,费用0).
每次往$S$增加1点流量,最小费用即是答案。

代码

#include <bits/stdc++.h>
using namespace std;
#define paii pair<int,int>
#define fr first
#define sc second
typedef long long ll;
const ll inf=1e17;
struct ZKW_SPFA{
    #define maxn 16005
    #define maxe 100050
    const ll INF=(ll)1e17;
    ll dis[maxn],vis[maxn],head[maxn],tot;
    ll n,Cost=0,Flow=0;
    struct Edge{ll v,cap,cost,nxt;}g[maxe<<1];
    void init(ll _n){tot=0,Cost=Flow=0;memset(head,-1,sizeof(head));n=_n;}
    void add(ll u,ll v,ll cap,ll cost){
        g[tot]={v,cap,cost,head[u]};head[u]=tot++;
    }
    void addedge(ll u,ll v,ll cap,ll cost){
        add(u,v,cap,cost);add(v,u,0,-cost);
    }
    bool spfa(ll S,ll T){
        for(ll i=0;i<=n;i++) vis[i]=0,dis[i]=INF;
        deque<ll>Q;Q.push_back(T);dis[T]=0;vis[T]=1;
        while(!Q.empty()){
            ll u=Q.front();Q.pop_front();
            for(ll i=head[u],v;~i;i=g[i].nxt)
                if(g[i^1].cap&&dis[v=g[i].v]>dis[u]+g[i^1].cost){
                    dis[v]=dis[u]+g[i^1].cost;
                    if(!vis[v]){
                        vis[v]=1;
                        if(!Q.empty()&&dis[v]<dis[Q.front()]) Q.push_front(v);
                        else Q.push_back(v);
                        //SLF优化
                    }
                } vis[u]=0;
        } return dis[S]<INF;
    }
    ll dfs(ll S,ll T,ll flow){
        if(S==T){vis[T]=1;return flow;}
        ll used=0,res;vis[S]=1;
        for(ll i=head[S],v;~i;i=g[i].nxt)
            if(!vis[v=g[i].v]&&g[i].cap&&dis[S]-g[i].cost==dis[v]){
                res=dfs(v,T,min(g[i].cap,flow-used));
                if(res) Cost+=res*g[i].cost,g[i].cap-=res,g[i^1].cap+=res,used+=res;
                if(used==flow)break;
            }
        return used;
    }
    void solve(ll S,ll T){
        while(spfa(S,T)){
            vis[T]=1;
            while(vis[T]) memset(vis,0,sizeof vis),Flow+=dfs(S,T,INF);
        }
    }
    //先zkw.init(n),再zkw.addedge(),再zkw.solve(S,T)
    //可以输出zkw.Flow和zkw.Cost
}zkw;

ll a[55],b[55],c[55];
set<int>s;
map<int,int>mp;
int main()
{
    int t;
    scanf("%d",&t);
    while(t--){
        s.clear();
        mp.clear();
        int n,m;
        scanf("%d%d",&n,&m);
        for(int i=1;i<=n;i++){
            scanf("%lld%lld%lld",&a[i],&b[i],&c[i]);
        }
        zkw.init(7000);
        for(int i=1;i<=n;i++){
            int x=-b[i]/(2*a[i]);
            for(int j=min(max(1,x-50),max(1,m-50));j<=max(min(50,m),min(m,x+50));j++){
                s.insert(j);
            }
        } 
        int Ss=6100;
        int S=6101;
        int T=6102;
        int cnt=0;
        for(auto x:s){
            mp[x]=++cnt;
            zkw.addedge(Ss,cnt,1,0);
        }
       
        for(int i=1;i<=n;i++){
            int x=-b[i]/(2*a[i]);
            for(int j=min(max(1,x-50),max(1,m-50));j<=max(min(50,m),min(m,x+50));j++){
                zkw.addedge(mp[j],6000+i,1ll,1ll*a[i]*j*j+1ll*b[i]*j+1ll*c[i]);
                
            }
            zkw.addedge(6000+i,T,1,0);
        }
        for(int i=1;i<=n;i++){
            zkw.addedge(S,Ss,1,0);
            zkw.solve(S,T);
            printf("%lld%c",zkw.Cost,i==n?'\n':' ');
        }
    }
}

F.The Oculus

lmj 01:13:37 +0

题意

给出2个数由斐波那契进制构成,然后给出2个数的乘积以斐波那契进制构成,然后答案的某一进制被修改了,0变成1,1变成0,求被改的是哪位

题解

使用自然溢出直接做即可。

代码

#include <bits/stdc++.h>
using namespace std;
#define paii pair<int,int>
#define fr first
#define sc second
typedef long long ll;
typedef unsigned long long ull;
const int N=2e6+5;
const int p=1e9+7;
ll qpow(ll a,ll n){ll res=1;while(n){if(n&1)res=res*a%p;a=a*a%p;n>>=1;}return res;}
ull f[N];
int a[N];
int b[N];
int c[N];
void work()
{
    int na,nb,nc;
    scanf("%d",&na);
    ull suma=0;
    for(int i=1;i<=na;i++){
        scanf("%d",&a[i]);
        if(a[i]){
            suma+=f[i];
        }
    }
    scanf("%d",&nb);
    ull sumb=0;
    for(int i=1;i<=nb;i++){
        scanf("%d",&b[i]);
        if(b[i]){
            sumb+=f[i];
        }
    }
    scanf("%d",&nc);
    ull sumc=0;
    for(int i=1;i<=nc;i++){
        scanf("%d",&c[i]);
        if(c[i]){
            sumc+=f[i];
        }
    }
    ull tmp=suma*sumb-sumc;
    //printf("%llu %llu %llu\n",suma,sumb,sumc);
    for(int i=1;i<=na+nb+1;i++){
        if(f[i]==tmp||f[i]==~tmp){
            printf("%d\n",i);
            return;
        }
    }
}
int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    f[1]=1;
    f[2]=2;
    for(int i=3;i<N;i++){
        f[i]=f[i-1]+f[i-2];
    }
    int T=1;
    scanf("%d",&T);
    //cin>>T;
    while(T--){
        work();
    }
}

G.In Search of Gold

lmj (赛后)

题意

给一个n个节点的树,每条边有两种边权$a_i,b_i$,其中有k条选了a,另外的选了b,求最小的树直径。

题解

考虑二分答案,然后判断是否直径小于等于这个值,判断使用树形dp,dpi代表j的子树中有i个选了a,到j这个点时所产生的最长链,转移时需要注意得子树中的和不超过直径才能转移。挺卡常的(在dfs时一个个初始化比整体初始化慢了好多)

代码

#include <bits/stdc++.h>
using namespace std;
#define paii pair<int,int>
#define fr first
#define sc second
typedef long long ll;
const ll inf=1e18;
const int N=2e4+5;
const int p=1e9+7;
ll qpow(ll a,ll n){ll res=1;while(n){if(n&1)res=res*a%p;a=a*a%p;n>>=1;}return res;}
ll dp[25][N];
struct Edge{
    int v,a,b,nxt;
}g[N<<1];
int head[N],edge_tot;
int siz[N];
int n,k;
void init(){for(int i=0;i<=n;i++) head[i]=0;edge_tot=1;}
void addedge(int u,int v,int a,int b){g[edge_tot]={v,a,b,head[u]};head[u]=edge_tot++;}
void dfs(int past,int now,ll limit)
{ 
    ll tmp[25];
    for(int i=0;i<=k;i++){
        // dp[i][now]=inf;
        tmp[i]=inf;
    }
    siz[now]=1;
    dp[0][now]=0;
    for(int i=head[now];i;i=g[i].nxt){
        int u=g[i].v;
        if(u==past)continue;
        dfs(now,u,limit);
        for(int j=0;j<=min(k,siz[now]+siz[u]);j++)tmp[j]=inf;
        for(int j=0;j<=min(k,siz[u]);j++){
            for(int t=0;t<=min(k,siz[now]);t++){
                if(t+j<=min(k,siz[now]+siz[u])&&dp[j][u]+dp[t][now]+g[i].b<=limit){
                    tmp[t+j]=min(tmp[t+j],max(dp[t][now],dp[j][u]+g[i].b));
                }
                if(t+j+1<=min(k,siz[now]+siz[u])&&dp[j][u]+dp[t][now]+g[i].a<=limit){
                    tmp[t+j+1]=min(tmp[t+j+1],max(dp[t][now],dp[j][u]+g[i].a));
                }
            }
        }
        siz[now]+=siz[u];
        for(int j=0;j<=min(k,siz[now]);j++){
            dp[j][now]=tmp[j];
        }
    }
}
void work()
{
    scanf("%d%d",&n,&k);
    //printf("%d %d\n",n,k);
    init();
    ll r=0;
    for(int i=1;i<n;i++){
        int x,y,a,b;
        scanf("%d%d%d%d",&x,&y,&a,&b);
        addedge(x,y,a,b);
        addedge(y,x,a,b);
        r+=max(a,b);
    }
    ll l=1;
    while(l<=r){
        ll m=(l+r)>>1;
        for(int i=1;i<=n;i++){
            for(int j=0;j<=k;j++){
                dp[j][i]=inf;
            }
        }
        dfs(-1,1,m);
        if(dp[k][1]>=inf){
            l=m+1;
        }else{
            r=m-1;
        }
    }
    printf("%lld\n",l);
    
}
int main()
{
    //freopen("1.in","r",stdin);
    //ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int T=1;
    scanf("%d",&T);
    //cin>>T;
    while(T--){
        work();
    }
}

H.Dynamic Convex Hull

lmj (赛后)

题意

给n个函数,每个函数$f_i(x)=(x-a_i)^4+b_i$。
m次操作,1 a b代表加入一个函数,2 t代表删除第t个函数,3 x求$f_i(x)$的最小值

题解

考虑将操作离线,将所有的操作都离线对应到以时间为下标的线段树的区间,对于每一种函数,可以求出其什么时候进入,什么时候删除(没被删除就当最后删除),然后就可以插入到线段树的log个点内,然后对于第3种操作,其会受到从该子节点到根的log个点上的函数影响,插入这些位置,计算答案。
对于每一个节点,如果暴力去求,可以发现是$n^2$的,考虑进行一定的优化,可以将所有函数分为俩种$a_i<=x$和$a_i>=x$,可以发现当$a_i<=x$时,若$a_i<a_j$,$(x-a_i)^4+b_i$>=$(x-a_j)^4+b_j$是随着x的增大一直成立的,满足四边形不等式,可以使用决策单调性进行优化,考虑分治做法。
如何决策单调性,首先函数(l,r,dl,dr),代表l-r这段的答案,只受到dl-dr的函数影响,再以(l+r)>>1的这个询问进行分割,通过暴力查找最后一个能使得其更优的函数,继续分割。

代码

#include <bits/stdc++.h>
using namespace std;
#define paii pair<int,int>
#define fr first
#define sc second
typedef long long ll;
const ll inf=8e18;
const int N=2e5+5;
const int p=1e9+7;
ll qpow(ll a,ll n){ll res=1;while(n){if(n&1)res=res*a%p;a=a*a%p;n>>=1;}return res;}
ll ans[N];
int vis[N];
struct node
{
    int l,r,a;
    ll b;
}a[N],b[N];
node q1[N];
node q2[N];
vector<node>v[N<<2];
vector<node>v2[N<<2];
void build(int l,int r,int rt)
{
    v[rt].clear();
    v2[rt].clear();
    if(l==r){
        return;
    }
    int m=(l+r)>>1;
    build(l,m,rt<<1);
    build(m+1,r,rt<<1|1);
}
void update(int l,int r,int rt,int L,int R,node tmp)
{
    if(L<=l&&R>=r){
        v[rt].push_back(tmp);
        return;
    }
    int m=(l+r)>>1;
    if(L<=m)update(l,m,rt<<1,L,R,tmp);
    if(R>m) {
        update(m+1,r,rt<<1|1,L,R,tmp);
    }
}
void update(int l,int r,int rt,int x,node tmp)
{
    v2[rt].push_back(tmp);
    if(l==r)return;
    int m=(l+r)>>1;
    if(x<=m)update(l,m,rt<<1,x,tmp);
    else {
        update(m+1,r,rt<<1|1,x,tmp);
    }
}
bool cmp(node x,node y)
{
    return x.a<y.a;
}
ll cal(ll x){
    return x*x*x*x;
}
void solve1(int l,int r,int L,int R)
{
    int m=(l+r)>>1,M=L,x=q2[m].a;
    ll tmp=inf;
    for(int i=L;i<=R&&x>=q1[i].a;i++){
        ll now=cal(x-q1[i].a)+q1[i].b;
        if(tmp>now)tmp=now,M=i;
    }
    if(tmp<ans[q2[m].l])ans[q2[m].l]=tmp;
    if(l<m)solve1(l,m-1,L,M);
    if(r>m)solve1(m+1,r,M,R);
}
void solve2(int l,int r,int L,int R)
{
    int m=(l+r)>>1,M=R,x=q2[m].a;
    ll tmp=inf;
    for(int i=R;i>=L&&x<=q1[i].a;i--){
        ll now=cal(x-q1[i].a)+q1[i].b;
        if(tmp>now)tmp=now,M=i;
    }
    if(tmp<ans[q2[m].l])ans[q2[m].l]=tmp;
    if(l<m)solve2(l,m-1,L,M);
    if(r>m)solve2(m+1,r,M,R);
}
void work(int rt)
{
    int tot1=0;
    int tot2=0;
    //printf("%d %d\n",v[rt].size(),v2[rt].size());
    for(int i=0;i<v[rt].size();i++)q1[++tot1]=v[rt][i];
    for(int i=0;i<v2[rt].size();i++)q2[++tot2]=v2[rt][i];
    if(tot1==0||tot2==0)return;
    for(int i=1;i<=tot2;i++){
        if(q2[i].a>q1[1].a){
            solve1(i,tot2,1,tot1);break;
        }
    }
    for(int i=tot2;i>=1;i--){
        if(q2[i].a<q1[tot1].a){
            solve2(1,i,1,tot1);break;
        }
    }
}
void dfs(int l,int r,int rt)
{
    //printf("%d %d %d %d\n",l,r,v[rt].size(),v2[rt].size());
    work(rt);
    if(l==r){
        if(vis[l]){
            if(ans[l]>=inf){
                printf("-1\n");
            }else{
                printf("%lld\n",ans[l]);
            }
        }
        return;
    }
    int m=(l+r)>>1;
    dfs(l,m,rt<<1);
    dfs(m+1,r,rt<<1|1);
}
void work()
{
    int n,m;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++){
        scanf("%d%lld",&a[i].a,&a[i].b);
        a[i].l=1;
        a[i].r=m;
    }
    int tot=0;
    build(1,m,1);
    for(int i=1;i<=m;i++){
        vis[i]=0;
        int op;
        scanf("%d",&op);
        if(op==1){
            n++;
            scanf("%d%lld",&a[n].a,&a[n].b);
            a[n].l=i;
            a[n].r=m;
        }
        if(op==2){
            int t;
            scanf("%d",&t);
            a[t].r=i;
        }
        if(op==3){
            int x;
            scanf("%d",&b[++tot].a);
            b[tot].l=i;
            vis[i]=1;
            ans[i]=inf;
        }
    }
    sort(a+1,a+n+1,cmp);
    sort(b+1,b+tot+1,cmp);
    for(int i=1;i<=n;i++)update(1,m,1,a[i].l,a[i].r,a[i]);
    for(int i=1;i<=tot;i++)update(1,m,1,b[i].l,b[i]);
    dfs(1,m,1);
}
int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int T=1;
    scanf("%d",&T);
    //cin>>T;
    while(T--){
        work();
    }
}

I.It's All Squares

lmj (赛后)

题意

给一个$n*m$的矩阵,矩阵中每个方框中都有一个值,$w_{ij}$代表(i-0.5,j-0.5)的位置的值,q次询问,每次询问站在一个点上,然后给出一系列由LRDU组成的字符串代表走的路径,求路径围成的多边形内含有的不同数的数量。

题解

对于每次询问,求一个矩阵将该多边形框起来,然后枚举,采用射线法来判断该点是否在多边形内,在走的路径UD的时候,在其右边进行^1的操作,然后每次横着射过去一条线,每次都异或一下当前记下来的值,判断该点是否在多边形内,将其计入答案。

代码

    #include <bits/stdc++.h>
using namespace std;
#define paii pair<int,int>
#define fr first
#define sc second
typedef long long ll;
const int N=2e5+5;
const int p=1e9+7;
ll qpow(ll a,ll n){ll res=1;while(n){if(n&1)res=res*a%p;a=a*a%p;n>>=1;}return res;}
int a[405][405];
int b[405][405];
int sum[160010];
char c[160005];
void work()
{
    int n,m,q;
    scanf("%d%d%d",&n,&m,&q);
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            scanf("%d",&a[i][j]);
        }
    }
    while(q--){
        int x,y;
        scanf("%d%d",&x,&y);
        scanf("%s",c);
        int l=strlen(c);
        int xx=x,yy=y;
        int maxx=xx,maxy=yy,minx=xx,miny=yy;
        for(int i=0;i<l;i++){
            if(c[i]=='U'){
                yy++;
                b[xx+1][yy]^=1;
            }
            if(c[i]=='D'){
                yy--;
                b[xx+1][yy+1]^=1;
            }
            if(c[i]=='L'){
                xx--;
            }
            if(c[i]=='R'){
                xx++;
            }
            maxx=max(maxx,xx);
            minx=min(minx,xx);
            maxy=max(maxy,yy);
            miny=min(miny,yy);
        }
        int cnt=0;
        for(int i=miny;i<=maxy;i++){
            int now=0;
            for(int j=minx;j<=maxx;j++){
                now^=b[j][i];
                if(!now)continue;
                if(sum[a[j][i]]==0){
                    cnt++;
                }
                sum[a[j][i]]=1;
            }
        }
        printf("%d\n",cnt);
        for(int i=minx;i<=maxx+1;i++){
            for(int j=miny;j<=maxy;j++){
                sum[a[i][j]]=0;
                b[i][j]=0;
            }
        }
    }
}
int main()
{
    // freopen("1.in","r",stdin);
    // freopen("1.out","w",stdout);
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int T=1;
    scanf("%d",&T);
    //cin>>T;
    while(T--){
        work();
    }
}

J.Lead of Wisdom

lmj 2:43:47 +4

题意

给n个四元数分别属于k组,要求每组取1个,使得$(100+\sum{a_i})*(100+\sum{b_i})*(100+\sum{c_i})*(100+\sum(d_i))$最大

题解

一开始暴搜T了,采用了meet in middle,将n个数分为2组,尽量两边平均,然后求出每组的所有情况,然后和另外一组合并。

代码

#include <bits/stdc++.h>
using namespace std;
#define paii pair<int,int>
#define fr first
#define sc second
typedef long long ll;
const int N=2e5+5;
const int p=1e9+7;
ll qpow(ll a,ll n){ll res=1;while(n){if(n&1)res=res*a%p;a=a*a%p;n>>=1;}return res;}
struct node
{
    int a,b,c,d;
};
vector<node>v[105];
int vis[105][105];
int n,k;
node q1[N];
node q2[N];
int tot1=0;
int tot2=0;
void dfs(int l,int r,ll A,ll B,ll C,ll D)
{
    if(l>r){
        node tmp;
        tmp.a=A;
        tmp.b=B;
        tmp.c=C;
        tmp.d=D;
        q1[++tot1]=tmp;
        return;
    }
    if(v[l].size()==0){
        dfs(l+1,r,A,B,C,D);
    }
    for(int i=0;i<v[l].size();i++){
        if(!vis[l][i])
            dfs(l+1,r,A+v[l][i].a,B+v[l][i].b,C+v[l][i].c,D+v[l][i].d);
    }
}
void dfs1(int l,int r,ll A,ll B,ll C,ll D)
{
    if(l>r){
        node tmp;
        tmp.a=A;
        tmp.b=B;
        tmp.c=C;
        tmp.d=D;
        q2[++tot2]=tmp;
        return;
    }
    if(v[l].size()==0){
        dfs1(l+1,r,A,B,C,D);
    }
    for(int i=0;i<v[l].size();i++){
        if(!vis[l][i])
            dfs1(l+1,r,A+v[l][i].a,B+v[l][i].b,C+v[l][i].c,D+v[l][i].d);
    }
}
bool cmp(node x,node y)
{
    if(x.a!=y.a)return x.a>y.a;
    else if(x.b!=y.b)return x.b>y.b;
    else if(x.c!=y.c)return x.c>y.c;
    else return x.d>y.d;
}
void work()
{
    scanf("%d%d",&n,&k);
    memset(vis,0,sizeof(vis));
    for(int i=1;i<=k;i++){
        v[i].clear();
    }
    for(int i=1;i<=n;i++){
        int op;
        scanf("%d",&op);
        node tmp;
        scanf("%d%d%d%d",&tmp.a,&tmp.b,&tmp.c,&tmp.d);
        v[op].push_back(tmp);
    }
    for(int i=1;i<=k;i++){
        sort(v[i].begin(),v[i].end(),cmp);
        for(int j=0;j<v[i].size();j++){
            for(int t=j+1;t<v[i].size();t++){
                if(v[i][j].a>=v[i][t].a&&v[i][j].b>=v[i][t].b&&v[i][j].c>=v[i][t].c&&v[i][j].d>=v[i][t].d){
                    vis[i][t]=1;
                }
            }
        }
    }
    tot1=0;
    tot2=0;
    q1[++tot1]={0,0,0,0};
    q2[++tot2]={0,0,0,0};
    int sum=0;
    int f=k+1;
    for(int i=1;i<=k;i++){
        if(sum>=k/2){
            f=i;break;
        }
        sum+=v[i].size();
    }
    dfs(1,f-1,0,0,0,0);
    dfs1(f,k,0,0,0,0);
    ll ans=0;
    for(int i=1;i<=tot1;i++){
        for(int j=1;j<=tot2;j++){
            ans=max(ans,1ll*(100+q1[i].a+q2[j].a)*(100+q1[i].b+q2[j].b)*(100+q1[i].c+q2[j].c)*(100+q1[i].d+q2[j].d));
        }
    }
    printf("%lld\n",ans);
}
int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int T=1;
    scanf("%d",&T);
    //cin>>T;
    while(T--){
        work();
    }
}

K.King of Hot Pot

题意

题解

代码


L.String Distance

wrf (03:47:34) +0

题意

题解

代码

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;

const int inf=0x3f3f3f3f;
const ll mint=0x7fffffff;
const ll linf=1000000000000000000LL;
const ll mod=998244353LL;
const double eps=1e-3;

const int N=100020;

inline ll read()
{
    ll x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}

char s[N],t[25];
int a[N][26];
int ta[26];
int dp[24][24];

int main(void)
{
    for(int _=read();_>0;_--)
    {
        memset(a,0,sizeof(a));

        scanf("%s",s+1);
        scanf("%s",t);

        int n=strlen(s+1),m=strlen(t);
        for(int i=0;i<26;i++) ta[i]=n+1;
        for(int i=n;i>=0;i--)
        {
            for(int j=0;j<26;j++) a[i][j]=ta[j];
            ta[s[i]-'a']=i;
        }

        for(int __=read();__>0;__--)
        {
            int l=read(),r=read();
            for(int i=0;i<24;i++)
            {
                for(int j=0;j<24;j++)
                {
                    dp[i][j]=inf;
                }
            }
            for(int i=0;i<m;i++) dp[i][0]=l-1;
            for(int i=0;i<m;i++)
            {
                for(int j=1;j<=i+1;j++)
                {
                    if(i==0) dp[i][j]=a[l-1][t[i]-'a'];
                    else 
                    {
                        dp[i][j]=min(dp[i-1][j],dp[i][j]);
                        if(dp[i-1][j-1]<=r)
                        {
                            dp[i][j]=min(dp[i][j],a[dp[i-1][j-1]][t[i]-'a']);
                        }
                    }
                }
            }

            int ans;
            for(ans=m;ans>=0;ans--)
            {
                if(dp[m-1][ans]<=r) break;
            }

            printf("%lld\n",(r-l+1+m)-2*ans);
        }
    }
    
    return 0;
}
Responses