2020SpringTraining/TeamTraining20200419

训练情况

训练时间: 2020-04-19 13:00-18:00

训练地址: http://codeforces.com/gym/102465

总共写出A,B,C,D,E,F,H,K共八题

A City of Lights

暴力开关即可 –by hxm

#include<algorithm>
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<cstdio>
#include<vector>
#include<queue>
#include<cmath>
#include<map>
#include<set>
#define LL long long int
#define REP(i,n) for (int i = 1; i <= (n); i++)
#define Redge(u) for (int k = h[u],to; k; k = ed[k].nxt)
#define cls(s,v) memset(s,v,sizeof(s))
#define mp(a,b) make_pair<int,int>(a,b)
#define cp pair<int,int>
using namespace std;
const int maxn = 1000005,maxm = 100005,INF = 0x3f3f3f3f;
inline int read(){
	int out = 0,flag = 1; char c = getchar();
	while (c < 48 || c > 57){if (c == '-') flag = 0; c = getchar();}
	while (c >= 48 && c <= 57){out = (out << 1) + (out << 3) + c - 48; c = getchar();}
	return flag ? out : -out;
}
int st[maxn],n,k,sum = 0,ans = 0;
int main(){
	n = read(); k = read();
	int x;
	while (k--){
		x = read();
		for (int i = x; i <= n; i += x){
			if (!st[i]) sum += 1;
			else sum -= 1;
			st[i] ^= 1;
		}
		ans = max(ans,sum);
	}
	printf("%d\n",ans);
	return 0;
}

B Blurred Pictures

题目大意:

给一个\(n*n\) 的01像素图,求最大全1正方形

每行的像素1的分布都是一段连续的区间,而且左端点是单峰向左凸的(或者单调递减),右端点是单峰向右凸的(或者单调递增)

根据这个性质,可以分析出如何判断一段区域是否为正方形,直接判断他的上下两条边是否符合要求就行(因为不会出现两边凹进去的情况)

#include<bits/stdc++.h>
using namespace std;
#define mem(a,b) memset(a,b,sizeof(a))
typedef long long LL;
typedef pair<int,int> PII;
#define X first
#define Y second
inline int read()
{
	int x=0,f=1;char c=getchar();
	while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
	while(isdigit(c)){x=x*10+c-'0';c=getchar();}
	return x*f;
}
const int maxn=100010;
int n,l[maxn],r[maxn],ans,L,R;
bool judge(int index)
{
	for(int i=1;i<=n-index+1;i++)
	{
		if(r[i]-l[i]+1<index)continue;
		int tmp=max(l[i],l[i+index-1]);
		if(r[i+index-1]-tmp+1<index)continue;
		if(r[i]-tmp+1<index)continue;
		ans=max(ans,index);
		return 1;
	}
	return 0;
}
int main()
{
	n=read();
	for(int i=1;i<=n;i++)l[i]=read(),r[i]=read();
	L=1;R=n;
	while(R-L>1)
	{
		int mid=L+R>>1;
		if(judge(mid))L=mid;
		else R=mid;
	}
	judge(L);judge(R);
	printf("%d\n",ans);
	return 0;
}

–by fyh

C Crosswords

–by wxg

题意:给了两个字符串组,字符串的长度为 \(M,N(2 \leq N,M \leq 4)\) 要求你求出有多少个\(N \times M\) 字母矩阵,每行和每列的单词都在给定的字符串组里。

