题目:B–Balls of Buma
题意
给你一个字符串（代表不同颜色），让你插入一个字符（一种颜色）后，可以消掉整个字符串。（相同颜色、长度变长、长度>=3才会抵消）
思路
将原串变成“种类串”（例如：AABBAA—> ABA）后，“种类串”应当是回文串，且长度应该是奇数。 同时,一个可以被消去的串，根据中心对称的同类部分的长度和，应当>=3。中心部分长度应当>=2.满足以上条件，答案为中心部分答案+1；
代码
#include<iostream>
#include<string>
#include<map>
#include<queue>
#include<cstdio>
#include<vector>
#include<cstring>
#include<algorithm>
#include<iomanip>
#include<stack>
#include<cmath>
#include<fstream>
#define X first
#define Y second
#define best 131
#define INF 0x3f3f3f3f
#define P pair<int,int>
#define ls p<<1
#define rs p<<1|1
using namespace std
;
typedef long long ll
;
typedef unsigned long long ull
;
const double eps
=1e-5;
const double pai
=acos(-1.0);
const int N
=3e5+10;
const int maxn
=110;
const int mod
=1000000007;
char s
[N
],p
[N
];
int t
[N
];
bool check(int x
)
{
int l
=0,r
=x
-1;
while(l
<r
)
{
if(p
[l
]==p
[r
]&&t
[l
]+t
[r
]>=3) l
++,r
--;
else return 0;
}
return 1;
}
int main()
{
scanf("%s",s
);
int len
=strlen(s
),cnt
=0,ans
=0;
p
[cnt
++]=s
[0];
t
[cnt
-1]++;
for(int i
=1;i
<len
;i
++)
{
if(s
[i
]!=s
[i
-1]) p
[cnt
++]=s
[i
],t
[cnt
-1]++;
else t
[cnt
-1]++;
}
if(cnt
==1)
{
if(len
>=2) printf("%d\n",len
+1);
else printf("0\n");
return 0;
}
if(cnt
%2==0||!check(cnt
))
{
printf("0\n");
return 0;
}
int tot
=1;
for(int i
=1;i
<len
;i
++)
{
if(s
[i
]!=s
[i
-1]) tot
++;
if(tot
==(cnt
/2+1)) ans
++;
if(tot
>(cnt
/2+1)) break;
}
if(ans
>=2) printf("%d\n",ans
+1);
else printf("0\n");
return 0;
}
题目：E–Elections
题意
n个候选人，m个投票站，每个人在每个投票站都有自己的得票，n号候选人是坏的，你的目的是阻止坏人胜出（即不让他的总得票数比其他所有人都要高），你可以取消一些投票站的结果（就是让所有人在这个投票站都不得票），求最少取消的投票站数目及其编号。
思路
枚举每个人，求每个人每个投票站和n号坏人得票的差值，对差值排序，从大到小累加，>=0的站台留着，<0的消去，最后得到这个人的最少取消的站台数，最后从每个人的最少取消的站台数中去最小值即为答案。（还是看代码吧/(ㄒoㄒ)/~~）
代码
#include<iostream>
#include<string>
#include<map>
#include<queue>
#include<cstdio>
#include<vector>
#include<cstring>
#include<algorithm>
#include<iomanip>
#include<stack>
#include<cmath>
#include<fstream>
#define X first
#define Y second
#define best 131
#define INF 0x3f3f3f3f
#define P pair<int,int>
#define ls p<<1
#define rs p<<1|1
using namespace std
;
typedef long long ll
;
typedef unsigned long long ull
;
const double eps
=1e-5;
const double pai
=acos(-1.0);
const int N
=1e6+10;
const int maxn
=110;
const int mod
=1000000007;
vector
<int>ans
;
vector
<int>tep
;
int a
[110][110];
struct node
{
int v
;
int p
;
}st
[110];
bool cmp(node x
,node y
)
{
return x
.v
>y
.v
;
}
int main()
{
int n
,m
,minn
=INF
;
scanf("%d%d",&n
,&m
);
for(int i
=1;i
<=m
;i
++)
{
for(int j
=1;j
<=n
;j
++)
{
scanf("%d",&a
[i
][j
]);
}
}
for(int i
=1;i
<n
;i
++)
{
tep
.clear();
for(int j
=1;j
<=m
;j
++)
{
st
[j
].v
=a
[j
][i
]-a
[j
][n
];
st
[j
].p
=j
;
}
sort(st
+1,st
+m
+1,cmp
);
int sum
=0;
for(int j
=1;j
<=m
;j
++)
{
if(sum
+st
[j
].v
>=0) sum
+=st
[j
].v
;
else tep
.push_back(st
[j
].p
);
}
if(tep
.size()<minn
)
{
ans
=tep
;
minn
=tep
.size();
}
}
printf("%d\n",minn
);
for(int i
=0;i
<minn
;i
++)
printf("%d ",ans
[i
]);
return 0;
}
题目:J–Just Arrange the Icons
题意
n个软件，每个软件都有种类，相同的可以放在一个屏幕上，而屏幕有容量 s (自己决定)，你要么在这个屏幕放 s-1 个 ，要么放 s 个，让你求最小的屏幕数。
思路
枚举 s ,确定最少屏幕数。 一种软件需要的屏幕数 =（这种软件的总数 - 1）/ s +1;同时还要满足( 需要的屏幕数 * (s−1) <=这种软件的数目 <=需要的屏幕数 * s） 。
代码
#include<iostream>
#include<string>
#include<map>
#include<queue>
#include<cstdio>
#include<vector>
#include<cstring>
#include<algorithm>
#include<iomanip>
#include<stack>
#include<cmath>
#include<fstream>
#define X first
#define Y second
#define best 131
#define INF 0x3f3f3f3f
#define P pair<int,int>
#define ls p<<1
#define rs p<<1|1
using namespace std
;
typedef long long ll
;
typedef unsigned long long ull
;
const double eps
=1e-5;
const double pai
=acos(-1.0);
const int N
=2e6+10;
const int maxn
=110;
const int mod
=1000000007;
int a
[N
];
int main()
{
int t
;
scanf("%d",&t
);
while(t
--)
{
memset(a
,0,sizeof(a
));
vector
<int>v
;
int n
;
scanf("%d",&n
);
for(int i
=1;i
<=n
;i
++)
{
int x
;
scanf("%d",&x
);
if(!a
[x
]) v
.push_back(x
);
a
[x
]++;
}
int cnt
=n
/v
.size()+1;
int ans
=INF
;
for(int i
=2;i
<=cnt
;i
++)
{
bool flag
=0;
int sum
=0;
for(int j
=0;j
<v
.size();j
++)
{
int tot
=(a
[v
[j
]]-1)/i
+1;
if(a
[v
[j
]]<tot
*(i
-1)||a
[v
[j
]]>tot
*i
)
{
flag
=1;
break;
}
sum
+=tot
;
}
if(flag
==1) continue;
else ans
=min(ans
,sum
);
}
printf("%d\n",ans
);
}
return 0;
}
题目：L–Lexicography
题意
给你给一个 n * l 的串，让你构造 n 个长 l 的单词，单词按字典序排序，要求第 k 个单词的字典序尽可能的小。
思路
对串按字典序排序，先构造前 1-k 个单词，先按序赋予 k 个单词首字母，看有没有和 k 相同首字母的单词，如果有，从最前面的相同首字母的单词开始赋予第二个字母，一直重复到没有跟 k 相同的单词或 k 长度达到 l ；如果没有，直接将 k 赋到长度 l ，剩下的单词按剩下的串赋值。（语文不大好，还是看代码吧/(ㄒoㄒ)/~~）
代码
#include<iostream>
#include<string>
#include<map>
#include<queue>
#include<cstdio>
#include<vector>
#include<cstring>
#include<algorithm>
#include<iomanip>
#include<stack>
#include<cmath>
#include<fstream>
#define X first
#define Y second
#define best 131
#define INF 0x3f3f3f3f
#define P pair<int,int>
#define ls p<<1
#define rs p<<1|1
using namespace std
;
typedef long long ll
;
typedef unsigned long long ull
;
const double eps
=1e-5;
const double pai
=acos(-1.0);
const int N
=1e6+10;
const int maxn
=110;
const int mod
=1000000007;
string ans
[1010],s
;
int n
,l
,k
,len
,pre
;
int main()
{
scanf("%d%d%d",&n
,&l
,&k
);
cin
>>s
;
sort(s
.begin(),s
.end());
if(k
==1)
{
for(int i
=1;i
<=l
;i
++) ans
[k
]+=s
[len
++];
}
else
{
for(int i
=1;i
<=k
;i
++) ans
[i
]+=s
[len
++];
for(int i
=1;i
<=k
;i
++)
{
if(ans
[i
][0]==ans
[k
][0])
{
pre
=i
;
break;
}
}
}
while(ans
[k
].size()<l
)
{
if(pre
==k
)
{
for(int i
=ans
[k
].size();i
<l
;i
++) ans
[k
]+=s
[len
++];
}
else
{
for(int i
=pre
;i
<=k
;i
++) ans
[i
]+=s
[len
++];
int ll
=ans
[k
].size();
for(int i
=pre
;i
<=k
;i
++)
{
if(ans
[i
][ll
-1]==ans
[k
][ll
-1])
{
pre
=i
;
break;
}
}
}
}
for(int i
=1;i
<=n
;i
++)
{
if(ans
[i
].size()<l
)
{
while(ans
[i
].size()<l
) for(int j
=ans
[i
].size();j
<l
;j
++) ans
[i
]+=s
[len
++];
}
}
for(int i
=1;i
<=n
;i
++)
{
cout
<<ans
[i
]<<endl
;
}
return 0;
}
