首页 > 其他分享 >练习记录-cf-div2-864(A-D)

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

时间:2023-04-09 16:56:24浏览次数:37  
标签:const 864 int ll cf long div2 节点 size

状态不怎么好 场上就写出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();
}
View Code

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();
}
View Code

C. Li Hua and Chess

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

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

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

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

再询问 1,1+a1+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();
}
View Code

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();
}
View Code

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

标签:const,864,int,ll,cf,long,div2,节点,size
From: https://www.cnblogs.com/xishuiw/p/17300560.html

相关文章

  • FastCFS:再谈 选主 与 过半写:续:2节点群集 默认配置下,十分不可靠,几乎100%会发生脑裂问题
     如题:仅能由于测试。千万不要用于生产环境!“选主” 通常能够完成,无法是否有vote参与;问题在于:“过半写”的any或auto模式(即隐含的smart模式)在成功“选主“后,会运行在单节点server的群集模式下,此时,根本就无法且没有完成正常意义上的数据层的主从同步,即必然发生脑裂!数据就不一......
  • 【cf864】赛后结
    属实是失踪人口了,想了一下还是把题解打到这儿。conteset地址:https://codeforces.com/contest/1797 A.题目大意:n*m的方格上给两个点,询问最少增加的障碍格子使得这两个点不连通。解题思路:水题,但是手速有点慢。直接问靠不靠墙,靠几面墙,不靠墙答案4,靠一面答案3,靠两面答案2,取两个点......
  • Codeforces Round 864 (Div. 2)
    评价:A~E感觉出的挺一般,特别是D怎么放这种暴力题,场上我还没调出来,F没看。但是Orzrui_er。A在一个点周围放障碍即可。B求出最少需要的操作次数\(p\),若\(p>k\)就无解,否则若\(n\)为偶数只能任选一个格子翻偶数次,即有解当且仅当\(2\mid(k-p)\);若\(n\)为奇数可......
  • 【题解】CF472G Design Tutorial: Increase the Constraints
    《正解分块+FFT跑1min,__builtin_popcount暴力跑10s》《没人写正解,CF也不卡》思路正解:分块+FFT乱搞:__builtin_popcount首先我们知道哈明距离可以用一种\(O(|字符集||S|)\)的算法求。具体考虑枚举字符集中的每一个字符,将两个串中是该字符的位置看作\(1\),不是该字......
  • FastCFS:再谈 选主 与 过半写
    这二者乍一看好像是一回事:都是要求遵循大多数原则(即过半数原则)。其实,在概念上是不同的! 选主:本质是功能角色的概念。“国不能一日无主、群龙不能无首;否则,则是”一盘散沙、溃不成军“。对于FastCFS组件的群集来说,必须要有master,这个master是在server中自动选出来的,选择mast......
  • FastCFS:FastVote-server的作用、使用的时机
     第一:fastvote-server仅仅是个简单的投票辅助服务器,所谓的投票客户端功能原生集成在fastdir、faststore服务器组件中第二:fastdir、faststore当且仅当 其群集中的servers个数为【偶数】(even)时,才去使用fastvote-server的辅助投票功能第三:当fastdir、faststore的配置中,servers......
  • CF1810E 题解
    一、题目描述:给你一个n个点,m条边的无向图,点带权,起点可任意选择。每走过一个新的点,你的能力值会+1。一开始你的能力值为0。你只能经过点权小于等于你能力值的点。每条边,每个点都可以经过无限次,问能否走遍整个图。如果可以,输出"YES"。否则输出"NO"。......
  • cf-edu-146b
    题目链接:https://codeforces.com/contest/1814/problem/B只有残缺的思路,还不足以解决这道题。完整思路:对于一个数x来说,如果一个数a除以它的余数为y,商为z,所需步数为y+z+(x-1),那么反过来(x变为它的商,z为除数,所需步数依然是不变的,可以举几个例子看看,易得。),所以我们只需要枚举\(n^(......
  • 4月CF杂题
    CodeforcesRound862(Div.2)E.ThereShouldBeaLotofMaximums题意:定义一棵点有颜色的树的\(\text{MAD}\)为树上编号最大的出现了至少两次的颜色。对于树上每条边,求出断开它后生成的两棵树的\(\text{MAD}\)的最大值。\(n\le2\times10^5,a_i\le10^9\)。先找到整棵树......
  • 3d打印 LCD2004/12864显示不清楚 正面看不清 背光太强 的问题
    第一次买相关配件,没经验解决方法:背面有一个调节显示电压的旋钮。背光强调低点,字体弱,调高点。背部调节电压的旋钮:   原因:用专业语言就是液晶屏鬼影和字浅,鬼影是本不该显示的内容显示出来了,一般是电路供给液晶屏的电压高于液晶屏的工作电压造成的;字浅就是液晶屏上的内容颜......