Codeforces Round #472 Div. 1

　　A：某个格子被染黑说明该行和该列同时被选中，使用并查集合并，最后看每个集合中是否有未被染黑的格子即可。

#include<iostream>

#include<cstdio>

#include<cmath>

#include<cstdlib>

#include<cstring>

#include<algorithm>

using namespace std;

#define ll long long

#define N 55

char getc(){char c=getchar();while (c!='.'&&c!='#') c=getchar();return c;}

int gcd(int n,int m){return m==0?n:gcd(m,n%m);}

int read()

{

	int x=0,f=1;char c=getchar();

	while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();}

	while (c>='0'&&c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar();

	return x*f;

}

int n,m,fa[N<<1],u[N],v[N];

char a[N][N];

void error(){cout<<"No";exit(0);}

int find(int x){return fa[x]==x?x:fa[x]=find(fa[x]);}

signed main()

{

#ifndef ONLINE_JUDGE

	freopen("a.in","r",stdin);

	freopen("a.out","w",stdout);

#endif

	n=read(),m=read();

	for (int i=1;i<=n+m;i++) fa[i]=i;

	for (int i=1;i<=n;i++)

		for (int j=1;j<=m;j++)

		{

			a[i][j]=getc();

			if (a[i][j]=='#') fa[find(j+n)]=find(i);

		}

	for (int i=1;i<=n+m;i++)

	{

		int p=0,q=0;

		for (int j=1;j<=n;j++)

		if (find(j)==i) u[++p]=j;

		for (int j=1;j<=m;j++)

		if (find(j+n)==i) v[++q]=j;

		for (int x=1;x<=p;x++)

			for (int y=1;y<=q;y++)

			if (a[u[x]][v[y]]=='.') error();

	}

	cout<<"Yes";

	return 0;

	//NOTICE LONG LONG!!!!!

}

　　B：显然E和E相邻时最优，在固定E后E越靠后越优，双指针即可。然而我这个弱智硬是写了个分数规划+单调队列。

#include<iostream>

#include<cstdio>

#include<cmath>

#include<cstdlib>

#include<cstring>

#include<algorithm>

using namespace std;

#define ll long long

#define N 100010

char getc(){char c=getchar();while (c!='.'&&c!='#') c=getchar();return c;}

int gcd(int n,int m){return m==0?n:gcd(m,n%m);}

int read()

{

	int x=0,f=1;char c=getchar();

	while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();}

	while (c>='0'&&c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar();

	return x*f;

}

int n,m,a[N],q[N];

long double calc(int j,long double k){return a[j]-a[j-1]*k;}

bool check(long double k)

{

	int head=1,tail=0;q[++tail]=2;

	for (int i=3;i<=n;i++)

	{

		while (a[q[head]-1]+m<a[i]&&head<=tail) head++;

		if (head<=tail&&a[i]*(1-k)>=calc(q[head],k)) return 1;

		while (head<=tail&&calc(i,k)<=calc(q[tail],k)) tail--;

		q[++tail]=i;

	}

	return 0;

}

signed main()

{

#ifndef ONLINE_JUDGE

	freopen("a.in","r",stdin);

	freopen("a.out","w",stdout);

#endif

	n=read(),m=read();

	for (int i=1;i<=n;i++) a[i]=read();

	bool flag=0;

	for (int i=1;i<n-1;i++) if (a[i+2]-a[i]<=m) {flag=1;break;}

	if (!flag) {cout<<-1;return 0;}

	long double l=0,r=1,ans;

	for (int i=1;i<=200;i++)

	{

		long double mid=(l+r)/2;

		if (check(mid)) ans=mid,l=mid;

		else r=mid;

	}

	double u=ans;printf("%.9f",u);

	return 0;

	//NOTICE LONG LONG!!!!!

}

　　C：严格小于=all-严格大于-1，所以即要最小化每天的标记数之和。显然其要大于给定的m，当然令其为m+1即最优。但同时每天最多添加一个标记，所以每个数还得对后一个数-1取max。

#include<iostream>

#include<cstdio>

#include<cmath>

#include<cstdlib>

#include<cstring>

#include<algorithm>

using namespace std;

#define ll long long

#define N 100010

char getc(){char c=getchar();while (c!='.'&&c!='#') c=getchar();return c;}

int gcd(int n,int m){return m==0?n:gcd(m,n%m);}

int read()

{

	int x=0,f=1;char c=getchar();

	while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();}

	while (c>='0'&&c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar();

	return x*f;

}

int n,a[N],b[N];

ll ans;

signed main()

{

#ifndef ONLINE_JUDGE

	freopen("a.in","r",stdin);

	freopen("a.out","w",stdout);

#endif

	n=read();

	for (int i=1;i<=n;i++) a[i]=read(),ans-=a[i]+1;

	for (int i=1;i<=n;i++) b[i]=max(b[i-1],a[i]+1);

	for (int i=n;i>=1;i--) b[i]=max(b[i],b[i+1]-1);

	for (int i=1;i<=n;i++) ans+=b[i];

	cout<<ans;

	return 0;

	//NOTICE LONG LONG!!!!!

}

