首页 > 编程语言 >2022“杭电杯”中国大学生算法设计超级联赛（10） 题解

2022“杭电杯”中国大学生算法设计超级联赛（10） 题解

时间：2022-08-25 21:44:24浏览次数：84  
标签：10 cnt ch int 题解 pos ++ MAXN 2022

C. Wavy Tree

发现修改次数和相邻两数的相对大小有关，所以可先求出差分数组。

分两种情况考虑：① 奇数位置为波峰 ② 偶数位置为波峰。

以情况 ① 为例，若奇数位置差分后值小于等于0则不合法，需要修改至1；若偶数位置差分后值大于等于0则不合法，需要修改至-1。

情况 ② 同理。

#include<bits/stdc++.h>
#define int long long
using namespace std;

const int MAXN = 1e6 + 5;

int n, a[MAXN], b[MAXN], d[MAXN];

int Solve(int x) {
	int res = 0;
	for(int i = 1; i <= n; i++) a[i] = d[i];
	//for(int i = 1; i <= n; i++) cout << a[i] << " "; cout << " a\n"; 
	for(int i = 2; i <= n; i++) {
		if(i % 2 == x) {
			if(a[i] <= 0) {
				int c = 1 - a[i];
				res += c;
				a[i + 1] -= c;
				a[i] = 1;
			}
		} else {
			if(a[i] >= 0) {
				int c = a[i] + 1;
				res += c;
				a[i + 1] += c;
				a[i] = -1;
			}
		}
	}
	return res;
}

void Solve() {
	cin >> n;
	for(int i = 1; i <= n; i++) cin >> b[i];
	for(int i = 1; i <= n; i++) d[i] = b[i] - b[i - 1];
	
	int ans = min( Solve(0), Solve(1) );
	cout << ans << "\n";
}

signed main()
{
	ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	int T; cin >> T;
	while(T--) Solve();
	return 0;
}

D. Average Replacement

猜了两个结论：① 同一个连通块的所有点最后值相等；② 同一个连通块内 \(\sum (deg_i+1)a_i\) 为定值，其中 \(deg_i\) 为 \(i\) 的度数。

最后猜了每个连通块中点的值则为 \(\frac{\sum(deg_i+1)a_i}{\sum(deg_i+1)}\)。

#pragma GCC optimize(2)
#include<bits/stdc++.h>
using namespace std;

namespace fastIO{
	#define BUF_SIZE 100000
	#define OUT_SIZE 100000
	#define ll long long
	bool IOerror=0;
	int qr;
	char obuf[OUT_SIZE],*oS=obuf,*oT=oS+OUT_SIZE-1,qu[55];
	inline void flush(){
		fwrite(obuf,1,oS-obuf,stdout);
		oS=obuf;
	}
	inline char nc(){
		static char buf[BUF_SIZE],*p1=buf+BUF_SIZE,*pend=buf+BUF_SIZE;
		if (p1==pend){
			p1=buf;pend=buf+fread(buf,1,BUF_SIZE,stdin);
			if(pend==p1){IOerror=1;return -1;}
		}
		return *p1++;
	}
	inline bool blank(char ch){return ch==' '||ch=='\n'||ch=='\r'||ch=='\t';}
	inline void read(int &x){
		bool sign=0; char ch=nc(); x=0;
		for(;blank(ch);ch=nc());
		if(IOerror)return;
		if(ch=='-')sign=1,ch=nc();
		for(;ch>='0'&&ch<='9';ch=nc())x=x*10+ch-'0';
		if(sign)x=-x;
	}
	inline void read(ll &x){
		bool sign=0;char ch=nc();x=0;
		for(;blank(ch);ch=nc());
		if(IOerror)return;
		if(ch=='-')sign=1,ch=nc();
		for(;ch>='0'&&ch<='9';ch=nc())x=x*10+ch-'0';
		if(sign)x=-x;
	}
	inline void read(float &x){
		x=0;char ch=nc();int w=1,cnt=1,n=0;
		for(;blank(ch);ch=nc());
		if(IOerror)return;
		if(ch=='-') w=-w,ch=nc();
		for(;ch>='0'&&ch<='9';ch=nc())x=x*10+ch-'0';
		if(ch=='.'){ch=nc();for(;ch>='0'&&ch<='9';ch=nc())n=n*10+ch-'0',cnt*=10;}
		x=1.0*w*(x+1.0*n/cnt);
	}
	inline void read(double &x){
		x=0;char ch=nc();int w=1,cnt=1,n=0;
		for(;blank(ch);ch=nc());
		if(IOerror)return;
		if(ch=='-') w=-w,ch=nc();
		for(;ch>='0'&&ch<='9';ch=nc())x=x*10+ch-'0';
		if(ch=='.'){ch=nc();for(;ch>='0'&&ch<='9';ch=nc())n=n*10+ch-'0',cnt*=10;}
		x=1.0*w*(x+1.0*n/cnt);
	}
 	inline void read(char &x){
		char ch=nc();
		for(;blank(ch);ch=nc());
		if(IOerror)return;
		x=ch;
	}
	inline void write(char x){
		*oS++=x;
		if(oS==oT)flush();
	}
	template <class I>
	inline void write(I x){
		if(!x) write('0');if(x < 0) write('-'),x=-x;
		while (x) qu[++qr]=x%10+'0',x/=10;
		while (qr) write(qu[qr--]);
	}
	struct Flusher_{~Flusher_(){flush();}}io_flusher_;
	#undef ll
	#undef OUT_SIZE
	#undef BUF_SIZE
};
using namespace fastIO;

