【学习笔记】CF1290

出这种猜结论题，我挺无语的

不妨从字符集大小为$2$入手。如果$s_1\ne s_n$那么显然将$s_1$和$s_n$交换就能构造出合法的方案。

最难的地方可能就在于发现这个条件事实上也是充要的。道理很简单，画一个折线图不难发现中间必定有交。

然后是字符集$\ge 3$的情况。我们发现这种情况直接把三种字符顺次拼接起来就做完了。

不过这道题的二级结论居然要用到$s_1=s_n$这个小条件，倒挺令我意外的。

#include<bits/stdc++.h>
#define ll long long
#define pb push_back
using namespace std;
string s;
int n,Q,sum[200005];
vector<int>vec[26];
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    cin>>s,n=s.size();
    for(int i=0;i<n;i++){
     vec[s[i]-'a'].pb(i+1);
 }
    for(int i=2;i<=n;i++){
     sum[i]=sum[i-1]+(s[i-1]==s[i-2]);
 }
    cin>>Q;
    while(Q--){
     int l,r;
     cin>>l>>r;
     if(l==r){
      cout<<"Yes"<<"\n";
  }
  else if(sum[r]-sum[l]==r-l){
   cout<<"No"<<"\n";
  }
  else if(s[l-1]!=s[r-1]){
   cout<<"Yes"<<"\n";
  }
  else{
   int tot=0;
   for(int i=0;i<26;i++){
    int it=lower_bound(vec[i].begin(),vec[i].end(),l)-vec[i].begin();
    if(it!=vec[i].size()&&vec[i][it]<=r){
     tot++;
    }
   }
   if(tot>=3){
    cout<<"Yes"<<"\n";
   }
   else{
    cout<<"No"<<"\n";
   }
  }
 }
}

近期做过最难的交互题了。

逻辑链条有点长。但是我就是卡在第一步 看来大脑该升级了 。

对于每个元素，我们希望求出它之前是否出现过。将$\frac{k}{2}$个元素分成一组，按顺序加入两组元素可以检测后一组的元素是否在前一组出现过。同时，同一组内的相同元素我们也考虑到了。这样一共有$\left(\genfrac{}{}{0ex}{}{\frac{2n}{k}}{2}\right)=\frac{2n^2}{k^2}$对二元组，每次检验需要询问$k$次，总操作次数$\frac{2n^2}{k}$。

不难发现上述做法的瓶颈在于，每次遍历两个块的时候都要清空队列，效率太低。我们先给出，对于一个$n$个点（$n$是偶数）的完全图有一个性质，就是覆盖它的边集最少要用的链的数目是
$\frac{n}{2}$，具体构造是我们枚举$s\in [1,\frac{n}{2}]$，然后按照$s\to s-1\to s+1\to s-2\to s+2$这样的顺序遍历，这样每条边恰好被覆盖一次。这样总操作次数$\frac{k}{2}\cdot \left(\genfrac{}{}{0ex}{}{\frac{2n}{k}}{2}\right)=\frac{n^2}{k}$，可以通过。

这道题最难的部分在于，如何处理$i<j$的限制。我们考虑维护一个集合表示目前没有值与其重复的元素，对于每个$a_i$，如果发现集合中有一个数值与其相同，那么就把$a_i$删去。那么我们只将在集合内的数加入队列中，这样如果查询到有重复的元素，说明这个元素的值还没有被删完，就可以放心把这个元素给删去了。总而言之，相同值的元素最终一定只会保留一个。

$\text{remark}:$ 确实是非常聪明的解法呀。

#include<bits/stdc++.h>
#define ll long long
#define pb push_back
using namespace std;
int n,K,siz,cnt,is[2000];
int qry(int x){
    cout<<"?"<<" "<<x<<endl;
    char c;cin>>c;return (c=='Y');
}
void solve(int x){
    for(int i=(x-1)*siz+1;i<=x*siz;i++){
        if(is[i]&&qry(i)){
            is[i]=0;
        }
    }
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    cin>>n>>K;siz=max(K/2,1),cnt=n/siz;
    for(int i=1;i<=n;i++)is[i]=1;
    for(int i=1;i<=cnt/2;i++){
        int cur=-1;
        for(int j=1;j<=cnt;j++){
            solve((i+j/2*cur+cnt-1)%cnt+1),cur*=-1;
        }
        cout<<"R"<<endl;
    }
    int res=0;
    for(int i=1;i<=n;i++)res+=is[i];
    cout<<"!"<<" "<<res<<endl;
}

数据结构题。不会。所以跳了。

要做这道题，首先必须要知道一个结论：一旦组成凸包的向量的集合确定，这个凸包的形态就是唯一确定的。这是因为，不存在两条向量是平行的。于是问题就转化成了单纯的计数问题。

这道题最难的部分在于，如何优化状态。比如，记$A={\sum }_{x_i>0}{a}_i{x}_i,B={\sum }_{x_i<0}{a}_i{x}_i,C={\sum }_{y_i>0}{a}_i{y}_i,D={\sum }_{y_i<0}{a}_i{y}_i$，那么我们有$A=B\le m,C=D\le m$。

然后我们按二进制位数 从低位到高位 来确定。更确切的说，这是一个更类似于倍增的做法，即从在模$2^k$意义下拓展到模$2^{k+1}$的意义，直到这个模取得足够大的时候，我们就得到了确切的限制。当然，我们同样要记录$A/2^k$的值，以便求出$A\mathrm{mod}{2}^{k+1}$的答案。这其实非常好估计，因为$a_i\in [0,2^k)$，所以$A/2^k\le {\sum }_{x_i>0}{x}_i\le 20$。

至于$A\le m$这个限制，用$0/1$状态记录是否超出即可。

于是只剩下代码难度。复杂度$O(20^4{2}^5\log M)$。

#include<bits/stdc++.h>
#define ll long long
#define pb push_back
using namespace std;
const int mod=998244353;
int n,m,a[35],len;
ll dp[35][25][25][25][25][2][2],X[5],Y[5];
void add(ll &x,ll y){
    x=(x+y)%mod;
}
ll dfs(int x,int A,int B,int C,int D,int f1,int f2){
    if(x>len){
        return !(A||B||C||D||f1||f2);
    }
    if(~dp[x][A][B][C][D][f1][f2])return dp[x][A][B][C][D][f1][f2];
    ll res(0);
    for(int i=0;i<1<<n;i++){
        int A2=A,B2=B,C2=C,D2=D;
        for(int j=0;j<n;j++){
            if(i>>j&1){
                if(X[j]>0)A2+=X[j];
                else if(X[j]<0)B2-=X[j];
                if(Y[j]>0)C2+=Y[j];
                else if(Y[j]<0)D2-=Y[j];
            }
        }
        if(A2%2==B2%2&&C2%2==D2%2){
            add(res,dfs(x+1,A2/2,B2/2,C2/2,D2/2,!(A2%2<a[x]||A2%2==a[x]&&!f1),!(C2%2<a[x]||C2%2==a[x]&&!f2)));
        }
    }
    return dp[x][A][B][C][D][f1][f2]=res;
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    cin>>n>>m;for(int i=0;i<n;i++)cin>>X[i]>>Y[i];
    memset(dp,-1,sizeof dp);
    while(m)a[++len]=m&1,m>>=1;
    cout<<(dfs(1,0,0,0,0,0,0)+mod-1)%mod;
}