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！