可以知道较小字符串组里最多有 \(10^3\) 个字符串,最多出现 4 个字符串,搜索的暴力复杂度是 \(10^{12}\) ,但我们可以剪枝,对另一个字符串组建trie树,记录之前矩阵每列字符串在trie树中的位置,枚举当前行的字符串,同时每列在trie树上看能不能走下一步,不能走就剪掉。这样就用玄学复杂度通过了此题。

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#define ll long long
using namespace std;
int read()
{
	int k=0,f=1;char c=getchar();
	for(;!isdigit(c);c=getchar()) if(c=='-') f=-1;
	for(;isdigit(c);c=getchar()) k=k*10+c-'0';return k*f;
}
char s[10005][5],str[55];
int tot,ch[100005][26],val[100055];
int n,m,p,q,ans,pos[10],la[10][10],vis[10005];
void ins()
{
	int len=strlen(str),now=0;
	for(int i=0;i<len;i++)
		if(!ch[now][str[i]-'a'])
		{
			ch[now][str[i]-'a']=++tot;
			now=ch[now][str[i]-'a'];
		}
		else now=ch[now][str[i]-'a'];
}	
void dfs(int dep)
{
	if(dep>m)  {ans++;return;}
	for(int i=1;i<=p;i++)
		{
			int fl=1;
			for(int j=0;j<n;j++)
				if(!ch[pos[j]][s[i][j]])
				{
					fl=0;break;
				}
			if(fl)
			{	
				for(int j=0;j<n;j++)
					la[dep][j]=pos[j],pos[j]=ch[pos[j]][s[i][j]];
				dfs(dep+1);
				for(int j=0;j<n;j++)
					pos[j]=la[dep][j];
			}
		}
}
int main()
{
	n=read();p=read();
	m=read();q=read();
	if(p<=q)
	{
		for(int i=1;i<=p;i++)
			scanf("%s",s[i]);
		for(int i=1;i<=q;i++)
			scanf("%s",str),ins();
	}
	else 
	{
		for(int i=1;i<=p;i++)
			scanf("%s",str),ins();
		for(int i=1;i<=q;i++)
			scanf("%s",s[i]);
		swap(n,m);swap(p,q);
	}
	for(int i=1;i<=p;i++)
		for(int j=0;j<n;j++)
			s[i][j]-='a';
	dfs(1);
	cout<<ans<<endl;
	return 0;
}

D Monument Tour

求一条平行y轴的直线使所有不被其它点遮挡的点到这条直线距离和最小n

扫一遍动态更新答案即可

–by hxm

#include<algorithm>
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<cstdio>
#include<vector>
#include<queue>
#include<cmath>
#include<map>
#include<set>
#define LL long long int
#define REP(i,n) for (int i = 1; i <= (n); i++)
#define Redge(u) for (int k = h[u],to; k; k = ed[k].nxt)
#define cls(s,v) memset(s,v,sizeof(s))
#define mp(a,b) make_pair<int,int>(a,b)
#define cp pair<int,int>
using namespace std;
const int maxn = 100005,maxm = 100005;
LL INF = 1000000000000000ll;
inline int read(){
	int out = 0,flag = 1; char c = getchar();
	while (c < 48 || c > 57){if (c == '-') flag = 0; c = getchar();}
	while (c >= 48 && c <= 57){out = (out << 1) + (out << 3) + c - 48; c = getchar();}
	return flag ? out : -out;
}
int n,m,N;
int X[maxn],Y[maxn],id[maxn];
int cnt[maxn];
LL ans1[maxn],ans2[maxn];
inline bool cmp(const int& a,const int& b){
	return Y[a] == Y[b] ? X[a] < X[b] : Y[a] < Y[b];
}
int main(){
	n = read(); m = read(); N = read();
	REP(i,N) X[i] = read(),Y[i] = read(),id[i] = i;
	sort(id + 1,id + 1 + N,cmp);
	int now = 0,tot = 0;
	for (int i = 1; i <= N; i++){
		int u = id[i];
		ans1[i] = ans1[i - 1] + 2ll * (Y[u] - now) * tot;
		now = Y[u];
		if (cnt[X[u]]) tot -= cnt[X[u]],cnt[X[u]] = 0;
		cnt[X[u]]++; tot++;
	}
	now = 100000; tot = 0;
	for (int i = 0; i <= 100000; i++) cnt[i] = 0;
	for (int i = N; i; i--){
		int u = id[i];
		ans2[i] = ans2[i + 1] + 2ll * (now - Y[u]) * tot;
		now = Y[u];
		if (cnt[X[u]]) tot -= cnt[X[u]],cnt[X[u]] = 0;
		cnt[X[u]]++; tot++;
	}
	LL ans = INF;
	for (int i = 1; i <= N; i++) ans = min(ans,ans1[i] + ans2[i]);
	cout << ans + n - 1 << endl;
	return 0;
}