const int MAXN = 1e5 + 5;

int n, m, a[MAXN], f[MAXN], u[MAXN], v[MAXN];
long long tot[MAXN], sze[MAXN];

int find(int x) { return x == f[x] ? x : f[x] = find(f[x]); }

void merge(int u, int v) {
	int fu = find(u), fv = find(v);
	if(fu == fv) return ;
	if(fu > fv) { swap(u, v); swap(fu, fv); }
	f[fv] = fu;
	sze[fu] += sze[fv], sze[fv] = 0;
	tot[fu] += tot[fv], tot[fv] = 0;
}

void Solve() {
	read(n); read(m);
	for(int i = 1; i <= n; ++i) {
		f[i] = i;
		tot[i] = 0;
		sze[i] = 1;
	}
	for(int i = 1; i <= n; ++i) read(a[i]);
	for(int i = 1; i <= m; ++i) {
		read(u[i]); read(v[i]);
		sze[ u[i] ]++; sze[ v[i] ]++;
	}
	//for(int i = 1; i <= n; i++) write(sze[i]), write(' '); write('\n');

	for(int i = 1; i <= n; ++i) tot[i] = 1ll * sze[i] * a[i];
	for(int i = 1; i <= m; i++) merge(u[i], v[i]);
	
	//for(int i = 1; i <= n; i++) write(tot[i]), write(' '); write('\n');
	//for(int i = 1; i <= n; i++) write(sze[i]), write(' '); write('\n');
	
	for(int i = 1; i <= n; ++i) {
		int fi = find(i);
		double ans = 1.0 * tot[fi] / (1.0 * sze[fi]);
		printf("%.6lf\n", ans);
		/*
		int d1 = tot[fi] / sze[fi];
		int d2 = 1ll * ((tot[fi] % sze[fi]) * 1000000ll) / sze[fi];
		int cnt = 0, cur = d2;
		while(cur) cur /= 10, ++cnt;
		//double ans = 1.0 * tot[fi] / (1.0 * sze[fi]);
		//printf("%.6lf", ans);
		write(d1);
		write('.');
		for(int j = cnt + 1; j <= 6; j++) write('0');
		if(d2) write    (d2);
		write('\n');
		*/
	}
}

signed main()
{
	int T; read(T);
	while(T--) Solve();
	return 0;
}

I. Painting Game

设当前最后一个被涂黑的位置为 \(pos\)，对于 \(Alice\)，其下一个所涂位置一定为 \(pos+3\)；对于 \(Bob\)，其下一个所涂位置一定为 \(pos+4\)，最后阶段再返回来涂 \(pos+2\)。讨论一下边界，中间过程可以直接通过每次跳7步的方式加速，具体看代码。

#pragma GCC optimize(2)
#include<bits/stdc++.h>
using namespace std;

const int MAXN = 1e5 + 5;

int n;
string S;

