心得
总体感觉前7个题中规中矩，虽然dp苦手差点没想出来d咋做
后面的题偏难一些，有时间再补吧（咕咕咕）
题目
I - Cyclic Apple Strings（贪心）
把连续的0段往左换
#include<iostream>
#include<cstring>
#include<cstdio>
#include<vector>
#include<queue>
#include<vector>
using namespace std;
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define per(i,a,b) for(int i=(a);i>=(b);--i)
typedef long long ll;
typedef double db;
typedef pair<int,int> P;
#define fi first
#define se second
#define pb push_back
#define dbg(x) cerr<<(#x)<<":"<<x<<" ";
#define dbg2(x) cerr<<(#x)<<":"<<x<<endl;
#define SZ(a) (int)(a.size())
#define sci(a) scanf("%d",&(a))
#define pt(a) printf("%d",a);
#define pte(a) printf("%d\n",a)
#define ptlle(a) printf("%lld\n",a)
#define debug(...) fprintf(stderr, __VA_ARGS__)
const int N=2e5+10;
char s[N];
bool ok;
int ans,n;
int main(){
scanf("%s",s+1);
n=strlen(s+1);
rep(i,1,n){
if(s[i]==s[i-1])continue;
int v=s[i]-'0';
ok|=(v==1);
if(v==0)ans+=ok;
}
pte(ans);
return 0;
}K - Party Games（博弈）
可以结合1、2、3、4时的答案，
以及i%4==0时i^(i+1)^(i+2)^(i+3)=0的结论数学归纳
#include<iostream>
#include<cstring>
#include<cstdio>
#include<vector>
#include<queue>
#include<vector>
using namespace std;
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define per(i,a,b) for(int i=(a);i>=(b);--i)
typedef long long ll;
typedef double db;
typedef pair<int,int> P;
#define fi first
#define se second
#define pb push_back
#define dbg(x) cerr<<(#x)<<":"<<x<<" ";
#define dbg2(x) cerr<<(#x)<<":"<<x<<endl;
#define SZ(a) (int)(a.size())
#define sci(a) scanf("%d",&(a))
#define pt(a) printf("%d",a);
#define pte(a) printf("%d\n",a)
#define ptlle(a) printf("%lld\n",a)
#define debug(...) fprintf(stderr, __VA_ARGS__)
const int N=2e5+10;
int t,n;
int main(){
sci(t);
while(t--){
sci(n);
ll x=n%4;
if(x<=1)puts("Fluttershy");
else puts("Pinkie Pie");
}
return 0;
}B - Countless Me（贪心）
如果当前位需要至少n个数，那显然可以填当前位，
否则贪心，尝试一下当前位能否不填，看看后面的位填满够不够用，
如果填满够用的话，当前位就可以不填
否则当前位一定要填，实际能填的个数和n取min
#include<iostream>
#include<cstring>
#include<cstdio>
#include<vector>
#include<queue>
#include<vector>
using namespace std;
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define per(i,a,b) for(int i=(a);i>=(b);--i)
typedef long long ll;
typedef double db;
typedef pair<int,int> P;
#define fi first
#define se second
#define pb push_back
#define dbg(x) cerr<<(#x)<<":"<<x<<" ";
#define dbg2(x) cerr<<(#x)<<":"<<x<<endl;
#define SZ(a) (int)(a.size())
#define sci(a) scanf("%d",&(a))
#define pt(a) printf("%d",a);
#define pte(a) printf("%d\n",a)
#define ptlle(a) printf("%lld\n",a)
#define debug(...) fprintf(stderr, __VA_ARGS__)
const int N=2e5+10;
ll sum,ans;
int n,a[N];
int main(){
sci(n);
rep(i,1,n){
sci(a[i]);
sum+=a[i];
}
if(sum%n==0)ptlle(sum/n);
else{
per(i,30,0){
ll v=1<<i;
if(sum/v>=n){
ans+=v;
sum-=n*v;
}
else{
ll x=v-1;
if(sum<=1ll*n*x)continue;
ll cnt=min(1ll*n,sum/v);
ans+=v;
sum-=cnt*v;
}
}
ptlle(ans);
}
return 0;
}F - Custom-Made Clothes（二分 单调性）
这是个力扣原题，Leetcode378
下面的行是非严格递减的，所以一次二分最多检查2n个位置，满足50000次数的要求
#include<iostream>
#include<cstring>
#include<cstdio>
#include<vector>
#include<queue>
#include<vector>
using namespace std;
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define per(i,a,b) for(int i=(a);i>=(b);--i)
typedef long long ll;
typedef double db;
typedef pair<int,int> P;
#define fi first
#define se second
#define pb push_back
#define dbg(x) cerr<<(#x)<<":"<<x<<" ";
#define dbg2(x) cerr<<(#x)<<":"<<x<<endl;
#define SZ(a) (int)(a.size())
#define sci(a) scanf("%d",&(a))
#define pt(a) printf("%d",a);
#define pte(a) printf("%d\n",a)
#define ptlle(a) printf("%lld\n",a)
#define debug(...) fprintf(stderr, __VA_ARGS__)
const int N=2e5+10;
int n,k;
int ask(int i,int j,int x){
printf("? %d %d %d\n",i,j,x);
fflush(stdout);
int v;
sci(v);
return v;
}
void out(int x){
printf("! %d\n",x);
fflush(stdout);
}
int cal(int x){
int cur=n,ans=0;
rep(i,1,n){
while(cur>=1 && ask(i,cur,x)==0)cur--;
if(!cur)break;
ans+=cur;
}
return ans;
}
int main(){
sci(n),sci(k);
k=n*n-k+1;
int l=1,r=n*n;
while(l<=r){
int mid=(l+r)/2;
if(cal(mid)<k)l=mid+1;
else r=mid-1;
}
out(l);
return 0;
}E - Boomerang（树的直径性质）
对于一个确定结束谣言传播的时刻t，
记此时的树的直径为d，那么得在t之前选择直径中点开始止损，
需要满足2*(t-t0)>=d，
然后这个止损速度显然是有单调性的，
每一段连续速度区间对应一个止损时间，
所以可以不二分，双指针来跑
维护直径的话，每次只会新加一条边，
记原来的直径两端是u，v，本次加的边的远根端点是w，
直径只可能是uv、uw、vw三者其一
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define per(i,a,b) for(int i=(a);i>=(b);--i)
typedef long long ll;
typedef double db;
typedef pair<int,int> P;
#define fi first
#define se second
#define pb push_back
#define dbg(x) cerr<<(#x)<<":"<<x<<" ";
#define dbg2(x) cerr<<(#x)<<":"<<x<<endl;
#define SZ(a) (int)(a.size())
#define sci(a) scanf("%d",&(a))
#define pt(a) printf("%d",a);
#define pte(a) printf("%d\n",a)
#define ptlle(a) printf("%lld\n",a)
#define debug(...) fprintf(stderr, __VA_ARGS__)
const int N=2e5+10,M=18;
int n,a[N],u,v,r,t0,ans[N],dep[N],f[N][M],mx;
vector<int>e[N],d[N*2];
int lca(int x,int y){
if(dep[x]<dep[y])swap(x,y);
int d=dep[x]-dep[y];
for(int i=17;i>=0;--i)
if(d>>i&1)x=f[x][i];
if(x==y)return x;
for(int i=17;i>=0;--i){
if(f[x][i]!=f[y][i])
x=f[x][i],y=f[y][i];
}
return f[x][0];
}
int dis(int x,int y){
int g=lca(x,y);
return dep[x]+dep[y]-2*dep[g];
}
void dfs(int u,int fa){
for(auto &v:e[u]){
if(v==fa)continue;
dep[v]=dep[u]+1;
mx=max(mx,dep[v]);
f[v][0]=u;
rep(i,1,17){
f[v][i]=f[f[v][i-1]][i-1];
}
d[dep[v]].pb(v);
dfs(v,u);
}
}
int main(){
sci(n);
rep(i,2,n){
sci(u),sci(v);
e[u].pb(v);
e[v].pb(u);
}
sci(r),sci(t0);
dfs(r,0);
int p=r,q=r,now=0,cur=n;
rep(i,0,2*n){
for(auto &u:d[i]){
int wp=dis(p,u),wq=dis(q,u),ori=dis(p,q);
int big=max({wp,wq,ori});
if(wp==big)q=u;
else if(wq==big)p=u;
now=big;
}
int far=(now+1)/2;
if(i>=t0){
while(cur>=1 && 1ll*cur*(i-t0)>=far){
ans[cur]=i;
cur--;
}
}
}
rep(i,1,n){
printf("%d%c",ans[i]," \n"[i==n]);
}
return 0;
}
//dis<=D - ICPC（dp）
显然最优决策只有两种，
先往左（可以为空）之后一直往右
先往右（可以为空）之后一直往左
假设i-1是先走到了i-2，再走到了i，花了3步，获得了最大值
那么i可以效仿这个路线，先走到i-2，再走到i，花4步去更新最大值
也就是说需要多花i到i-1的这一步，但是没有额外的价值收益
直至这条路径被展平成i-2到i的路线，就可以直接由区间上的一段更新答案了
也就是对于这种先左再右存在走重复路线的行为，可以认为是走到左端点之后再走时才有贡献，
那么前面的步数纯属浪费，浪费1步从相邻点更新即可
用i+1更新i也是同理，所以可以多花1步从相邻的地方更新
此外，如果转移的方向反了的话，实际是应该少花步数
这里松弛一下，只用多花步数的这一种情况去更新答案，方向就是对的了，
换言之，能更新到最优解，且不会使最优解里有错解
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define per(i,a,b) for(int i=(a);i>=(b);--i)
typedef long long ll;
typedef double db;
typedef pair<int,int> P;
#define fi first
#define se second
#define pb push_back
#define dbg(x) cerr<<(#x)<<":"<<x<<" ";
#define dbg2(x) cerr<<(#x)<<":"<<x<<endl;
#define SZ(a) (int)(a.size())
#define sci(a) scanf("%d",&(a))
#define pt(a) printf("%d",a);
#define pte(a) printf("%d\n",a)
#define ptlle(a) printf("%lld\n",a)
#define debug(...) fprintf(stderr, __VA_ARGS__)
const int N=5e3+10,M=2*N;
typedef array<ll,3> A;
int n,a[N];
ll sum[N],dp[N][M],ans[N],res;
ll cal(int l,int r){return sum[r]-sum[l-1];}
int main(){
sci(n);
rep(i,1,n){
sci(a[i]);
sum[i]=sum[i-1]+a[i];
dp[i][0]=a[i];
}
rep(i,1,2*n){
rep(s,1,n){
dp[s][i]=max(dp[s][i],dp[s][i-1]);
if(s-i>=1)dp[s][i]=max(dp[s][i],cal(s-i,s));
if(s+i<=n)dp[s][i]=max(dp[s][i],cal(s,s+i));
if(s-1>=1)dp[s][i]=max(dp[s][i],dp[s-1][i-1]);
if(s+1<=n)dp[s][i]=max(dp[s][i],dp[s+1][i-1]);
ans[s]^=(1ll*i*dp[s][i]);
}
}
// rep(s,1,n){
// rep(i,1,2*n){
// printf("%lld ",dp[s][i]);
// }
// puts("");
// }
rep(s,1,n){
res^=(ans[s]+s);
}
ptlle(res);
return 0;
}M - Merge（贪心+递归）
注意到x和x+1（或者x和x-1）只能合出来奇数，合不出来偶数，
而一次合并至少需要一个偶数，
所以ai<=1e18时，最多只能合并到2e18，没有2e18的偶数可以再合了，long long足以
80 40 41 42这种肯定是先合81再合161，
但是为了防止后效性的连锁反应，应该先检查大偶数，也就是偶数从大到小检查
如果当前最大的奇数x，最大偶数y，满足x>y+1的话，奇数是不能再合的，直接取走
否则，对于y来说，
1. 检查一下2y+1能不能合，
2. 如果不能，再检查2y-1能不能合
3. 如果不能，就把y取走
map实时记录这个合并的过程，对于已经用完的数直接跳过
最后都取走时，说明不再存在合并了，将取出来的所有数再排个序即可
map写法
这个map写法跑了1.1s，改成umap反倒跑了1.6s，感觉可能刻意卡了一下umap
#include<bits/stdc++.h>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<vector>
#include<queue>
#include<vector>
#include<map>
#include<unordered_map>
using namespace std;
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define per(i,a,b) for(int i=(a);i>=(b);--i)
typedef long long ll;
typedef double db;
typedef pair<ll,int> P;
#define fi first
#define se second
#define pb push_back
#define dbg(x) cerr<<(#x)<<":"<<x<<" ";
#define dbg2(x) cerr<<(#x)<<":"<<x<<endl;
#define SZ(a) (int)(a.size())
#define sci(a) scanf("%d",&(a))
#define pt(a) printf("%d",a);
#define pte(a) printf("%d\n",a)
#define ptlle(a) printf("%lld\n",a)
#define debug(...) fprintf(stderr, __VA_ARGS__)
const int N=2e5+10;
int n,tot,c,num;
long long a[N];
ll even[N],odd[N],ans[N];
map<ll,int>cnt[2],tmp[2];
bool ok(ll w){
int b=w&1;
if(cnt[b].count(w) && cnt[b][w]>tmp[b][w]){
tmp[b][w]++;
return 1;
}
if(w==1 || w%2==0)return 0;
return ok(w/2) && ok(w-w/2);
}
int main(){
sci(n);
rep(i,1,n){
scanf("%lld",&a[i]);
cnt[a[i]&1][a[i]]++;
if(a[i]%2==0)even[++tot]=a[i];
else odd[++num]=a[i];
}
sort(even+1,even+tot+1,greater<ll>());
sort(odd+1,odd+num+1);
rep(j,1,tot){
ll vl=even[j];
if(!cnt[0].count(vl))continue;
while(num>=1){// 5 3 2
while(num>=1 && !cnt[1].count(odd[num]))num--;
if(num<1)break;
ll vr=odd[num];
if(vr>vl+1){
ans[++c]=vr;
cnt[1][vr]--;
if(!cnt[1][vr])cnt[1].erase(vr);
num--;
}
else{
break;
}
}
for(auto w:{2ll*vl+1,2ll*vl-1,vl}){
rep(i,0,1)tmp[i].clear();
if(ok(w)){
rep(i,0,1){
for(auto &x:tmp[i]){
cnt[i][x.fi]-=x.se;
if(!cnt[i][x.fi])cnt[i].erase(x.fi);
}
}
ans[++c]=w;
break;
}
}
}
rep(i,0,1){
for(auto &x:cnt[i]){
rep(j,1,x.se)ans[++c]=x.fi;
}
}
sort(ans+1,ans+c+1,greater<ll>());
pte(c);
rep(i,1,c){
printf("%lld%c",ans[i]," \n"[i==c]);
}
return 0;
}
/*
3
2 3 5
*/手动哈希写法
无所谓，哈希哥将绝杀
#include<bits/stdc++.h>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<vector>
#include<queue>
#include<vector>
#include<map>
#include<unordered_map>
using namespace std;
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define per(i,a,b) for(int i=(a);i>=(b);--i)
typedef long long ll;
typedef double db;
typedef pair<ll,int> P;
#define fi first
#define se second
#define pb push_back
#define dbg(x) cerr<<(#x)<<":"<<x<<" ";
#define dbg2(x) cerr<<(#x)<<":"<<x<<endl;
#define SZ(a) (int)(a.size())
#define sci(a) scanf("%d",&(a))
#define pt(a) printf("%d",a);
#define pte(a) printf("%d\n",a)
#define ptlle(a) printf("%lld\n",a)
#define debug(...) fprintf(stderr, __VA_ARGS__)
const int N=2e5+10,mod=19260817,S=2e5+10;
int n,tot,c,num;
ll a[N],even[N],odd[N],ans[N];
//map<ll,int>cnt[2],tmp[2];
struct node{
int head[mod],nex[S],cnt;
P b[S];
inline void upd(ll x,int v){
int u=x%mod;
for(int i=head[u];i;i=nex[i]){
if(b[i].fi==x){
b[i].se+=v;
return;
}
}
b[++cnt]=P(x,v);
nex[cnt]=head[u];
head[u]=cnt;
}
inline int operator[](ll x){
int u=x%mod;
for(int i=head[u];i;i=nex[i]){
if(b[i].fi==x)return b[i].se;
}
return 0;
}
inline void clear(){
rep(i,1,cnt)head[b[i].fi%mod]=0;
cnt=0;
}
}cnt[2],tmp[2];
bool ok(ll w){
int b=w&1;
if(cnt[b][w]>tmp[b][w]){
tmp[b].upd(w,1);
return 1;
}
if(w==1 || w%2==0)return 0;
return ok(w/2) && ok(w-w/2);
}
int main(){
sci(n);
rep(i,1,n){
scanf("%lld",&a[i]);
cnt[a[i]&1].upd(a[i],1);
if(a[i]%2==0)even[++tot]=a[i];
else odd[++num]=a[i];
}
sort(even+1,even+tot+1,greater<ll>());
sort(odd+1,odd+num+1);
rep(j,1,tot){
ll vl=even[j];
if(!cnt[0][vl])continue;
while(num>=1){// 5 3 2
while(num>=1 && !cnt[1][odd[num]])num--;
if(num<1)break;
ll vr=odd[num];
if(vr>vl+1){
ans[++c]=vr;
cnt[1].upd(vr,-1);
//if(!cnt[1][vr])cnt[1].erase(vr);
num--;
}
else{
break;
}
}
for(auto w:{2ll*vl+1,2ll*vl-1,vl}){
rep(i,0,1)tmp[i].clear();
if(ok(w)){
rep(i,0,1){
rep(j,1,tmp[i].cnt){
P &x=tmp[i].b[j];
cnt[i].upd(x.fi,-x.se);
//if(!cnt[i][x.fi])cnt[i].erase(x.fi);
}
}
ans[++c]=w;
break;
}
}
}
rep(i,0,1){
rep(j,1,cnt[i].cnt){
P &x=cnt[i].b[j];
rep(k,1,x.se)ans[++c]=x.fi;
}
}
sort(ans+1,ans+c+1,greater<ll>());
pte(c);
rep(i,1,c){
printf("%lld%c",ans[i]," \n"[i==c]);
}
return 0;
}
/*
3
2 3 5
*/
扫一扫
278
被折叠的 条评论
为什么被折叠?
到【灌水乐园】发言
