首页 > 其他分享 >CF1747 题解

CF1747 题解

时间：2022-11-09 15:12:43浏览次数：85  
标签：CF1747 int 题解 long maxn BAN include define

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

题解：
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,maxn=2e5+5;

int n,a[maxn];

void solve(){
	LL s=0;
	scanf("%d",&n);
	for(int i=1;i<=n;i++)scanf("%d",&a[i]), s+=a[i];
	printf("%lld\n",abs(s));
}

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

	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;
//BANBANBAN
//BANBANBANBANBANBAN
//BANBANBANBANBANBANBANBANBAN
//BAN
//BANBANBANBANBANBANBAN
//BAN BAN BAN BAN BAN BAN BAN BAN BAN BAN
//BAN BAN BAN BAN BAN 5 3
// BAN BAN BAN BAN BAN BAN BAN BAN 8 5
//BNNBAABANBAN
int n;
void solve(){
	scanf("%d",&n);
		int t=1,cnt=0;
		for(int i=n*3;;i-=3){
			if(t >= i)break;
			++cnt;
//			printf("%d %d\n",t,i);
			t += 3;
		}
		printf("%d\n",cnt);
		t=1;
		for(int i=n*3;;i-=3){
			if(t >= i)break;
			++cnt;
			printf("%d %d\n",t,i);
			t += 3;
		}
}
signed main(){
	int te;scanf("%d",&te);
	while(te--){solve();
	}

	return 0;
}

C
当前选手输：0 [a2 ... an]
什么情况能推到出上面的局面？a1 [a2 .. 0 .. an] 必胜 ;因此 1 [a2 .. an]（且ai>=1，否则就是前面一种情况）必输
什么时候能有1 [a2 .. an]情况？我们发现这就是一个归纳的过程，最后结论就是a2..an如果有一个<a1就剩否则输

// 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;
int n,a[200005];
signed main(){
	int te;scanf("%d",&te);
	while(te--){
		scanf("%d",&n);
		for(int i=1;i<=n;i++)scanf("%d",&a[i]);
		int fg=0;
		for(int i=2;i<=n;i++)
			if(a[i] < a[1])fg = 1;
		puts(fg ? "Alice" : "Bob");
	}

	return 0;
}

D
如果区间长度是奇数，结论是平凡的：-1/0/1
区间长度是偶数？答案一定不超过2！
证明？首先答案一定不可能是3（3个奇数加起来不是偶数）
如果答案是4？那我取3个和1个奇数不就变成了答案2
注意答案可能是1：a[l]==0 || a[r] == 0
于是就把前缀异或和按位置的奇偶性存一下，需要用map把异或和离散化
此题卡常！

// by SkyRainWind
#include <cstdio>
#include <vector>
#include <cstring>
#include <map> 
#include <iostream>
#include <set>
#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;
#define int LL

const int inf = 1e9, INF = 0x3f3f3f3f,maxn=2e5+5;
int n,q,a[maxn],sum2[maxn], xo[maxn], sum3[maxn];
map<int, int>hs;
set<int>S[maxn][2];
int cnt = 0;
int read()
{
	int x=0;
	char c=getchar();
	while(c<'0' || c>'9')	c=getchar();
	while(c>='0' && c<='9')	x=(x<<1)+(x<<3)+(c^'0'),c=getchar();
	return x;
}
signed main(){
	n=read(),q=read();
	for(int i=1;i<=n;i++){
		a[i]=read();
		xo[i] = xo[i-1] ^ a[i];
		sum3[i] = sum3[i-1] + (a[i] == 0);
		if(!hs.count(xo[i]))hs[xo[i]] = ++ cnt; 
		S[hs[xo[i]]][i&1].insert(i);
	}
	while(q --){
		int l=read(),r=read();
		if(xo[r] ^ xo[l-1]){
			puts("-1");
			continue;
		}
		if((r-l+1)&1){
			if(sum3[r] - sum3[l-1] == r-l+1)puts("0");
			else if((xo[r] ^ xo[l-1]) == 0)puts("1");
			else puts("-1");
		}else{
			if(sum3[r] - sum3[l-1] == r-l+1)puts("0");
			else{
				int L = l;
				int tmp = hs[xo[l-1]];
				auto it = S[tmp][L&1].lower_bound(L);
				if(it == S[tmp][L&1].end() || *it > r)puts("-1");
				else{
					if(a[l] == 0 || a[r] == 0)puts("1");
					else puts("2");
				}
			}
		}
	}

	return 0;
}

E
首先把问题抽象成：在一个网格图上，从(0,0) 到 (n,m)，每次只能往右/上走，得到一条路径，在路径上选一些点集，问所有点集大小之和
（不等的条件就是不能不走）
注意对于某个点集，可能有多条路径，于是我们只计算一条路径，即先上再右的唯一一条路径
先来考虑“特殊”的点，拐点，注意这个拐点一定是先右再上的
这个是C(n,i) * C(m,i) 的，如果选了i个拐点
这样路径上除了起点终点和拐点，就剩下\(s= n+m+1 - i - 2 = n+m-i-1\)个其它点，看我们需要选哪些（注意拐点确定之后路径就唯一确定了，因为我们已经只计算那唯一一条路径了）
（所以选择拐点的原因就是能够确定路径）
因为要算的是长度之和，因此可以拆开单独算
先算起点终点拐点：长度之和就是\(C(n,i)*C(m,i)*(i+2)*2^{s}\)（i+2是点集大小，也就是序列长度，注意我们是拆开来算了，2^s是可能存在的所有包含着i+2个点的情况，即我在这个路径上选了其它的点，有一个方案数，而这些方案中都包含着i+2，所以序列长度和也都包含）
那么该如何算选了的其它点对答案的贡献？显然贡献就是\(C(n,i)*C(m,i)*[\sum_{j=0}^sC(s,j)*j]\)，后面的和式就是选了j个其它点，对答案的贡献
（也可以这么理解：选了i个拐点和j个其它点之后对答案的贡献是i+j+2，只不过我拆开了i+2和j单独算（因为对于i，有很多种j满足条件））
如何处理后面的和式？发现就是\(s*2^{s-1}\)，于是做完了，对于每个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 = 5e6 + 5, mod=1e9+7;

