C
假设每种颜色的个数都相同,可以用轮换的方式,让答案达到最大n,当不同的时候,可以每次从每种颜色中取出相同个数的手套来操作;
一直迭代下去直到只剩下1种颜色;
再将这一种颜色与之前交换过的交换就行了,只要保证不会交换出同色手套即可.
bool cmp(node x,node y) {return x.t<y.t;}
void add2ans(int l,int r,int t)
{
// printf("add:l=%d r=%d t=%d\n",l,r,t);
rep(i,t) ans.push_back((node){l,r});
}
int modify(int c,int t,int& res)
{
vector<node>tmp;
tmp.clear();
// printf("c=%d t=%d\n",c,t);
rep(i,(int)ans.size()) if (ans[i].t!=c && ans[i].c!=c)
{
tmp.push_back((node){c,ans[i].t});
// printf("ans[%d].l=%d ans[%d].r=%d\n",i,ans[i].c,i,ans[i].t);
ans[i].t = c;
if ((int)tmp.size()==t) break;
}
rep(i,(int)tmp.size()) ans.push_back(tmp[i]);
// rep(i,(int)tmp.size()) printf("l=%d r=%d\n",tmp[i].c,tmp[i].t);
res = (int)ans.size();
return (int)tmp.size();
}
int main()
{
// freopen("test","r",stdin);
scanf("%d%d",&n,&m);
rep(i,n)
{
int t;
scanf("%d",&t);
cnt[t]++;
}
rep(i,m+) if(cnt[i]) rcd.push_back((node){i,cnt[i]});
sort(rcd.begin(),rcd.end(),cmp);
int res=-;
rep(i,(int)rcd.size()) if(rcd[i].t)
{
int use = rcd[i].t;
if (i==(int)rcd.size()-) use -= modify(rcd[i].c,rcd[i].t,res);
// printf("i=%d use=%d c=%d t=%d\n",i,use,rcd[i].c,rcd[i].t);
rcd[i].t -= use;
add2ans(rcd[i].c,rcd[rcd.size()-].c,use);
for (int j=i+ ; j<(int)rcd.size() ; j++ )
{
rcd[j].t -= use;
add2ans(rcd[j].c,rcd[j-].c,use);
}
}
if (res==-) res = (int)ans.size();
printf("%d\n",res);
rep(i,(int)ans.size()) printf("%d %d\n",ans[i].c,ans[i].t);
return ;
}
D
找到所有w的位置就可以确定正方形的变长,然后枚举左下角,用"部分和"的办法o(1)检查是否合法即可.
E
首先发现:如果"第a天是看i本书的第x天,第b天是看j本书的第y天"成立时,当且仅当(b-a)属于某个区间[l,r];
l,r可以O(1)计算,于是根据输入的n条信息,可以推出f[i][j]=true/false,它表示第i天,是看某本书的第j天.
其中f[1][1]=true,至于这是第几本书,可以根据输入计算出来,然后枚举最后一本书的编号即可.
#define maxn 200010
#define INF 100000
struct node
{
int day,id;
};vector<node>p;
int n,arr[maxn];
bool f[maxn][];
bool check(node a,int x,node b,int y)
{
if (a.id==b.id) return b.day-a.day==y-x;
else
{
int k = b.id-a.id,dif=b.day-a.day;
int l,r;
if (x==) l=+(k-)*+y,r=+(k-)*+y;
else l=(k-)*+y,r=(-x)+(k-)*+y;
return (l<=dif && dif<=r);
}
}
void printans()
{
for (int i= ; i<=n ; i++ ) printf("%d%c",arr[i],i==n?'\n':' ');
}
void getans(int book,int day,int read,int i)
{
int t;
for ( t= ; t<read ; t++ ) arr[day-t]=book;
while(i>=&&p[i].day>=day-t+)i--;
if (i<) return;
t = day-read;
node a = (node){t,book-};
for (int x= ; x<= ; x++ )
for (int y= ; y<= ; y++ ) if (f[p[i].day][x] && check(p[i],x,a,y))
{
getans(a.id,a.day,y,i);
return;
}
}
void solv()
{
if (arr[]>) {printf("-1\n"); return;}
arr[]=;
for (int i= ; i<=n ; i++ ) if(arr[i]) p.push_back((node){i,arr[i]});
f[][]=true;
rep(i,(int)p.size()-)
{
node a=p[i],b=p[i+];
for (int j= ; j<= ; j++ ) if(f[a.day][j])
for (int k= ; k<= ; k++ )
if (check(a,j,b,k)) f[b.day][k]=true;
}
for (int ans=INF ; ans>= ; ans-- )
{
node x = p[p.size()-];
for (int i= ; i<= ; i++ )
{
for (int j= ; j<= ; j++ )
if(f[x.day][j] && check(x,j,(node){n,ans},i))
{
getans(ans,n,i,p.size()-);
printf("%d\n",ans);
printans();
return;
}
}
}
printf("-1\n");
}