首页 > 其他分享 >XCPC集训48

XCPC集训48

时间：2022-09-03 17:49:22浏览次数：79  
标签：48 int long read while XCPC include 集训 define

A - Square String?

/*
	qwq!
*/

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <map>
#include <vector>
#include <queue>
#include <stack>
#include <set>
#include <cmath>
#include <unordered_map>
using namespace std;
#define pb push_back
#define pu push
#define fi first
#define se second
#define LL long long
#pragma GCC optimize(2)
#define IOS ios::sync_with_stdio(false); std::cin.tie(0),cout.tie(0);
//#define int long long
typedef pair<int,int> PII;
const int INF = 0x3f3f3f3f, mod = 1e9 + 7;
const int N = 2e5 + 10;
//int h[N], e[N], ne[N], idx;
int w[N];


inline int read () {
	int k=0,f=1;
	char c=getchar ();
	while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar ();}
	while (c>='0'&&c<='9') {k=k*10+c-'0';c=getchar ();}
	return k*f;
}

inline void write(int x){
    if(x<0) putchar('-'),x=-x;
    if(x>9) write(x/10);
    putchar(x%10-'0');
    return;
}


int main() {
	int T = read();
	while(T--) {
		string s; cin >> s;
		if(s.size() % 2) puts("NO");
		else {
			int x = s.size() / 2;
			if(s.substr(0, x) == s.substr(x)) puts("YES");
			else puts("NO");
		}
	}
	return 0;
}

B - Squares and Cubes

/*
	qwq!
*/

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <map>
#include <vector>
#include <queue>
#include <stack>
#include <set>
#include <cmath>
#include <unordered_map>
using namespace std;
#define pb push_back
#define pu push
#define fi first
#define se second
#define LL long long
#pragma GCC optimize(2)
#define IOS ios::sync_with_stdio(false); std::cin.tie(0),cout.tie(0);
#define int long long
typedef pair<int,int> PII;
const int INF = 0x3f3f3f3f, mod = 1e9 + 7;
const int N = 2e5 + 10;
//int h[N], e[N], ne[N], idx;
int w[N];
int cnt = 0;
unordered_map<int,int>mp;

inline int read () {
	int k=0,f=1;
	char c=getchar ();
	while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar ();}
	while (c>='0'&&c<='9') {k=k*10+c-'0';c=getchar ();}
	return k*f;
}

inline void write(int x){
    if(x<0) putchar('-'),x=-x;
    if(x>9) write(x/10);
    putchar(x%10-'0');
    return;
}

inline bool check(int x) {
	bool success = false;
	int t = sqrt(x);
	if(t * t == x) return true;
	t = pow(x, 1.0 / 3.0);
	if(t*t*t == x) return true;
	return false;
}
signed main() {
	int T = read();
	while(T--) {
		int n = read();
		int ans = 0;
		mp.clear();
		for(int i = 1; i * i <= n; i++) {
			if(i * i <= n) mp[i * i]++;
			if(i * i * i <= n) mp[i * i * i] ++;
		}
		cout << mp.size() << endl;
	}	 
	return 0;
}

C - Wrong Addition

/*
	qwq!
*/

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <map>
#include <vector>
#include <queue>
#include <stack>
#include <set>
#include <cmath>
#include <unordered_map>
using namespace std;
#define pb push_back
#define pu push
#define fi first
#define se second
#define LL long long
#pragma GCC optimize(2)
#define IOS ios::sync_with_stdio(false); std::cin.tie(0),cout.tie(0);
//#define int long long
typedef pair<int,int> PII;
const int INF = 0x3f3f3f3f, mod = 1e9 + 7;
const int N = 2e5 + 10;
//int h[N], e[N], ne[N], idx;
int w[N];
int ans[N];


inline int read () {
	int k=0,f=1;
	char c=getchar ();
	while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar ();}
	while (c>='0'&&c<='9') {k=k*10+c-'0';c=getchar ();}
	return k*f;
}

inline void write(int x){
    if(x<0) putchar('-'),x=-x;
    if(x>9) write(x/10);
    putchar(x%10-'0');
    return;
}


