前言
这里是1天之内写了6场vp的日总结
CF1557B Moamen and k-subarrays
按理说这种屑题应该猜个结论就上了……
结论为：直接考虑要分几段然后check
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<vector>
using namespace std;
int t,n,k,a[100005],b[100005],s;
bool cmp(int c,int b)
{
return a[c]<a[b];
}
int main()
{
scanf("%d",&t);
while (t--)
{
s=0;
scanf("%d%d",&n,&k);
for (int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
b[i]=i;
}
sort(b+1,b+1+n,cmp);
b[0]=-114514;
for (int i=1;i<=n;i++) if (b[i]!=b[i-1]+1) s++;
if (s>k) puts("NO");
else puts("YES");
}
return 0;
}
CF1557D Ezzat and Grid
考虑建边跑最长路。
那么首先对端点进行离散化，然后对于某个位置都为1的部分都选相邻的连边。
注意实现方式，严重影响时间复杂度。
#include<algorithm>
#include<iostream>
#include<cstring>
#include<vector>
#include<cstdio>
#include<queue>
#include<set>
using namespace std;
int n,m;
queue<int> q;
set<int> myd;
vector<pair<int,int> > wj[3000005],wj2[3000005],wj3[3000005];
int head[3000005],t,fr[3000005],su[3000005],vis[3000005],to[3000005],tot,nxt[3000005],b[6000006],lst[3000005],dis[3000005],top;
void add(int x,int y)
{
if (x==y) return;
to[++tot]=x;
nxt[tot]=head[y];
head[y]=tot;
return;
}
void bfs()
{
for (int i=1;i<=n;i++)
{
dis[i]=1;
fr[i]=i;
for (int j=head[i];j;j=nxt[j])
{
if (dis[to[j]]+1>dis[i]) dis[i]=dis[to[j]]+1,fr[i]=to[j];
}
if (dis[t]<dis[i]) t=i;
}
return;
}
int main()
{
pair<int,int> wjj;
scanf("%d%d",&n,&m);
for (int i=1;i<=m;i++)
{
int x,y,id;
scanf("%d%d%d",&id,&x,&y);
wj[id].push_back(make_pair(x,y));
b[++top]=x;
b[++top]=y;
}
sort(b+1,b+1+top);
for (int i=1;i<=n;i++)
{
for (int j=0;j<wj[i].size();j++)
{
wj[i][j].first=lower_bound(b+1,b+1+top,wj[i][j].first)-b;
wj[i][j].second=lower_bound(b+1,b+1+top,wj[i][j].second)-b;
wj2[wj[i][j].first].push_back({i,1});
wj3[wj[i][j].second+1].push_back({i,-1});
}
}
m=top;
for (int i=1;i<=m;i++)
{
int u=0;
for (u=0;u<wj3[i].size();u++)
{
pair<int,int> v=wj3[i][u];
su[v.first]+=v.second;
if (su[v.first]==0)
{
myd.erase(v.first);
}
}
u=0;
for (u=0;u<wj2[i].size();u++)
{
pair<int,int> v=wj2[i][u];
su[v.first]+=v.second;
if (su[v.first]==1)
{
if (myd.size()!=0)
{
set<int>::iterator it=myd.lower_bound(v.first);
if (it!=myd.end())
{
add(v.first,(*it));
}
if (it!=myd.begin())
{
it--;
add((*it),v.first);
}
}
myd.insert(v.first);
}
}
}
bfs();
cout<<n-dis[t]<<endl;
while (t!=fr[t])
{
vis[t]=1;
t=fr[t];
}
vis[t]=1;
for (int i=1;i<=n;i++) if (vis[i]==0) cout<<i<<' ';
return 0;
}
CF1492B Card Deck
这题猜个结论就好
结论为：尽量使结果字典序最大
#include<algorithm>
#include<iostream>
#include<cstring>
#include<vector>
#include<cstdio>
#include<queue>
#include<set>
using namespace std;
int n,t,a[100005];
int b[100005];
bool book[100005];
bool cmp(int c,int d)
{
return a[c]<a[d];
}
int main()
{
scanf("%d",&t);
while (t--)
{
scanf("%d",&n);
for (int i=1;i<=n;i++) scanf("%d",&a[i]),b[i]=i,book[i]=0;
sort(b+1,b+1+n,cmp);
int top=n,lz=n;
while (lz)
{
while (book[top]) top--;
for (int i=b[top];i<=lz;i++) printf("%d ",a[i]),book[a[i]]=1;
lz=b[top]-1;
}
puts("");
}
return 0;
}
CF1492D Genius’s Gambit
易得若有解，前b-1位必然相同，剩余2位的位置差为k
无解的情况有：在k≠0时，a=0,b=1,k>a+b-2都无解
#include<algorithm>
#include<iostream>
#include<cstring>
#include<vector>
#include<cstdio>
#include<queue>
#include<set>
using namespace std;
int n,t,a,b,k;
int main()
{
scanf("%d%d%d",&a,&b,&k);
if (k==0)
{
puts("Yes");
for (int i=1;i<=b;i++)
{
printf("1");
}
for (int i=1;i<=a;i++)
{
printf("0");
}
puts("");
for (int i=1;i<=b;i++)
{
printf("1");
}
for (int i=1;i<=a;i++)
{
printf("0");
}
return 0;
}
if (a==0||b==1||k>a+b-2)
{
printf("No\n");
return 0;
}
a--;
b-=2;
n=a;
t=b;
puts("Yes");
printf("11");
for (int i=1;i<=k-1;i++)
{
if (t)
{
t--;
printf("1");
}
else
{
n--;
printf("0");
}
}
printf("0");
for (int i=1;i<=a+b-k+1;i++)
{
if (t)
{
t--;
printf("1");
}
else
{
n--;
printf("0");
}
}
puts("");
n=a;
t=b;
printf("10");
for (int i=1;i<=k-1;i++)
{
if (t)
{
t--;
printf("1");
}
else
{
n--;
printf("0");
}
}
printf("1");
for (int i=1;i<=a+b-k+1;i++)
{
if (t)
{
t--;
printf("1");
}
else
{
n--;
printf("0");
}
}
return 0;
}
CF1095F Make It Connected
我们利用Kruskal思想，将
a
i
+
a
j
a_i+a_j
a
i
+
a
j
与给定边结合跑最小生成树即可。
#include<algorithm>
#include<iostream>
#include<cstring>
#include<vector>
#include<cstdio>
#include<queue>
#include<set>
using namespace std;
long long n,m,fa[200005],ans,v[200005],xx[200005];
struct f{
long long u,v,w;
} a[200005];
struct ff{
long long v,id;
} p;
bool operator <(const ff &a,const ff &b)
{
return a.v>b.v;
}
priority_queue<ff> wj;
bool cmp(f a,f b)
{
return a.w<b.w;
}
long long find(long long x)
{
if (x==fa[x]) return x;
return fa[x]=find(fa[x]);
}
int main()
{
scanf("%lld%lld",&n,&m);
for (long long i=1;i<=n;i++) scanf("%lld",&v[i]),fa[i]=i,xx[i]=i,p.v=v[i],p.id=i,wj.push(p);
for (long long i=1;i<=m;i++)
{
scanf("%lld%lld%lld",&a[i].u,&a[i].v,&a[i].w);
}
sort(a+1,a+1+m,cmp);
for (long long i=1,j=1;i<n;i++)
{
ff x=wj.top();
wj.pop();
ff y=wj.top();
wj.pop();
while (find(x.id)==find(y.id)) y=wj.top(),wj.pop();
while (j<=m&&find(a[j].u)==find(a[j].v)) j++;
if (j<=m&&a[j].w<x.v+y.v)
{
int fat=find(a[j].u),fb=find(a[j].v);
ans+=a[j].w;
fa[find(fat)]=find(fb);
p.id=find(fat),p.v=v[xx[fat]];
wj.push(p);
xx[find(fat)]=xx[fat];
wj.push(x);
wj.push(y);
}
else
{
int fat=find(x.id),fb=find(y.id);
ans+=x.v+y.v;
fa[find(fat)]=find(fb);
p.id=find(fat),p.v=x.v;
wj.push(p);
xx[find(fat)]=xx[fat];
}
}
cout<<ans;
return 0;
}
CF1296C Yet Another Walking Robot
STL大法好！
map直接上
#include<algorithm>
#include<iostream>
#include<cstring>
#include<vector>
#include<cstdio>
#include<map>
#include<string>
using namespace std;
int t,n,dx,dy,l,r,ans;
string x;
int main()
{
scanf("%d",&t);
while (t--)
{
scanf("%d",&n);
cin>>x;
dx=0,dy=0,ans=0x3f3f3f3f;
map<pair<int,int> ,int> au;
for(int i=0;i<n;i++)
{
if (x[i]=='U') ++dy;
if (x[i]=='D') --dy;
if (x[i]=='R') ++dx;
if (x[i]=='L') --dx;
if (au[make_pair(dx,dy)]||!dx&&!dy)
{
if (i-au[make_pair(dx,dy)]<ans)
{
ans=i-au[make_pair(dx,dy)];
l=au[make_pair(dx,dy)]+1;
r=i+1;
}
}
au[make_pair(dx,dy)]=i+1;
}
if (ans!=0x3f3f3f3f) printf("%d %d\n",l,r);
else puts("-1");
}
return 0;
}
CF1080B Margarite and the best present
直接前缀和吧，1min的水题
#include<algorithm>
#include<iostream>
#include<cstring>
#include<vector>
#include<cstdio>
#include<map>
#include<string>
using namespace std;
long long q,l,r;
long long ans;
long long sl(long long x)
{
if (x%2) return x/2-x;
return x/2;
}
int main()
{
cin>>q;
while (q--)
{
scanf("%lld%lld",&l,&r);
ans=sl(r)-sl(l-1);
printf("%lld\n",ans);
}
return 0;
}
CF1080D Olya and magical square
由初赛常识知，
(
4
32
−
1
)
/
3
>
1
0
18
(4^{32}-1)/3>10^{18}
(
4
3
2
−
1
)
/
3
>
1
0
1
8
，故当n>=32时，可以直接’yes’+n-1
接下来的部分不妨假设有解并枚举ans，对给定ans计算k的上下界，然后check即可
#include<algorithm>
#include<iostream>
#include<cstring>
#include<vector>
#include<cstdio>
#include<map>
#include<string>
using namespace std;
long long q,l,r,n,k,ans,wj[35];
int main()
{
cin>>q;
for (int i=1;i<=32;i++) wj[i]=wj[i-1]*4ll+1;
while (q--)
{
scanf("%lld%lld",&n,&k);
if (n>31)
{
printf("YES %lld\n",n-1);
continue;
}//2^31>1e18
for (ans=0;ans<n;ans++)
{
long long l=0;
for (long long j=1;j<=n-ans;j++) l+=(1ll<<j)-1;
if (l>k) continue;
long long r=wj[n]-((1ll<<(n-ans+1))-1)*wj[ans];
if (r<k) continue;
break;
}
if (ans==n) puts("NO");
else
{
printf("YES ");
printf("%lld\n",ans);
}
}
return 0;
}
CF1092B Teams Forming
一眼结论题
结论为：sort，然后相邻2个求差再求和
#include<algorithm>
#include<iostream>
#include<cstring>
#include<vector>
#include<cstdio>
#include<map>
#include<string>
using namespace std;
int n,a[200],s;
int main()
{
cin>>n;
for (int i=1;i<=n;i++) cin>>a[i];
sort(a+1,a+1+n);
for (int i=1;i<=n;i+=2) s+=a[i+1]-a[i];
cout<<s;
return 0;
}
CF1092D1 Great Vova Wall (Version 1)
按奇偶性划分，然后用栈进行扫描，最后栈的大小<2为YES
#include<algorithm>
#include<iostream>
#include<cstring>
#include<vector>
#include<cstdio>
#include<map>
#include<string>
using namespace std;
int n,a[200005],stak[200005],top;
int main()
{
cin>>n;
for (int i=1;i<=n;i++) scanf("%d",&a[i]),a[i]%=2;
for (int i=1;i<=n;i++)
{
stak[++top]=a[i];
if (top>1&&stak[top]==stak[top-1]) top-=2;
}
if (top<2) puts("YES");
else puts("NO");
return 0;
}
CF1092D2 Great Vova Wall (Version 2)
相比之前D1增加了一个限制。
所以我们在栈中进行抵消的时候就需要考虑是否出现栈大小大于2（也就是说有东西没抵消）的时候递增，这时由于新入栈的点更大，所以前面的就再也不可以抵消了
同时，如果最后栈里只剩1个，那么只有当其为max的时候才为YES
#include<algorithm>
#include<iostream>
#include<cstring>
#include<vector>
#include<cstdio>
#include<map>
#include<string>
using namespace std;
int n,a[200005],stak[200005],top,mx;
int main()
{
cin>>n;
for (int i=1;i<=n;i++) scanf("%d",&a[i]),mx=max(a[i],mx);
bool fl=0;
for (int i=1;i<=n;i++)
{
stak[++top]=a[i];
if (top>=2&&stak[top]==stak[top-1]) top-=2;
else if (top>=2&&stak[top-1]<stak[top]) fl=1,top--;
}
if (fl==0&&(top==0||top==1&&stak[top]==mx)) puts("YES");
else puts("NO");
return 0;
}