练习记录-cf-div2-864（A-D)

状态不怎么好 场上就写出3道 还磨磨蹭蹭推错结论qwq  警钟长鸣

A. Li Hua and Maze

一开始以为要切割 发现就把其中一个包起来就行了 计算包某个块需要的最小块数

#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,m;cin>>n>>m;
    int ans=4;
    for(int i=0;i<2;i++){
        int res=4;
        int x,y;cin>>x>>y;
        if(x==1||x==n) res--;
        if(y==1||y==m) res--;
        ans=min(ans,res);
    }
    cout<<ans<<"\n";
}
int main(){
    int t;cin>>t;
    while(t--) 
    solve();
}

B. Li Hua and Pattern

求变成中心对称（？）图形需要的变化次数 我遍历一整个图 与 （n+1-i，n+1-j）不一样的就++，因为图对称 所以/2 就行了

#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;
#define int long long
int a[1004][1004];
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;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            cin>>a[i][j];
        }
    }
    int sum=0;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            if(a[i][j]!=a[n+1-i][n+1-j]) sum++;
        }
    }
    sum/=2;
    if(m>=sum&&((m-sum)%2==0||n%2==1)) cout<<"YES\n";
    else cout<<"NO\n";
}
signed main(){
    int t;cin>>t;
    while(t--)
    solve();
}

C. Li Hua and Chess

问三次 每次给移动到询问点的次数 即（x-x1)(y-y1)的绝对值的最大值 

本来在三点定位 结果发现特殊情况可以有重复的数 无法求

其实就是 先问 1 1 回答a 之后 这样就知道 点肯定在x=1+a 或者y=1+a

如果其中一个越界 那么肯定在另一条线上 

再询问 1，1+a 和1+a 1 如果距离还是a 就表示在对面线上 否则就可以确定点的x或者y

自己演示一下会很清楚

#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;
#define int long long 
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,x,y;cin>>n>>m;
    int a,b,c;
    cout<<"? 1 1"<<endl;
    cin>>a;
    int xx=a+1,yy=a+1;
    if(xx>n){
        y=yy;
    }
    else{
        cout<<"? "<<xx<<" 1"<<endl;
        cin>>b;
        y=min(b+1,yy);
    }
    if(yy>m){
        x=xx;
    }
    else{
        cout<<"? 1 "<<yy<<endl;
        cin>>c;
        x=min(c+1,xx); 
    }
    

    
    cout<<"! "<<x<<" "<<y<<endl;
    fflush(stdout) ;
}
signed main(){
    int t;cin>>t;
    while(t--)
    solve();
}

D. Li Hua and Tree

写到这个只有20分钟了 以为是树剖 写不出 就和朋友吹水去了 补题的时候一看是模拟 哈哈 

甚至不需要维护hson（最重的子树） 只需要把所有节点的子节点全塞入set中即可

当交换一个节点时 

　　1 子树大小： 父节点不变 该节点变成 ->该节点-子节点 子节点变成原该节点大小

　　2 子树的重要性： 与子树大小变化一致

　　3 重树维护：把父节点的set中的该节点删去，把该节点的最重节点删去，父节点的set加上子节点，字节点的set加上该节点的set

　　4 父节点更新： 把子节点更新父节点，该节点更新为子节点

用set执行以上操作 就解决题目啦~ 值得注意的是 set中 由于从小到大 因此 不会重载的可以把树的大小反着塞（我写了个greater<int> 反着塞节点序号 但是不知道为什么塞不进去

以下是代码

#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;
#define int long long
int f[MAXN],deep[MAXN],size[MAXN],sum[MAXN],a[MAXN];
vector<int> adj[MAXN];
set<pair<int,int>> hson[MAXN];
int tree_build(int u,int fa,int dep){
    deep[u]=dep;
    size[u]=1;
    sum[u]=a[u];
    f[u]=fa;
    for(auto &v:adj[u]){
         if(v==fa)continue;
         f[v]=u;
        tree_build(v,u,dep+1);
        size[u]+=size[v];
        sum[u]+=sum[v];
        hson[u].insert({-size[v],v});
    }
}
void solve(){
    int n,m;cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>a[i];
    for(int i=1;i<n;i++){
        int u,v;cin>>u>>v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    //    f[v]=u;
    }
    tree_build(1,-1,0);
//    for(int i=1;i<=n;i++){
//        cout<<"# "<<i<<":"<<a[i]<<" "<<sum[i]<<" "<<size[i]<<"\n";
//    }
    for(int i=1;i<=m;i++){
        int op,x;cin>>op>>x;
        if(op==1){
            cout<<sum[x]<<"\n";
            continue;
        }
        else{
            if(size[x]==1) continue;
            int u=hson[x].begin()->second;
            hson[f[x]].erase({-size[x],x});
            hson[f[x]].insert({-size[x],u});
            int t=sum[x];
            sum[x]-=sum[u];
            sum[u]=t;
            t=size[x];
            size[x]-=size[u];
            size[u]=t;
            hson[u].insert({-size[x],x});    
            hson[x].erase(hson[x].begin());
            f[u]=f[x];
            f[x]=u; 
        //    int k=1;
        }
//    cout<<"After op :"<<i<<"\n";
//    for(int i=1;i<=n;i++){
//        cout<<"# "<<i<<":"<<a[i]<<" "<<sum[i]<<" "<<size[i]<<"\n";
//    }
    }
}
signed main(){
    solve();
}

E好像才是正统的树的题目 后续补了再更新