Codeforces Round #580 (Div. 2)

选最大的两个数

#include <bits/stdc++.h>
#define sc scanf
#define pr printf
#define ll long long
using namespace std;
const int MAXN = 200005;
int a[200005], b[200005];
int main()
{
	int n, m, t;
	sc("%d", &n);
	for (int i = 0; i < n; i++)
	{
		sc("%d", &a[i]);
	}
	sc("%d", &m);
	for (int i = 0; i < m; i++)
	{
		sc("%d", &b[i]);
	}
	sort(a, a + n, [](int q, int w) {
		return q > w;
		});
	sort(b, b + m, [](int q, int w) {
		return q > w;
		});
	printf("%d %d", a[0], b[0]);
}

B - Make Product Equal One

乱搞

#include <bits/stdc++.h>
#define ll long long
using namespace std;
int aa[200000];
int book[30000];
int main()
{
	int n;
	scanf("%d", &n);
	ll ans = 0;
	for (int i = 1; i <= n; i++)
	{
		scanf("%d", &aa[i]);
		if (aa[i] < 0)
		{
			ans -= 1 + aa[i];
			aa[i] = -1;
			book[2]++;
			continue;
		}
		else if (aa[i] > 0)
		{
			ans += aa[i] - 1;
			aa[i] = 1;
			book[1]++;
		}
		else
		{
			book[0]++;
		}
	}
	if ((book[2] & 1) == 0)
		ans += book[0];
	else
	{
		if (book[0] != 0)
			ans += book[0];
		else
			ans += 2;
	}
	printf("%lld", ans);
}

C - Almost Equal

简单构造，偶数判掉，然后奇数，一前一后构造

#include <bits/stdc++.h>
#define sc scanf
#define pr printf
#define ll long long
using namespace std;
const int MAXN = 200005;
int a[MAXN];
int main()
{
	int n;
	sc("%d", &n);
	if (n & 1)
	{
		puts("YES");
		int cnt = 1;
		for (int i = 1; i <= n; i++)
		{
			if (i & 1)
			{
				a[i] = cnt++;
				a[i + n] = cnt++;
			}
			else
			{
				a[i + n] = cnt++;
				a[i] = cnt++;
			}
		}
		for (int i = 1; i <= 2 * n; i++)
		{
			printf("%d%c", a[i], i == 2 * n ? '\n' : ' ');
		}
	}
	else
	{
		puts("NO");
	}
}

D - Shortest Cycle

给你n个点,每个点都有权值,两个点当且仅当(ai&aj)!=0时才会有边.
让你求最小的循环长度 (循环中的点要大于等于3)

点的权值的上限是1e18,比2^60小.
易得结论:n>120时必定存在一个循环长度为3的环
假设前60个点每个点都不会与其他点连边,这是最坏的情况,也就是每个点都是2的k次方这样子
那么后面不论加什么点都会与前面60个点的其中至少一个点连有边,再考虑最坏的情况,加入120
个点后恰好每两个点有边,此时再加入任意一个点,即存在一个环.
注意点的权值可以为0,把权值为0的点剔除就好.
对于n<=120 跑个floyd最小环

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll MAX = 1e3 + 5;
const ll INF = 0x3f3f3f3f;
const ll MAXN = 1e5 + 5;
ll n, m, book[MAX][MAX], dis[MAX][MAX];
ll A[MAXN], num = 0;
vector<ll> list1;
void solve() {
	int n;
	scanf("%d", &n);
	for (int i = 1; i <= n; ++i) {
		scanf("%lld", &A[i]);
		if (A[i] != 0) {
			++num;
			list1.push_back(A[i]);
		}
	}
	n = list1.size();
	for (int i = 1; i <= n; ++i) {
		A[i] = list1[i - 1];
	}
	if (n > 120) {
		printf("3\n");
		return;
	}
	for (int i = 1; i <= n; ++i) {
		for (int j = 1; j <= n; ++j) {
			book[i][j] = dis[i][j] = INF;
		}
	}
	for (int i = 1; i <= n; ++i) {
		for (int j = i + 1; j <= n; ++j) {
			if ((A[i] & A[j]) != 0) {
				ll  a, b, c;
				a = i, b = j, c = 1;
				ll w = book[a][b];
				dis[a][b] = dis[b][a] = book[a][b] = book[b][a] = min(w, c);
			}
		}
	}
	ll ans = INF;
	for (ll k = 1; k <= n; ++k) {
		for (ll i = 1; i <= n; ++i)
			for (ll j = 1; j <= n; ++j)
				if (i != j && j != k && i != k)
					ans = min(ans, dis[i][j] + book[i][k] + book[k][j]);
		for (ll i = 1; i <= n; ++i)
			for (ll j = 1; j <= n; ++j)
				dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j]);
	}
	if (ans == INF) printf("-1\n");
	else printf("%lld\n", ans);
}
int main(void)
{
	solve();
	return 0;
}

