[A] Girls Band Party

给出一些牌,每张牌有一个名字,颜色和点数.现在需要从其中挑出不重名的五张牌,使得点数之和最大.

此外,有一些情况可以增加点数.一开始钦定了5个名字和1种颜色.挑选出的牌中每有一张牌的名字位于钦定的5个之中,就获得10%的加成;每有一张牌的颜色是被钦定的,就获得20%的加成.一张牌的名字合并颜色可以同时带来加成效果.最后点数为基础点数乘以加成比率.求最大点数.

每张牌带来的加成按照比率可以分为0%,10%,20%,30%四种情况.将所有牌分为这四类,每一类按照点数从高到低排序,同一名称只保留点数最高的.然后从这四类里各抽出前五张牌.不难证明,最后的最优解一定会从20牌中产生.然后DFS枚举组合情况即可.时间复杂度为 O(nlogn)

#include<cstring>
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<unordered_map>
#define N 100010
using namespace std;

int n,i,T,sum=0,Ans=0;
int d[N],l[11];
int Buff[5]={0,10,20,30,0};
char name[N][11],col[N][11],a[6][11],c[11];

unordered_map <string,int> M,M1,M2,M3,M4;

struct Data{
    int a,b,c;
}f1[N],f2[N],f3[N],f4[N],f5[N];

inline int Min(int a,int b){return (a<b)?a:b;}
inline int Max(int a,int b){return (a>b)?a:b;}
inline bool cmp(const Data &x,const Data &y){return x.a>y.a;}

inline void Ready(){
    register int i=0,s=0,j=0,len=0;
    M.clear();
    for (i=1;i<=5;i++)  M[a[i]]=1;
    memset(l,0,sizeof(l));
    for (i=1;i<=n;i++){
        s=M[name[i]]+10;
        len=Min(strlen(col[i]),strlen(c));
        if (strlen(col[i])!=strlen(c))  s-=10;
        else
            for (j=0;j<len;j++)
                if (col[i][j]!=c[j])    {s-=10; break;}
        if (s==11)  f3[++l[3]].a=d[i],f3[l[3]].b=3,f3[l[3]].c=i;
        else if (s==10) f2[++l[2]].a=d[i],f2[l[2]].b=2,f2[l[2]].c=i;
        else if (s==1)  f1[++l[1]].a=d[i],f1[l[1]].b=1,f1[l[1]].c=i;
        else f4[++l[4]].a=d[i],f4[l[4]].b=4,f4[l[4]].c=i;
    }
    sort(f1+1,f1+l[1]+1,cmp);   sort(f2+1,f2+l[2]+1,cmp);
    sort(f3+1,f3+l[3]+1,cmp);   sort(f4+1,f4+l[4]+1,cmp);
}

inline void Dfs(int x,int s,int cnt,int buff){
    register int i=0;
    if (s==5){
        Ans=Max(Ans,cnt*buff);  return;
    }
    if (x>sum)  return;
    for (i=x+1;i<=sum;i++){
        if (M[name[f5[i].c]]==10)   continue;
        M[name[f5[i].c]]=10;
        Dfs(i,s+1,cnt+f5[i].a,buff+Buff[f5[i].b]);
        M[name[f5[i].c]]=0;
    }
}

inline void Work(){
    register int i=0,cnt=0;
    sum=0;  Ans=0;
    M1.clear(); M2.clear(); M3.clear(); M4.clear();
    for (i=1;i<=n;i++)  M1[name[i]]=1;  M2=M3=M4=M1;
    for (cnt=0,i=1;i<=l[1]&&cnt<5;i++)
        if (M1[name[f1[i].c]]!=3)   f5[++sum]=f1[i],M1[name[f1[i].c]]=3,cnt++;
    for (cnt=0,i=1;i<=l[2]&&cnt<5;i++)
        if (M2[name[f2[i].c]]!=3)   f5[++sum]=f2[i],M2[name[f2[i].c]]=3,cnt++;
    for (cnt=0,i=1;i<=l[3]&&cnt<5;i++)
        if (M3[name[f3[i].c]]!=3)   f5[++sum]=f3[i],M3[name[f3[i].c]]=3,cnt++;
    for (cnt=0,i=1;i<=l[4]&&cnt<5;i++)
        if (M4[name[f4[i].c]]!=3)   f5[++sum]=f4[i],M4[name[f4[i].c]]=3,cnt++;
    M.clear();
    for (i=1;i<=sum;i++)    M[name[f5[i].c]]=0;
    Dfs(0,0,0,100);
    printf("%d\n",Ans/100);
}

