1104练习赛

T1算面积

r*c个方块，每个都有一个面积，求一个矩阵内的面积之和。
由于r*c很大，所以这里我们规定如下：每一行输入一串字符串，表示这一行由这个字符串重复得到。
字符串长度不超过100.

1<=r,c<=100000

很容易往给循环节分类这方面思考。

分类后分别得到前缀和，在把询问离线一下，就可以了。

#include
using namespace std;
#define re register int
#define LL long long
const int N=1e5+5;
struct node{
    int x, y, id;
    bool operator<(const node&p)const{
        return x < p.x;
    }
}A[N<<2];
int n, m, ct, q;
LL Ans[N], f[105][105];
char ch[N][105];
inline void add(int x)
{
    LL sum=0;
    for(re i=1,len=strlen(ch[x]+1);i<=len;++i)
    {
        sum+=(ch[x][i]-'0');
        f[len][i]+=sum;
    }
}
signed main()
{
    scanf("%d%d",&n,&m);
    for(re i=1;i<=n;++i) scanf("%s",ch[i]+1);
    scanf("%d",&q);
    for(re i=1;i<=q;++i)
    {
        int x,y,xx,yy;
        scanf("%d%d%d%d",&x,&y,&xx,&yy);
        A[++ct]=(node){xx,yy,i};
        if(y-1)A[++ct]=(node){xx,y-1,-i};
        if(x-1)A[++ct]=(node){x-1,yy,-i};
        if(x-1&&y-1)A[++ct]=(node){x-1,y-1,i};
    }
    sort(A+1,A+1+ct);
    for(re i=1,l=0;i<=ct;++i)
    {
        int x=A[i].x, y=A[i].y, k=A[i].id;
        LL ret=0;
        while(l+1<=n&&l+1<=x)add(l+1),l++;
        for(re j=1;j<=100;++j)
        {
            if(y%j)ret+=f[j][y%j]+y/j*f[j][j];
            else ret+=y/j*f[j][j];
        }
        Ans[abs(k)]+=(k<0?-1:1)*ret;
    }
    for(re i=1;i<=q;++i)printf("%lld\n",Ans[i]);
    return 0;
}

T2猜数

定义mirror(x)表示把x翻转后的值。
求有多少个x满足x+mirror(x)=z

1<=z<=10^18

手玩一下就很好得到。

可惜kzsn考场上暴力写错了，没调出来。

以后一定先写好暴力，再写正解，还要对拍。

#include
using namespace std;
#define re register int
#define int long long
int num[50], sum[50], head;
inline int dfs(int x, int y)
{
    while(num[y]<0)num[y]+=10,num[y-1]--;
    if(x==y)return (num[x]&1)?0:1;
    if(x+1==y)
    {
        if(num[x]==num[y])return (x==head?num[x]:sum[num[x]]);
        if(num[x]-1==num[y]+10)return sum[num[x]-1];
        return 0;
    }
    if(num[x]==num[y])return (x==head?num[x]:sum[num[x]])*dfs(x+1,y-1);
    if(num[x]==num[y]+10)
    {
        num[y-1]--;
        return sum[num[x]]*dfs(x+1,y-1);
    }
    if(num[x]-1==num[y]+10)
    {
        num[x+1]+=10;
        num[y-1]--;
        return sum[num[x]-1]*dfs(x+1,y-1);
    }
    if(num[x]-1==num[y])
    {
        num[x+1]+=10;
        return (x==head?num[x]-1:sum[num[x]-1])*dfs(x+1,y-1);
    }
    return 0;
}
char ch[50];
signed main()
{
    for(re i=0;i<=9;++i)for(re j=0;j<=9;++j)sum[i+j]++;
    int T;scanf("%lld",&T);
    for(re i=1;i<=T;++i)
    {
        scanf("%s",ch+1);
        int ct=strlen(ch+1), ans=0;
        num[0]=0;for(re i=1;i<=ct;++i)num[i]=ch[i]-'0';num[ct+1]=0;
        head=1;ans+=dfs(1, ct);
        num[0]=0;for(re i=1;i<=ct;++i)num[i]=ch[i]-'0';num[ct+1]=0;
        if(num[1]==1 && ct>=2)
        {
            num[2]+=10*num[1];
            head=2;
            ans+=dfs(2, ct);
        }
        printf("%lld\n",ans);
    }
}

T3排序

 有点难，可以线段树模拟，也可以根据性质O(n)求。