E Rounding

–by wxg

题意:给了 \(P\) 个频率的百分数,这些频率都是四舍五入到个位的,已知这些频率都是两位小数,求每个频率四舍五入之前的可能最小值和可能最大值。(P个频率之和为100%)

先判断可不可能

之后逐个计算,先求其他的频率的最小值和最大值,再看这个值能取多少,复杂度 \(O(P^2)\)

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#define ll long long
using namespace std;
int read()
{
	int k=0,f=1;char c=getchar();
	for(;!isdigit(c);c=getchar()) if(c=='-') f=-1;
	for(;isdigit(c);c=getchar()) k=k*10+c-'0';return k*f;
}
int n,m,l,r,a[10005];
int mn(int x)
{
	if(!x) return 0;
	else return x*100-50;
}
int mx(int x)
{
	if(x==100) return x*100;
	else return x*100+49;
}
char s[10005][22];
int main()
{
	int fl=0;
	n=read();
	for(int i=1;i<=n;i++)
	{
		scanf("%s%d",s[i],&a[i]);
		l+=mn(a[i]);
		r+=mx(a[i]);
	}
	if(l>10000||r<10000)
	{
		puts("IMPOSSIBLE");return 0;
	}
	for(int i=1;i<=n;i++)
	{
		l=0,r=0;
		for(int j=1;j<=n;j++)
			if(i!=j)
				l+=mn(a[j]),r+=mx(a[j]);
		printf("%s %.2lf %.2lf\n",s[i],max(mn(a[i]),10000-r)/100.0,min(mx(a[i]),10000-l)/100.0);
	}
	return 0;
}

F Paris by Night

平面上有N个不出现三点共线的点,找到一条过两点的直线使得两侧点数差最小

对每个点,将其它点按极坐标排序,扫描更新答案即可

–by hxm

