更好的阅读体验

来观看

T1-打印收费

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

解法

贪心，对于打印若干张，有两种可能

就按当前张打印

或者多打印，打印张数为某个临界点

ac代码

#include
    
     #define ll long long#define inf 0x3f3f3f3fusing 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]=1ll*s[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("%lld\n",1ll*p[k-1]*q);        else printf("%lld\n",min(1ll*p[k-1]*q,a[k]));    }    return 0;}
    

T2-最长合法括号序列

这是另一道处理合法括号序列的题目。

我们应该提醒你，如果一个括号序列插入“+”和“1”后，可以得到一个正确的数学表达式，那么它被称为“合法”的。

例如，序列“(())()”，“()”和“(()(()))”是合法的，但“)(”，“(()”和“(()))(”不是。

给出一个由“(”和“)”字符组成的字符串。你要找出它最长的是合法括号序列的子串，也同样要找出最长子串的个数。

解法

可以先找到所有的()

然后以最基础的匹配括号开始拓展，先检验外面是否有'('和')'

然后与相邻的合并

直到不再更新，统计答案

ac代码

#include
    
     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
     
      maxl)maxl=a[i].r-a[i].l+1,ans=1;    }    printf("%d %d\n",maxl,ans);    return 0;}
     
    

T3-钻石游戏

一个 M 行 N 列的棋盘，里面放了 M*N 个各种颜色的钻石。每一次你可以选择任意两个相邻的颜色不同的钻石，进行交换。两个格子相邻的定义是两个格子有一条公共边。每次交换的分值为通过这次交换后能够形成的最大矩形的面积，具体请见样例。

跟传统的钻石游戏不太一样的是，交换后钻石不会消除。现在告诉你每一次操作，请输出每一次所能得到的分值。

解法

维护4个数组，分别表示当前点上下左右相同数字的个数

每次交换的时候需要维护2行2列，然后分情况讨论

如果是上下交换，只需查找上下的最大矩阵

如果是左右交换，只需查找左右的最大矩阵

查找具体看代码

ac代码

#include
    
     #define N 510using namespace std;int n,m,p,xa,ya,xb,yb,a[N][N],u[N][N],d[N][N],l[N][N],r[N][N];void upda(int i,int j){    if(a[i][j]==a[i-1][j])u[i][j]=u[i-1][j]+1;else u[i][j]=1;    if(a[i][j]==a[i][j-1])l[i][j]=l[i][j-1]+1;else l[i][j]=1;}void updb(int i,int j){    if(a[i][j]==a[i+1][j])d[i][j]=d[i+1][j]+1;else d[i][j]=1;    if(a[i][j]==a[i][j+1])r[i][j]=r[i][j+1]+1;else r[i][j]=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=l[x][y];i>=1;i--)    {        while(a[ll-1][y]==a[x][y]&&l[ll-1][y]>=i)ll--;        //如果左边的颜色和当前颜色相同，且高度足够，就可以拓展        //这样一共只会拓展n次        while(a[rr+1][y]==a[x][y]&&l[rr+1][y]>=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=r[x][y];i>=1;i--)    {        while(a[ll-1][y]==a[x][y]&&r[ll-1][y]>=i)ll--;        while(a[rr+1][y]==a[x][y]&&r[rr+1][y]>=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=u[x][y];i>=1;i--)    {        while(a[x][ll-1]==a[x][y]&&u[x][ll-1]>=i)ll--;        while(a[x][rr+1]==a[x][y]&&u[x][rr+1]>=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=d[x][y];i>=1;i--)    {        while(a[x][ll-1]==a[x][y]&&d[x][ll-1]>=i)ll--;        while(a[x][rr+1]==a[x][y]&&d[x][rr+1]>=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",&a[i][j]);    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(a[xa][ya],a[xb][yb]),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("%d\n",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("%d\n",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
    
     #define N 200010#define M 300010#define lim (1<<20)#define v e[i].tousing 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
     
      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<