状态不怎么好 场上就写出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好像才是正统的树的题目 后续补了再更新