Codeforces Round 1002 (Div. 2，A-C)
想了一下，我觉得个人赛的一个基本流程大致是这样的
- 认真的读一遍题，如果有，一定要看样例的解释，最后模拟样例
- 从问题的性质出发，包括但不限于复杂度，题目与数据的限制，重新读题，将问题转化为子问题。如果一个hint都没有，建议重复步骤1，如果卡这超过10分钟，建议切题
- 给出相应的解决方法，一定要思考可做性，可以参考过题人数与速度，同时思考一下代码的实现难易程度，在这里卡超过10分钟，也建议重新读题/切题
A
GuessForces
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| void solve(){
int n;cin>>n;
vector<int>a(n),b(n);
for(int i=0;i<n;i++) cin>>a[i];
for(int i=0;i<n;i++) cin>>b[i];
sort(a.begin(),a.end());
sort(b.begin(),b.end());
set<int>st;
vector<int>v1,v2;
for(int i=0;i<n;i++){
if(!st.count(a[i]+b[i])) st.insert(a[i]+b[i]);
else{
v1.push_back(a[i]);
v2.push_back(b[i]);
}
}
sort(v1.begin(),v1.end());
sort(v2.begin(),v2.end(),greater<int>());
for(int i=0;i<v1.size();i++){
st.insert(v1[i]+v2[i]);
}
cout<<(st.size()>=3?"YES\n":"NO\n");
}
|
B
贪心的想，越长的串出现非i数一定越多
如果恰好填满(即k==n),只能按部就班的模拟
否则我们使得前2个子数组尽可能长(即让后k-2个子数组每个只包含一个数字)，遍历前[2,n-(k-2)]的数组，容易发现一旦a[i]!=1，我们就将其作为第二段子数组的起点，此时答案为1
否则只能是该段数组都只包含1，此时将a[1]作为第一段子数组，第二段子数组将包含>1个数的1(因为此时n>k)，此时答案为2
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
| void solve(){
int n,k,cnt=1;cin>>n>>k;
vector<int>a(n+1),st;
for(int i=1;i<=n;i++){
cin>>a[i];
}
if(k==n){
for(int i=1;i<=n;i++){
if(i%2==0) st.push_back(a[i]);
}
st.push_back(0);
for(auto i:st){
if(i!=cnt){
cout<<cnt<<"\n";
return;
}
cnt++;
}
}
for(int i=2;i<=n-(k-2);i++){
if(a[i]!=1){
cout<<1<<"\n";
return;
}
}
cout<<2<<"\n";
}
|
v1.5.2