int main(){
    #ifdef __Marvolo
    freopen("zht.in","r",stdin);
    freopen("zht.out","w",stdout);
    #endif
    scanf("%d",&T);
    while (T--){
        scanf("%d",&n);
        for (i=1;i<=n;i++)  scanf("%s %s %d",&name[i],&col[i],&d[i]);
        for (i=1;i<=5;i++)  scanf("%s",&a[i]),getchar();
        scanf("%s",&c);
        Ready();    Work();
    }
    return 0;
}

[B] So Easy

给出一个n*n的矩形,初始时所有元素都为0.每一次可以选择某一行或者某一列,使其中的所有元素的值+1.给出经过一系列操作后的矩阵,其中有个位置的值为-1(即为未知).求出该位置的值.

注意到,任意子矩形对角线上元素之和相等,分四种情况计算即可.

#include<cstring>
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<vector>
#include<cmath>
#define l(x) (x<<1)
#define r(x) ((x<<1)+1)
#define LL long long
#define INF 0x3f3f3f3f
using namespace std;

int n,i,j,x,y,Ans;
int a[1010][1010];

inline int Abs(int x){return (x<0)?-x:x;}
inline void Swap(int &a,int &b){a^=b^=a^=b;}
inline int Min(int a,int b){return (a<b)?a:b;}
inline int Max(int a,int b){return (a>b)?a:b;}

inline int read(){
    int p=0;    char    c=getchar();
    while (c<48||c>57)  c=getchar();
    while (c>=48&&c<=57)    p=(p<<1)+(p<<3)+c-48,c=getchar();
    return p;
}

int main(){
    #ifdef __Marvolo
    freopen("zht.in","r",stdin);
    freopen("zht.out","w",stdout);
    #endif
    scanf("%d",&n);
    for (i=1;i<=n;i++)
        for (j=1;j<=n;j++){
            scanf("%d",&a[i][j]);
            if (a[i][j]==-1)    x=i,y=j;
        }
    if (x>1&&y>1)   Ans=a[x-1][y]+a[x][y-1]-a[x-1][y-1];
    else if (x<n&&y<n)  Ans=a[x+1][y]+a[x][y+1]-a[x+1][y+1];
    else if (x>1&&y<n)  Ans=a[x-1][y]+a[x][y+1]-a[x-1][y+1];
    else Ans=a[x+1][y]+a[x][y-1]-a[x+1][y-1];
    printf("%d\n",Ans);
    return 0;
}

[F] Function!

计算\sum_{a=2}^{n}a\sum_{b=a}^{n}\lfloor \log_a{b} \rfloor

当a<\sqrt{n}时,\lfloor \log_a{b} \rfloor的值至多有log_2{n}种情况.暴力循环,枚举每一种情况计算.

当a>\sqrt{n}时,\lfloor \log_a{b} \rfloor的值恒为1.推导可知,这部分的值为(n+1)\sum_{i=\sqrt{n}+1}^{n}i-\sum_{i=\sqrt{n}}^{n}i^2.

#include<cstring>
#include<cstdio>
#include<iostream>
#include<cmath>
#define LL long long
#define MOD 998244353ll
using namespace std;

LL n,m=0,sum=0,cnt=0,Ans=0,i,l,r,t=0;

inline LL Mi(LL x,LL y){
    LL p=x,t=1,Res=1;
    for (;t<=y;(t&y)?Res=(Res*p)%MOD:0,p=(p*p)%MOD,t<<=1);
    return Res;
}

inline LL S1(LL x){
    LL l=x,r=x+1;
    (l%2)?r/=2:l/=2;
    return ((l%MOD)*(r%MOD))%MOD;
}

inline LL S2(LL x){
    LL s=1,ss=Mi(6,MOD-2);
    s=((x%MOD)*((x+1)%MOD))%MOD;
    s=(s*((2*x+1)%MOD))%MOD;
    return (s*ss)%MOD;
}

