本文最后更新于 938 天前,其中的信息可能已经有所发展或是发生改变。
Origional Link
- 给定只包含0和1的字符串a和b
- 对a进行操作:
- 将a2=min(a1,a2),并删除a1,使得a2变为新的a1
- 将a2=max(a1,a2),并删除a1,使得a2变为新的a1
- 上述操作不限次数,求最终是否可以使得a=b
| #include <bits/stdc++.h> |
| using namespace std; |
| |
| void solve(){ |
| |
| int n, m; |
| |
| cin >> n >> m; |
| |
| string a, b; |
| cin >> a >> b; |
| |
| int k = a.size() - b.size(); |
| |
| string s1 = a.substr(k + 1,b.size() - 1); |
| string s2 = b.substr(1,b.size() - 1); |
| |
| if(s1 == s2){ |
| |
| int flag = 0; |
| |
| if(a.rfind(b[0], k) != -1) flag = 1; |
| |
| if(flag) cout << "YES" << endl; |
| else cout << "NO" << endl; |
| |
| } |
| else cout << "NO" << endl; |
| |
| } |
| |
| int main(){ |
| |
| int _; |
| cin >> _; |
| while(_ --){ |
| solve(); |
| } |
| |
| |
| |
| return 0; |
| |
| } |
Origional Link
- 对于ai和固定的x
- 有可以变成任意整数的v,使得∣v−ai∣≤x
- 遍历数组a,求v最小变化的次数
- 由∣v−ai∣≤x可知ai−x≤v≤ai+x
- 故对于
a[i]
,必然存在满足∣v−ai∣≤x的区间[l,r]
,l = a[i] - x, r = a[i] + x
- 设
a[i + 1]
的区间[l',r']
,l = a[i + 1] - x, r = a[i + 1] + x
- 若
[l,r]
与[l',r']
有公共区间时,v
可以不用发生改变,并将区间更新为其公共区间
- 若
[l,r]
与[l',r']
无公共区间时,v
将发生改变,并将区间变为[l',r']
- 公共区间存在判断:
max(l,l') <= min(r,r')
说明存在公共区间
| #include <bits/stdc++.h> |
| using namespace std; |
| |
| typedef long long LL; |
| |
| void solve(){ |
| |
| LL n, x; |
| |
| cin >> n >> x; |
| |
| LL cnt = 0; |
| |
| LL t; |
| cin >> t; |
| |
| LL l = t - x, r = x + t; |
| |
| for(int i = 1; i < n; i ++){ |
| LL y; |
| cin >> y; |
| LL p1 = y - x, p2 = y + x; |
| if(max(p1,l) <= min(p2,r)){ |
| l = max(p1,l); |
| r = min(p2,r); |
| } |
| else{ |
| cnt ++; |
| l = p1; |
| r = p2; |
| } |
| |
| } |
| |
| cout << cnt << endl; |
| |
| } |
| |
| int main(){ |
| |
| int _; |
| cin >> _; |
| while(_ --){ |
| solve(); |
| } |
| |
| |
| |
| return 0; |
| |
| } |
Origional Link
- 1∼N的房屋围成一圈
- 给出初始感染病毒的房屋编号
- 每天可选择未感染的房屋进行保护,可使其永久不被感染
- 每天已感染的房屋其左右邻居都会受到感染
- 求最优策略下,最终感染的房屋数量
- 贪心
- 每次选择未感染的最长区间进行保护
- 对于被保护的区间
[l,r]
:
- 经过第一天:
- 保护
[l,r]
的一个端点,设保护a[l]
a[l]
不会感染,a[r]
会被感染
- 其他所有未受到保护的区间
[l',r']
里,a[l']
和a[r']
被感染
- 经过第二天:
- 保护
[l,r]
的另一个端点a[r]
,由于第一天a[r]
被感染,故只能保护a[r - 1]
- 其他所有未受到保护的区间
[l',r']
里,a[l' + 1]
和a[r' - 1]
被感染
- 即对于选择保护的区间
[l,r]
,a[r]
被感染,我们只能保护到[l,r - 1]
这一段,且其余所有未受到保护的区间[l',r']
里a[l'],a[r'],a[l' + 1],a[r' - 1]
受到感染,感染后的区间变为[l' + 2, r' - 2]
- 综上可知,我们优先保护最长的未被感染的区间,即可实现最优策略
- 由于选择保护的区间端点可以任选,故只需要考虑区间长度,不需要维护额外的信息
- 注意不要忽略首尾相连的区间
| #include <bits/stdc++.h> |
| using namespace std; |
| |
| void solve(){ |
| |
| int n, m; |
| |
| cin >> n >> m; |
| |
| vector<int> vis; |
| |
| for(int i = 0; i < m; i ++){ |
| int x; |
| cin >> x; |
| vis.push_back(x); |
| } |
| |
| sort(vis.begin(),vis.end()); |
| |
| priority_queue<int> st; |
| |
| st.push(n - vis.back() + vis[0] - 1); |
| |
| for(int i = 0; i + 1 < vis.size(); i ++){ |
| st.push(vis[i + 1] - vis[i] - 1); |
| } |
| |
| int cnt = 0; |
| |
| for(int i = 0; i + 1 > 0; i ++){ |
| if(!st.empty() && st.top() - i * 4 > 0){ |
| int k = st.top() - i * 4; |
| if(k > 1) k --; |
| cnt += k; |
| st.pop(); |
| } |
| else break; |
| } |
| |
| cout << n - cnt << endl; |
| |
| } |
| |
| int main(){ |
| |
| int _; |
| cin >> _; |
| while(_ --){ |
| solve(); |
| } |
| |
| |
| |
| return 0; |
| |
| } |
Origional Link
- 对于一个长度为m的数组b,构造n个与b相同的的数组c
- 对于数组ct(1≤t≤n)现有操作:
- 操作1:首先将ct[i]=ct[i]−1,ct[j]=ct[j]−1,然后将ct[i−1]=ct[i−1]+1,ct[j+1]=ct[j+1]+1
- 操作2:首先将ct[i]=ct[i]−1,ct[j]=ct[j]−1,然后将ct[i−1]=ct[i−1]+1,ct[j+2]=ct[j+2]+1
- 选择某一个数k(1≤k≤n),使得ck为特别数组
- 非特别数组ci(1≤i≤n,i=k)只能执行操作1若干次
- 特别数组ck(1≤k≤n)只能执行操作2若干次
- 给出这些操作后的数组c,找出其中的特别数组的编号k,及其执行了多少次操作2
对于ct(1≤t≤n)(一)对于对于ci−1,ci,cj,cj+1,可以得到ci−1×(i−1)+ci×i+cj×j+cj+1×(j+1)化简得:i×(ci−1+ci)+j×(cj+cj+1)−ci−1+cj+1①ci−1,ci,cj,cj+1执行操作1:(ci−1+1)×(i−1)+(ci−1)×i+(cj−1)×j+(cj+1+1)×(j+1)化简得:i×(ci−1+ci)+j×(cj+cj+1)−ci−1+cj+1②可知①=②,即操作1不会改变ci×i的和(二)对于对于ci−1,ci,cj,cj+1,cj+2,可以得到ci−1×(i−1)+ci×i+cj×j+cj+1×(j+1)+cj+2×(j+2)化简得:i×(ci−1+ci)+j×(cj+cj+1+cj+2)−ci−1+cj+1+2×cj+2③ci−1,ci,cj,cj+1,cj+2执行操作2:(ci−1+1)×(i−1)+(ci−1)×i+(cj−1)×j+cj+1×(j+1)+(cj+2+1)×(j+2)化简得:i×(ci−1+ci)+j×(cj+cj+1+cj+2)−ci−1+cj+1+2×cj+2+1④可知③=④+1,即操作1会改变ci×i的和,使其加1综上可知:对每一个数组c,求Sf=∑ci×i与其他数组c的Sf不同的数组即为特别数组,记为Sp其操作2的次数为Sp−Sf
| #include <bits/stdc++.h> |
| using namespace std; |
| |
| typedef long long LL; |
| |
| void solve(){ |
| |
| LL n, m; |
| |
| cin >> n >> m; |
| |
| LL S1 = -1, S2 = -1; |
| LL cnt1 = 0, cnt2 = 0; |
| LL p1, p2; |
| |
| for(LL i = 1; i <= n; i ++){ |
| |
| LL sum = 0; |
| |
| for(LL j = 1; j <= m; j ++){ |
| LL x; |
| cin >> x; |
| sum += x * j; |
| } |
| |
| if(S1 == -1){ |
| S1 = sum; |
| p1 = i; |
| } |
| else if(S1 != -1 && S2 == -1 && S1 != sum){ |
| S2 = sum; |
| p2 = i; |
| } |
| |
| if(S1 == sum) cnt1 ++; |
| if(S2 == sum) cnt2 ++; |
| |
| } |
| |
| if(cnt1 > cnt2){ |
| cout << p2 << " " << S2 - S1 << endl; |
| } |
| else cout << p1 << " " << S1 - S2 << endl; |
| |
| } |
| |
| int main(){ |
| |
| LL _; |
| cin >> _; |
| while(_ --){ |
| solve(); |
| } |
| |
| |
| |
| return 0; |
| |
| } |
- A题一开始没找到规律,找到规律后居然没有把错思路的代码删掉,狠狠的吃
WA
的铁头娃
- B题读懂题意就很简单了,没什么好说的,就是判断公共区间
- C题一直在想着怎么维护端点的信息,最后发现根本不需要,只要长度就行了QAQ
- D题没时间了,太抽象了也看不懂,补题看题解发现证明的想法实在是妙极了,根本想不到
- 最后还是没能上绿,
我是废物