题意
有n块饼，可以通过一次操作将x大小的饼分成y、z两份。
问最少操作数，使得任意两块饼的大小严格小于两倍
思路
假设n块饼中最小的为a[0]，最终最小的饼大小为min
那么为了达到最优解，不能分割a[0]，不然所有的饼都要分割
于是
m
i
n
≤
a
[
0
]
并且
2
?
m
i
n
?
1
≤
a
[
0
]
min\leq a[0]并且2*min-1\leq a[0]
min≤a[0]并且2?min?1≤a[0]，为了让操作数尽可能小，选取min尽可能大，于是min=a[0]，每次重其他饼中拆最多2*a[0]-1的饼
注意：
- 当
其他饼%(2*a[0]-1)==0时，那么操作数为其他饼/(2*a[0]-1)-1 - 当
其他饼%(2*a[0]-1)!=0时，那么操作数为其他饼/(2*a[0]-1)，并且不用担心余数会小于min，因为拆出的饼大小为2*a[0]-1，那么a[0]-1+余数会大于等于min的
代码
#include<bits/stdc++.h>
#define ll long long
using namespace std;
int n;
ll a[1000];
int main(){
int t;
cin>>t;
while(t--){
cin>>n;
for(int i=0;i<n;i++)cin>>a[i];
sort(a,a+n);
ll ans=0;
// ll ans=0;
// if(a[0]==1){
// for(int i=0;i<n;i++)ans+=a[i]-1;
// cout<<ans<<endl;
// continue;
// }
for(int i=1;i<n;i++){
ans+=a[i]/(2*a[0]-1);
if(a[i]%(2*a[0]-1)==0)ans--;
}
cout<<ans<<endl;
}
}
题意
我们可以把每个字符进行一个映射，但是要求这个映射关系是可以组成一个26个字母成环，给你一个字符串f，问最后能得到的映射的最小字典序的字符串s，其中s[i]->f[i]
思路
为了得到最小字典序，优先选择为出现的小字符进行映射。
但是注意防止提前出现成环现象，因为这样就不能形成一个26个字母环。
可以通过遍历一遍已形成的映射关系判断是否成环，但是还得注意最终26个字母可以可以成环，要进行特判
代码
#include<bits/stdc++.h>
using namespace std;
map<char,char>m;
bool check(char j,char k){
int num=0;
while(m[j]){
if(m[j]==k)return true;
j=m[j];
num++;
if(num==24)return false;
}
return false;
}
int main(){
int t;
cin>>t;
while(t--){
int n;
string s,out="";
cin>>n>>s;
m.clear();
map<char,int>vis;
for(char i='a';i<='z';i++)vis[i]=0;
for(int i=0;i<s.length();i++){
if(m[s[i]]){
out+=m[s[i]];
continue;
}
for(char j='a';j<='z';j++){
if(vis[j]||s[i]==j)continue;
if(check(j,s[i]))continue;
vis[j]=1;
m[s[i]]=j;
out+=j;
break;
}
}
cout<<out<<endl;
}
}
题意
张卡片都有k个元素，每个元素的赋值只可能是0,1，2，三张卡如果每个元素要么相同要么都不同的时候，我们就说这三张卡是一组good，我们说五张卡中如果能选出至少两组good，那么这五张卡被称为一队，问有几队。
思路
-
先考虑组：
- 若三张卡属于一组，那么他们每个元素要么全相同、要么全相异。而元素可取的值只有3种，那么可以得出任意两张卡可以唯一确定第三张卡，使三张卡属于一组
- 由于元素可以取值为0、1、2，而且元素最多为20个。可以利用3进制状态压缩，将每一张卡压缩为一个数，那么这个数就与这张卡一一对应形成映射，这样就方便判断某张卡是否在集合中
- 暴力枚举两张卡，确定第三张卡是否在集合中，如果在那么它们可以组成一组。记录下可以组成的组数。
-
再考虑队：
代码
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=1e3+5,K=30;
int a[N][K];
int n,k;
ll three[K];
map<ll,int>ma;
map<int,int >se;
set<vector<int> >sett;
void solve(){
three[0]=1;
for(int i=1;i<=k;i++)three[i]=three[i-1]*3;
for(int i=0;i<n;i++){
ll ans=0;
for(int j=0;j<k;j++){
cin>>a[i][j];
ans+=a[i][j]*three[j];
}
ma[ans]=i;
}
for(int i=0;i<n;i++){
for(int j=i+1;j<n;j++){
ll ans=0;
for(int w=0;w<k;w++){
if(a[i][w]==a[j][w])ans+=a[i][w]*three[w];
else{
map<int,int>m;
m[a[i][w]]=1;
m[a[j][w]]=1;
if(!m[0])ans+=0;
else if(!m[1])ans+=1*three[w];
else if(!m[2])ans+=2*three[w];
}
}
if(ma.find(ans)!=ma.end()){
vector<int>v;
v.push_back(i);
v.push_back(j);
v.push_back(ma[ans]);
sort(v.begin(),v.end());
sett.insert(v);
}
}
}
for(set<vector<int> >::iterator it=sett.begin();it!=sett.end();it++){
se[(*it)[0]]++;
se[(*it)[1]]++;
se[(*it)[2]]++;
}
ll ans=0;
for(map<int,int >::iterator it=se.begin();it!=se.end();it++){
ll y=it->second;
ans+=(y*(y-1))/2;
}
cout<<ans<<endl;
}
int main(){
cin>>n>>k;
solve();
}
|