CF1151div2(Round 553)

思路题大赛

A

少考虑了一种情况,到死没想到

B

貌似我随机化50000次,没找到就无解貌似也过了

感觉随随便便乱搞+分类讨论都可以过的样子

#include<cstdio>

#include<iostream>

#include<queue>

#include<algorithm>

#include<cstring>

#include<cctype>

#include<vector>

#include<ctime>

#include<cmath>

#define LL long long

#define pii pair<int,int>

#define mk make_pair

#define fi first

#define se second

using namespace std;

const int N = 505;

inline int read(){

	int v = 0,c = 1;char ch = getchar();

	while(!isdigit(ch)){

		if(ch == '-') c = -1;

		ch = getchar();

	}

	while(isdigit(ch)){

		v = v * 10 + ch - 48;

		ch = getchar();

	}

	return v * c;

}

int a[N][N];

int b[N][N];

int tot;

int s[N];

int n,m;

inline bool pan(){

	for(int i = 1;i <= n;++i)

		for(int j = 1;j <= n;++j)

			if(b[i][j] != 1) return 0;

	return 1;

}

inline bool check(){

	if(pan()){

		if(n & 1){

			for(int i = 1;i <= n;++i) s[++tot] = 1;

			return 1;

		}

		else return 0;

	}

}

int main(){

	srand(time(0));

	n = read(),m = read();

	for(int i = 1;i <= n;++i) for(int j = 1;j <= m;++j) a[i][j] = read();

	for(int t = 1;t <= 50000;++t){

		int now = 0;

		for(int i = 1;i < n;++i) s[i] = rand() % m + 1,now ^= a[i][s[i]];

		for(int i = 1;i <= m;++i){

			if((now ^ a[n][i]) != 0){

				s[n] = i;

				printf("TAK\n");

				for(int j = 1;j <= n;++j) printf("%d ",s[j]);

				return 0;

			}

		}

	}

	printf("NIE\n");

	return 0;

}

C

辣鸡CF连__int128都不支持

我们将所有的区间分成log块去考虑

每一块的内部其实都是等差数列

我们可以用等差数列求和公式

对于\(L,R\)就求一下前缀和

另外项数可能很大,一定要%mod（我就是因为这个WA的）

#include<cstdio>

#include<iostream>

#include<queue>

#include<algorithm>

#include<cstring>

#include<cctype>

#include<vector>

#include<ctime>

#include<cmath>

#define LL long long

#define pii pair<int,int>

#define mk make_pair

#define fi first

#define se second

using namespace std;

const LL mod = 1e9 + 7;

inline LL read(){

	LL v = 0,c = 1;char ch = getchar();

	while(!isdigit(ch)){

		if(ch == '-') c = -1;

		ch = getchar();

	}

	while(isdigit(ch)){

		v = v * 10 + ch - 48;

		ch = getchar();

	}

	return v * c;

}

LL L,R;

LL sum[129];

LL shou[129];

inline LL quick(LL x,LL y){

	LL res = 1;

	while(y){

		if(y & 1) res = res * x % mod;

		y >>= 1;

		x = x * x % mod;

	}

	return res;

}

LL inv2 = quick(2,mod - 2);

inline LL work(LL x){

	if(x == 0) return 0;

	LL cnt = 0;

	LL gg = 0;

	LL ans = 0;

	while(gg + (1ll << cnt) <= x){

		ans = (ans + sum[cnt]) % mod;

		gg += (1ll << cnt);

		cnt++;

	}

	if(gg != x){

		LL rest = (x - gg) % mod;

		LL rail = (shou[cnt] + (rest - 1) * 2 % mod) % mod;

		ans = (ans + (shou[cnt] + rail) % mod * rest % mod * inv2 % mod) % mod;

	}

	return ans;

}

int main(){

	L = read(),R = read();

	LL now = 0;

	LL base = 0;

	LL ji = 1;

	LL ou = 2;

	long long rr = R;

	do{

		rr -= (1ll << base);

	//	printf("%lld\n",rr);

		if(base & 1){

			shou[base] = ou;

			sum[base] = (ou + (ou + 2 * (quick(2,base) - 1) % mod) % mod) % mod * quick(2,base) % mod * inv2 % mod;

			ou = (ou + 2 * (quick(2,base)) % mod) % mod;

		}

		else{

			shou[base] = ji;

			sum[base] = (ji + (ji + 2 * (quick(2,base) - 1) % mod) % mod) % mod * quick(2,base) % mod * inv2 % mod;

			ji = (ji + 2 * (quick(2,base)) % mod) % mod;

		}

		base++;

	}while(rr > 0);

//	for(int i = 0;i <= base;++i) printf("%lld\n",(long long)(sum[i]));

	long long ans = ((work(R) - work(L - 1) + mod) % mod + mod) % mod;

	printf("%lld\n",(long long)ans);

	return 0;

}

D

化式子可以发现,只和\(a_i-b_i\)的值有关

然后就快乐排序算贡献

#include<cstdio>

#include<iostream>

#include<queue>

#include<algorithm>

#include<cstring>

#include<cctype>

#include<vector>

#include<ctime>

#include<cmath>

#define LL long long

#define pii pair<int,int>

#define mk make_pair

#define fi first

#define se second

using namespace std;

const LL mod = 1e9 + 7;

