Codeforces Round #784 (Div. 4)
前言:
题目都挺新手的,符合div4该有的难度,并且给我贡献了史上第一次ak局,相对还蛮欢乐的,适合新人。
1小时15分钟ak,老年人手速了。
A. Division?
思路:if else即可。
- 参考代码:
#include<bits/stdc++.h>
using namespace std;
#define int long long
void cf(){
int x;
cin>>x;
if(x<1400)cout<<"Division 4"<<endl;
else if(x<1600)cout<<"Division 3"<<endl;
else if(x<1900)cout<<"Division 2"<<endl;
else cout<<"Division 1"<<endl;
}
signed main(){
int t=1;
cin>>t;
while(t--){
cf();
}
}
B. Triple
思路: a的数据范围很小直接拿数组存,边跑边存,出现某个数个数大于等于3输出那个数,都没有输出−1
- 参考代码:
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N = 2e5+10;
int a[N];
int sum[N];
void cf(){
int n;
cin>>n;
for(int i=1;i<=n;i++){cin>>a[i];sum[a[i]]=0;}
for(int i=1;i<=n;i++){
sum[a[i]]++;
if(sum[a[i]]>=3){cout<<a[i]<<endl;return ;}
}
cout<<"-1"<<endl;
}
signed main(){
int t=1;
cin>>t;
while(t--){
cf();
}
}
C. Odd/Even Increments
思路: 奇偶性问题,不管奇数位怎么变,偶数位怎么变,如果两个数都在奇数位或者两个数都在偶数位,他们之间的奇偶关系始终保持不变,例如1 3 5这组数据1和5都是奇数位不管怎么加,他们都是共奇共偶的,如果是1 3 6这组数据,1和6都是奇数位不管怎么加,他们都是1奇1偶。且奇数位和偶数位相互独立互不影响,所以我们是要判断是否存在奇数位上的所有数且偶数位上的所有数都是共奇共偶的情况,如果存在即为YES否则是NO,注意只有两个数的情况,因此我们直接从3和4开始判断即可。
- 参考代码:
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N = 55;
int a[N];
void cf(){
int n;
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i];
}
bool ok = true;
for(int i=3;i<=n;i+=2){
if((a[i]%2)!=(a[i-2]%2)){
ok=false;
}
}
for(int i=4;i<=n;i+=2){
if((a[i]%2)!=(a[i-2]%2)){
ok=false;
}
}
if(ok)cout<<"YES"<<endl;
else cout<<"NO"<<endl;
}
signed main(){
int t=1;
cin>>t;
while(t--){
cf();
}
}
D. Colorful Stamp
思路: 这题是个结论题,红蓝染色问题,因为不能染到格子外,所以我们令下标0和下标n+1全部当作w处理。然后将w、b、r分别转化为0、1、2。此外,如果一段区间染色,那么必然两种颜色都存在,全为b或者全为r显然是不成立的。且每段染色区间由两个w进行隔开,例如染色区间为:wrrbrbrbrbrw。那么同样得到了这个结论我们进行O(n)扫描,如果出现不合法的输出NO,否则输出YES。
- 参考代码:
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1e5+10;
int a[N];
void cf(){
a[0]=0;
int n;
cin>>n;
string s;
cin>>s;
for(int i=0;i<s.size();i++){
if(s[i]=='W')a[i+1]=0;
else if(s[i]=='B')a[i+1]=1;
else if(s[i]=='R')a[i+1]=2;
}
a[n+1]=0;
for(int i=0;i<=n+1;i++){
if(a[i]==0){
bool ok = false;
int res=0;//用来判断出现几种颜色
for(int j=i+1;j<=n+1;j++){
if(a[j]!=0&&res==0){
res=a[j];
}
else if(a[j]!=0&&res!=0&&res!=a[j]){
ok=true;//出现两种颜色区间合法
}
if(a[j]==0){//右边的w
if(!ok&&res!=0){//如果没染色或者染了两种颜色是合法的
cout<<"NO"<<endl;
return ;
}
else{//更新i,因为右边的w可以作为新的区间段的左边界所以i=j-1
i=j-1;
goto GG;
}
}
}
GG:;
}
}
cout<<"YES"<<endl;
return ;
}
signed main(){
int t=1;
cin>>t;
while(t--){
cf();
}
}
E. 2-Letter Strings
思路: 无脑hash,用mp1存第1关键字符,mp2存第2关键字符,mp存string,接下去每次出现新的string s加上前面统计过的mp1[s[0]]和mp2[s[1]],并且如果前面出现了和s相同的string,实则是不合法的,但是mp1和mp2同样会统计其第1关键字和第2关键字出现的次数,所以我们需要减去mp[s] ∗ 2
- 参考代码:
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N = 2e5+10;
map<char,int>mp1,mp2;
map<string,int>mp;
void cf(){
mp.clear();
mp1.clear();
mp2.clear();
int n;
cin>>n;
int sum=0;
for(int i=1;i<=n;i++){
string s;
cin>>s;
sum+=mp1[s[0]];
sum+=mp2[s[1]];
sum-=mp[s]*2;
mp1[s[0]]++;
mp2[s[1]]++;
mp[s]++;
}
cout<<sum<<endl;
}
signed main(){
int t=1;
cin>>t;
while(t--){
cf();
}
}
F. Eating Candies
思路: 双指针,用left和right统计两边吃的number,如果相等就更新一下,否则left和right谁小谁吃糖,直至l>r退出。
- 参考代码:
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N = 2e5+10;
int a[N];
void cf(){
int n;
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i];
}
int l=1,r=n;
int ma=0;
int left=0,right=0;
while(l<=r){
if(left==right){
ma=l-1+n-r;
}
if(left<=right){
left+=a[l];
l++;
}
else if(left>right){
right+=a[r];
r--;
}
}
if(left==right)ma=n;
cout<<ma<<endl;
}
signed main(){
int t=1;
cin>>t;
while(t--){
cf();
}
}
G. Fall Down
思路: 一道模拟题,数据范围很小直接暴力模拟,因为最后一层也算一个终止点,所以我们可以初始化令第n+1行的所有字符变成o,然后每次单独处理每一列即可,在碰到o之前只要出现 ∗ 就统计一下 ∗ 出现的次数,一旦碰到o,就将前面统计过的 ∗ 出现从下到上依次放好,且清空 ∗ 出现次数,重新统计。
- 参考代码:
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N = 55;
char s[N][N];
void cf(){
int n,m;
cin>>n>>m;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)cin>>s[i][j];
for(int i=1;i<=m;i++)s[n+1][i]='o';
for(int i=1;i<=m;i++){//列
int cnt=0;
int st=1;
for(int j=1;j<=n+1;j++){
if(s[j][i]=='*')cnt++;
else if(s[j][i]=='.')continue;
else if(s[j][i]=='o'){
for(int k=st;k<=j-1;k++){
s[k][i]='.';
}
for(int k=j-cnt;k<j;k++){
s[k][i]='*';
}
st=j+1;
cnt=0;
}
}
}
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++)cout<<s[i][j];cout<<endl;}
return ;
}
signed main(){
int t=1;
cin>>t;
while(t--){
cf();
}
}
H. Maximal AND
思路: 二进制高位贪心,首先统计一下所有数在二进制位下每一位出现的次数,由于我们每次操作可以使一个数的二进制为从0变成1,且要求最终所有数的AND值最大,那么最优策略就是从高位进行填补,如果k的剩余值能将高位所有0变成1显然将所有0变成1更优。
- 参考代码:
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N = 2e5+10;
int a[N];
int sum[35];
void cf(){
memset(sum,0,sizeof sum);
int n,k;
cin>>n>>k;
for(int i=1;i<=n;i++){
cin>>a[i];
}
for(int i=30;i>=0;i--){
for(int j=1;j<=n;j++){
if((a[j]>>i)&1)sum[i]++;
}
}
int res=0;
for(int i=30;i>=0;i--){
if(k>=n-sum[i]){
k-=(n-sum[i]);
res|=1<<i;
}
}
cout<<res<<endl;
}
signed main(){
int t=1;
cin>>t;
while(t--){
cf();
}
}
nb
%%%
昨晚小号打也ak了, 太舒服了hhh
确实舒服
%%%%,snowgg比我手速快🥳
🥳
厉害
很强,只能这么说了
public static void solve() { int n = in.nextInt(); String str = in.next(); int sumr = 0; int sumb = 0; str += 'W'; for (int i = 0; i < str.length(); i++) { if (str.charAt(i) == 'W') { if ((sumb == 0 && sumr == 0) || (sumb > 0 && sumr > 0)) { sumb = 0; sumr = 0; } else { System.out.println("NO"); return; } } else if (str.charAt(i) == 'B') { sumb++; } else { sumr++; } } System.out.println("YES"); }
我觉得我的D题解法更容易理解一点,用‘W’来区分区间,每个区间中,必须包含两种颜色(不能全蓝,也不能全红) 如果出现全蓝或者全红,直接输出NO
差不多的,两个w之间为一段连续区域,如果出现颜色单一的就输出NO