2020-11-25 examination summary

The test is very fried. It's not that there are too many points. It's mainly because I didn't expect it, but it seems that the ranking is better without points???

T1

A lot of water, too lazy to talk.

T2 CF575A Fibonotci

Title portal

thinking

Hu is really a good hu, but it needs some skills to realize it. So we learn from Rainybunny's Code

It is not difficult to see that if there is no modification operation, the number of each \ (n \) must be a cycle segment, and the relative relationship between a certain number of each cycle segment and the first two numbers is determined. This thing can be optimized with a matrix.

Considering the modification, it is not difficult to see that a matrix has been changed. Specifically, it can be directly disassembled for consideration. However, the trouble is how to consider the two adjacent modifications. In fact, you can record how many first bits have been considered, and judge whether the matrix is considered by judging the relationship between the current bit and the modification point. See the code for details.

\(\texttt{Code}\)

#include <bits/stdc++.h>
using namespace std;

#define Int register int
#define int long long
#define MAXN 50005

template <typename T> inline void read (T &t){t = 0;char c = getchar();int f = 1;while (c < '0' || c > '9'){if (c == '-') f = -f;c = getchar();}while (c >= '0' && c <= '9'){t = (t << 3) + (t << 1) + c - '0';c = getchar();} t *= f;}
template <typename T,typename ... Args> inline void read (T &t,Args&... args){read (t);read (args...);}
template <typename T> inline void write (T x){if (x < 0){x = -x;putchar ('-');}if (x > 9) write (x / 10);putchar (x % 10 + '0');}

int n,m,K,lg,mod,s[MAXN];
int mul (int a,int b){return 1ll * a * b % mod;}
int dec (int a,int b){return a >= b ? a - b : a + mod - b;}
int add (int a,int b){return a + b >= mod ? a + b - mod : a + b;}

struct Matrix{
	int a,b,c,d;
	Matrix(){}
	Matrix (int _a,int _b,int _c,int _d){a = _a,b = _b,c = _c,d = _d;}
	Matrix operator * (const Matrix &p)const{return Matrix (add (mul (a,p.a),mul (b,p.c)),add (mul (a,p.b),mul (b,p.d)),add (mul (c,p.a),mul (d,p.c)),add (mul (c,p.b),mul (d,p.d)));}
}st[MAXN][65],tmp,ans;

void init (){
	for (Int i = 0;i < n;++ i) st[i][0] = Matrix (0,1,s[i],s[(i + 1) % n]);
	for (Int j = 1;(1ll << j) <= K;lg = j ++)
		for (Int i = 0;i < n;++ i)
			st[i][j] = st[(i + (1ll << j - 1)) % n][j - 1] * st[i][j - 1];
}

void getit (int& cur,int goal){
	for (Int i = lg;~i;-- i)
		if (cur + (1ll << i) < goal)
			ans = st[cur % n][i] * ans,cur += (1ll << i);
}

#define PII pair<int,int>
PII sk[MAXN];

signed main(){
	read (K,mod,n);
	if (mod == 1) return puts ("0"),0;
	for (Int i = 0;i < n;++ i) read (s[i]);
	init ();
	read (m);for (Int i = 1;i <= m;++ i){
		read (sk[i].first,sk[i].second);
		if (sk[i].first >= K) -- i,-- m; 
	}
	sort (sk + 1,sk + m + 1),ans.c = 1;int cur = 0;
	for (Int i = 1;i <= m;++ i){
		getit (cur,sk[i].first);
		if (cur < sk[i].first) tmp = Matrix (0,1,s[cur % n],sk[i].second),ans = tmp * ans,++ cur;
		if (i != m && sk[i + 1].first == sk[i].first + 1) tmp = Matrix (0,1,sk[i].second,sk[i + 1].second);
		else tmp = Matrix (0,1,sk[i].second,s[(cur + 1) % n]);
		ans = tmp * ans,++ cur;
	}
	getit (cur,K);
	write (cur < K ? ans.c : ans.a),putchar ('\n');
	return 0;
}

