比赛链接:https://codeforc.es/contest/1729
本场比赛赛后补题,感觉比较轻松的做出前四题,第五题看不懂,是一个交互题(做的还是太少了)
A题:大意就是有两个电梯,第一个电梯在a楼,如果你使用第一个电梯,它会直接来1楼接你。第二个电梯在b楼,如果你使用第二个电梯,它需要先去c楼再来接你,即使第二个电梯在1楼你也不能先坐上。
直接对比a 和 b-c的绝对值+c。
code:
#include<bits/stdc++.h> using namespace std; #pragma GCC optimize(2) #define ll long long inline int read() { int x=0,f=1;char ch=getchar(); while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();} while (ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();} return x*f; } void solve() { int a,b,c; cin>>a>>b>>c; if(a<abs(b-c)+c) cout<<1<<endl; else if(a>abs(b-c)+c) cout<<2<<endl; else cout<<3<<endl; } int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int t; cin>>t; while(t--) { solve(); } }
B题:大意是给出一个字符串,串中元素为数字。数字对应英文字符。如果是两个元素对应字符,那么第三位置会是个0。即100 为10所对应的字符。
倒着做,判断是否为0,为0就看前两个元素,不为零就是当前元素。然后倒着输出出来就好
这里为什么要倒着做 可以 想一下 1100,如果正着做怎么做呢????
code:
#include<bits/stdc++.h> using namespace std; #pragma GCC optimize(2) #define ll long long inline int read() { int x=0,f=1;char ch=getchar(); while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();} while (ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();} return x*f; } void solve() { int n; cin>>n; string a; cin>>a; vector<char>ve; for(int i=a.size()-1;i>=0;) { if(a[i]!='0') { ve.push_back('a'+a[i]-'0'-1); i--; } else { ve.push_back('a'+(a[i-2]-'0')*10+(a[i-1]-'0')-1); i-=3; } } for(int i=ve.size()-1;i>=0;i--) cout<<ve[i]; cout<<endl; } int main() { // ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int t; cin>>t; while(t--) { solve(); } }
C题:大意是给出一个字符串,每个字符串对应数字 a == 1。你的任务时从字符串s[1]走到s[n],所需要最短的长度,相同长度下输出路线最多的那个。存在多个任意。从s[i] 走到 s[j]的长度 定义为 abs(s[i] - s[j])。
这个题很明显,你需要走出一条最长上升或下降路线,注意是路线不是序列。具体上升还是下降,需要看 s[n] 和 s[1]的大小
如果s[n]大于s[1],我们需要在2 - n-1这些元素中找到所有 s[1]<=s[i]<=s[n]的元素,然后升序,分别输出s[1] 升序列 s[n]
如果s[n]小于s[1],我们需要在2 - n-1这些元素中找到所有 s[1]>=s[i]>=s[n]的元素,然后降序,分别输出s[1] 降序列 s[n]
如果s[n]等于s[1],我们需要在2 - n-1这些元素中找到所有 s[1]==s[i]==s[n]的元素,然后升序,分别输出s[1] 序列 s[n]
code:
#include<bits/stdc++.h> using namespace std; #pragma GCC optimize(2) #define ll long long inline int read() { int x=0,f=1;char ch=getchar(); while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();} while (ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();} return x*f; } const int nn = 2*1e5+10; struct zifu{ char c; int pos; }; bool cmp(zifu a,zifu b){ return a.c<b.c; } vector<zifu> ve; void solve() { ve.clear(); string s; cin>>s; if(s[s.size()-1]>s[0]) { for(int i=1;i<s.size()-1;i++) if(s[i]>=s[0]&&s[i]<=s[s.size()-1]) ve.push_back({s[i],i+1}); sort(ve.begin(),ve.end(),cmp); cout<<abs(s[s.size()-1]-s[0])<<' '<<ve.size()+2<<endl; cout<<1<<' '; for(int i=0;i<ve.size();i++) cout<<ve[i].pos<<' '; cout<<s.size()<<endl; }else if(s[s.size()-1]<s[0]){ for(int i=1;i<s.size()-1;i++) if(s[i]<=s[0]&&s[i]>=s[s.size()-1]) ve.push_back({s[i],i+1}); sort(ve.begin(),ve.end(),cmp); cout<<abs(s[s.size()-1]-s[0])<<' '<<ve.size()+2<<endl; cout<<1<<' '; for(int i=ve.size()-1;i>=0;i--) cout<<ve[i].pos<<' '; cout<<s.size()<<endl; }else{ for(int i=1;i<s.size()-1;i++) if(s[i]==s[0]) ve.push_back({s[i],i+1}); cout<<0<<' '<<ve.size()+2<<endl; cout<<1<<' '; for(int i=0;i<ve.size();i++) cout<<ve[i].pos<<' '; cout<<s.size()<<endl; } } int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int t; cin>>t; while(t--) { solve(); } }
D题:大意是有n个人,每个人有想要消费的金额和现有金额。你的任务时将他们分组,每组至少两个人,这组的人满足现有金额总和大于等于想要消费金额总和。输出最大组数。
贪心思想,每组两人出最优解。大于两个人,两个正(现有大于消费),那么相等,一定存在金额多的人带动金额低的。
很难以描述。一种思想如果一个人需要多个人带动,那么带动的人可以形成组
这样来看,这个题可以直接双指针解决。计算出金额差值并排序,反复比较左右两边,如果满足就+1,不满足可以直接舍去左边负金额的人。(一定舍去的是负,因为如果左正 右面必然是正,存在满足)
code:
#include<bits/stdc++.h> using namespace std; #pragma GCC optimize(2) #define ll long long inline int read() { int x=0,f=1;char ch=getchar(); while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();} while (ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();} return x*f; } const int nn = 1e5+10; int a[nn]; int b[nn]; void solve() { memset(a,0,sizeof a); int n; cin>>n; for(int i=1;i<=n;i++) cin>>a[i]; for(int i=1;i<=n;i++) cin>>b[i],b[i]-=a[i]; sort(b+1,b+n+1); int l = 1, r = n; int ans = 0; while(l<r){ if(b[l]+b[r]>=0) l++,r--,ans++; else l++; } cout<<ans<<endl; } int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int t; cin>>t; while(t--) { solve(); } }
E题:大意是存在一个n个节点的环,你不知道n的大小,你可以询问两个节点的距离,会返回两个节点的路径长度,一共有2条,一条长一条短。只能询问50次,请猜出n的大小。
反复询问1与其他任意,如果存在-1.说明i在环外,那么n一定为 i-1,因为i的值是逐渐增加的。
如果存在 x!=y ,即对 1 i 和 i 1的询问并不相等,因为距离是等概率出现,所以,50次数的循环查询,大概率存在一个x!=y从而找到环的两侧
因为2的50次方很难出锅。
本质上还是一个思维题,而且是一个思维性并不强的题,难就难在读题上,毕竟蓝题+,还是要给点面子的啊哈哈哈。
code:
#include<bits/stdc++.h> using namespace std; #pragma GCC optimize(2) #define ll long long inline int read() { int x=0,f=1;char ch=getchar(); while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();} while (ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();} return x*f; } ll ask(int a,int b){ cout<<"? "<<a<<' '<<b<<endl; ll x;cin>>x; return x; } ll solve() { for(int i=2;i<=26;i++){ ll x = ask(1,i); ll y = ask(i,1); if(x==-1) return i-1; if(x!=y) return x+y; } } int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); ll ans = solve(); cout<<"! "<<ans<<endl; }