526互联

AtCoder Beginner Contest 285（B,D,E,F)

发布时间 2023-05-06 20:44:48作者: righting

AtCoder Beginner Contest 285（B,D,E,F)

B （暴力，非二分）

B

这道题其实很简单，但是我在\(vp\)的过程，有了一个错误的认识，纠正一下

那就是，我把这个当成了一个二分题，并且还有点坚定不移，后来细想，发现不对

二分，适用于那种边界分明的那种题（左边一定是符合条件，右边一定符合条件，也可表达为线性问题那种）这种的，但是这个题不符合这个条件，不符合（万一右边出现了一个符合条件的，但是左边也可能存在不符合条件的）

所以这道题直接暴力即可

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include<cmath>
#include <unordered_map>
#include <array>
#include <cstring>
using namespace std;
#define int long long 
#define LL long long
#define ios  ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define inf 1e18
#define INF 1e18
#define mem(a,b) memset((a),(b),sizeof(a))
const double eps=1e-9;
const int maxn=1e6+10;
const int mod=998244353;
int n;
string s;
int solve(int pos)
{
   int ans=n-pos;
   for (int i=1;i<=n-pos;i++)
   {
      if(s[i]==s[i+pos])
      {
         ans=i-1;
         break;
      }
   }
   return ans;
}
signed main() 
{
   cin>>n>>s;
   s=" "+s;
   for (int i=1;i<n;i++)
   {
     cout<<solve(i)<<"\n";
   }
   system ("pause");
    return 0;
}

D (图，拓扑排序)

D

为什么每次我都没有看懂题意，好难过

这个题的大意就是每个人都会使用一个字符串\(s\),但是每个人都想要换这个字符串\(s\)换成\(t\),但是这个换字符串还有一个条件很关键，那就是那个\(t\)是没有正在被其他人所使用的

题目问是否可以让每个人都可以换成功（我一开始以为是只要一个人换成功就好了，我就在想，怎么会有这么简单的\(D\)题）

正难则反，我们不太可能找到一个正确的换字符串的顺序，我们可以找有哪些是一定换不了的

然后，我们发现这个换来换去的有点像图，如果把这个过程当成图来看（有向边），如果有一个环的话，那么这个环里面的字符都是换不成功的了，所以我们只需要找到环即可（找到，就是\(No\))

对于找环，有两种方法

一种是直接\(dfs\)，如果出现了一个点到了\(2\)次以上，那么一定存在一个环

一种是拓扑排序，判断进入队列里面是否有\(n\)个

题目里面的字符串我对他们进行了离散化

我这里用的是拓扑排序

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include<cmath>
#include <unordered_map>
#include <array>
#include <cstring>
using namespace std;
#define int long long 
#define LL long long
#define ios  ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define inf 1e18
#define INF 1e18
#define mem(a,b) memset((a),(b),sizeof(a))
const double eps=1e-9;
const int maxn=1e6+10;
const int mod=998244353;
int n;
string s[maxn],t[maxn];
set<string>rk;
map<string,int>has;
int in[maxn];
vector<int>g[maxn];
signed main() 
{
   cin>>n;
   for (int i=1;i<=n;i++)
   {
      cin>>s[i]>>t[i];
      rk.insert(s[i]);
      rk.insert(t[i]);
   }
   int now=0;
   for (auto x:rk)
   {
      now++;
      has[x]=now;
   }
   for (int i=1;i<=n;i++)
   {
      int u=has[s[i]],v=has[t[i]];
      g[u].push_back(v);
      in[v]++;
   }
   queue<int>q;
   int cnt=now;
   for (int i=1;i<=now;i++)
   {
      if(in[i]==0)
      {
         q.push(i);
         cnt--;
      }
   }
   while (!q.empty())
   {
      int u=q.front();
      q.pop();
      for (auto x:g[u])
      {
         in[x]--;
         if(in[x]==0)
         {
            q.push(x);
            cnt--;
         }
      }
   }
   if(cnt)
   {
      cout<<"No\n";
   }
   else 
   {
      cout<<"Yes\n";
   }
   system ("pause");
    return 0;
}

E（dp,前缀和）

E

这个题目的大意就是有n天，我们可以选择任意天作为假期，我们每一天都会有一个效率

对于这一天是假期，那么这一天的效率为\(0\)

对于这一天是工作日，那么我们需要知道上一次假期离现在的天数\(x\),还需要知道现在距离下一次假期的天数，那么这一天的效率为\(A_{min(x,y)}\)

我们发现假期具体是哪一天不重要，重要的是这一天距离自己较近的那一天的距离是多少

所以干脆把第一天作为作为上一次工作的假期，这样就不用了担心后面寻找前一个不太好找了

然后我们可以设\(dp[i]\)为前\(i\)天，并且第\(i\)天是假期的最大效率

可以得到状态转移方程为

