练习记录-cf-div2-682(A-D)-526互联

终于场上写出4道，听说E是树链剖分，学的不够深，学完再补感动感动

A. We Need the Zero

题意：求一个数所有数异或上这个数使得所有数是异或和为0

分奇偶考虑，奇数个的情况下，异或这么多次，相当于只异或了1次x，那么先求出原数组的异或和，再异或一遍就是0了，x就是原数组的异或和、

偶数情况下异或偶数次x并不能改变每位1的奇偶性，因此要么输出0，要么输出-1

#include<bits/stdc++.h>
#define close     std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
using namespace std;
typedef long long ll;
const ll MAXN = 3e5+7;
const ll mod =1e9+7;
const ll inf =0x3f3f3f3f;
const ll INF =0x3f3f3f3f3f3f3f3f;

int lowbit(int x){ return x&-x; }
int gcd(int x,int y){int k=0; if(x<y){k=x;x=y;y=k;}while(x%y!=0){k=x%y;x=y;y=k;}return y;}
ll _power(ll a,int b){ll ans=1,res=a;while(b){if(b&1) ans=ans*res%mod;res=res*res%mod;b>>=1;}return ans%mod;}
void solve(){
    int n;int a;
    cin>>n;
    int ans=0;
    for(int i=1;i<=n;i++){
        cin>>a;
        ans^=a;
    }
    if(n%2==1){
        cout<<ans;
    }
    else{
        if(ans!=0) cout<<-1;
        else cout<<"0";
    }
    cout<<"\n";
}
int main(){
    int t;cin>>t;
    while(t--) 
    solve();
}

View Code

B. The String Has a Target

题意：执行一次把后面某一个字母换到最前面的操作，寻找字典序最小的情况

应该是个贪心，优先找最小的相同的情况优先后面

我写了<首字母特判，其实没必要，直接比就好了，如果大于首字母会被首字母替代

意思就是一路记录最小的

#include<bits/stdc++.h>
#define close     std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
using namespace std;
typedef long long ll;
const ll MAXN = 3e5+7;
const ll mod =1e9+7;
const ll inf =0x3f3f3f3f;
const ll INF =0x3f3f3f3f3f3f3f3f;

int lowbit(int x){ return x&-x; }
int gcd(int x,int y){int k=0; if(x<y){k=x;x=y;y=k;}while(x%y!=0){k=x%y;x=y;y=k;}return y;}
ll _power(ll a,int b){ll ans=1,res=a;while(b){if(b&1) ans=ans*res%mod;res=res*res%mod;b>>=1;}return ans%mod;}
void solve(){
    int n;string s;
    cin>>n>>s;
    int cnt=-1;
    for(int i=n-1;i>=0;i--){
        if((s[i]<=s[0]&&cnt==-1)||(cnt!=-1&&s[i]<s[cnt])){
            cnt=i;
        }
    }
    cout<<s[cnt];
    for(int i=0;i<n;i++){
        if(i!=cnt) cout<<s[i];
    }
    cout<<'\n';
}
int main(){
    int t;cin>>t;
    while(t--)
    solve();
}

View Code

C. Place for a Selfie

我这c写的很丑感觉时不时会被hack www

题意：对于每个抛物线找是否有给定直线没有交点

感觉纯纯初中数学题把所有k放进set 然后对于每个抛物线由求根公式(?)求出需要的k

b-√4ab<k<b+√4ab 我求出不等式左边的值然后进行lowwer_bound 考虑到有可能该点刚好相切

就再往后判断一位

为防止精度问题增加下面特判验证

(b-k)*(b-k)-4*a*c<0

