#767（div2）
感受
掉大分，思路没问题代码各种手误，卡手了。
还有如果有思路不要一会换一道，一会换一道，认真思考而不是换题。
A. Download More RAM
原题链接
题意：
加内存，有n个加内存的软件，每个需要ai，打开后返回ai并增加bi。求最大的内存。
分析：
按a从小到大排序，从头开始遍历，到第一个不满足条件的跳出，此时内存为最大值。
代码：
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
| #include<bits/stdc++.h>
#define x first
#define y second
using namespace std;
const int N=110;
typedef pair<int, int> PII;
PII a[N];
int n,k;
int main()
{
int t;cin>>t;
while(t--)
{
cin>>n>>k;
for(int i=1;i<=n;i++)cin>>a[i].x;
for(int i=1;i<=n;i++)cin>>a[i].y;
sort(a+1,a+n+1);
for(int i=1;i<=n;i++)
{
if(a[i].x<=k)k+=a[i].y;
else break;
}
cout<<k<<endl;
}
}
|
B. GCD Arrays
原题链接
题意：
给l，r，k。求区间[l,r]内k个操作内其中任意两个数gcd不为1。
分析：
因为数据极大，所以不可能求gcd，肯定是找规律。
特判+求奇数个数。
如果k大于等于奇数个数，输出YES，不然输出NO。
特判：l==r的时候，除了1是NO，以外均是YES
代码：
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
| #include<bits/stdc++.h>
using namespace std;
int l,r,k;
int main()
{
int t;cin>>t;
while(t--)
{
cin>>l>>r>>k;
if(r==1)
{
cout<<"NO"<<endl;
continue;
}
if(l==r && l!=1)
{
cout<<"YES"<<endl;
continue;
}
int num=(r-l)/2;
if((r-l)%2==1)num++;
if(r%2==1 && l%2==1)num++;
if(num<=k)cout<<"YES"<<endl;
else cout<<"NO"<<endl;
}
}
|
C. Meximum Array
原题链接
题意：
新定义MEX概念：数组内第一个没有的非负整数
e.g.MEX({1,2,31,2,3}) =0=0 and MEX({0,1,2,4,50,1,2,4,5}) =3=3.
给定一个数组a，取出前k个数求MEX放到最后，然后从剩下的继续，直到a数组为空。求b数组最大（仅按第几位比较，不比长度）的情况下的长度及每次取出k个数的MEX值。
分析：
贪心。
因为n<2*105,所以可以维护一个桶寻找MEX最大值num，然后根据每次找到的MEX最大值遍历a数组，直到满足。记录sum，num的值并重复，直到a数组为空。
代码：
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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
| #include<bits/stdc++.h>
using namespace std;
const int N=200010;
int a[N];
int s[N],st[N];
int b[N];
int main()
{
int t;cin>>t;
while(t--)
{
int n;cin>>n;
for(int i=1;i<=n;i++)
{
int num;
cin>>num;
s[num]++;
a[i]=num;
}
int sum=0;
for(int k=1;k<=n;k++)
{
int num=0,op=0,fl=0;
while (s[num])num++;
for(int i=k;i<=n;i++)
{
s[a[i]]--;
if(!st[a[i]] && a[i]<=num)op++,st[a[i]]=1;
if(op==num)
{
b[sum++]=num;
for(int j=0;j<=num;j++)st[j]=0;
k=i;fl=1;
break;
}
}
}
cout<<sum<<endl;
for(int i=0;i<sum;i++)cout<<b[i]<<' ';
cout<<endl;
}
}
|
D. Peculiar Movie Preferences
原题链接
题意：
n个长度不超过3的字符串，使其组合成回文串。
跳过场景，而不是随意选。
分析：
分情况讨论
- 字符长度是1：是回文。
- 字符长度是2：存进map，reverse然后看是否有回文。
- 字符长度是3：判自己是否是回文，不是的话存进map，reverse然后看是否有回文。没有的话
- 前两位放到map中并于之前长度为二的分开（map存的值不一样）。
- 后两位reverse后从之前字符长度为2中找是否有回文。
- 以上所有只要有一个回文条件满足，那么输出YES，不然输出NO
代码：
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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
| #include<bits/stdc++.h>
using namespace std;
const int N=100010;
string s;
int main()
{
int t;cin>>t;
while(t--)
{
int n;cin>>n;
map<string,int> q,p;
int fl=0;
for(int i=1;i<=n;i++)
{
cin>>s;
if(fl==1)continue;
if(s.size()==1)
{
fl=1;continue;
}
if(s.size()==2)
{
q[s]=1;
swap(s[0],s[1]);
if(q[s]!=0)fl=1;
}else
{
if(s[0]==s[2])
{
fl=1;
continue;
}
q[s]=1;
swap(s[0],s[2]);
if(q[s]==1)fl=1;
else
{
swap(s[0],s[2]);
string l,r;
l+=s[0];l+=s[1];
q[l]=2;
r+=s[1];r+=s[2];
swap(r[0],r[1]);
if(q[r]==1)fl=1;
}
}
}
if(fl)cout<<"YES"<<endl;
else cout<<"NO"<<endl;
}
}
|
