题目链接  gym101778

Problem A

转化成绝对值之后算一下概率。这个题有点像 2018 ZOJ Monthly March Problem D ？ 不过那个题要难一些~

#include <bits/stdc++.h>

using namespace std;

#define rep(i, a, b)	for (int i(a); i <= (b); ++i)

#define dec(i, a, b)	for (int i(a); i >= (b); --i)

#define MP		make_pair

#define fi		first

#define se		second

typedef long long LL;

const LL mod = 1e9 + 7;

const int N  = 2e5 + 10;

int T;

int n, m;

LL fac[N];

inline LL Pow(LL a, LL b, LL mod){

        LL ret(1);

        for (; b; b >>= 1, (a *= a) %= mod) if (b & 1) (ret *= a) %= mod;

        return ret;

}

inline LL C(LL n, LL m){ return m > n ? 0 : fac[n] * Pow(fac[m] * fac[n - m] % mod, mod - 2, mod) % mod; }

int main(){

	fac[0] = 1;

	rep(i, 1, 2e5 + 1) fac[i] = fac[i - 1] * 1ll * i % mod; 

	scanf("%d", &T);

	while (T--){

		scanf("%d%d", &n, &m);

		n = abs(n);

		if (n == 0 && m == 0){

			puts("1");

			continue;

		}

		if (m < n){

			puts("0");

			continue;

		}

		if ((m + n) % 2 == 1){

			puts("0");

			continue;

		}

		int x = (m + n) / 2;

		printf("%lld\n", C(m, x) * Pow(Pow(2, m, mod), mod - 2, mod) % mod);

	}

	return 0;

}

Problem B

把首项定成$1$然后二分答案就可以了

#include <bits/stdc++.h>

using namespace std;

#define rep(i, a, b)	for (int i(a); i <= (b); ++i)

#define dec(i, a, b)	for (int i(a); i >= (b); --i)

#define MP		make_pair

#define fi		first

#define se		second

typedef long long LL;

int T;

LL n, a, l, r, t;

int main(){

	scanf("%d", &T);

	while (T--){

		scanf("%lld%lld", &n, &a);

		l = 0, r = n;

		while (l + 1 < r){

			LL mid = (l + r) >> 1;

			if (mid * (mid + 1) / 2ll <= n * a - n + mid) l = mid;

			else r = mid - 1;

		}

		if (r * (r + 1) / 2ll <= n * a - n + r) t = r;

		else t = l;

		printf("%lld\n", t);

	}

	return 0;

}

Problem C

找规律。$ans = (n - 1) * phi(n)$

#include <bits/stdc++.h>

using namespace std;

#define rep(i, a, b)	for (int i(a); i <= (b); ++i)

#define dec(i, a, b)	for (int i(a); i >= (b); --i)

typedef long long LL;

const int N = 1e6 + 10;

int T;

int phi[N];

int n;

int main(){

	rep(i, 2, 1e6 + 1){

		if (!phi[i]){

			for (int j = i; j <= 1e6; j += i){

				if (!phi[j]) phi[j] = j;

				phi[j] -= phi[j] / i;

			}

		}

	}

	scanf("%d", &T);

	while (T--){

		scanf("%d", &n);

		printf("%lld\n", 1ll * (n - 1) * phi[n]);

	}

	return 0;

}

Problem D

状态压缩，对于每一个集合求MST

#include <bits/stdc++.h>

using namespace std;

#define rep(i, a, b)	for (int i(a); i <= (b); ++i)

#define dec(i, a, b)	for (int i(a); i >= (b); --i)

const int N = 16;

int T;

int n, m, k;

int a[N][N], c[1 << N];

int all;

int ans;

int main(){

	scanf("%d", &T);

	while (T--){

		scanf("%d%d%d", &n, &m, &k);

		memset(c, 0, sizeof c);

		memset(a, -1, sizeof a);

		ans = 2e9;

		rep(i, 1, m){

			int x, y, z;

			scanf("%d%d%d", &x, &y, &z);

			--x;

			--y;

			a[x][y] = a[y][x] = z;

		}

		all = 0;

		rep(i, 1, k){

			int x;

			scanf("%d", &x);

			--x;

			all |= (1 << x);

		}

		int mx = (1 << n) - 1;

		rep(i, 1, mx){

			c[i] = 2e9;

			int p = 0;

			dec(j, n - 1, 0) if ((i >> j) & 1){

				p = j;

				break;

			}

			if ((i ^ (1 << p)) == 0){

				c[i] = 0;

				continue;

			}

			dec(j, n - 1, 0){

				if ((i >> j) & 1){

					rep(k, 0, n - 1){

						if (((i >> k) & 1) && (j != k) && (~a[j][k])) c[i] = min(c[i], c[i ^ (1 << j)] + a[j][k]);

					}

				}

			}

		}

		rep(i, 1, mx) if ((i & all) == all) ans = min(ans, c[i]);

		printf("%d\n", ans);

	}

	return 0;

}

