A
signed main(){
int l,r;cin>>l>>r;
if(!(l==1&&r==1||l!=1&&r!=1)){
if(l==1)cout<<"Yes\n";
else cout<<"No\n";
}
else cout<<"Invalid\n";
}
B
signed main(){
int n;cin>>n;
F(i,1,n)F(j,1,i)cin>>a[i][j];
int now=1;
F(i,1,n)
if(i>=now)now=a[i][now];
else now=a[now][i];
cout<<now<<'\n';
}
C
观察到 \(n\) 很小，因此考虑暴力枚举每一个满足 \(s_i\neq t_i\) 的 \(i\) 并计算出修改这个位置的 \(s_i\) 为 \(t_i\) 之后的字符串，将所有这样的字符串集合 \(S\) 按照字典序从小到大排序之后贪心选择当前字典序最小的即可。时间复杂度为 \(O(n^3\log n)\)。
const int N=1000100,mod=1e9+7;
char s[N],t[N];
signed main(){
scanf("%s%s",s+1,t+1);
vector<string>v;
int n=strlen(s+1);
int cnt=0;
F(i,1,n)
if(s[i]!=t[i])++cnt;
F(i,1,cnt){
vector<pair<string,int> > tv;
F(p,1,n){
if(s[p]!=t[p]){
char tt=s[p];
s[p]=t[p];
string o;
F(j,1,n)o.push_back(s[j]);
tv.eb(o,p);
s[p]=tt;
}
}
sort(rng(tv));
s[tv[0].second]=t[tv[0].second];
v.eb(tv[0].first);
}
cout<<v.size()<<'\n';
for(auto &x:v)
cout<<x<<'\n';
}
D
考虑开 \(2n\) 个 set 分别记录 每一行 / 每一列 所有有障碍物的位置，然后查询位置 \((x,y)\)：
- 若 \((x,y)\) 有障碍物，则直接删除。
- 否则在
set上二分找出 \((x,y)\) 上面、下面、左边、右边第一个障碍物的位置。
然后更新 \(2n\) 个 set 即可。注意到一次最多只可能删除 \(4\) 个位置，且每一个位置最多只会被删除一次，因此总的时间复杂度为 \(O((nm+q)\log nm)\)。
set<int>s1[N],s2[N],s3[N],s4[N];
signed main(){
// freopen(".out","w",stdout);
int n,m,q;cin>>n>>m>>q;
mp.resize(n+3);
zuo.resize(n+3);
you.resize(n+3);
shang.resize(m+3);
xia.resize(m+3);
set<PII>se;
F(i,1,n)F(j,1,m)se.insert({i,j});
F(i,1,n)F(j,1,m)s1[i].insert(j);
F(i,1,m)F(j,1,n)s2[i].insert(j);
while(q--){
int x,y;cin>>x>>y;
if(se.count({x,y})){
s1[x].erase(y);
s2[y].erase(x);
se.erase({x,y});
}else{
auto i1=s1[x].upper_bound(y);
vector<PII>cx;
if(i1!=s1[x].end()){
int _x=x,_y=*i1;
cx.eb(_x,_y);
se.erase({_x,_y});
}
if(i1!=s1[x].begin()){
--i1;
int _x=x,_y=*i1;
cx.eb(_x,_y);
se.erase({_x,_y});
}
i1=s2[y].upper_bound(x);
vector<PII>cy;
if(i1!=s2[y].end()){
int _x=*i1,_y=y;
cy.eb(_x,_y);
se.erase({_x,_y});
}
if(i1!=s2[y].begin()){
--i1;
int _x=*i1,_y=y;
// cout<<"wtf "<<_x<<' '<<_y<<'\n';
cy.eb(_x,_y);
se.erase({_x,_y});
}
for(auto &[_x,_y]:cx)
s1[x].erase(_y),s2[_y].erase(x);
for(auto &[_x,_y]:cy)
s2[y].erase(_x),s1[_x].erase(y);
}
// for(auto &[x,y]:se)
// cout<<"qwq "<<x<<' '<<y<<'\n';
// cout<<'\n';
}
cout<<se.size()<<'\n';
}
E
设 \(f_i\) 表示当前枚举到的连续子序列以 \(i\) 结尾的不同方案数，显然答案为 \(\sum\limits_{i=1}^n f_i\)，若 \(1\le j\le i\) 且 \(j\sim i\) 一段区间的和不为 \(k\) 则 \(f_i\leftarrow f_j\)。因此可以做到 \(O(n^2)\)。
考虑优化，设 \(g_i\) 表示当前前缀和为 \(i\) 的 \(f\) 值的和，则 \(g\) 的转移容易，\(f_i\) 的转移可以优化为 \(f_i=(\sum\limits_{j=0}^{i-1} f_j)-g_{(\sum\limits_{j=1}^i a_i)-k}\)
其中 \(\sum\limits_{j=0}^{i-1} f_j\) 和 \(\sum\limits_{j=1}^i a_i\) 都可以处理出，因此这样计算时间复杂度为 \(O(n\log n)\)，瓶颈在于 map。
\(O(n^2)\) 代码
const int N=500100,mod=998244353;
int a[N],s[N],n,k,f[N];
signed main(){
cin>>n>>k;
F(i,1,n)cin>>a[i],s[i]=s[i-1]+a[i];
f[0]=1;
F(i,1,n){
F(j,1,i)
if(s[i]-s[j-1]!=k)
f[i]=(f[i]+f[j-1])%mod;
}
cout<<f[n]<<'\n';
}
\(O(n\log n)\) 代码
const int N=500100,mod=998244353;
int a[N],s[N],n,k,f[N];
map<int,int>g;
signed main(){
cin>>n>>k;
F(i,1,n)cin>>a[i],s[i]=s[i-1]+a[i];
f[0]=1;
g[0]=1;
int all=1;
F(i,1,n){
f[i]=all-g[s[i]-k];
f[i]%=mod;f[i]+=mod;f[i]%=mod;
all+=f[i];
all%=mod;
g[s[i]]+=f[i];
}
cout<<f[n]<<'\n';
}
F
首先套路的破换成链，然后二分答案 \(p\)。
对于每一个二分的答案 \(p\)，考虑先二分出 \(f_{i,0}\) 表示 \(i\) 之后第一个满足 \(\sum\limits_{j=i}^{f_{i,0}} a_j\ge p\) 的 \(f_{i,0}\)，然后倍增的设 \(f_{i,j}\) 表示 \(i\) 之后满足 \(2^j\) 次上述条件的下标为 \(f_{i,j}\)。特殊的若不可以满足则令 \(f_{i,j}=-1\)。
然后考虑枚举起点，直接暴力倍增计算出 \(k\) 次操作之后的答案即可。时间复杂度为 \(O(n\log^2n)\)。代码有点混乱。
const int N=400100,mod=998244353;
int a[N],s[N],n,k,now,nxt[N][20],res;
bool chk(int p){
memset(nxt,-1,sizeof nxt);
F(i,1,n+n){
int l=i,r=i+n-1,best=-2;
r=min(r,n+n);
while(l<=r){
int mid=l+r>>1;
if(s[mid]-s[i-1]>=p)best=mid,r=mid-1;
else l=mid+1;
}
nxt[i][0]=best+1;
}
nxt[n+n+1][0]=n+n+1;
F(i,1,19)
F(j,1,n+n+1)
if(~nxt[j][i-1])
nxt[j][i]=nxt[nxt[j][i-1]][i-1];
// F(i,1,n+n)
// cout<<i<<": "<<nxt[i][0]<<' '<<nxt[i][1]<<" qwq\n";
int cnt=0;
F(i,1,n){
int x=i;
G(j,19,0)
if(k>>j&1){
x=nxt[x][j];
if(x==-1||x>i+n)break;
}
if(x!=-1&&x<=i+n)
++cnt;
}
if(cnt)
res=n-cnt;
return !!cnt;
}
signed main(){
cin>>n>>k;
F(i,1,n)cin>>a[i],s[i]=s[i-1]+a[i];
F(i,1,n)a[i+n]=a[i],s[i+n]=s[i+n-1]+a[i];
int l=1,r=s[n],best=-1;
while(l<=r){
int mid=l+r>>1;
if(chk(mid))best=mid,l=mid+1;
else r=mid-1;
}
cout<<best<<' '<<res<<'\n';
}