多校 杭电

摘要

题目

A.Auto-correction

题意

题解

代码

B.Breaking Down News

lmj 赛后

题意

给定一个序列，分为连续的若干组，要求每组的长度为$(L,R)$之间，如果每组的和为正数，那么贡献为1，如果为负数贡献为-1，如果为0，贡献为0，求最大贡献和。

题解

可以发现，选在哪里分割，对答案的贡献差只有1，那么考虑去维护最大和次大（次大的要求为dp值比最大的小），然后用线段树转移即可。

代码

#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=1e6+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;}
paii ans[N<<2];
int dp[N];
int a[N];
int pre[N];
void pushup(int rt)
{
    paii l=ans[rt<<1];
    paii r=ans[rt<<1|1];
    if(dp[l.fr]>dp[r.fr]||dp[l.fr]==dp[r.fr]&&pre[l.fr]<pre[r.fr]){
        ans[rt].fr=l.fr;
        if(dp[r.fr]<dp[l.fr]){
            if(l.sc==-1||dp[l.sc]<dp[r.fr]||dp[l.sc]==dp[r.fr]&&pre[l.sc]>pre[r.fr]){
                ans[rt].sc=r.fr;
            }else{
                ans[rt].sc=l.sc;
            }
        }else{
            if(r.sc==-1){
                ans[rt].sc=l.sc;
            }
            else if(l.sc==-1||dp[l.sc]<dp[r.sc]||dp[l.sc]==dp[r.sc]&&pre[l.sc]>pre[r.sc]){
                ans[rt].sc=r.sc;
            }else{
                ans[rt].sc=l.sc;
            }
        }
    }else{
        ans[rt].fr=r.fr;
        if(dp[l.fr]<dp[r.fr]){
            if(r.sc==-1||dp[r.sc]<dp[l.fr]||dp[r.sc]==dp[l.fr]&&pre[r.sc]>pre[l.fr]){
                ans[rt].sc=l.fr;
            }else{
                ans[rt].sc=r.sc;
            }
        }else{
            if(l.sc==-1){
                ans[rt].sc=r.sc;
            }
            else if(r.sc==-1||dp[r.sc]<dp[l.sc]||dp[r.sc]==dp[l.sc]&&pre[r.sc]>pre[l.sc]){
                ans[rt].sc=l.sc;
            }else{
                ans[rt].sc=r.sc;
            }
        }
    }
}
void build(int l,int r,int rt)
{
    if(l==r){
        ans[rt]={l,-1};
        return;
    }
    int m=(l+r)>>1;
    build(l,m,rt<<1);
    build(m+1,r,rt<<1|1);
    pushup(rt);
}
void update(int l,int r,int rt,int x)
{
    if(l==r)return;
    int m=(l+r)>>1;
    if(x<=m)update(l,m,rt<<1,x);
    else update(m+1,r,rt<<1|1,x);
    pushup(rt);
}
paii query(int l,int r,int rt,int L,int R)
{
    if(R<L)return {-1,-1};
    if(L<=l&&R>=r){
        return ans[rt];
    }
    int m=(l+r)>>1;
    if(R<=m)return query(l,m,rt<<1,L,R);
    else if(L>m)return query(m+1,r,rt<<1|1,L,R);
    else {
        paii tmp;
        paii tmp1=query(l,m,rt<<1,L,R);
        paii tmp2=query(m+1,r,rt<<1|1,L,R);
        if(dp[tmp1.fr]>dp[tmp2.fr]||dp[tmp1.fr]==dp[tmp2.fr]&&pre[tmp1.fr]<pre[tmp2.fr]){
            tmp.fr=tmp1.fr;
            if(dp[tmp2.fr]<dp[tmp1.fr]){
                if(tmp1.sc==-1||dp[tmp1.sc]<dp[tmp2.fr]||dp[tmp1.sc]==dp[tmp2.fr]&&pre[tmp1.sc]>pre[tmp2.fr]){
                    tmp.sc=tmp2.fr;
                }else{
                    tmp.sc=tmp1.sc;
                }
            }else{
                if(tmp2.sc==-1){
                    tmp.sc=tmp1.sc;
                }
                else if(tmp1.sc==-1||dp[tmp1.sc]<dp[tmp2.sc]||dp[tmp1.sc]==dp[tmp2.sc]&&pre[tmp1.sc]>pre[tmp2.sc]){
                    tmp.sc=tmp2.sc;
                }else{
                    tmp.sc=tmp1.sc;
                }
            }
        }else{
            tmp.fr=tmp2.fr;
            if(dp[tmp1.fr]<dp[tmp2.fr]){
                if(tmp2.sc==-1||dp[tmp2.sc]<dp[tmp1.fr]||dp[tmp2.sc]==dp[tmp1.fr]&&pre[tmp2.sc]>pre[tmp1.fr]){
                    tmp.sc=tmp1.fr;
                }else{
                    tmp.sc=tmp2.sc;
                }
            }else{
                if(tmp1.sc==-1){
                    tmp.sc=tmp2.sc;
                }
                else if(tmp2.sc==-1||dp[tmp2.sc]<dp[tmp1.sc]||dp[tmp2.sc]==dp[tmp1.sc]&&pre[tmp2.sc]>pre[tmp1.sc]){
                    tmp.sc=tmp1.sc;
                }else{
                    tmp.sc=tmp2.sc;
                }
            }
        }
        return tmp;
    }
}
int cal(int x)
{
    if(x>0)return 1;
    if(x==0)return 0;
    if(x<0)return -1;
    return 0;
}
void work()
{
    int n,L,R;
    scanf("%d%d%d",&n,&L,&R);
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
    }
    for(int i=1;i<=n;i++){
        pre[i]=pre[i-1]+a[i];
    }
    for(int i=1;i<=n;i++){
        dp[i]=-1e7;
    }
    build(0,n,1);
    for(int i=1;i<=n;i++){
        paii tmp=query(0,n,1,max(0,i-R),i-L);
        //printf("%d %d %d\n",i,tmp.fr,tmp.sc);
        if(tmp.fr!=-1){
            dp[i]=max(dp[i],dp[tmp.fr]+cal(pre[i]-pre[tmp.fr]));
        }
        if(tmp.sc!=-1){
            dp[i]=max(dp[i],dp[tmp.sc]+cal(pre[i]-pre[tmp.sc]));
        }
        //printf("%d\n",dp[i]);
        update(0,n,1,i);
    }
    printf("%d\n",dp[n]);
}
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();
    }
}