#include<algorithm>
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<cstdio>
#include<vector>
#include<queue>
#include<cmath>
#include<map>
#include<set>
#define LL long long int
#define REP(i,n) for (int i = 1; i <= (n); i++)
#define Redge(u) for (int k = h[u],to; k; k = ed[k].nxt)
#define cls(s,v) memset(s,v,sizeof(s))
#define mp(a,b) make_pair<int,int>(a,b)
#define cp pair<int,int>
using namespace std;
const int maxn = 4005,maxm = 100005;
const LL INF = 100000000000000000ll;
inline int read(){
	int out = 0,flag = 1; char c = getchar();
	while (c < 48 || c > 57){if (c == '-') flag = 0; c = getchar();}
	while (c >= 48 && c <= 57){out = (out << 1) + (out << 3) + c - 48; c = getchar();}
	return flag ? out : -out;
}
int n,id[maxn],tag[maxn];
LL v[maxn],v1,v2;
double X[maxn],Y[maxn],nx,ny;
inline bool cmp(const int& a,const int& b){
	if (X[a] == nx && Y[a] == ny) return true;
	if (X[b] == nx && Y[b] == ny) return false;
	double c1,c2;
	if (X[a] == nx) c1 = Y[a] > ny ? 1 : -1;
	else if (X[a] < nx) c1 = 1.0 * (Y[a] - ny) / sqrt((nx - X[a]) * (nx - X[a]) + (Y[a] - ny) * (Y[a] - ny));
	else  c1 = 1.0 * (ny - Y[a]) / sqrt((nx - X[a]) * (nx - X[a]) + (Y[a] - ny) * (Y[a] - ny));
	if (X[b] == nx) c2 = Y[b] > ny ? 1 : -1;
	else if (X[b] < nx) c2 = 1.0 * (Y[b] - ny) / sqrt((nx - X[b]) * (nx - X[b]) + (Y[b] - ny) * (Y[b] - ny));
	else  c2 = 1.0 * (ny - Y[b]) / sqrt((nx - X[b]) * (nx - X[b]) + (Y[b] - ny) * (Y[b] - ny));
	return c1 > c2;
}
inline LL abs(const LL& a,const LL& b){
	return a > b ? a - b : b - a;
}
int main(){
	n = read();
	REP(i,n) X[i] = read(),Y[i] = read(),v[i] = read();
	int last; LL ans = INF;
	REP(i,n){
		nx = X[i]; ny = Y[i];
		REP(j,n) id[j] = j;
		sort(id + 1,id + 1 + n,cmp);
		v1 = 0; v2 = 0; last = 0;
		for (int j = 1; j <= n; j++){
			if (i == j) continue;
			if (X[j] < X[i]) v1 += v[j],tag[j] = true;
			else if (X[j] > X[i]) v2 += v[j],tag[j] = false;
			else last = j;
		}
		ans = min(ans,abs(v1 - v2));
		if (last){
			if (Y[last] > Y[i]) v2 += v[last],tag[last] = false;
			else v1 += v[last],tag[last] = true;
		}
		for (int j = 2; j <= n; j++){
			int u = id[j];
			if (X[u] == X[i]) continue;
			if (tag[u]) v1 -= v[u];
			else v2 -= v[u];
			ans = min(ans,abs(v1 - v2));
			if (tag[u]) v2 += v[u];
			else v1 += v[u];
			tag[u] ^= 1;
		}
	}
	cout << ans << endl;
	return 0;
}

G Strings

not finished yet

H Travel Guide

–by wxg 题意:给定一个图,求有多少点距离给点的三个点的距离\(d_1,d_2,d_3\) 不存在另外一个点三个距离均比这个点小。

裸的最短路加三位偏序

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<queue>
#define fi first 
#define se second
#define ll long long
using namespace std;
int read()
{
	int k=0,f=1;char c=getchar();
	for(;!isdigit(c);c=getchar()) if(c=='-') f=-1;
	for(;isdigit(c);c=getchar()) k=k*10+c-'0';return k*f;
}
const int N=500055,inf=0x3f3f3f3f;
typedef pair<int,int> P;
int n,m,tot,to[N<<1],nextt[N<<1],head[N],w[N<<1],dis[N][3],sum[10000555],mx;
struct node
{
	int x,y,z,cnt,ans;
}p[N];
bool cmp(node a,node b)
{
	if(a.x!=b.x) return a.x<b.x;
	if(a.y!=b.y) return a.y<b.y;
	return a.z<b.z;
} 
bool cp(node a,node b)
{
	if(a.y!=b.y) return a.y<b.y;
	return a.z<b.z;
}
void add(int x,int v) {for(;x<=mx;x+=x&-x) sum[x]+=v;}
int query(int x) {int s=0;for(;x;x-=x&-x) s+=sum[x];return s;}
void ad(int a,int b,int c)
{
	to[++tot]=b;
	nextt[tot]=head[a];
	w[tot]=c;
	head[a]=tot;
}
priority_queue<P,vector<P>,greater<P> > q;
void dij(int s)
{
	dis[s][s]=0;
	for(int i=0;i<n;i++)
		if(i!=s)
			dis[i][s]=inf;
	q.push(P(0,s));
	while(!q.empty())
	{
		P k=q.top();q.pop();
		int u=k.se;
		if(k.fi>dis[u][s]) continue;
		for(int i=head[u];i;i=nextt[i])
			if(dis[to[i]][s]>dis[u][s]+w[i])
				dis[to[i]][s]=dis[u][s]+w[i],q.push(P(dis[to[i]][s],to[i]));
	}
	return ;
}
void cdq(int l,int r)
{
	if(l==r) return;
	int mid=l+r>>1;
	cdq(l,mid);cdq(mid+1,r);
	sort(p+l,p+mid+1,cp);sort(p+mid+1,p+r+1,cp);
	int now=l;
	for(int i=mid+1;i<=r;i++)
	{
		while(p[i].y>=p[now].y&&now<=mid) add(p[now].z+1,p[now].cnt),now++;
		p[i].ans+=query(p[i].z+1);
	}
	
	for(int i=l;i<now;i++) add(p[i].z+1,-p[i].cnt);
}
int main()
{
	n=read();m=read();
	int a,b,c;
	for(int i=1;i<=m;i++)
	{
		a=read();b=read();c=read();
		ad(a,b,c);ad(b,a,c);
	}
	for(int i=0;i<3;i++)
		dij(i);
	for(int i=0;i<n;i++)	
		p[i].x=dis[i][0],p[i].y=dis[i][1],p[i].z=dis[i][2],p[i].cnt=1;
	int sm=0;
	sort(p,p+n,cmp);
	for(int i=1;i<n;i++)
		if(p[i].x==p[sm].x&&p[i].y==p[sm].y&&p[i].z==p[sm].z)
			p[sm].cnt++;
		else p[++sm]=p[i];
	for(int i=0;i<n;i++)
		mx=max(dis[i][2],mx);
	mx++;
	cdq(0,sm);
	int res=0;
	for(int i=0;i<=sm;i++)
		if(!p[i].ans) 
			res+=p[i].cnt;
	printf("%d\n",res);
	return 0;
}

