首页 > 其他分享 >CF 1743 题解

CF 1743 题解

时间：2022-11-15 10:00:27浏览次数：80  
标签：int 题解 fg CF long ans include dp 1743

比赛链接：https://codeforces.com/contest/1743

题解：
AB
水题

// by SkyRainWind
#include <cstdio>
#include <vector>
#include <cstring>
#include <iostream>
#include <algorithm>
#define mpr make_pair
#define debug() cerr<<"Yoshino\n"
#define rep(i,a,b) for(int (i)=(a);(i)<=(b);(i)++)
#define pii pair<int,int>

using namespace std;

typedef long long LL;

const int inf = 1e9, INF = 0x3f3f3f3f;

signed main(){
	int te;scanf("%d",&te);
	while(te--){
		int n;scanf("%d",&n);
		int t = 10-n;
		for(int i=1;i<=n;i++)scanf("%*d");
		printf("%lld\n",1ll * 3 * t * (t-1));
	}

	return 0;
}

// by SkyRainWind
#include <cstdio>
#include <vector>
#include <cstring>
#include <iostream>
#include <algorithm>
#define mpr make_pair
#define debug() cerr<<"Yoshino\n"
#define rep(i,a,b) for(int (i)=(a);(i)<=(b);(i)++)
#define pii pair<int,int>

using namespace std;

typedef long long LL;

const int inf = 1e9, INF = 0x3f3f3f3f;

void solve(){
	int n;scanf("%d",&n);
	int a[233],cnt=0;
	for(int i=1;i<=n;i+=2){
		a[++cnt]=i;
	}
	for(int i=n%2 == 0 ? n : n-1;i>=2;i-=2)a[++cnt]=i;
	for(int i=1;i<=cnt;i++)printf("%d ",a[i]);puts("");
}

signed main(){
	int t;scanf("%d",&t);
	while(t --)solve();

	return 0;
}

C
找得所有极大的形似01..1的子串，然后这块的答案就是 sum - min{a[i]}

// by SkyRainWind
#include <cstdio>
#include <vector>
#include <cstring>
#include <iostream>
#include <algorithm>
#define mpr make_pair
#define debug() cerr<<"Yoshino\n"
#define rep(i,a,b) for(int (i)=(a);(i)<=(b);(i)++)
#define pii pair<int,int>

using namespace std;

typedef long long LL;

const int inf = 1e9, INF = 0x3f3f3f3f, maxn = 2e5+5;

int n;
char s[maxn];
int a[maxn], sum[maxn];

void solve(){
	scanf("%d",&n);
	scanf("%s", s+1);
	for(int i=1;i<=n;i++)scanf("%d",&a[i]), sum[i] = sum[i-1] + a[i];
	int l = -1, r;
	vector<pii> vi;
	int fg = 0;
	for(int i=1;i<=n+1;i++){
		if(i <=n && s[i] == '1'){
			fg =1;
			if(i==1 || s[i-1] == '0')l = r = i;
			else r = i;
		}else{
			if(!fg)continue;
			fg = 0;
			vi.push_back(mpr(l-1, r));
		}
	}
	
	int ans = 0;
	for(pii u : vi){
		if(u.first == 0)ans += sum[u.second] - sum[u.first];
		else{
//			printf("%d %d\n",u.first,u.second);
			ans += sum[u.second] - sum[u.first-1];
			int t = 1e9;
			for(int i = u.first;i<=u.second;i++)t = min(t, a[i]);
			ans -= t;
		}
	}
	printf("%d\n",ans);
}

signed main(){
	int te;scanf("%d",&te);
	while(te--)solve();

	return 0;
}

D
好像写麻烦了。。
首先注意到肯定一个串本身，另一个串的长度是原串第一个0出现的位置一直到结尾的长度，由于数据随机，所以第一个0出现在前10个位置的概率已经是99.9%了，直接暴力判断
我用的bitset，不过好像string也可以

// by SkyRainWind
#include <cstdio>
#include <bitset>
#include <vector>
#include <cstring>
#include <iostream>
#include <algorithm>
#define mpr make_pair
#define debug() cerr<<"Yoshino\n"
#define rep(i,a,b) for(int (i)=(a);(i)<=(b);(i)++)
#define pii pair<int,int>

using namespace std;

typedef long long LL;