#include<bits/stdc++.h>
#define close     std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
using namespace std;
typedef long long ll;
const ll MAXN = 3e5+7;
const ll mod =1e9+7;
const ll inf =0x3f3f3f3f;
const ll INF =0x3f3f3f3f3f3f3f3f;
const double eps =1e-6;
#define int ll
int lowbit(int x){ return x&-x; }
int gcd(int x,int y){int k=0; if(x<y){k=x;x=y;y=k;}while(x%y!=0){k=x%y;x=y;y=k;}return y;}
ll _power(ll a,int b){ll ans=1,res=a;while(b){if(b&1) ans=ans*res%mod;res=res*res%mod;b>>=1;}return ans%mod;}
void solve(){
    int n,m;cin>>n>>m;
    set<int> sz;
    for(int i=1;i<=n;i++){
        int a;cin>>a;
        sz.insert(a);
    }
    for(int i=0;i<m;i++){
        int a,b,c;cin>>a>>b>>c;
        double delta=1.0*b-2.0*sqrt(a*1.0*c);
        int k=delta;
        auto kk=sz.lower_bound(k);
        if(kk!=sz.end()&&(b-*kk)*(b-*kk)-4*a*c<0){//先判断找到的第一个 
            
            cout<<"YES\n";
            cout<<*kk;
        }
        else if(kk!=sz.end()&&((++kk)!=sz.end())&&(b-*kk)*(b-*kk)-4*a*c<0){//再判断第二个 
            cout<<"YES\n";
            cout<<*kk;
        }
        else        cout<<"NO";
        cout<<"\n";
    }
    cout<<"\n";
}
signed main(){
    int t;cin>>t;
    while(t--) 
    solve();
}

View Code

D. A Wide, Wide Graph

一看题目疑似树dp就想着这次必须得做出来上次打的校赛全是树，结果一题没出，丢人死了

题意：给定一棵树，现在再给你一个数字k，只有相距大于等于k的点被连上一条线，求k={1~n}的连通块数量

假如1点与6点连线长度很大，是3，那么k<=3时，1与6都会被选中

因此，就是相当于求某个点为根的最大子树深度，看第k个的时候有几个点符合要求，这几个点都是一个连通块(没有严格证明，但画画应该就知道了) 点数不等于0的时候，就是没有被连接的点的个数+1 否则0

显然每个点跑一边dfs会超时但是这个问题是很明显的树的中心问题即需要求出某点到树上任意点的最长距离用上下dfs(换根dp) 解决即可树的中心模板也是毛的

#include<bits/stdc++.h>
#define close     std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
using namespace std;
typedef long long ll;
const ll MAXN = 3e5+7;
const ll mod =1e9+7;
const ll inf =0x3f3f3f3f;
const ll INF =0x3f3f3f3f3f3f3f3f;
int f[MAXN];
vector<int> adj[MAXN]; 
ll up1[MAXN],up2[MAXN],down[MAXN];
void dfs_down(int u,int fa){
    up1[u]=0,up2[u]=0;
    for(auto &v:adj[u]){//往下寻找下面的最大值 
    int w=1;
        if(v==fa) continue;
        dfs_down(v,u);
        if(up1[v]+w>=up1[u]){//更新最大的 
            up2[u]=up1[u];
            up1[u]=up1[v]+w; 
        }
        else if(up1[v]+w>=up2[u]){//更新第二大的 
            up2[u]=up1[v]+w;
        }
    }
}
void dfs_up(int u,int fa){
    for(auto &v:adj[u]){
        int w=1;
        if(v==fa) continue;
        if(w+up1[v]==up1[u]){
            down[v]=max(up2[u]+1,down[u]+1);
        }
        else{
            down[v]=max(up1[u]+w,down[u]+1);
        }
        dfs_up(v,u);
    }
}
void solve(){
    int n;cin>>n;
    for(int i=0;i<n-1;i++){
        int u,v;cin>>u>>v;
        adj[u].push_back(v);
        adj[v].push_back(u); 
    }
    dfs_down(1,-1);
    dfs_up(1,-1);
    
    for(int i=1;i<=n;i++){
        int x=max(up1[i],down[i]);
        f[x]++;
    }
    for(int i=n-1;i>=1;i--){
        f[i]+=f[i+1];
    }
    for(int i=1;i<=n;i++){
        if(f[i]!=0)
        cout<<n-f[i]+1;
        else cout<<n;
        cout<<" ";
    }
}
int main(){
    solve();
}

View Code

就是要先预处理子树的最深和次深

在由上到下，如果子节点在父节点的最长路径上，就取向下+1与次长+1的最大值，否则取向下+1和最长+1的最大值还是很模板的