E - Palindromic Paths

赛后把输出中间的空格删掉了，就过了，我寻思再给我两分钟，我就能过这题？

1、首先确认位置是1，然后我们通过询问可以得到所有位置的值

2、然后我们假设位置是0，通过询问可以得到所有位置的值

3、那么我们现在知道了所有的值，和所有的相对值，如果我们能知道位置的某一个确定值，那么我们就可以确定矩阵

4、那么我们假设原矩阵为 A2 矩阵，将所有位置的值取反的矩阵为 A1 矩阵

5、那么我们希望在A1和A2里面找到一个相对位置相同的串，使得在 A1 A2 中，一个是回文串，另一个不是，这样我们就可以在一次询问中得到某个位置的确定值，然后判断一下这个位置的符号，不同就所有这个位置的元素取反，就可以AC。

#include <bits/stdc++.h>
#define sc scanf
#define pr printf
#define ll long long
using namespace std;
int a[55][55];
const int MAX = 1e3 + 5;
const int INF = 0x3f3f3f3f;
int color;
int A[MAX][MAX];
int A1[MAX][MAX], A2[MAX][MAX];
int N;
int DX[2] = { 0,1 }, DY[2] = { 1,0 };
int NOW1[4], NOW2[4];
int X1, Y1, X2, Y2;
bool FLAG = false;
bool VIS[MAX][MAX];
void dfs(int x, int y, int count) {
	if (FLAG)
		return;
	if (count == 4) {
		if (NOW1[1] == NOW1[2] && NOW1[0] == NOW1[3]) {
			if (NOW2[1] != NOW2[2] || NOW2[0] != NOW2[3]) {
				FLAG = true;
				X2 = x, Y2 = y;
				color = 1;
				return;
			}
		}
		if (NOW2[1] == NOW2[2] && NOW2[0] == NOW2[3]) {
			if (NOW1[1] != NOW1[2] || NOW1[0] != NOW1[3]) {
				FLAG = true;
				X2 = x, Y2 = y;
				color = 2;
				return;
			}
		}
		return;
	}
	for (int i = 0; i < 2; ++i) {
		int numX = x + DX[i];
		int numY = y + DY[i];
		if (numX >= 1 && numX <= N && numY >= 1 && numY <= N && \
			!VIS[numX][numY]) {
			NOW1[count] = A1[numX][numY];
			NOW2[count] = A2[numX][numY];
			VIS[numX][numY] = true;
			dfs(numX, numY, count + 1);
			VIS[numX][numY] = false;
		}
	}
}
void solve() {
	//sc("%d", &N);
	for (int i = 1; i <= N; ++i) {
		for (int j = 1; j <= N; ++j) {
			A[i][j] = a[i][j];
			if ((i + j) & 1) {
				if (A[i][j] == 0)
					A1[i][j] = 1, A2[i][j] = 0;
				else
					A1[i][j] = 0, A2[i][j] = 1;
			}
			else A1[i][j] = A2[i][j] = A[i][j];
		}
	}
	for (int i = 1; i <= N; ++i) {
		for (int j = 1; j <= N; ++j) {
			//			if(!((i+j)&1)){
			//				NOW1[0]=NOW2[0]=A1[i][j];
			NOW1[0] = A1[i][j];
			NOW2[0] = A2[i][j];
			VIS[i][j] = true;
			dfs(i, j, 1);
			VIS[i][j] = false;
			if (FLAG) {
				X1 = i, Y1 = j;
				return;
			}
		}
	}
}
 
 
int main()
{
	int n, t;
	sc("%d", &n);
	N = n;
	a[1][1] = 1;
	a[1][2] = 0;
	a[n][n] = 0;
	printf("? %d %d %d %d\n", 1, 2, 2, 3);
	fflush(stdout);
	scanf("%d", &t);
	if (t == 1)
		a[2][3] = a[1][2];
	else
		a[2][3] = a[1][2] ^ 1;
 
	printf("? %d %d %d %d\n", 2, 1, 2, 3);
	fflush(stdout);
	scanf("%d", &t);
	if (t == 1)
		a[2][1] = a[2][3];
	else
		a[2][1] = a[2][3] ^ 1;
 
	for (int i = 3; i <= n; i++)
	{
		printf("? %d %d %d %d\n", i - 2, 1, i, 1);
		fflush(stdout);
		scanf("%d", &t);
		if (t == 1)
			a[i][1] = a[i - 2][1];
		else
			a[i][1] = a[i - 2][1] ^ 1;
 
		printf("? %d %d %d %d\n", 1, i - 2, 1, i);
		fflush(stdout);
		scanf("%d", &t);
		if (t == 1)
			a[1][i] = a[1][i - 2];
		else
			a[1][i] = a[1][i - 2] ^ 1;
	}
	for (int i = 2; i <= n; i++)
	{
		for (int j = 2; j <= n; j++)
		{
			if (i == j && j == n)
				continue;
			if (i == 2 && j == 3)
				continue;
			printf("? %d %d %d %d\n", i - 1, j - 1, i, j);
			fflush(stdout);
			scanf("%d", &t);
			if (t == 1)
				a[i][j] = a[i - 1][j - 1];
			else
				a[i][j] = a[i - 1][j - 1] ^ 1;
		}
	}
 
	/*for (int i = 1; i <= n; i++)
		for (int j = 1; j <= n; j++)
			printf("%d%c", a[i][j], j == n ? '\n' : ' ');
	return 0;*/
	
	solve();
	printf("? %d %d %d %d\n", X1, Y1, X2, Y2);
	fflush(stdout);
	scanf("%d", &t);
	printf("!\n");
	if (t == 1)
	{
			if (color == 1)//不是
			{
				for (int i = 1; i <= n; i++)
				{
					for (int j = 1; j <= n; j++)
					{
						if ((i + j) % 2 == 1)
							printf("%d", a[i][j] ^ 1);
						else
							printf("%d", a[i][j]);
					}
					printf("\n");
				}
			}
			else
			{
				for (int i = 1; i <= n; i++)
				{
					for (int j = 1; j <= n; j++)
						printf("%d", a[i][j]);
					printf("\n");
				}
			}
	}
	else
	{
		if (color == 2)//是
		{
			for (int i = 1; i <= n; i++)
			{
				for (int j = 1; j <= n; j++)
				{
					if ((i + j) % 2 == 1)
						printf("%d", a[i][j] ^ 1);
					else
						printf("%d", a[i][j]);
				}
				printf("\n");
			}
		}
		else
		{
			for (int i = 1; i <= n; i++)
			{
				for (int j = 1; j <= n; j++)
					printf("%d", a[i][j]);
				printf("\n");
			}
		}
	}
}
/*
3
0
0
0
0
0
1
 
101
110
010
*/

F - Remainder Problem

两个操作，操作一，给定下标元素加上一个值，操作二，求

分块，预处理所有操作二的模数小于的，直接输出答案，对于模数大于的，暴力求出答案，复杂度，然后对于每一个操作一，我们只维护模数小于的，复杂度也是，总体复杂度

#include <bits/stdc++.h>
#define ll long long
#define sc scanf
#define pr printf
using namespace std;
ll s[715][715];
ll a[500005];
int main()
{
	int T;
	sc("%d", &T);
	while (T--)
	{
		int op, l, r;
		sc("%d%d%d", &op, &l, &r);
		if (op == 1)
		{
			for (int i = 1; i <= 710; i++)
				s[i][l % i] += r;
			a[l] += r;
		}
		else
		{
			ll ans = 0;
			if (l > 710)
			{
				for (int i = r; i <= 500000; i += l)
					ans += a[i];
			}
			else
			{
				ans = s[l][r];
			}
			printf("%lld\n", ans);
		}
	}
}