I Mason’s Mark

找到矩阵上规定的构图ABC三个字母

细节多的大模拟,有了正确的思路但没有调出来。

具体来说,找到ABC三个字母的构图特征,从某个特征开始找,然后通过调查使其尺寸完全定义,再判断是否合法。

运用预处理的dp矩阵f[i][j]等表示(i,j)向指定方向延伸同颜色的最长距离以及最大矩形来加快对比。

#include<algorithm>
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<cstdio>
#include<vector>
#include<queue>
#include<cmath>
#include<map>
#include<set>
#define LL long long int
#define REP(i,n) for (int i = 1; i <= (n); i++)
#define Redge(u) for (int k = h[u],to; k; k = ed[k].nxt)
#define cls(s,v) memset(s,v,sizeof(s))
#define mp(a,b) make_pair<int,int>(a,b)
#define cp pair<int,int>
using namespace std;
const int maxn = 1005,maxm = 100005,INF = 0x3f3f3f3f;
inline int read(){
	int out = 0,flag = 1; char c = getchar();
	while (c < 48 || c > 57){if (c == '-') flag = 0; c = getchar();}
	while (c >= 48 && c <= 57){out = (out << 1) + (out << 3) + c - 48; c = getchar();}
	return flag ? out : -out;
}
int n,m,s[maxn][maxn],r[maxn][maxn],d[maxn][maxn],f[maxn][maxn];
int ans1,ans2,ans3;
void readin(){
	m = read(); n = read();
	char c = getchar();
	REP(i,n) REP(j,m){
		while (c != '.' && c != '#') c = getchar();
		s[i][j] = c == '.' ? 0 : 1;
		c = getchar();
	}
}
void pre_work(){
	for (int i = 1; i <= n; i++){
		r[i][m] = 1;
		for (int j = m - 1; j; j--){
			r[i][j] = s[i][j] == s[i][j + 1] ? r[i][j + 1] + 1 : 1;
		}
	}
	for (int j = 1; j <= m; j++){
		d[n][j] = 1;
		for (int i = n - 1; i; i--){
			d[i][j] = s[i][j] == s[i + 1][j] ? d[i + 1][j] + 1 : 1;
		}
	}
	for (int i = n; i; i--){
		for (int j = m; j; j--){
			if (i == n || j == m || s[i + 1][j + 1] != s[i][j]) f[i][j] = 1;
			else f[i][j] = min(f[i + 1][j + 1] + 1,min(d[i][j],r[i][j]));
		}
	}
	//REP(i,n){REP(j,m) printf("%d ",f[i][j]); puts("");}
}
void workab(){
	int x,y,flag,flag2;
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= m; j++){
			if (s[i][j]) continue;
			y = f[i][j];
			x = 0;
			while (i - x - 1 > 0 && s[i - x - 1][j]) x++;
			if (!x) continue;
			//if (i == 7 && j == 21) printf("[%d,%d]\n",x,y);
			flag = true;
			for (int k = 0; k < x; k++)
				if (i - x + k < 0 || j - x < 0 || !s[i - x + k][j - x] || r[i - x + k][j - x] != 2 * x + y){flag = false; break;}
			if (!flag) continue;
			for (int k = 0; k < x; k++)
				if (i - x < 0 || j - x + k < 0 || !s[i - x][j - x + k] || d[i - x][j - x + k] != 3 * x + 2 * y){flag = false; break;}
			if (!flag) continue;
			for (int k = 0; k < x; k++)
				if (i - x < 0 || j + y + x - 1 - k > m || !s[i - x][j + y + x - 1 - k] || d[i - x][j + y + x - 1 - k] != 3 * x + 2 * y){flag = false; break;}
			if (!flag) continue;
			for (int k = 0; k < x; k++)
				if (i + x + y - 1 - k > n || j - x < 0 || !s[i + x + y - 1 - k][j - x] || r[i + x + y - 1 - k][j - x] != 2 * x + y){flag = false; break;}
			if (!flag) continue;
			if (i - x - 1 < 0 || j - x - 1 < 0 || s[i - x - 1][j - x - 1] || r[i - x - 1][j - x - 1] < 2 * x + y + 2) flag = false;
			if (!flag) continue;
			if (i - x - 1 < 0 || j - x - 1 < 0 || s[i - x - 1][j - x - 1] || d[i - x - 1][j - x - 1] < 3 * x + 2 * y + 2) flag = false;
			if (!flag) continue;
			if (i - x - 1 < 0 || j + y + x > m || s[i - x - 1][j + y + x] || d[i - x - 1][j + y + x] < 3 * x + 2 * y + 2) flag = false;
			if (!flag) continue;//cout << i << ' ' << j << endl;
			if (i + 2 * y + 2 * x > n || j - x - 1 < 0 || s[i + 2 * y + 2 * x][j - x - 1] || r[i + 2 * y + 2 * x][j - x - 1] < 2 * x + y + 2) flag = false;
			if (!flag) continue;
			
			if (i + x + y > n || s[i + x + y][j] || f[i + x + y][j] != y) flag = false;
			if (!flag) continue;
			//cout << i << ' ' << j << endl;
			flag = true; flag2 = true;
			for (int k = 0; k < x; k++){
				if (i + 2 * y + x + k > n) {flag = flag2 = false; break;}
				if (s[i + 2 * y + x + k][j]) flag = false;
				else flag2 = false;
				if (r[i + 2 * y + x + k][j] < y) flag = flag2 = false;
			}
			if (flag) ans1++;
			if (flag2) {ans2++; /*printf("(%d,%d)",i,j);*/}
		}
}
void workc(){
	int x,y,flag;
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= m; j++){
			if (!s[i][j]) continue;
			x = f[i][j];
			y = r[i][j] - 2 * x;
			if (y <= 0) continue;
			flag = true;
			for (int k = 0; k < x; k++)
				if (i + k > n || !s[i + k][j] || r[i + k][j] != 2 * x + y){flag = false; break;}
			if (!flag) continue;//cout << i << ' ' << j << endl;
			for (int k = 0; k < x; k++)
				if (j + k > m || !s[i][j + k] || d[i][j + k] != 3 * x + 2 * y){flag = false; break;}
			if (!flag) continue;
			for (int k = 0; k < x; k++)
				if (i + 2 * x + 2 * y + k > n || !s[i + 2 * x + 2 * y + k][j] || r[i + 2 * x + 2 * y + k][j] != 2 * x + y){flag = false; break;}
			if (!flag) continue;
			for (int k = 0; k < y + x; k++)
				if (i + x > n || j + x + k > m || s[i + x][j + x + k] || d[i + x][j + x + k] != x + 2 * y){flag = false; break;}
			if (!flag) continue;
			if (i - 1 < 0 || j - 1 < 0 || s[i - 1][j - 1] || r[i - 1][j - 1] < 2 * x + y + 2) flag = false;
			if (!flag) continue;
			if (i - 1 < 0 || j - 1 < 0 || s[i - 1][j - 1] || d[i - 1][j - 1] < 3 * x + 2 * y + 2) flag = false;
			if (!flag) continue;
			if (i - 1 < 0 || j + 2 * x + y > m || s[i - 1][j + 2 * x + y] || d[i - 1][j + 2 * x + y] < 3 * x + 2 * y + 2) flag = false;
			if (!flag) continue;
			if (i + 2 * y + 3 * x > n || j - 1 < 0 || s[i + 2 * y + 3 * x][j - 1] || r[i + 2 * y + 3 * x][j - 1] < 2 * x + y + 2) flag = false;
			
			if (flag) {ans3++; /*printf("[%d,%d]\n",i,j);*/}
		}
}
int main(){
	readin();
	pre_work();
	workab();
	workc();
	//REP(i,n){REP(j,m) printf("%d ",f[i][j]); puts("");}
	//cout << r[13][18] << endl;
	printf("%d %d %d\n",ans1,ans2,ans3);
	return 0;
}

