Contest 179 F.Simplified Reversi"/>
AtCoder Beginner Contest 179 F.Simplified Reversi
AtCoder Beginner Contest 179 F.Simplified Reversi
题目链接
非常有趣的思维题~
假设黑色区域宽为 x x x,长为 y y y,我们考虑一种修改,比如 1 , k 1,k 1,k,此时不难发现修改后对 [ k + 1 , y ] [k+1,y] [k+1,y] 的 1 1 1 操作,都是固定的减去 x x x,所以这是一种典型的缩小策略,每操作一次都将黑色区域的长宽进行缩小,并用数组记录减少的黑色方块数即可,AC代码如下:
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=2e5+5;
int n,x,y,q,op,k,r[N],c[N];
int main(){cin>>n>>q;x=y=n;ll ans=(n-2LL)*(n-2LL);while(q--){cin>>op>>k;if(op==1) {if (k < y) {ans -= x - 2;while (y > k) c[y--] = x - 2;} else ans -= c[k];}else{if (k < x) {ans -= y - 2;while (x > k) r[x--] = y - 2;} else ans -= r[k];}}cout<<ans;return 0;
}
更多推荐
AtCoder Beginner Contest 179 F.Simplified Reversi
发布评论