int main() {
	int T = read();
	while(T--) {
		string a, s; cin >> a >> s;
		int i = a.size() - 1, j = s.size() - 1;
		int k = 0;
		bool flag = true;
		while(j > -1 && i > -1) {
			int x = a[i] - '0';
			int y = s[j] - '0';
			if(y >= x) ans[k++] = y - x, j--, i--;
			else {
				if(!j) {
					flag = false;
					break;
				}
				j--;
			//	cout << y << "*" << endl;
				y = 10 * (s[j] - '0') + y;
			//	cout << y << endl;
				ans[k++] = y - x;
				if(y - x > 9 || y < x) {
					flag = false;
					break;
				}
				i--, j--;
			} 
		}
	//	cout << i << endl;
	//	cout << j << endl;
		if(!flag || i != -1) puts("-1");
		else {
			bool f = 0;
			while(j > -1) ans[k++] = s[j--] - '0';
			for(int i = k - 1; i >= 0; i--) {
				if(ans[i] > 0) f = 1;
				if(f) cout << ans[i];
			}
			cout << endl;
		}
	}
	return 0;
}

D - Not Shading

/*
	qwq!
*/

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <map>
#include <vector>
#include <queue>
#include <stack>
#include <set>
#include <cmath>
#include <unordered_map>
using namespace std;
#define pb push_back
#define pu push
#define fi first
#define se second
#define LL long long
#pragma GCC optimize(2)
#define IOS ios::sync_with_stdio(false); std::cin.tie(0),cout.tie(0);
//#define int long long
typedef pair<int,int> PII;
const int INF = 0x3f3f3f3f, mod = 1e9 + 7;
const int N = 110;
//int h[N], e[N], ne[N], idx;
char g[N][N];


inline int read () {
	int k=0,f=1;
	char c=getchar ();
	while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar ();}
	while (c>='0'&&c<='9') {k=k*10+c-'0';c=getchar ();}
	return k*f;
}

inline void write(int x){
    if(x<0) putchar('-'),x=-x;
    if(x>9) write(x/10);
    putchar(x%10-'0');
    return;
}


int main() {
	int T = read();
	while(T--) {
		int n = read(), m = read(), r = read(), c = read();
		r--, c--;
		bool success = false;
		for(int i = 0; i < n; i++)
			for(int j = 0; j < m; j++) {
				cin >> g[i][j];
				if(g[i][j] == 'B') success = true;
			}
		if(!success) puts("-1");
		else {
			if(g[r][c] == 'B') {
				cout << 0 << endl;
				continue;
			}
			int r_cnt = 0, c_cnt = 0;
			for(int i = 0; i < m; i++) 
				if(g[r][i] == 'B') r_cnt++;
			for(int i = 0; i < n; i++) 
				if(g[i][c] == 'B') c_cnt++;
			int ans = 0;
			if(r_cnt > 0 || c_cnt > 0) ans = 1;
			else ans = 2;
			cout << ans << endl;
		}
		
	}
	return 0;
}

E - Not Sitting

思路：

因为A要尽量靠近B，B要尽量远离A，所以B一定会是在某个角落里，A就会趋近于整个图的中心，这样才能达到平衡。所以应当每次都涂里某个角落距离最近的点，且该点尽量靠近中心。

代码：

/*
	qwq!
*/

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <map>
#include <vector>
#include <queue>
#include <stack>
#include <set>
#include <cmath>
#include <unordered_map>
using namespace std;
#define pb push_back
#define pu push
#define fi first
#define se second
#define LL long long
#pragma GCC optimize(2)
#define IOS ios::sync_with_stdio(false); std::cin.tie(0),cout.tie(0);
//#define int long long
typedef pair<int,int> PII;
const int INF = 0x3f3f3f3f, mod = 1e9 + 7;
const int N = 2e5 + 10;
//int h[N], e[N], ne[N], idx;
int w[N];

inline int read () {
	int k=0,f=1;
	char c=getchar ();
	while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar ();}
	while (c>='0'&&c<='9') {k=k*10+c-'0';c=getchar ();}
	return k*f;
}

inline void write(int x){
    if(x<0) putchar('-'),x=-x;
    if(x>9) write(x/10);
    putchar(x%10-'0');
    return;
}

int main() {
	int T = read();
	while(T--) {
		int n = read(), m = read();
		//int x = (n + 1) / 2, y = (m + 1) / 2;
		//cout << x << ' ' << y << endl;
		int k = 0;
		for(int i = 0; i < n; i++)
			for(int j = 0; j < m; j++) {
				w[k++] = max(i, n - i - 1) + max(j, m - j - 1);
			}
		sort(w, w + k);
	//	for(int i = 0; i < k; i++) cout << w[i].dist << endl;
	//	for(int i = 0; i < n * m - 1; i++) {
	//		int x = w[i].x + w[i].y - 2;
	//		cout << x << ' ';
	//	}
		for(int i = 0; i < k; i++) cout << w[i] << ' ';
		cout << endl;
	}
	return 0;
}

