hgoi#20190628

muronglin
muronglin 2019年06月28日
  • 在其它设备中阅读本文章

T1- 打印收费

CZYZ 校园内有一家打印店,收费有着奇葩的规则,对于打印的量不同的情况会收取不同的费用。例如打印少于 100 张的时候,收取 20 分每张,但是打印不少于 100 张,收取 10 分每张,显然打印 99 张时候应该打印 100 张,而不是打印 99 张。现在告诉你打印店的收费策略,给出一些询问,求出打印若干张时候最少需要支付的钱数。

解法

贪心,对于打印若干张,有两种可能 就按当前张打印 或者多打印,打印张数为某个临界点

ac 代码

#include<bits/stdc++.h>
#define ll long long
#define inf 0x3f3f3f3f
using namespace std;
int n,m,q,k,s[100010],p[100010];
ll a[100010];
int main()
{
    freopen("printer.in","r",stdin),freopen("printer.out","w",stdout);
    scanf("%d%d",&n,&m),p[0]=inf;
    for(int i=1;i<=n;i++)scanf("%d%d",&s[i],&p[i]),a[i]=1lls[i]p[i];
    for(int i=n;i>1;i--)a[i-1]=min(a[i-1],a[i]);
    //计算a数组,此临界点的最小花费
    while(m--)
    {
        scanf("%d",&q),k=lower_bound(s+1,s+1+n,q)-s;
        //二分查找即可
        if(k==n+1)printf("%lldn",1llp[k-1]q);
        else printf("%lldn",min(1llp[k-1]q,a[k]));
    }
    return 0;
}

T2- 最长合法括号序列

这是另一道处理合法括号序列的题目。 我们应该提醒你,如果一个括号序列插入“+”和“1”后,可以得到一个正确的数学表达式,那么它被称为“合法”的。 例如,序列“(())()”,“()”和“(()(()))”是合法的,但“)(”,“(()”和“(()))(”不是。 给出一个由“(”和“)”字符组成的字符串。你要找出它最长的是合法括号序列的子串,也同样要找出最长子串的个数。

解法

可以先找到所有的() 然后以最基础的匹配括号开始拓展,先检验外面是否有 '(' 和 ')' 然后与相邻的合并 直到不再更新,统计答案

ac 代码

#include<bits/stdc++.h>
using namespace std;
struct node{int l,r;}a[1000010];
char s[1000010];
int len,st=1,ed,cnt,flg=1,maxl,ans=1,l[1000010],r[1000010];
void del(int i){if(i==st)st=r[i];else r[l[i]]=r[i],l[r[i]]=l[i];}
int main()
{
    freopen("lrbs.in","r",stdin),freopen("lrbs.out","w",stdout);
    scanf("%s",s),len=strlen(s);
    for(int i=0;i<len;i++)if(s[i]=='('&&s[i+1]==')')a[++cnt]={i,i+1};
    for(int i=1;i<=cnt;i++)l[i]=i-1,r[i]=i+1;
    if(cnt)
    {
        ed=cnt+1;
        while(flg)
        {
            flg=0;
            for(int i=st;i!=ed;i=r[i])
            {
                while(1)
                {
                    if(a[i].l==0||a[i].r==len-1)break;
                    if(s[a[i].l-1]=='('&&s[a[i].r+1]==')')
                        a[i].l--,a[i].r++;
                    else break;
                }
                if(i!=st)if(a[l[i]].r+1==a[i].l)
                    flg=1,a[i].l=a[l[i]].l,del(l[i]);
                if(r[i]!=ed)if(a[i].r+1==a[r[i]].l)
                    flg=1,a[i].r=a[r[i]].r,del(r[i]);
            }
        }
    }
    else puts("0 1"),exit(0);
    maxl=a[st].r-a[st].l+1;
    for(int i=r[st];i!=ed;i=r[i])
    {
        if(a[i].r-a[i].l+1==maxl)ans++;
        if(a[i].r-a[i].l+1>maxl)maxl=a[i].r-a[i].l+1,ans=1;
    }
    printf("%d %dn",maxl,ans);
    return 0;
}

T3- 钻石游戏

一个 M 行 N 列的棋盘,里面放了 M*N 个各种颜色的钻石。每一次你可以选择任意两个相邻的颜色不同的钻石,进行交换。两个格子相邻的定义是两个格子有一条公共边。每次交换的分值为通过这次交换后能够形成的最大矩形的面积,具体请见样例。 跟传统的钻石游戏不太一样的是,交换后钻石不会消除。现在告诉你每一次操作,请输出每一次所能得到的分值。

解法

维护 4 个数组,分别表示当前点上下左右相同数字的个数 每次交换的时候需要维护 2 行 2 列,然后分情况讨论 如果是上下交换,只需查找上下的最大矩阵 如果是左右交换,只需查找左右的最大矩阵 查找具体看代码

ac 代码

#include<bits/stdc++.h>
#define N 510
using namespace std;
int n,m,p,xa,ya,xb,yb,aN,uN,dN,lN,rN;
void upda(int i,int j)
{
    if(ai==ai-1)ui=ui-1+1;else ui=1;
    if(ai==ai)li=li+1;else li=1;
}
void updb(int i,int j)
{
    if(ai==ai+1)di=di+1+1;else di=1;
    if(ai==ai)ri=ri+1;else ri=1;
}
void upd(int i,int j){upda(i,j),updb(i,j);}
int getl(int x,int y)
{
    int ll=x,rr=x,ans=0;
    //设定左右边界
    for(int i=lx;i>=1;i--)
    {
        while(all-1==ax&&lll-1>=i)ll--;
        //如果左边的颜色和当前颜色相同,且高度足够,就可以拓展
        //这样一共只会拓展n次
        while(arr+1==ax&&lrr+1>=i)rr++;
        ans=max(ans,(rr-ll+1)*i);
    }
    return ans;
}
int getr(int x,int y)
{
    int ll=x,rr=x,ans=0;
    for(int i=rx;i>=1;i--)
    {
        while(all-1==ax&&rll-1>=i)ll--;
        while(arr+1==ax&&rrr+1>=i)rr++;
        ans=max(ans,(rr-ll+1)*i);
    }
    return ans;
}
int getu(int x,int y)
{
    int ll=y,rr=y,ans=0;
    for(int i=ux;i>=1;i--)
    {
        while(ax==ax&&ux>=i)ll--;
        while(ax==ax&&ux>=i)rr++;
        ans=max(ans,(rr-ll+1)*i);
    }
    return ans;
}
int getd(int x,int y)
{
    int ll=y,rr=y,ans=0;
    for(int i=dx;i>=1;i--)
    {
        while(ax==ax&&dx>=i)ll--;
        while(ax==ax&&dx>=i)rr++;
        ans=max(ans,(rr-ll+1)*i);
    }
    return ans;
}
int main()
{
    freopen("diamond.in","r",stdin),freopen("diamond.out","w",stdout);
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)scanf("%d",&ai);
    for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)upda(i,j);
    for(int i=n;i>=1;i--)for(int j=m;j>=1;j--)updb(i,j);
    scanf("%d",&p);
    while(p--)
    {
        scanf("%d%d%d%d",&xa,&ya,&xb,&yb);
        swap(axa,axb),upd(xa,ya),upd(xb,yb);
        if(xa==xb)
        {
            if(ya>yb)swap(ya,yb);
            for(int i=ya-1;i>=1;i--)updb(xa,i),updb(xb,i);
            for(int i=yb+1;i<=m;i++)upda(xa,i),upda(xb,i);
            for(int i=xa-1;i>=1;i--)updb(i,ya),updb(i,yb);
            for(int i=xb+1;i<=n;i++)upda(i,ya),upda(i,yb);
            printf("%dn",max(getl(xa,ya),getr(xb,yb)));
        }
        else
        {
            if(xa>xb)swap(xa,xb);
            for(int i=ya-1;i>=1;i--)updb(xa,i),updb(xb,i);
            for(int i=yb+1;i<=m;i++)upda(xa,i),upda(xb,i);
            for(int i=xa-1;i>=1;i--)updb(i,ya),updb(i,yb);
            for(int i=xb+1;i<=n;i++)upda(i,ya),upda(i,yb);
            printf("%dn",max(getu(xa,ya),getd(xb,yb)));
        }
    }
    return 0;
}

