CodeForces 1267

题目:B–Balls of Buma

题意

给你一个字符串（代表不同颜色），让你插入一个字符（一种颜色）后，可以消掉整个字符串。（相同颜色、长度变长、长度>=3才会抵消）

思路

将原串变成“种类串”（例如：AABBAA—> ABA）后，“种类串”应当是回文串，且长度应该是奇数。
同时,一个可以被消去的串，根据中心对称的同类部分的长度和，应当>=3。中心部分长度应当>=2.满足以上条件，答案为中心部分答案+1；

代码

#include
#include
#include
//#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#define X first
#define Y second
#define best 131 
#define INF 0x3f3f3f3f
#define P pair
#define ls p<<1
#define rs p<<1|1
//#define int long long
//#define int long long
//const ll lnf=0x3f3f3f3f3f3f3f3f;
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;
//const int d[4][2]={0,1,1,0,-1,0,0,-1};
//int day[2][13]={{0,31,28,31,30,31,30,31,31,30,31,30,31},{0,31,29,31,30,31,30,31,31,30,31,30,31}};
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
#include
#include
//#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#define X first
#define Y second
#define best 131 
#define INF 0x3f3f3f3f
#define P pair
#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
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#define X first
#define Y second
#define best 131 
#define INF 0x3f3f3f3f
#define P pair
#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
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#define X first
#define Y second
#define best 131 
#define INF 0x3f3f3f3f
#define P pair
#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;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！