比赛链接:https://codeforc.es/contest/1705
这个周赛没有参加。后来A了A和B。C题有思路,但是不知道怎么入手。
A题:大意是给出n个人的身高,要求排成两排,后排比前排要高出x。
运用贪心的思想,易得,在排序后的前后半边,高的对高的,矮的对矮的。
code:
#include<bits/stdc++.h> using namespace std; int n,x; int a[210]; void panduan() { for(int i=1;i<=n;i++) { if(a[n+i]-a[i]<x) { printf("NO\n"); return; } } printf("YES\n"); } int main() { int t; cin>>t; while(t--) { memset(a,0,sizeof a); cin>>n>>x; for(int i=1;i<=2*n;i++) cin>>a[i]; sort(a+1,a+2*n+1); panduan(); } }
B题:思维题,大意是有n个房间,每个房间都有一定的灰尘,我们定义灰尘量为数字。有一个扫地机器人,它可以同时使连续的多个房间的灰尘从a[i]=a[i-1],a[i+1]=a[i+1]+1。这样就使得灰尘右移,问最少通过多少种操作可以使得对于每个ai,1<=i<=n-1的灰尘为0。也就是所有灰尘都挪到了n号房间。
这个题我的解决方案是通过面向样例编程实现的(没错,这招我也悟了)。首先移动的次数肯定是和最先有灰尘的房子和n号房的距离有关,也肯定和灰尘数量有关,因为每次操作我们都只能移动一个数量级灰尘。知道了这个因果关系,假设最先有灰尘的房间和n号房之间没有任何空灰尘房间,那么答案一定是这之间的房间灰尘数量加起来。如果有空房间,那么我们需要把后面的灰尘移动到空房间里。所以房间无论有无灰尘,都要与n号房做一次交互。
code:
#include<bits/stdc++.h> using namespace std; #define ll long long int main() { ll t; cin>>t; while(t--) { int n,x; cin>>n; bool sign = false; ll ans = 0; for(int i=1;i<=n;i++) { cin>>x; if(i!=n&&(sign||x)) { ans+=max(1,x); sign = true; } } cout<<ans<<endl; } }
C题:一个字符串的题。大意是给出一个字符串,然后c次操作,每次操作可以使得l - r这些字符复制粘贴到字符串末尾,这样字符串的大小也改变了。
然后给出q次查询,每次查询给出一个k,询问位置k的字符是什么?
这个题给出的字符串的长度挺大2*1e5,c是40次,字符串长度最高可以达到 2*1ec * 2 ^40,接近1e18。这个题暴力直接爆内存。
我的想法是开数组记录每次操作后的新字符串的新加长度的开始位置和结束位置。这个和正解也是一致的。然后通过递归(回推)的方式,由k转移到原始字符的某一个位置。想法是好的,但是没有实现==。
解决方法:分别记录每次操作的新加长度的开始位置、结束位置和差异数量。给出k后,对着我们保存的区间进行查找,如果在区间范围内,那么我们就让k减去这个差异数量,从而确定到初始的字符串
code:
#include<bits/stdc++.h> using namespace std; #define ll long long int main() { int t; cin>>t; while(t--) { ll n,c,q; cin>>n>>c>>q; string a; vector<ll>left(c+1),right(c+1),diff(c+1); cin>>a; ll l,r; left[0] = 0; right[0] = n; for(ll i=1;i<=c;i++) { cin>>l>>r; l--,r--; left[i] = right[i-1]; right[i] = right[i-1] + r-l+1; diff[i] = left[i] - l;//差异长度 } while(q--) { ll k; cin>>k; k--; for(ll i=c;i>=1;i--) { if(k>=left[i]) k-=diff[i]; } cout<<a[k]<<endl; } } }