void Solve() {
	cin >> n >> S;
	int pos = 0, cnt = 0, st;
	if(n == 1 || n == 2) return void(cout << "1\n");
	
	if(S[0] == 'B') {
		st = 1;
		
		pos = 3;
		cnt += 2;
		st = 0;
		
		int k = (n - pos) / 7;
		cnt += 3 * k;
		pos += 7 * k;
		while(pos <= n) {
			if(pos + 3 > n) break;
			pos += 3, cnt += 1;
			st = 1;
			if(pos + 4 > n) break;
			pos += 4, cnt += 2;
			st = 0;
		}
		
		if(!pos) {
			if(pos + 1 == n) cnt++;
			if(pos + 2 == n) cnt++;
			if(pos + 3 == n) {
				cnt++;
				if(st) cnt++; 
			}
			if(pos + 4 == n) {
				cnt += 2;
			}
		} else {
			if(pos + 1 == n) ;
			if(pos + 2 == n) cnt++;
			if(pos + 3 == n) cnt++;	
			if(pos + 4 == n) {
				cnt++;
				if(st) cnt++;
			}		
		}
		

	} else {
		st = 0;
		
		pos = 2;
		cnt++;
		st = 1;
		
		int k = (n - pos) / 7;
		cnt += 3 * k;
		pos += 7 * k;
		while(pos <= n) {
			if(pos + 4 > n) break;
			pos += 4, cnt += 2;
			st = 0;
			if(pos + 3 > n) break;
			pos += 3, cnt += 1;
			st = 1;
		}
		
		if(!pos) {
			if(pos + 1 == n) cnt++;
			if(pos + 2 == n) cnt++;
			if(pos + 3 == n) {
				cnt++;
				if(st) cnt++; 
			}
			if(pos + 4 == n) {
				cnt += 2;
			}
		} else {
			if(pos + 1 == n) ;
			if(pos + 2 == n) cnt++;
			if(pos + 3 == n) cnt++;	
			if(pos + 4 == n) {
				cnt++;
				if(st) cnt++;
			}		
		}
	}
	cout << cnt << "\n";
}

signed main()
{
	ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);	
	int T; cin >> T;
	while(T--) Solve();
	return 0;
}

标签：10,cnt,ch,int,题解,pos,++,MAXN,2022
From： https://www.cnblogs.com/Orzjh/p/16625857.html

相关文章

  • win10系统中修改hosts文件
    进入hosts文件目录选择以管理员身份打开WindowsPowerShell输入cmd进入管理员界面，输入notepadhosts编辑hosts文件......
  • 2022-8-24 js
    JavaScript脚本语言，解释性主要给HTML网页增加动态功能通常的JS是运行在浏览器环境下的，是由浏览器解释执行的，可以控制页面JS分两种模型：DOM：文档对象模型，d......
  • Idea创建Maven Web工程的web.xml版本问题解决
    问题使用Maven创建web工程的时候，创建出来的web.xml版本有问题。临时解决方案将在Tomcat安装目录下的webapps/ROOT/WEB-INF下的web.xml替换项目下的web.xml......
  • 10.Java中Map的entrySet() 详解以及用法
    一、Map.entry是什么？Map是java中的接口，Map.Entry是Map的一个内部接口。此接口为泛型，定义为Entry<K,V>。它表示Map中的一个实体（一个key-value对）接口中有get......
  • 2022-8-25第一组孙乃宇JavaScript
    JavaScript最后元素的属性获取元素的属性所有的HTML元素，我们可以根据具体需求，自定义添加属性<divhaha="abc"id="xyz"name="123"></div>获取这个属性的值为什么na......
  • jmeter-特殊问题解决
    1、相应报文乱码问题：方法一：1、在相应节点的下方，比如http请求，添加后置处理器–》BeanShellPostProcessor2、然后在其脚本框中添加如下代码prev.setDataEncoding(“UTF-8......
  • 2022/8/25 总结
    A.幸福考场上没想起矩阵，写了个\(\mathtt{O(n)}\)的暴力，得\(\mathtt{70pts}\)；Solution矩阵乘法。对\(F_n\)进行化简，就可以化得一个式子：\(F_n=F_{n-1}+F_{n-2}......
  • 2022-08-25 第五组 赖哲栋 学习笔记
    元素的设置<!--所有的HTMl元素，我们可以根据具体需求，自定义添加属性--><divhaha="abc"id="xyz"></div>获取属性的值元素.属性名的方式只适用于元素原生的属性......
  • 2022-08-25 第二组刘禹彤 学习笔记
    打卡40天###学习内容Javascript自定义属性获取属性所有的html元素，我们可以根据具体需求，自定义添加属性元素.属性名的方式只适用于元素原生的属性自定义属性di......
  • Educational Codeforces Round 106 (Rated for Div. 2) | CF1499
    E一个暴力是显然的，\(f(i,j,k)\)表示当前已经使用\(a\)的前\(i\)位，\(b\)的前\(j\)位，最后一位是\(a\)还是\(b\)的。然后\(O(n^2)\)枚举起点跑下去即可。为啥......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99