【USACO23DEC】Cu 复盘
我先用了一个号打，然后是 T1 TLE * 4，T2 AC，T3 WA * 2。然后后面开了一个号调了一些，喜提阿克。
T1：
首先我们知道，对于 \(a_1\) 每一次是最先吃糖果的。
所以必然有两个情况：
- 全部给他吃了
- 吃了一些
首先情况一，我们可以直接特判掉。
剩下情况二，吃了一些没吃完代表：吃了自己的高度，相当于身高乘2。于是我们只需要进行 \(\log 10^9\) 次。然后后面直接 \(O(n)\) 暴力。时间复杂度 \(O(n \log 10^9)\)。
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5+5;
#define int long long
int n,m;
int a[N],b[N];
void solve(){
cin >> n >> m;
for(int i = 1;i <= n;i++)
cin >> a[i];
for(int i = 1;i <= m;i++)
cin >> b[i];
for(int i = 1;i <= m;i++){
if(b[i] <= a[1]){
a[1]+=b[i];
continue;
}
int tmp = 1;
for(int j = 1;j <= n;j++)
if(a[j] >= tmp && tmp <= b[i]){
int t=a[j]+1;
a[j] += min(a[j]-tmp+1,b[i]-tmp+1);
tmp = t;
}
}
for(int i = 1;i <= n;i++)
cout<<a[i]<<endl;
}
signed main(){
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
solve();
return 0;
}
T2
这是我第一次唯一场切的一道题：
首先我在这题上写了三份代码。原因是我一开始想到分讨，写复杂了。
根据贪心策略，很容易知道：天数越大，奶牛数少，所以我们让天数最多。
然后我们会发现头尾的那个区间如果是 \(x\)，那么相当于一个 \(2 \times x - 1\) 的一个普通区间（就是在中间的那种区间）。
所以我们根据处理后的每一个区间的长度进行计算，然后得到了每一个区间最小的天数，也就是我们能够放最多的天数。
所以按照这个去模拟即可。
#include <bits/stdc++.h>
using namespace std;
#define int long long
int n;
int xx=-1,yy=-1;
string s;
vector<pair<int,bool> > v;
int res,ok=1,cnt=0;
int minn = 1e9;
void solve(){
cin >> n >> s;
s = ' '+s;
for(int i = 1;i <= n;i++){
if(s[i]=='0'){
if(res)v.push_back({res,ok});
ok=0;
res=0;
}else if(s[i]=='1'){
res++;cnt++;
}
}
if(res) v.push_back({res,1});
int min2=1e9;
for(auto it:v){
if(it.second == 0)min2 = min(min2,it.first);
else{
min2 = min(min2,it.first * 2-1);
if(xx == -1)
xx = it.first;
else
yy = it.first;
}
}
minn=(min2+1)/2;
int res=0;
for(auto it:v){
if(it.first % (minn * 2 - 1) == 0) res+=it.first / (minn * 2 - 1);
else res+=it.first / (minn * 2 - 1) + 1;
}
cout<<res;
}
signed main(){
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
solve();
return 0;
}
T3
高级的说：解个不等式，低级的说：前缀和。
首先，我们先将所有 \(a\) 变换位置到最终应该在的位置。
然后，我们可以通过 \(a_i\) 和 \(a_{i-1}\) 的高度差和速度差，算出来他们之间还需要多久可以符合要求，或者是多久就不符合要求了。拿出草稿纸，自己列举四种情况分别讨论。
如果这个点开始合法，那么在这里进行标记，如果这里开始不合法，也搞一个标记。最后一遍前缀和，结束。
我被这道题卡了很久的问题是一些细节没有处理好。一些边界少加一，多加一的。随后在自己手搓 hack 下，终于过掉啦啊。
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 2e5+5;
int n,t[N];
struct node{
int h,a;
}a[N],c[N];
bool cmp(pair<int,bool> a,pair<int,bool> b){
if(a.first == b.first)
return a.second > b.second;
return a.first < b.first;
}
bool check(){
for(int i = 2;i <= n;i++) if(a[i].h<=a[i-1].h) return false;
return true;
}
vector<pair<int,bool> > v;
bool solve(){
v.clear();
//1为开始，0为结束。
cin >> n;
for(int i = 1;i <= n;i++) {
cin >> a[i].h;
}
for(int i = 1;i <= n;i++) {
cin >> a[i].a;
}
for(int i = 1;i <= n;i++) {
cin >> t[i];
}
if(n==1){
cout<<0<<endl;
return true;
}
for(int i = 1;i <= n;i++){
c[n-t[i]] = a[i];
}
for(int i = 1;i <= n;i++){
a[i] = c[i];
}
if(check()){
cout<<0<<endl;
return true;
}
int res=0;
for(int i = 2;i <= n;i++){
if(a[i-1].h > a[i].h) {
if(a[i].a <= a[i-1].a) {
return false;
}
v.push_back({((a[i-1].h - a[i].h) / (a[i].a-a[i-1].a) + 1),1});
}else if(a[i-1].h < a[i].h){
if(a[i].a >= a[i-1].a) v.push_back({0,1});
else {
v.push_back({(a[i].h - a[i-1].h) % (a[i-1].a-a[i].a) == 0?(a[i].h - a[i-1].h) / (a[i-1].a-a[i].a):((a[i].h - a[i-1].h) / (a[i-1].a-a[i].a)+1),0});
res++;
}
}else{
if(a[i].a > a[i-1].a) v.push_back({0,1});
else return false;
}
}
sort(v.begin(),v.end(),cmp);
// for(auto it:v){
// cout<<it.first<<" "<<it.second<<endl;
// }
for(int it=0;it < v.size();it++){
if(v[it].second == 1)
res++;
else
res--;
if(res == n-1 && v[it+1].first != v[it].first) {
cout<<v[it].first<<endl;
return true;
}
}
return false;
}
signed main(){
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int T;
cin >> T;
while(T--){
if(!solve()) cout<<-1<<endl;
}
return 0;
}