又考挂了QAQ 总rank直接滑出前20

晚上考试脑子还算比较清醒，可惜都用来xjb乱想错误思路了。

T1一眼推柿子，然而并没有头绪所以先码了个暴力。然后……

一个垃圾暴力我调了1h，大概解决了两位数个sb错误之后终于调出来了。本来觉得考了这么多场代码能力长了不少，暴搜什么的一边过样例应该没问题的。可能这次写的时候比较急躁？抑或是学了几天文化课码力大减？反正浪费这么多时间是很不应该的。

暴力尽量一遍打对，它不配你在调试上花时间。

然后写了个打表程序去看T2。因为T1只打了个暴力所以A掉T2的想法十分强烈，想了各种奇奇怪怪的方法(甚至想到了正解的时光倒流)，但要么是复杂度不优，要么打到一半把自己否了，又不得不删了重想。就这么删了码码了删浪费了很多时间，感觉像是回到了一开始没怎么考过试的时候。

码之前一定要保证思路基本是正确的，条件允许的话应该先手玩几组样例。

这样大概过了一个半小时，忽然发现自己连最sb的暴力都没打，慌忙码了一个二维前缀和结果死也调不出来，后来发现是自己二维前缀和查询的柿子打错了，赶紧手推了一下过了样例。

二维前缀和查询$(i,j)$到$(x,y)$的权值和：$ans=sum(x,y)-sum(i-1,y)-sum(x,j-1)-sum(i-1,j-1)$。简单的东西一定要记清楚，确保自己考场能不浪费一秒钟。

最后不剩多少时间了，T1交了个表，T2感觉q=1的点不一定能跑过去于是卡了卡常，看了一会T3发现期望题好像不能骗分就弃掉了。然后大概检查了一下好像没有问题，于是就无奈地闲坐着心里mmp。

结束之后发现T1看错数据范围打表打少了扔掉20，T3有20分是白痴暴搜没打。

最后一定要再看一眼题啊QAQ

发现T1的柿子好像挺简单的，要是一开始打完T2的暴力就回来想正解的话应该能推出来。T2没有我想的那么水，感觉自己分析难度能力基本没有啊ccc。

$Solution:$

A.Chinese

解题关键在于理解$\sum i\times f[i]$的含义，所有方案中炼字个数之和。

考虑$[1,k]$每个数对答案的贡献，当方格$(x,y)$填$i (i \in [1,k])$且$i$是炼字时，它对答案的贡献(产生的方案数)是$(i-1)^{n-1}(i-1)^{m-1}k^{nm-n-m+1}$。

那么最后的答案就是$nm \times \sum \limits _{i=1}^{k} (i-1)^{n-1} (i-1)^{m-1} k^{nm-n-m+1}$

#include<cstdio>

#include<iostream>

#include<cstring>

using namespace std;

typedef long long ll;

const ll mod=1e9+7;

ll n,m,k,ans;

ll qpow(ll a,ll b)

{

    ll res=1;

    while(b)

    {

        if(b&1)res=res*a%mod;

        a=a*a%mod;

        b>>=1;

    }

    return res;

}

int main()

{

    scanf("%lld%lld%lld",&n,&m,&k);

    for(ll i=1;i<=k;i++)

        ans+=(qpow(i-1,n-1)*qpow(i-1,m-1)%mod*qpow(k,n*m-n-m+1)%mod),ans%=mod;

    ans=ans*n%mod*m%mod;

    cout<<ans<<endl;

    return 0;

}

B.physics

没打正解A掉的(捂脸)。

统计一下负电子的二维前缀和，对于每次询问，修改的话直接暴力更新前缀和，查询之前先看一下更改的位置在不在之前记录下来的最大正方形里，如果不在就直接输出上次的结果，否则二分答案得到新的最大正方形以及答案。

二分答案合法性判断就看能不能找到边长为目前check值的正方形，这个直接用二维前缀和$O(1)$验证即可。

复杂度O(可过)。主要是因为这题数据不好造所以这玩意跑的飞快QAQ。

#include<cstdio>

#include<iostream>

#include<cstring>

#include<cmath>

#define re register

using namespace std;

const int N=1e3+55;

inline int read()

{

    int x=0,f=1;char ch=getchar();

    while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}

    while(isdigit(ch))x=x*10+ch-'0',ch=getchar();

    return x*f;

}

int a[N][N],sum[N][N];

int n,m,q,K;

int nowx,nowy;

inline bool check(int k)

{

    for(re int i=1;i+k-1<=n;i++)

        for(re int j=1;j+k-1<=m;j++)

            if(sum[i+k-1][j+k-1]-sum[i-1][j+k-1]-sum[i+k-1][j-1]+sum[i-1][j-1]==0)

            {

                nowx=i,nowy=j;

                return 1;

            }

    return 0;

}

inline void update(int x,int y)

{

    for(re int i=x;i<=n;i++)

        for(re int j=y;j<=m;j++)

            sum[i][j]++;

}

inline void binary_ans()

{

    int l=0,r=K;

    while(l<=r)

    {

        int mid=l+r>>1;

        if(check(mid))l=mid+1,K=mid;

        else r=mid-1;

    }

}

inline bool in(int x,int y,int len,int xx,int yy)

{

    if(xx<x||xx>x+len-1||yy<y||yy>y+len-1)return 0;

    return 1;

}

int main()

{

    //freopen("physics3.in","r",stdin);

    n=read();m=read();q=read();

    char s[1005];

    for(re int i=1;i<=n;i++)

    {

        scanf("%s",s+1);

        for(re int j=1;j<=m;j++)

        {

            if(s[j]=='+')a[i][j]=1;

            else if(s[j]=='-')

                a[i][j]=2;

            sum[i][j]=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]+(a[i][j]==2);

        }

    }

    K=min(n,m);

    binary_ans();

    while(q--)

    {

        int x=read(),y=read();

        a[x][y]=2;

        update(x,y);

        if(in(nowx,nowy,K,x,y))

            binary_ans();

        printf("%d\n",K);

    }

    return 0;

}

巴特西

[NOIP模拟测试32]反思+题解

A.Chinese

B.physics

最新文章

热门文章