Codeforces Round 767 (Div. 2) A~E
大意是你一开始有 m G内存,每次你可以使用不超过你内存的RAM来升级你的内存，第i个扩充内存b[i].
思路：
直接贪心即可，每次都选最小的来升级。
1
2
3
4
5
6
7
8
9
| void solve(){
n=read();m=read();
rep(i,1,n) a[i].x=read(),a[i].y=i;
rep(i,1,n) b[i]=read();
sort(a+1,a+1+n);
for(int i=1;i<=n;++i)
if(m>=a[i].x) m+=b[a[i].y];
print(m);
}
|
大意是给你一段连续的[l,r]之内的数，每次可以选择两个数丢掉并把他们的乘积加进来，问k次操作以内是否可以把整个序列的gcd大于1
思路：
我们可以直接想到让区间内的所有数获得因子2是操作最少的，因此把所有奇数操作掉即可。因此判断[l,r]中的奇数数量是否小于等于k,注意l=r=1的时候要特判
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| void solve(){
l=read(),r=read(),k=read();
LL num=(r-l)/2+(((l%2)==0)||(r%2==0));
num=r-l+1-num;
if(l==1&&r==1){
puts("NO");
return ;
}
if(l==r&&l!=1) {
puts("YES");
return ;
}
if(k>=num) puts("YES");
else puts("NO");
}
|
大意是给你一个序列，你可以任意分割序列使得得到的每一段序列的mex值按顺序组成新序列字典序最大
思路：
容易想到，需要贪心的让第一端mex最大，然后在剩下的让第二段mex最大…因此我们可以利用双指针直接模拟，用两个辅助数组，一个记录哪些数出现过，另一个记录每个数出现了多少次。前面的指针每次找到当前端mex-1第一次出现的位置，然后记录答案，后面的指针删去这一段的次数。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
| const int N = 200010, tot=200000;
int n,cnt[N],a[N],num[N];
vector<int> ans;
int mex=0,last=0,mx=0;
void solve(){
mex=mx=0; ans.clear();
n=read();
rep(i,1,n) a[i]=read(),mx=max(mx,a[i]),num[a[i]]++;
last=1;
for(int i=1;i<=n;++i){
cnt[a[i]]++;
while(cnt[mex]) mex++;
if(!num[mex]){
ans.push_back(mex);
for(int j=last;j<=i;++j) num[a[j]]-=cnt[a[j]],cnt[a[j]]=0;
mex=0;
last=i+1;
}
}
print(ans.size());
for(auto u:ans) printf("%d ",u); puts("");
rep(i,0,mx) num[i]=0,cnt[i]=0;
}
|
大意是给你一些长度不超过3的字符串，问在保留原有顺序的情况下是否可以选择一些字符串（不可以不选）拼接成回文串
思路：
最终是回文串一共只有五种情况。
- 存在单个字符或者本身回文的字符串
- 长度2+长度2拼接成回文串
- 长度2+长度3拼接成回文串
- 长度3+长度2拼接成回文串
- 长度3+长度3拼接成回文串
由于长度很短，因此我们可以不用哈希，直接开数组存储即可。
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
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
| #define int LL
const int N=200010,M=27;
int n,m,k;
string str[N];
int t1[M],t2[M][M],t3[M][M][M];
int get(char ch){
return ch-'a'+1;
}
void solve(){
memset(t1,0,sizeof t1);
memset(t2,0,sizeof t2);
memset(t3,0,sizeof t3);
cin >> n;
rep(i,1,n) cin >> str[i];
bool ok=false;
rep(i,1,n){
if(str[i].size()==1){
ok=true;
break;
}
else if(str[i].size()==2){
t2[get(str[i][0])][get(str[i][1])]++;
if(str[i][0]==str[i][1]) {
ok=true;
break;
}
}
else{
t3[get(str[i][0])][get(str[i][1])][get(str[i][2])]++;
}
}
if(ok){
puts("YES");
return ;
}
for(int i=1;i<=n;++i){
if(str[i].size()==1) continue;
else if(str[i].size()==2){
if(t2[get(str[i][1])][get(str[i][0])]) {
ok=true;
break;
}
for(int j=1;j<=26;++j) {
if(ok) break;
if(t3[j][get(str[i][1])][get(str[i][0])]){
ok=true;
break;
}
}
}
else{
if(t3[get(str[i][2])][get(str[i][1])][get(str[i][0])]){
ok=true;
break;
}
if(t2[get(str[i][1])][get(str[i][0])]){
ok=true;
break;
}
}
if(str[i].size()==2) t2[get(str[i][0])][get(str[i][1])]--;
else if(str[i].size()==3) t3[get(str[i][0])][get(str[i][1])][get(str[i][2])]--;
}
puts(ok?"YES":"NO");
}
|
大意是给你一个边长为偶数的正方形方格，只告诉你每个方格其所有相邻方格的异或和，求整个方形的全部元素异或和。
思路：
我们通过模拟4*4的发现一定是两个两个选的，且不能选会覆盖之前已经选了的区域。根据题目中
可以证明解一定唯一，我们得知解一定存在，又由于是正方形，因此我们一行一行的选取格子并将其覆盖区域染色，时刻保证
- 前面的空格不被遗漏
- 后面新选取的格子覆盖的区域与之前无重叠
因为有重叠了等于没染，此时又要新的格子来染被消除的，会导致新的格子被消除。
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
| const int N = 1010;
int n,a[N][N],g[N][N],mov[4][2]={1,0,0,1,-1,0,0,-1};
LL ans=0;
void solve(){
memset(g,0,sizeof g);
ans=0;
n=read();
rep(i,1,n) rep(j,1,n) a[i][j]=read();
rep(i,1,n) rep(j,1,n){
bool flag=true;
rep(k,0,3){
int x=i+mov[k][0], y=j+mov[k][1];
if(g[x][y]) flag=false;
}
if(flag){
ans^=a[i][j];
rep(k,0,3){
int x=i+mov[k][0], y=j+mov[k][1];
g[x][y] ++;
}
}
}
print(ans);
}
|