J Mona Lisa

not finished yet

K Dishonest Driver

区间dp,暴力找到最小表示长度

by fyh

#include<bits/stdc++.h>
using namespace std;
#define mem(a,b) memset(a,b,sizeof(a))
typedef long long LL;
typedef pair<int,int> PII;
#define X first
#define Y second
inline int read()
{
	int x=0,f=1;char c=getchar();
	while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
	while(isdigit(c)){x=x*10+c-'0';c=getchar();}
	return x*f;
}
const int maxn=710;
int n,dp[maxn][maxn];
char s[maxn];
int DP(int L,int R)
{
	if(dp[L][R]<n)return dp[L][R];
	int &res=dp[L][R];
	if(L>R)return res;
	if(L==R)return (res=1);
	int len=R-L+1;
	for(int i=L;i<R;i++)res=min(res,DP(L,i)+DP(i+1,R));
	for(int i=1;i<len;i++)
		if(len%i==0)
		{
			bool ok=0;
			for(int j=0;j<i;j++)
			{
				for(int k=1;k<len/i;k++)
					if(s[L+j]!=s[L+k*i+j]){
						ok=1;break;
					}
				if(ok==1)break;
			}
			if(!ok)res=min(res,DP(L,L+i-1));
		}
	return res;
}
int main()
{
	mem(dp,42);
	n=read();
	scanf("%s",s+1);
	DP(1,n);
	printf("%d\n",dp[1][n]);
	return 0;
}
<<<<<<< edited

训练总结

本次最大的遗憾是没有把I题调出来,之前的确是把细节想清楚了,但是hxm写的时候还是有地方手残打错了,fyh虽然在围观写代码也没有帮忙调出来,肉眼调题能力太菜。

B题耽误了一段时间,原因在于那个特殊性质在wxg转述的时候没有说清楚,以后应该确认题意了再说。

wxg在全场只有一个人A“C”题的情况下坚定自己能A掉,用了短短半小时写了一份很神奇的“暴力”,然后A掉了,着实nb!