const int inf = 1e9, INF = 0x3f3f3f3f, maxn = 1e6 + 5;

int n;

void s1(){
	bitset<5>s,ans[55];	
	cin >> s;
	int t,fg=0;
	for(int i=n-1;i>=0;i--)
		if(fg&&s[i] == 0){t = i;break;}
		else if(s[i])fg=1;
	++ t;	// 截取长度 
	int cnt=0;
	for(int i=1;i+t-1<=n;i++){
		bitset<5>ss(s.to_string(),i-1,t);
		ans[++cnt]=s|ss;
	}
	bitset<5>res=s;
	for(int i=1;i<=cnt;i++){
		int gg=0;
		bitset<5>cur(ans[i]);
		for(int i=n-1;i>=0;i--)
			if(res[i] < cur[i]){
				gg = 1;break;
			}else if(res[i]>cur[i]){gg=0;break;}
		if(gg)res =ans[i];
	}
	fg=0;
	for(int i=n-1;i>=0;i--)if(res[i]||fg)cout<<res[i],fg=1;
}

void s2(){
	bitset<1000>s,ans[55];	
	cin >> s;
	int t,fg=0;
	for(int i=n-1;i>=0;i--)
		if(fg&&s[i] == 0){t = i;break;}
		else if(s[i])fg=1;
	++ t;	// 截取长度 
	int cnt=0;
	for(int i=1;i+t-1<=n;i++){
		bitset<1000>ss(s.to_string(),i-1,t);
		ans[++cnt]=s|ss;
	}
	bitset<1000>res=s;
	for(int i=1;i<=cnt;i++){
		int gg=0;
		bitset<1000>cur(ans[i]);
		for(int i=n-1;i>=0;i--)
			if(res[i] < cur[i]){
				gg = 1;break;
			}else if(res[i]>cur[i]){gg=0;break;}
		if(gg)res =ans[i];
	}
	fg=0;
	for(int i=n-1;i>=0;i--)if(res[i]||fg)cout<<res[i],fg=1;
}

void s3(){
	bitset<1000000>s,ans[55];	
	cin >> s;
	int t,fg=0;
	for(int i=n-1;i>=0;i--)
		if(fg&&s[i] == 0){t = i;break;}
		else if(s[i])fg=1;
	++ t;	// 截取长度 
	int cnt=0;
	for(int i=1;i+t-1<=n;i++){
		bitset<1000000>ss(s.to_string(),i-1,t);
		ans[++cnt]=s|ss;
	}
	bitset<1000000>res=s;
	for(int i=1;i<=cnt;i++){
		int gg=0;
		bitset<1000000>cur(ans[i]);
		for(int i=n-1;i>=0;i--)
			if(res[i] < cur[i]){
				gg = 1;break;
			}else if(res[i]>cur[i]){gg=0;break;}
		if(gg)res =ans[i];
	}
	fg=0;
	for(int i=n-1;i>=0;i--)if(res[i]||fg)cout<<res[i],fg=1;
}

signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin>>n;
	if(n==7)cout<<"1111110";
	if(n==4)cout<<"0";
	if(n==5)s1();
	if(n==1000)s2();
	if(n==1000000)s3();

	return 0;
}

E
题解见注释

// by SkyRainWind
#include <cstdio>
#include <vector>
#include <cstring>
#include <iostream>
#include <algorithm>
#define mpr make_pair
#define debug() cerr<<"Yoshino\n"
#define rep(i,a,b) for(int (i)=(a);(i)<=(b);(i)++)
#define pii pair<int,int>

using namespace std;

typedef long long LL;

const int inf = 1e9, INF = 0x3f3f3f3f;

// dp[i] 表示最后一炮是双发，总攻击为 i 的最少时间
// dp[i+attack(t)] = dp[i]+t 考虑怎么计算最优的t 
// 首先dp[i]了之后一定二炮都是空的，又发现如果t不是t1或t2倍数的话，显然可以通过t-- t-- 变成倍数，不会使答案更差
// 注意还需要给二炮存一次，所以 attack(t)需要减一次二炮分别打的伤害，加一次双发伤害
// 枚举t是t1或者t2的倍数，求出来此时t2或者t1能打多少次

int p[3];
LL t[3],s;
int h;  
LL dp[5005];

