2018 ICPC 沈阳 G.Best ACMer Solves the Hardest Problem（预处理 思维）

题目链接：https://nanti.jisuanke.com/t/A2168

分析

这题关键在怎么将 k 拆分成两个可以开方的数，可以先预处理出可能的对数，然后直接调用，同时一定要注意越界的问题。

代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;const ll mod = 6000;
int n,m,t;
map<pair<int,int>,int> mp;
ll ans;
vector<pair<int,int> > g[10000007];bool check(int x,int y)
{
    if(x <= 6000 && x > 0 && y > 0 && y <= 6000) return 1;return 0;
}void init()
{
    for(int i=0;i<=6000;i++){
    for(int j=0;j<=6000;j++){
    if(i * i + j * j > 1e7) break;g[i * i + j * j].push_back({
    i, j});}}
}int main()
{
    init();scanf("%d",&t);for(int T=1;T<=t;T++){
    mp.clear();ans = 0;scanf("%d%d",&n,&m);for(int i=1;i<=n;i++){
    int x,y,w;scanf("%d%d%d",&x,&y,&w);mp[{
    x, y}] = w;}printf("Case #%d:\n",T);while(m--){
    int op,x,y,w,k;scanf("%d%d%d",&op,&x,&y);x = (x + ans) % mod + 1;y = (y + ans) % mod + 1;if(op == 1){
    scanf("%d",&w);mp[{
    x, y}] = w;}if(op == 2){
    mp[{
    x, y}] = 0;}if(op == 3){
    scanf("%d%d",&k,&w);if(k == 0){
    mp[{
    x, y}] += w;continue;}for(int i=0;i<g[k].size();i++){
    int t1 = g[k][i].first;int t2 = g[k][i].second;if(t1 == 0){
    if(check(x - t1, y + t2) && mp[{
    x - t1, y + t2}] > 0) mp[{
    x - t1, y + t2}] += w;if(check(x - t1, y - t2) && mp[{
    x - t1, y - t2}] > 0) mp[{
    x - t1, y - t2}] += w;}else if(t2 == 0){
    if(check(x + t1, y + t2) && mp[{
    x + t1, y + t2}] > 0) mp[{
    x + t1, y + t2}] += w;if(check(x - t1, y + t2) && mp[{
    x - t1, y + t2}] > 0) mp[{
    x - t1, y + t2}] += w;}else{
    if(check(x + t1, y + t2) && mp[{
    x + t1, y + t2}] > 0) mp[{
    x + t1, y + t2}] += w;if(check(x - t1, y + t2) && mp[{
    x - t1, y + t2}] > 0) mp[{
    x - t1, y + t2}] += w;if(check(x + t1, y - t2) && mp[{
    x + t1, y - t2}] > 0) mp[{
    x + t1, y - t2}] += w;if(check(x - t1, y - t2) && mp[{
    x - t1, y - t2}] > 0) mp[{
    x - t1, y - t2}] += w;}}}if(op == 4){
    ans = 0;scanf("%d",&k);if(k == 0){
    printf("%lld\n",mp[{
    x, y}]);ans = mp[{
    x, y}];continue;}for(int i=0;i<g[k].size();i++){
    int t1 = g[k][i].first;int t2 = g[k][i].second;if(t1 == 0){
    if(check(x - t1, y + t2) && mp[{
    x - t1, y + t2}] > 0) ans += mp[{
    x - t1, y + t2}];if(check(x - t1, y - t2) && mp[{
    x - t1, y - t2}] > 0) ans += mp[{
    x - t1, y - t2}];}else if(t2 == 0){
    if(check(x + t1, y + t2) && mp[{
    x + t1, y + t2}] > 0) ans += mp[{
    x + t1, y + t2}];if(check(x - t1, y + t2) && mp[{
    x - t1, y + t2}] > 0) ans += mp[{
    x - t1, y + t2}];}else{
    if(check(x - t1, y + t2) && mp[{
    x - t1, y + t2}] > 0) ans += mp[{
    x - t1, y + t2}];if(check(x - t1, y - t2) && mp[{
    x - t1, y - t2}] > 0) ans += mp[{
    x - t1, y - t2}];if(check(x + t1, y - t2) && mp[{
    x + t1, y - t2}] > 0) ans += mp[{
    x + t1, y - t2}];if(check(x + t1, y + t2) && mp[{
    x + t1, y + t2}] > 0) ans += mp[{
    x + t1, y + t2}];}}printf("%lld\n",ans);}}}return 0;
}