526互联

AtCoder Beginner Contest 295 A-D题解

发布时间 2023-03-26 16:28:22作者: HikariFears

比赛地址

A.Probably English

 1 void solve()
 2 {
 3     int n;cin>>n;
 4     set<string>st;
 5     st.insert("and");
 6     st.insert("not");
 7     st.insert("that");
 8     st.insert("the");
 9     st.insert("you");
10     while(n--)
11     {
12         string s;
13         cin>>s;
14         if(st.count(s))
15         {
16             cout<<"Yes"<<"\n";
17             return;
18         }
19     }
20     cout<<"No\n";
21 }
View Code

B.Bombs

 1 void solve()
 2 {
 3     int n,m;cin>>n>>m;
 4     for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)cin>>a[i][j];
 5     for(int i=1;i<=n;i++)
 6     {
 7         for(int j=1;j<=m;j++)
 8         {
 9             if(a[i][j]>='0'&&a[i][j]<='9')
10             {
11                 for(int ii=i-(a[i][j]-'0');ii<=i+(a[i][j]-'0');ii++)
12                 {
13                     for(int jj=j-(a[i][j]-'0');jj<=j+(a[i][j]-'0');jj++)
14                     {
15                         if(ii>0&&ii<=n&&jj>0&&jj<=m&&abs(i-ii)+abs(j-jj)<=(a[i][j]-'0'))
16                         {
17                             if(a[ii][jj]=='#')a[ii][jj]='.';
18                         }
19                     }
20                 }
21                 a[i][j]='.';
22             }
23         }
24     }
25     for(int i=1;i<=n;i++)
26     {
27         for(int j=1;j<=m;j++)
28         {
29             cout<<a[i][j];
30         }
31         cout<<"\n";
32     }
33 }
View Code

C.Socks

 1 void solve()
 2 {
 3     int n;cin>>n;
 4     set<int>st;
 5     int ans=0;
 6     while(n--)
 7     {
 8         int x;cin>>x;
 9         if(st.count(x))
10         {
11             ans++;
12             st.erase(x);
13         }else st.insert(x);
14     }
15     cout<<ans<<"\n";
16 }
View Code

D.Three Days Ago

题意：给出一个数字字符串，问有多少个子区间能表示成一个字符串重复两次

Solution

前缀和，很明显当区间内每个数字的个数均为偶数时才成立

我们用前缀和记录下从1到i的每个数字个数，然后对于[l,r]，如果l-1和r的每一个数字的奇偶性相同，那么就能保证[l,r]成立

这里用二进制的方式来表示每一位数字的状态，因为相邻的状态一定不同，所以不用判断，另外对于i=0的状态为0，要注意一下

 1 int a[N][10];
 2 int b[1<<10];
 3 void solve()
 4 {
 5     string s;cin>>s;
 6     int ans=0;
 7     a[0][s[0]-'0']=1;
 8     for(int i=1;i<s.length();i++)
 9     {
10         for(int j=0;j<=9;j++)
11         {
12             a[i][j]=a[i-1][j];
13         }
14         a[i][s[i]-'0']=a[i-1][s[i]-'0']+1;
15     }
16     b[0]=1;
17     for(int i=0;i<s.length();i++)
18     {
19         int res=0;
20         for(int j=0;j<=9;j++)
21         {
22             if(a[i][j]&1)res+=1;
23             if(j!=9)res<<=1;
24         }
25         
26         ans+=b[res];
27         b[res]++;
28     }
29     cout<<ans<<"\n";
30 }
View Code