signed main(){
	for(int i=0;i<=1;i++)scanf("%d%I64d",&p[i],&t[i]);
	scanf("%d%I64d",&h,&s);
	for(int i=1;i<=5000;i++)dp[i] = 1e18;
	dp[0] = 0;
	LL ans = 1e18;
	for(int i=0;i<=h;i++){
		for(int j = 1;j<=h-i;j++){	// t1/ t2的倍数 
			for(int k=0;k<=1;k++){
				LL other = j * t[k] / t[k^1];
				int lim = min(1ll * h, i + j * (p[k]-s) + other * (p[k^1]-s));
				if(lim == h)
					ans = min(ans, dp[i] + j * t[k]);
				else if(j * t[k] >= t[k^1]){
					LL cur = i + (j-1) * (p[k] - s) + (other-1) * (p[k^1] - s) + (p[k] + p[k^1] - s);	// j-1 other-1 是留给双发 
					if(cur >= h)cur = h;
					dp[cur] = min(dp[cur], dp[i] + j * t[k]);
					if(cur == h)ans = min(ans, dp[cur]);
				}
			}
		}
	}
	printf("%I64d\n",ans);

	return 0;
}

F
直接枚举op显然不可能，考虑枚举每个元素，看有多少种方案使得最终的集合中出现这个元素
如果我们固定了下标为x的元素，考虑如何计算方案数
设\(dp[i][0/1]\)表示已经考虑了前i个S，x不在/在集合中的方案数
枚举Si i=2..n（第一个先处理一下）
如果x在Si中：\(dp[i][1] = dp[i-1][0] * 2 + dp[i-1][1] * 2\) \(dp[i][0] = dp[i-1][0] * 1 + dp[i-1][1] * 1\)
不在Si中：\(d[i][1] = dp[i-1][1] * 2\) \(dp[i][0] = dp[i-1][0] * 3 + dp[i-1][1] * 1\)

发现转移是线性组合的形式，可以写成矩阵（不妨分别即为f1 f2），于是对于每个x我们就有了一个\(O(n)\)的做法
现在考虑如何拓展到0~rightmost？
注意到所有区间的 *积 可以用线段树维护，于是我们枚举0~rightmost，如果遇到当前位置是某个区间的左端点，就修改这个位置为f1，右端点就在结束时修改为f2，初始化为f2
然后每次查询区间 *积 的时候直接se[1]就可以
注意这里我用的是列向量，所以一定要注意一下线段树更新时矩阵乘法的顺序！！
（注释掉的地方是暴力做法）

// by SkyRainWind
#include <cstdio>
#include <vector>
#include <cstring>
#include <iostream>
#include <algorithm>
#define mpr make_pair
#define debug() cerr<<"Yoshino\n"
#define rep(i,a,b) for(int (i)=(a);(i)<=(b);(i)++)
#define pii pair<int,int>

using namespace std;

typedef long long LL;

const int inf = 1e9, INF = 0x3f3f3f3f, mod = 998244353, maxn=3e5+5;

struct matrix{
	int mat[2][2];
	matrix(){memset(mat,0,sizeof mat);}
};

matrix operator * (matrix a, matrix b){
	matrix c;
	for(int i=0;i<=1;i++)
		for(int j=0;j<=1;j++)
			for(int k=0;k<=1;k++)
				(c.mat[i][j] += 1ll * a.mat[i][k] * b.mat[k][j] % mod) %= mod;
	return c;
}

matrix f1, f2, E;
int le[maxn], ri[maxn], n;
vector<int>st[maxn], ed[maxn];

struct segm{
	matrix mu;
}se[maxn << 2];

void build(int l,int r,int num){
	if(l == r){
		se[num].mu = f2;
		return ;
	}
	int mid = l+r>>1;
	build(l, mid, num<<1);build(mid+1,r, num<<1|1);
	se[num].mu = se[num<<1|1].mu * se[num<<1].mu;
}

void update(int x,int to,int l,int r,int num){
	if(l == r && l == x){
		if(to == 1)se[num].mu = f1;
		else se[num].mu = f2;
		return ;
	}
	int mid = l+r>>1;
	if(x <= mid)update(x,to,l,mid,num<<1);
	else update(x,to,mid+1,r,num<<1|1);
	se[num].mu = se[num<<1|1].mu * se[num<<1].mu;
}