C.Clockwise or Counterclockwise

zyj (00:11:24) +0

题意

给定圆上三点$A,B,C$的坐标，询问这个圆是顺时针还是逆时针。

题解

叉积判断正负即可。

代码

void solve(){
    Point A,B,C;
    A.input();B.input();C.input();
    Line AB=Line(A,B),AC=Line(A,C);
    ll x=AB*C;
    if(x>0) puts("Counterclockwise");
    else puts("Clockwise");
}

D.Discovery of Cycles

zyj (03:11:24) +2

题意

给一张无向图，询问连续区间内的边是否能构成环，强制在线。$(n,m,q \leq 3e5)$。

题解

首先这个强制在线是个假的强制在线，因为$lastans$只有$0$和$1$，因此可以理解为给了$2*q$个询问，然后离线做。离线之后就可以用可撤销并查集加线段树分治来解决。

真的要强制在线的话也不难，首先维护一个数组$R[i]$表示以$i$为起点，最早能构成环的右端点。
那么对于每个询问就查询$R[l]$是否大于等于$l$。
至于如何维护$R[i]$，用双指针和$LCT$来维护连通性即可。

代码

E.Easy NPC Problem

题意

题解

代码

F.Fluctuation Limit

题意

给定若干区间，求一个序列，每个数分别在对应的区间中，该序列差分的绝对值不超过 k。

题解

做法

每个区间都会对前后区间造成约束，用这个约束反复更新区间即可。

时间复杂度

$O(n)$

代码

#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;
}

