夏晓光(loveJY)的博客

仍要向下扎根,向上结果

首页 归档 标签 关于 友链

20zr普及组五连测day2

2020-09-18 12 min read # 计数题 # 比赛题 # 构造

哎...人总有写挂的一天吗?

A

傻逼题用map直接模拟即可

最后剩下的那个就是答案

卡双模hash

时间复杂度O(nlogn)


#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int bas1 = 12344;
const int bas2 = 67891;
const int P1 = 1e9 + 9;
const int P2 = 1e9 + 3;
const int MAXS = 30;
const int MAXN = 1e5 + 7;
#define pii pair<ll,ll>
#define se second
#define fi first
#define mkp(x,y) make_pair(x,y)
int n;
string s;
map<string, int> mp;

int main() {
	scanf("%d", &n);
	for(int i = 0; i < n + n - 1; ++i) {
		cin >> s;
		mp[s]++;
	}
	for(auto v : mp) {
		if(v.se & 1)
			cout << v.fi << endl;
	}
	return 0;
}

B

就是base为2i的进制转换

直接模拟即可

这个可以看看代码

注意

  1. 输出虚数部分的+时要小心,因为可能前面那个数是0啊
  2. 特判0

而又没法对拍,只能手动....

code:

/*
_/_/_/_/    _/_/_/_/_/  _/_/_/
_/      _/      _/    _/      _/
_/      _/      _/    _/      _/
_/      _/      _/    _/      _/
_/      _/      _/    _/  _/  _/
_/      _/  _/  _/    _/    _/_/
_/_/_/_/      _/_/     _/_/_/_/_/

_/_/_/_/    _/    _/  _/      _/
_/      _/   _/  _/   _/_/  _/_/
_/      _/    _/_/    _/ _/_/ _/
_/      _/     _/     _/  _/  _/
_/      _/    _/_/    _/      _/
_/      _/   _/  _/   _/      _/
_/_/_/_/    _/    _/  _/      _/

_/_/_/_/_/ _/_/_/_/_/ _/_/_/_/_/
    _/         _/     _/
    _/         _/     _/
    _/         _/     _/_/_/_/
    _/         _/     _/
    _/         _/     _/
    _/     _/_/_/_/_/ _/_/_/_/_/

_/_/_/_/_/ _/_/_/_/_/ _/_/_/_/_/
    _/         _/     _/
    _/         _/     _/
    _/         _/     _/_/_/_/
    _/         _/     _/
    _/         _/     _/
    _/     _/_/_/_/_/ _/_/_/_/_/
*/
//orzEI!
#include<bits/stdc++.h>
#define ll __int128
using namespace std;
const int MAXN = 100;

ll t1, t2, p1, p2, q1, q2;
char s[MAXN];
int cnt;
ll qwq[MAXN];

namespace fastIO {
	int _C = -1, _Z;
	char _sr[1 << 21], _z[20];
	inline void Ot() {
		fwrite(_sr, 1, _C + 1, stdout), _C = -1;
	}
	inline void print(ll x) {
		if(_C > 1 << 20)Ot();
		while(_z[++_Z] = x % 10 + 48, x /= 10);
		while(_sr[++_C] = _z[_Z], --_Z);
	}
	inline void print2(char s) {
		_sr[++_C] = s;
	}
}
using namespace fastIO;

inline void init() {
	qwq[0] = 1;
	for(int i = 1; i < 80; ++i)qwq[i] = qwq[i - 1] * 2;
	return ;
}

inline ll ksm(int x) {
	return qwq[x];
}

inline ll gcd(ll x, ll y) {
	return y == 0 ? x : gcd(y, x % y);
}