int main(){
    #ifdef __Marvolo
    freopen("zht.in","r",stdin);
    freopen("zht.out","w",stdout);
    #endif
    scanf("%lld",&n);
    m=(LL)sqrt(n);
    while (m*m>n)   m--;
    for (i=2;i<=m;i++){
        l=i;    r=i*i;  t=1;    sum=0;
        while (r<=n+1){
            sum=(sum+((r-l)%MOD*t)%MOD)%MOD;
            t++;    l=r;    r=r*i;
        }
        if (l<=n)
            sum=(sum+((n-l+1)%MOD*t)%MOD)%MOD;
        cnt=(cnt+(sum*i)%MOD)%MOD;
    }
    Ans=cnt%MOD;    sum=cnt=0;
    sum=(S1(n)-S1(m)+MOD)%MOD;
    sum=(sum*((n+1)%MOD))%MOD;
    Ans=(Ans+sum)%MOD;
    sum=(S2(n)-S2(m)+MOD)%MOD;
    Ans=(Ans-sum+MOD)%MOD;
    cout<<Ans%MOD;
    return 0;
}

[G] Pot!!

给出一个长度为n的数列和两种操作.数列初始值为1.第一种操作是将[l,r]中的每个数乘以x,x\leq 10.第二种是求[l,r]中某个数对质数的阶最高是多少.

显然,质数只有2,3,5,7四种情况.用线段树维护区间最大值,并进行区间累加操作即可.

#include<cstring>
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<vector>
#include<cmath>
#define N 100010
#define l(x) (x<<1)
#define r(x) ((x<<1)+1)
#define LL long long
#define INF 0x3f3f3f3f
using namespace std;

int n,m,i,l,r,x;
char s[110];

inline int Max(int a,int b){return (a>b)?a:b;}

struct SegmentTrere{
    struct Tree{
        int x,l,r,d,p;
    }t[N*4];

    inline void Maketree(int x,int low,int high){
        int mid=(low+high)>>1;
        t[x].l=low; t[x].r=high;
        if (low==high) return;
        Maketree(l(x),low,mid); Maketree(r(x),mid+1,high);
    }

    inline void Push(int x){
        int p=t[x].p;
        t[l(x)].d+=p;   t[r(x)].d+=p;
        t[l(x)].p+=p;   t[r(x)].p+=p;
        t[x].p=0;
    }

    inline void Add(int x,int low,int high,int val){
        int mid=(t[x].l+t[x].r)>>1;
        if (t[x].l==low&&t[x].r==high){
            t[x].d+=val;    t[x].p+=val;    return;
        }
        if (t[x].p) Push(x);
        if (high<=mid)  Add(l(x),low,high,val);
        else    if (low>mid)    Add(r(x),low,high,val);
        else    Add(l(x),low,mid,val),Add(r(x),mid+1,high,val);
        t[x].d=Max(t[l(x)].d,t[r(x)].d);
    }

    inline int Query(int x,int low,int high){
        int mid=(t[x].l+t[x].r)>>1;
        if (t[x].l==low&&t[x].r==high)  return t[x].d;
        if (t[x].p) Push(x);
        if (high<=mid)  return Query(l(x),low,high);
        else if (low>mid)   return Query(r(x),low,high);
        else return Max(Query(l(x),low,mid),Query(r(x),mid+1,high));
    }
}T2,T3,T5,T7;

inline void Mul(int l,int r,int p){
    if (p==2)   T2.Add(1,l,r,1);
    else if (p==3)  T3.Add(1,l,r,1);
    else if (p==4)  T2.Add(1,l,r,2);
    else if (p==5)  T5.Add(1,l,r,1);
    else if (p==6)  T2.Add(1,l,r,1),T3.Add(1,l,r,1);
    else if (p==7)  T7.Add(1,l,r,1);
    else if (p==8)  T2.Add(1,l,r,3);
    else if (p==9)  T3.Add(1,l,r,2);
    else if (p==10) T2.Add(1,l,r,1),T5.Add(1,l,r,1);
}

inline int Query(int l,int r){
    return Max(Max(T2.Query(1,l,r),T3.Query(1,l,r)),Max(T5.Query(1,l,r),T7.Query(1,l,r)));
}

int main(){
    #ifdef __Marvolo
    freopen("zht.in","r",stdin);
    freopen("zht.out","w",stdout);
    #endif
    scanf("%d%d",&n,&m);
    T2.Maketree(1,1,n); T3.Maketree(1,1,n);
    T5.Maketree(1,1,n); T7.Maketree(1,1,n);
    for (i=1;i<=m;i++){
        scanf("%s %d%d",&s,&l,&r);
        if (s[1]=='U'){
            scanf("%d",&x);
            Mul(l,r,x);
        }   else printf("ANSWER %d\n",Query(l,r));
    }
    return 0;
}