void solve()
{
    int n=read();
    ll k=read();
    vector<ll> l(n),r(n);

    for(int i=0;i<n;i++) l[i]=read(),r[i]=read();

    while(true)
    {
        bool f=false;
        for(int i=0;i<n-1;i++)
        {
            ll tl=max(l[i+1],l[i]-k),tr=min(r[i+1],r[i]+k);
            
            if(tl!=l[i+1] || tr!=r[i+1]) f=true;
            l[i+1]=tl,r[i+1]=tr;
        }
        for(int i=n-1;i>0;i--)
        {
            ll tl=max(l[i-1],l[i]-k),tr=min(r[i-1],r[i]+k);
            
            if(tl!=l[i-1] || tr!=r[i-1]) f=true;
            l[i-1]=tl,r[i-1]=tr;
        }

        if(!f) break;
    }

    for(int i=0;i<n;i++) 
    {
        if(l[i]>r[i])
        {
            printf("NO\n");
            return ;
        }
    }

    printf("YES\n");
    ll pl=l[0],pr=l[0];
    for(int i=0;i<n-1;i++)
    {
        printf("%lld ",pl);
        pl=max(pl-k,l[i+1]),pr=min(pr+k,r[i+1]);
        if(pl<=pr) pr=pl;
    }
    printf("%lld\n",pl);
}

int main(void)
{
    //ios::sync_with_stdio(false);
    
    //freopen("1.in","r",stdin);
    //freopen("1.out","w",stdout);
    
    for(int _=read();_>0;_--)
    {
        solve();
    }
    
    return 0;
}

G.Gaming of Co-prime Disallowance

题意

题解

代码

H.Hexagon

lmj 1:46:49 +2

题意

给定半径为x的正六边形图，求一种遍历方案使得每个正六边形只被遍历一次，并且路线旋转次数最多。

题解

两层两层做即可

代码

#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;}
void work()
{
    int n;
    scanf("%d",&n);
    while((n-2)>0){
        n-=2;
        for(int i=1;i<=n;i++){
            printf("35");
        }
        printf("4");
        for(int i=1;i<=n;i++){
            printf("24");
        }
        printf("3");
        for(int i=1;i<=n;i++){
            printf("13");
        }
        printf("2");
        for(int i=1;i<=n;i++){
            printf("62");
        }
        printf("1");
        for(int i=1;i<=n;i++){
            printf("51");
        }
        printf("6");
        if(n&1){
            printf("5");
        }else{
            printf("4");
        }
        for(int i=n-1;i>=1;i--){
            if(i&1){
                printf("65");
            }else{
                printf("35");
            }
        }
        printf("34");
    }
    if(n==2){
        printf("353216");
    }
    printf("\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();
    }
}

I.Isomorphic Strings

题意

题解

代码

J.Jumping on a Cactus

题意

题解

代码

K.Kidnapper's Matching Problem

lmj 赛后

题意

给定$2$个数组和一个线性基，定义两段序列匹配的条件是相对应的位置的值异或后能被线性基表示。求$\sum_{i=1}^{n-m+1}[(a_i,a_{i+1},……,a_{i+m-1}) matches b]*2^{i-1}$

题解

考虑异或完可以被线性基表示，那么意味着不可以被表示的部分相同。将$a,b$数组都先用线性基筛掉，剩下无法表示的部分，跑$KMP$即可

代码

