A Ahahahahahahahaha standard input/output 1 s, 256 MB Submit Add to favourites x13926
题意给你一个长度为n的01数组，最后要变成一个奇数项之和 等于 减偶数项之和的数组， 你最多可以抹去n/2个 初始数组的元素， 输出符合条件的数组长度 和 数组
因为这个数组只有01， 所以可以先计算0 1的个数，如果0的个数大于等于n/2 那么直接输出所有0就好了， 如果小于的话 输出最大的偶数1个数即可
B Big Vova standard input/output 1 s, 256 MB Submit Add to favourites x10875
ci=GCD(b1,…,bi) 因为 ci= GCD(GCD(b1,…,bi-1), bi) 所以 直接暴力枚举即可 O(n2logn)
C Chocolate Bunny standard input/output 1 s, 256 MB Submit Add to favourites x7116
题目题意 每次输入n 然后可以最多进行2*n次询问 最后需要猜出n个数组的每个元素并输出， （询问的方式是 输入两个数组下标 i j 然后会给出a[i] % a[j]的值），
假设两个数x y( x>y) 那么 x%y<y%x ， 因为 x%y<y y%x=y 所以x%y<y%x， (或者随便写两个数 模拟一下就知道了
根据这个原理 我们可以每次询问两个下标 i、j 和 j、i 就可以确定更小的数的下标 然后不断重复这个过程最多2*(n-1)次就可以确认 n-1 个数， 最后剩下一个未知的数就是最大的 也就是 n
D Discrete Centrifugal Jumps standard input/output 2 s, 256 MB Submit Add to favourites x2885
题目题意 给你n个数 代表n座山峰， 然后balabalbala 你需要从第一座山峰跳到最后一座山峰 然后可以有三种跳跃方式（如下图
1、直接跳到下一座 2、跳到右边最近的大于本山峰高度的山峰 3、跳到右边最近的小于本山峰高度的山峰
可以用四个数组分别记录下每座山峰的右边（左边）的最近大于（小于） 本山峰的山峰 下标
然后把每座山峰 当成一个顶点 能到达的下一座山峰作为有向边 建图， 然后用dp计算 到达每个点 的最小步数， 最后输出dp[n-1]即可 O(n)
#include<bits/stdc++.h> using namespace std; #define _for(i,a,b) for(int i = (a); i < (b); i++) #define _rep(i,a,b) for(int i = (a); i <= (b); i++) #define all(v) (v).begin(), (v).end() #define ll long long #define pi 3.1415926 #define PI acos(-1.0)
1 void taskA() {
2 int t; cin >> t;
3 while(t--) {
4 int cnt = 0;
5 int n; cin >> n;
6 _for(i,0,n)
7 {
8 int x; cin >> x;
9 if(!x) cnt++;
10 }
11 if(2*cnt >= n) {
12 cout << cnt << "\n";
13 _for(i,0,cnt) cout << "0 ";
14 cout << "\n";
15 } else {
16 int k = n/2;
17 if(k&1) k++;
18 cout << k << "\n";
19 _for(i,0,k) cout << "1 ";
20 cout << "\n";
21 }
22 }
23 return;
24 }
View A Code
1 int gcd(int a, int b) {return !b?a:gcd(b, a%b);}
2 void taskB() {
3 int t; cin >> t;
4 while(t--) {
5 int n; cin >> n;
6 vector<int> a(n);
7 _for(i,0,n) cin >> a[i];
8 int g = 0;
9 _for(i,0,n) {
10 int g1 = 0, k = i;
11 _for(j,i,n) {
12 int tmp = gcd(g, a[j]);
13 if(g1 < tmp)
14 k = j, g1 = tmp;
15 }
16 g = g1;
17 swap(a[k], a[i]);
18 } _for(i,0,n) cout << a[i] << " "; cout << "\n\n";
19 } return;
20 }
View B Code
1 int ask(int x, int y) {
2 cout << "? " << x+1 << " " << y+1 << "\n";
3 int z; cin >> z;
4 return z;
5 }//1 3 2
6 void taskC() {
7 //ios::sync_with_stdio(false), cin.tie(nullptr);
8 int n; cin >> n;
9 int mx = 0;
10 vector<int> ans(n, 0);
11 _for(i,1,n) {
12 int a = ask(mx, i);
13 int b = ask(i, mx);
14 if(a > b) ans[mx] = a, mx = i;
15 else ans[i] = b;
16 }
17 ans[mx] = n;
18 cout << "! ";
19 _for(i,0,n) cout << ans[i] << " ";
20 cout << "\n";
21 //cout.flush();
22 return;
23 }
View C Code
1 const int N = 3e5+100;
2 int lge[N], lle[N], rge[N], rle[N], dp[N], n;
3 vector<int > jump[N];
4
5 void taskD() {
6 while(cin >> n and n) {
7 vector<int> a(n);
8 _for(i,0,n) {
9 cin >> a[i];
10 dp[i] = N;
11 }
12 vector<pair<int, int> > st;
13 _for(i,0,n) {
14 while(!st.empty() and st.back().first < a[i]) st.pop_back();
15 lge[i] = (!st.empty() ? st.back().second: -1);
16 st.push_back({a[i], i});
17 }
18 st.clear();
19 _for(i,0,n) {
20 while(!st.empty() and st.back().first > a[i]) st.pop_back();
21 lle[i] = (!st.empty() ? st.back().second: -1);
22 st.push_back({a[i], i});
23 }
24 st.clear();
25 for(int i = n-1; i >= 0; i--) {
26 while(!st.empty() and st.back().first < a[i]) st.pop_back();
27 rge[i] = (!st.empty() ? st.back().second: -1);
28 st.push_back({a[i], i});
29 }
30 st.clear();
31 for(int i = n-1; i >= 0; i--) {
32 while(!st.empty() and st.back().first > a[i]) st.pop_back();
33 rle[i] = (!st.empty() ? st.back().second: -1);
34 st.push_back({a[i], i});
35 }
36 _for(i,0,n) {
37 if(rle[i] != -1) jump[i].push_back(rle[i]);
38 if(rge[i] != -1) jump[i].push_back(rge[i]);
39 if(lle[i] != -1) jump[lle[i]].push_back(i);
40 if(lge[i] != -1) jump[lge[i]].push_back(i);
41 }
42 dp[0] = 0;
43 _for(i,0,n) {
44 for(auto to : jump[i])
45 dp[to] = min(dp[to], dp[i]+1);
46 }
47 cout << dp[n-1] << "\n";
48 }
49 return;
50 }
View D Code
int main() {
ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
taskD();
return 0;
}