首页 > 代码库 > Codeforces Round #384 Div.2
Codeforces Round #384 Div.2
A：Vladik and flights
题目大意：给定一个长度为n的01串和a,b两个位置，如果一个位置和另一个位置上的数相同，那么这两个位置之间相互到达的代价是0，否则代价是这两个位置的距离，问从a到b最少需要多少代价。
思路：答案非0即1,0的情况就是这两个位置上的数相同，1就代表一定同时存在0和1，那么就把这两个点分别移到0，1交界的位置，那么答案就是1。
#include<cmath>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
#define maxn 100005
const int inf=1e9;
int n,st,ed,ans;
char s[maxn];
inline int read(){
int x=0,f=1;char ch=getchar();
for (;ch<‘0‘||ch>‘9‘;ch=getchar()) if (ch==‘-‘) f=-1;
for (;ch>=‘0‘&&ch<=‘9‘;ch=getchar()) x=x*10+ch-‘0‘;
return x*f;
}
inline void print(int x){
if (x>=10) print(x/10);putchar(x%10+‘0‘);
}
int main(){
n=read(),st=read(),ed=read();
scanf("%s",s+1);
puts(s[st]==s[ed]?"0":"1");
return 0;
}
B：Chloe and the sequence
题目大意：给定一个序列的构造方式，第一个序列是[1]，第二个序列是[1,2,1]，第三个序列是[1,2,1,3,1,2,1]，然后第n个序列就是把第n-1个序列翻折后再在最中间加一个数n，然后问第n个序列中第k个数是多少。
思路：设len为第n个序列的长度（显然len=(1<<n)-1），mid为最中间数的位置，然后如果k>mid，显然有a[k]=a[len-k+1]（满足对称性），然后如果k<mid，那么就可以把序列折半看成是一个子问题，k==mid就输出这是第几个序列就好了。
#include<cmath>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
int n;
long long len,k;
inline long long read(){
long long x=0,f=1;char ch=getchar();
for (;ch<‘0‘||ch>‘9‘;ch=getchar()) if (ch==‘-‘) f=-1;
for (;ch>=‘0‘&&ch<=‘9‘;ch=getchar()) x=x*10+ch-‘0‘;
return x*f;
}
inline void print(int x){
if (x>=10) print(x/10);putchar(x%10+‘0‘);
}
int main(){
n=read(),k=read();
len=(1ll<<n)-1;
for (int i=n;i;i--){
if (k==len/2+1){printf("%d\n",i);return 0;}
if (k>len/2+1) k=len-k+1;
len>>=1;
}
return 0;
}
C：Vladik and fractions
题目大意：给定n，找到三个互不相同的整数使得2/n=1/a+1/b+1/c。
思路：2/n=1/n+1/(n+1)+1/(n*(n+1))，注意互不相同要特判n=1的情况。
#include<cmath>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
int n,m;
inline int read(){
int x=0,f=1;char ch=getchar();
for (;ch<‘0‘||ch>‘9‘;ch=getchar()) if (ch==‘-‘) f=-1;
for (;ch>=‘0‘&&ch<=‘9‘;ch=getchar()) x=x*10+ch-‘0‘;
return x*f;
}
inline void print(int x){
if (x>=10) print(x/10);putchar(x%10+‘0‘);
}
int main(){
n=read();
if (n==1){puts("-1");return 0;}
else{printf("%d %d %d\n",n,n+1,n*(n+1));}
return 0;
}
D：Chloe and pleasant prizes
题目大意：一颗以1为根的树，给定每个点的点权，找到两颗没有交集的子树并使它们的权值和尽量大，如果找不到输出-1。
思路：首先找不到的情况就是一条链的情况（当然1必须是该链的一个端点），然后答案直接就tree dp就好了，和tree dp求树最长链基本一毛一样。
#include<cmath>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
#define maxn 200005
const long long inf=1e18;
int n,m,maxdeg,tot;
long long ans;
int now[maxn],pre[maxn*2],son[maxn*2],deg[maxn];
long long sum[maxn];
bool vis[maxn];
inline int read(){
int x=0,f=1;char ch=getchar();
for (;ch<‘0‘||ch>‘9‘;ch=getchar()) if (ch==‘-‘) f=-1;
for (;ch>=‘0‘&&ch<=‘9‘;ch=getchar()) x=x*10+ch-‘0‘;
return x*f;
}
inline void print(int x){
if (x>=10) print(x/10);putchar(x%10+‘0‘);
}
void add(int a,int b){
son[++tot]=b;
pre[tot]=now[a];
now[a]=tot;
}
void link(int a,int b){
add(a,b),add(b,a);
}
long long tree_dp(int x,int fa){
long long mx=-inf,tx=-inf;
for (int p=now[x];p;p=pre[p])
if (son[p]!=fa){
long long tmp=tree_dp(son[p],x);
if (tmp>mx) tx=mx,mx=tmp;
else tx=max(tx,tmp);
ans=max(ans,tx+mx);
sum[x]+=sum[son[p]];
}
return max(mx,sum[x]);
}
void dfs(int x,int fa){
vis[x]=1;
for (int p=now[x];p;p=pre[p]) if (son[p]!=fa){dfs(son[p],x);break;}
}
bool check(){
dfs(1,0);
for (int i=1;i<=n;i++) if (!vis[i]) return 1;
return 0;
}
int main(){
n=read(); ans=-inf;
for (int i=1;i<=n;i++) sum[i]=read();
for (int i=1,a,b;i<n;i++) a=read(),b=read(),link(a,b);
if (!check()){puts("Impossible"); return 0;}
tree_dp(1,0);
printf("%lld\n",ans);
return 0;
}
E：Vladik and cards
题目大意：在给定的只由1到8组成的序列中，找到一个子序列，使得其满足以下条件：1.任意一个数字出现的次数之间不能相差超过1，也就是说每个数字要么出现x次，要么出现x+1次。2.如果子序列中第一次出现某个数字，就必须全部出现完，也就是说相同的数字在子序列中一定是一条线段而不能断开。在以上基础上要求子序列长度最长。
思路：状压dp很显然，关键是二分比较难想，因为一个数字要么出现x次，要么出现x+1次，那么我们就二分这个x（显然具有单调性），然后考虑如何去check就好了。
因为答案肯定是形如x*y+(8-y)*(x+1)，这个y就是有多少个数字出现x次，然后就可以令状态f[i][S]表示当前状态为S，当前位于第i个时的y的值，然后枚举当前选哪个数字转移即可。
#include<cmath>
#include<cstdio>
#include<vector>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
#define maxn 1005
#define maxs (1<<8)
const int inf=1e9;
int n,ans=-inf;
int a[maxn],cnt[9];
int f[maxn][maxs];
inline int read(){
int x=0,f=1;char ch=getchar();
for (;ch<‘0‘||ch>‘9‘;ch=getchar()) if (ch==‘-‘) f=-1;
for (;ch>=‘0‘&&ch<=‘9‘;ch=getchar()) x=x*10+ch-‘0‘;
return x*f;
}
vector<int> v[9];
void clear(){memset(cnt,0,sizeof(cnt)),memset(f,-1,sizeof(f));}
bool check(int mid){
clear();f[1][0]=0;
for (int i=1;i<=n;i++){
for (int S=0;S<maxs;S++){
if (f[i][S]==-1) continue;
for (int j=1;j<=8;j++)
if (!(S&(1<<(j-1)))){
int x=cnt[j]+mid;
if (x>v[j].size()) continue;
f[v[j][x-1]+1][S|(1<<(j-1))]=max(f[v[j][x-1]+1][S|(1<<(j-1))],f[i][S]);
if (++x>v[j].size()) continue;
f[v[j][x-1]+1][S|(1<<(j-1))]=max(f[v[j][x-1]+1][S|(1<<(j-1))],f[i][S]+1);
}
}
cnt[a[i]]++;
}
int tt=-1;
for (int i=1;i<=n+1;i++) tt=max(tt,f[i][maxs-1]);
return tt==-1?0:(ans=max(ans,tt*(mid+1)+(8-tt)*mid),1);
}
int main(){
n=read();
for (int i=1;i<=n;i++) a[i]=read(),v[a[i]].push_back(i);
int l=1,r=n;
while (l<=r){
int mid=(l+r)>>1;
if (check(mid)) l=mid+1;
else r=mid-1;
}
if (ans==-inf){
ans=0;
for (int i=1;i<=8;i++) if (v[i].size()) ans++;
}
printf("%d\n",ans);
return 0;
}
Codeforces Round #384 Div.2