首页 > 其他分享 >Codeforces Round 864(Div.2) A~C

Codeforces Round 864(Div.2) A~C

时间:2023-07-04 19:24:11浏览次数:55  
标签:结点 cin int siz sum 864 Codeforces Div.2 son

vp过三题,c是交互题,想起了打华师大校赛时的不愉快经历了。

A.Li Hua and Maze

Problem - A - Codeforces

题意

给定一个n×m的矩阵,矩阵中有两个点(x1,y1),(x2,y2)。可以往矩阵中添加障碍物,使两个点之间不存在任何路径,求添加的障碍物数量最少为多少。

思路

可以把其中一个点的四周围起来,这样两点之间就不存在任何路径,所以答案最多为4。若有点的位置在边界处,所到的障碍就不到4个。

所以计算把两个点围起来所用的障碍物数量最少分别是多少,最终的答案就是较少的那个。

代码

void solve() {
    int n, m;
    cin >> n >> m;
 
    int x1, y1, x2, y2;
    cin >> x1 >> y1 >> x2 >> y2;
 
    int t1 = (x1 != 1) + (x1 != n) + (y1 != 1) + (y1 != m),
        t2 = (x2 != 1) + (x2 != n) + (y2 != 1) + (y2 != m);

    cout << min(t1, t2) << "\n";
}

B.Li Hua and Pattern

Problem - B - Codeforces

题意

给定一个n×n的矩阵,其中每个元素为0或1。定义操作,把一个值为0的元素修改为1,或把一个值为1的元素修改为0。要求必须进行k次操作,使原矩阵变成一个中心对称的矩阵(即倒转180度后矩阵不变)。如果可以,输出YES,否则输出NO。

思路

遍历一遍,记录关于中心对称位置的元素不同的个数cnt。

如果n为奇数,那么只要cnt不大于k则为YES,否则为NO。因为修改完不同的元素后,剩下的操作次数全用于中心位置的元素即可,修改中心位置的元素不影响该矩阵是否符合要求。

如果n为偶数,则在cnt不大于k的同时,(k - cnt)还要为一个偶数才为YES。这是因为此时矩阵没有中心点,修改其它位置的元素会影响其对称性,所以需要剩余的修改次数为偶数,这样使得修改后还能在修改回去。

代码

void solve() {
	int n ,k;
	cin >> n >> k;
 
	vector<vector<int>> v(n+1, vector<int>(n+1));
	for(int i = 1; i <= n; i++) {
		for(int j = 1; j <= n; j++) {
			cin >> v[i][j];
		}
	}
 
	int cnt = 0;
	for(int i = 1; i <= n / 2; i++) {
		for(int j = 1; j <= n; j++) {
			if(v[i][j] != v[n-i+1][n-j+1]) cnt++;
		}
	}
 
	if(n & 1) {
		for(int i = 1; i <= n / 2; i++) {
			if(v[n/2+1][i] != v[n/2+1][n-i+1]) cnt++;
		}
		if(cnt <= k) cout << "YES\n";
		else cout << "NO\n";
	}
 
	else {
		if(cnt <= k && (k - cnt) % 2 == 0) cout << "YES\n";
		else cout << "NO\n";
	}
}

C.Li Hua and Chess

Problem - C - Codeforces

题意

交互题,给定一个n×m棋盘和棋盘上的一个皇后,皇后一步可以向四周9个点移动。每次询问一个点,交互机给出皇后到这个点最短所需的步数,最多询问三次,确定皇后的位置。

思路

第一次询问点(1,1),得到步骤d1。如果d1为4,那么所有可能的点如下图:

我们再询问点(1,d1+1)和点(d1+1,1),即可确定皇后的位置。

但要注意,有时候d1+1大于n或m,需要特判。

代码