#include
using namespace std;
#define re register int
#define LL long long
const int N=1e6+6;
struct node{
    int x,id;
    bool operator<(const node&p)const{
        return (x==p.x)?(idp.x);
    }
}a[N];
LL ans;
signed main()
{
    int n;
    scanf("%d",&n);
    for(re i=1;i<=n;i++)scanf("%d",&a[i].x),a[i].id=i;
    sort(a+1,a+1+n);
    for(re i=n,j=n,rd=0,rt=0,nxt;i&&j;i=j)
    {
        int x=a[i].x, flag=0;
        nxt=a[i].id;
        while(a[j].x==x)
        {
            if(!flag && a[j].id1;
            ans+=rd;
            j--;
        }
        rt=nxt;
    }
    printf("%lld\n",ans);
    return 0;
}

T4排水

 数据范围：4<=n<=300000,k<=n/2;

挺容易想到笛卡尔树的，但是考场上kzsn不敢贪心，准确的说没完全分析清楚。

这道题就是把笛卡尔树建出来，然后求一条条最长的链，贪心的搞就行了。

#include
using namespace std;
#define re register int
#define int long long
const int N=1e6+5;
int n, a[N], b[N], c[N], d[N], cnt, di, root, WA=1e9;
int ls[N], rs[N], sz[N], q[N];
void dfs(int x)
{
    sz[x]=d[x];
    if(ls[x])
    {
        dfs(ls[x]);
        sz[x]+=sz[ls[x]];
    }
    if(rs[x])
    {
        dfs(rs[x]);
        sz[x]+=sz[rs[x]];
    }
}
int f[N];
priority_queue<int>Q;
void dp(int x)
{
    if(ls[x])dp(ls[x]);if(rs[x])dp(rs[x]);
    if(ls[x] && rs[x])
    {
        int xx=f[ls[x]]+(c[x]-c[ls[x]])*sz[ls[x]];
        int yy=f[rs[x]]+(c[x]-c[rs[x]])*sz[rs[x]];
        if(xx<yy)Q.push(xx);
        else Q.push(yy);
        f[x]=max(xx, yy);
        return;
    }
    if(ls[x])
    {
        f[x]=f[ls[x]]+(c[x]-c[ls[x]])*sz[ls[x]];
    }
    if(rs[x])
    {
        f[x]=f[rs[x]]+(c[x]-c[rs[x]])*sz[rs[x]];
    }
}
signed main()
{
    scanf("%lld",&n);
    for(re i=1;i<=n;++i)
    {
        scanf("%lld%lld",&a[i],&b[i]);
        di = max(di, b[i]);
    }
    int xx=a[1];
    for(re i=2;i<=n;++i)
    {
        if(a[i]!=xx)
        {
            c[++cnt] = di-b[i];
            WA = min(WA, di-c[cnt]);
            d[cnt] = a[i]-xx;
            xx=a[i];
        }
    }
    for(re i=1, h=0;i<=cnt;++i)
    {
        while(h && c[q[h]]];
        if(!h) root=i;
        else rs[q[h]]=i;
        q[++h]=i;
    }
    dfs(root);
    dp(root);
    int ans = WA * sz[root] + f[root], K;
    scanf("%lld",&K);
    while(K>1)
    {
        ans+=Q.top();
        Q.pop();
        K--;
    }
    printf("%lld\n", ans);
    return 0;
}

1104练习赛 王启钧总结

这次考试就很惨，（这几次似乎都是）就差一步就是正解了，却没有继续深入下去。
像这次T4，我那40分就是笛卡尔树做出来的，很贪心，但没有继续想到正解就可以继续贪下去。
误以为是什么神奇的背包dp，但是数组开不下，就思维僵化了。

T1，一个就按照长度来分类的题，怎么做都可以，但我没有仔细思考他那特殊的数据范围
导致只得了暴力分。
T2，我认为自己可以得满分的题。
考试过程中一直对拍着，没有任何错误。
但很离谱的是，我暴力写错了，而且和暴力思想没任何关系的正解，也恰好答案全部对得上！
好离谱。
T2也是我唯一一道先写正解，再写暴力的题，暴力写错了，需要好好反思。

T3，分析了很久，也画了图想找些规律，但没弄出来，很可惜。
T4，完美找对方向，笛卡尔树，但为什么就不更深一步想啊。
这次考试时间还是有点紧，主要是自己想T3太久了。下次注意时间以及让脑瓜子活动起来。