#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;}
const int MAXB=62;
struct Linear_Basis
{
    ll b[63],nb[63],tot;
     bool f;
    void init()
    {
        tot=0;
        f=true;
        memset(b,0,sizeof(b));
        memset(nb,0,sizeof(nb));
    }
    bool ins(ll x)
    {
        for(int i=MAXB;i>=0;i--)
            if (x&(1ll<<i))
            {
                if (!b[i]) {b[i]=x;break;}
                x^=b[i];
            }
        if(x==0)f=false;
        return x>0;
    }
    ll cal(ll x)
    {
        for(int i=MAXB;i>=0;i--){
            if(x&(1ll<<i)){
                x^=b[i];
            }
        }
        return x;
    }
} LB;
int n,m,k;
int a[N],b[N],s[N];
ll ans;
int nxt[N];
void GetNext(){
    for(int i=1;i<=n;i++){
        nxt[i]=0;
    }
    int i=1,j=0;
    while(i<m+1)
    {
        if(j==0||b[i]==b[j]) {++i,++j,nxt[i]=j;}
        else j=nxt[j];
    }
    return ;
}
void kmp(){
    int i=0,j=0;
    while(i<n+1)
    {
        if(j==0||a[i]==b[j]) i++,j++;
        else j=nxt[j];
        if(j==m+1)
        {
            ans=(ans+qpow(2,i-m-1))%p;
            j=nxt[j];
        }
    }
}
void work()
{
    ans=0;
    scanf("%d%d%d",&n,&m,&k);
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
    }
    for(int i=1;i<=m;i++){
        scanf("%d",&b[i]);
    }
    LB.init();
    for(int i=1;i<=k;i++){
        scanf("%d",&s[i]);
        LB.ins(s[i]);
    }
    for(int i=1;i<=n;i++){
        a[i]=LB.cal(a[i]);
        //printf("%d ",a[i]);
    }
    //printf("\n");
    for(int i=1;i<=m;i++){
        b[i]=LB.cal(b[i]);
        //printf("%d ",b[i]);
    }
    //printf("\n");
    GetNext();
    kmp();
    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();
    }
}

L.Linuber File System

lmj 赛后

题意

给定一棵有根树，每次可以选择一棵子树对其整体加减任意值,树中每个点的权值都要满足不同的区间要求，求符合要求的最少操作数。

题解

赛中看成一次只能加减一，想不到咋做。。。。
可以发现从一个区间变到其他区间只需要一次操作，那么考虑将区间离散化，这样可以获得$2n$个区间，然后对于父子关系来说，如果两者的区间相同，那么不需要修改，否则需要进行一次修改，dfs解决即可。

代码

#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 dp[2005][4005];
int l[2005];
int r[2005];
int q[4005];
int minn[2005];
int tot;
vector<int>v[N];
void dfs(int x,int fa)
{
    int sum=0;
    for(int i=0;i<v[x].size();i++){
        int u=v[x][i];
        if(u!=fa){
            dfs(u,x);
            sum+=minn[u]+1;
        }
    }
    for(int i=l[x];i<=r[x];i++){
        dp[x][i]=sum;
        for(int j=0;j<v[x].size();j++){
            int u=v[x][j];
            if(u==fa)continue;
            if(minn[u]==dp[u][i]){
                dp[x][i]--;
            }
        }
    }
    minn[x]=1e5;
    for(int i=l[x];i<=r[x];i++){
        minn[x]=min(minn[x],dp[x][i]);
    }
}
void work()
{
    int n;
    scanf("%d",&n);
    memset(dp,127,sizeof(dp));
    for(int i=1;i<=n;i++){
        v[i].clear();
    }
    for(int i=1;i<n;i++){
        int x,y;
        scanf("%d%d",&x,&y);
        v[x].push_back(y);
        v[y].push_back(x);
    }
    tot=0;
    for(int i=1;i<=n;i++){
        scanf("%d%d",&l[i],&r[i]);
        q[++tot]=l[i]-1;
        q[++tot]=r[i];
    }
    q[++tot]=-1e9;
    q[++tot]=1e9;
    sort(q+1,q+tot+1);
    tot=unique(q+1,q+tot+1)-q-1;
    for(int i=1;i<=n;i++){
        l[i]=lower_bound(q+1,q+tot+1,l[i])-q;
        r[i]=lower_bound(q+1,q+tot+1,r[i])-q;
    }
    dfs(1,0);
    int ans=1e5;
    for(int i=l[1];i<=r[1];i++){
        if(q[i-1]<0&&q[i]>=0){
            ans=min(ans,dp[1][i]);
        }else{
            ans=min(ans,dp[1][i]+1);
        }
        //printf("%d\n",q[i]);
        //printf("%d\n",dp[1][i]);
    }
    printf("%d\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();
    }
}

本文由 Edwiv 创作，采用 知识共享署名4.0 国际许可协议进行许可
本站文章除注明转载/出处外，均为本站原创或翻译，转载前请务必署名
最后编辑时间为: Aug 15, 2020 at 09:15 am