void solve() {
	int n, m;
	cin >> n >> m;
 
	cout << "? 1 1" << "\n";
	cout.flush();
 
	int a1, a2 = 0, a3 = 0;
	cin >> a1;
 
	if(a1 == 0) {
		cout << "! 1 1" << "\n";
		cout.flush();
		return;
	}
 
	if(a1 + 1 <= m) {
		cout << "? 1 " << a1 + 1 << "\n";
		cout.flush(); cin >> a2;
		if(a2 == 0) {
			cout << "! 1 " << a1 + 1 << "\n";
			cout.flush();
			return;
		}
	}
	if(a1 + 1 <= n) {
		cout << "? " << a1 + 1 << " 1" << "\n";
		cout.flush(); cin >> a3;
		if(a3 == 0) {
			cout << "! " << a1 + 1 << " 1" << "\n";
			cout.flush();
			return;
		}
	}
 
	if(a2 != 0 && a3 != 0) {
		if(a2 == a1) {
			cout << "! " << a1 + 1 << " " << a3 + 1 << "\n";
			cout.flush();
		} else {
			cout << "! " << a2 + 1 << " " << a1 + 1 << "\n";
			cout.flush();
		}
	} else {
		if(a2 == 0) {
			cout << "! " << a1 + 1 << " " << a3 + 1 << "\n";
			cout.flush();
		} else {
			cout << "! " << a2 + 1 << " " << a1 + 1 << "\n";
			cout.flush();
		}
	}
}

D. Li Hua and Tree

Problem - D - Codeforces

题意

给定一个有n个结点和n - 1条边的树,每个结点有权值。在一个结点的所有子结点中,子结点数最多的称为该结点的重子结点。

有两种操作,”1 x“表示输出以结点x为根节点为子树的权值和,”2 x“表示把x结点变成重子结点的子结点,而该重子结点则代替原来的x结点。

思路

模拟,用邻接表建树,dfs遍历得出每一个结点的子结点数量,子树权值和,父结点,用set维护每个结点的重子结点。操作1直接输出x的子树权值和,操作2按题意模拟即可。

代码

#include<bits/stdc++.h>

using namespace std;
using ll = long long;
const int N = 1e5+10;

struct node {
    int siz, id;
    bool operator <(const node &t) const {
        if(siz != t.siz) return siz > t.siz;
        return id < t.id;
    }
};
set<node> s[N];

vector<int> adj[N];
vector<int> a(N), siz(N), p(N);
vector<ll> sum(N);

void dfs(int u, int fa) {
    siz[u] = 1;
    sum[u] = a[u];
    for(int v : adj[u]) {
        if(v == fa) continue;
        p[v] = u;
        dfs(v, u);
        sum[u] += sum[v];
        siz[u] += siz[v];
        s[u].insert({siz[v], v});
    }
}

int main () {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    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);
    }

    dfs(1, -1);

    while(m--) {
        int opt, x;
        cin >> opt >> x;
        if(opt == 1) {
            cout << sum[x] << "\n";
        } else {
            if(s[x].empty()) continue;
            int son = s[x].begin()->id;
            s[p[x]].erase({siz[x], x});
            s[x].erase(s[x].begin());
            int t_siz = siz[son];
            ll t_sum = sum[son];
            sum[son] = sum[x];
            siz[son] = siz[x];
            sum[x] -= t_sum;
            siz[x] -= t_siz;
            s[p[x]].insert({siz[son], son});
            s[son].insert({siz[x], x});
            p[son] = p[x];
            p[x] = son;
        }
    }

    return 0;
}

标签:结点,cin,int,siz,sum,864,Codeforces,Div.2,son
From: https://www.cnblogs.com/cenqi/p/17526773.html