Problem E

直接模拟

#include <bits/stdc++.h>

using namespace std;

#define rep(i, a, b)	for (int i(a); i <= (b); ++i)

#define	dec(i, a, b)	for (int i(a); i >= (b); --i)

#define	fi		first

#define	se		second

#define	MP		make_pair

typedef long long LL;

int T;

int n, x, y;

int id, d, m;

int mxd, mxm;

int main(){

	scanf("%d", &T);

	while (T--){

		scanf("%d%d%d", &n, &x, &y);

		mxd = 1e9, mxm = 0;

		id = -1;

		rep(i, 1, n){

			scanf("%d%d", &d, &m);

			if (d <= x && m >= y){

				if (mxd > d || (mxd == d && mxm < m)){

					mxd = d;

					mxm = m;

					id  = i;

				}

			}

		}

		printf("%d\n", id);

	}

	return 0;

}

Problem F

这个题略卡常数。

对每个权值求二维前缀和，二分答案就好了。

#include <bits/stdc++.h>

namespace IO{

	const int MT = 20 * 1024 * 1024;

	char IO_BUF[MT];

	int IO_PTR, IO_SZ;

	void begin(){

		IO_PTR = 0;

		IO_SZ = fread (IO_BUF, 1, MT, stdin);

	}

	template<typename T>

		inline bool scan_d (T & t){

			while (IO_PTR < IO_SZ && IO_BUF[IO_PTR] != '-' && (IO_BUF[IO_PTR] < '0' || IO_BUF[IO_PTR] > '9'))IO_PTR ++;

			if (IO_PTR >= IO_SZ) return false;

			bool sgn = false;

			if (IO_BUF[IO_PTR] == '-') sgn = true, IO_PTR ++;

			for (t = 0; IO_PTR < IO_SZ && '0' <= IO_BUF[IO_PTR] && IO_BUF[IO_PTR] <= '9'; IO_PTR ++)

				t = t * 10 + IO_BUF[IO_PTR] - '0';

			if (sgn) t = -t;

			return true;

		}

};

using namespace IO;

using namespace std;

#define rep(i, a, b)	for (int i(a); i <= (b); ++i)

#define dec(i, a, b)	for (int i(a); i >= (b); --i)

#define MP		make_pair

#define fi		first

#define se		second

typedef long long LL;

const int M = 503;

const int N = 1e2 + 2;

int c[M][N][N];

int a[N][N];

int n, m, q;

int mx;

int T;

int calc(int x1, int y1, int x2, int y2, int val){

	return c[val][x2][y2] - c[val][x2][y1 - 1] - c[val][x1 - 1][y2] + c[val][x1 - 1][y1 - 1];

}

void print(int x){

	if (x > 9) print(x / 10);

	putchar(x % 10 + '0');

}

int main(){

	begin();

	scan_d(T);;

	while (T--){

		scan_d(n);

		scan_d(m);

		scan_d(q);

		mx = 0;

		rep(i, 1, n){

			rep(j, 1, m) scan_d(a[i][j]), mx = max(mx, a[i][j]);

		}

		rep(k, 0, mx){

			rep(i, 0, n + 1){

				rep(j, 0, m + 1) c[k][i][j] = 0;

			}

		}

		rep(k, 1, mx){

			rep(i, 1, n){

				rep(j, 1, m){

					c[k][i][j] = c[k][i - 1][j] + c[k][i][j - 1] - c[k][i - 1][j - 1] + (a[i][j] <= k);

				}

			}

		}

		while (q--){

			int x1, y1, x2, y2;

			scan_d(x1);

			scan_d(y1);

			scan_d(x2);

			scan_d(y2);

			int all = (x2 - x1 + 1) * (y2 - y1 + 1);

			all = (all + 1) / 2;

			int l = 1, r = mx;

			while (l + 1 < r){

				int mid = (l + r) >> 1;

				if (calc(x1, y1, x2, y2, mid) >= all) r = mid;

				else l = mid + 1;

			}

			int t;

			if (calc(x1, y1, x2, y2, l) >= all) t = l;

			else t = r;

			print(t);

			putchar(10);

		}

	}

	return 0;

}