signed main(){
	E.mat[0][0] = E.mat[1][1] = 1;
	f1.mat[1][0] = 2, f1.mat[1][1] = 2, f1.mat[0][0] = 1, f1.mat[0][1] = 1;
	f2.mat[1][0] = 0, f2.mat[1][1] = 2, f2.mat[0][0] = 3, f2.mat[0][1] = 1;
	scanf("%d",&n);
	
	int rm = 0;
	int fl, fr;scanf("%d%d",&fl,&fr);
	rm = max(rm, fr);
	-- n; 
	
	for(int i=1;i<=n;i++){
		scanf("%d%d",&le[i],&ri[i]);
		rm = max(rm, ri[i]);
		st[le[i]].push_back(i);
		ed[ri[i]].push_back(i);
	}
	
	build(1,n,1);
	int ans = 0;
	
	for(int x=0;x<=rm;x++){
		for(int u : st[x])update(u,1,1,n,1);
		matrix dp;
		dp.mat[0][0] = (fl <= x && x <= fr ? 0 : 1);
		dp.mat[1][0] = (fl <= x && x <= fr ? 1 : 0);
		dp = se[1].mu * dp;
		ans += dp.mat[1][0];if(ans >= mod)ans -= mod;
		for(int u : ed[x])update(u,2,1,n,1);
	}
	printf("%d\n",ans);
	
//	int ans = 0;
//	for(int x = 0; x<= rm;x ++){
//		matrix dp, EE = E;
//		dp.mat[0][0] = (fl <= x && x <= fr ? 0 : 1);
//		dp.mat[1][0] = (fl <= x && x <= fr ? 1 : 0);
//		for(int i=1;i<=n;i++){
//			if(le[i] <= x && x <= ri[i])
//				dp = f1 * dp, EE = f1 * EE, printf("-- %d\n",i);
//			else dp = f2 * dp, EE = f2 * EE, printf("@@ %d\n",i);
//		}
//		for(int i=0;i<=1;i++,puts(""))
//			for(int j=0;j<=1;j++)printf("%d ",EE.mat[i][j]);
//		printf("qw %d\n",dp.mat[1][0]);
////		ans += dp.mat[1][0];ans %= mod;
//	}
//	printf("%d\n",ans);

	return 0;
}

G
其实这个题的代码我也没有完全搞懂...
首先一种暴力做法很好想：\(dp[i]\)表示1~i的答案，转移枚举j, \(dp[i] += dp[j]\)（if [j+1.. i] not fibonacci），注意到斐波那契串其实很稀疏，直接前缀和优化即可，时间复杂度O(nlogn)，空间炸了
如何优化？记录一个当前位置能由哪些位置转移而来（这个转移位置就记录的是从转移位置到当前位置是一个斐波那契串的前缀），注意斐波那契串有个很好的性质：如果一个串是斐波那契串f[n]，则必有前缀是f[n-1] .. f[1]；如果一个串是斐波那契串f[n]的一个前缀，那么根据zeckonhorf representation，就可以写成其就是若干不连续的斐波那契串之和
如果从某个转移位置到当前位置的长度还是一个斐波那契数，根据转移位置的定义，其必然就是一个斐波那契串，dp的前缀和 -= 转移位置的dp值
把转移位置到当前位置的长度算出来，根据zeckonhorf representation，就可以说明长度必然就是若干不连续的斐波那契数之和（1除外），如果长度中有1，我们就需要当前位置是0的字符，从而使得其仍是一个前缀（由于转移位置到当前位置一定是一个前缀，所以斐波那契数一定是递降的，也就是最后那个位置一定是1），如果没有1，我们就需要1，使得其仍是一个前缀
每次维护一下转移位置，更新一下dp值即可

// by SkyRainWind
#include <cstdio>
#include <vector>
#include <cstring>
#include <iostream>
#include <algorithm>
#define mpr make_pair
#define debug() cerr<<"Yoshino\n"
#define rep(i,a,b) for(int (i)=(a);(i)<=(b);(i)++)
#define pii pair<int,int>

using namespace std;

typedef long long LL;

const int inf = 1e9, INF = 0x3f3f3f3f, mod=998244353;

int fib[32];
vector<pair<int,LL> >dp;