相关文章

  • codeforces 树上题目总结
    codeforces树上题目总结CF1559D2先猜一个结论——一定能通过加边让一个森林变成一棵树,归纳一下发现是对的,并且随便加合法的边都符合条件,所以暴力是\(\mathcalO(n^2)\)的。那么考虑如何降低复杂度。我并没有想到。我一直是在往快速找到两个不属于同一集合的点这个方向思考的......
  • Codeforces 293B Distinct Paths
    发现\(n,m\)的数据范围是假的,因为每一步一个颜色最多也就\(k\le10\)种颜色,所以当\(n+m-1>k\)时一定无解。接下来发现这个数据范围挺小的,考虑状压,设\(f_{x,y}\)为走到\((x,y)\)点所用的颜色的集合,其可以由\(f_{x-1,y},f_{x,y-1}\)推来。然后就可以......
  • Codeforces Round 878 (Div3)
    B.BinaryCafe\(1\leqn,k\leq10^9\)题解:思维考虑两种情况第一种:钱足够多,每种咖啡都可以买的情况下,答案为\(2^k\)第二种:钱不够多,因为任一面值的钱数都有唯一的二进制表达方式,所以答案为\(n+1\)所以我们不妨先判断一下\(2^k\)有没有超过\(10^9\),如果超过了说明钱......
  • CodeForces 1508D Swap Pass
    洛谷传送门CF传送门先忽略掉所有\(a_i=i\)的点。考虑我们钦定一个点\(s\),每次与\(a_s\)换直到\(a_s=s\)为止。不难发现这样相当于在置换环上删掉\(a_s\)这个点。这样可以解决\(s\)所在的环。问题是可能会形成很多个环。我们把其他点按照\(s\)极角排序,注意......
  • Codeforces 585D Lizard Era: Beginning
    很容易想到可以对于每个任务选不去的那一个人进行搜索,时间复杂度\(O(3^n)\),明显过不了。发现\(n\le25,\lceil\frac{n}{2}\rceil\le13\),且各个任务间不会互相影响,便可以用折半搜索分成\(2\)部分来搜最后来合并。考虑如何合并两部分,令前一部分得到的值分别为\(a,b,c\),后......
  • Codeforces Round 881 Div2 A-F1题解
    codeforcesround881div2题解马上要秋招了,自己本事全丢了,感觉如果这样的话今年就估计要饿死了。先打div3,7月份得开始收心了A.SashaandArrayColoring题意,可以分任意组,每组的贡献是max-min,问最大贡献显然是贪心,从大到小配对一下就行,不想放代码了’B.LongLong给出一......
  • Codeforces Round #877 (Div. 2) A-E
    A代码#include<bits/stdc++.h>usingnamespacestd;usingll=longlong;boolsolve(){intn;cin>>n;intmx=-2e9,mi=2e9;for(inti=1;i<=n;i++){intx;cin>>x;mi=min(x,mi);......
  • Educational Codeforces Round 151 (Rated for Div. 2)
    Preface期末考终于结束了,终于可以回来写题了这场是刚考完最后一门的那个晚上打的,因为太久没有写代码了所以不是很熟练而且脑子也不太灵光,只能堪堪写到D题而且手速感人上次CF第二个号因为Rating被roll了导致从紫名掉下来了,这场就把它又打上去了,再这样后面兴许要用第三个号打了......
  • Educational Codeforces Round 151 [div.2 #A-C] 赛后总结(contest/1845)
    link\(\textcolor{lightgreen}{A}-\textcolor{yellow}{B}-\textcolor{yellow}{C}-\textcolor{red}{D}-\textcolor{red}{E}-\color{red}{F}\)A给你一个数n,在给你一个数列1~k,其中x不能用,然后用其他的数任意累加,如能得到n,输出所用数字数量和具体数列。一眼分类。先分是......
  • CodeForces 高分段 dp 选做
    选取方式:CF*3000+按通过人数排序。CF1188DMakeEqual记\(cnt(x)\)表示\(x\)二进制下\(1\)的个数,题目等价于求\(x\)使得\[\sum_{x=1}^ncnt(x+a_n-a_i)\]最小。令\(a_i=a_n-a_i\)。从低位到高位考虑,假设当前要决策第\(k\)位,我们需要知道:\(1.\)\(x\)......