Problem G

根据割线定理来做。

#include <bits/stdc++.h>

using namespace std;

#define rep(i, a, b)	for (int i(a); i <= (b); ++i)

#define	dec(i, a, b)	for (int i(a); i >= (b); --i)

#define	fi		first

#define	se		second

#define	MP		make_pair

typedef long long LL;

int T;

int n, x, y;

int id, d, m;

int mxd, mxm;

int main(){

	scanf("%d", &T);

	while (T--){

		scanf("%d%d%d", &n, &x, &y);

		mxd = 1e9, mxm = 0;

		id = -1;

		rep(i, 1, n){

			scanf("%d%d", &d, &m);

			if (d <= x && m >= y){

				if (mxd > d || (mxd == d && mxm < m)){

					mxd = d;

					mxm = m;

					id  = i;

				}

			}

		}

		printf("%d\n", id);

	}

	return 0;

}

Problem H

假的数据结构……其实还是模拟

#include <bits/stdc++.h>

using namespace std;

#define rep(i, a, b)	for (int i(a); i <= (b); ++i)

#define dec(i, a, b)	for (int i(a); i >= (b); --i)

#define MP		make_pair

#define fi		first

#define se		second

typedef long long LL;

const int N = 1e5 + 10;

int T;

int n, m;

char s[N], ch[2];

int main(){

	scanf("%d", &T);

	while (T--){

		scanf("%d%d", &n, &m);

		scanf("%s", s + 1);

		int c = 0;

		rep(i, 1, (n + 1) >> 1) if (s[i] == s[n - i + 1]) ++c;

		int all = (n + 1) >> 1;

		int ans = 0;

		while (m--){

			int x;

			scanf("%d%s", &x, ch);

			if (s[x] == s[n - x + 1]){

				s[x] = ch[0];

				if (s[x] != s[n - x + 1]) --c;

			}

			else{

				s[x] = ch[0];

				if (s[x] == s[n - x + 1]) ++c;

			}

			if (c == all) ++ans;

		}

		printf("%d\n", ans);

	}

	return 0;

}

Problem I

签到

#include <bits/stdc++.h>

using namespace std;

#define rep(i, a, b)	for (int i(a); i <= (b); ++i)

#define dec(i, a, b)	for (int i(a); i >= (b); --i)

#define MP		make_pair

#define fi		first

#define se		second

typedef long long LL;

int T;

int main(){

	scanf("%d", &T);

	while (T--){

		int a, b, c, d;

		scanf("%d%d%d%d", &a, &b, &c, &d);

		if (a == d && b == c){

			puts("-1");

			continue;

		}

		if (a + c == b + d){

			if (c > a) puts("1"); else puts("2");

		}

		else if (a + c > b + d) puts("1");

		else puts("2");

	}

	return 0;

}

Problem J

挺有意思的一个题。

其实暴力做就可以了。因为在1e9的范围内质数间隔最大大概只有$320$。

#include <bits/stdc++.h>

using namespace std;

#define	rep(i, a, b)	for (int i(a); i <= (b); ++i)

#define	dec(i, a, b)	for (int i(a); i >= (b); --i)

typedef long long LL;

int T;

int fg;

LL  l, r;

bool check(LL x){

	if (x <= 10) return false;

	string s1 = "";

	for (; x; x /= 10) s1 += x % 10 + '0';

	reverse(s1.begin(), s1.end());

	int n = s1.length();

	string s2 = s1.substr(0, (n + 1) / 2);

	string s3 = s1.substr((n + 1) / 2);

	LL a = 0, b = 0;

	for (auto u : s2) a = a * 10 + u - '0';

	for (auto u : s3) b = b * 10 + u - '0';

	return __gcd(a, b) == 1;

}