F - Triangle

思路：

斜着看每一行向上的个数，可得：(1 + 2^n) * (2^n) / 2, 要用到快速幂

代码：

/*
	qwq!
*/

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <map>
#include <vector>
#include <queue>
#include <stack>
#include <set>
#include <cmath>
#include <unordered_map>
using namespace std;
#define pb push_back
#define pu push
#define fi first
#define se second
#define LL long long
#pragma GCC optimize(2)
#define IOS ios::sync_with_stdio(false); std::cin.tie(0),cout.tie(0);
#define int long long
typedef pair<int,int> PII;
const int INF = 0x3f3f3f3f, mod = 1e9 + 7;
const int N = 2e5 + 10;
//int h[N], e[N], ne[N], idx;
int w[N];


inline int read () {
	int k=0,f=1;
	char c=getchar ();
	while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar ();}
	while (c>='0'&&c<='9') {k=k*10+c-'0';c=getchar ();}
	return k*f;
}

inline void write(int x){
    if(x<0) putchar('-'),x=-x;
    if(x>9) write(x/10);
    putchar(x%10-'0');
    return;
}

inline LL qmi(LL a, LL b) {
	LL ans = 1;
	while(b) {
		if(b&1) ans = ans * a % mod;
		a = a * a % mod;
		b >>= 1;
	}
	return ans % mod;
}

signed main() {
	LL n = read();
	if(n == 0) {
		cout << 1 << endl;
		return 0;
	}
	LL ans = (1 + qmi(2, n) % mod) * qmi(2, n - 1) % mod;
	cout << ans % mod << endl;
	return 0;
}

G - Banh-mi

思路：

对于某一段来说，肯定是优先选择1，最后1选完了再选0。 假设有a个1，b个0, 当作全是1，叠加总和为2^(a+b) - 1, 0拖了后腿，使得总和比实际多了2^b-1，所以实际为：
2(a+b)-1-(2b-1) = 2(a_b)-2b;
所以只需要统计区间0的个数就行了，可以用前缀和。

代码:

/*
	qwq!
*/

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <map>
#include <vector>
#include <queue>
#include <stack>
#include <set>
#include <cmath>
#include <unordered_map>
using namespace std;
#define pb push_back
#define pu push
#define fi first
#define se second
#define LL long long
#pragma GCC optimize(2)
#define IOS ios::sync_with_stdio(false); std::cin.tie(0),cout.tie(0);
#define int long long
typedef pair<int,int> PII;
const int INF = 0x3f3f3f3f, mod = 1e9 + 7;
const int N = 2e5 + 10;
//int h[N], e[N], ne[N], idx;
int w[N];


inline int read () {
	int k=0,f=1;
	char c=getchar ();
	while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar ();}
	while (c>='0'&&c<='9') {k=k*10+c-'0';c=getchar ();}
	return k*f;
}

inline void write(int x){
    if(x<0) putchar('-'),x=-x;
    if(x>9) write(x/10);
    putchar(x%10-'0');
    return;
}

inline int qmi(int a, int b) {
	int ans = 1;
	while(b) {
		if(b & 1) ans = ans * a % mod;
		a = a * a % mod;
		b >>= 1; 
	}
	return ans % mod;
}
signed main() {
	int n = read(), m = read();
	string s; cin >> s;
	s = " " + s;
	for(int i = 1; i <= n; i++) {
		w[i] = w[i-1];
		if(s[i] == '0') w[i]++;
	} 
	while(m--) {
		int a = read(), b = read();
		int ans = (qmi(2, b - a + 1) - qmi(2, w[b] - w[a - 1])) % mod ;
		printf("%lld\n", (ans + mod) % mod);
	}
	return 0;
}

H - Anton and Fairy Tale

思路：

  • 当n<=m时，到第n天，仓库就空了。所以答案为n
  • 当n>m时：第m+1天开始数量才会开始减少：

m + 1天： n - (m + 1) + m = n - 1
m + 2天： n - 1 - (m + 2) = n - 1 - 2
...
所以可得第i天仓空： n <= i * (i + 1) / 2
故可以二分答案；

代码：

