一些杂题（9.23）

八月赛

A. Extra Large Knapsack

我的思路

是否可行只要看所有异或在一起是否为0就可以了

可行的方案只要有一个在第一个包里，剩下的都在第二个包里就可以了

注意：n==1的时候不可行，要特判

代码

#include
using namespace std;
int main()
{
    ios::sync_with_stdio(0);cin.tie(0);
    int T;cin>>T;
    while(T--){
        int n;cin>>n;int sum=0,w=0;
        for(int i=0;i
            cin>>w;
            sum=sum^w;
        }
        if(n!=1&&!sum){
            cout<<"Yes\n";
            cout << 0;
            for(int i = 1; i < n; i++) cout << 1;
            cout<<'\n';
        }
        else{
            cout<<"No\n";
        }
    }
    return 0;
}

P4551 最长异或路径

P4551 最长异或路径t

题意：

前置知识 字符串Trie

之前学过string中的Trie，一个节点一共有26个指针，u是当前节点的编号，a[u][c-'a']用来存储下一个结点的序号

思路 XOR Trie+贪心

一道相比较而言更简单的题目：#10050.  The XOR Largest Pair 

上面这道题目中，把每个在a数组里的数字都遍历了，找a[i]能够找到的异或最大值，更新最后的最大值就可以了；因为一个数字最长32位，顺着Trie下去找32次就可以了；所以总时间复杂度是O(32n)

代码

注意1<<31要 long long

#include
using namespace std;
#define int long long
int a[10000005][2];int ans=0;int v[100005];int cnt=0;
void insert(int x){
    int p=0;
    for(int i=(long long)1<<31;i;i>>=1){
        if(i&x){
            if(!a[p][1]){a[p][1]=++cnt;}
            p=a[p][1];
        }
        else{
            if(!a[p][0]){a[p][0]=++cnt;}
            p=a[p][0];
        }
    }//上面在造树
    return;
}
int search(int x){
    int p=0;int sum=0;
    for(int i=(long long)1<<31;i;i>>=1){
        int flag=i&x;
        if(i&x){//如果当前是1，那就要找0
            if(a[p][0]){//如果0存在的话
                p=a[p][0];sum=sum|i;
            }
            else p=a[p][1];
        }
        else{
            if(a[p][1]){//如果1存在的话
                p=a[p][1];sum=sum|i;
            }
            else p=a[p][0];
        }
    }
    return sum;
} 
signed main()
{
    int n;cin>>n;
    for(int q=0;q
        cin>>v[q]; insert(v[q]);
    }
    for(int q=0;q
        ans=max(ans,search(v[q]));
    }
    cout<
    return 0;
}

会了上面这道题，再来看看P4551

思路

可以分为两个子问题，(1)所有结点到根结点的距离D(x) （2）D(x)数组中两个最大的异或和

第一个子问题可以用dfs来解决；第二个子问题可以用上面的01树解决

#include
using namespace std;
#define int long long
vectorint,int> >mp[100004];int n;
int D[100005];
int a[10000006][2];int cnt=0;int sum=0;
void dfs(int x,int fa,int w){
     for(auto q:mp[x]){
          D[x]=D[fa]^w;//
          if(q.first==fa)continue;
          dfs(q.first,x,q.second);
     }
}
void tinsert(int x){
    int p=0;
    for(int i=(long long)1<<31;i;i>>=1){
        if(i&x){
            if(!a[p][1]){a[p][1]=++cnt;}
            p=a[p][1];
        }
        else{
            if(!a[p][0]){a[p][0]=++cnt;}
            p=a[p][0];
        }
    }//上面在造树
    return;
}
int search(int x){
     int p=0;int ans=0;
     for(int i=(long long)1<<31;i;i>>=1){
          bool flag=i&x;
          if(a[p][!flag]){ans=ans|i;p=a[p][!flag];}
          else
               p=a[p][flag];
     }
     return ans;
}
signed main()
{
     cin>>n;
     for(int i=0;i-1;i++){
          int u,v,w;cin>>u>>v>>w;
          mp[u].push_back({v,w}); mp[v].push_back({u,w});
     }//树建好了
     dfs(1,0,0);//D[x]准备好了
     for(int i=1;i<=n;i++) tinsert(D[i]);//建字典树
     for(int i=1;imax(sum,search(D[i]));
     cout<
     return 0;
}

CF126B Password

给你一个字符串S（|S|<=1000000），找到既是S前缀又是S后缀又在S中间出现过（既不是S前缀又不是S后缀）的最长子串，如果不存在输出“Just a legend”。

方法一 哈希

要注意的是找最长的字符串 符合二分的特性

#include
using namespace std;
const int N = 1000000 + 5;
const unsigned long long base = 163;
string s;
unsigned long long has[N];
unsigned long long p[N];int n;
//unsigned long long 自动 mod 2^64
//s[]是读入的数组
//p[]预处理存储p的n次方，计算区间时候会用到
//hash[]存储对应字符串的哈希值
void init(){ //处理hash值
   p[0]=1; //p的0次方为1
   has[0]=0;
   n = s.size()-1;
   for(int i=1;i<=n;i++) p[i]=p[i-1]*base;
   for(int i=1;i<=n;i++) has[i]=has[i-1]*base+(s[i]-'a');
}
unsigned long long get(int l, int r){//取出g里[l,r]里面的字符串的hash值
    return has[r]-has[l-1]*p[r-l+1];
}
int main()
{
     cin>>s;s='#'+s;
     init();vector<int> dp;//从1开始到flag都是
     for(int i=1;i//可以不等于n，因为如果是n就是字符串自己了 // 不可以break
          if(get(1,i)==get(n-i+1,n)) {
               dp.push_back(i);
          }
     }
     int l=0,r=dp.size()-1,ans=0,mid;
     while(l<=r){
          mid=(l+r)/2;bool flag=0;
          for(int i=2;i+dp[mid]-1//dp[mid]是长度，不等于n是因为不能和后缀的相同
               if(get(1,dp[mid])==get(i,i+dp[mid]-1)){
                    ans=dp[mid];l=mid+1;
                    flag=1;break;//存在就可以break了
               }
          }
          if(!flag)r=mid-1;
     }
     if(!ans)cout<<"Just a legend\n";
     else cout<substr(1,ans);
 
     return 0;
}