int main(){

	scanf("%d", &T);

	while (T--){

		scanf("%lld%lld", &l, &r);

		fg = 0;

		for (LL i = r; i >= l; --i){

			if (check(i)){

				fg = 1;

				printf("%lld\n", i);

				break;

			}

		}

		if (!fg) puts("-1");

	}

	return 0;

}

Problem K

模拟……

#include <bits/stdc++.h>

using namespace std;

#define rep(i, a, b)	for (int i(a); i <= (b); ++i)

#define dec(i, a, b)	for (int i(a); i >= (b); --i)

#define MP		make_pair

#define fi		first

#define se		second

typedef long long LL;

struct state{

	int x, y, z, t;

	state(){

		x = y = z = t = -1;

	}

	state(int x, int y, int z, int t) :

			x(x), y(y), z(z), t(t){

	}

	bool operator < (const state &e) const{

		return t < e.t;

	}

};

const int N = 1e2 + 2;

int T;

int n, m, k;

int fb[N];

int WA[N][N], FAC[N];

vector <state> sub;

int main(){

	scanf("%d", &T);

	while (T--){

		scanf("%d%d%d", &n, &m, &k);

		int x, y, z, tm, ts;

		sub.clear();

		rep(i, 0, k - 1){

			scanf("%d%d%d%d:%d", &x, &y, &z, &tm, &ts);

			sub.push_back(state(x - 1, y - 1, z, tm * 60 + ts));

		}

		sort(sub.begin(), sub.end());

		memset(fb, -1, sizeof fb);

		memset(WA, 0, sizeof WA);

		memset(FAC, 0, sizeof FAC);

		int ep = -1, sg = -1;

		pair<int, int> sp(-1, 0), rp(-1, 0);

		rep(i, 0, k - 1){

			if (sub[i].z == 0)

				++WA[sub[i].x][sub[i].y];

			else{

				if (fb[sub[i].x] == -1)

					fb[sub[i].x] = sub[i].y + 1;

				if (ep == -1)

					ep = sub[i].y + 1;

				sg = sub[i].y + 1;

				if (WA[sub[i].x][sub[i].y] == 0)

					++FAC[sub[i].y];

				if (FAC[sub[i].y] > sp.first || (FAC[sub[i].y] == sp.first && sub[i].y + 1 < sp.second))

					sp = make_pair(FAC[sub[i].y], sub[i].y + 1);

				if (WA[sub[i].x][sub[i].y] > rp.first || (WA[sub[i].x][sub[i].y] == rp.first && sub[i].y + 1 < rp.second))

					rp = make_pair(WA[sub[i].x][sub[i].y], sub[i].y + 1);

			}

		}

		rep(i, 0, n - 1) printf("%s%d", i ? " " : "", fb[i]);

		putchar(10);

		printf("%d %d %d %d\n", ep, sg, sp.se, rp.se);

	}

	return 0;

}

最新文章

  1. Excel 自动更正
  2. jpa更新数据出错
  3. 手把手教你实现一个完整的 Promise
  4. 使用eclipse开发的兼容性配置
  5. Spring Remoting: Burlap--转
  6. MVC中JQuery文件引入的路径问题，@Url.Content函数
  7. 第11章 System V 信号量
  8. SQL服务器更改名称后
  9. java-多线程-join函数
  10. ab的排列 aa , ab ba,bb
  11. Android的logcat命令详解
  12. linux使用技巧(shell/vi/screen)
  13. Swift - 高级运算符介绍
  14. python3之正则表达式
  15. redis对键进行的相关操作
  16. 一次linux服务器黑客入侵后处理
  17. SpringCloud无废话入门02：Ribbon负载均衡
  18. linux基础之系统管理类命令
  19. win10 插入16k采样的耳机无法播放和录音的问题定位
  20. 死磕nginx系列--nginx 目录

热门文章

  1. ICG-智能代码生成器.(权限控制.融入平台).(表单引擎).(最低兼容IE8)
  2. wxPython 安装 及参考文档
  3. ASP.NET Core 2.1 源码学习之 Options[3]:IOptionsMonitor 【转】
  4. Python全栈工程师（每周总结：1）
  5. 孤荷凌寒自学python第六十天在windows10上搭建本地Mongodb数据服务
  6. springboot11 JPA
  7. Linux静态ip设置及一些网络设置
  8. JAVA并发-线程协作
  9. nf_register_hooks解读
  10. 开源作品ThinkJDBC—一行代码搞定数据库操作