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:显然Ei和Ej相邻时最优,在固定Ei后Ek越靠后越优,双指针即可。然而我这个弱智硬是写了个分数规划+单调队列。
#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,所以即要最小化每天的标记数之和。显然其要大于给定的mi,当然令其为mi+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!!!!! }