比赛时间

2020-05-20 13:00-18:00

提交记录

D: Accepted 2020-05-20 17:39:39

D: Runtime Error(ACCESS_VIOLATION) 2020-05-20 17:19:16

D: Time Limit Exceeded 2020-05-20 17:05:43

J: Accepted 2020-05-20 16:48:33

C: Accepted 2020-05-20 16:41:33

C: Wrong Answer 2020-05-20 16:35:54

C: Wrong Answer 2020-05-20 16:30:29

J: Wrong Answer 2020-05-20 16:26:31

J: Wrong Answer 2020-05-20 16:22:36

K: Accepted 2020-05-20 13:57:23

B: Accepted 2020-05-20 13:36:47

A: Accepted 2020-05-20 13:14:42

solved by Zars19

给出元素为$\{0,1,2\}$的$N\times M$的矩阵，对某个格子进行操作时对该位置的值加$2$，四周分别加$1$，结果都是模$3$意义下的。给出的矩阵最终必能在$2NM$次操作内化为全$0$，输出一种操作。

题解：模$3$意义下的高斯消元，对于每一个位置$a_{i,j}+2\times opt_{i,j}+\sum opt_{i+dx,j+dy}\equiv 0 \pmod 3$。格子至多$30\times 30$个，看起来$O(N^3M^3)$好像不太行，但事实上每一个方程所关联到的变量不多，矩阵较为稀疏，注意if(!a[mxline][i])continue;即可。

code:

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cassert>
#include<cstdlib>
#include<cmath>
#include<vector>
#include<algorithm>
#define LL long long
using namespace std;
int read()
{
	int x=0,f=1;char c=getchar();
	while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
	while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
	return x*f;
}
int n,m,chess[33][33],a[1001][1001],f[1001],res;
int num(int x,int y){return (x-1)*m+y;}
int dx[4]={-1,1,0,0};
int dy[4]={0,0,-1,1};
bool in(int x,int y){return x>=1&&x<=n*m&&y>=1&&y<=m;}
void exgcd(LL a,LL b,LL &d,LL &x,LL &y)
{
    if(!b)d=a,x=1,y=0;
    else exgcd(b,a%b,d,y,x),y-=x*(a/b);
}
LL inv(LL a,LL p)
{
    LL d,x,y;exgcd(a,p,d,x,y);
    return (x+p)%p==0?p:(x+p)%p;
}
void Gauss()
{
	for(int i=1;i<=n*m;i++)
	{
		int mxline=i;
		for(int j=i;j<=n*m;j++)
		if(a[j][i]>a[mxline][i])mxline=j;
		if(!a[mxline][i])continue;
		if(mxline!=i)
		for(int j=i;j<=n*m+1;j++)swap(a[mxline][j],a[i][j]);
		for(int j=i+1;j<=n*m;j++)
		{
			if(!a[j][i])continue;
			int t=a[j][i]*inv(a[i][i],3)%3;
			for(int k=i;k<=n*m+1;k++)
			a[j][k]=(a[j][k]-(t*a[i][k]%3)+3)%3;
		}
	}
	for(int i=n*m;i;i--)
	{
		for(int j=n*m;j>i;j--)
		a[i][n*m+1]=((a[i][n*m+1]-f[j]*a[i][j]%3)+3)%3;
		f[i]=a[i][n*m+1]*inv(a[i][i],3)%3;
		if(f[i])res+=f[i];
	}
}
int main()
{
	int T=read();
	while(T--)
	{
		memset(a,0,sizeof(a));
		n=read(),m=read(),res=0;
		for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
		chess[i][j]=read();
		for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
		{
			a[num(i,j)][n*m+1]=(3-chess[i][j])%3;
			a[num(i,j)][num(i,j)]=2;
			for(int k=0;k<4;k++)
			{
				int tx=i+dx[k],ty=j+dy[k];
				if(!in(tx,ty))continue;
				a[num(tx,ty)][num(i,j)]=1;
			}
		}
		Gauss();
		printf("%d\n",res);
		for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
		for(int k=1;k<=f[num(i,j)];k++)
		printf("%d %d\n",i,j);
	}
	return 0;
}

有一条在坐标轴上的河，一条船目前在$(0,a)$，水流速度$v_2$延x轴，船的速度$v_1$始终指向原点，问船需要多久到达原点。

$0\leq a,v_1,v_2 \leq 100$

如图

_wzx27开到A发现可打表找范围做，提交，正确。

Zars19发现J是可做物理题，和_wzx27讨论，好像要积分，然后不会。

发现很多人过B，读题，infinity37提出概率大概是固定的。

infinity37找到1/3和1/2概率规律，提交B，正确。

三人讨论K题，过得人太多了，感到迷惑。

infinity37提出曼哈顿距离种数依赖于坐标范围，种数不多，鸽巢原理暴力即可，Zars19附和。

infinity37提交K题，正确。

_wzx27开到D题发现可做，提出爆搜DP说。

Zars19加入D题资源开发，提出贪心说（后证实为假）。

infinity37阐述了C题概况，手玩得到king解和castle猜想

_wzx27和Zars19加入进行一些讨论

讨论了knight平局问题，king解打表得到证实，castle猜想可以直接归纳证明。

进行了很多对queue的讨论，Zars19打了一些表（虽然最后不太有用）

_wzx27提出C题皇后的O(NM)做法。去写C

_wzx27提交C题，wa两次后正确。

infinity37去积分了，得到J题柿子，Zars19和_wzx27以为然。

infinity37提交J题，wa了2次，其间更正了下无解条件。

infinity37使用G++提交J题，正确，之前疑似是选用C++编译器导致的精度问题。

Zars19提出D题高斯消元说，开始写。

Zars19提交D题，由于没有continue掉多解消元时主对角线上元素为0的情况TLE一次。然后出现了令人疑惑的RE

种种推理下没有道理RE，扩大数组范围再交，数据范围可能假了，D正确。

大家这次状态比上次好，不过可能是因为题比上次的可做，区分度没有把我们区分出去，不过我不太行好几个题反应很迟钝orz。rank1是8题，比我们题多的一般会做出来相对更可做的G（我错了这好像是我的树DP）和不太可做我们没开到的E（好像是主席树）或者I（字符串DP）。罚时有点多，6题里面我们很靠后了，对一些套路更熟悉的话有些题应该可以更快想到，另外交题的时候可以冷静一点。

这次比赛签到题过的比较快，但是中部用了很多时间解题，说明我们的解题速度还有待加强，同时认识到了我们在博弈论上有一些缺陷，那么就这么愉快的决定了，这周就学博弈论（）

这次做得比上次好一点，可能是因为简单一点（不过为什么会有物理题啊）。不过感觉自己手速和思维都好慢啊，有待提高。以及知识点不够全，有些题不怎么有思路，还是得拓宽知识面才行。