int main() {
	scanf("%s", s + 1);
	int a = strlen(s + 1);
	if(a == 1 && s[1] == '0') {
		return puts("0"), 0;
	}
	init();
	cnt = a + 1;
	for(int i = 1; i <= a; ++i) {
		if(s[i] == '.') {
			cnt = i;
			break;
		}
	}
	//处理整数部分
	for(int i = 1; i < cnt; ++i) {
		int t = (cnt - i) % 4;
		if(t == 1) { //正数
			t1 += ksm(cnt - i - 1) * (s[i] - '0');
		} else if(t == 2) { //正数i
			t2 += ksm(cnt - i - 1) * (s[i] - '0');
		} else if (t == 3) { //负数
			t1 -= ksm(cnt - i - 1) * (s[i] - '0');
		} else {//负数i
			t2 -= ksm(cnt - i - 1) * (s[i] - '0');
		}
		//		printf("%d %lld %lld %d\n",s[i]-'0',t1,t2,i);
	}
	//处理小数部分
	//使用最大的那一部分，然后除除gcd吧QAQ
	for(int i = a; i > cnt; --i) {
		if(s[i] == '0')continue;
		int t = (i - cnt) % 4;
		//		printf("%d?%d\n",t,i);
		if((t == 1 || t == 3) && !q2) {
			q2 = ksm(i - cnt);
		}
		if((t == 2 || t == 0) && !q1) {
			q1 = ksm(i - cnt);
		}
	}
	if(!q1)q1 = 1;
	if(!q2)q2 = 1;
	//	printf("%lld %lld\n",q1,q2);
	for(int i = cnt + 1; i <= a; ++i) {
		int t = (i - cnt) % 4;
		if(t == 1) { //负数i
			p2 -= q2 / ksm(i - cnt) * (s[i] - '0');
		} else if(t == 2) { //负数
			p1 -= q1 / ksm(i - cnt) * (s[i] - '0');
		} else if(t == 3) { //正数i
			p2 += q2 / ksm(i - cnt) * (s[i] - '0');
		} else {//正数
			p1 += q1 / ksm(i - cnt) * (s[i] - '0');
		}
		//		printf("%d %lld %lld %d\n",s[i]-'0',p1,p2,i);
	}
	//	printf("%lld %lld %lld %lld %lld %lld\n",p1,q1,t1,p2,q2,t2);
	p2 += q2 * t2;
	p1 += q1 * t1;
	ll qwq1 = gcd(p1, q1);
	ll qwq2 = gcd(p2, q2);
	p2 /= qwq2;
	q2 /= qwq2;
	p1 /= qwq1;
	q1 /= qwq1;
	if(q1 < 0)p1 = -p1, q1 = -q1; //同时乘-1
	if(q2 < 0)p2 = -p2, q2 = -q2;
	if(p1 != 0) {
		if(p1 < 0) {
			print2('-');
			p1 = -p1;
		}
		if(q1 == 1) {
			print(p1);
		} else {
			print(p1);
			print2('/');
			print(q1);
		}
	}
	if(p2 != 0) {
		if(p2 < 0) {
			print2('-');
			p2 = -p2;
		} else {
			if(p1 != 0)
				print2('+');//死因啊
		}
		if(q2 == 1) {
			if(p2 != 1)
				print(p2);
		} else {
			print(p2);
			print2('/');
			print(q2);
		}
		print2('i');
	}
	Ot();
	return 0;
}

/*

311111111.11111
11111111.11111
111111111111111111111111111111.11111111111111111111111111111111
11111111111111111111111111111111

*/

哎...这尼玛的都能卡

C

就差一步啊QAQTAT

首先把整个序列变成一个前1后-1的差分的形式后

我们可以发现相邻的1,-1可以用后面的一个1替代,然后相邻的-1,1 可以用后面的一个-1替代....

就做完了....最后数数序列中有数的位置有多少个即可


/*
_/_/_/_/    _/_/_/_/_/  _/_/_/
_/      _/      _/    _/      _/
_/      _/      _/    _/      _/
_/      _/      _/    _/      _/
_/      _/      _/    _/  _/  _/
_/      _/  _/  _/    _/    _/_/
_/_/_/_/      _/_/     _/_/_/_/_/

_/_/_/_/    _/    _/  _/      _/
_/      _/   _/  _/   _/_/  _/_/
_/      _/    _/_/    _/ _/_/ _/
_/      _/     _/     _/  _/  _/
_/      _/    _/_/    _/      _/
_/      _/   _/  _/   _/      _/
_/_/_/_/    _/    _/  _/      _/

_/_/_/_/_/ _/_/_/_/_/ _/_/_/_/_/
    _/         _/     _/
    _/         _/     _/
    _/         _/     _/_/_/_/
    _/         _/     _/
    _/         _/     _/
    _/     _/_/_/_/_/ _/_/_/_/_/

_/_/_/_/_/ _/_/_/_/_/ _/_/_/_/_/
    _/         _/     _/
    _/         _/     _/
    _/         _/     _/_/_/_/
    _/         _/     _/
    _/         _/     _/
    _/     _/_/_/_/_/ _/_/_/_/_/
*/

#include<bits/stdc++.h>
using namespace std;
const int MAXN = 2e6 + 7;
int T;
char a[MAXN];
int b[MAXN];


