总
补题
牛客
训4
https://ac.nowcoder.com/acm/contest/120564#question
A
双重循环判断有多少个数小于等于ai
if (cnt * 10 >= (n - 1) * 8) sum += a[i];
B
用前缀和记录第i个首领在位第1年是公元几年
然后每次询问时b[x]+y-1
I
手动模拟会发现 多种颜色筹码下注会使得期望进一步降低
于是所有筹码都不下注是最优解
输出"####"即可
C
构造的序列最后就是格雷码
格雷码：相邻两个数字在二进制中有且仅有一位不同
H
维护受单点更新影响的少量状态，也就是说维护的是每个格子作为中心时、曼哈顿距离不超过2的13个格子的总和
预先计算每个格子f[i][j]（以该格子为中心、曼哈顿距离≤2 的菱形区域之和），当某个格点(x,y)增加z 时，仅会影响满足∣i−x∣+∣j−y∣≤2 的至多13个中心格子的 f值，逐个把这 13 个f加上z并更新全局最大值即可
点击查看代码
#include<bits/stdc++.h>
using namespace std;#define ll long long
#define endl '\n'
const ll modd=998244353;const ll N=5e2+10;
ll a[N][N];
ll f[N][N];ll cnt;
ll ddx[15],ddy[15];void solve()
{ll n,m,q;cin>>n>>m>>q;for(ll i=1;i<=n;++i){for(ll j=1;j<=m;++j){cin>>a[i][j];}}for(ll i=-2;i<=2;++i){for(ll j=-2;j<=2;++j){if(abs(i)+abs(j)<=2){ddx[cnt]=i;ddy[cnt]=j;cnt++;}}}ll maxval=-1;ll maxi=1,maxj=1;for(ll i=1;i<=n;++i){for(ll j=1;j<=m;++j){ll sum=0;for(ll k=0;k<cnt;++k){ll xx=i+ddx[k];ll yy=j+ddy[k];if(xx>=1&&xx<=n&&yy>=1&&yy<=m){sum+=a[xx][yy];}}f[i][j]=sum;if(sum>maxval){maxval=sum;maxi=i;maxj=j;}}}for(ll i=0;i<q;++i){ll x,y,z;cin>>x>>y>>z;a[x][y]+=z;for(ll i=0;i<cnt;++i){ll xx=x+ddx[i];ll yy=y+ddy[i];if(xx>=1&&xx<=n&&yy>=1&&yy<=m){f[xx][yy]+=z;if(f[xx][yy]>maxval){maxval=f[xx][yy];maxi=xx;maxj=yy;}}}cout<<maxi<<" "<<maxj<<'\n';}
}int main()
{ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);ll lll=1;
// cin>>lll;while(lll--){solve();
// if(lll) cout<<'\n';}return 0;
}