模拟赛
T1
简单题
离散化+差分即可
或者直接贪心
对可能成为答案的点计算删的区间并取min
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<iomanip>
#include<bits/stdc++.h>
#define int long long
#define jiaa(a,b) {a+=b;if(a>=MOD) a-=MOD;}
#define jian(a,b) {a-=b;if(a<0) a+=MOD;}
using namespace std;
int ksm(int a,int b,int p){if(b==0) return 1;if(b==1) return a%p;int c=ksm(a,b/2,p);c=c*c%p;if(b%2==1) c=c*a%p;return c%p;
}
inline int read()
{int x=0,f=1;char ch=getchar();while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}while (ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}return x*f;
}
int L[200005],R[200005],cnt,cn;
double p[800005],an[400005];
signed main()
{freopen("interval.in", "r", stdin);freopen("interval.out", "w", stdout);int T=read();while(T--){int n=read();cn=0;for(int i=1;i<=n;i++){L[i]=read();R[i]=read();an[++cn]=L[i];an[++cn]=R[i];}if(n<=1){cout<<-1<<'\n';continue;}sort(L+1,L+n+1);sort(R+1,R+n+1);sort(an+1,an+cn+1);cnt=0;for(int i=1;i<=cn;i++){p[++cnt]=1.0*an[i];if(i<cn) p[++cnt]=(an[i]+an[i+1])/2.0;}int minn=n;for(int i=1;i<=cnt;i++){int rsu=lower_bound(R+1,R+n+1,p[i])-R-1;int lsu=n-(upper_bound(L+1,L+n+1,p[i])-L-1);if(rsu&&lsu){minn=min(minn,n-rsu-lsu);}}if(minn>=n) cout<<-1<<'\n';else cout<<minn<<'\n';}return 0;
}
T2
猜结论
容易发现一开始答案为2^(n+m-1)
因为只要第一行第一列填满，剩余就全部确定了
具体的，a[i,j]=a[1,1]a[1,j]a[i,1]
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<iomanip>
#include<bits/stdc++.h>
#define int long long
#define jiaa(a,b) {a+=b;if(a>=MOD) a-=MOD;}
#define jian(a,b) {a-=b;if(a<0) a+=MOD;}
using namespace std;
int ksm(int a,int b,int p){if(b==0) return 1;if(b==1) return a%p;int c=ksm(a,b/2,p);c=c*c%p;if(b%2==1) c=c*a%p;return c%p;
}
inline int read()
{int x=0,f=1;char ch=getchar();while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}while (ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}return x*f;
}
const int MOD=1e9+7;
int ans,n,m,q,sec[600005];
int fa[600005],val[600005];
int find(int x){if(fa[x]==x) return x;int ff=find(fa[x]);val[x]^=val[fa[x]];fa[x]=ff;return ff;
}
int merge(int x,int y,int c){int fx=find(x);int fy=find(y);if(fx==fy){if((val[x]^val[y])!=c) return 2;else return 1;} fa[fx]=fy;val[fx]=val[y]^val[x]^c;return 0;
}
signed main()
{freopen("color.in", "r", stdin);freopen("color.out", "w", stdout);n=read(),m=read(),q=read();sec[0]=1;for(int i=1;i<=n+m;i++) sec[i]=sec[i-1]*2%MOD;ans=n+m-1;cout<<sec[ans]<<'\n';for(int i=1;i<=n+m;i++) fa[i]=i;while(q--){int x=read(),y=read(),c=read();int zh=merge(x,y+n,c);if(zh==2) ans=-1;else if(!zh){if(ans!=-1) ans--;} if(ans==-1) cout<<0<<'\n';else cout<<sec[ans]<<'\n';}return 0;
}