int p2[maxn * 2];
int fac[maxn], inv[maxn];

int pw(int x,int y){
	if(y == 0)return 1;
	if(y == 1)return x;
	int mid = pw(x, y>>1);
	if(y&1)return 1ll*mid*mid%mod*x%mod;
	return 1ll*mid*mid%mod;
}

int C(int x,int y){
	return 1ll*fac[x] * inv[y] % mod * inv[x-y] % mod;
}

void solve(){
	int n,m;scanf("%d%d",&n,&m);
	if(n > m)swap(n,m);
	int ans = 0;
	for(int i=0;i<=n;i++){
		int cur = 1ll * C(n,i) * C(m,i) % mod;
		int s = n+m-i-1;
		cur = 1ll * cur * ((1ll * p2[s] * (i+2) % mod + 1ll * s * p2[s-1] % mod) % mod) % mod;
		(ans += cur) %= mod;
	}
	printf("%d\n",ans);
}

signed main(){
	p2[0] = 1;
	fac[0] = inv[0] = 1;
	for(int i=1;i<=maxn - 5;i++)fac[i] = 1ll*fac[i-1]*i%mod;
	for(int i=1;i<=10000000;i++) p2[i] = 2ll*p2[i-1]%mod;
	inv[maxn - 5] = pw(fac[maxn-5] ,mod-2);
	for(int i=maxn-6;i>=1;i--)inv[i] = 1ll*inv[i+1]*(i+1)%mod;
	int te;scanf("%d",&te);
	while(te --)solve();

	return 0;
}

标签：CF1747,int,题解,long,maxn,BAN,include,define
From： https://www.cnblogs.com/SkyRainWind/p/16873755.html

相关文章

  • P1688 新单词接龙问题 题解
    大家好，我喜欢Hash，所以我用Hash通过了这道题。思路：处理方法有点类似于P6521首先我们最终接出的字符串要求其中的小字符串按字典序排序，那么我们就将所有字符串排好序......
  • 问题解决-白鹭引擎Egret Wing3修改项目内容后进行调试，项目仍显示修改前样式
    问题描述：修改前： 修改后： 解决方法：点击上方菜单栏项目-清理，进行项目清理    点击菜单栏项目-调试  重新进行调试。  调试成功后，问题成功解......
  • 问题解决-白鹭引擎Egret Wing3调试出错，输出台显示乱码而且编译终止问题Failed to load
    问题描述：Failedtoloadresource:theserverrespondedwithastatusof404()未能加载资源：服务器响应，状态为404（） 解决方法：卸载引擎并重新安装，安装时使用默认路径（C......
  • maven打包失败，Could not resolve dependencies for project...Could not find artifac
    一、问题原因：在阿里私服或者Maven的中央仓库找不到Pom文件引入的Jar，也就是说，你想引的依赖Jar包根本没有成功加载到项目中。二、分析2.1这个包可能处于隐患或者其他原因，原作......
  • CF1750题解
    A.IndirectSort首先，如果\(a_i>a_k\),\(a_i\)就会变大，而这样的操作是没有意义的.因此操作可以转换为\(\forallj,k(j<k)\),如果\(\existsi,i<j\),使得\(a[i]<=a[k]\),......
  • [CSP-S 2022]数据传输 题解
    提示：我这个方法比其它解法还要麻烦，目前最简洁的解法是dottle的解法，推荐阅读，我仅在此说明我的思路。给定\(n\)个点的树，点\(i\)的点权为\(a_i\)，给定整数\(k\)。称......
  • 线上问题解决
    1.服务重启2.部署回滚3.限流降级利用日志和故障现场保留的dump文件等进行根因分析；修复故障后在测试环境进行验证，确认没问题后再发布到生产环境；记录故障从发生到彻底......
  • cannot resolve symbol 'String' 问题解决
    在拉取一个新的项目的时候，maven和jdk都是配置好的，没问题，但是String会报红，显示cannotresolvesymbol'String'。maven的setting文件需要更改内容，因公司有自己的特殊的依......
  • CS Academy Telegraph 题解 (分层DP)
    CSAcademy是一个比较小众的罗马尼亚OJ，UI好看功能多样，但是需要fq才能注册。访问是不用fq的常用工具：画图找不同题目链接前段时间刚做过类似的分层dp题，这次又忘了，深刻反......
  • 题解 ABC154F【Many Many Paths】
    problem令\(f(i,j)\)表示，在平面直角坐标系中，从\((0,0)\)出发，每次向上或向右走一步，到达\((i,j)\)的方案数，求：\[\sum_{l_1\leqi\leqr_1}\sum_{l_2\leqj\leqr_2}f(......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99