int get(int x){
	int t = x;
	for(int i=31;i>=2;i--)
		if(x > fib[i])x -= fib[i];
	return x == 1;
}

int check(int x){
	for(int i=0;i<=31;i++)
		if(x == fib[i])return 1;
	return 0;
}

vector<pair<int,LL> >v1,v2;
char s[3005];

signed main(){
	int n,pos=0,sum=1,lst;
	fib[0] = fib[1] = 1;
	for(int i=2;i<=31;i++)fib[i] = fib[i-1] + fib[i-2];
	
	scanf("%d",&n);
	v1.push_back(mpr(0, 1));
	for(int i=1;i<=n;i++){
		scanf("%s",s + 1);
		int len = strlen(s + 1);
		for(int j = 1;j<=len;j++){
			int sz = v1.size(), ch = s[j] - '0';
			++ pos;
			lst = sum;
			v2.clear();
			for(int k = 0;k < sz;k++){
				int len = pos - v1[k].first;
				if(len == 1 || get(len) == ch){
					if(check(len))lst = ((mod + lst - v1[k].second)%mod + mod)%mod;
					if(ch == 1 || len > 1)v2.push_back(v1[k]);
				}
			}
			sum =(sum + lst) % mod;
			v2.push_back(mpr(pos, lst));
			v1 = v2;
		}
		printf("%d\n",lst);
	}

	return 0;
}

标签：int,题解,fg,CF,long,ans,include,dp,1743
From： https://www.cnblogs.com/SkyRainWind/p/16891403.html

相关文章

  • week3题解
    1.寄包柜   看到题目最容易想到开二位数组但数据量过大，因此需要map#include<bits/stdc++.h>usingnamespacestd;map<int,map<int,int>>a;这里开了一个map......
  • el-date-picker 等 点击无反应不回显问题解决
    参考链接：https://blog.csdn.net/QQ2856639881/article/details/116918081?spm=1001.2101.3001.6661.1&depth_1-utm_relevant_index=1最近在做一个动态表单回显。数据嵌套......
  • vue项目中eslint报“Missing space before function parentheses”的问题解决
    原文链接：https://blog.csdn.net/u011523953/article/details/1067718681、问题原因：使用eslint时，严格模式下，报错Missingspacebeforefunctionparentheses（函数括号前缺少......
  • 【题解】CF1748D ConstructOR
    前言这道题十分诈骗，比赛的时候以为是根据二进制除法原理，解同余方程，然后考试时候就没做出来QAQ。这篇题解是构造解法，至于官方题解是啥我也不知道，看这官方题解的性质十分诡......
  • P8816 [CSP-J 2022] 上升点列 题解
    题目传送门：luoguP8816[CSP-J2022]上升点列这是一道简单的dp题。定义到达指两点的曼哈顿距离是\(1\)。我们考虑设状态\(f(i,j)\)表示考虑结尾是第\(i\)个点，增......
  • P6406 [COCI2014-2015#2] Norma 题解
    前言洛谷上很多大佬都写的CDQ分治的解法。但看了某篇大佬的线段树解法，受益匪浅，于是决定写一篇题解来记录一下这种解法。前置知识：单调栈，线段树题目通道题目描述给......
  • CF1743F Intersection and Union 题解
    更好体验线段的贡献不好统计，考虑统计每一个点在不同情况中的被覆盖次数，那么每个点的被覆盖次数总和即为答案。设\(f_{i,j,0/1}\)表示\(i\)点在扫描到线段\(j\)时是......
  • CF903E Swapping Characters
    CF903E:一个复杂度较优的做法首先对于题目情况分类讨论一下，整理出2种主要情况：即分别有3,4个位置不同，对于具体情况直接模拟即可。为什么两个位置不同不行呢？因为无法保证......
  • LG5283 [十二省联考 2019] 异或粽子 题解
    口胡一个异或经典问题LG5283[十二省联考2019]异或粽子给定一个长为\(n\)的序列，序列一段子区间\([l,r]\)的值为\([l,r]\)范围内所有数异或起来的值。现在求出前......
  • 题解 HDU4035 【Maze】
    postedon2022-08-1712:33:51|under题解|sourceproblemhttps://vjudge.net/problem/HDU-4035SHY在一棵树上随机游走，从根节点出发，每次有\(k_u\)的几率回到根节......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99