武汉大学2023年新生程序设计竞赛（同步赛）

题目J

思路：

注意到，行和列的贡献可以分开算，故操作顺序对最终的结果没有影响，可以直接从左到右、从上到下进行放棋子操作，按行按列分别计算即可

时间复杂度

Code:

#include <bits/stdc++.h>

using namespace std;
#define IOS ios::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr);
#define int long long
#define ull unsigned long long
#define lowbit(i) ((i)&(-i))
#define ls(p) (p<<1)
#define rs(p) (p<<1|1)
#define rep(i, a, b) for(int i=a;i<=b;i++)
#define per(i, a, b) for(int i=a;i>=b;i--)

typedef pair<int, int> PII;
const int mod = 1e9 + 7;
const int inf = 0x3f3f3f3f;
const int N = 2e5 + 200;

int qpow(int a, int n) {
    int ans = 1;
    while (n) {
        if (n & 1) {
            ans = ans * a % mod;
        }
        a = a * a % mod;
        n >>= 1;
    }
    return ans;
}
signed main() {
    IOS
    int n,m;
    cin>>n>>m;
    vector<vector<char>> a(n+1,vector<char>(m+1));
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            cin>>a[i][j];
        }
    }
    int ans=0;
    for(int i=1;i<=n;i++)
    {
        int cnt=0;
        for(int j=1;j<=m;j++)
        {
            if(a[i][j]=='#')
            {
                cnt++;
            }
            else{
                ans+=(cnt)*(cnt+1)*(2*cnt+1)/6;
                cnt=0;
            }
        }
        ans+=(cnt)*(cnt+1)*(2*cnt+1)/6;
    }
    for(int i=1;i<=m;i++)
    {
        int cnt=0;
        for(int j=1;j<=n;j++)
        {
            if(a[j][i]=='#')
            {
                cnt++;
            }
            else{
                ans+=(cnt)*(cnt+1)*(2*cnt+1)/6;
                cnt=0;
            }
        }
        ans+=(cnt)*(cnt+1)*(2*cnt+1)/6;
    }
    cout<<ans<<endl;
    return 0;
}