dp[i]=max(dp[i],dp[j]+(a[min(i-(j+1),(j+1)-j)]+a[min(i-(j+2),(j+2)-j]+....+a[min(i-(i-1),(i-1)-j)]+dp[j]))

我们发现那一段\(a\)的和好像是有规律的，对于那些里\(i\)近的，选择\(i\),可以是从\(1\)到中间，对于那些里\(j\)近的，选择\(j\),可以是从\(1\)到中间，但是注意最中间的那一个，离\(i\)和\(j\)一样，只需要加一次即可，我们可以直接通过前缀和预处理出来

故，对于\(l,r\)范围，可以直接得到\(sum[len/2]+sum[(len+1)/2]\)

然后我们可以得到一个更简单的状态转移方程

dp[i]=max(dp[i],dp[j]+get(j,i))

具体看代码

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include<cmath>
#include <unordered_map>
#include <array>
#include <cstring>
using namespace std;
#define int long long 
#define LL long long
#define ios  ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define inf 1e18
#define INF 1e18
#define mem(a,b) memset((a),(b),sizeof(a))
const double eps=1e-9;
const int maxn=1e6+10;
const int mod=998244353;
int n;
int a[maxn],sum[maxn];
int dp[maxn];
int get(int l,int r)
{
   int len=(r-l-1);
   int L=len/2,R=(len+1)/2;
   return sum[L]+sum[R];
}
signed main() 
{
   cin>>n;
   for (int i=1;i<=n;i++)
   {
      cin>>a[i];
      sum[i]=sum[i-1]+a[i];
   }
   dp[1]=0;
   for (int i=2;i<=n+1;i++)
   {
      for (int j=1;j<i;j++)
      {
         dp[i]=max(dp[i],dp[j]+get(j,i));
      }
   }
   cout<<dp[n+1]<<"\n";
   system ("pause");
    return 0;
}

F(树状数组)

F

这个题大意很简单，就是给你一个字符串，有两种操作

一种是需要把\(x\)位置的字符改成\(ch\)

还有一种是需要判断对于此时的字符串\(s\),把里面的字符按从小到大的顺序排列可以得到一个字符串\(t\)，我们需要判断的就是此时的\(s\)的\(l\)到\(r\)这一段字符串是不是\(t\)的子串

由题可知，要想为子串，\(s[l...r]\)必须是从小到大的，而且除了最前面的（最小的）和最后面的（最大的）（对于子串，我们都很熟悉，就是一个串删除前面若干个，删除后面若干个），这里面的字符数量都必须和整个字符串里面的字符数量一样，而且还必须连续

我们知道字符的数量不是很大，而且每修改一次，区间里面的字符数量都会改变

所以我们这里给每一个字符都创建了一棵树，用来记录这个字符的分布情况

前面都是很典型的树状数组

但是还有一点需要注意，我们这里的连续的判断，就是每次更新现在的位置，通过现在的位置和该字符的数量，判断这一小段里面是不是都是这一个字符，注意更新最新位置

具体操作可看代码

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include<cmath>
#include <unordered_map>
#include <array>
#include <cstring>
using namespace std;
#define int long long 
#define LL long long
#define ios  ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define inf 1e18
#define INF 1e18
#define mem(a,b) memset((a),(b),sizeof(a))
const double eps=1e-9;
const int maxn=1e5+10;
const int mod=998244353;
int n,q;
string s;
int lowbit(int x)
{
   return x&(-x);
}
struct tree
{
   int bit[maxn];
   void add(int x,int val)
   {
      while (x<=n)
      {
         bit[x]+=val;
         x+=lowbit(x);
      }
   }
   int query(int x)
   {
      int res=0;
      while (x)
      {
         res+=bit[x];
         x-=lowbit(x);
      }
      return res;
   }
   int Query(int l,int r)
   {
      return query(r)-query(l-1);
   }
   
}tr[27];
signed main() 
{
   cin>>n;
   cin>>s;
   s=" "+s;
   for (int i=1;i<=n;i++)
   {
      int now=s[i]-'a';
      tr[now].add(i,1);
   }
   cin>>q;
   while (q--)
   {
      int op;
      cin>>op;
      if(op==1)
      {
         int pos;
         char ch;
         cin>>pos>>ch;
         int last=s[pos]-'a';
         tr[last].add(pos,-1);
         s[pos]=ch;
         int now=s[pos]-'a';
         tr[now].add(pos,1);
      }
      else 
      {
         int l,r;
         cin>>l>>r;
         int mx=0,mi=26;
         for (int i=0;i<26;i++)//还有这个寻找最大最小值，最好不要从字符串的l,r里面寻找，太慢了，我们只要知道这里面有没有这个字符即可
         {
            if(tr[i].Query(l,r)>0)
            {
               mx=max(mx,i);
               mi=min(mi,i);
            }
         }
         int pos=l;
         bool yes=true;
         for (int now=mi;now<=mx;now++)
         {
            int cnt=tr[now].Query(l,r);
            if(now!=mi&&now!=mx)
            {
               int all=tr[now].Query(1,n);
               if(cnt!=all)
               {
                  yes=false;
                  break;
               }
            }
            int ll=pos,rr=pos+cnt-1;
            int tot=tr[now].Query(ll,rr);
            if(tot!=cnt)
            {
               yes=false;
               break;
            }
            pos=rr+1;//注意边界，是rr而不是ll
         }
         if(yes)
         {
            cout<<"Yes\n";
         }
         else 
         {
            cout<<"No\n";
         }
      }
   }
   system ("pause");
    return 0;
}