USACO 2024 Open Bronze铜组题解

迟到了一个月的题解......

Logical Moos:

啊这题放在铜组T1雀食有点BT......

首先，我们关注l前第一和r最后那两组。如果这俩有一个是true，那答案肯定也是true。

否则，在l和r外边的都是false。那我们就只用仔细看l和r中间的玩意儿。对于l和r中间的每一组，只要第一组和最后一组都是false，那结果肯定也是false。

所以：如果换掉的对最后结果木有影响，那就不管；如果有，就换。

对于true的查询，我们必须再次检查该段是否包含l这组的第一个false，以及r这组的最后一个false。如果不是，那么即使我们将其余部分替换为true，结果也将还是false。

对于false的查询，如果输入是false，结果将为false。

我们每次只需记录每组中最左的false和最右的false，复杂度 $\Theta (N+Q)$ 。

#include <bits/stdc++.h>
using namespace std;
string expr[maxn];
int group[maxn];
int main(){int N,Q;cin>>N>>Q;for(int i=0;i<N;i++)cin>>expr[i];int idx=0;for(int i=0;i<N;i++){if(expr[i]=="or")idx++;else{if(i%2==0)group[i]=idx;}}vector<int> first_false(idx+1,INF);vector<int> last_false(idx+1,-1);for(int i=0;i<N;i+=2){int g=group[i];if(expr[i]=="false"){if(first_false[g]==INF)first_false[g]=i;last_false[g]=i;}}int first_true=INF,last_true=-1;for(int i=0;i<=idx;i++){if(first_false[i]==INF){if(first_true==INF)first_true=i;last_true=i;}}while(Q--){int l,r;cin>>l>>r;--l;--r;string query;cin>>query;int gl=group[l],gr=group[r];if(first_true<gl || last_true>gr){cout<<(query=="true"?'Y':'N');continue;}if(query=="true")cout<<(first_false[gl]<l || last_false[gr]>r?'N':'Y');elsecout<<'Y';}return 0;
}

好长啊。。。

Walking Along a Fence:

我们用一个二维矩阵记录每个点沿栅栏的距离，我们按顺序读入栅栏，当我们这样做时，我们遍历栅栏上的每个点，在数组中标记每个点0,1,2，…；同时记录周长。由于篱笆最多访问每个点一次，时间复杂度为 $\Theta (L^2)$ 。

#include <bits/stdc++.h>
using namespace std;
const int MAX=200005;
struct loc{int x;int y;
}posts[MAX];
int perimeter,dist[1005][1005];
void walk(loc st,loc ed){diff.x=ed.x-st.x,diff.y=ed.y-st.y;int dis=abs(diff.x)+abs(diff.y);diff.x=diff.x/dis,diff.y=diff.y/dis;for(int i=0;i<dis;i++){dist[st.x][st.y]=perimeter;perimeter++;st.x=st.x+diff.x,st.y=st.y+diff.y;}
}
int main(){int N,P;cin>>N>>P;for(int i=0;i<P;i++)cin>>posts[i].x>>posts[i].y;for(int i=0;i<P;i++)walk(posts[i],posts[(i+1)%P]);for(int i=0;i<N;i++){int x1,y1,x2,y2;cin>>x1>>y1>>x2>>y2;int p1=dist[x1][y1];int p2=dist[x2][y2];int ans=abs(p1-p2);ans=min(ans,perimeter-ans);cout<<ans<<endl;}return 0;
}

Farmer John's Favorite Permutation:

Farmer Nhoj????????????????????????????????????????????????????????????

Emmmmmmmmmm， $\Theta (N!)$ 暴力的话肯定是不行的。那怎么办呢？

我们会发现，不管怎么动，1，永远不会动。所以，1，必然是那个活到最后的人。 $h_{N-1}=1$ 。否则直接不可以总司令然后走人。

如果不是-1，我们就把最后一个从h里踢出去，不管它。

那p的最小字典序一定满足 $p_1<p_N$ 。接下来，我们会想:只有一组这样的p吗？

我们知道，h都是不同的，看起来，如果存在一些映射到h的p，p必然是唯一的。

大家可以手推一下，把h和p都算出来，可以发现这两点:

1. 每个h里的元素都是不同的

2. p结尾的数正好是从h里消失的两个。

所以，只要确定了p结尾的数，就可以得出整个p。

#include <bits/stdc++.h>
using namespace std;
int main(){int T;cin>>T;while(T--){int N;cin>>N;vector<int> h(N-1);for(auto &x:h)cin>>x;vector<bool> has(N+1);for(int x:h)has[x]=true;vector<int> not_has;for(int i=1;i<=N;i++){if(!has[i])not_has.push_back(i);}int cnt_one=count(h.begin(),h.end(),1);if(not_has.size()>2 || h.back()!=1 || (not_has.size()==2 && cnt_one!=2)){cout<<-1<<endl;continue;}vector<int> p(N);if(not_has.size()==1){p[0]=1;p[N-1]=not_has[0];}else{p[0]=not_has[0];p[N-1]=not_has[1];}int l=0,r=N-1;for(int i=0;i<N-1;i++){if(p[l]>p[r])p[++l]=h[i];elsep[--r]=h[i];}for(int i=0;i<N;i++)cout<<p[i];cout<<endl;}return 0; 
}

好了，以上就是本期的全部内容了。我们下期再见！\(^o^)/~

友情提示:本期的代码都有问题，请不要无脑Ctrl C+Ctrl V

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：http://www.rhkb.cn/news/301402.html

如若内容造成侵权/违法违规/事实不符，请联系长河编程网进行投诉反馈email:809451989@qq.com，一经查实，立即删除！