/*
	qwq!
*/

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <map>
#include <vector>
#include <queue>
#include <stack>
#include <set>
#include <cmath>
#include <unordered_map>
using namespace std;
#define pb push_back
#define pu push
#define fi first
#define se second
#define LL long long
#pragma GCC optimize(2)
#define IOS ios::sync_with_stdio(false); std::cin.tie(0),cout.tie(0);
#define int long long
//#define int __int64
typedef pair<int,int> PII;
const int INF = 0x3f3f3f3f, mod = 1e9 + 7, INT_MAX = 0x7fffffff;
const int N = 2e5 + 10;
//int h[N], e[N], ne[N], idx;
int w[N];


inline int read () {
	int k=0,f=1;
	char c=getchar ();
	while (c<'0'||c>'9') {
		if (c=='-') f=-1;
		c=getchar ();
	}
	while (c>='0'&&c<='9') {
		k=k*10+c-'0';
		c=getchar ();
	}
	return k*f;
}

inline void write(int x) {
	if(x<0) putchar('-'),x=-x;
	if(x>9) write(x/10);
	putchar(x%10-'0');
	return;
}


signed main() {
	int n = read(), m = read();
	if(n <= m) cout << n << endl;
	else {
		n -= m;
		int l = 0, r = 2e9;
		while(l < r) {
			int mid = l + r >> 1;
			//cout << mid << endl;
			if(mid * (mid + 1) / 2 >= n) r = mid;
			else l = mid + 1;
		}
		cout << m + r << endl;
	}
	return 0;
}

标签：48,int,long,read,while,XCPC,include,集训,define
From： https://www.cnblogs.com/MoonSkyy/p/16653150.html

相关文章

  • 56*4/52*8段 高抗干扰低功耗/抗噪 LCD液晶显示驱动控制电路（IC）-VK2C23A/B LQFP48/64
    产品品牌：永嘉微电/VINKA产品型号：VK2C23A/B封装形式：LQFP64/48概述：VK2C23是一个点阵式存储映射的LCD驱动器，可支持最大224点（56SEGx4COM）或者最大416点（52SEGx8COM）的LCD屏。......
  • ESP8266转RS485/RS232/TTL控制板-下载和运行第一个程序(arduino)
    <p><iframename="ifd"src="https://mnifdv.cn/resource/cnblogs/circuit_module/8266_485_industrial"frameborder="0"scrolling="auto"width="100%"height="1500"><......
  • luoguP4824 [USACO15FEB] Censoring S 解题报告
    血的教训。。。传送门题意FJ已经根据杂志的所有文字，创建了一个字符串$S$($S$的长度保证不超过$10^6$)，他想删除其中的子串$T$,他将删去$S$......
  • 集训，我究竟在训练什么?
    集训，我究竟在训练什么？8.22找规律图论按位贪心找规律这题挺水的，但是我不会，看了题解才补的。图论这题我认真想了一会儿反而会了。ABC257剩两题没有补，懒了。按位贪心......
  • HDU3487 Play With Chain
    题目链接  题目大意就是要我们对一个区间执行区间翻转和整体移动区间的操作。  思路：将一个区间分裂出来再移动到另一个节点的后面，可以用\(fhq-treap\)来将这一个子树......
  • 雅礼集训 2018 Day1
    「雅礼集训2018Day1」树首先发现这个期望是诈骗，我们只需要求出\(g_i\)表示深度为\(i\)的树的个数然后带权除以总方案数即可。树的题目容易想到一个子树一个子树抠出来，......
  • [Google] LeetCode 489 Robot Room Cleaner
    Youarecontrollingarobotthatislocatedsomewhereinaroom.Theroomismodeledasanmxnbinarygridwhere0representsawalland1representsanempt......
  • [Bug0048] Redis安装成功后Warning: no config file specified, using the default co
    1、问题redis启动错误：Warning:noconfigfilespecified,usingthedefaultconfig.Inordertospecifyaconfig2、场景迁移环境，新windows环境下双击redis-serve......
  • Hyper Prefix Sets UVA - 11488
    题目链接思路我们对所有字符串建\(Trie\)树，求答案时，直接在插入新的字符串的时候，把答案更新一下就好了。代码#include<iostream>#include<cstdio>#include<cstri......
  • P1659 [国家集训队]拉拉队排练
    求字符串的奇数长回文子串中前\(k\)长的大小之积\(mod\)19930726。\(k\leq10^{12},|S|\leq10^6\)。不插入#跑一遍马拉车得到长度为奇数的回文串，用数组\(k\)表示......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99