20zr提高组十连测day4

阴间的dmy

http://www.zhengruioi.com/contest/703

提高组D2T1送分题

但是题面不够长所以qwq

做法: $f_{i,j}$ 表示第一个串匹配到i第二个串匹配到j的最小代价

然后转移:

$a_i!=b_j$

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

$a_i==b_j$

f_{i,j}=f_{i-1,j-1}

优化:因为答案不会超过50,所以第二维有用的只有100个状态

直接用这些dp即可

其实本题造数据很难把

code:


#include<bits/stdc++.h>
using namespace std;
const int MAXN=1e5+7;
int n;
int f[MAXN][105];
char s[MAXN],t[MAXN];
int main() {
	scanf("%s",s+1);
	scanf("%s",t+1);
	int n1=strlen(s+1);
	int n2=strlen(t+1);
	if(n1<n2) {
		swap(n1,n2);
		swap(s,t);
	}
	if(n1-n2>50)return printf("-1"),0;
	memset(f,0x3f3f3f3f,sizeof(f));
	f[0][50]=0;
	for(int i=1; i<=n1; ++i) {
		for(int j=50; j>=-50; --j) {
			int p=i-j;
			if(p<0 || p>n2)continue;
			if(s[i]==t[p]) {
				f[i][j+50]=f[i-1][j+50];
			} else {
				f[i][j+50]=min(f[i][j+1+50],min(f[i-1][j-1+50],f[i-1][j+50]))+1;
			}
		}
	}
	if(f[n1][n1-n2+50]>50)return printf("-1"),0;
	printf("%d\n",f[n1][n1-n2+50]);
	return 0;
}

神仙数学题

你考虑维护两个L,R是2的幂次,同时满足形式:

11111111(k个)00000000....

11111112(k个)00000000....

然后考虑合法成为答案的数x一定在 $l,r$ 之间

那么这个数字的幂次要尽可能的小于是想到再维护两个和这个差不多的 $Lx,Rx$

Lx表示把前200位拿出来的前缀幂次最小值,如果不够两百位我们后面用0补齐两百位

Rx表示把前两百位拿出来的前缀幂次最大值不够两百位也是用零补齐

然后每次用x*Lx,如果正好大于L就是答案,否则我们如果小于Rx就留下更新然后不乘了

否则然后更新一次后我们把 $Lx*Rx$ 这个值去考虑更新 $Lx,Rx$ 如果大于Rx更新Rx否则更新Lx

因为我们Lx,Rx的性质他一定满足大于或小于!

那你会发现 $LxRx$ 的形式都是

1000000000(x个)????...

9999999999(y个)????...

所以仔细思考一下我们一定能倍增出第一个合法的了

然后做完了

code:



#include <bits/stdc++.h>
#define ll long long
#define maxn 100005 /*rem*/
#define mod 998244353
#define db double
#define vi vector<int>
#define pb push_back
#define mp make_pair
#define pi pair<int, int>
#define fi first
#define se second
using namespace std;
ll ksm(ll a, ll b) {
   if (!b) return 1;
   ll ns = ksm(a, b >> 1);
   ns = ns * ns % mod;
   if (b & 1) ns = ns * a % mod;
   return ns;
}
const int mxs = 230; /*reme*/
void upd(vi &a) {
	for (int i = 0; i < a.size(); i++)
		if (a[i] >= 10) {
			if (i == a.size() - 1)
				a.pb(a[i] / 10);
			else a[i + 1] += a[i] / 10;
			a[i] %= 10;
		}	
	if (a.size() > mxs) {
		for (int j = 0; j < mxs; j++)
			a[j] = a[a.size() - mxs + j];
		a.resize(mxs);
	} 
}
void otp(vi a) {
	for (int i = a.size() - 1; i >= 0; i--)
		cout << a[i];
	cout << endl;
}
vi operator * (vi &a, vi &b) {
	vi c(a.size() + b.size() - 1);
	for (int i = 0; i < c.size(); i++) c[i] = 0;
	for (int i = 0; i < a.size(); i++)
		for (int j = 0; j < b.size(); j++)
			c[i + j] += a[i] * b[j];
	upd(c);
//	cout <<"NUL" << endl;
//	otp(a), otp(b), otp(c);
	return c;
}
bool operator < (vi &a, vi &b) {
	for (int i = a.size() - 1; i >= 0; i--)
		if (a[i] != b[i]) return a[i] < b[i];
	return 0;
} 
vi operator + (vi &a, vi &b) {
	vi c(max(a.size(), b.size()));
	for (int i = 0; i < c.size(); i++) {
		c[i] = 0;
		if (i < a.size())
			c[i] += a[i];
		if (i < b.size())
			c[i] += b[i];
	}
	upd(c);
	return c;
}
struct pw {
	vi a;
	vi b; // ��
	pw(){a.clear(), b.clear();}
	pw(vi x, vi y) {
		a = x, b = y;
	} 
	pw operator * (pw c) {
		
		return pw(a * c.a, b + c.b);
	}
};
pw L, R, cur;
vi lb, mx;
char inp[mxs];
void otp(pw a) {
	otp(a.a), otp(a.b);
}
int main() {
//	freopen("power.in", "r", stdin);
//	freopen("power.out", "w", stdout);
	int l;
	cin >> l;
	for (int i = 0; i < l; i++)
		inp[i] = '1';
	vi u, v;
	for (int i = 0; i < mxs - 1; i++)
		u.pb(0);
	u.pb(2), v.pb(1);	
	for (int i = 0; i < mxs - l; i++)
		lb.pb(0), mx.pb(9);
	for (int i = l - 1; i >= 0; i--)
		lb.pb(inp[i] - '0'), mx.pb(inp[i] - '0'); 
	L = pw(u, v);
	R = pw(u, v);		
	v[0] = 0, u[mxs - 1] = 1;
	cur = pw(u, v);
	while (1) {
	//	otp(L), otp(R);
		while (1) {
			pw ed = cur * L;
		//	otp(ed);
			if (cur.a < ed.a && ed.a < mx) {
				cur = ed;
				if (!(cur.a < lb)) {
					for (int i = cur.b.size() - 1; i >= 0; i--)
						cout << cur.b[i];
					cout << endl;
					return 0;
				}
			}
			else break;
		}
		while (1) {
			pw nr = L * R;
			if (nr.a[mxs - 1] == 1) {
				L = nr;
				break;
			}
			else R = nr;
		}
	}
	return 0;
}



