本文最后更新于 937 天前,其中的信息可能已经有所发展或是发生改变。
Origional Link
- 从拿到钥匙的门开始,用其得到的钥匙遍历对应的门
- 直到钥匙为0,若共打开了3道门,则为
YES
| #include <bits/stdc++.h> |
| using namespace std; |
| |
| const int N = 10; |
| |
| void solve(){ |
| |
| int a[N]; |
| |
| int n; |
| |
| cin >> n; |
| |
| int flag = 1; |
| |
| for(int i = 1; i <= 3; i++) cin >> a[i]; |
| |
| for(int i = n; a[i] != 0; i = a[i]) flag++; |
| |
| if(flag == 3) cout << "YES" << "\n"; |
| else cout << "NO" << "\n"; |
| |
| } |
| |
| int main(){ |
| |
| int _; |
| |
| cin >> _; |
| |
| while(_--){ |
| solve(); |
| } |
| |
| return 0; |
| |
| } |
Origional Link
- 利用前缀和与后缀和预处理区间的伤害值
- 对于每个询问:l<r 为前缀,l>r 为后缀
注意:开long long
!开long long
!开long long
!
| #include <bits/stdc++.h> |
| using namespace std; |
| |
| #define int long long |
| |
| const int N = 1e6 + 10; |
| |
| int a[N]; |
| |
| int b[N],c[N]; |
| |
| void solve(){ |
| |
| int n, m; |
| |
| cin >> n >> m; |
| |
| for(int i = 1 ; i <= n ; i++){ |
| |
| cin >> a[i]; |
| |
| if(a[i] < a[i-1]){ |
| b[i] = a[i-1] - a[i]; |
| } |
| else if(a[i] > a[i-1]){ |
| c[i] = a[i] - a[i-1]; |
| } |
| |
| b[i] += b[i-1]; |
| c[i] += c[i-1]; |
| |
| } |
| |
| while(m--){ |
| |
| int l, r; |
| |
| cin >> l >> r; |
| |
| if(l < r){ |
| cout << b[r] - b[l] << "\n"; |
| } |
| else cout << c[l] - c[r] << "\n"; |
| |
| } |
| |
| } |
| |
| signed main(){ |
| |
| solve(); |
| |
| return 0; |
| |
| } |
Origional Link
- 贪心
- 设
dep
表示当前遍历到的还未配对的(
的数量,vis
表示当前遍历到的?
的数量
- 从左边向右遍历括号序列
s
dep
:若s[i] == '('
,则dep++
,若s[i] == ')'
,则dep--
vis
:若s[i] == '?'
,则vis++
,
- 在遍历过程中,
dep
的状态会影响序列的唯一性
- 若
dep < 0
,则在之前遍历的序列中,必然存在至少一个?
即(vis>0
),使得括号序列合法,且?
的状态将唯一确定,此时dep++,vis--
- 若
dep == 0 && vis == 1
,则在之前遍历的序列中,?
的状态也将唯一确定,此时dep++,vis--
- 遍历结束后,由于遍历时
dep
和vis
唯一确定的状态已经消去,故现在只剩下了还未确定唯一性状态的dep
和vis
- 若
abs(dep) == vis
,说明剩下的状态也将唯一确定并消去,该括号序列合法且唯一,反之则不符合。
| #include <bits/stdc++.h> |
| using namespace std; |
| |
| void solve(){ |
| |
| string s; |
| |
| cin >> s; |
| |
| int dep = 0, vis = 0; |
| |
| for(int i = 0 ; i < s.size() ; i++){ |
| |
| if(s[i] == '(') dep++; |
| else if(s[i] == ')'){dep--; |
| if(dep < 0){ |
| if(vis > 0)dep++, vis--; |
| else{ |
| dep = 1, vis = 0; |
| break; |
| } |
| } |
| } |
| else vis++; |
| |
| if(dep == 0 && vis == 1) dep++, vis--; |
| |
| } |
| |
| if(abs(dep) == vis) cout << "YES" << '\n'; |
| else cout << "NO" << '\n'; |
| |
| } |
| |
| int main(){ |
| |
| int _; |
| |
| cin >> _; |
| |
| while(_--){ |
| solve(); |
| } |
| |
| return 0; |
| |
| } |
- A题肥肠煎蛋,不过由于可选性的方法太多,一时间不知道选哪个最好,写的时候有点乱套
- B题居然是以Terraira为背景的,
本来还激动了一下,读懂题之后发现是前缀和,比较简单
- 但是做的时候眼瞎,没看见ai的范围,不开
long long
吃了四发WA
,活该()
- 记得开
long long
!!!
- 记得开
long long
!!!
- 记得开
long long
!!!
- C题遇到括号序列就不会,这次好好补补,贪心学不会的无力感QAQ
- 最后发现D过的居然比C多?!D好像是
st表
的模板题,还没学,等我学完之后回来复仇
- 读英文题一定要理解清楚,读假题太伤了。