不想欠题了..... 多打打CF才知道自己智商不足啊...
A. Vladik and flights
给你一个01串 相同之间随便飞 没有费用 不同的飞需要费用为 abs i-j
真是题意杀啊，，，实际上我们只考虑01转换的代价一定为1如果目的地和起点相同 费用为0
不相同 肯定为1 因为0旁边必然有1
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <vector>
#include <set>
#include <string.h>
#include <cctype>
#include <climits>
using namespace std;
typedef long long ll;
template <class T>
inline bool r(T &ret)
{
char c;
int sgn;
if (c = getchar(), c == EOF)
{
return ; //EOF
}
while (c != '-' && (c < '' || c > ''))
{
c = getchar();
}
sgn = (c == '-') ? - : ;
ret = (c == '-') ? : (c - '');
while (c = getchar(), c >= '' && c <= '')
{
ret = ret * + (c - '');
}
ret *= sgn;
return ;
}
const int N = 1e5+;
char ch[N];
int main()
{
int n;
r(n);
int x,y;
r(x),r(y);
scanf("%s",ch+);
if(ch[x]==ch[y])
{
printf("0\n");
}
else{
printf("1\n");
}
return ;
}
zz
B. Chloe and the sequence
给一个n，然后按照 1 121 1213121 的第n个串
那么肯定是二分n次必得.... 赛场拿python写的 （L+R）没加括号T1
n,k = map(int, input().split())
def calc(k):
L =
R = **n
M = L+R//
ans =
while(k!=M):
if(k>M):
L = M
else:
R = M
M = (L+R)//
ans+=
print(n-ans)
calc(k)
Py
C. Vladik and fractions
问2/n能不能由1/a+1/b+1/c（a,b,c互不相同） 太粗心，没看到互不相同 wa1 没特判1 被hack 1
手推 a = n b = n+1 c = n*(n+1)
n=1分不出的
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <vector>
#include <set>
#include <string.h>
#include <cctype>
#include <climits>
using namespace std;
typedef long long ll;
template <class T>
inline bool r(T &ret)
{
char c;
int sgn;
if (c = getchar(), c == EOF)
{
return ; //EOF
}
while (c != '-' && (c < '' || c > ''))
{
c = getchar();
}
sgn = (c == '-') ? - : ;
ret = (c == '-') ? : (c - '');
while (c = getchar(), c >= '' && c <= '')
{
ret = ret * + (c - '');
}
ret *= sgn;
return ;
} int main()
{
int n;
r(n);
if(n==) printf("-1");
else printf("%d %d %d\n",n,n+,n*(n+));
return ;
}
AC
D.Chloe and pleasant prizes
带权有根树 选两个不相交子树的之和最大，裸DFS。
吐槽一下自己奇差无比的代码。。。两个dfs才完成任务...
还因为各种写搓 wa了3次
#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <limits.h>
#include <vector>
using namespace std;
typedef long long ll;
const int N = 2e5+;
vector<int>g[N];
ll sum[N];
ll son[N];
int a[N];
void push(int x,int y){g[x].push_back(y);g[y].push_back(x);}
bool flag = true;
void UMAX(ll& a,ll& b,ll c){
if(c>a)
{
b = a;
a = c;
}
else{
if(c>=b)
{
b = c;
}
}
}
ll dfs(int now,int pre)
{
sum[now] += a[now]; bool mk = true;
for(int i=;i<g[now].size();i++)
{
if(g[now][i]==pre) continue;
ll val = dfs(g[now][i],now);
sum[now] += val;
if(!mk)son[now] = max(son[now],son[g[now][i]]);
else{
mk = false;
son[now] = son[g[now][i]];
}
}
if(mk)son[now] = a[now];
son[now] = max(son[now],sum[now]);
return sum[now];
}
ll ans = LONG_LONG_MIN;
void F(int now,int pre)
{
//cout<<now<<endl;
ll a = LONG_LONG_MIN;
ll b = LONG_LONG_MIN;
for(int i=;i<g[now].size();i++)
{
if(pre==g[now][i]) continue;
UMAX(a,b,son[g[now][i]]);
F(g[now][i],now);
}
//if(now==4) cout<<a<<" "<<b<<endl;
if(b!=LONG_LONG_MIN)ans = max(ans,a+b);
}
int main()
{
int n;
scanf("%d",&n);
for(int i=;i<=n;i++)
{
scanf("%d",&a[i]);
}
int x,y;
for(int i=;i<n;i++)
{
scanf("%d%d",&x,&y);
push(x,y);
}
dfs(,-);
/*
for(int i=1;i<=n;i++)
printf("%d\t",i);
printf("\n");
for(int i=1;i<=n;i++)
printf("%I64d\t",sum[i]);
printf("\n");
for(int i=1;i<=n;i++)
printf("%I64d\t",son[i]);
printf("\n");
//*/
F(,-);
if(ans==LONG_LONG_MIN)
printf("Impossible\n");
else{
printf("%I64d\n",ans);
}
return ;
}
AC代码
贴一下陈老师的代码....
#include<cstdio>
#include<algorithm>
typedef long long ll;
const int N=;
const ll inf=1LL<<;
int n,i,x,y,a[N],g[N],v[N<<],nxt[N<<],ed;ll f[N],dp[N],ans=-inf;
inline void add(int x,int y){v[++ed]=y;nxt[ed]=g[x];g[x]=ed;}
void dfs(int x,int y){
f[x]=a[x];
dp[x]=-inf;
for(int i=g[x];i;i=nxt[i]){
int u=v[i];
if(u==y)continue;
dfs(u,x);
f[x]+=f[u];
if(dp[x]>-inf)ans=std::max(ans,dp[x]+dp[u]);
dp[x]=std::max(dp[x],dp[u]);
}
dp[x]=std::max(dp[x],f[x]);
}
int main(){
scanf("%d",&n);
for(i=;i<=n;i++)scanf("%d",&a[i]);
for(i=;i<n;i++)scanf("%d%d",&x,&y),add(x,y),add(y,x);
dfs(,);
if(ans>-inf)printf("%I64d",ans);else puts("Impossible");
}
claris
E. Vladik and cards
题意给以一个1-8组成的串 选出一个子串（在原串中可以不连续） 选出来的串 每个数相同的一定相邻 而且 每种数的个数相差不超过1
比赛时只想到DFS的解，后来证实是错的
后来看别人的代码一脸蒙=。=... 后来一神说了两个数组的作用才明白...就这样 参考claris的写法
而且....
这样也写了好久 而且还少更新状态 长度可以为0......
#include<cstdio>
#include<cstring>
void Min(int &a,int b) {if(a>b) a=b;}
void Max(int &a,int b) {if(a<b) a=b;}
const int maxn = ;
int cnt[];
int g[maxn][maxn][];//i j k
int dp[][];//i 选择方案 j 代表 长度的集合个数 长度最多n/8+1
int val[maxn];
int n;
int main()
{
scanf("%d",&n);
for(int i=;i<=n;i++) scanf("%d",&val[i]),val[i]--;
for(int i=;i<=n;i++)
{
for(int j=;j<=n+;j++)
for(int k=;k<=;k++) g[i][j][k] = maxn;
memset(cnt,,sizeof(cnt));
for(int j=i;j<=n;j++)
g[i][++cnt[val[j]]][val[j]] = j;
}
int ans = ;
for(int i=;i*<=n;i++)//长度
{
for(int j=;j<;j++)
for(int k=;k<=;k++)
dp[j][k] = maxn;
dp[][] = ; //从1开始
for(int j=;j<;j++)//选择方案
{
for(int k=;k<=;k++)//
{
if(dp[j][k]>n)continue;
for(int l=;l<;l++)
{
if((<<l)&j) continue;
Min(dp[j|(<<l)][k],g[dp[j][k]][i][l]+);
Min(dp[j|(<<l)][k+],g[dp[j][k]][i+][l]+);
}
}
}
for(int j=;j<=;j++) if(dp[][j]<n+){
Max(ans,j+*i);
}
}
printf("%d\n",ans);
return ;
}
状压DP