不是自己写的

倒序染色

然后你会发现我们每次还没有染色的相邻的不能染同一种颜色

其他的随便染上当前颜色即可

这个k的构造方式就是每次 $n-n/3$ 的迭代到0的次数....

可以证明最后这样染出颜色的方案一定不会存在一个区间的没有出现次数为1的

因为不管怎么样你都会被一个新颜色叉掉

倒序是因为前面的限制严,要用出现次数少的颜色

code:



#include<bits/stdc++.h>
using namespace std;
const int MAXN = 1e5 + 7;
int n, k, a[MAXN];
//考虑用一种颜色染大于sum/3的灯然后我们递归剩下的解决
//我们要小心任何时刻都不能有相临相同的?
int b[MAXN], vis[MAXN], c[MAXN];
vector<int>  near[MAXN];
set<int> st;
inline void init() {
	st.clear();
	st.insert(n + 1);
	st.insert(0);
	for(int i = 1; i <= n; ++i) {
		near[i].clear();
	}
	for(int i = 1; i <= n; ++i)
		if(!vis[i]) {
			auto qwq1 = st.lower_bound(i);
			auto qwq2 = st.upper_bound(i);
			// printf("%d?%d\n", qwq1, qwq2);
			// near[a[i]].push_back(*qwq2);
			// near[*qwq2].push_back(a[i]);
			qwq1--;
			near[i].push_back(*qwq1);
			near[i].push_back(*qwq2);
			near[*qwq1].push_back(i);
			near[*qwq2].push_back(i);
			st.insert(i);
		}
	for(int i = 1; i <= n; ++i) {
		if(!vis[i]) {
			sort(near[i].begin(), near[i].end());
			near[i].erase(unique(near[i].begin(), near[i].end()), near[i].end());
			// printf("%d\n", i);
			// for(auto v : near[i]) {
			// 	printf("%d ", v);
			// }
			// puts("??");
		}
	}
	return ;
}

inline void solve(int l, int r, int dep) {
	if(l > r)return;
	// printf("%d %d %d\n", l, r, dep);
	init();
	int limit = ceil((double)(r - l + 1) / 3);
	// if(limit == 0)limit = 1;
	for(int i = r; i >= l; --i) {
		int p = a[i];
		if(!vis[p]) {
			bool flg = 1;
			// printf("in- > %d\n", p);
			for(auto v : near[p]) {
				if(b[v] == dep) {
					// printf("%d %d???\n", v, dep);
					flg = 0;
				}
			}
			if(flg) {
				vis[p] = 1;
				b[p] = dep;
				limit--;
				// printf("%d %d\n", p, dep);
			}
		}
		if(!limit)break;
	}
	int tot = 0;
	for(int i = l; i <= r; ++i) {
		if(!vis[a[i]]) {
			// printf("%d?\n", i);
			c[++tot] = a[i];
		}
	}
	// printf("tot->%d\n", tot);
	for(int i = l; i <= l + tot - 1; ++i) {
		// printf("%d\n", c[i - l + 1]);
		a[i] = c[i - l + 1];
	}
	// if(l = l + tot - 1)
	solve(l, l + tot - 1, dep + 1);
	return ;
}

int main() {
	scanf("%d%d", &n, &k);
	for(int i = 1; i <= n; ++i)scanf("%d", &a[i]);
	init();
	solve(1, n, 1);
	for(int i = 1; i <= n; ++i)printf("%d ", b[i]);
	puts("");
	return 0;
}

/*

3 3
1  2  3

4 3
4 3 2 1

*/

夏晓光(loveJY)的博客

因为我们Lx,Rx的性质他一定满足大于或小于!

ZR2020普转提七连测day3