　　D：显然到达原点的时间随风速的变化是一个单调函数，且拎出两个函数他们的大小关系也是单调的，于是只需要比较两端点的函数值即可。求出速度两个极限，数二维偏序数量就完了。卡精。

#include<iostream>

#include<cstdio>

#include<cmath>

#include<cstdlib>

#include<cstring>

#include<algorithm>

using namespace std;

#define ll long long

#define double long double

#define N 100010

#define lson tree[k].ch[0]

#define rson tree[k].ch[1]

char getc(){char c=getchar();while (c!='.'&&c!='#') c=getchar();return c;}

int gcd(int n,int m){return m==0?n:gcd(m,n%m);}

int read()

{

	int x=0,f=1;char c=getchar();

	while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();}

	while (c>='0'&&c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar();

	return x*f;

}

int n,m,cnt,root;

const double eps=1E-11;

ll ans;

struct data

{

	double x,y;

	bool operator <(const data&a) const

	{

		return x<a.x||fabs(x-a.x)<eps&&y>a.y;

	}

}a[N],b[N],c[N];

struct data2{double x;int ch[2],p,s;

}tree[N];

void up(int k){tree[k].s=tree[lson].s+tree[rson].s+1;}

void move(int &k,int p)

{

	int t=tree[k].ch[p];

	tree[k].ch[p]=tree[t].ch[!p],tree[t].ch[!p]=k,up(k),up(t),k=t;

}

void ins(int &k,double x)

{

	if (k==0){k=++cnt;tree[k].x=x;lson=rson=0;tree[k].p=rand();tree[k].s=1;return;}

	tree[k].s++;

	if (tree[k].x>x) {ins(lson,x);if (tree[lson].p>tree[k].p) move(k,0);}

	else {ins(rson,x);if (tree[rson].p>tree[k].p) move(k,1);}

}

int query(int k,double x)

{

	if (k==0) return 0;

	if (tree[k].x+eps<x) return query(rson,x);

	else return query(lson,x)+tree[rson].s+1;

}

void clear(){root=cnt=0;}

void solve(int l,int r)

{

	int t=0;

	for (int i=l;i<=r;i++) t++,c[t].x=-a[i].x/(a[i].y+m),c[t].y=-a[i].x/(a[i].y-m);

	sort(c+1,c+t+1);clear();

	for (int i=1;i<=t;i++)

	{

		ans+=query(root,c[i].y);

		ins(root,c[i].y);

	}

}

signed main()

{

#ifndef ONLINE_JUDGE

	freopen("a.in","r",stdin);

	freopen("a.out","w",stdout);

#endif

	srand(20020509);

	n=read(),m=read();

	for (int i=1;i<=n;i++) a[i].x=-read(),a[i].y=read();

	for (int i=1;i<=n;i++)

	{

		double x=a[i].x/(a[i].y+m),y=a[i].x/(a[i].y-m);

		a[i]=(data){x,y};

	}

	sort(a+1,a+n+1);

	for (int i=1;i<=n;i++)

	{

		ans+=query(root,a[i].y);

		ins(root,a[i].y);

	}

	cout<<ans;

	return 0;

	//NOTICE LONG LONG!!!!!

}

　　E：确定了哪些重要盒子放在顶部且不计入答案后，剩余的重要盒子看起来应该从大到小放置，但有一些比较麻烦的边界情况比如样例2。不妨将堆出来的塔翻转过来，这样就变成了要求顶部在范围内，问题就变得清新起来。于是先背包出不重要盒子的所有高度，然后将重要盒子从大到小排序，设f[i][j]为前i个重要盒子高度为j时的最优答案，转移显然，初值即仅对存在的不重要盒子集合高度设为0，其他设为-inf。

#include<iostream>

#include<cstdio>

#include<cmath>

#include<cstdlib>

#include<cstring>

#include<algorithm>

#include<bitset>

using namespace std;

#define ll long long

#define N 10010

char getc(){char c=getchar();while (c!='.'&&c!='#') c=getchar();return c;}

int gcd(int n,int m){return m==0?n:gcd(m,n%m);}

int read()

{

	int x=0,f=1;char c=getchar();

	while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();}

	while (c>='0'&&c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar();

	return x*f;

}

int n,m,l,r,u,v,a[N],b[N],c[N],f[N],ans;

bitset<N> F;

signed main()

{

#ifndef ONLINE_JUDGE

	freopen("a.in","r",stdin);

	freopen("a.out","w",stdout);

#endif

	n=read(),l=read(),r=read();

	for (int i=1;i<=n;i++) m+=c[i]=read();

	l=m-l,r=m-r;swap(l,r);

	for (int i=1;i<=n;i++) if (read()) a[++u]=c[i];else b[++v]=c[i];

	F[0]=1;

	for (int i=1;i<=v;i++)

	F|=F<<b[i];

	sort(a+1,a+u+1);reverse(a+1,a+u+1);

	memset(f,200,sizeof(f));for (int i=0;i<=10000;i++) if (F[i]) f[i]=0;

	for (int i=1;i<=u;i++)

		for (int j=10000;j>=a[i];j--)

		f[j]=max(f[j],f[j-a[i]]+(j>=l&&j<=r));

	for (int i=0;i<=10000;i++) ans=max(ans,f[i]);

	cout<<ans;

	return 0;

}