T4-Walk

在比特镇一共有 n 个街区,编号依次为 1 到 n,它们之间通过若干条单向道路连接。 比特镇的交通系统极具特色,除了 m 条单向道路之外,每个街区还有一个编码 vali,不同街区可能拥有相同的编码。如果 vali and valj = valj,即 vali 在二进制下与 valj 做与运算等于 valj,那么也会 存在一条额外的从 i 出发到 j 的单向道路。 Byteasar 现在位于 1 号街区,他想知道通过这些道路到达每一个街区最少需要多少时间。因为比特镇的交通十分发达,你可以认为通过每条道路都只需要 1 单位时间。

解法

val 规则不能直接连边,不能枚举判断 所以要将它转化 我们新建 2^20 个点,将这些点与 val 值为其的点相连 由于我用的是 spfa 和优先队列,所以需要虚点到实点的距离为 1,实点到虚点的距离为 0,虚点与虚点之间的距离为 0 如果这个反一下,同一个实点到达的实点和虚点距离就是一样的,而虚点之间转移无代价,就会导致答案大了 1 至于虚点之间的转移,每次将其位数上的一个 1 删去,如此转移即可

ac 代码

#include<bits/stdc++.h>
#define N 200010
#define M 300010
#define lim (1<<20)
#define v e[i].to
using namespace std;
int n,m,a,b,cnt,dis[N+lim],head[N+lim];
struct node{int to,w,next;}e[2*N+M];
struct Node{int id;bool operator<(const Node b)const{return dis[id]>dis[b.id];}}u;
priority_queue<Node>q;
void add(int x,int y,int z){e[++cnt]={y,z,head[x]},head[x]=cnt;}
void spfa()
{
    while(!q.empty())
    {
        u=q.top(),q.pop();
        if(u.id<=lim)for(int i=0;i<20;i++)
            if(u.id>>i&1)if(dis[u.id^(1<<i)]==-1)
                dis[u.id^(1<<i)]=dis[u.id],q.push({u.id^(1<<i)});
        for(int i=head[u.id];i!=-1;i=e[i].next)
            if(dis[v]==-1)dis[v]=dis[u.id]+e[i].w,q.push({v});
    }
}
int main()
{
    freopen("walk.in","r",stdin),freopen("walk.out","w",stdout);
    memset(head,-1,sizeof(head)),memset(dis,-1,sizeof(dis)),scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)scanf("%d",&a),add(lim+i,a,0),add(a,lim+i,1);
    for(int i=1;i<=m;i++)scanf("%d%d",&a,&b),add(lim+a,lim+b,1);
    q.push({lim+1}),dis[lim+1]=0,spfa();
    for(int i=1;i<=n;i++)printf("%dn",dis[i+lim]);
}