[I] Base62

给出一个a进制数,要求转化为b进制输出.

用Python实现方便一些.

a,b,c=input().split()
a=int(a)
b=int(b)
l=len(c)
s=int(0)
f=int(1)
for i in range(l-1,-1,-1):
    if (c[i]>='A' and c[i]<='Z'):
        s+=(ord(c[i])-(ord('A')-10))*f
    elif (c[i]>='a' and c[i]<='z'):
        s+=(ord(c[i])-(ord('a')-36))*f
    else:
        s+=(ord(c[i])-48)*f
    f*=a
ans=[]
if (s==0):
    ans.append('0')
while s>=1:
    x=s%b
    if (x>=36):
        ans.append(chr(int(x)+ord('a')-36))
    elif (x>=10):
        ans.append(chr(int(x)+ord('A')-10))
    else:
        ans.append(chr(int(x)+48))
    s//=b
for i in range(len(ans)-1,-1,-1):
    print(ans[i],end='')

[K] Largest Common Submatrix

给出两个n*m的矩形,每个矩形中的元素都是1到n*m的排列.现在要求出两个矩形的最大公共子矩形的面积是多少.不要求公共子矩形在同样的位置.

让第一个矩形每个元素的坐标减去其在第二个矩形的坐标,得到类似二维向量的东西,然后填到原位置.问题就转化为了求一个矩形中最大的相同元素子矩形的面积是多少.用悬线法直接做即可.

#include<cstring>
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<vector>
#include<cmath>
#define N 1010
using namespace std;

int n,m,i,j,x,Ans;
int a[N][N],l[N][N],r[N][N],h[N][N];

struct Data{
    int x,y;
}f[N][N],t[N*N];

inline int Abs(int x){return (x<0)?-x:x;}
inline void Swap(int &a,int &b){a^=b^=a^=b;}
inline int Min(int a,int b){return (a<b)?a:b;}
inline int Max(int a,int b){return (a>b)?a:b;}

inline int read(){
    int p=0;    char    c=getchar();
    while (c<48||c>57)  c=getchar();
    while (c>=48&&c<=57)    p=(p<<1)+(p<<3)+c-48,c=getchar();
    return p;
}

inline void Insert(int x,int p,int q){
    t[x].x=p;   t[x].y=q;
}

int operator ==(Data x,Data y){return (x.x==y.x)&(x.y==y.y);}

inline void Work(){
    register int i=0,j=0,w=0;
    Ans=1;
    for (i=1;i<=n;i++)
        for (j=1;j<=m;j++){
            f[i][j].x=i-t[a[i][j]].x;   f[i][j].y=j-t[a[i][j]].y;
        }
    for (i=1;i<=m;i++)  h[1][i]=1;
    for (i=1;i<=n;i++){
        r[i][m]=l[i][1]=0;
        for (j=2;j<=m;j++)  l[i][j]=(l[i][j-1]+1)*(f[i][j]==f[i][j-1]);
        for (j=m-1;j;j--)   r[i][j]=(r[i][j+1]+1)*(f[i][j]==f[i][j+1]);
    }
    for (i=2;i<=n;i++)
        for (j=1;j<=m;j++)
            if (f[i][j]==f[i-1][j]){
                l[i][j]=Min(l[i][j],l[i-1][j]);
                r[i][j]=Min(r[i][j],r[i-1][j]);
                h[i][j]=h[i-1][j]+1;
            }   else h[i][j]=1;
    for (i=1;i<=n;i++)
        for (j=1;j<=m;j++)
            Ans=Max(Ans,h[i][j]*(l[i][j]+r[i][j]+1));
    printf("%d\n",Ans);
}

int main(){
    #ifdef __Marvolo
    freopen("zht.in","r",stdin);
    freopen("zht.out","w",stdout);
    #endif
    n=read();   m=read();
    for (i=1;i<=n;i++)
        for (j=1;j<=m;j++){
            x=read();   Insert(x,i,j);
        }
    for (i=1;i<=n;i++)
        for (j=1;j<=m;j++)
            a[i][j]=read();
    Work();
    return 0;
}

[N] Fibonacci Sequence

print("1 1 2 3 5",end='')