当前栏目
【每日一题】Codeforce | Adjustment Office
题目描述
Garrison and Anderson are working in a company named “Adjustment Office”. In competing companies workers change the reality, in this company they try to predict the future.
They are given a big square board n × n. Initially in each cell (x, y) of this board the value of x + y is written (1 ≤ x, y ≤ n). They know that in the future there will be two types of queries on the board:
“R r” — sum up all values in row r, print the result and set all values in row r to zero;
“C c” — sum up all values in column c, print the result and set all values in column c to zero.
They have predicted what queries and results there will be. They need to ensure that they have correctly predicted the results. Help them by computing the results of the queries.
输入描述:
The first line of the input contains two integers n and q (1 ≤ n ≤ 106, 1 ≤ q ≤ 105) — the size of the square and the number of queries.
Each of the next q lines contains the description of the query. Each query is either “R r” (1 ≤ r ≤ n) or “C c” (1 ≤ c ≤ n).
输出描述:
The output file shall contain q lines. The i-th line shall contain one integer — the result of the i-th query.
示例1
输入
3 7
R 2
C 3
R 2
R 1
C 2
C 1
R 3
输出
12
10
0
5
5
4
0
思路
简单地说 ,就是 给出一个 n*n 的矩阵,且 a[x][y] 的值为 x + y,每次可以查询行 or 列。每次查询的时候先输出 查询的行 or 列的和,然后把这行/列的值全部置为 0,要求输出每次查询的结果。
可以通过简单推导发现,该矩阵的每一行或者每一列都是等差数列;而由于其求出每一行 / 每一列的和之后,都会清零该行/列,所以可以用数组去标记即可。
然后考虑之前删除列操作的累积效果,用sum_r 、sum_c、cnt_r、cnt_c分别表示 行的和、列的和、删去的行数、删去的列数;那么通过对矩阵的模拟,可以推导出为
该行总和 = 该行之和 + 该行中被清零的列数
该列总和 = 该列之和 + 该列中被清零的行数
等差数列的和减去累积的影响输出即可,但要记得更新sum_r 、sum_c、cnt_r、cnt_c的值。
AC代码
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e6 + 10;
ll n, m, x;
ll sum_r , sum_c, cnt_r , cnt_c ;
char op;
bool r[N], c[N];
int main()
{
scanf("%lld%lld", &n, &m);
cnt_r = n, cnt_c = n;
sum_r = sum_c = (1 + n) * n / 2;
while (m--)
{
scanf(" %c%lld", &op, &x);
if (op == 'R') // 操作对象为行时
{
if (r[x]) //该行如果被清零,则直接输出 0 ;
{
puts("0");
continue;
}
r[x] = true; // 标记该行已被清零
sum_c -= x; // 列的和减去x;
cnt_r--; // 行的数减去1;
printf("%lld
", cnt_c * x + sum_r);
}
else // 操作对象为列时
{
if (c[x]) //该列如果被清零,则直接输出 0 ;
{
puts("0");
continue;
}
c[x] = true; // 标记该列已被清零
sum_r -= x; // 行的和减去x;
cnt_c--; // 列的数减去1;
printf("%lld
", cnt_r * x + sum_c);
}
}
return 0;
}
相关文章
- 前端面试 【JavaScript】— typeof 是否能正确判断类型?
- 前端面试 【JavaScript】— instanceof 能否判断基本数据类型?
- 前端面试 【JavaScript】— 能不能手动实现一下 instanceof 的功能?
- 前端面试 【JavaScript】— Object.is和=== 有什么区别?
- 前端面试 【JavaScript】— JS中类型转换有哪几种?
- 前端面试 【JavaScript】— == 和 ===有什么区别?
- 前端面试 【JavaScript】— 对象转原始类型是根据什么流程运行的?
- JavaScript 的 parseInt() 函数
- javascript实现两个数字进行组合
- JS监听键盘按键
- 大前端开发中的路由管理之五:Flutter篇
- Javascript的DOM操作
- 在Vue项目中使用WebSocket技术
- 新手向:前端程序员必学基本技能——调试JS代码
- React 毁了 Web 开发!
- 「JS 逆向百例」cnki 学术翻译 AES 加密分析
- 商标注册域名后缀用什么?商标和域名有哪些区别?
- 网站建设流程是怎样的?需要看重哪些细节?
- 网站域名商标注册流程是什么?网站域名商标有什么用?
- 如何建设一个实用性强的网站 网站上线后如何运营