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

原文地址：http://www.cnblogs.com/SkyRainWind/p/16891403.html

1. 本站所有资源来源于用户上传和网络，如有侵权请邮件联系站长！ 2. 分享目的仅供大家学习和交流，请务用于商业用途! 3. 如果你也有好源码或者教程，可以到用户中心发布，分享有积分奖励和额外收入！ 4. 本站提供的源码、模板、插件等等其他资源，都不包含技术服务请大家谅解！ 5. 如有链接无法下载、失效或广告，请联系管理员处理！ 6. 本站资源售价只是赞助，收取费用仅维持本站的日常运营所需！ 7. 如遇到加密压缩包，默认解压密码为"gltf",如遇到无法解压的请联系管理员！ 8. 因为资源和程序源码均为可复制品，所以不支持任何理由的退款兑现，请斟酌后支付下载声明：如果标题没有注明"已测试"或者"测试可用"等字样的资源源码均未经过站长测试.特别注意没有标注的源码不保证任何可用性

排行榜展示

3D打印机glb模型下载-机械glb模型

树glb模型下载-树2

水稻glb模型下载-水稻1

变电箱1glb模型下载-机械glb模型

树glb模型下载-树3

模型