AtCoder Beginner Contest 285（B,D,E,F)
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 (图，拓扑排序)
为什么每次我都没有看懂题意，好难过
这个题的大意就是每个人都会使用一个字符串\(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,前缀和）
这个题目的大意就是有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(树状数组)
这个题大意很简单，就是给你一个字符串，有两种操作
一种是需要把\(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;
}