当前位置:网站首页>Codeforces Global Round 19
Codeforces Global Round 19
2022-07-05 22:43:00 【eyuhaobanga】
Sign in problem , Judge whether the input sequence has been arranged
AC Code :
/* Tips: 1.int? long long? 2.don't submit wrong answer 3.figure out logic first, then start writing please 4.know about the range 5.check if you have to input t or not 6.modulo of negative numbers is not a%b, it is a%b + abs(b) */ #pragma GCC optimize(2) #pragma GCC optimize(3) #pragma GCC optimize("Ofast") #include<bits/stdc++.h> using namespace std; #define lowbit(x) ((x) & -(x)) #define endl '\n' #define IOS1 ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr); #define IOS2 ios::sync_with_stdio(0);cin.tie(0);cout.tie(0); typedef vector<int> vi; typedef vector<long long> vll; typedef vector<char> vc; typedef long long ll; template<class T> T gcd(T a, T b) { return b ? gcd(b, a % b) : a; } template<class T> T lcm(T a, T b) { return a / gcd(a, b) * b; } template<class T> T power(T a, int b) { T res = 1; for (; b; b >>= 1, a = a * a) { if (b & 1) { res = res * a; } } return res; } template <typename T> inline void read(T& x) { x = 0; int f = 1; char ch = getchar(); while (!isdigit(ch)) { if (ch == '-') f = -1; ch = getchar(); } while (isdigit(ch)) { x = x * 10 + ch - '0', ch = getchar(); } x *= f; } const int INF = 0x3f3f3f3f; const int mod = 1000000007; const double PI = acos(-1.0); const double eps = 1e-6; inline int sgn(double x) { return x < -eps ? -1 : x > eps; } void solve() { int n; cin >> n; vector<int> a(n + 5); for (int i = 0; i < n; i++) { cin >> a[i]; } if(is_sorted(a.begin(), a.begin() + n)){ cout << "NO" << endl; } else{ cout << "YES" << endl; } return; } int main() { IOS1; //IOS2; int __t = 1; cin >> __t; for (int _t = 1; _t <= __t; _t++) { solve(); } return 0; } /* */
Problem - B - Codeforces
It is known that the length used is 1 Instead of a line segment with a length of k(k>1) Its contribution will not change . Consider two situations ,1. There is 0,2. There is no 0, Because if there is no 0,mex Always equal to 0, At this time, each length is 1 The contribution of the line segment is 1,k The first contribution is k, If there is 0, that 1+mex<=1+k, But the length is 1 The line segment of contributes at least 1+k, So you can use all the length 1 Instead of the line segment of and will not reduce the contribution , Therefore, to calculate the total value, we need to calculate the length and 0 The contribution of , From mathematical knowledge, we know that the sum of all field lengths is n*(n+1)*(n+2)/6, The first i In position 0 Contribution: i*(n-i+1) (DP Good idea , Time complexity O(n))
AC Code :
/* Tips: 1.int? long long? 2.don't submit wrong answer 3.figure out logic first, then start writing please 4.know about the range 5.check if you have to input t or not 6.modulo of negative numbers is not a%b, it is a%b + abs(b) */ #pragma GCC optimize(2) #pragma GCC optimize(3) #pragma GCC optimize("Ofast") #include<bits/stdc++.h> using namespace std; #define lowbit(x) ((x) & -(x)) #define endl '\n' #define IOS1 ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr); #define IOS2 ios::sync_with_stdio(0);cin.tie(0);cout.tie(0); typedef vector<int> vi; typedef vector<long long> vll; typedef vector<char> vc; typedef long long ll; template<class T> T gcd(T a, T b) { return b ? gcd(b, a % b) : a; } template<class T> T lcm(T a, T b) { return a / gcd(a, b) * b; } template<class T> T power(T a, int b) { T res = 1; for (; b; b >>= 1, a = a * a) { if (b & 1) { res = res * a; } } return res; } template <typename T> inline void read(T& x) { x = 0; int f = 1; char ch = getchar(); while (!isdigit(ch)) { if (ch == '-') f = -1; ch = getchar(); } while (isdigit(ch)) { x = x * 10 + ch - '0', ch = getchar(); } x *= f; } const int INF = 0x3f3f3f3f; const int mod = 1000000007; const double PI = acos(-1.0); const double eps = 1e-6; inline int sgn(double x) { return x < -eps ? -1 : x > eps; } void solve() { int n; cin >> n; vector<int> a(n + 5); for (int i = 1; i <= n; i++) { cin >> a[i]; } int ans = 0; for (int i = 1; i <= n; i++) { ans += i * (n - i + 1) * (1 + (a[i] == 0)); } cout << ans << endl; return; } int main() { IOS1; //IOS2; int __t = 1; cin >> __t; for (int _t = 1; _t <= __t; _t++) { solve(); } return 0; } /* */
The meaning of the title is generally from 2 To n-1 Traverse every heap , Take two at a time , Then assign to any two , The minimum number of 2 To n-1 All the stones are allocated to 1 and n In the pile , When 2 To n-1 It's all about 1 I can't take any of them at the time of , Output -1, When n=3 And a2 When it is an odd number, no matter how you make it, the last thing left 1 You can't get all of them , Others should have a non 1 Under the circumstances , It can be proved that even numbers can be constructed continuously without appearing 1 The situation of .
AC Code :
/* Tips: 1.int? long long? 2.don't submit wrong answer 3.figure out logic first, then start writing please 4.know about the range 5.check if you have to input t or not 6.modulo of negative numbers is not a%b, it is a%b + abs(b) */ #pragma GCC optimize(2) #pragma GCC optimize(3) #pragma GCC optimize("Ofast") #include<bits/stdc++.h> using namespace std; #define lowbit(x) ((x) & -(x)) #define endl '\n' #define IOS1 ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr); #define IOS2 ios::sync_with_stdio(0);cin.tie(0);cout.tie(0); typedef vector<int> vi; typedef vector<long long> vll; typedef vector<char> vc; typedef long long ll; template<class T> T gcd(T a, T b) { return b ? gcd(b, a % b) : a; } template<class T> T lcm(T a, T b) { return a / gcd(a, b) * b; } template<class T> T power(T a, int b) { T res = 1; for (; b; b >>= 1, a = a * a) { if (b & 1) { res = res * a; } } return res; } template <typename T> inline void read(T& x) { x = 0; int f = 1; char ch = getchar(); while (!isdigit(ch)) { if (ch == '-') f = -1; ch = getchar(); } while (isdigit(ch)) { x = x * 10 + ch - '0', ch = getchar(); } x *= f; } const int INF = 0x3f3f3f3f; const int mod = 1000000007; const double PI = acos(-1.0); const double eps = 1e-6; inline int sgn(double x) { return x < -eps ? -1 : x > eps; } void solve() { int n; cin >> n; vector<int> a(n + 5); int cnt1 = 0, cnt2 = 0; for (int i = 1; i <= n; i++) { cin >> a[i]; } if (n == 3 && a[2] & 1) { cout << "-1" << endl; return; } bool ok = false; for (int i = 2; i < n; i++) { if (a[i] != 1) { ok = true; } } if (!ok) { cout << "-1" << endl; return; } long long ans = 0; for (int i = 2; i < n; i++) { ans += (a[i] + 1) / 2; } cout << ans << endl; return; } int main() { IOS1; //IOS2; int __t = 1; cin >> __t; for (int _t = 1; _t <= __t; _t++) { solve(); } return 0; } /* */
Official simplification , So the topic becomes let suma The square of +sumb The sum of the squares of is the smallest , According to the mean inequality , Must be suma and sumb The smaller the absolute value of the difference , The smaller their sum ,01 knapsack ,i Said go ai,j Before presentation i individual ai And ,dp[i][j] Before presentation i One of the suma and sumb Difference
AC Code :
/* Tips: 1.int? long long? 2.don't submit wrong answer 3.figure out logic first, then start writing please 4.know about the range 5.check if you have to input t or not 6.modulo of negative numbers is not a%b, it is a%b + abs(b) */ #pragma GCC optimize(2) #pragma GCC optimize(3) #pragma GCC optimize("Ofast") #include<bits/stdc++.h> using namespace std; #define lowbit(x) ((x) & -(x)) #define endl '\n' #define IOS1 ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr); #define IOS2 ios::sync_with_stdio(0);cin.tie(0);cout.tie(0); typedef vector<int> vi; typedef vector<long long> vll; typedef vector<char> vc; typedef long long ll; template<class T> T gcd(T a, T b) { return b ? gcd(b, a % b) : a; } template<class T> T lcm(T a, T b) { return a / gcd(a, b) * b; } template<class T> T power(T a, int b) { T res = 1; for (; b; b >>= 1, a = a * a) { if (b & 1) { res = res * a; } } return res; } template <typename T> inline void read(T& x) { x = 0; int f = 1; char ch = getchar(); while (!isdigit(ch)) { if (ch == '-') f = -1; ch = getchar(); } while (isdigit(ch)) { x = x * 10 + ch - '0', ch = getchar(); } x *= f; } const int INF = 0x3f3f3f3f; const int mod = 1000000007; const double PI = acos(-1.0); const double eps = 1e-6; inline int sgn(double x) { return x < -eps ? -1 : x > eps; } void solve() { int n; cin >> n; vector<int> a(n + 5); vector<int> b(n + 5); long long sum = 0; for (int i = 1; i <= n; i++) { cin >> a[i]; sum += a[i]; } for (int i = 1; i <= n; i++) { cin >> b[i]; sum += b[i]; } vector<vector<int>> dp(110, vector<int> (10010, INF)); dp[0][0] = 0; for (int i = 0; i <= n; i++) { for (int j = 0; j < 10010; j++) { if (j >= a[i + 1] && abs(dp[i + 1][j]) > abs(dp[i][j - a[i + 1]] + a[i + 1] - b[i + 1])) { dp[i + 1][j] = dp[i][j - a[i + 1]] + a[i + 1] - b[i + 1]; } if (j >= b[i + 1] && abs(dp[i + 1][j]) > abs(dp[i][j - b[i + 1]] + b[i + 1] - a[i + 1])) { dp[i + 1][j] = dp[i][j - b[i + 1]] + b[i + 1] - a[i + 1]; } } } int ans = INF, pos = 0; for (int j = 0; j < 10010; j++) { if (abs(dp[n][j]) < ans) { ans = abs(dp[n][j]); pos = j; } } long long res = 0; for (int i = 1; i <= n; i++) { res += (a[i] * a[i] + b[i] * b[i]) * (n - 2); } res += pos * pos + (sum - pos) * (sum - pos); cout << res << endl; return; } int main() { IOS1; //IOS2; int __t = 1; cin >> __t; for (int _t = 1; _t <= __t; _t++) { solve(); } return 0; } /* */
边栏推荐
- How to reverse a string fromCharCode? - How to reverse String. fromCharCode?
- 分布式解决方案之TCC
- FBO and RBO disappeared in webgpu
- Wonderful review of the digital Expo | highlight scientific research strength, and Zhongchuang computing power won the digital influence enterprise award
- [error record] groovy function parameter dynamic type error (guess: groovy.lang.missingmethodexception: no signature of method)
- Metaverse Ape猿界应邀出席2022·粤港澳大湾区元宇宙和web3.0主题峰会,分享猿界在Web3时代从技术到应用的文明进化历程
- 2022软件测试工程师涨薪攻略,3年如何达到30K
- Overriding equals() & hashCode() in sub classes … considering super fields
- d3dx9_ How to repair 31.dll_ d3dx9_ 31. Solution to missing DLL
- Overview of Fourier analysis
猜你喜欢
Cobaltstrike builds an intranet tunnel
Nacos 的安装与服务的注册
Interview questions for famous enterprises: Coins represent a given value
Golang writes the opening chapter of selenium framework
I closed the open source project alinesno cloud service
Event trigger requirements of the function called by the event trigger
Three "factions" in the metauniverse
50. Pow(x, n). O(logN) Sol
What if the files on the USB flash disk cannot be deleted? Win11 unable to delete U disk file solution tutorial
Technology cloud report: how many hurdles does the computing power network need to cross?
随机推荐
Binary tree (III) -- heap sort optimization, top k problem
Overview of Fourier analysis
【无标题】
344. Reverse String. Sol
Vcomp110.dll download -vcomp110 What if DLL is lost
Sub total of Pico development
[groovy] mop meta object protocol and meta programming (execute groovy methods through metamethod invoke)
请求二进制数据和base64格式数据的预览显示
Why does the C# compiler allow an explicit cast between IEnumerable&lt; T&gt; and TAlmostAnything?
EasyCVR集群部署如何解决项目中的海量视频接入与大并发需求?
Qtquick3d real time reflection
Leetcode simple question: find the nearest point with the same X or Y coordinate
Platformio create libopencm3 + FreeRTOS project
[error record] groovy function parameter dynamic type error (guess: groovy.lang.missingmethodexception: no signature of method)
[agc009e] eternal average - conclusion, DP
Postman核心功能解析-参数化和测试报告
Double pointeur de liste liée (pointeur rapide et lent, pointeur séquentiel, pointeur de tête et de queue)
从 1.5 开始搭建一个微服务框架——日志追踪 traceId
VIM tail head intercept file import
Distance entre les points et les lignes