当前位置:网站首页>Sum of three terms (construction)
Sum of three terms (construction)
2022-07-05 06:16:00 【whitewall_ nine】
https://atcoder.jp/contests/arc135/tasks
#include<iostream>
#include<map>
#include<cstring>
using namespace std;
#define rep(i,l,r) for(int i=(l);i<=(r);i++)
#define per(i,l,r) for(int i=(l);i>=(r);i--)
#define ll long long
#define pii pair<int, int>
#define mset(s,t) memset(s,t,sizeof(t))
#define mcpy(s,t) memcpy(s,t,sizeof(t))
#define fir first
#define pb push_back
#define sec second
#define sortall(x) sort((x).begin(),(x).end())
inline int read () {
int x = 0, f = 0;
char ch = getchar();
while (!isdigit(ch)) f |= (ch=='-'),ch= getchar();
while (isdigit(ch)) x = x * 10 + ch - '0', ch = getchar();
return f?-x:x;
}
template<typename T> void print(T x) {
if (x < 0) putchar('-'), x = -x;
if (x >= 10) print(x/10);
putchar(x % 10 + '0');
}
const int mod = 998244353;
const int N = 3e5 + 10;
int a[N];
int s[N];
int n;
void solve() {
cin >> n;
for (int i = 0; i< n; i ++) cin >> a[i];
int minvy = 0, minvx = 0;
// Negative numbers need not be considered , Because he was a positive number , It must be greater than or equal to 0 Conditions , Then we just need to find the smallest negative number
int maxx = 0x3f3f3f3f;
for (int i = 2; i< n + 2; i ++) {
s[i] = a[i - 2] - s[i - 1] - s[i - 2];
if (i % 3 == 0) {
minvy = max (minvy, -s[i]);
}
else if (i % 3 == 1) {
minvx = max(minvx, -s[i]);
}
else {
maxx = min(maxx, s[i]);
}
}
if (minvy + minvx > maxx) {
puts("No");
return ;
}
puts("Yes");
s[0] = minvy, s[1] = minvx;
for (int i = 2; i < n + 2; i ++)
s[i] = a[i - 2] - s[i - 1] - s[i - 2];
for (int i = 0; i < n + 2; i ++)
cout << s[i] << " \n"[i == n + 1];
}
int main () {
int t;
t = 1;
while (t --) solve();
return 0;
}
This problem is solved by finding the boundary range and then constructing a feasible solution . By simplifying the formula You can find i % 3 == 0 s[i] = x +a i % 3 == 1 s[i] = x + b i % 3== 2 s[i] = x - a - b We need to find out whether the limit conditions are feasible To this end, we construct c1, c2, c3 c1 <= a c2 <= b a + b <=c3 c1 + c2<= a + b <= c3 Maximum left , Take the minimum on the right and judge whether it meets the size relationship to judge whether it is feasible . If it is satisfied, just substitute the value directly
边栏推荐
- 多屏电脑截屏会把多屏连着截下来,而不是只截当前屏
- Sword finger offer II 058: schedule
- Leetcode-6110: number of incremental paths in the grid graph
- leetcode-31:下一个排列
- Daily question 1342 Number of operations to change the number to 0
- 6. Logistic model
- 1041 Be Unique
- 1040 Longest Symmetric String
- Error ora-28547 or ora-03135 when Navicat connects to Oracle Database
- SQLMAP使用教程(二)实战技巧一
猜你喜欢
Network security skills competition in Secondary Vocational Schools -- a tutorial article on middleware penetration testing in Guangxi regional competition
MySQL advanced part 1: stored procedures and functions
Data visualization chart summary (II)
Error ora-28547 or ora-03135 when Navicat connects to Oracle Database
1.14 - 流水线
Erreur de connexion Navicat à la base de données Oracle Ora - 28547 ou Ora - 03135
数据可视化图表总结(二)
Appium自动化测试基础 — Appium测试环境搭建总结
LaMDA 不可能觉醒吗?
Smart construction site "hydropower energy consumption online monitoring system"
随机推荐
LeetCode 0108. Convert an ordered array into a binary search tree - the median of the array is the root, and the left and right of the median are the left and right subtrees respectively
Operator priority, one catch, no doubt
1.15 - 输入输出系统
Dynamic planning solution ideas and summary (30000 words)
Smart construction site "hydropower energy consumption online monitoring system"
liunx启动redis
LeetCode 0108.将有序数组转换为二叉搜索树 - 数组中值为根,中值左右分别为左右子树
Appium automation test foundation - Summary of appium test environment construction
Leetcode-1200: minimum absolute difference
Basic explanation of typescript
【Rust 笔记】16-输入与输出(上)
Daily question 2006 Number of pairs whose absolute value of difference is k
LeetCode 0107. Sequence traversal of binary tree II - another method
Arduino 控制的 RGB LED 无限镜
RGB LED infinite mirror controlled by Arduino
6. Logistic model
Daily question 1984 Minimum difference in student scores
SPI details
1040 Longest Symmetric String
1.13 - RISC/CISC