Educational Codeforces Round 171 (Rated for Div. 2) A~E
A - Perpendicular Segments
找对角线
void solve()
{
cin>>n>>m>>k;
int t=min(n,m);
cout<<0<<" "<<0<<" "<<t<<" "<<t<<'\n';
cout<<t<<" "<<0<<" "<<0<<" "<<t<<'\n';
return ;
}B - Black Cells
模拟
int q[N];
bool check(int x)
{
if(n%2==0)
{
_rep(i,2,n)
{
if(q[i]-q[i-1]<=x)i++;
else return false;
}
return true;
}
else
{
if(n==1)return true;
_rep(i,1,n)
{
bool bl=true;
for(int j=1;j<=n-1;j+=2)
{
if(j==i){j--;continue;};
if(j+1==i)
{
if(q[j+2]-q[j]>x)
{
bl=false;
break;
}
}
else
{
if(q[j+1]-q[j]>x)
{
bl=false;
break;
}
}
}
if(bl)return true;
}
return false;
}
return true;
}
void solve()
{
cin>>n;
_rep(i,1,n)cin>>q[i];
int l=1,r=1e18;
while(l<r)
{
int mid=l+r>>1;
check(mid)?r=mid:l=mid+1;
}
cout<<l<<"\n";
return ;
}C - Action Figures
题意
给定一个长度为n的01序列,第i个点的价格是i,假设第i个点可以在i~n的任意时刻购买,并且如果一次性买了>=2个物品的话最贵的物品可以免费
思路
结合样例很快就可以发现
第i个点假如为0的话,那我不可避免的一定要花钱买i,为了使花费最少,也就是免费的物品的价格最高,那么我一定是尽可能找一个最右边的1来和这个0配对,然后使这个1对应的物品免费,用队列即可实现
所以从后往前遍历,遇到1就push,遇到0就看当前右边是否还有1(即queue的size是否>0),如果有就出队,然后出队的点就可以免费拿
注意的是,遍历完数组之后，假如队列的大小>=2说明我可以用数组中靠左边的1来免费拿靠右边的1,于是靠右边的1也免费
const int N=1e6+10,INF=4e18;
int n,m;
void solve()
{
deque<int>q;
cin>>n;
string s;
cin>>s;
int res=(n+1)*n/2;
_pre(i,(int)s.size()-1,0)
{
if(s[i]=='0')
{
if(q.size())res-=q.front(),q.pop_front();
}
else
q.pb(i+1);
}
while(q.size()>=2)
{
res-=q.front();
q.pop_back();
q.pop_front();
}
cout<<res<<'\n';
return ;
}D - Sums of Segments
题意
思路
可以发现根据这个图(假设n=6),可以把所有的前缀和分为六个块,每个块分别是6,5,4,3,2,1,第一个块的大小可以用前缀和的前缀和求出来,然后由第一个块可以推出第二个块(可以发现就是第一个元素*第一个块的行数),第二个块又可以推出第三个块,以此类推,那么我可以求出每个块的大小,那么L+1~R-1如果相差多个块,那么可以用块的前缀和O(1)求出,现在只需要求出L所在块(所在哪个块可以用二分找出)的下半部分,以及R所在块的上半部分即可,可以发现图中L所在块的下半部分,其实就是第一个块的4 5 6行减去第1个元素的值*3,也就是说这个下半部分也可以从第一块推出来(只不过要记录一下L实际上是在这个块中的第几个元素),R的上半部分计算同理,只需要推公式+利用一下前缀和以及前缀和的前缀和即可,要注意当L==R的时候,L的下半部分和R的上半部分相加其实是重复算了整个当前块的值,所以此时求得的答案减去这一块的值即可
#include<iostream>
#include<map>
#include<cmath>
#include<string>
#include<vector>
#include<cstring>
#include<algorithm>
#include<unordered_map>
#define pb push_back
#define fi first
#define se second
#define int long long
#define all(x) (x).begin(),(x).end()
#define _for(i, a) for(int i = 0; i < (a); ++i)
#define _rep(i, a, b) for(int i = (a);i <= (b); ++i)
#define IOS ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define u1 (u<<1)
#define u2 (u<<1|1)
//#define endl '\n'
using namespace std;
typedef pair<int,int> PII;
const int INF=0x3f3f3f3f;
const int P=1e9+7;
const int N=1e6+20,M=2*N;
int n,m,k,q[N];
int qian[N],qqian[N],row[N];
bool check(int x,int a)
{
int sum=n*(n+1)/2;
sum-=(n-x+1)*(n-x)/2;
return sum>=a;
}
int deal(int a)
{
int l=1,r=n;
while(l<r)
{
int mid=l+r>>1;
check(mid,a)?r=mid:l=mid+1;
}
return l;
}
void init()
{
_rep(i,1,n)
{
qqian[1]+=qian[i];
row[i]=row[i-1]+qian[i];
}
int sub=n;
_rep(i,2,n)
{
qqian[i]=qqian[i-1]-qqian[i-2]-q[i-1]*sub+qqian[i-1];
sub--;
}
}
int getkuai(int x,int id,int op)//块号,编号
{
int sum=n*(n+1)/2;
sum-=(n-x+2)*(n-x+1)/2;
int l,r;
if(op==1)
{
l=id-sum;//块内编号
r=n-x+1;//块内编号
}
else
{
l=1;
r=id-sum;
}
return row[r+x-1]-row[l+x-2]-(r-l+1)*qian[x-1];
}
void solve(){
cin>>n;
_rep(i,1,n)cin>>q[i],qian[i]=qian[i-1]+q[i];
init();
cin>>m;
while(m--)
{
int l,r;
cin>>l>>r;
int sum=0;
int a=deal(l),b=deal(r);
if(a+1<=b-1)sum+=qqian[b-1]-qqian[a];
sum+=getkuai(a,l,1);
sum+=getkuai(b,r,2);
if(a==b)sum-=qqian[a]-qqian[a-1];
cout<<sum<<'\n';
}
}
signed main(){
IOS;
int T=1;
// cin>>T;
_rep(i,1,T){
solve();
}
return 0;
}E - Best Subsequence
(个人感觉E<D)
题意
定义一个数组的'值'为数组长度减去数组所有元素或起来之后的二进制中1的个数，给定一个数组,问在这个数组中的所有子序列(包括自己)的最大'值'是多少
思路
根据样例可以发现一个规律
假设这个数组为{1,2,3},那么可以发现
以{1}为子序列,或起来之后的二进制中1的个数为1,数组长度为1
以{2}为子序列,或起来之后的二进制中1的个数为1,数组长度为1
以{3}为子序列,或起来之后的二进制中1的个数为2,数组长度为1('值'为-1)
以{1,2}为子序列,或起来之后的二进制中1的个数为2,数组长度为2
以{1,2,3}为子序列,或起来之后的二进制中1的个数为2,数组长度为3('值'为1,最优)
可以发现,当选一个数字作为子序列的一部分时候,这个数字如果贡献出来的1的个数<=1(假设为a),那么这个数字就可以使得数组长度+1,并且或起来之后的二进制中1的个数+a(a<=1)
如果以{3}为子序列,那么可以发现此时'值'为-1,比什么都不选的‘值‘0还要小,显然不会选3
但是如果以{1,2}为子序列,此时'值'为0,这个时候再选上3,可以发现这次选上这个3,贡献出来的1的个数=0,于是这个新子序列{1,2,3}的'值'就为1也就是3有贡献了
如何模拟这种3为负贡献的时候不选,然后3为正贡献的话就选(已经选定{1,2}之后再选3的情况)的这种场景呢
那就是让3占个'坑位',也就是让3随便占一个位置(前提是自己这一位二进制下为1才能占，而且不能有选择性的占而是随便占一个位置),这样随便占虽然说,这个占坑位的3贡献了一个二进制中1的个数和一个数组长度,那么'值'当然是不变的,但是这样占下去如果碰到下一个数字,它的每一位都被占用了,那么此时这个数字的贡献的1的个数就为1,那么'值'就可以+1
综上所述,可以让一个点随机占一个自己的某一位二进制位1下的位,然后接下来的点如果要占的点被前面的点占了，就让前面的点退而求其次找另一个自己二进制位1下的位的点(模拟这个随机占位的过程)，这个过程也就相当于是二分图的匹配,最后的最大值即为n-最大匹配数
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <cmath>
#include <vector>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <unordered_map>
using namespace std;
#define fi first
#define se second
#define u1 (u<<1)
#define u2 (u<<1|1)
#define pb push_back
#define pp pop_back()
#define int long long
#define laile cout<<"laile"<<endl
#define lowbit(x) ((x)&(-x))
#define double long double
#define sf(x) scanf("%lld",&x)
#define sff(x,y) scanf("%lld %lld",&x,&y)
#define sd(x) scanf("%Lf",&x)
#define sdd(x,y) scanf("%Lf %Lf",&x,&y)
#define _for(i,n) for(int i=0;i<(n);++i)
#define _rep(i,a,b) for(int i=(a);i<=(b);++i)
#define _pre(i,a,b) for(int i=(a);i>=(b);--i)
#define all(x) (x).begin(), (x).end()
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
typedef unsigned long long ULL;
typedef pair<int,int>PII;
typedef pair<double,double>PDD;
const int N=210,M=6010,INF=4e18;
int n,m;
int e[M],ne[M],h[N];
bool st[N];
int idx,mac[N];
void add(int a,int b){e[idx]=b;ne[idx]=h[a];h[a]=idx++;}
bool match(int u)
{
for(int i=h[u];i!=-1;i=ne[i])
{
int j=e[i];
if(!st[j])
{
st[j]=true;
if(!mac[j]||match(mac[j]))
{
mac[j]=u;
return true;
}
}
}
return false;
}
void solve()
{
cin>>n;
memset(h,-1,sizeof h);
memset(mac,0,sizeof mac);
idx=0;
_rep(i,1,n)
{
cin>>m;
_rep(j,0,60)
if(m>>j&1)
add(i,j+n+1);
}
int cnt=0;
_rep(i,1,n)
{
memset(st,false,sizeof(st));
if(match(i))cnt++;
}
cout<<n-cnt<<'\n';
return ;
}
signed main()
{
IOS;
int T=1;
cin>>T;
while(T--)
solve();
return 0;
}