// inline void solve() {
// 	int n = strlen(a + 1);
// 	int cnt = 0;
// 	ans = 0;
// 	bool flg = 1;
// 	memset(b, 0, sizeof(b));
// 	a[n + 1] = '0';
// 	for(int i = 1; i <= n; ++i) {
// 		if(flg && a[i] == '1') {
// 			//			ans++;
// 			b[i] = 1;
// 			continue;
// 		}
// 		if(flg && a[i] == '0') {
// 			flg = 0;
// 		}
// 		cnt += a[i] - '0';
// 		if(cnt == 1 && a[i + 1] == '0') {
// 			//			++ans;
// 			b[i] = 1;
// 			cnt = 0;
// 		} else if(a[i + 1] == '0' && cnt > 1) {
// 			b[i - cnt] = 1;
// 			b[i] = -1;
// 			cnt = 0;
// 			//			ans+=2;
// 		}
// 	}
// 	//	puts("qwq");
// 	for(int i = 1; i <= n; ++i) {
// 		if(b[i] == -1 && b[i + 1] == 1) {
// 			b[i + 1] = -1;
// 			b[i] = 0;
// 		}
// 		ans += (b[i] != 0);
// 		//		printf("%d ",b[i]);

// 	}
// 	//	puts("");
// 	//	printf("%d\n",ans);
// }

inline void solve2() {
	int n = strlen(a + 1);
	int cnt = 0;
	int ans = 0;
	bool flg = 1;
	memset(b, 0, sizeof(b));
	a[n + 1] = '0';
	for(int i = 1; i <= n; ++i) {
		if(flg && a[i] == '1') {
			//			ans++;
			b[i] = 1;
			continue;
		}
		if(flg && a[i] == '0') {
			flg = 0;
		}
		cnt += a[i] - '0';
		if(a[i + 1] == '0' && cnt >= 1) {
			b[i - cnt] = 1;
			b[i] = -1;
			cnt = 0;
			//			ans+=2;
		}
	}
	//	puts("qwq");
	for(int i = 1; i <= n; ++i) {
		if(b[i] == 1 && b[i + 1] == -1) {
			b[i + 1] = 1;
			b[i] = 0;
		}
		if(b[i] == -1 && b[i + 1] == 1) {
			b[i + 1] = -1;
			b[i] = 0;
		}
		ans += (b[i] != 0);
		//		printf("%d ",b[i]);

	}
	//	puts("");
	printf("%d\n", ans);
}

int main() {
	scanf("%d", &T);
	while(T-- > 0) {
		scanf("%s", a + 1);
		// solve();
		solve2();
	}
	return 0;
}

D

OEIS

i*(i+1)爆int了

正确做法:

考虑组合数学

首先我们枚举k表示把第一类小球分成几组

然后方案数为(n−1k−1)\binom{n-1}{k-1}

然后我们在此基础上把第二类小球加进去,就是考虑我们只能插在第一类小球之间,和第一类放在一起

假设有t种,方案数为(n−1t−1)\binom{n-1}{t-1}

那么我们第一种是第一类小球两侧都是第二类小球,第二种是左侧或者右侧是第二类小球,第三种是第二类小球两侧都是第一类小球

对应t的k+1,k,k-1三种可能

方案数就是(n−1k−1)(n−1t−1)∗(1+[t==k])\binom{n-1}{k-1}\binom{n-1}{t-1}*(1+[t==k])

然后第三类小球只能把所有我们相邻的位置杀掉

考虑我们一共有(k+t+1)(k+t+1)个位置颜色相邻不相同

而我们现在加入了2n个球,所以我们有2n+1−k−t−12n+1-k-t-1个位置颜色相邻相同

所以说我们需要插入n−(2n−k−t)n-(2n-k-t)个第三类小球干掉这些位置

然后剩下的第三类小球从左向右依次蹦进我们相邻颜色不相同的位置就行了

因为其实就是每个第三类小球匹配了前面的一些合法空当位置,变成了有标号

然后我们再把他们拿出一些分给不相同就是无标号组合数了

code:


#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int P = 998244353;
const int MAXN = 1e6 + 7;
inline ll ksm(ll x, ll y) {
	ll ans = 1;
	while(y) {
		if(y & 1)ans = ans * x % P;
		x = x * x % P;
		y >>= 1;
	}
	return ans;
}
ll f[MAXN];
int main() {
	int n;
	scanf("%d", &n);
	f[1] = 6;
	f[2] = 30;
	for(int i = 3; i <= n; ++i) {
		f[i] = (f[i - 1] * (7 * i - 4) % P * (i + 1) % P + f[i - 2] * 8 % P * (i - 2) % P * (i - 2) % P) % P * ksm(1ll * i * (i + 1) % P, P - 2) % P;
		f[i] %= P;
	}
	printf("%lld\n", f[n]);
	return 0;
}
Powered by Gridea RSS