@KirinBill
2017-12-25T14:27:13.000000Z
字数 4853
阅读 1261
题解
目录
题目大意:构造一个序列,使且有,求。。
#include <cstdio>
int main(){
unsigned long long x,y;
scanf("%llu%llu",&x,&y);
int ans=0;
while(x<=y) x<<=1,++ans;
printf("%d",ans);
return 0;
}
题目大意:给你一个01串,每次可以选一段长度不小于的区间对~取反。求使能够变为全0串的。。
#include <cstdio>
#include <cstring>
#include <algorithm>
using std::max;
using std::min;
const int MAXN=1e5+5;
char s[MAXN];
int main(){
scanf("%s",s);
int n=strlen(s),ans=n;
for(int i=1;i<n;++i){
if(s[i]!=s[i-1])
ans=min(ans,max(i,n-i));
}
printf("%d",ans);
return 0;
}
题目大意:给你一个字符串,每次可以交换相邻两个字符,求使变为回文串的最小交换次数(无解则输出)。。
#include <cstdio>
#include <cstring>
const int MAXN=2e5+5,INF=0x7f7f7f7f;
int n;
int a[MAXN];
char s[MAXN];
inline int chr_idx(char c){return c-'a';}
template<class T>
long long mge_sort(T a[],int l,int r){
static T tmp[MAXN];
if(l==r) return 0;
int mid=l+r>>1;
long long ret=mge_sort(a,l,mid)+mge_sort(a,mid+1,r);
int lp=l,rp=mid+1,cur=l-1;
while(lp<=mid && rp<=r){
if(a[lp]<=a[rp]) tmp[++cur]=a[lp++];
else{
ret+=mid-lp+1;
tmp[++cur]=a[rp++];
}
}
while(lp<=mid) tmp[++cur]=a[lp++];
while(rp<=r) tmp[++cur]=a[rp++];
memcpy(a+l,tmp+l,(r-l+1)*sizeof(T));
return ret;
}
inline void deal(){
static int fir_pos[26],last_pos[26],pre[MAXN],nex[MAXN];
static bool use[MAXN];
for(int i=n;i;--i){
nex[i]=fir_pos[chr_idx(s[i])];
fir_pos[chr_idx(s[i])]=i;
}
for(int i=1;i<=n;++i){
pre[i]=last_pos[chr_idx(s[i])];
last_pos[chr_idx(s[i])]=i;
}
for(int i=0;i<26;++i){
if(!fir_pos[i]) continue;
for(int l=fir_pos[i],r=last_pos[i];r;l=nex[l],r=pre[r])
a[n-l+1]=r;
}
}
inline bool spj(){
static int cnt[26];
for(int i=1;i<=n;++i)
++cnt[chr_idx(s[i])];
int tot=0;
for(int i=0;i<26;++i){
if(cnt[i]&1) ++tot;
}
return tot==(n&1);
}
int main(){
scanf("%s",s+1);
n=strlen(s+1);
if(!spj()){
printf("-1");
return 0;
}
deal();
printf("%lld",mge_sort(a,1,n)>>1);
return 0;
}
题目大意:你有个长度最多为的路径。每次可以选在不同连通块中的两个点,将它们合成一个点。最后要求合并成一个与所给的树同构的树。求的最小值及此时的最小值。
#include <cstdio>
#include <algorithm>
#include <vector>
using std::sort;
using std::vector;
const int MAXN=1e5+5;
int rt,n,A,B;
int he[MAXN],deg[MAXN];
int dp[MAXN];
struct line{int to,nex;}ed[MAXN<<1];
inline void addE(int u,int v){
static int cnt;
ed[++cnt]=(line){v,he[u]};
he[u]=cnt;
}
inline bool cmp_dp(int a,int b){return dp[a]<dp[b];}
inline bool check(vector<int> &vec,int son){
for(int l=0,r=vec.size()-1;l<r;++l,--r){
if(l==son) ++l;
if(r==son) --r;
if(dp[vec[l]]+dp[vec[r]]>B)
return false;
}
return true;
}
inline int bin_chop_son(vector<int> &vec){
int l=0,r=vec.size()-1,mid;
while(l<=r){
mid=l+r>>1;
if(check(vec,mid)) r=mid-1;
else l=mid+1;
}
return l;
}
bool treeDP(int u,int fa){
vector<int> vec;
for(int i=he[u],v;i;i=ed[i].nex){
v=ed[i].to;
if(v!=fa){
if(!treeDP(v,u)) return false;
vec.push_back(v);
}
}
if(vec.size()==0){
dp[u]=1;
return true;
}
//度数为奇数,则儿子为偶数个
if(deg[u]&1) vec.push_back(0);
sort(vec.begin(),vec.end(),cmp_dp);
int v=bin_chop_son(vec);
if(v==vec.size()) return false;
dp[u]=dp[vec[v]]+1;
return dp[u]<=B+1;
}
inline void bin_chop_B(){
int l=0,r=n;
while(l<=r){
B=l+r>>1;
if(treeDP(rt,0)) r=B-1;
else l=B+1;
}
B=l;
}
inline void cal_A(){
int cnt=0;
for(int i=1;i<=n;++i)
cnt+=deg[i]&1;
A=cnt>>1;
}
int main(){
scanf("%d",&n);
for(int i=1,u,v;i<n;++i){
scanf("%d%d",&u,&v);
++deg[u],++deg[v];
addE(u,v),addE(v,u);
}
cal_A();
for(int i=1;i<=n;++i){
if(deg[i]==1){
rt=i;
break;
}
}
bin_chop_B();
printf("%d %d",A,B);
return 0;
}