inline LL read(){

	LL v = 0,c = 1;char ch = getchar();

	while(!isdigit(ch)){

		if(ch == '-') c = -1;

		ch = getchar();

	}

	while(isdigit(ch)){

		v = v * 10 + ch - 48;

		ch = getchar();

	}

	return v * c;

}

LL L,R;

LL sum[129];

LL shou[129];

inline LL quick(LL x,LL y){

	LL res = 1;

	while(y){

		if(y & 1) res = res * x % mod;

		y >>= 1;

		x = x * x % mod;

	}

	return res;

}

LL inv2 = quick(2,mod - 2);

inline LL work(LL x){

	if(x == 0) return 0;

	LL cnt = 0;

	LL gg = 0;

	LL ans = 0;

	while(gg + (1ll << cnt) <= x){

		ans = (ans + sum[cnt]) % mod;

		gg += (1ll << cnt);

		cnt++;

	}

	if(gg != x){

		LL rest = (x - gg) % mod;

		LL rail = (shou[cnt] + (rest - 1) * 2 % mod) % mod;

		ans = (ans + (shou[cnt] + rail) % mod * rest % mod * inv2 % mod) % mod;

	}

	return ans;

}

int main(){

	L = read(),R = read();

	LL now = 0;

	LL base = 0;

	LL ji = 1;

	LL ou = 2;

	long long rr = R;

	do{

		rr -= (1ll << base);

	//	printf("%lld\n",rr);

		if(base & 1){

			shou[base] = ou;

			sum[base] = (ou + (ou + 2 * (quick(2,base) - 1) % mod) % mod) % mod * quick(2,base) % mod * inv2 % mod;

			ou = (ou + 2 * (quick(2,base)) % mod) % mod;

		}

		else{

			shou[base] = ji;

			sum[base] = (ji + (ji + 2 * (quick(2,base) - 1) % mod) % mod) % mod * quick(2,base) % mod * inv2 % mod;

			ji = (ji + 2 * (quick(2,base)) % mod) % mod;

		}

		base++;

	}while(rr > 0);

//	for(int i = 0;i <= base;++i) printf("%lld\n",(long long)(sum[i]));

	long long ans = ((work(R) - work(L - 1) + mod) % mod + mod) % mod;

	printf("%lld\n",(long long)ans);

	return 0;

}

E

首先一个小\(trick\)

树上的连通块数 = 点数 - 边数(本题是链也)

所以答案变成了点数之和减去边数之和

对于一个点\(i\),他的贡献应该是

\[a_i*(n - a_i + 1)
\]

就是左端点和右端点的取值都要合法

一条边存在仅当他链接的两个点都存在

\[min(a_i,a_{i + 1}) * (n - max(a_i,a_{i + 1}) + 1)
\]

所以把这些东西算一算就好了

#include<cstdio>

#include<iostream>

#include<queue>

#include<algorithm>

#include<cstring>

#include<cctype>

#include<vector>

#include<ctime>

#include<cmath>

#define LL long long

#define pii pair<int,int>

#define mk make_pair

#define fi first

#define se second

using namespace std;

const int N = 1e5 + 3;

int a[N];

int n;

inline int read(){

	int v = 0,c = 1;char ch = getchar();

	while(!isdigit(ch)){

		if(ch == '-') c = -1;

		ch = getchar();

	}

	while(isdigit(ch)){

		v = v * 10 + ch - 48;

		ch = getchar();

	}

	return v * c;

}

int main(){

	LL ans = 0;

	n = read();

	for(int i = 1;i <= n;++i) a[i] = read();

	for(int i = 1;i <= n;++i) ans += 1ll * a[i] * (n - a[i] + 1);

	for(int i = 1;i < n;++i) ans -= 1ll * min(a[i],a[i + 1]) * (n - max(a[i],a[i + 1]) + 1);

	cout << ans;

	return 0;

}

F

见这一篇

最新文章

  1. javascript数据结构-栈
  2. (转)关于Oracle AUTONOMOUS TRANSACTION(自治事务)的介绍
  3. AppleWatch___学习笔记（三）iPhone和Apple Watch上的数据同步
  4. 《Java程序设计》第八周学习总结
  5. 转】Mahout学习路线图
  6. C#根据域名查询IP(CMD命令参数输入或者启动程序后再输入查询)
  7. 这两天dede 仿站的收货
  8. Docker第一弹：下载运行hello-world程序
  9. spring-mvc访问本地html文件
  10. 解决win10 蓝牙设备只能配对无法连接 ，并且删除设备无效的问题
  11. Docker之 默认桥接网络与自定义桥接网卡
  12. Java8-dateTimeFormatter
  13. Ionic 动态配置url路由的设置
  14. hadoop 常见 命令
  15. Android 系统中运行jar文件
  16. 【SE】Week3 : 四则运算式生成评分工具Extension&amp;Release Version(结对项目)
  17. Linux块设备驱动详解
  18. create session 参数介绍
  19. Linux：curl
  20. 什么是EOF -- 转

热门文章

  1. Flutter SDK path为空导致工程打开后不显示iOS模拟器的问题
  2. LeetCode108 Convert Sorted Array to Binary Search Tree
  3. 利用IDEA构建springboot应用-Controller的使用
  4. 罗列Python标准模块
  5. Spring Data JPA 查询结果返回至自定义实体
  6. 设置select和option的文字居中
  7. g++ 编译单个文件和多个文件
  8. cmd导入比较大的sql脚本
  9. 如何学习Python的一些总结
  10. Flex AIR应用拍照功能（Android和IOS版本）