T3 CF480E Parking Lot

Title portal

thinking

The original question can't make a series...

First, consider the 50 pts method (I won't tell you that the result of \ (nmk\log n \) I wrote is only 10 pts). It's easy to see that we can set \ (f {I, J} \) to represent the maximum square side length with \ ((i,j) \) as the bottom, and get the transfer formula:

\[f_{i,j}=\min(f_{i-1,j},f_{i,j-1},f_{i-1,j-1})+1 \]

Considering 100 pts, it is not difficult to see whether it is good to do it, so we can do it backwards. So the requirement is to delete a position, including the maximum square side length of this position.

This is easy to do. We can use and query the set to maintain the vacancy, and then use monotonicity to achieve \ (\ Theta(nm) \). (assume that the join search set is linear.)

\(\ texttt{Code} \) (the code from a year ago)

#include<bits/stdc++.h>
using namespace std;
const int maxn = 2e3 + 10;
int n,m,k;
int Ans;
int dp[maxn][maxn];
int l1[maxn];
int r1[maxn];
int qx[maxn];
int qy[maxn];
int ans[maxn];
char Map[maxn][maxn];

struct node
{
	int fa[maxn];
	int findSet (int x)
	{
		if (x == fa[x]) return x;
		else return fa[x] = findSet (fa[x]);
	}
}l[maxn],r[maxn];

void Delete(int x,int y)
{
	l[x].fa[y] = l[x].findSet(y - 1);
	r[x].fa[y] = r[x].findSet(y + 1);
}

int main()
{
	scanf("%d%d%d",&n,&m,&k);
	for(int i = 1; i <= n; i++)
		scanf("%s", Map[i]+1);
	for(int i = 1; i <= k; i++)
	{
		scanf("%d%d",&qx[i],&qy[i]);
		Map[qx[i]][qy[i]] = 'X';
	}
	for(int i = 1; i <= n; i++)
	{
		for(int j = 1; j <= m+1; j++)
		{
			l[i].fa[j] = j;
			r[i].fa[j] = j;
		}
	}
	for(int i = 1; i <= n; i++)
		for(int j = 1; j <= m; j++)
			if(Map[i][j] == '.')
				Delete(i, j);
	for(int i = 1; i <= n; i++)
		for(int j = 1; j <= m; j++)
			if(Map[i][j] == '.')
			{
				dp[i][j] = min(dp[i-1][j-1], min(dp[i-1][j],dp[i][j-1]))+1;
				Ans = max (Ans,dp[i][j]);
			}
	for (int j = k;j >= 1;-- j)
	{
		ans[j] = Ans;
		Delete (qx[j],qy[j]);
		for(int i = 1; i <= n; i++)
		{
			l1[i] = qy[j] - l[i].findSet(qy[j]);
			r1[i] = r[i].findSet(qy[j]) - qy[j];
		}
		for(int i = qx[j] + 1; i <= n; i++)
		{
			l1[i] = min(l1[i], l1[i - 1]);
			r1[i] = min(r1[i], r1[i - 1]);
		}
		for(int i = qx[j] - 1; i; i--)
		{
			l1[i] = min(l1[i], l1[i + 1]);
			r1[i] = min(r1[i], r1[i + 1]);
		}
		for(int i = 1; i <= qx[j]; i++)
			while(min(r1[i], r1[i + Ans]) + min(l1[i], l1[i + Ans]) - 1 > Ans)
				Ans++;
	}
	for(int i = 1; i <= k; i ++)
		printf("%d\n",ans[i]);
	return 0;
}

T4 ant

Title portal

thinking

It is not difficult to see the Gaussian elimination optimization of \ (n^6 \).

It is not difficult to see that if we determine the expected value on the boundary, we can determine the dp value of each point. So you can do \ (\ Theta(n^3) \) by solving the equation.

\(\texttt{Code}\)

#include <bits/stdc++.h>
using namespace std;

#define hash screwyourwholefamily
#define double long double
#define Int register int
#define get whysoserious
#define MAXN 205

template <typename T> inline void read (T &t){t = 0;char c = getchar();int f = 1;while (c < '0' || c > '9'){if (c == '-') f = -f;c = getchar();}while (c >= '0' && c <= '9'){t = (t << 3) + (t << 1) + c - '0';c = getchar();} t *= f;}
template <typename T,typename ... Args> inline void read (T &t,Args&... args){read (t);read (args...);}
template <typename T> inline void write (T x){if (x < 0){x = -x;putchar ('-');}if (x > 9) write (x / 10);putchar (x % 10 + '0');}

int n,m,x,y;
int hash (int x,int y){return !x ? y : m - 1 + x;}

struct node{
	double a[MAXN << 1];
}get[MAXN][MAXN];

double mat[MAXN][MAXN],f[MAXN];

signed main(){
//	freopen ("ant.in","r",stdin);
//	freopen ("ant.out","w",stdout);
	read (n,m,x,y);
	for (Int i = 0;i < m;++ i) get[0][i].a[hash (0,i)] = 1;
	for (Int i = 0;i < n;++ i) get[i][0].a[hash (i,0)] = 1;
	for (Int i = 1;i < n;++ i)
		for (Int j = 1;j < m;++ j){
			for (Int k = 0;k <= n + m - 1;++ k)
				get[i][j].a[k] = 0.5 * (get[i - 1][j].a[k] + get[i][j - 1].a[k]);
			get[i][j].a[n + m - 1] ++;
		}
	int up = n + m - 1;
	mat[0][0] = 1;
	for (Int i = 1;i < m;++ i){
		mat[hash (0,i)][hash (0,i)] = mat[hash (0,i)][up] = 2;
		for (Int j = 0;j <= up;++ j) if (j != up) mat[hash (0,i)][j] -= get[0][i - 1].a[j];else mat[hash (0,i)][j] += get[0][i - 1].a[j];
		for (Int j = 0;j <= up;++ j) if (j != up) mat[hash (0,i)][j] -= get[n - 1][i].a[j];else mat[hash (0,i)][j] += get[n - 1][i].a[j];
	}
	for (Int i = 1;i < n;++ i){
		mat[hash (i,0)][hash (i,0)] = mat[hash (i,0)][up] = 2;
		for (Int j = 0;j <= up;++ j) if (j != up) mat[hash (i,0)][j] -= get[i - 1][0].a[j];else mat[hash (i,0)][j] += get[i - 1][0].a[j];
		for (Int j = 0;j <= up;++ j) if (j != up) mat[hash (i,0)][j] -= get[i][m - 1].a[j];else mat[hash (i,0)][j] += get[i][m - 1].a[j];
	}	
	for (Int i = 0;i < up;++ i){
		int pos = i;
		for (Int j = i + 1;j < up;++ j) if (abs (mat[j][i]) > abs (mat[pos][i])) pos = j;
		if (abs (mat[pos][i]) < 1e-9) continue;
		if (pos ^ i) swap (mat[pos],mat[i]);
		for (Int j = i + 1;j < up;++ j){
			double d = mat[j][i] / mat[i][i];
			for (Int k = i;k <= up;++ k) mat[j][k] -= mat[i][k] * d; 
		} 
	}
	for (Int i = up - 1;~i;-- i){
		for (Int j = i + 1;j < up;++ j)
			mat[i][up] -= mat[i][j] * f[j];
		f[i] = mat[i][up] / mat[i][i];
	}
	double ans = get[x][y].a[up];
	for (Int i = 0;i < up;++ i) ans += get[x][y].a[i] * f[i];
	printf ("%.15Lf\n",ans);
	return 0;
}

Tags: dp matrix

Posted by Nick~C on Thu, 05 May 2022 23:54:46 +0300